VEBroot

A van Emde Boas node implementation

Constructors

this this(size_t val): It is allowed to construct the root of the van Emde Boas tree directly, without the convenience method.

Postblit

this(this) this(this): Node constructor. A universe size provided, if the size is below the cutoff there is nothing to be done, as the underlying value created and set to zero by default. If otherwise create an array of children. This array has to be (according to Cormen) of size of higher square root of the current universe size + 1. The extra place is reserved for the summary. For each just created child call its constructor. For the summary with the universe size of the higher square root of the current universe size. For each other child with the universe size of the lower square root of the currennt universe size. Then, assign the fully initialized children array to the pointer in the current node, doing approprate steps to show, that this node is an intermediate node, not containing any values yet. The knowledge of the current universe size is lost at this moment. As this keeps every build up node smaller (and there could be a lot of them). This is why, the VEBtree class continues to hold the global universe size, which is passed on every call to the root node. In this way this, extern saved value has the role of being outsourced array size for each (!) node in the tree, as its size is reconstructed during the access to them.

Members

Functions

back size_t back(): The maximal contained key in the van Emde Boas tree
capacity size_t capacity(): As a usual container, van Emde Boas tree provides the notion of capacity
dup typeof(this) dup(): yields a deep copy of the node. I. e. copies all data in children and allocates another tree
empty bool empty(): the empty method to inform of an empty state of the tree.
front size_t front(): The minimal contained key in the van Emde Boas tree
insert bool insert(size_t val): The insertion method of the van Emde Boas tree.
isLeaf bool isLeaf(): This yields whether the node is a leaf node.
length size_t length(): This tree has a length notion: it is the current number of inserted elements.
next size_t next(size_t val): The successor search method of the van Emde Boas tree.
opApply int opApply(int delegate(ref size_t) @(nogc) operations)
int opApply(int delegate(ref size_t, ref size_t) @(nogc) operations)
int opApply(int delegate(ref size_t) operations)
int opApply(int delegate(ref size_t, ref size_t) operations): the opApply method grants the correct foreach behavior, nogc version
opBinaryRight bool opBinaryRight(size_t key): member method for the case universe size < base size. Overloads by passing only one parameter, which is the bit number of interest. Returns whether the appropriate bit inside the bitvector is set.
opCall auto opCall(): ()-slicing. Yields a "random access range" with the content of the tree. Keys can be NIL.
opEquals bool opEquals(T input): Equality operator checks for any iterable, whether in contains the same values, as the current tree.
opIndex auto opIndex(): []-slicing. Yields a "random access range" with the content of the tree, always containing zero and the key after the maximum element as keys. The key after the maximal key is the universe, if the tree is empty or the maximal contained key is lesser then empty, otherwise the capacity of the tree.
prev size_t prev(size_t val): The predecessor search method of the van Emde Boas tree.
remove bool remove(size_t val): remove method of the van Emde Boas tree
universe size_t universe(): The cached value of the universe, provided on creation

VEBroot

Constructors

Postblit

Members

Functions

Meta

Source