Mercurial > projects > ldc
diff tango/tango/util/collection/impl/RBCell.d @ 132:1700239cab2e trunk
[svn r136] MAJOR UNSTABLE UPDATE!!!
Initial commit after moving to Tango instead of Phobos.
Lots of bugfixes...
This build is not suitable for most things.
author | lindquist |
---|---|
date | Fri, 11 Jan 2008 17:57:40 +0100 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tango/tango/util/collection/impl/RBCell.d Fri Jan 11 17:57:40 2008 +0100 @@ -0,0 +1,811 @@ +/* + File: RBCell.d + + Originally written by Doug Lea and released into the public domain. + Thanks for the assistance and support of Sun Microsystems Labs, Agorics + Inc, Loral, and everyone contributing, testing, and using this code. + + History: + Date Who What + 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file + +*/ + + +module tango.util.collection.impl.RBCell; + +private import tango.util.collection.impl.Cell; + +private import tango.util.collection.model.Iterator, + tango.util.collection.model.Comparator; + +/** + * RBCell implements basic capabilities of Red-Black trees, + * an efficient kind of balanced binary tree. The particular + * algorithms used are adaptations of those in Corman, + * Lieserson, and Rivest's <EM>Introduction to Algorithms</EM>. + * This class was inspired by (and code cross-checked with) a + * similar class by Chuck McManis. The implementations of + * rebalancings during insertion and deletion are + * a little trickier than those versions since they + * don't swap Cell contents or use special dummy nilnodes. + * <P> + * It is a pure implementation class. For harnesses, see: + * See_Also: RBTree + * Authors: Doug Lea +**/ + + + + +public class RBCell(T) : Cell!(T) +{ + static bool RED = false; + static bool BLACK = true; + + /** + * The node color (RED, BLACK) + **/ + + package bool color_; + + /** + * Pointer to left child + **/ + + package RBCell left_; + + /** + * Pointer to right child + **/ + + package RBCell right_; + + /** + * Pointer to parent (null if root) + **/ + + private RBCell parent_; + + /** + * Make a new Cell with given element, null links, and BLACK color. + * Normally only called to establish a new root. + **/ + + public this (T element) + { + super(element); + left_ = null; + right_ = null; + parent_ = null; + color_ = BLACK; + } + + /** + * Return a new RBCell with same element and color as self, + * but with null links. (Since it is never OK to have + * multiple identical links in a RB tree.) + **/ + + protected RBCell duplicate() + { + RBCell t = new RBCell(element()); + t.color_ = color_; + return t; + } + + + /** + * Return left child (or null) + **/ + + public final RBCell left() + { + return left_; + } + + /** + * Return right child (or null) + **/ + + public final RBCell right() + { + return right_; + } + + /** + * Return parent (or null) + **/ + public final RBCell parent() + { + return parent_; + } + + + /** + * See_Also: tango.util.collection.model.View.View.checkImplementation. + **/ + public void checkImplementation() + { + + // It's too hard to check the property that every simple + // path from node to leaf has same number of black nodes. + // So restrict to the following + + assert(parent_ is null || + this is parent_.left_ || + this is parent_.right_); + + assert(left_ is null || + this is left_.parent_); + + assert(right_ is null || + this is right_.parent_); + + assert(color_ is BLACK || + (colorOf(left_) is BLACK) && (colorOf(right_) is BLACK)); + + if (left_ !is null) + left_.checkImplementation(); + if (right_ !is null) + right_.checkImplementation(); + } + + /+ + public final void assert(bool pred) + { + ImplementationError.assert(this, pred); + } + +/ + + /** + * Return the minimum element of the current (sub)tree + **/ + + public final RBCell leftmost() + { + auto p = this; + for ( ; p.left_ !is null; p = p.left_) + {} + return p; + } + + /** + * Return the maximum element of the current (sub)tree + **/ + public final RBCell rightmost() + { + auto p = this; + for ( ; p.right_ !is null; p = p.right_) + {} + return p; + } + + /** + * Return the root (parentless node) of the tree + **/ + public final RBCell root() + { + auto p = this; + for ( ; p.parent_ !is null; p = p.parent_) + {} + return p; + } + + /** + * Return true if node is a root (i.e., has a null parent) + **/ + + public final bool isRoot() + { + return parent_ is null; + } + + + /** + * Return the inorder successor, or null if no such + **/ + + public final RBCell successor() + { + if (right_ !is null) + return right_.leftmost(); + else + { + auto p = parent_; + auto ch = this; + while (p !is null && ch is p.right_) + { + ch = p; + p = p.parent_; + } + return p; + } + } + + /** + * Return the inorder predecessor, or null if no such + **/ + + public final RBCell predecessor() + { + if (left_ !is null) + return left_.rightmost(); + else + { + auto p = parent_; + auto ch = this; + while (p !is null && ch is p.left_) + { + ch = p; + p = p.parent_; + } + return p; + } + } + + /** + * Return the number of nodes in the subtree + **/ + public final int size() + { + int c = 1; + if (left_ !is null) + c += left_.size(); + if (right_ !is null) + c += right_.size(); + return c; + } + + + /** + * Return node of current subtree containing element as element(), + * if it exists, else null. + * Uses Comparator cmp to find and to check equality. + **/ + + public RBCell find(T element, Comparator!(T) cmp) + { + auto t = this; + for (;;) + { + int diff = cmp.compare(element, t.element()); + if (diff is 0) + return t; + else + if (diff < 0) + t = t.left_; + else + t = t.right_; + if (t is null) + break; + } + return null; + } + + + /** + * Return number of nodes of current subtree containing element. + * Uses Comparator cmp to find and to check equality. + **/ + public int count(T element, Comparator!(T) cmp) + { + int c = 0; + auto t = this; + while (t !is null) + { + int diff = cmp.compare(element, t.element()); + if (diff is 0) + { + ++c; + if (t.left_ is null) + t = t.right_; + else + if (t.right_ is null) + t = t.left_; + else + { + c += t.right_.count(element, cmp); + t = t.left_; + } + } + else + if (diff < 0) + t = t.left_; + else + t = t.right_; + } + return c; + } + + + + + /** + * Return a new subtree containing each element of current subtree + **/ + + public final RBCell copyTree() + { + auto t = cast(RBCell)(duplicate()); + + if (left_ !is null) + { + t.left_ = left_.copyTree(); + t.left_.parent_ = t; + } + if (right_ !is null) + { + t.right_ = right_.copyTree(); + t.right_.parent_ = t; + } + return t; + } + + + /** + * There's no generic element insertion. Instead find the + * place you want to add a node and then invoke insertLeft + * or insertRight. + * <P> + * Insert Cell as the left child of current node, and then + * rebalance the tree it is in. + * @param Cell the Cell to add + * @param root, the root of the current tree + * Returns: the new root of the current tree. (Rebalancing + * can change the root!) + **/ + + + public final RBCell insertLeft(RBCell Cell, RBCell root) + { + left_ = Cell; + Cell.parent_ = this; + return Cell.fixAfterInsertion(root); + } + + /** + * Insert Cell as the right child of current node, and then + * rebalance the tree it is in. + * @param Cell the Cell to add + * @param root, the root of the current tree + * Returns: the new root of the current tree. (Rebalancing + * can change the root!) + **/ + + public final RBCell insertRight(RBCell Cell, RBCell root) + { + right_ = Cell; + Cell.parent_ = this; + return Cell.fixAfterInsertion(root); + } + + + /** + * Delete the current node, and then rebalance the tree it is in + * @param root the root of the current tree + * Returns: the new root of the current tree. (Rebalancing + * can change the root!) + **/ + + + public final RBCell remove (RBCell root) + { + + // handle case where we are only node + if (left_ is null && right_ is null && parent_ is null) + return null; + + // if strictly internal, swap places with a successor + if (left_ !is null && right_ !is null) + { + auto s = successor(); + // To work nicely with arbitrary subclasses of RBCell, we don't want to + // just copy successor's fields. since we don't know what + // they are. Instead we swap positions _in the tree. + root = swapPosition(this, s, root); + } + + // Start fixup at replacement node (normally a child). + // But if no children, fake it by using self + + if (left_ is null && right_ is null) + { + + if (color_ is BLACK) + root = this.fixAfterDeletion(root); + + // Unlink (Couldn't before since fixAfterDeletion needs parent ptr) + + if (parent_ !is null) + { + if (this is parent_.left_) + parent_.left_ = null; + else + if (this is parent_.right_) + parent_.right_ = null; + parent_ = null; + } + + } + else + { + auto replacement = left_; + if (replacement is null) + replacement = right_; + + // link replacement to parent + replacement.parent_ = parent_; + + if (parent_ is null) + root = replacement; + else + if (this is parent_.left_) + parent_.left_ = replacement; + else + parent_.right_ = replacement; + + left_ = null; + right_ = null; + parent_ = null; + + // fix replacement + if (color_ is BLACK) + root = replacement.fixAfterDeletion(root); + + } + + return root; + } + + /** + * Swap the linkages of two nodes in a tree. + * Return new root, in case it changed. + **/ + + static final RBCell swapPosition(RBCell x, RBCell y, RBCell root) + { + + /* Too messy. TODO: find sequence of assigments that are always OK */ + + auto px = x.parent_; + bool xpl = px !is null && x is px.left_; + auto lx = x.left_; + auto rx = x.right_; + + auto py = y.parent_; + bool ypl = py !is null && y is py.left_; + auto ly = y.left_; + auto ry = y.right_; + + if (x is py) + { + y.parent_ = px; + if (px !is null) + if (xpl) + px.left_ = y; + else + px.right_ = y; + x.parent_ = y; + if (ypl) + { + y.left_ = x; + y.right_ = rx; + if (rx !is null) + rx.parent_ = y; + } + else + { + y.right_ = x; + y.left_ = lx; + if (lx !is null) + lx.parent_ = y; + } + x.left_ = ly; + if (ly !is null) + ly.parent_ = x; + x.right_ = ry; + if (ry !is null) + ry.parent_ = x; + } + else + if (y is px) + { + x.parent_ = py; + if (py !is null) + if (ypl) + py.left_ = x; + else + py.right_ = x; + y.parent_ = x; + if (xpl) + { + x.left_ = y; + x.right_ = ry; + if (ry !is null) + ry.parent_ = x; + } + else + { + x.right_ = y; + x.left_ = ly; + if (ly !is null) + ly.parent_ = x; + } + y.left_ = lx; + if (lx !is null) + lx.parent_ = y; + y.right_ = rx; + if (rx !is null) + rx.parent_ = y; + } + else + { + x.parent_ = py; + if (py !is null) + if (ypl) + py.left_ = x; + else + py.right_ = x; + x.left_ = ly; + if (ly !is null) + ly.parent_ = x; + x.right_ = ry; + if (ry !is null) + ry.parent_ = x; + + y.parent_ = px; + if (px !is null) + if (xpl) + px.left_ = y; + else + px.right_ = y; + y.left_ = lx; + if (lx !is null) + lx.parent_ = y; + y.right_ = rx; + if (rx !is null) + rx.parent_ = y; + } + + bool c = x.color_; + x.color_ = y.color_; + y.color_ = c; + + if (root is x) + root = y; + else + if (root is y) + root = x; + return root; + } + + + + /** + * Return color of node p, or BLACK if p is null + * (In the CLR version, they use + * a special dummy `nil' node for such purposes, but that doesn't + * work well here, since it could lead to creating one such special + * node per real node.) + * + **/ + + static final bool colorOf(RBCell p) + { + return (p is null) ? BLACK : p.color_; + } + + /** + * return parent of node p, or null if p is null + **/ + static final RBCell parentOf(RBCell p) + { + return (p is null) ? null : p.parent_; + } + + /** + * Set the color of node p, or do nothing if p is null + **/ + + static final void setColor(RBCell p, bool c) + { + if (p !is null) + p.color_ = c; + } + + /** + * return left child of node p, or null if p is null + **/ + + static final RBCell leftOf(RBCell p) + { + return (p is null) ? null : p.left_; + } + + /** + * return right child of node p, or null if p is null + **/ + + static final RBCell rightOf(RBCell p) + { + return (p is null) ? null : p.right_; + } + + + /** From CLR **/ + protected final RBCell rotateLeft(RBCell root) + { + auto r = right_; + right_ = r.left_; + if (r.left_ !is null) + r.left_.parent_ = this; + r.parent_ = parent_; + if (parent_ is null) + root = r; + else + if (parent_.left_ is this) + parent_.left_ = r; + else + parent_.right_ = r; + r.left_ = this; + parent_ = r; + return root; + } + + /** From CLR **/ + protected final RBCell rotateRight(RBCell root) + { + auto l = left_; + left_ = l.right_; + if (l.right_ !is null) + l.right_.parent_ = this; + l.parent_ = parent_; + if (parent_ is null) + root = l; + else + if (parent_.right_ is this) + parent_.right_ = l; + else + parent_.left_ = l; + l.right_ = this; + parent_ = l; + return root; + } + + + /** From CLR **/ + protected final RBCell fixAfterInsertion(RBCell root) + { + color_ = RED; + auto x = this; + + while (x !is null && x !is root && x.parent_.color_ is RED) + { + if (parentOf(x) is leftOf(parentOf(parentOf(x)))) + { + auto y = rightOf(parentOf(parentOf(x))); + if (colorOf(y) is RED) + { + setColor(parentOf(x), BLACK); + setColor(y, BLACK); + setColor(parentOf(parentOf(x)), RED); + x = parentOf(parentOf(x)); + } + else + { + if (x is rightOf(parentOf(x))) + { + x = parentOf(x); + root = x.rotateLeft(root); + } + setColor(parentOf(x), BLACK); + setColor(parentOf(parentOf(x)), RED); + if (parentOf(parentOf(x)) !is null) + root = parentOf(parentOf(x)).rotateRight(root); + } + } + else + { + auto y = leftOf(parentOf(parentOf(x))); + if (colorOf(y) is RED) + { + setColor(parentOf(x), BLACK); + setColor(y, BLACK); + setColor(parentOf(parentOf(x)), RED); + x = parentOf(parentOf(x)); + } + else + { + if (x is leftOf(parentOf(x))) + { + x = parentOf(x); + root = x.rotateRight(root); + } + setColor(parentOf(x), BLACK); + setColor(parentOf(parentOf(x)), RED); + if (parentOf(parentOf(x)) !is null) + root = parentOf(parentOf(x)).rotateLeft(root); + } + } + } + root.color_ = BLACK; + return root; + } + + + + /** From CLR **/ + protected final RBCell fixAfterDeletion(RBCell root) + { + auto x = this; + while (x !is root && colorOf(x) is BLACK) + { + if (x is leftOf(parentOf(x))) + { + auto sib = rightOf(parentOf(x)); + if (colorOf(sib) is RED) + { + setColor(sib, BLACK); + setColor(parentOf(x), RED); + root = parentOf(x).rotateLeft(root); + sib = rightOf(parentOf(x)); + } + if (colorOf(leftOf(sib)) is BLACK && colorOf(rightOf(sib)) is BLACK) + { + setColor(sib, RED); + x = parentOf(x); + } + else + { + if (colorOf(rightOf(sib)) is BLACK) + { + setColor(leftOf(sib), BLACK); + setColor(sib, RED); + root = sib.rotateRight(root); + sib = rightOf(parentOf(x)); + } + setColor(sib, colorOf(parentOf(x))); + setColor(parentOf(x), BLACK); + setColor(rightOf(sib), BLACK); + root = parentOf(x).rotateLeft(root); + x = root; + } + } + else + { + auto sib = leftOf(parentOf(x)); + if (colorOf(sib) is RED) + { + setColor(sib, BLACK); + setColor(parentOf(x), RED); + root = parentOf(x).rotateRight(root); + sib = leftOf(parentOf(x)); + } + if (colorOf(rightOf(sib)) is BLACK && colorOf(leftOf(sib)) is BLACK) + { + setColor(sib, RED); + x = parentOf(x); + } + else + { + if (colorOf(leftOf(sib)) is BLACK) + { + setColor(rightOf(sib), BLACK); + setColor(sib, RED); + root = sib.rotateLeft(root); + sib = leftOf(parentOf(x)); + } + setColor(sib, colorOf(parentOf(x))); + setColor(parentOf(x), BLACK); + setColor(leftOf(sib), BLACK); + root = parentOf(x).rotateRight(root); + x = root; + } + } + } + setColor(x, BLACK); + return root; + } +} +