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.

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.

struct StackTree (

alias key = "a"

alias compFun = "a < b"

) {

this(RegionAllocator alloc);

void insert(T toInsert);

void remove(U whatToRemove);

T find(U whatToFind);

T* opBinaryRight(U whatToFind);

int opApply(int delegate(ref T) dg);

size_t length [@property getter];

}

Members

Functions

find T find(U whatToFind): 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.
insert void insert(T toInsert): Insert an element.
opApply int opApply(int delegate(ref T) dg): Iterate over the elements of this tree in sorted order.
opBinaryRight T* opBinaryRight(U whatToFind): Find an element and return a pointer to it, or null if not present.
remove void remove(U whatToRemove): 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.

Properties

length size_t length [@property getter]: Number of elements in the tree.

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;

The OpenD Programming Language

StackTree

Constructors

Members

Functions

Properties

Examples

Meta

Source