The default response of a tree node on a key request is null. I. e. if a key is not contained, null is returned.
calculating the type, based on native type of the underlying system
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}
convenience method for initializing a van emde boas tree root. This is the default method to get a tree.
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.
precalculated powers of two table for unit testing
This is the struct to represent a VEB tree node. Its members are - a pointer to the stats: universe and current inserted element amount - a pointer to the min and max values. These pointee is used as a bit array in the leaf nodes. - a poitner (or array) to the child nodes, in case the node is not a leaf node - a pointer (an array) to the data pointers, in case the tree is used with data. 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.
bit mask representing size_t.max without uint.max.
bit mask representing uint.max.
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.