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 field. 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.

struct TTree (

bool allowDuplicates = false

alias less = "a < b"

bool supportGC = true

size_t cacheLineSize = 64

) {

this(this);

~this();

enum size_t nodeCapacity;

alias Value = ContainerStorageType!T;

void opOpAssign(T value);

bool insert(T value);

bool insert(R r);

bool insert(T[] values);

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

bool contains(T value);

size_t length();

bool empty();

auto range();

alias opSlice = range;

auto lowerBound(T value);

auto equalRange(T value);

auto upperBound(T value);

struct Range(ThisT);

}

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Aliases

Value alias Value = ContainerStorageType!T: Undocumented in source.
opSlice alias opSlice = range: Undocumented in source.

Functions

contains bool contains(T value): Returns true if the tree _conains the given value
empty bool empty()
equalRange auto equalRange(T value)
insert bool insert(T value)
bool insert(R r)
bool insert(T[] values): Returns true if any values were added. This is not a stable insert. You will get strange results if you insert into a tree while iterating over it.
length size_t length()
lowerBound auto lowerBound(T value)
opOpAssign void opOpAssign(T value): tree ~= item operator overload.
range auto range()
remove bool remove(T value, void delegate(T) cleanup): Removes a value from the tree.
upperBound auto upperBound(T value)

Structs

Range struct Range(ThisT): Tree range

Variables

nodeCapacity enum size_t nodeCapacity;: Undocumented in source.

Parameters

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