tango.util.container.RedBlack

License:

Version:

Authors:

Since:

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