Use single shared Empty instance across all RedBlack trees.

3 files changed, 32 insertions, 23 deletions

diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 4069c86c57..fad4f7fd53 100644
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -15,7 +15,7 @@ package immutable
  *
  *  @since 2.3
  */
-@SerialVersionUID(8691885935445612921L)
+private[immutable]
 object RedBlack extends Serializable {
 
   private def blacken[A, B](t: Tree[A, B]): Tree[A, B] = t match {
@@ -25,7 +25,7 @@ object RedBlack extends Serializable {
   private def mkTree[A, B](isBlack: Boolean, k: A, v: B, l: Tree[A, B], r: Tree[A, B]) =
     if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)
 
-  abstract class Tree[A, +B] extends Serializable {
+  sealed abstract class Tree[A, +B] extends Serializable {
     def isEmpty: Boolean
     def isBlack: Boolean
     def lookup(x: A)(implicit ordering: Ordering[A]): Tree[A, B]
@@ -45,7 +45,7 @@ object RedBlack extends Serializable {
     def count : Int
     protected[immutable] def nth(n: Int): NonEmpty[A, B]
   }
-  abstract class NonEmpty[A, +B] extends Tree[A, B] with Serializable {
+  sealed abstract class NonEmpty[A, +B] extends Tree[A, B] with Serializable {
     def isEmpty = false
     def key: A
     def value: B
@@ -124,8 +124,8 @@ object RedBlack extends Serializable {
         case _ => RedTree(key, value, left, right.del(k))
       }
       def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = (tl, tr) match {
-        case (Empty(), t) => t
-        case (t, Empty()) => t
+        case (Empty.Instance, t) => t
+        case (t, Empty.Instance) => t
         case (RedTree(x, xv, a, b), RedTree(y, yv, c, d)) =>
           append(b, c) match {
             case RedTree(z, zv, bb, cc) => RedTree(z, zv, RedTree(x, xv, a, bb), RedTree(y, yv, cc, d))
@@ -147,8 +147,8 @@ object RedBlack extends Serializable {
       }
     }
 
-    def smallest: NonEmpty[A, B] = if (left.isEmpty) this else left.smallest
-    def greatest: NonEmpty[A, B] = if (right.isEmpty) this else right.greatest
+    def smallest: NonEmpty[A, B] = if (left  eq Empty.Instance) this else left.smallest
+    def greatest: NonEmpty[A, B] = if (right eq Empty.Instance) this else right.greatest
 
     def toStream: Stream[(A,B)] = iterator.toStream
 
@@ -168,8 +168,8 @@ object RedBlack extends Serializable {
       val newLeft = left.rng(from, None)
       val newRight = right.rng(None, until)
       if ((newLeft eq left) && (newRight eq right)) this
-      else if (newLeft.isEmpty) newRight.upd(key, value);
-      else if (newRight.isEmpty) newLeft.upd(key, value);
+      else if (newLeft eq Empty.Instance) newRight.upd(key, value);
+      else if (newRight eq Empty.Instance) newLeft.upd(key, value);
       else rebalance(newLeft, newRight)
     }
 
@@ -188,7 +188,7 @@ object RedBlack extends Serializable {
         val next = if (leftMost) zipper.head.left else zipper.head.right
         next match {
           case node: NonEmpty[_, _] => unzip(node :: zipper, leftMost)
-          case Empty()              => zipper
+          case _                    => zipper
         }
       }
 
@@ -207,12 +207,12 @@ object RedBlack extends Serializable {
           unzipBoth(left, r.left, leftZipper, r :: rightZipper, smallerDepth)
         case (l @ RedTree(_, _, _, _), _) =>
           unzipBoth(l.right, right, l :: leftZipper, rightZipper, smallerDepth)
-        case (Empty(), Empty()) =>
+        case (Empty.Instance, Empty.Instance) =>
           (Nil, true, false, smallerDepth)
-        case (Empty(), r @ BlackTree(_, _, _, _)) =>
+        case (Empty.Instance, r @ BlackTree(_, _, _, _)) =>
           val leftMost = true
           (unzip(r :: rightZipper, leftMost), false, leftMost, smallerDepth)
-        case (l @ BlackTree(_, _, _, _), Empty()) =>
+        case (l @ BlackTree(_, _, _, _), Empty.Instance) =>
           val leftMost = false
           (unzip(l :: leftZipper, leftMost), false, leftMost, smallerDepth)
       }
@@ -252,8 +252,8 @@ object RedBlack extends Serializable {
         zippedTree
       }
     }
-    def first = if (left .isEmpty) key else left.first
-    def last  = if (right.isEmpty) key else right.last
+    def first = if (left  eq Empty.Instance) key else left.first
+    def last  = if (right eq Empty.Instance) key else right.last
     val count = 1 + left.count + right.count
     protected[immutable] def nth(n: Int) = {
       if (n < left.count) left.nth(n)
@@ -261,7 +261,12 @@ object RedBlack extends Serializable {
       else this
     }
   }
-  case class Empty[A]() extends Tree[A, Nothing] {
+  object Empty {
+    def empty[A]: Tree[A, Nothing] = Instance.asInstanceOf[Tree[A, Nothing]]
+
+    val Instance: Tree[_ >: Nothing, Nothing] = Empty[Nothing]()
+  }
+  final case class Empty[A] private () extends Tree[A, Nothing] {
     def isEmpty = true
     def isBlack = true
     def lookup(k: A)(implicit ordering: Ordering[A]): Tree[A, Nothing] = this
@@ -279,14 +284,18 @@ object RedBlack extends Serializable {
     def last = throw new NoSuchElementException("empty map")
     def count = 0
     protected[immutable] def nth(n: Int) = throw new NoSuchElementException("empty map")
+
+    override def toString() = "Empty"
+
+    private def readResolve() = Empty.empty
   }
-  case class RedTree[A, +B](override val key: A,
+  final case class RedTree[A, +B](override val key: A,
                          override val value: B,
                          override val left: Tree[A, B],
                          override val right: Tree[A, B]) extends NonEmpty[A, B] {
     def isBlack = false
   }
-  case class BlackTree[A, +B](override val key: A,
+  final case class BlackTree[A, +B](override val key: A,
                            override val value: B,
                            override val left: Tree[A, B],
                            override val right: Tree[A, B]) extends NonEmpty[A, B] {
@@ -299,19 +308,19 @@ object RedBlack extends Serializable {
     override def hasNext: Boolean = !next.isEmpty
 
     override def next: (A, B) = next match {
-      case Empty() =>
+      case Empty.Instance =>
         throw new NoSuchElementException("next on empty iterator")
       case tree: NonEmpty[A, B] =>
         val result = (tree.key, tree.value)
         addLeftMostBranchToPath(tree.right)
-        next = if (path.isEmpty) Empty() else path.pop()
+        next = if (path.isEmpty) Empty.empty else path.pop()
         result
     }
 
     @annotation.tailrec
     private[this] def addLeftMostBranchToPath(tree: Tree[A, B]) {
       tree match {
-        case Empty() =>
+        case Empty.Instance =>
         case tree: NonEmpty[A, B] =>
           path.push(tree)
           addLeftMostBranchToPath(tree.left)
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index a13e78086b..bab60f06fb 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -61,7 +61,7 @@ class TreeMap[A, +B](override val size: Int, t: RedBlack.Tree[A, B])(implicit va
 
   def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)
 
-  protected val tree: RedBlack.Tree[A, B] = if (size == 0) Empty() else t
+  protected val tree: RedBlack.Tree[A, B] = if (size == 0) Empty.empty else t
 
   override def rangeImpl(from : Option[A], until : Option[A]): TreeMap[A,B] = {
     val ntree = tree.range(from,until)
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 8462ae5af3..2e6ba17749 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -103,7 +103,7 @@ class TreeSet[A](override val size: Int, t: RedBlack.Tree[A, Unit])
 
   def this()(implicit ordering: Ordering[A]) = this(0, null)(ordering)
 
-  protected val tree: RedBlack.Tree[A, Unit] = if (size == 0) Empty() else t
+  protected val tree: RedBlack.Tree[A, Unit] = if (size == 0) Empty.empty else t
 
   private def newSet(s: Int, t: RedBlack.Tree[A, Unit]) = new TreeSet[A](s, t)