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 (

Allocator = Mallocator

bool allowDuplicates = false

alias less = "a < b"

bool supportGC = shouldAddGCRange!T

size_t cacheLineSize = 64

) {

this(this);

this();

this(Allocator allocator);

alias AllocatorType = void*;

~this();

alias Value = ContainerStorageType!T;

void opOpAssign(T value);

bool insert(T value);

bool insert(R r);

bool insert(T[] values);

alias put = insert;

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);

}

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

~this ~this(): Undocumented in source.

Postblit

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

Members

Aliases

AllocatorType alias AllocatorType = void*: Undocumented in source.
Value alias Value = ContainerStorageType!T: Undocumented in source.
opSlice alias opSlice = range: Undocumented in source.
put alias put = insert: Undocumented in source.

Functions

contains bool contains(T value)
empty bool empty()
equalRange auto equalRange(T value)
insert bool insert(T value)
bool insert(R r)
bool insert(T[] values): Inserts the given value into the tree.
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

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