TTree

Implements a binary search tree with multiple items per tree node.

T-tree Nodes are (by default) sized to fit within a 64-byte cache line. The number of items stored per node can be read from the nodeCapacity enum. Each node has 0, 1, or 2 children. Each node has between 1 and nodeCapacity items, or it has nodeCapacity items and 0 or more children.

Inserting or removing items while iterating a range returned from opSlice, upperBound, equalRange, or other similar functions will result in unpredicable and likely invalid iteration orders.

struct TTree (

Allocator = Mallocator

bool allowDuplicates = false

alias less = "a < b"

bool supportGC = shouldAddGCRange!T

size_t cacheLineSize = 64

) {

this(this);

this();

this(Allocator allocator);

void clear();

void opOpAssign(T value);

size_t insert(T value, bool overwrite);

size_t insert(R r, bool overwrite);

size_t insert(T[] values, bool overwrite);

alias insertAnywhere = insert;

alias put = insert;

bool remove(T value, void delegate(T) cleanup);

bool contains(T value);

size_t length();

bool empty();

auto opSlice();

auto lowerBound(T value);

auto equalRange(T value);

auto upperBound(T value);

auto front();

auto back();

struct Range(ThisT);

enum size_t nodeCapacity;

}

Constructors

this this(): No default construction if an allocator must be provided.
this this(Allocator allocator): Use allocator to allocate and free nodes in the tree.

Destructor

A destructor is present on this object, but not explicitly documented in the source.

Postblit

this(this) this(this): T-Trees are not copyable due to the way they manage memory and interact with allocators.

Members

Aliases

insertAnywhere alias insertAnywhere = insert
put alias put = insert: Inserts the given value(s) into the tree.

Functions

back auto back()
clear void clear(): Removes all elements from the tree.
contains bool contains(T value)
empty bool empty()
equalRange auto equalRange(T value)
front auto front()
insert size_t insert(T value, bool overwrite)
size_t insert(R r, bool overwrite)
size_t insert(T[] values, bool overwrite): Inserts the given value(s) into the tree.
length size_t length()
lowerBound auto lowerBound(T value)
opOpAssign void opOpAssign(T value): tree ~= item operator overload.
opSlice auto opSlice()
remove bool remove(T value, void delegate(T) cleanup): Removes a single value from the tree, or does nothing.
upperBound auto upperBound(T value)

Structs

Range struct Range(ThisT): Tree range

Variables

nodeCapacity enum size_t nodeCapacity;: The number of values that can be stored in a single T-Tree node.

Parameters

T: the element type
Allocator: the allocator to use. Defaults to Mallocator.
allowDuplicates: if true, duplicate values will be allowed in the tree
less: the comparitor function to use
supportGC: true if the container should support holding references to GC-allocated memory.
cacheLineSize: Nodes will be sized to fit within this number of bytes.

The OpenD Programming Language