Scala immutable SortedSet are not "stable" on deletion

Question

I've to deal with an immutable object in scala 2.7.5, and one of its member is an immutable Sortedset. I've no problem with addition, to synthetise, it gives:

class MyClass[A](s:SortedSet[A]) {
  ...
  def  + (elem:A):MyClass[A] {
    new MyClass(s + elem)
  }
}

And it works, since + operator is overload in trait sortedSet to return a SortedSet.

Unfortunately removing an element fails since - methos is not overloaded:

class MyClass[A](s:SortedSet[A]) {
  ...
  def  - (elem:A):MyClass[A] {
    new MyClass(s - elem) // Compiler error: (s - elem) is a Set[A]
  }
}

Does anyone knows how I can obtain a sorted set when i suppress an element knowing that: - I don't want to use a more specific kind of set like TreeSet. - I can't use a less specific trait as Set[A] instead of my SortedSet.

Answer 1

If you can wait until 2.8, it looks like this will work properly.

From SortedSetLike.scala (the super-trait of the immutable SortedSet trait)

trait SortedSetLike[A, +This <: SortedSet[A] with SortedSetLike[A, This]] extends Sorted[A, This] with SetLike[A, This]

This makes the This type a SortedSet. Then in SetLike.scala, the - operator's signature is

def - (elem: A): This

So will correctly return a SortedSet when used on a SortedSet.

Answer 2

I think all you need to do is cast it. "-" returns a Set but it is also a SortedSet. It may not be pretty but it works:

class MyClass[A](s:SortedSet[A]) {
    def  +(elem:A): MyClass[A] = {
      new MyClass(s + elem)
    }

    def  -(elem:A): MyClass[A] = {
      new MyClass((s - elem).asInstanceOf[SortedSet[A]])
    }

    override def toString = "sorted set = " + s
  }

  val a = new MyClass(new TreeSet[Int])
  println(a) // prints "sorted set = Set()"
  val b = a + 1
  println(b) // prints "sorted set = Set(1)"
  val c = a - 1
  println(c) // prints "sorted set = Set()"

Answer 3

Contrary to what one may think, - will not guarantee a SortedSet result. Small sets are optimized through different classes. Since Set's - is abstract, you don't know how it might be implemented, and a SortedSet is free to implement it in a way which returns a non-sorted set.

The following is inefficient, but it works. You can use it, live with asInstanceOf, or wait for 2.8. :-)

class MyClass[A](s: SortedSet[A]) {
  def -(elem: A)(implicit view: A => Ordered[A]): MyClass[A] = {
    new MyClass(TreeSet(s.toList - elem: _*))
  }
}