VEBnode

This is the struct to represent a VEB tree node. As memebers it contains a value and a pointer to the children array. As the pointer does not know the size of the array, it has to be passed in all methods, which require an access to it. Dependent from the (universe) size passed in a method the stored value will be interpretated in two different ways: If the parameter passed shows, that the universe size is below the bit size of the stored value, then, it can be handled as a bit array and all operations decay to operations defined in core.bitop. This case correspond to the state of the node being a leaf. No children exist and the pointer should stay uninitialized Otherwise, the value is interpretated as two values, the minimum and maximum stored at the same place in memory. The minimum and maximum shows, which range is achievable through this node. The parameters passed to a function of the node have to be well chosen, to hit the appropriate child. The first element of the children array, if present is handled different. According to literature, it has the role of the summary of the remaining children cluster. With it help it is possible to achieve a very small recursion level during an access.

Constructors

this this(): Undocumented in source.
this this(size_t uS): 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

insert bool insert(size_t bitnum): insert method. given a leaf, sets the bit and returns, whether the bit was unset. Overloads by passing only one parameter, which is the bit number of interest.
insert bool insert(size_t value, size_t uS): insert method. this method is called from class with a universe size given. It performs recursion calls untill the universe size is reduced to the base size. Then the overloaded insert method is called.
member bool member(size_t value, size_t uS): member method. this method is called from class with a universe size given. It performs recursion calls until the universe size is reduced to the base size. Then the overloaded member method is called.
opIn_r bool opIn_r(size_t bitnum): 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.
predecessor Nullable!(size_t, maxSizeBound) predecessor(size_t bitNum): predecessor method. given a leaf, returns the previous set bit if exists, otherwise Nullable.null. Overloads by passing only one parameter, which is the bit number of interest.
predecessor Nullable!(size_t, maxSizeBound) predecessor(size_t value, size_t uS): predecessor method. this method is called from class with a universe size given. It performs recursion calls until the universe size is reduced to the base size. Then the overloaded predecessor method is called.
remove bool remove(size_t bitnum): remove method. given a leaf, remove the bit and returns, whether the bit was set. Overloads by passing only one parameter, which is the bit number of interest.
remove bool remove(size_t value, size_t uS): remove method. this method is called from class with a universe size given. It performs recursion calls untill the universe size is reduced to the base size. Then the overloaded remove method is called.
successor Nullable!(size_t, maxSizeBound) successor(size_t bitNum): successor method. given a leaf, returns the next set bit if exists, otherwise Nullable.null. Overloads by passing only one parameter, which is the bit number of interest.
successor Nullable!(size_t, maxSizeBound) successor(size_t value, size_t uS): successor method. this method is called from class with a universe size given. It performs recursion calls until the universe size is reduced to the base size. Then the overloaded successor method is called.

Properties

cluster VEBnode* cluster [@property getter]: property returning the cluster array
isLeaf bool isLeaf [@property getter]: convinience method to check, if the node belongs to the lowest level in the tree
isNull bool isNull [@property getter]: method to check whether the current node holds a value
max Nullable!(size_t, maxSizeBound) max [@property getter]: method returning either the higher part of the stored value (intermediate node) or the highest bit set (bit vector mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned.
max size_t max [@property setter]: setter for the max, setting either the highest bit or the max part of the value.
min Nullable!(size_t, maxSizeBound) min [@property getter]: method returning either the lower part of the stored value (intermediate node) or the lowest bit set (bit vector mode. If the node does not contain any value (min > max or value == 0) Nullable.null is returned.
min size_t min [@property setter]: setter for the min, setting either the lowest bit or the min part of the value.
nullify void nullify [@property getter]: method executing the appropriate steps to nullify the current node
summary VEBnode summary [@property getter]: property returning the summary node

Unions

__anonymous union __anonymous: Undocumented in source.

Examples

VEBnode vN = VEBnode(baseSize); 
static assert(vN.sizeof < baseSize/2); 
assert(vN.isNull); 
assert(vN.sizeof == 2 * size_t.sizeof); 
assert(vN.isLeaf); 
assert(vN.isNull); 
vN._val = 3; 
assert(vN._min == 3);
assert(1 in vN);
assert(!(2 in vN));
assert(vN.isLeaf);
assert(vN.ptrArr == null); 
vN.nullify; 
assert(vN.isNull); 
assert(vN._val == 0);