TreeMap

Implements an AVL tree backed treemap. Intended to used as an alternative to D's own associative array. If E set to void, then it works more like a regular tree datastructure, and can be indexed with any type K has an opCmp override. nogcIndexing changes the behavior of opIndex if no match is found. If set to true, indexing returns the default value if no match found, which will need some design consideration. If set to false, indexing throws an exception if no match found. Nodes should have the lesser elements on the left side. Behavior can be changed with less.

struct TreeMap (

bool nogcIndexing = true

alias less = "a < b"

) {

E opIndex(K key);

E* ptrOf(K key);

E opIndex(T key);

K opIndex(T key);

auto opIndexAssign(E elem, K key);

E remove(T key);

K put(K key);

K remove(K key);

void rebalance();

int opApply(scope int delegate(ref E) dg);

int opApply(scope int delegate(K, ref E) dg);

int opApplyReverse(scope int delegate(ref E) dg);

int opApplyReverse(scope int delegate(K, ref E) dg);

int opApply(scope int delegate(K) dg);

int opApplyReverse(scope int delegate(K) dg);

size_t length();

string toString();

}

Members

Functions

length size_t length(): Returns the number of currently held elements within the tree.
opApply int opApply(scope int delegate(ref E) dg): Implements a simple left-to-right tree traversal.
opApply int opApply(scope int delegate(K, ref E) dg): Implements a simple left-to-right tree traversal.
opApply int opApply(scope int delegate(K) dg): Implements a simple left-to-right tree traversal by depth.
opApplyReverse int opApplyReverse(scope int delegate(ref E) dg): Implements a simple right-to-left tree traversal.
opApplyReverse int opApplyReverse(scope int delegate(K, ref E) dg): Implements a simple right-to-left tree traversal.
opApplyReverse int opApplyReverse(scope int delegate(K) dg): Implements a simple right-to-left tree traversal.
opIndex E opIndex(K key): @nogc capable indexing. Can be indexed with any type of value as long as K.opCmp supports it. Returns the found element if match found. Returns E.init if match not found.
opIndex E opIndex(T key): Indexing function that relies on the GC, and throws if no match found Can be indexed with any type of value as long as K.opCmp supports it. Returns the found element if match found.
opIndex K opIndex(T key): @nogc capable indexing. Can be indexed with any type of value as long as K.opCmp supports it. Returns the found element if match found. Returns E.init if match not found.
opIndex K opIndex(T key): Indexing function that relies on the GC, and throws if no match found Can be indexed with any type of value as long as K.opCmp supports it. Returns the found element if match found.
opIndexAssign auto opIndexAssign(E elem, K key): Assigns a value to the given key. If key found, the value will be overwritten without node insertion. If key isn't found, a new node will be inserted.
ptrOf E* ptrOf(K key): Returns the pointer of the element, or null if key not found.
put K put(K key): Puts an element into the TreeMap
rebalance void rebalance(): Rebalances the tree.
remove E remove(T key): Removes an item by key. Returns the removed item if found, or E.init if not.
remove K remove(K key): Removes an item by key. Returns the removed item if found, or K.init if not.
toString string toString(): returns the string representation of the tree.

TreeMap

Members

Functions

Meta

Source