OrderedNodeMixin

ordered node implementation

mixin template OrderedNodeMixin (

size_t N

) {

alias Node = typeof(this)*;

version(PtrHackery)

version(PtrHackery)

Node _parent [@property setter];

version(PtrHackery)

Node _parent [@property getter];

version(PtrHackery)

Color color [@property setter];

version(PtrHackery)

Color color [@property getter];

version(!PtrHackery)

Node _parent;

version(!PtrHackery)

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];

parentmost [@property getter];

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

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

}

Members

Aliases

Node alias Node = typeof(this)*: Undocumented in source.

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

_parent Node _parent [@property setter]: Undocumented in source. Be warned that the author may not have intended to support it.
_parent Node _parent [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
color Color color [@property setter]: Undocumented in source. Be warned that the author may not have intended to support it.
color Color color [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
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
parentmost parentmost [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
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

_left Node _left;: Undocumented in source.
_p size_t _p;: Undocumented in source.
_parent Node _parent;: Undocumented in source.
_right Node _right;: Undocumented in source.
color Color color;: The color of the node.

Meta

Source

See Implementation