This class represents the VEB tree itself. It saves the provided at the initialization step wished size. The generated tree has the capacity of the next higher power of 2. Beyond this, it stores the root element, through which all accesses to the tree are managed. The tree implements also the interface for being a bidirectional range.
This function returns the higher square root of the given input. It is needed in the initialization step of the VEB tree to calculate the number of children of a given layer. And this is the universe size of the summary of a node. The upper square root is defined by 2^{\lceil(\lg u)/2\rceil}
This function returns the lower square root of the given input. It is needed by the indexing functions high(x), low(x) and index(x,y) of elements in the tree. Also, this is the universe size of a child of a node. The lower square root is defined by 2^{\lfloor(\lgu)/2\rfloor}
the baseSize defines the cutoff limit, where the node goes into the bit array mode. It is parametrized on the size of size_t and changes dynamically with the architecture used.
the maxSizeBound defines the maximum the tree can be constructed with. It is parametrized on the size of size_t and changes dynamically with the architecture used.
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.
As an important optimization a bottom out technique is used to compactify the tree to the level of nodes, where bit operations become possible. As a side effect, the optimization now relies on the underlying architecture. This leads to the fact, that the maximum of elements which can be stored is 2^16 on a 32-bit architecture and 2^32 on a 64-bit architecture. This was intentionally chosen for two reasons: i) to keep the size of a single node also depending from the underlying architecture. ii) for bitoperations, which the tree is relying on, to use the native word size of the architecture without emulating bigger entities.