vebTree vT = new vebTree(100);
vT.insert(2);
assert(vT.member(2));
vebTree vT2 = vT.save();
assert(vT2.member(2));
vT2.insert(3);
assert(vT2.member(3));
assert(!vT.member(3));
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));
Random rndGenInUse;
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, rndGenInUse); //(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); Random rndGenInUse;
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, rndGenInUse); //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); Random rndGenInUse;
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, rndGenInUse); //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));
Random rndGenInUse;
//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.
// last test says: inserting and removing with veb of 8.126.464 elements lasts: 19secs,217ms
uint M = uniform(0U, 1 << 16, rndGenInUse); // set universe size to some integer.
vebTree vT = new vebTree(M);
uint[] arr;
auto howMuchFilled = vT.fill(arr, rndGenInUse);
assert(arr.length == howMuchFilled);
vebTree vT2 = new vebTree(M);
assert(vT2.capacity == vT.capacity);
auto rbt = redBlackTree!uint(0);
rbt.clear;
void fill1()
{
foreach(uint i; arr)
{
vT2.insert(i);
}
/*
foreach(uint i; arr)
{
vT2.remove(i);
}
assert(vT2.empty);
*/
}
void fill2()
{
foreach(uint i; arr)
{
rbt.insert(i);
}
}
/*
import std.stdio;
writeln("howMuchFilled: ", howMuchFilled);
auto r = benchmark!(fill1, fill2)(1);
//auto r = benchmark!(fill1)(1);
auto f0Result = to!Duration(r[0]);
auto f1Result = to!Duration(r[1]);
writeln("VEB: ", f0Result); //10ms
writeln("rbt: ", f1Result); //40sec
assert(f0Result < f1Result);
//*/Random rndGenInUse;
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); Random rndGenInUse;
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, rndGenInUse, 16);
assert(setSymmetricDifference(vT[], sort(arr)).empty);
Random rndGenInUse;
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, rndGenInUse, 16);
uint begin = 5;
uint end = 100;
auto filterRes = sort(arr).filter!(a => a >= begin && a < end);
assert(setSymmetricDifference(filterRes, vT[begin..end]).empty);
Random rndGenInUse;
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, rndGenInUse, 16);
assert(vT.length == vT.elementCount);
Random rndGenInUse;
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, rndGenInUse, 16);
assert(!vT.member(0));
assert(!vT.member(1));
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].array == [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]);
assert(isBidirectionalRange!vebTree);
vebTree vT = new vebTree(14);
vT.insert(2);
vT.insert(5);
vT.insert(10);
assert(vT[] == [2, 5, 10]);
assert(vT[6].array == [5, 6, 7, 8, 9]);
assert(vT[11].array == [10, 11, 12, 13]);
assert(vT[-1].array == []);
assert(vT[18].array == []);
assert(vT[1].array == [0, 1]);
assert(vT[15].array == [10, 11, 12, 13, 14, 15]);
assert(vT[16].array == []);
vebTree vT = new vebTree(15);
vT.insert(2);
auto testrange = vT[3];
assert(testrange.array == [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]);
vT.insert(6);
testrange = vT[3];
assert(testrange.array == [2, 3, 4, 5]);
//another stress test
Random rndGenInUse;
auto currentSeed = 11351568; //unpredictableSeed();
rndGenInUse.seed(currentSeed); //initialize the random generator
void fill16(){ vebTree vT = new vebTree(1 << 16); }
void fill17(){ vebTree vT = new vebTree(1 << 17); }
void fill18(){ vebTree vT = new vebTree(1 << 18); }
void fill19(){ vebTree vT = new vebTree(1 << 19); }
void fill20(){ vebTree vT = new vebTree(1 << 20); }
void fill21(){ vebTree vT = new vebTree(1 << 21); }
void fill22(){ vebTree vT = new vebTree(1 << 22); }
void fill23(){ vebTree vT = new vebTree(1 << 23); }
void fill24(){ vebTree vT = new vebTree(1 << 24); }
void fill25(){ vebTree vT = new vebTree(1 << 25); }
/*
import std.stdio;
auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25)(1);
//auto r = benchmark!(fill1)(1);
auto f16Result = to!Duration(r[0]);
auto f17Result = to!Duration(r[1]);
auto f18Result = to!Duration(r[2]);
auto f19Result = to!Duration(r[3]);
auto f20Result = to!Duration(r[4]);
auto f21Result = to!Duration(r[5]);
auto f22Result = to!Duration(r[6]);
auto f23Result = to!Duration(r[7]);
auto f24Result = to!Duration(r[8]);
auto f25Result = to!Duration(r[9]);
writeln("VEB with M of ", 1 << 16, ": ", f16Result);
writeln("VEB with M of ", 1 << 17, ": ", f17Result);
writeln("VEB with M of ", 1 << 18, ": ", f18Result);
writeln("VEB with M of ", 1 << 19, ": ", f19Result);
writeln("VEB with M of ", 1 << 20, ": ", f20Result);
writeln("VEB with M of ", 1 << 21, ": ", f21Result);
writeln("VEB with M of ", 1 << 22, ": ", f22Result);
writeln("VEB with M of ", 1 << 23, ": ", f23Result);
writeln("VEB with M of ", 1 << 24, ": ", f24Result);
writeln("VEB with M of ", 1 << 25, ": ", f25Result);
//*//*
uint[] arr = [1, 2, 8, 2147483647];
auto vT = new vebTree(arr));
*/