From 5c05f66b619ea9c8a543518fd9d7d601268c6f19 Mon Sep 17 00:00:00 2001 From: Erik Rozendaal Date: Mon, 2 Jan 2012 19:48:37 +0100 Subject: Use null to represent empty trees. Removed Empty/NonEmpty classes. --- .../scala/collection/immutable/RedBlack.scala | 569 ++++++++++----------- .../scala/collection/immutable/TreeMap.scala | 46 +- .../scala/collection/immutable/TreeSet.scala | 44 +- test/files/scalacheck/redblack.scala | 112 ++-- 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 not 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 } } } -- cgit v1.2.3