fill

uint currentSeed = 433849; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = fill(M); //fill the tree with some values 
Nullable!uint i = vT.max; 

// remove all members beginning from the maximum
while(!i.isNull)
{
    vT.remove(i); 
    auto j = vT.predecessor(i); 
    if(!j.isNull)
        assert(j != i); 
    i = j; 
}
// assert, that all members are removed, iff when no predecessors are left. 
assert(vT.empty); 

uint currentSeed = 438749; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = fill(M); //fill the tree with some values 
Nullable!uint i = vT.min-1;

// remove all members beginning from the minimum
while(!i.isNull)
{
    vT.remove(i); 
    auto j = vT.successor(i); 
    if(!j.isNull)
        assert(j != i); 
    i = j; 
} 
// assert, that all members are removed, iff when no successors are left.
assert(vT.empty); 

uint M = 1 << 16; 
vebTree vT = new vebTree(M); 
vT.insert(0x000f); 
assert(vT.predecessor(0x000f).isNull);
vT.insert(0x00f0);
assert(vT.predecessor(0x00f0) == 0x000f); 
vT.insert(0x0f00); 
assert(vT.predecessor(0x0f00) == 0x00f0); 
vT.insert(0xf000); 
assert(vT.predecessor(0xf000) == 0x0f00);

vT.remove(0xf000); 
assert(vT.predecessor(0xf000) == 0x0f00);
vT.remove(0x0f00); 
assert(vT.predecessor(0x0f00) == 0x00f0); 
vT.remove(0x00f0); 
assert(vT.predecessor(0x00f0) == 0x000f); 
vT.remove(0x000f); 
assert(vT.predecessor(0x000f).isNull);

uint M = 1 << 16; 
vebTree vT = new vebTree(M); 
vT.insert(0xf000); 
assert(vT.member(0xf000)); 
vT.insert(0x0f00); 
assert(vT.member(0x0f00)); 
vT.insert(0x00f0);
assert(vT.member(0x00f0)); 
vT.insert(0x000f); 
assert(vT.member(0x000f)); 

vT.remove(0xf000); 
assert(!vT.member(0xf000)); 
vT.remove(0x0f00); 
assert(!vT.member(0x0f00)); 
vT.remove(0x00f0); 
assert(!vT.member(0x00f0)); 
vT.remove(0x000f); 
assert(!vT.member(0x000f)); 

//stress test
uint currentSeed = 1948642567; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
// do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 
uint M = uniform(0U, 1 << 14, rndGenInUse); // set universe size to some integer. 
vebTree vT = new vebTree(M); 
uint[] arr; 
auto howMuchFilled = vT.fill(arr); 
assert(arr.length == howMuchFilled); 

vebTree vT2 = new vebTree(M); 
assert(vT2.capacity == vT.capacity); 

import std.datetime; import std.conv : to;
import std.container;
auto rbt = redBlackTree!uint(0); 
rbt.clear; 

void fill1()
{
    foreach(uint i; arr)
    {
        vT2.insert(i); 
    }
}

void fill2()
{
    foreach(uint i; arr)
    {
        rbt.insert(i); 
    }
}

/*
import std.stdio; 
writeln("howMuchFilled: ", howMuchFilled);
auto r = benchmark!(fill1, fill2)(1); 
auto f0Result = to!Duration(r[0]); 
auto f1Result = to!Duration(r[1]); 
writeln("VEB: ", f0Result); 
writeln("rbt: ", f1Result); 
assert(f0Result < f1Result); 
*/

import std.algorithm; 
uint currentSeed = 1230394; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer.
uint[] sourceArr; 
sourceArr.length = M; 
// generate a random array as the source for the tree
for(uint i = 0; i < M; i++) sourceArr[i] = uniform(0U, M, rndGenInUse); 

// constructor to test
vebTree vT = new vebTree(sourceArr); 

// make the array values unique. 
auto uniqueArr = sort(sourceArr).uniq;
// check, that all values are filled 
foreach(uint i; uniqueArr)
{
    assert(vT.member(i)); 
    vT.remove(i); 
}
// check, that no other elements are present. 
assert(vT.empty); 

uint currentSeed = 2349062; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
// do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = new vebTree(M); 
uint[] arr; 
vT.fill(arr, 16); 
import std.algorithm;
assert(setSymmetricDifference(vT[], sort(arr)).empty); 

uint currentSeed = 2309532090; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
// do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = new vebTree(M); 
uint[] arr; 
vT.fill(arr, 16); 

uint begin = 5; 
uint end = 100; 

import std.algorithm; 
auto filterRes = sort(arr).filter!(a => a >= begin && a < end); 
assert(setSymmetricDifference(filterRes, vT[begin..end]).empty); 

uint currentSeed = 1223409; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
// do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = new vebTree(M); 
uint[] arr; 
vT.fill(arr, 16); 
assert(vT.elementCount == vT.elementCount_ut); 

uint currentSeed = 1435856534; //unpredictableSeed(); 
rndGenInUse.seed(currentSeed); //initialize the random generator
// do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer. 
vebTree vT = new vebTree(M); 
uint[] arr; 
vT.fill(arr, 16); 

assert(!vT.member(0));
assert(!vT.member(1)); 
import std.algorithm; 
assert(startsWith(vT[1], 0)); 
assert(vT.successor(vT[1][$-1]) == vT.successor(1));
assert(startsWith(vT[vT.successor(1)],vT.min)); 
assert(!vT.member(65535)); 
assert(vT[65535] == [65534, 65535]); 
assert(vT.member(4)); 
assert(startsWith(vT[4],4)); 
assert(!vT.member(vT[4][$-1])); 
assert(!vT.member(5)); 
assert(startsWith(vT[5],4)); 
assert(vT[5][$-1] == vT[4][$-1]);