CODEWITHSUNDEEP
scala
netta
netta

Reputation: 518

Mutable Sorted Set in Scala doesn't work I expect (maybe I'm missing something)

Let's say you have the following:

case class Foo(x: Int, y: Int) extends Ordered[Foo] {
  override def compare(that: Foo): Int = x compareTo that.x
}

val mutableSet: scala.collection.mutable.SortedSet[Foo] =
    scala.collection.mutable.SortedSet(Foo(1, 2), Foo(1,3))

I expect the result of mutableSet.size to be 2. Why, Foo(1,2) and Foo(1,3) are not equal but they have the same ordering. So the sorted set should be (IMO) Foo(1,2), Foo(1,3). As this is the order they were created in (even the other way around would be fine, counter intuitive but fine).

However, the result of mutableSet.size is 1 and it saves the last value i.e. Foo(1,3). What am I missing?

Upvotes: 2

Views: 282

Answers (2)

Taky
Taky

Reputation: 5344

The behavior is similar to the Java SortedSet collections. SortedSet uses compareTo in order to define equality, thus it eliminates the same Foo case classes from your example.

In Scala 2.11 it uses scala.collection.TreeSet for the implementation SortedSet implementation. The best way to figure out this is to put breakpoint into your compareTo method.

TreeSet is implemented using AVL Tree data structure, you can inspect the behavior by looking into the AVLTree.scala insert method of the Node class. It compare compareTo result with 0 in order to figure out does it duplicated element in the collection.

Upvotes: 3

mattinbits
mattinbits

Reputation: 10428

You have overridden compare so that only the first field is used in comparison. The Set uses this compare function not just to sort the items but also to determine if the items are equal for the purpose of storing them in the Set.

Upvotes: 2

Related Questions