vebTree

This class represents the VEB tree itself. For the sake of convinience it saves the provided at the initialization step wished maximum element. However at the point of development it is only used for testing. Beyond this, it stores only the reference to the root element, as the theory tells.

Constructors

this this(): default constructor of a VEB tree is disabled.
this this(uint maximumElement): to construct a VEB tree one should provide the maximum element one wish to be able to store.
this this(uint[] range): another possibility is to construct a VEB tree by providing an array.

Members

Functions

capacity size_t capacity(): this method returns the capacity of the tree. It is equal to the next power of two with regard to the maximum element
fill uint fill(uint[] arr, uint fillPercentage): Undocumented in source. Be warned that the author may not have intended to support it.
fill uint fill(uint m): Undocumented in source. Be warned that the author may not have intended to support it.
insert void insert(uint x): this method is used to add an element to the tree. duplicate values will be ignored.
member bool member(uint x): this method is used to determine, whether an element is currently present in the tree
opIndex uint[] opIndex(uint i): This is a nontrivial opIndex operator on indizies of the tree. Given an index a range (!) is returned, which is, either the range of elements in the tree build up by [predecessor(i) .. successor(i)] (i. e. excluding the successor(i)), when the given index is not set. Or, if the given index is set, [member(i), successor(i)]. If an index out of bounds is given, an empty array is returned. The tree must not be empty to use this function.
opSlice uint[] opSlice(): opSlice operator to get the underlying array. This is a draft version, as it uses the successor method of the class. So getting the underlying array is proportional to n. As this functionaly is not seen as crucial, it is enough for the first time.
opSlice uint[] opSlice(uint begin, uint end): opSlice operator to get the underlying array between given bounds. This is a draft version, as it uses the successor method of the class. So getting the underlying array is proportional to min(n, m), where n is the number of elements between bounds and m are the number of present elements in the tree.
popBack void popBack(): Undocumented in source. Be warned that the author may not have intended to support it.
popFront void popFront(): Undocumented in source. Be warned that the author may not have intended to support it.
predecessor Nullable!uint predecessor(uint x): this method retrieves the predecessor of the given input.
remove void remove(uint x): this method is used to remove elements from the tree. not existing values will be ignored.
successor Nullable!uint successor(uint x): this method retrieves the successor of the given input.

Properties

back Nullable!uint back [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
elementCount size_t elementCount [@property getter]: This method returns the amount of elements currently present in the tree. This is a draft version, as it uses the slice operator of the class. So getting this number has a complexity proportional to n. As this functionaly is not seen as crucial, it is enough for the first time.
elementCount_ut size_t elementCount_ut [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
empty bool empty [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
front Nullable!uint front [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.
max Nullable!uint max [@property getter]: this method is used to determine the maximum of the tree
min Nullable!uint min [@property getter]: this method is used to determine the minimum of the tree
save vebTree save [@property getter]: Undocumented in source. Be warned that the author may not have intended to support it.

Inherited Members

From Iveb

insert void insert(uint x): Undocumented in source.
remove void remove(uint x): Undocumented in source.
member bool member(uint x): Undocumented in source.
min Nullable!uint min(): Undocumented in source.
max Nullable!uint max(): Undocumented in source.
successor Nullable!uint successor(uint x): Undocumented in source.
predecessor Nullable!uint predecessor(uint x): Undocumented in source.

Examples

assert(!__traits(compiles, new vebTree())); 
vebTree vT = new vebTree(1000); 
assert(vT.capacity == 1024); 
assert(vT.min.isNull); 

vT.insert(2); 
vT.insert(5); 
assert(!vT.member(8)); 
vT.insert(88);
vT.insert(8); 
assert(vT.predecessor(75) == 8); 
assert(vT.successor(6) == 8); 
assert(!vT.member(1029)); 
vT.insert(1029); 
assert(!vT.member(1029)); 


assert(!vT.member(865)); 
vT.insert(865); 
assert(vT.member(865)); 
vT.insert(865); 
assert(vT.member(865)); 
assert(!vT.member(866)); 
vT.remove(866); 
assert(vT.member(865)); 
vT.remove(865); 
assert(!vT.member(865));

uint currentSeed = 83843; // unpredictableSeed();
rndGenInUse.seed(currentSeed); //initialize the random generator
uint M = uniform(0U,1 << 14, rndGenInUse); //set universe size to some integer. 
//M = 30_000_000; 
vebTree vT = new vebTree(M); //create the tree
assert(vT.capacity == nextPowerOfTwo(M)); 
uint m = vT.fill(1000); //(try to) fill the tree with thousend values 
uint n; 
Nullable!uint i = vT.predecessor(vT.max)+1; 
// discover the thousend (or little less) values with the predecessor method
while(!i.isNull)
{
    ++n; 
    i = vT.predecessor(i); 
}
// assert, that all members are discovered, iff when no predecessors are left
assert(n == m);