Use null to represent empty trees. Removed Empty/NonEmpty classes.

4 files changed, 367 insertions, 404 deletions

diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 3b16f719bf..2537d043fd 100644
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -11,6 +11,8 @@
 package scala.collection
 package immutable
 
+import annotation.meta.getter
+
 /** An object containing the RedBlack tree implementation used by for `TreeMaps` and `TreeSets`.
  *
  *  @since 2.3
@@ -18,389 +20,354 @@ package immutable
 private[immutable]
 object RedBlack {
 
-  private def blacken[A, B](t: Tree[A, B]): Tree[A, B] = t.black
+  private def blacken[A, B](t: Tree[A, B]): Tree[A, B] = if (t eq null) null else t.black
 
   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)
-  def isRedTree[A, B](tree: Tree[A, B]) = tree.isInstanceOf[RedTree[_, _]]
+
+  def isBlack(tree: Tree[_, _]) = (tree eq null) || isBlackTree(tree)
+  def isRedTree(tree: Tree[_, _]) = tree.isInstanceOf[RedTree[_, _]]
   def isBlackTree(tree: Tree[_, _]) = tree.isInstanceOf[BlackTree[_, _]]
 
+  def isEmpty(tree: Tree[_, _]): Boolean = tree eq null
+
+  def contains[A](tree: Tree[A, _], x: A)(implicit ordering: Ordering[A]): Boolean = lookup(tree, x) ne null
+  def get[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Option[B] = lookup(tree, x) match {
+    case null => None
+    case tree => Some(tree.value)
+  }
+
   @annotation.tailrec
-  def lookup[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq Empty.Instance) tree else {
-      val cmp = ordering.compare(x, tree.key)
-      if (cmp < 0) lookup(tree.left, x)
-      else if (cmp > 0) lookup(tree.right, x)
-      else tree
+  def lookup[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
+    val cmp = ordering.compare(x, tree.key)
+    if (cmp < 0) lookup(tree.left, x)
+    else if (cmp > 0) lookup(tree.right, x)
+    else tree
   }
-  sealed abstract class Tree[A, +B] extends Serializable {
-    def key: A
-    def value: B
-    def left: Tree[A, B]
-    def right: Tree[A, B]
-    def isEmpty: Boolean
-    def isBlack: Boolean
-    def lookup(x: A)(implicit ordering: Ordering[A]): Tree[A, B]
-    def update[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(k, v))
-    def delete(k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(k))
-    def range(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = blacken(rng(from, until))
-    def foreach[U](f: ((A, B)) =>  U)
-    def foreachKey[U](f: A =>  U)
-    def iterator: Iterator[(A, B)]
-    def keyIterator: Iterator[A]
-    def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1]
-    def del(k: A)(implicit ordering: Ordering[A]): Tree[A, B]
-    def smallest: NonEmpty[A, B]
-    def greatest: NonEmpty[A, B]
-    def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B]
-    def first : A
-    def last : A
-    def count : Int
-    protected[immutable] def nth(n: Int): NonEmpty[A, B]
-    def black: Tree[A, B] = this
-    def red: Tree[A, B]
+
+  def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count
+  def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v))
+  def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k))
+  def range[A, B](tree: Tree[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = blacken(rng(tree, from, until))
+
+  def smallest[A, B](tree: Tree[A, B]): Tree[A, B] = {
+    if (tree eq null) throw new NoSuchElementException("empty map")
+    var result = tree
+    while (result.left ne null) result = result.left
+    result
   }
-  sealed abstract class NonEmpty[A, +B](final val key: A, final val value: B, final val left: Tree[A, B], final val right: Tree[A, B]) extends Tree[A, B] with Serializable {
-    def isEmpty = false
-    def lookup(k: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
-      val cmp = ordering.compare(k, key)
-      if (cmp < 0) left.lookup(k)
-      else if (cmp > 0) right.lookup(k)
-      else this
-    }
-    private[this] def balanceLeft[B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[A, B1], d: Tree[A, B1])/*: NonEmpty[A, B1]*/ = {
-      if (isRedTree(l) && isRedTree(l.left))
-        RedTree(l.key, l.value, BlackTree(l.left.key, l.left.value, l.left.left, l.left.right), BlackTree(z, zv, l.right, d))
-      else if (isRedTree(l) && isRedTree(l.right))
-        RedTree(l.right.key, l.right.value, BlackTree(l.key, l.value, l.left, l.right.left), BlackTree(z, zv, l.right.right, d))
-      else
-        mkTree(isBlack, z, zv, l, d)
-    }
-    private[this] def balanceRight[B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[A, B1], r: Tree[A, B1])/*: NonEmpty[A, B1]*/ = {
-      if (isRedTree(r) && isRedTree(r.left))
-        RedTree(r.left.key, r.left.value, BlackTree(x, xv, a, r.left.left), BlackTree(r.key, r.value, r.left.right, r.right))
-      else if (isRedTree(r) && isRedTree(r.right))
-        RedTree(r.key, r.value, BlackTree(x, xv, a, r.left), BlackTree(r.right.key, r.right.value, r.right.left, r.right.right))
-      else
-        mkTree(isBlack, x, xv, a, r)
-    }
-    def upd[B1 >: B](k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = {
-      val cmp = ordering.compare(k, key)
-      if (cmp < 0) balanceLeft(isBlack, key, value, left.upd(k, v), right)
-      else if (cmp > 0) balanceRight(isBlack, key, value, left, right.upd(k, v))
-      else mkTree(isBlack, k, v, left, right)
-    }
+  def greatest[A, B](tree: Tree[A, B]): Tree[A, B] = {
+    if (tree eq null) throw new NoSuchElementException("empty map")
+    var result = tree
+    while (result.right ne null) result = result.right
+    result
+  }
+
+  def foreach[A, B, U](tree: Tree[A, B], f: ((A, B)) => U): Unit = if (tree ne null) {
+    foreach(tree.left, f)
+    f((tree.key, tree.value))
+    foreach(tree.right, f)
+  }
+  def foreachKey[A, U](tree: Tree[A, _], f: A => U): Unit = if (tree ne null) {
+    foreachKey(tree.left, f)
+    f(tree.key)
+    foreachKey(tree.right, f)
+  }
+
+  def iterator[A, B](tree: Tree[A, B]): Iterator[(A, B)] = if (tree eq null) Iterator.empty else new TreeIterator(tree)
+  def keyIterator[A, _](tree: Tree[A, _]): Iterator[A] = if (tree eq null) Iterator.empty else new TreeKeyIterator(tree)
+
+  private[this] def balanceLeft[A, B, B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[A, B1], d: Tree[A, B1]): Tree[A, B1] = {
+    if (isRedTree(l) && isRedTree(l.left))
+      RedTree(l.key, l.value, BlackTree(l.left.key, l.left.value, l.left.left, l.left.right), BlackTree(z, zv, l.right, d))
+    else if (isRedTree(l) && isRedTree(l.right))
+      RedTree(l.right.key, l.right.value, BlackTree(l.key, l.value, l.left, l.right.left), BlackTree(z, zv, l.right.right, d))
+    else
+      mkTree(isBlack, z, zv, l, d)
+  }
+  private[this] def balanceRight[A, B, B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[A, B1], r: Tree[A, B1]): Tree[A, B1] = {
+    if (isRedTree(r) && isRedTree(r.left))
+      RedTree(r.left.key, r.left.value, BlackTree(x, xv, a, r.left.left), BlackTree(r.key, r.value, r.left.right, r.right))
+    else if (isRedTree(r) && isRedTree(r.right))
+      RedTree(r.key, r.value, BlackTree(x, xv, a, r.left), BlackTree(r.right.key, r.right.value, r.right.left, r.right.right))
+    else
+      mkTree(isBlack, x, xv, a, r)
+  }
+  private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree == null) {
+    RedTree(k, v, null, null)
+  } else {
+    val cmp = ordering.compare(k, tree.key)
+    if (cmp < 0) balanceLeft(tree.isBlack, tree.key, tree.value, upd(tree.left, k, v), tree.right)
+    else if (cmp > 0) balanceRight(tree.isBlack, tree.key, tree.value, tree.left, upd(tree.right, k, v))
+    else mkTree(tree.isBlack, k, v, tree.left, tree.right)
+  }
+
     // Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
     // http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html
-    def del(k: A)(implicit ordering: Ordering[A]): Tree[A, B] = {
-      def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
-        if (isRedTree(tr)) {
-          RedTree(x, xv, tl.black, tr.black)
-        } else if (isRedTree(tl.left)) {
-          RedTree(tl.key, tl.value, tl.left.black, BlackTree(x, xv, tl.right, tr))
-        } else if (isRedTree(tl.right)) {
-          RedTree(tl.right.key, tl.right.value, BlackTree(tl.key, tl.value, tl.left, tl.right.left), BlackTree(x, xv, tl.right.right, tr))
-        } else {
-          BlackTree(x, xv, tl, tr)
-        }
-      } else if (isRedTree(tr)) {
-        if (isRedTree(tr.right)) {
-          RedTree(tr.key, tr.value, BlackTree(x, xv, tl, tr.left), tr.right.black)
-        } else if (isRedTree(tr.left)) {
-          RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), BlackTree(tr.key, tr.value, tr.left.right, tr.right))
-        } else {
-          BlackTree(x, xv, tl, tr)
-        }
+  private[this] def del[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree == null) null else {
+    def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
+      if (isRedTree(tr)) {
+        RedTree(x, xv, tl.black, tr.black)
+      } else if (isRedTree(tl.left)) {
+        RedTree(tl.key, tl.value, tl.left.black, BlackTree(x, xv, tl.right, tr))
+      } else if (isRedTree(tl.right)) {
+        RedTree(tl.right.key, tl.right.value, BlackTree(tl.key, tl.value, tl.left, tl.right.left), BlackTree(x, xv, tl.right.right, tr))
       } else {
         BlackTree(x, xv, tl, tr)
       }
-      def subl(t: Tree[A, B]) =
-        if (t.isInstanceOf[BlackTree[_, _]]) t.red
-        else sys.error("Defect: invariance violation; expected black, got "+t)
-
-      def balLeft(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
-        RedTree(x, xv, tl.black, tr)
-      } else if (isBlackTree(tr)) {
-        balance(x, xv, tl, tr.red)
-      } else if (isRedTree(tr) && isBlackTree(tr.left)) {
-        RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), balance(tr.key, tr.value, tr.left.right, subl(tr.right)))
+    } else if (isRedTree(tr)) {
+      if (isRedTree(tr.right)) {
+        RedTree(tr.key, tr.value, BlackTree(x, xv, tl, tr.left), tr.right.black)
+      } else if (isRedTree(tr.left)) {
+        RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), BlackTree(tr.key, tr.value, tr.left.right, tr.right))
       } else {
-        sys.error("Defect: invariance violation at "+right)
+        BlackTree(x, xv, tl, tr)
       }
-      def balRight(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tr)) {
-        RedTree(x, xv, tl, tr.black)
-      } else if (isBlackTree(tl)) {
-        balance(x, xv, tl.red, tr)
-      } else if (isRedTree(tl) && isBlackTree(tl.right)) {
-        RedTree(tl.right.key, tl.right.value, balance(tl.key, tl.value, subl(tl.left), tl.right.left), BlackTree(x, xv, tl.right.right, tr))
+    } else {
+      BlackTree(x, xv, tl, tr)
+    }
+    def subl(t: Tree[A, B]) =
+      if (t.isInstanceOf[BlackTree[_, _]]) t.red
+      else sys.error("Defect: invariance violation; expected black, got "+t)
+
+    def balLeft(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
+      RedTree(x, xv, tl.black, tr)
+    } else if (isBlackTree(tr)) {
+      balance(x, xv, tl, tr.red)
+    } else if (isRedTree(tr) && isBlackTree(tr.left)) {
+      RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), balance(tr.key, tr.value, tr.left.right, subl(tr.right)))
+    } else {
+      sys.error("Defect: invariance violation at ") // TODO
+    }
+    def balRight(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tr)) {
+      RedTree(x, xv, tl, tr.black)
+    } else if (isBlackTree(tl)) {
+      balance(x, xv, tl.red, tr)
+    } else if (isRedTree(tl) && isBlackTree(tl.right)) {
+      RedTree(tl.right.key, tl.right.value, balance(tl.key, tl.value, subl(tl.left), tl.right.left), BlackTree(x, xv, tl.right.right, tr))
+    } else {
+      sys.error("Defect: invariance violation at ") // TODO
+    }
+    def delLeft = if (isBlackTree(tree.left)) balLeft(tree.key, tree.value, del(tree.left, k), tree.right) else RedTree(tree.key, tree.value, del(tree.left, k), tree.right)
+    def delRight = if (isBlackTree(tree.right)) balRight(tree.key, tree.value, tree.left, del(tree.right, k)) else RedTree(tree.key, tree.value, tree.left, del(tree.right, k))
+    def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = if (tl eq null) {
+      tr
+    } else if (tr eq null) {
+      tl
+    } else if (isRedTree(tl) && isRedTree(tr)) {
+      val bc = append(tl.right, tr.left)
+      if (isRedTree(bc)) {
+        RedTree(bc.key, bc.value, RedTree(tl.key, tl.value, tl.left, bc.left), RedTree(tr.key, tr.value, bc.right, tr.right))
       } else {
-        sys.error("Defect: invariance violation at "+left)
+        RedTree(tl.key, tl.value, tl.left, RedTree(tr.key, tr.value, bc, tr.right))
       }
-      def delLeft = if (isBlackTree(left)) balLeft(key, value, left.del(k), right) else RedTree(key, value, left.del(k), right)
-      def delRight = if (isBlackTree(right)) balRight(key, value, left, right.del(k)) else RedTree(key, value, left, right.del(k))
-      def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = if (tl eq Empty.Instance) {
-        tr
-      } else if (tr eq Empty.Instance) {
-        tl
-      } else if (isRedTree(tl) && isRedTree(tr)) {
-        val bc = append(tl.right, tr.left)
-        if (isRedTree(bc)) {
-          RedTree(bc.key, bc.value, RedTree(tl.key, tl.value, tl.left, bc.left), RedTree(tr.key, tr.value, bc.right, tr.right))
-        } else {
-          RedTree(tl.key, tl.value, tl.left, RedTree(tr.key, tr.value, bc, tr.right))
-        }
-      } else if (isBlackTree(tl) && isBlackTree(tr)) {
-        val bc = append(tl.right, tr.left)
-        if (isRedTree(bc)) {
-          RedTree(bc.key, bc.value, BlackTree(tl.key, tl.value, tl.left, bc.left), BlackTree(tr.key, tr.value, bc.right, tr.right))
-        } else {
-          balLeft(tl.key, tl.value, tl.left, BlackTree(tr.key, tr.value, bc, tr.right))
-        }
-      } else if (isRedTree(tr)) {
-        RedTree(tr.key, tr.value, append(tl, tr.left), tr.right)
-      } else if (isRedTree(tl)) {
-        RedTree(tl.key, tl.value, tl.left, append(tl.right, tr))
+    } else if (isBlackTree(tl) && isBlackTree(tr)) {
+      val bc = append(tl.right, tr.left)
+      if (isRedTree(bc)) {
+        RedTree(bc.key, bc.value, BlackTree(tl.key, tl.value, tl.left, bc.left), BlackTree(tr.key, tr.value, bc.right, tr.right))
       } else {
-        sys.error("unmatched tree on append: " + tl + ", " + tr)
+        balLeft(tl.key, tl.value, tl.left, BlackTree(tr.key, tr.value, bc, tr.right))
       }
-
-      val cmp = ordering.compare(k, key)
-      if (cmp < 0) delLeft
-      else if (cmp > 0) delRight
-      else append(left, right)
+    } else if (isRedTree(tr)) {
+      RedTree(tr.key, tr.value, append(tl, tr.left), tr.right)
+    } else if (isRedTree(tl)) {
+      RedTree(tl.key, tl.value, tl.left, append(tl.right, tr))
+    } else {
+      sys.error("unmatched tree on append: " + tl + ", " + tr)
     }
 
-    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
+    val cmp = ordering.compare(k, tree.key)
+    if (cmp < 0) delLeft
+    else if (cmp > 0) delRight
+    else append(tree.left, tree.right)
+  }
 
-    def iterator: Iterator[(A, B)] = new TreeIterator(this)
-    def keyIterator: Iterator[A] = new TreeKeyIterator(this)
+  private[this] def rng[A, B](tree: Tree[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = {
+    if (tree eq null) return null
+    if (from == None && until == None) return tree
+    if (from != None && ordering.lt(tree.key, from.get)) return rng(tree.right, from, until);
+    if (until != None && ordering.lteq(until.get, tree.key)) return rng(tree.left, from, until);
+    val newLeft = rng(tree.left, from, None)
+    val newRight = rng(tree.right, None, until)
+    if ((newLeft eq tree.left) && (newRight eq tree.right)) tree
+    else if (newLeft eq null) upd(newRight, tree.key, tree.value);
+    else if (newRight eq null) upd(newLeft, tree.key, tree.value);
+    else rebalance(tree, newLeft, newRight)
+  }
 
-    override def foreach[U](f: ((A, B)) => U) {
-      if (left ne Empty.Instance) left foreach f
-      f((key, value))
-      if (right ne Empty.Instance) right foreach f
+  // The zipper returned might have been traversed left-most (always the left child)
+  // or right-most (always the right child). Left trees are traversed right-most,
+  // and right trees are traversed leftmost.
+
+  // Returns the zipper for the side with deepest black nodes depth, a flag
+  // indicating whether the trees were unbalanced at all, and a flag indicating
+  // whether the zipper was traversed left-most or right-most.
+
+  // If the trees were balanced, returns an empty zipper
+  private[this] def compareDepth[A, B](left: Tree[A, B], right: Tree[A, B]): (List[Tree[A, B]], Boolean, Boolean, Int) = {
+    // Once a side is found to be deeper, unzip it to the bottom
+    def unzip(zipper: List[Tree[A, B]], leftMost: Boolean): List[Tree[A, B]] = {
+      val next = if (leftMost) zipper.head.left else zipper.head.right
+      next match {
+        case null => zipper
+        case node => unzip(node :: zipper, leftMost)
+      }
     }
 
-    override def foreachKey[U](f: A => U) {
-      if (left ne Empty.Instance) left foreachKey f
-      f(key)
-      if (right ne Empty.Instance) right foreachKey f
+    // Unzip left tree on the rightmost side and right tree on the leftmost side until one is
+    // found to be deeper, or the bottom is reached
+    def unzipBoth(left: Tree[A, B],
+                  right: Tree[A, B],
+                  leftZipper: List[Tree[A, B]],
+                  rightZipper: List[Tree[A, B]],
+                  smallerDepth: Int): (List[Tree[A, B]], Boolean, Boolean, Int) = {
+      if (isBlackTree(left) && isBlackTree(right)) {
+        unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth + 1)
+      } else if (isRedTree(left) && isRedTree(right)) {
+        unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth)
+      } else if (isRedTree(right)) {
+        unzipBoth(left, right.left, leftZipper, right :: rightZipper, smallerDepth)
+      } else if (isRedTree(left)) {
+        unzipBoth(left.right, right, left :: leftZipper, rightZipper, smallerDepth)
+      } else if ((left eq null) && (right eq null)) {
+        (Nil, true, false, smallerDepth)
+      } else if ((left eq null) && isBlackTree(right)) {
+        val leftMost = true
+        (unzip(right :: rightZipper, leftMost), false, leftMost, smallerDepth)
+      } else if (isBlackTree(left) && (right eq null)) {
+        val leftMost = false
+        (unzip(left :: leftZipper, leftMost), false, leftMost, smallerDepth)
+      } else {
+        sys.error("unmatched trees in unzip: " + left + ", " + right)
+      }
     }
-
-    override def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = {
-      if (from == None && until == None) return this
-      if (from != None && ordering.lt(key, from.get)) return right.rng(from, until);
-      if (until != None && ordering.lteq(until.get, key)) return left.rng(from, until);
-      val newLeft = left.rng(from, None)
-      val newRight = right.rng(None, until)
-      if ((newLeft eq left) && (newRight eq right)) this
-      else if (newLeft eq Empty.Instance) newRight.upd(key, value);
-      else if (newRight eq Empty.Instance) newLeft.upd(key, value);
-      else rebalance(newLeft, newRight)
+    unzipBoth(left, right, Nil, Nil, 0)
+  }
+   private[this] def rebalance[A, B](tree: Tree[A, B], newLeft: Tree[A, B], newRight: Tree[A, B]) = {
+    // This is like drop(n-1), but only counting black nodes
+    def  findDepth(zipper: List[Tree[A, B]], depth: Int): List[Tree[A, B]] = zipper match {
+      case head :: tail if isBlackTree(head) =>
+        if (depth == 1) zipper else findDepth(tail, depth - 1)
+      case _ :: tail => findDepth(tail, depth)
+      case Nil => sys.error("Defect: unexpected empty zipper while computing range")
     }
 
-    // The zipper returned might have been traversed left-most (always the left child)
-    // or right-most (always the right child). Left trees are traversed right-most,
-    // and right trees are traversed leftmost.
-
-    // Returns the zipper for the side with deepest black nodes depth, a flag
-    // indicating whether the trees were unbalanced at all, and a flag indicating
-    // whether the zipper was traversed left-most or right-most.
-
-    // If the trees were balanced, returns an empty zipper
-    private[this] def compareDepth(left: Tree[A, B], right: Tree[A, B]): (List[NonEmpty[A, B]], Boolean, Boolean, Int) = {
-      // Once a side is found to be deeper, unzip it to the bottom
-      def unzip(zipper: List[NonEmpty[A, B]], leftMost: Boolean): List[NonEmpty[A, B]] = {
-        val next = if (leftMost) zipper.head.left else zipper.head.right
-        next match {
-          case node: NonEmpty[_, _] => unzip(node :: zipper, leftMost)
-          case _                    => zipper
-        }
+    // Blackening the smaller tree avoids balancing problems on union;
+    // this can't be done later, though, or it would change the result of compareDepth
+    val blkNewLeft = blacken(newLeft)
+    val blkNewRight = blacken(newRight)
+    val (zipper, levelled, leftMost, smallerDepth) = compareDepth(blkNewLeft, blkNewRight)
+
+    if (levelled) {
+      BlackTree(tree.key, tree.value, blkNewLeft, blkNewRight)
+    } else {
+      val zipFrom = findDepth(zipper, smallerDepth)
+      val union = if (leftMost) {
+        RedTree(tree.key, tree.value, blkNewLeft, zipFrom.head)
+      } else {
+        RedTree(tree.key, tree.value, zipFrom.head, blkNewRight)
       }
-
-      // Unzip left tree on the rightmost side and right tree on the leftmost side until one is
-      // found to be deeper, or the bottom is reached
-      def unzipBoth(left: Tree[A, B],
-                    right: Tree[A, B],
-                    leftZipper: List[NonEmpty[A, B]],
-                    rightZipper: List[NonEmpty[A, B]],
-                    smallerDepth: Int): (List[NonEmpty[A, B]], Boolean, Boolean, Int) = {
-        lazy val l = left.asInstanceOf[NonEmpty[A, B]]
-        lazy val r = right.asInstanceOf[NonEmpty[A, B]]
-        if (isBlackTree(left) && isBlackTree(right)) {
-          unzipBoth(l.right, r.left, l :: leftZipper, r :: rightZipper, smallerDepth + 1)
-        } else if (isRedTree(left) && isRedTree(right)) {
-          unzipBoth(l.right, r.left, l :: leftZipper, r :: rightZipper, smallerDepth)
-        } else if (isRedTree(right)) {
-          unzipBoth(left, r.left, leftZipper, r :: rightZipper, smallerDepth)
-        } else if (isRedTree(left)) {
-          unzipBoth(l.right, right, l :: leftZipper, rightZipper, smallerDepth)
-        } else if ((left eq Empty.Instance) && (right eq Empty.Instance)) {
-          (Nil, true, false, smallerDepth)
-        } else if ((left eq Empty.Instance) && isBlackTree(right)) {
-          val leftMost = true
-          (unzip(r :: rightZipper, leftMost), false, leftMost, smallerDepth)
-        } else if (isBlackTree(left) && (right eq Empty.Instance)) {
-          val leftMost = false
-          (unzip(l :: leftZipper, leftMost), false, leftMost, smallerDepth)
-        } else {
-          sys.error("unmatched trees in unzip: " + left + ", " + right)
-        }
+      val zippedTree = zipFrom.tail.foldLeft(union: Tree[A, B]) { (tree, node) =>
+        if (leftMost)
+          balanceLeft(node.isBlack, node.key, node.value, tree, node.right)
+        else
+          balanceRight(node.isBlack, node.key, node.value, node.left, tree)
       }
-      unzipBoth(left, right, Nil, Nil, 0)
+      zippedTree
     }
+  }
 
-    private[this] def rebalance(newLeft: Tree[A, B], newRight: Tree[A, B]) = {
-      // This is like drop(n-1), but only counting black nodes
-      def  findDepth(zipper: List[NonEmpty[A, B]], depth: Int): List[NonEmpty[A, B]] = zipper match {
-        case head :: tail if isBlackTree(head) =>
-          if (depth == 1) zipper else findDepth(tail, depth - 1)
-        case _ :: tail => findDepth(tail, depth)
-        case Nil => sys.error("Defect: unexpected empty zipper while computing range")
-      }
-
-      // Blackening the smaller tree avoids balancing problems on union;
-      // this can't be done later, though, or it would change the result of compareDepth
-      val blkNewLeft = blacken(newLeft)
-      val blkNewRight = blacken(newRight)
-      val (zipper, levelled, leftMost, smallerDepth) = compareDepth(blkNewLeft, blkNewRight)
-
-      if (levelled) {
-        BlackTree(key, value, blkNewLeft, blkNewRight)
-      } else {
-        val zipFrom = findDepth(zipper, smallerDepth)
-        val union = if (leftMost) {
-          RedTree(key, value, blkNewLeft, zipFrom.head)
-        } else {
-          RedTree(key, value, zipFrom.head, blkNewRight)
-        }
-        val zippedTree = zipFrom.tail.foldLeft(union: Tree[A, B]) { (tree, node) =>
-            if (leftMost)
-              balanceLeft(node.isBlack, node.key, node.value, tree, node.right)
-            else
-              balanceRight(node.isBlack, node.key, node.value, node.left, tree)
-        }
-        zippedTree
-      }
-    }
-    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) = {
-      val count = left.count
+  sealed abstract class Tree[A, +B](
+    @(inline @getter) final val key: A,
+    @(inline @getter) final val value: B,
+    @(inline @getter) final val left: Tree[A, B],
+    @(inline @getter) final val right: Tree[A, B])
+  extends Serializable {
+    @(inline @getter) final val count: Int = 1 + RedBlack.count(left) + RedBlack.count(right)
+    def isBlack: Boolean
+    def nth(n: Int): Tree[A, B] = {
+      val count = RedBlack.count(left)
       if (n < count) left.nth(n)
       else if (n > count) right.nth(n - count - 1)
       else this
     }
+    def black: Tree[A, B]
+    def red: Tree[A, B]
   }
-  object Empty {
-    def empty[A]: Tree[A, Nothing] = Instance.asInstanceOf[Tree[A, Nothing]]
 
-    final val Instance: Tree[_ >: Nothing, Nothing] = Empty[Nothing]()
-  }
-  final case class Empty[A] private () extends Tree[A, Nothing] {
-    def key = throw new NoSuchElementException("empty map")
-    def value = throw new NoSuchElementException("empty map")
-    def left = this
-    def right = this
-    def isEmpty = true
-    def isBlack = true
-    def lookup(k: A)(implicit ordering: Ordering[A]): Tree[A, Nothing] = this
-    def upd[B](k: A, v: B)(implicit ordering: Ordering[A]): Tree[A, B] = RedTree(k, v, this, this)
-    def del(k: A)(implicit ordering: Ordering[A]): Tree[A, Nothing] = this
-    def smallest: NonEmpty[A, Nothing] = throw new NoSuchElementException("empty map")
-    def greatest: NonEmpty[A, Nothing] = throw new NoSuchElementException("empty map")
-    def iterator: Iterator[(A, Nothing)] = Iterator.empty
-    def keyIterator: Iterator[A] = Iterator.empty
-
-    override def foreach[U](f: ((A, Nothing)) => U) {}
-    override def foreachKey[U](f: A => U) {}
-
-    def rng(from: Option[A], until: Option[A])(implicit ordering: Ordering[A]) = this
-    def first = throw new NoSuchElementException("empty map")
-    def last = throw new NoSuchElementException("empty map")
-    def count = 0
-    protected[immutable] def nth(n: Int) = throw new NoSuchElementException("empty map")
-    override def red = sys.error("cannot make leaf red")
-
-    override def toString() = "Empty"
-
-    private def readResolve() = Empty.empty
-  }
   final class RedTree[A, +B](key: A,
-                         value: B,
-                         left: Tree[A, B],
-                         right: Tree[A, B]) extends NonEmpty[A, B](key, value, left, right) {
-    def isBlack = false
+                             value: B,
+                             left: Tree[A, B],
+                             right: Tree[A, B]) extends Tree[A, B](key, value, left, right) {
+    override def isBlack = false
     override def black = BlackTree(key, value, left, right)
     override def red = this
+    override def toString = "RedTree(" + key + ", " + value + ", " + left + ", " + right + ")"
   }
   object RedTree {
     def apply[A, B](key: A, value: B, left: Tree[A, B], right: Tree[A, B]) = new RedTree(key, value, left, right)
     def unapply[A, B](t: RedTree[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
   final class BlackTree[A, +B](key: A,
-                           value: B,
-                           left: Tree[A, B],
-                           right: Tree[A, B]) extends NonEmpty[A, B](key, value, left, right) {
-    def isBlack = true
+                               value: B,
+                               left: Tree[A, B],
+                               right: Tree[A, B]) extends Tree[A, B](key, value, left, right) {
+    override def isBlack = true
+    override def black = this
     override def red = RedTree(key, value, left, right)
+    override def toString = "BlackTree(" + key + ", " + value + ", " + left + ", " + right + ")"
   }
   object BlackTree {
     def apply[A, B](key: A, value: B, left: Tree[A, B], right: Tree[A, B]) = new BlackTree(key, value, left, right)
     def unapply[A, B](t: BlackTree[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
 
-  private[this] class TreeIterator[A, B](tree: NonEmpty[A, B]) extends Iterator[(A, B)] {
-    override def hasNext: Boolean = next ne Empty.Instance
+  private[this] class TreeIterator[A, B](tree: Tree[A, B]) extends Iterator[(A, B)] {
+    override def hasNext: Boolean = next ne null
 
     override def next: (A, B) = next match {
-      case Empty.Instance =>
+      case null =>
         throw new NoSuchElementException("next on empty iterator")
-      case tree: NonEmpty[A, B] =>
+      case tree =>
         addLeftMostBranchToPath(tree.right)
-        next = if (path.isEmpty) Empty.empty else path.pop()
+        next = if (path.isEmpty) null else path.pop()
         (tree.key, tree.value)
     }
 
     @annotation.tailrec
     private[this] def addLeftMostBranchToPath(tree: Tree[A, B]) {
-      tree match {
-        case Empty.Instance =>
-        case tree: NonEmpty[A, B] =>
-          path.push(tree)
-          addLeftMostBranchToPath(tree.left)
+      if (tree ne null) {
+        path.push(tree)
+        addLeftMostBranchToPath(tree.left)
       }
     }
 
-    private[this] val path = mutable.ArrayStack.empty[NonEmpty[A, B]]
+    private[this] val path = mutable.ArrayStack.empty[Tree[A, B]]
     addLeftMostBranchToPath(tree)
     private[this] var next: Tree[A, B] = path.pop()
   }
 
-  private[this] class TreeKeyIterator[A](tree: NonEmpty[A, _]) extends Iterator[A] {
-    override def hasNext: Boolean = next ne Empty.Instance
+  private[this] class TreeKeyIterator[A](tree: Tree[A, _]) extends Iterator[A] {
+    override def hasNext: Boolean = next ne null
 
     override def next: A = next match {
-      case Empty.Instance =>
+      case null =>
         throw new NoSuchElementException("next on empty iterator")
-      case tree: NonEmpty[A, _] =>
+      case tree =>
         addLeftMostBranchToPath(tree.right)
-        next = if (path.isEmpty) Empty.empty else path.pop()
+        next = if (path.isEmpty) null else path.pop()
         tree.key
     }
 
     @annotation.tailrec
     private[this] def addLeftMostBranchToPath(tree: Tree[A, _]) {
-      tree match {
-        case Empty.Instance =>
-        case tree: NonEmpty[A, _] =>
-          path.push(tree)
-          addLeftMostBranchToPath(tree.left)
+      if (tree ne null) {
+        path.push(tree)
+        addLeftMostBranchToPath(tree.left)
       }
     }
 
-    private[this] val path = mutable.ArrayStack.empty[NonEmpty[A, _]]
+    private[this] val path = mutable.ArrayStack.empty[Tree[A, _]]
     addLeftMostBranchToPath(tree)
     private[this] var next: Tree[A, _] = path.pop()
   }
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 48a0bc3d44..45e936444f 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -51,39 +51,39 @@ class TreeMap[A, +B] private (tree: RedBlack.Tree[A, B])(implicit val ordering:
      with MapLike[A, B, TreeMap[A, B]]
      with Serializable {
 
-  import RedBlack._
+  import immutable.{RedBlack => RB}
 
   def isSmaller(x: A, y: A) = ordering.lt(x, y)
 
   override protected[this] def newBuilder : Builder[(A, B), TreeMap[A, B]] =
     TreeMap.newBuilder[A, B]
 
-  override def size = tree.count
+  override def size = RB.count(tree)
 
-  def this()(implicit ordering: Ordering[A]) = this(RedBlack.Empty.empty)(ordering)
+  def this()(implicit ordering: Ordering[A]) = this(null)(ordering)
 
   override def rangeImpl(from : Option[A], until : Option[A]): TreeMap[A,B] = {
-    val ntree = tree.range(from,until)
+    val ntree = RB.range(tree, from,until)
     new TreeMap[A,B](ntree)
   }
 
-  override def firstKey = tree.first
-  override def lastKey = tree.last
+  override def firstKey = RB.smallest(tree).key
+  override def lastKey = RB.greatest(tree).key
   override def compare(k0: A, k1: A): Int = ordering.compare(k0, k1)
 
   override def head = {
-    val smallest = tree.smallest
+    val smallest = RB.smallest(tree)
     (smallest.key, smallest.value)
   }
-  override def headOption = if (tree.isEmpty) None else Some(head)
+  override def headOption = if (RB.isEmpty(tree)) None else Some(head)
   override def last = {
-    val greatest = tree.greatest
+    val greatest = RB.greatest(tree)
     (greatest.key, greatest.value)
   }
-  override def lastOption = if (tree.isEmpty) None else Some(last)
+  override def lastOption = if (RB.isEmpty(tree)) None else Some(last)
 
-  override def tail = new TreeMap(tree.delete(firstKey))
-  override def init = new TreeMap(tree.delete(lastKey))
+  override def tail = new TreeMap(RB.delete(tree, firstKey))
+  override def init = new TreeMap(RB.delete(tree, lastKey))
 
   override def drop(n: Int) = {
     if (n <= 0) this
@@ -134,7 +134,7 @@ class TreeMap[A, +B] private (tree: RedBlack.Tree[A, B])(implicit val ordering:
    *  @param value   the value to be associated with `key`
    *  @return        a new $coll with the updated binding
    */
-  override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(tree.update(key, value))
+  override def updated [B1 >: B](key: A, value: B1): TreeMap[A, B1] = new TreeMap(RB.update(tree, key, value))
 
   /** Add a key/value pair to this map.
    *  @tparam   B1   type of the value of the new binding, a supertype of `B`
@@ -175,13 +175,13 @@ class TreeMap[A, +B] private (tree: RedBlack.Tree[A, B])(implicit val ordering:
    *  @return       a new $coll with the inserted binding, if it wasn't present in the map
    */
   def insert [B1 >: B](key: A, value: B1): TreeMap[A, B1] = {
-    assert(tree.lookup(key).isEmpty)
-    new TreeMap(tree.update(key, value))
+    assert(!RB.contains(tree, key))
+    new TreeMap(RB.update(tree, key, value))
   }
 
   def - (key:A): TreeMap[A, B] =
-    if (tree.lookup(key).isEmpty) this
-    else new TreeMap(tree.delete(key))
+    if (!RB.contains(tree, key)) this
+    else new TreeMap(RB.delete(tree, key))
 
   /** Check if this map maps `key` to a value and return the
    *  value if it exists.
@@ -189,21 +189,19 @@ class TreeMap[A, +B] private (tree: RedBlack.Tree[A, B])(implicit val ordering:
    *  @param  key     the key of the mapping of interest
    *  @return         the value of the mapping, if it exists
    */
-  override def get(key: A): Option[B] = lookup(tree, key) match {
-    case n: NonEmpty[_, _] => Some(n.value)
-    case _ => None
-  }
+  override def get(key: A): Option[B] = RB.get(tree, key)
 
   /** Creates a new iterator over all elements contained in this
    *  object.
    *
    *  @return the new iterator
    */
-  def iterator: Iterator[(A, B)] = tree.iterator
+  def iterator: Iterator[(A, B)] = RB.iterator(tree)
 
-  override def toStream: Stream[(A, B)] = tree.iterator.toStream
+  override def contains(key: A): Boolean = RB.contains(tree, key)
+  override def isDefinedAt(key: A): Boolean = RB.contains(tree, key)
 
-  override def foreach[U](f : ((A,B)) =>  U) = tree foreach f
+  override def foreach[U](f : ((A,B)) =>  U) = RB.foreach(tree, f)
 }
 
 
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index 74c63d0eb5..00ebeab868 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -50,19 +50,19 @@ object TreeSet extends ImmutableSortedSetFactory[TreeSet] {
 class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: Ordering[A])
   extends SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable {
 
-  import RedBlack._
+  import immutable.{RedBlack => RB}
 
   override def stringPrefix = "TreeSet"
 
-  override def size = tree.count
+  override def size = RB.count(tree)
 
-  override def head = tree.smallest.key
-  override def headOption = if (tree.isEmpty) None else Some(head)
-  override def last = tree.greatest.key
-  override def lastOption = if (tree.isEmpty) None else Some(last)
+  override def head = RB.smallest(tree).key
+  override def headOption = if (RB.isEmpty(tree)) None else Some(head)
+  override def last = RB.greatest(tree).key
+  override def lastOption = if (RB.isEmpty(tree)) None else Some(last)
 
-  override def tail = new TreeSet(tree.delete(firstKey))
-  override def init = new TreeSet(tree.delete(lastKey))
+  override def tail = new TreeSet(RB.delete(tree, firstKey))
+  override def init = new TreeSet(RB.delete(tree, lastKey))
 
   override def drop(n: Int) = {
     if (n <= 0) this
@@ -102,7 +102,7 @@ class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: O
 
   def isSmaller(x: A, y: A) = compare(x,y) < 0
 
-  def this()(implicit ordering: Ordering[A]) = this(RedBlack.Empty.empty)(ordering)
+  def this()(implicit ordering: Ordering[A]) = this(null)(ordering)
 
   private def newSet(t: RedBlack.Tree[A, Unit]) = new TreeSet[A](t)
 
@@ -115,7 +115,7 @@ class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: O
    *  @param elem    a new element to add.
    *  @return        a new $coll containing `elem` and all the elements of this $coll.
    */
-  def + (elem: A): TreeSet[A] = newSet(tree.update(elem, ()))
+  def + (elem: A): TreeSet[A] = newSet(RB.update(tree, elem, ()))
 
   /** A new `TreeSet` with the entry added is returned,
    *  assuming that elem is <em>not</em> in the TreeSet.
@@ -124,8 +124,8 @@ class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: O
    *  @return        a new $coll containing `elem` and all the elements of this $coll.
    */
   def insert(elem: A): TreeSet[A] = {
-    assert(tree.lookup(elem).isEmpty)
-    newSet(tree.update(elem, ()))
+    assert(!RB.contains(tree, elem))
+    newSet(RB.update(tree, elem, ()))
   }
 
   /** Creates a new `TreeSet` with the entry removed.
@@ -134,31 +134,29 @@ class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: O
    *  @return        a new $coll containing all the elements of this $coll except `elem`.
    */
   def - (elem:A): TreeSet[A] =
-    if (tree.lookup(elem).isEmpty) this
-    else newSet(tree delete elem)
+    if (!RB.contains(tree, elem)) this
+    else newSet(RB.delete(tree, elem))
 
   /** Checks if this set contains element `elem`.
    *
    *  @param  elem    the element to check for membership.
    *  @return true, iff `elem` is contained in this set.
    */
-  def contains(elem: A): Boolean = !lookup(tree, elem).isEmpty
+  def contains(elem: A): Boolean = RB.contains(tree, elem)
 
   /** Creates a new iterator over all elements contained in this
    *  object.
    *
    *  @return the new iterator
    */
-  def iterator: Iterator[A] = tree.keyIterator
+  def iterator: Iterator[A] = RB.keyIterator(tree)
 
-  override def toStream: Stream[A] = tree.keyIterator.toStream
-
-  override def foreach[U](f: A =>  U) = tree foreachKey f
+  override def foreach[U](f: A =>  U) = RB.foreachKey(tree, f)
 
   override def rangeImpl(from: Option[A], until: Option[A]): TreeSet[A] = {
-    val tree = this.tree.range(from, until)
-    newSet(tree)
+    val ntree = RB.range(tree, from, until)
+    newSet(ntree)
   }
-  override def firstKey = tree.first
-  override def lastKey = tree.last
+  override def firstKey = head
+  override def lastKey = last
 }
diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala
index 78fb645ce8..5c52a27e38 100644
--- a/test/files/scalacheck/redblack.scala
+++ b/test/files/scalacheck/redblack.scala
@@ -8,7 +8,7 @@ Properties of a Red & Black Tree:
 
 A node is either red or black.
 The root is black. (This rule is used in some definitions and not others. Since the
-root can always be changed from red to black but not necessarily vice-versa this 
+root can always be changed from red to black but not necessarily vice-versa this
 rule has little effect on analysis.)
 All leaves are black.
 Both children of every red node are black.
@@ -21,17 +21,17 @@ abstract class RedBlackTest extends Properties("RedBlack") {
   def maximumSize = 5
 
   import RedBlack._
-  
-  def nodeAt[A](tree: Tree[String, A], n: Int): Option[(String, A)] = if (n < tree.iterator.size && n >= 0)
-    Some(tree.iterator.drop(n).next)
+
+  def nodeAt[A](tree: Tree[String, A], n: Int): Option[(String, A)] = if (n < iterator(tree).size && n >= 0)
+    Some(iterator(tree).drop(n).next)
   else
     None
-    
-  def treeContains[A](tree: Tree[String, A], key: String) = tree.iterator.map(_._1) contains key
-  
-  def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[String, Int]] = 
+
+  def treeContains[A](tree: Tree[String, A], key: String) = iterator(tree).map(_._1) contains key
+
+  def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[String, Int]] =
     if (level == 0) {
-      value(Empty.empty)
+      value(null)
     } else {
       for {
         oddOrEven <- choose(0, 2)
@@ -41,7 +41,7 @@ abstract class RedBlackTest extends Properties("RedBlack") {
         left <- mkTree(nextLevel, !isRed, label + "L")
         right <- mkTree(nextLevel, !isRed, label + "R")
       } yield {
-        if (isRed) 
+        if (isRed)
           RedTree(label + "N", 0, left, right)
         else
           BlackTree(label + "N", 0, left, right)
@@ -52,11 +52,11 @@ abstract class RedBlackTest extends Properties("RedBlack") {
     depth <- choose(minimumSize, maximumSize + 1)
     tree <- mkTree(depth)
   } yield tree
-  
+
   type ModifyParm
   def genParm(tree: Tree[String, Int]): Gen[ModifyParm]
   def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int]
-  
+
   def genInput: Gen[(Tree[String, Int], ModifyParm, Tree[String, Int])] = for {
     tree <- genTree
     parm <- genParm(tree)
@@ -65,41 +65,41 @@ abstract class RedBlackTest extends Properties("RedBlack") {
 
 trait RedBlackInvariants {
   self: RedBlackTest =>
-  
+
   import RedBlack._
-    
-  def rootIsBlack[A](t: Tree[String, A]) = t.isBlack
-  
+
+  def rootIsBlack[A](t: Tree[String, A]) = isBlack(t)
+
   def areAllLeavesBlack[A](t: Tree[String, A]): Boolean = t match {
-    case Empty.Instance => t.isBlack
-    case ne: NonEmpty[_, _] => List(ne.left, ne.right) forall areAllLeavesBlack
+    case null => isBlack(t)
+    case ne => List(ne.left, ne.right) forall areAllLeavesBlack
   }
-  
+
   def areRedNodeChildrenBlack[A](t: Tree[String, A]): Boolean = t match {
-    case RedTree(_, _, left, right) => List(left, right) forall (t => t.isBlack && areRedNodeChildrenBlack(t)) 
+    case RedTree(_, _, left, right) => List(left, right) forall (t => isBlack(t) && areRedNodeChildrenBlack(t))
     case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack
-    case Empty.Instance => true
+    case null => true
   }
-  
+
   def blackNodesToLeaves[A](t: Tree[String, A]): List[Int] = t match {
-    case Empty.Instance => List(1)
+    case null => List(1)
     case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1)
     case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves
   }
-  
+
   def areBlackNodesToLeavesEqual[A](t: Tree[String, A]): Boolean = t match {
-    case Empty.Instance => true
-    case ne: NonEmpty[_, _] => 
+    case null => true
+    case ne =>
       (
-        blackNodesToLeaves(ne).distinct.size == 1 
-        && areBlackNodesToLeavesEqual(ne.left) 
+        blackNodesToLeaves(ne).distinct.size == 1
+        && areBlackNodesToLeavesEqual(ne.left)
         && areBlackNodesToLeavesEqual(ne.right)
       )
   }
-  
-  def orderIsPreserved[A](t: Tree[String, A]): Boolean = 
-    t.iterator zip t.iterator.drop(1) forall { case (x, y) => x._1 < y._1 }
-    
+
+  def orderIsPreserved[A](t: Tree[String, A]): Boolean =
+    iterator(t) zip iterator(t).drop(1) forall { case (x, y) => x._1 < y._1 }
+
   def setup(invariant: Tree[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) =>
     invariant(newTree)
   }
@@ -113,10 +113,10 @@ trait RedBlackInvariants {
 
 object TestInsert extends RedBlackTest with RedBlackInvariants {
   import RedBlack._
-  
+
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, tree.iterator.size + 1)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = tree update (generateKey(tree, parm), 0)
+  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size + 1)
+  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = update(tree, generateKey(tree, parm), 0)
 
   def generateKey(tree: Tree[String, Int], parm: ModifyParm): String = nodeAt(tree, parm) match {
     case Some((key, _)) => key.init.mkString + "MN"
@@ -133,18 +133,18 @@ object TestInsert extends RedBlackTest with RedBlackInvariants {
 
 object TestModify extends RedBlackTest {
   import RedBlack._
-  
+
   def newValue = 1
   override def minimumSize = 1
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, tree.iterator.size)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map { 
-    case (key, _) => tree update (key, newValue)
+  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
+  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map {
+    case (key, _) => update(tree, key, newValue)
   } getOrElse tree
 
   property("update modifies values") = forAll(genInput) { case (tree, parm, newTree) =>
     nodeAt(tree,parm) forall { case (key, _) =>
-      newTree.iterator contains (key, newValue)
+      iterator(newTree) contains (key, newValue)
     }
   }
 }
@@ -154,11 +154,11 @@ object TestDelete extends RedBlackTest with RedBlackInvariants  {
 
   override def minimumSize = 1
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, tree.iterator.size)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map { 
-    case (key, _) => tree delete key
+  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
+  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map {
+    case (key, _) => delete(tree, key)
   } getOrElse tree
-  
+
   property("delete removes elements") = forAll(genInput) { case (tree, parm, newTree) =>
     nodeAt(tree, parm) forall { case (key, _) =>
       !treeContains(newTree, key)
@@ -168,37 +168,37 @@ object TestDelete extends RedBlackTest with RedBlackInvariants  {
 
 object TestRange extends RedBlackTest with RedBlackInvariants  {
   import RedBlack._
-  
+
   override type ModifyParm = (Option[Int], Option[Int])
   override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = for {
-    from <- choose(0, tree.iterator.size)
-    to <- choose(0, tree.iterator.size) suchThat (from <=)
+    from <- choose(0, iterator(tree).size)
+    to <- choose(0, iterator(tree).size) suchThat (from <=)
     optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug
     optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug
   } yield (optionalFrom, optionalTo)
-  
+
   override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = {
     val from = parm._1 flatMap (nodeAt(tree, _) map (_._1))
     val to = parm._2 flatMap (nodeAt(tree, _) map (_._1))
-    tree range (from, to)
+    range(tree, from, to)
   }
-  
+
   property("range boundaries respected") = forAll(genInput) { case (tree, parm, newTree) =>
     val from = parm._1 flatMap (nodeAt(tree, _) map (_._1))
     val to = parm._2 flatMap (nodeAt(tree, _) map (_._1))
-    ("lower boundary" |: (from forall ( key => newTree.iterator.map(_._1) forall (key <=)))) &&
-    ("upper boundary" |: (to forall ( key => newTree.iterator.map(_._1) forall (key >))))
+    ("lower boundary" |: (from forall ( key => iterator(newTree).map(_._1) forall (key <=)))) &&
+    ("upper boundary" |: (to forall ( key => iterator(newTree).map(_._1) forall (key >))))
   }
-  
+
   property("range returns all elements") = forAll(genInput) { case (tree, parm, newTree) =>
     val from = parm._1 flatMap (nodeAt(tree, _) map (_._1))
     val to = parm._2 flatMap (nodeAt(tree, _) map (_._1))
-    val filteredTree = (tree.iterator
-      .map(_._1) 
+    val filteredTree = (iterator(tree)
+      .map(_._1)
       .filter(key => from forall (key >=))
       .filter(key => to forall (key <))
       .toList)
-    filteredTree == newTree.iterator.map(_._1).toList
+    filteredTree == iterator(newTree).map(_._1).toList
   }
 }
 }