diff options
author | Erik Rozendaal <erik@deler.org> | 2012-01-02 16:35:58 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2012-01-02 16:35:58 +0100 |
commit | 82374ad4c2c518ef8ee3fe3d2ef3e72cce75d4f1 (patch) | |
tree | 1db6a653e405658ce63afd63a04525fb9618ea02 | |
parent | 6d8dca7a00eef3ce156abcf2e41a5fd5867688b8 (diff) | |
download | scala-82374ad4c2c518ef8ee3fe3d2ef3e72cce75d4f1.tar.gz scala-82374ad4c2c518ef8ee3fe3d2ef3e72cce75d4f1.tar.bz2 scala-82374ad4c2c518ef8ee3fe3d2ef3e72cce75d4f1.zip |
Implemented deletes without pattern matching.
-rw-r--r-- | src/library/scala/collection/immutable/RedBlack.scala | 133 |
1 files changed, 72 insertions, 61 deletions
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala index 949ab557ba..57b08c2b8c 100644 --- a/src/library/scala/collection/immutable/RedBlack.scala +++ b/src/library/scala/collection/immutable/RedBlack.scala @@ -22,7 +22,8 @@ object RedBlack { 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 isRed[A, B](tree: Tree[A, B]) = !tree.isBlack + def isRedTree[A, B](tree: Tree[A, B]) = tree.isInstanceOf[RedTree[_, _]] + def isBlackTree(tree: Tree[_, _]) = tree.isInstanceOf[BlackTree[_, _]] @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 { @@ -67,17 +68,17 @@ object RedBlack { 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 (isRed(l) && isRed(l.left)) + 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 (isRed(l) && isRed(l.right)) + 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 (isRed(r) && isRed(r.left)) + 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 (isRed(r) && isRed(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) @@ -91,65 +92,75 @@ object RedBlack { // 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]) = (tl, tr) match { - case (RedTree(y, yv, a, b), RedTree(z, zv, c, d)) => - RedTree(x, xv, BlackTree(y, yv, a, b), BlackTree(z, zv, c, d)) - case (RedTree(y, yv, RedTree(z, zv, a, b), c), d) => - RedTree(y, yv, BlackTree(z, zv, a, b), BlackTree(x, xv, c, d)) - case (RedTree(y, yv, a, RedTree(z, zv, b, c)), d) => - RedTree(z, zv, BlackTree(y, yv, a, b), BlackTree(x, xv, c, d)) - case (a, RedTree(y, yv, b, RedTree(z, zv, c, d))) => - RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d)) - case (a, RedTree(y, yv, RedTree(z, zv, b, c), d)) => - RedTree(z, zv, BlackTree(x, xv, a, b), BlackTree(y, yv, c, d)) - case (a, b) => - BlackTree(x, xv, a, b) - } - def subl(t: Tree[A, B]) = t match { - case BlackTree(x, xv, a, b) => RedTree(x, xv, a, b) - case _ => sys.error("Defect: invariance violation; expected black, got "+t) - } - def balLeft(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = (tl, tr) match { - case (RedTree(y, yv, a, b), c) => - RedTree(x, xv, BlackTree(y, yv, a, b), c) - case (bl, BlackTree(y, yv, a, b)) => - balance(x, xv, bl, RedTree(y, yv, a, b)) - case (bl, RedTree(y, yv, BlackTree(z, zv, a, b), c)) => - RedTree(z, zv, BlackTree(x, xv, bl, a), balance(y, yv, b, subl(c))) - case _ => sys.error("Defect: invariance violation at "+right) - } - def balRight(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = (tl, tr) match { - case (a, RedTree(y, yv, b, c)) => - RedTree(x, xv, a, BlackTree(y, yv, b, c)) - case (BlackTree(y, yv, a, b), bl) => - balance(x, xv, RedTree(y, yv, a, b), bl) - case (RedTree(y, yv, a, BlackTree(z, zv, b, c)), bl) => - RedTree(z, zv, balance(y, yv, subl(a), b), BlackTree(x, xv, c, bl)) - case _ => sys.error("Defect: invariance violation at "+left) + 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) + } + } else { + BlackTree(x, xv, tl, tr) } - def delLeft = left match { - case _: BlackTree[_, _] => balLeft(key, value, left.del(k), right) - case _ => RedTree(key, value, left.del(k), right) + 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 "+right) } - def delRight = right match { - case _: BlackTree[_, _] => balRight(key, value, left, right.del(k)) - case _ => RedTree(key, value, left, right.del(k)) + 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 "+left) } - def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = (tl, tr) match { - case (Empty.Instance, t) => t - case (t, Empty.Instance) => t - case (RedTree(x, xv, a, b), RedTree(y, yv, c, d)) => - append(b, c) match { - case RedTree(z, zv, bb, cc) => RedTree(z, zv, RedTree(x, xv, a, bb), RedTree(y, yv, cc, d)) - case bc => RedTree(x, xv, a, RedTree(y, yv, bc, d)) - } - case (BlackTree(x, xv, a, b), BlackTree(y, yv, c, d)) => - append(b, c) match { - case RedTree(z, zv, bb, cc) => RedTree(z, zv, BlackTree(x, xv, a, bb), BlackTree(y, yv, cc, d)) - case bc => balLeft(x, xv, a, BlackTree(y, yv, bc, d)) - } - case (a, RedTree(x, xv, b, c)) => RedTree(x, xv, append(a, b), c) - case (RedTree(x, xv, a, b), c) => RedTree(x, xv, a, append(b, c)) + 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 { + sys.error("unmatched tree on append: " + tl + ", " + tr) } val cmp = ordering.compare(k, key) |