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).

4 files changed, 182 insertions, 54 deletions

diff --git a/src/library/scala/collection/mutable/RedBlackTree.scala b/src/library/scala/collection/mutable/RedBlackTree.scala
index a3be011ae2..e4793242bf 100644
--- a/src/library/scala/collection/mutable/RedBlackTree.scala
+++ b/src/library/scala/collection/mutable/RedBlackTree.scala
@@ -82,6 +82,11 @@ private[collection] object RedBlackTree {
     case node => Some((node.key, node.value))
   }
 
+  def minKey[A](tree: Tree[A, _]): Option[A] = minNode(tree.root) match {
+    case null => None
+    case node => Some(node.key)
+  }
+
   private def minNode[A, B](node: Node[A, B]): Node[A, B] =
     if (node eq null) null else minNodeNonNull(node)
 
@@ -93,6 +98,11 @@ private[collection] object RedBlackTree {
     case node => Some((node.key, node.value))
   }
 
+  def maxKey[A](tree: Tree[A, _]): Option[A] = maxNode(tree.root) match {
+    case null => None
+    case node => Some(node.key)
+  }
+
   private def maxNode[A, B](node: Node[A, B]): Node[A, B] =
     if (node eq null) null else maxNodeNonNull(node)
 
@@ -109,6 +119,12 @@ private[collection] object RedBlackTree {
       case node => Some((node.key, node.value))
     }
 
+  def minKeyAfter[A](tree: Tree[A, _], key: A)(implicit ord: Ordering[A]): Option[A] =
+    minNodeAfter(tree.root, key) match {
+      case null => None
+      case node => Some(node.key)
+    }
+
   private[this] def minNodeAfter[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = {
     if (node eq null) null
     else {
@@ -133,6 +149,12 @@ private[collection] object RedBlackTree {
       case node => Some((node.key, node.value))
     }
 
+  def maxKeyBefore[A](tree: Tree[A, _], key: A)(implicit ord: Ordering[A]): Option[A] =
+    maxNodeBefore(tree.root, key) match {
+      case null => None
+      case node => Some(node.key)
+    }
+
   private[this] def maxNodeBefore[A, B](node: Node[A, B], key: A)(implicit ord: Ordering[A]): Node[A, B] = {
     if (node eq null) null
     else {
@@ -411,6 +433,17 @@ private[collection] object RedBlackTree {
     if (node.right ne null) foreachNodeNonNull(node.right, f)
   }
 
+  def foreachKey[A, U](tree: Tree[A, _], f: A => U): Unit = foreachNodeKey(tree.root, f)
+
+  private[this] def foreachNodeKey[A, U](node: Node[A, _], f: A => U): Unit =
+    if (node ne null) foreachNodeKeyNonNull(node, f)
+
+  private[this] def foreachNodeKeyNonNull[A, U](node: Node[A, _], f: A => U): Unit = {
+    if (node.left ne null) foreachNodeKeyNonNull(node.left, f)
+    f(node.key)
+    if (node.right ne null) foreachNodeKeyNonNull(node.right, f)
+  }
+
   def transform[A, B](tree: Tree[A, B], f: (A, B) => B): Unit = transformNode(tree.root, f)
 
   private[this] def transformNode[A, B, U](node: Node[A, B], f: (A, B) => B): Unit =
diff --git a/src/library/scala/collection/mutable/SortedSet.scala b/src/library/scala/collection/mutable/SortedSet.scala
index 0f2fa75abd..3dee57eb6d 100644
--- a/src/library/scala/collection/mutable/SortedSet.scala
+++ b/src/library/scala/collection/mutable/SortedSet.scala
@@ -48,3 +48,6 @@ object SortedSet extends MutableSortedSetFactory[SortedSet] {
   def empty[A](implicit ord: Ordering[A]): SortedSet[A] = TreeSet.empty[A]
 
 }
+
+/** Explicit instantiation of the `SortedSet` trait to reduce class file size in subclasses. */
+abstract class AbstractSortedSet[A] extends scala.collection.mutable.AbstractSet[A] with SortedSet[A]
diff --git a/src/library/scala/collection/mutable/TreeMap.scala b/src/library/scala/collection/mutable/TreeMap.scala
index b96cef5bee..dc7d5d750e 100644
--- a/src/library/scala/collection/mutable/TreeMap.scala
+++ b/src/library/scala/collection/mutable/TreeMap.scala
@@ -52,6 +52,20 @@ sealed class TreeMap[A, B] private (tree: RB.Tree[A, B])(implicit val ordering:
   override def empty = TreeMap.empty
   override protected[this] def newBuilder = TreeMap.newBuilder[A, B]
 
+  /**
+   * Creates a ranged projection of this map. Any mutations in the ranged projection will update the original map and
+   * vice versa.
+   *
+   * Only entries with keys between this projection's key range will ever appear as elements of this map, independently
+   * of whether the entries are added through the original map or through this view. That means that if one inserts a
+   * key-value in a view whose key is outside the view's bounds, calls to `get` or `contains` will _not_ consider the
+   * newly added entry. Mutations are always reflected in the original map, though.
+   *
+   * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower
+   *             bound.
+   * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper
+   *              bound.
+   */
   def rangeImpl(from: Option[A], until: Option[A]): TreeMap[A, B] = new TreeMapView(from, until)
 
   def -=(key: A): this.type = { RB.delete(tree, key); this }
@@ -157,10 +171,15 @@ sealed class TreeMap[A, B] private (tree: RB.Tree[A, B])(implicit val ordering:
       }
     }
 
+    // Using the iterator should be efficient enough; if performance is deemed a problem later, specialized
+    // `foreach(f, from, until)` and `transform(f, from, until)` methods can be created in `RedBlackTree`. See
+    // https://github.com/scala/scala/pull/4608#discussion_r34307985 for a discussion about this.
     override def foreach[U](f: ((A, B)) => U): Unit = iterator.foreach(f)
     override def transform(f: (A, B) => B) = {
       iterator.foreach { case (key, value) => update(key, f(key, value)) }
       this
     }
+
+    override def clone() = super.clone().rangeImpl(from, until)
   }
 }
diff --git a/src/library/scala/collection/mutable/TreeSet.scala b/src/library/scala/collection/mutable/TreeSet.scala
index f849eea569..ada6f145ad 100644
--- a/src/library/scala/collection/mutable/TreeSet.scala
+++ b/src/library/scala/collection/mutable/TreeSet.scala
@@ -11,8 +11,7 @@ package collection
 package mutable
 
 import generic._
-import scala.collection.immutable.{RedBlackTree => RB}
-import scala.runtime.ObjectRef
+import scala.collection.mutable.{RedBlackTree => RB}
 
 /**
  * @define Coll `mutable.TreeSet`
@@ -29,88 +28,162 @@ object TreeSet extends MutableSortedSetFactory[TreeSet] {
    */
   def empty[A](implicit ordering: Ordering[A]) = new TreeSet[A]()
 
+  /** $sortedMapCanBuildFromInfo */
+  implicit def canBuildFrom[A](implicit ord: Ordering[A]): CanBuildFrom[Coll, A, TreeSet[A]] =
+    new SortedSetCanBuildFrom[A]
 }
 
 /**
- * A mutable SortedSet using an immutable RedBlack Tree as underlying data structure.
+ * A mutable sorted set implemented using a mutable red-black tree as underlying data structure.
  *
- * @author Lucien Pereira
+ * @param ordering the implicit ordering used to compare objects of type `A`.
+ * @tparam A the type of the keys contained in this tree set.
+ *
+ * @author Rui Gonçalves
+ * @version 2.12
+ * @since 2.10
  *
+ * @define Coll mutable.TreeSet
+ * @define coll mutable tree set
  */
-@deprecatedInheritance("TreeSet is not designed to enable meaningful subclassing.", "2.11.0")
-class TreeSet[A] private (treeRef: ObjectRef[RB.Tree[A, Null]], from: Option[A], until: Option[A])(implicit val ordering: Ordering[A])
-  extends SortedSet[A] with SetLike[A, TreeSet[A]]
-  with SortedSetLike[A, TreeSet[A]] with Set[A] with Serializable {
+// Original API designed in part by Lucien Pereira
+@SerialVersionUID(-3642111301929493640L)
+sealed class TreeSet[A] private (tree: RB.Tree[A, Null])(implicit val ordering: Ordering[A])
+  extends AbstractSortedSet[A]
+  with SortedSet[A]
+  with SetLike[A, TreeSet[A]]
+  with SortedSetLike[A, TreeSet[A]]
+  with Serializable {
 
   if (ordering eq null)
     throw new NullPointerException("ordering must not be null")
 
-  def this()(implicit ordering: Ordering[A]) = this(new ObjectRef(null), None, None)
+  /**
+   * Creates an empty `TreeSet`.
+   * @param ord the implicit ordering used to compare objects of type `A`.
+   * @return an empty `TreeSet`.
+   */
+  def this()(implicit ord: Ordering[A]) = this(RB.Tree.empty)(ord)
 
-  override def size: Int = RB.countInRange(treeRef.elem, from, until)
+  override def empty = TreeSet.empty
+  override protected[this] def newBuilder = TreeSet.newBuilder[A]
 
-  override def stringPrefix = "TreeSet"
+  /**
+   * Creates a ranged projection of this set. Any mutations in the ranged projection affect will update the original set
+   * and vice versa.
+   *
+   * Only keys between this projection's key range will ever appear as elements of this set, independently of whether
+   * the elements are added through the original set or through this view. That means that if one inserts an element in
+   * a view whose key is outside the view's bounds, calls to `contains` will _not_ consider the newly added element.
+   * Mutations are always reflected in the original set, though.
+   *
+   * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower
+   *             bound.
+   * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper
+   *              bound.
+   */
+  def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = new TreeSetView(from, until)
 
-  override def empty: TreeSet[A] = TreeSet.empty
+  def -=(key: A): this.type = { RB.delete(tree, key); this }
+  def +=(elem: A): this.type = { RB.insert(tree, elem, null); this }
 
-  private def pickBound(comparison: (A, A) => A, oldBound: Option[A], newBound: Option[A]) = (newBound, oldBound) match {
-    case (Some(newB), Some(oldB)) => Some(comparison(newB, oldB))
-    case (None, _) => oldBound
-    case _ => newBound
-  }
+  def contains(elem: A) = RB.contains(tree, elem)
 
-  override def rangeImpl(fromArg: Option[A], untilArg: Option[A]): TreeSet[A] = {
-    val newFrom = pickBound(ordering.max, fromArg, from)
-    val newUntil = pickBound(ordering.min, untilArg, until)
+  def iterator = RB.keysIterator(tree)
+  def keysIteratorFrom(start: A) = RB.keysIterator(tree, Some(start))
+  override def iteratorFrom(start: A) = RB.keysIterator(tree, Some(start))
 
-    new TreeSet(treeRef, newFrom, newUntil)
-  }
+  override def size = RB.size(tree)
+  override def isEmpty = RB.isEmpty(tree)
 
-  override def -=(elem: A): this.type = {
-    treeRef.elem = RB.delete(treeRef.elem, elem)
-    this
-  }
+  override def head = RB.minKey(tree).get
+  override def headOption = RB.minKey(tree)
+  override def last = RB.maxKey(tree).get
+  override def lastOption = RB.maxKey(tree)
 
-  override def +=(elem: A): this.type = {
-    treeRef.elem = RB.update(treeRef.elem, elem, null, overwrite = false)
-    this
-  }
+  override def foreach[U](f: A => U): Unit = RB.foreachKey(tree, f)
+  override def clear(): Unit = RB.clear(tree)
+
+  override def stringPrefix = "TreeSet"
 
   /**
-   * Thanks to the immutable nature of the
-   * underlying Tree, we can share it with
-   * the clone. So clone complexity in time is O(1).
+   * A ranged projection of a [[TreeSet]]. Mutations on this set affect the original set and vice versa.
    *
+   * Only keys between this projection's key range will ever appear as elements of this set, independently of whether
+   * the elements are added through the original set or through this view. That means that if one inserts an element in
+   * a view whose key is outside the view's bounds, calls to `contains` will _not_ consider the newly added element.
+   * Mutations are always reflected in the original set, though.
+   *
+   * @param from the lower bound (inclusive) of this projection wrapped in a `Some`, or `None` if there is no lower
+   *             bound.
+   * @param until the upper bound (exclusive) of this projection wrapped in a `Some`, or `None` if there is no upper
+   *              bound.
    */
-  override def clone(): TreeSet[A] =
-    new TreeSet[A](new ObjectRef(treeRef.elem), from, until)
-
-  private val notProjection = !(from.isDefined || until.isDefined)
+  @SerialVersionUID(7087824939194006086L)
+  private[this] final class TreeSetView(from: Option[A], until: Option[A]) extends TreeSet[A](tree) {
+
+    /**
+     * Given a possible new lower bound, chooses and returns the most constraining one (the maximum).
+     */
+    private[this] def pickLowerBound(newFrom: Option[A]): Option[A] = (from, newFrom) match {
+      case (Some(fr), Some(newFr)) => Some(ordering.max(fr, newFr))
+      case (None, _) => newFrom
+      case _ => from
+    }
 
-  override def contains(elem: A): Boolean = {
-    def leftAcceptable: Boolean = from match {
-      case Some(lb) => ordering.gteq(elem, lb)
-      case _ => true
+    /**
+     * Given a possible new upper bound, chooses and returns the most constraining one (the minimum).
+     */
+    private[this] def pickUpperBound(newUntil: Option[A]): Option[A] = (until, newUntil) match {
+      case (Some(unt), Some(newUnt)) => Some(ordering.min(unt, newUnt))
+      case (None, _) => newUntil
+      case _ => until
     }
 
-    def rightAcceptable: Boolean = until match {
-      case Some(ub) => ordering.lt(elem, ub)
-      case _ => true
+    /**
+     * Returns true if the argument is inside the view bounds (between `from` and `until`).
+     */
+    private[this] def isInsideViewBounds(key: A): Boolean = {
+      val afterFrom = from.isEmpty || ordering.compare(from.get, key) <= 0
+      val beforeUntil = until.isEmpty || ordering.compare(key, until.get) < 0
+      afterFrom && beforeUntil
     }
 
-    (notProjection || (leftAcceptable && rightAcceptable)) &&
-      RB.contains(treeRef.elem, elem)
-  }
+    override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] =
+      new TreeSetView(pickLowerBound(from), pickUpperBound(until))
+
+    override def contains(key: A) = isInsideViewBounds(key) && RB.contains(tree, key)
+
+    override def iterator = RB.keysIterator(tree, from, until)
+    override def keysIteratorFrom(start: A) = RB.keysIterator(tree, pickLowerBound(Some(start)), until)
+    override def iteratorFrom(start: A) = RB.keysIterator(tree, pickLowerBound(Some(start)), until)
 
-  override def iterator: Iterator[A] = iteratorFrom(None)
+    override def size = iterator.length
+    override def isEmpty = !iterator.hasNext
 
-  override def keysIteratorFrom(start: A) = iteratorFrom(Some(start))
+    override def head = headOption.get
+    override def headOption = {
+      val elem = if (from.isDefined) RB.minKeyAfter(tree, from.get) else RB.minKey(tree)
+      (elem, until) match {
+        case (Some(e), Some(unt)) if ordering.compare(e, unt) >= 0 => None
+        case _ => elem
+      }
+    }
 
-  private def iteratorFrom(start: Option[A]) = {
-    val it = RB.keysIterator(treeRef.elem, pickBound(ordering.max, from, start))
-    until match {
-      case None => it
-      case Some(ub) => it takeWhile (k => ordering.lt(k, ub))
+    override def last = lastOption.get
+    override def lastOption = {
+      val elem = if (until.isDefined) RB.maxKeyBefore(tree, until.get) else RB.maxKey(tree)
+      (elem, from) match {
+        case (Some(e), Some(fr)) if ordering.compare(e, fr) < 0 => None
+        case _ => elem
+      }
     }
+
+    // Using the iterator should be efficient enough; if performance is deemed a problem later, a specialized
+    // `foreachKey(f, from, until)` method can be created in `RedBlackTree`. See
+    // https://github.com/scala/scala/pull/4608#discussion_r34307985 for a discussion about this.
+    override def foreach[U](f: A => U): Unit = iterator.foreach(f)
+
+    override def clone() = super.clone().rangeImpl(from, until)
   }
 }