containers.ttree
T-Tree.
License
-
Declaration
struct
TTree
(T, Allocator = Mallocator, bool allowDuplicates = false, alias less = "a < b", bool supportGC = shouldAddGCRange!T, size_t cacheLineSize = 64);Implements a binary search tree with multiple items per tree node.
Discussion
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 andnodeCapacity
items, or it hasnodeCapacity
items and 0 or more children.Parameters
T
the element type
Allocator
the allocator to use. Defaults to
Mallocator
.allowDuplicates
if
true
, duplicate values will be allowed in the treeless
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.
See Also
-
Declaration
this();
No default construction if an allocator must be provided.
-
Declaration
this(Allocator
allocator
);Use
to allocate and free nodes in the tree.allocator
-
Declaration
void
clear
();Removes all elements from the tree.
-
Declaration
void
opOpAssign
(string op)(Tvalue
) if (op == "~");tree ~= item operator overload.
-
Declaration
@safe size_t
insert
(Tvalue
, booloverwrite
= false);
size_tinsert
(R)(Rr
, booloverwrite
= false) if (isInputRange!R && is(ElementType!R == T));
size_tinsert
(T[]values
, booloverwrite
= false);
aliasinsertAnywhere
= insert;
aliasput
= insert;Inserts the given
value
(s) into the tree.Discussion
This is not a stable
insert
. You will get strange results if youinsert
into a tree while iterating over it.Parameters
T
value
the
value
toinsert
bool
overwrite
if
true
the given
will replace the first item in the tree that is equivalent (That is greater-than and less-than are bothvalue
false
) to
. This is useful in cases where opCmp and opEquals forvalue
T
type have different meanings. For example, if the element type is a circle that has a position and a color, the circle could implementopCmp
to sort by color, and calling
withinsert
set tooverwrite
true
would allow you to update the position of the circle with a certain color in the tree.Return Value
the number of
values
added. -
Declaration
bool
remove
(Tvalue
, void delegate(T)cleanup
= null);Removes a single
value
from the tree, or does nothing.Discussion
If
allowDuplicates
istrue
only a single element that is equivalent to the given
will be removed. Which of these elements is removed is not defined.value
Parameters
T
value
a
value
equal to the one to be removedvoid delegate(T)
cleanup
a function that should be run on the removed item
Retuns:
true
if anyvalue
was removed -
Declaration
const @nogc @safe bool
contains
(Tvalue
);Return Value
true
if the tree conains This page contains documentation for the EMSI containers library. Use the package index on the left to explore the documentation. the givenvalue
-
Declaration
const pure nothrow @nogc @property @safe size_t
length
();Return Value
the number of elements in the tree.
-
Declaration
const pure nothrow @nogc @property @safe bool
empty
();Return Value
true
if the tree isempty
. -
Declaration
inout @nogc @trusted auto
opSlice
(this This)();Return Value
a range over the tree. Do not insert into the tree while iterating because you may iterate over the same value multiple times or skip some values entirely.
-
Declaration
inout @trusted auto
lowerBound
(this This)(inout Tvalue
);Return Value
a range of elements which are less than
value
. -
Declaration
inout @trusted auto
equalRange
(this This)(inout Tvalue
);Return Value
a range of elements which are equivalent (though not necessarily equal) to
value
. -
Declaration
inout @trusted auto
upperBound
(this This)(inout Tvalue
);Return Value
a range of elements which are greater than
value
. -
Declaration
inout pure @property @trusted inout(T)
front
(this This)();Return Value
the first element in the tree.
-
Declaration
inout pure @property @trusted inout(T)
back
(this This)();Return Value
the last element in the tree.
-
Declaration
struct
Range
(ThisT);Tree range
-
Declaration
const @nogc @property ET
front
();
const pure nothrow @nogc @property @safe boolempty
();
voidpopFront
();Standard range operations
-
-