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}
Convinience function to return the ceiling to the next power of two of the given input.
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 maxSize 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.
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.