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, 4 insertions, 2 deletions

diff --git a/test/junit/scala/collection/SetMapConsistencyTest.scala b/test/junit/scala/collection/SetMapConsistencyTest.scala
index 5f14af7c37..eb864a8449 100644
--- a/test/junit/scala/collection/SetMapConsistencyTest.scala
+++ b/test/junit/scala/collection/SetMapConsistencyTest.scala
@@ -190,7 +190,9 @@ class SetMapConsistencyTest {
   def boxMbs = new BoxMutableSet[Int, cm.BitSet](new cm.BitSet, "mutable.BitSet")
   
   def boxMhs[A] = new BoxMutableSet[A, cm.HashSet[A]](new cm.HashSet[A], "mutable.HashSet")
-  
+
+  def boxMts[A: Ordering] = new BoxMutableSet[A, cm.TreeSet[A]](new cm.TreeSet[A], "mutable.TreeSet")
+
   def boxJavaS[A] = new BoxMutableSet[A, cm.Set[A]]((new java.util.HashSet[A]).asScala, "java.util.HashSet") {
     override def adders = 3
     override def subbers = 1
@@ -354,7 +356,7 @@ class SetMapConsistencyTest {
   def churnIntSets() {
     val sets = Array[() => MapBox[Int]](
       () => boxMhm[Int], () => boxIhm[Int], () => boxJavaS[Int],
-      () => boxMbs, () => boxMhs[Int], () => boxIbs, () => boxIhs[Int], () => boxIls[Int], () => boxIts[Int]
+      () => boxMbs, () => boxMhs[Int], () => boxMts[Int], () => boxIbs, () => boxIhs[Int], () => boxIls[Int], () => boxIts[Int]
     )
     assert( sets.sliding(2).forall{ ms => churn(ms(0)(), ms(1)(), smallKeys, 1000, valuer = _ => 0) } )
   }