OrderedNodeMixin

ordered node implementation

mixin template OrderedNodeMixin (

size_t N

) {

Node _left;

Node _right;

size_t _p;

Node _parent;

inout(typeof(this))* left [@property getter];

inout(typeof(this))* right [@property getter];

Node parent [@property getter];

Node left [@property setter];

Node right [@property setter];

Node rotateR();

Node rotateL();

bool isLeftNode [@property getter];

void setColor(Node end);

Node remove(Node end);

leftmost [@property getter];

rightmost [@property getter];

inout(typeof(this))* next [@property getter];

inout(typeof(this))* prev [@property getter];

}

Members

Functions

remove 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!
rotateL 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.
rotateR 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.
setColor 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.

Properties

isLeftNode bool isLeftNode [@property getter]: Returns true if this node is a left child.
left inout(typeof(this))* left [@property getter]: Get the left child
left Node left [@property setter]: Set the left child. Also updates the new child's parent node. This does not update the previous child.
leftmost leftmost [@property getter]: Return the leftmost descendant of this node.
next inout(typeof(this))* next [@property getter]: Returns the next valued node in the tree.
parent Node parent [@property getter]: Get the parent
prev inout(typeof(this))* prev [@property getter]: Returns the previous valued node in the tree.
right inout(typeof(this))* right [@property getter]: Get the right child
right Node right [@property setter]: Set the right child. Also updates the new child's parent node. This does not update the previous child.
rightmost rightmost [@property getter]: Return the rightmost descendant of this node

Variables

color Color color;: The color of the node.

Meta

Source

See Implementation

util multi_index classes

MultiIndexContainer

enums

Color

mixin templates

structs

templates