tango.util.container.RedBlack

License:

BSD style: see license.txt

Version:

Apr 2008: Initial release

Authors:

Kris, tsalm

Since:

0.99.7

Based upon Doug Lea's Java collection package
struct RedBlack(V, A = AttributeDummy)
RedBlack 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 Introduction to Algorithms. 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.
Doug Lea
Ref left [package]
Pointer to left child
Ref right [package]
Pointer to right child
Ref parent [package]
Pointer to parent (null if root)
bool color [package]
The node color (RED, BLACK)
Ref set(V v) [final]
Make a new Cell with given value, null links, and BLACK color. Normally only called to establish a new root.
Ref dup(scope Ref delegate() alloc) [protected]
Return a new Ref with same value and color as self, but with null links. (Since it is never OK to have multiple identical links in a RB tree.)
void checkImplementation() [public]

See Also:

tango.util.collection.model.View.View.checkImplementation.
Ref leftmost()
Return the minimum value of the current (sub)tree
Ref rightmost()
Return the maximum value of the current (sub)tree
Ref root()
Return the root (parentless node) of the tree
bool isRoot()
Return true if node is a root (i.e., has a null parent)
Ref successor()
Return the inorder successor, or null if no such
Ref predecessor()
Return the inorder predecessor, or null if no such
size_t size() [@property]
Return the number of nodes in the subtree
Ref find(V value, Compare!(V) cmp)
Return node of current subtree containing value as value(), if it exists, else null. Uses Comparator cmp to find and to check equality.
Ref findFirst(V value, Compare!(V) cmp, bool after = true)
Return node of subtree matching "value" or, if none found, the one just after or before if it doesn't exist, return null Uses Comparator cmp to find and to check equality.
int count(V value, Compare!(V) cmp)
Return number of nodes of current subtree containing value. Uses Comparator cmp to find and to check equality.
Ref find(V value, A attribute, Compare!(V) cmp)
find and return a cell holding (key, element), or null if no such
Ref copyTree(scope Ref delegate() alloc)
Return a new subtree containing each value of current subtree
Ref insertLeft(Ref cell, Ref root)
There's no generic value insertion. Instead find the place you want to add a node and then invoke insertLeft or insertRight.

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!)
Ref insertRight(Ref cell, Ref 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!)
Ref remove(Ref 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!)
Ref swapPosition(Ref x, Ref y, Ref root) [static]
Swap the linkages of two nodes in a tree. Return new root, in case it changed.
bool colorOf(Ref p) [static]
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.)
Ref parentOf(Ref p) [static]
return parent of node p, or null if p is null
void setColor(Ref p, bool c) [static]
Set the color of node p, or do nothing if p is null
Ref leftOf(Ref p) [static]
return left child of node p, or null if p is null
Ref rightOf(Ref p) [static]
return right child of node p, or null if p is null
Ref rotateLeft(Ref root) [package]
From CLR
Ref rotateRight(Ref root) [package]
From CLR
Ref fixAfterInsertion(Ref root) [package]
From CLR
Ref fixAfterDeletion(Ref root) [package]
From CLR