Struct StackTree

An AVL tree implementation on top of RegionAllocator. If elements are removed, they are stored on an internal free list and recycled when new elements are added to the tree.

struct StackTree(T, alias key, alias compFun) ;

Template paramters:

T = The type to be stored in the tree.

key = Function to access the key that what you're storing is to be compared on.

compFun = The function for comparing keys.

Constructors

NameDescription
this

Fields

NameTypeDescription
alloc RegionAllocator
freeList StackTreeAA.Node**
head StackTreeAA.Node*
_length size_t

Properties

NameTypeDescription
length[get] size_tNumber of elements in the tree.

Methods

NameDescription
find Find an element and return it. Throw an exception if it is not present. U is expected to be the type of the key that this tree is sorted on.
findImpl
insert Insert an element.
insertComp
insertImpl
newNode
opApply Iterate over the elements of this tree in sorted order.
opIn_r Find an element and return a pointer to it, or null if not present.
popFreeList
pushFreeList
rebalance
remove Remove an element from this tree. The type of U is expected to be the type of the key that this tree is sorted on.
rotateLeft
rotateRight

Aliases

NameDescription
BitwiseNode
comp
getKey
RealNode

Examples

struct StringNum {
    string someString;
    uint num;
}

// Create a StackTree of StringNums, sorted in descending order, using
// someString for comparison.
auto alloc = newRegionAllocator();
auto myTree = StackTree!(StringNum, "a.someString", "a > b")(alloc);

// Add some elements.
myTree.insert( StringNum("foo", 1));
myTree.insert( StringNum("bar", 2));
myTree.insert( StringNum("foo", 3));

assert(myTree.find("foo") == StringNum("foo", 3));
assert(myTree.find("bar") == StringNum("bar", 2));

Note

This tree supports a compile-time interface similar to StackSet and can be used as a finite set implementation.

Warning

This implementation places removed nodes on an internal free list and recycles them, since there is no way to delete RegionAllocator-allocated data in a non-LIFO order. Therefore, you may not retain the address of a variable stored in a StackTree after deleting it from the StackTree. For example, DO NOT do this: 

SomeType* myPtr = "foo" in myTree;
myTree.remove("foo");
*myPtr = someValue;