diff options
-rw-r--r-- | src/library/scala/collection/immutable/RedBlack.scala | 51 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/TreeMap.scala | 2 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/TreeSet.scala | 2 |
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) |