SI-6938 Use mutable red-black tree in TreeSet

The previous implementation of `mutable.TreeSet` uses a mutable reference to an immutable red-black tree as its underlying data structure. That leads to unnecessary objects being created, which can be a problem in systems with limited resources. It also has reduced performance when compared with common mutable implementations.

In this commit `mutable.TreeSet` is changed so that it uses the recently created `mutable.RedBlackTree` as its underlying data structure. Specialized red-black tree methods were created for working with keys for efficiency reasons. The new implementation is source-compatible with the previous one, although its serialized representation obviously changes.

Closes [SI-6938](https://issues.scala-lang.org/browse/SI-6938).

1 files changed, 18 insertions, 2 deletions

diff --git a/test/files/scalacheck/MutableTreeMap.scala b/test/files/scalacheck/MutableTreeMap.scala
index b072307a63..42b88c56a7 100644
--- a/test/files/scalacheck/MutableTreeMap.scala
+++ b/test/files/scalacheck/MutableTreeMap.scala
@@ -5,6 +5,7 @@ import org.scalacheck.Arbitrary._
 import org.scalacheck.Prop.forAll
 
 import scala.collection.generic.CanBuildFrom
+import scala.collection.immutable
 import scala.collection.mutable
 import scala.util.Try
 import scala.collection.mutable.{RedBlackTree => RB}
@@ -107,8 +108,9 @@ package scala.collection.mutable {
     }
 
     property("++=") = forAll { (map: mutable.TreeMap[K, V], entries: Seq[(K, V)]) =>
+      val oldEntries = map.toMap
       map ++= entries
-      entries.toMap.forall { case (k, v) => map.get(k) == Some(v) }
+      (oldEntries ++ entries).forall { case (k, v) => map.get(k) == Some(v) }
     }
 
     property("-=") = forAll { (map: mutable.TreeMap[K, V], k: K) =>
@@ -121,8 +123,10 @@ package scala.collection.mutable {
     }
 
     property("--=") = forAll { (map: mutable.TreeMap[K, V], ks: Seq[K]) =>
+      val oldElems = map.toList
       map --= ks
-      ks.toSet.forall { k => map.get(k) == None }
+      val deletedElems = ks.toSet
+      oldElems.forall { case (k, v) => map.get(k) == (if(deletedElems(k)) None else Some(v)) }
     }
 
     property("iterator") = forAll { (entries: Map[K, V]) =>
@@ -176,6 +180,18 @@ package scala.collection.mutable {
       val sameMap = in.readObject().asInstanceOf[mutable.TreeMap[K, V]]
       map.iterator.toSeq == sameMap.iterator.toSeq
     }
+
+    property("same behavior as immutable.TreeMap") = forAll { ops: Seq[Either[(K, V), K]] =>
+      var imap = immutable.TreeMap[K, V]()
+      val mmap = mutable.TreeMap[K, V]()
+
+      ops.foreach {
+        case Left((k, v)) => imap += k -> v; mmap += k -> v
+        case Right(k) => imap -= k; mmap -= k
+      }
+
+      imap.toList == mmap.toList
+    }
   }
 
   object MutableTreeMapViewProperties extends Properties("mutable.TreeMapView") with Generators {