License: see license.txt struct RBNode (V); Implementation for a Red Black node for use in a Red Black Tree (see below) this implementation assumes we have a marker Node that is the parent of the root Node. This marker Node is not a valid Node, but marks the end of the collection. The root is the left child of the marker Node, so it is always last in the collection. The marker Node is passed in to the setColor function, and the Node which has this Node as its parent is assumed to be the root Node. A Red Black tree should have O(lg(n)) insertion, removal, and search time. alias Node ; Convenience alias V value ; The value held by this node enum Color ; Enumeration determining what color the node is. Null nodes are assumed to be black. Color color ; The color of the node. Node left (); Get the left child Node right (); Get the right child Node parent (); Get the parent Node left (Node newNode); Set the left child. Also updates the new child's parent node. This does not update the previous child. Returns newNode Node right (Node newNode); Set the right child. Also updates the new child's parent node. This does not update the previous child. Returns newNode Node rotateR (); Rotate right. This performs the following operations: - The left child becomes the parent of this node. - This node becomes the new parent's right child. - The old right child of the new parent becomes the left child of this node. Node rotateL (); Rotate left. This performs the following operations: - The right child becomes the parent of this node. - This node becomes the new parent's left child. - The old left child of the new parent becomes the right child of this node. bool isLeftNode (); Returns true if this node is a left child. Note that this should always return a value because the root has a parent which is the marker node. void setColor (Node end); Set the color of the node after it is inserted. This performs an update to the whole tree, possibly rotating nodes to keep the Red-Black properties correct. This is an O(lg(n)) operation, where n is the number of nodes in the tree. Node remove (Node end); Remove this node from the tree. The 'end' node is used as the marker which is root's parent. Note that this cannot be null! Returns the next highest valued node in the tree after this one, or end if this was the highest-valued node. Node leftmost (); Return the leftmost descendant of this node. Node rightmost (); Return the rightmost descendant of this node Node next (); Returns the next valued node in the tree. You should never call this on the marker node, as it is assumed that there is a valid next node. Node prev (); Returns the previous valued node in the tree. You should never call this on the leftmost node of the tree as it is assumed that there is a valid previous node. struct RBTree (V,alias compareFunc,alias updateFunction,alias Allocator = DefaultAllocator,bool allowDuplicates = false,bool doUpdates = true); Implementation of a red black tree. This uses RBNode to implement the tree. Set allowDuplicates to true to allow duplicate values to be inserted. alias Node ; Convenience alias alias allocator ; alias for the allocator allocator alloc ; The allocator uint count ; The number of nodes in the tree Node end ; The marker Node. This is the parent of the root Node. void setup (); Setup this RBTree. bool add (V v); Add a Node to the RBTree. Runs in O(lg(n)) time. Returns true if a new Node was added, false if it was not. This can also be used to update a value if it is already in the tree. Node begin (); Return the lowest-valued Node in the tree Node remove (Node z); Remove the Node from the tree. Returns the next Node in the tree. Do not call this with the marker (end) Node. Node find (V v); Find a Node in the tree with a given value. Returns end if no such Node exists. void clear (); clear all the nodes from the tree. template RBNoUpdatesTree (V,alias compareFunc,alias Allocator = DefaultAllocator) used to define a RB tree that does not require updates. template RBDupTree (V,alias compareFunc,alias Allocator = DefaultAllocator) used to define a RB tree that takes duplicates

(C) 2008 by Steven Schveighoffer. All rights reserved :: page rendered by CandyDoc