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.
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 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 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.
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 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 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 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 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 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 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.
property returning the cluster array
convinience method to check, if the node belongs to the lowest level in the tree
method to check whether the current node holds a value
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.
setter for the max, setting either the highest bit or the max part of the value.
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.
setter for the min, setting either the lowest bit or the min part of the value.
method executing the appropriate steps to nullify the current node
property returning the summary node
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);
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.