default constructor of a VEB tree is disabled.
to construct a VEB tree the wished size has to be provided. However, the size should be greater then one and should not excess the maximum allowed size for the current architecture.
another possibility is to construct a VEB tree is by providing an array.
this method returns the capacity of the tree. It is equal to the next power of 2 regarding the size used at initialization.
this method is used to add an element to the tree. duplicate values will be ignored. the class provides an intermediate layer between the caller and the contained root and enrichs the input by the stored size.
this method overrides the insert method to directly use arrays
this method is used to determine, whether an element is currently present in the tree
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 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.
this method removes the maximum element
this method removes the minimum element
this method retrieves the predecessor of the given input.
this method is used to remove elements from the tree. not existing values will be ignored.
this method retrieves the successor of the given input.
bidirectional range also needs
this method is used to determine, whether the tree is currently containing an element.
this method returns the minimium.
This method returns the amount of elements currently present in the tree.
this method is used to determine the maximum of the tree
this method is used to determine the minimum of the tree
forward range also needs save. This is a draft version of the save function, it uses the opslice of the struct to construct a new one via an array
this member stores the initialization size, as it would be lost forever after initialization, otherwise
VEBtree vT = new VEBtree(100); assert(vT.root.isNull); auto result = vT.insert(2); assert(result); assert(!vT.root.isNull); assert(vT.member(2)); VEBtree vT2 = vT.save(); assert(vT2.member(2)); result = vT2.insert(3); assert(result); assert(vT2.member(3)); assert(!vT.member(3));
1 assert(!__traits(compiles, new VEBtree())); 2 VEBtree vT = new VEBtree(1000); 3 assert(vT.capacity == 1024); 4 assert(vT.min.isNull); 5 assert(vT.insert(2)); 6 vT.insert(5); 7 assert(!vT.member(8)); 8 assert(vT.insert(88)); 9 assert(vT.member(88)); 10 assert(vT.predecessor(4) == 2); 11 assert(!vT.member(8)); 12 assert(vT.insert(8)); 13 assert(vT.member(8)); 14 assert(vT.predecessor(75) == 8); 15 assert(vT.predecessor(90) == 88); 16 assert(vT.predecessor(7) == 5); 17 assert(vT.predecessor(4) == 2); 18 assert(vT.predecessor(2).isNull); 19 assert(vT.successor(6) == 8); 20 assert(vT.successor(5) == 8); 21 assert(vT.successor(4) == 5); 22 assert(vT.successor(1) == 2); 23 assert(vT.successor(75) == 88); 24 assert(vT.successor(90).isNull); 25 assert(!vT.member(1029)); 26 assert(!vT.member(1029)); 27 assert(vT.successor(1025).isNull); 28 29 auto vT2 = new VEBtree(500); 30 assert(vT2.empty); 31 vT2.insert(50); 32 vT2.insert(500); 33 assert(vT2.max == 500); 34 assert(vT2.min == 50); 35 assert(vT2.successor(40) == 50); 36 assert(vT2.successor(50) == 500); 37 38 /* about 20 seconds in debug mode. 39 auto vT3 = new VEBtree(uint.max); 40 assert(vT3.insert(5)); 41 assert(vT3.member(5)); 42 assert(vT3.capacity == cast(ulong)uint.max + 1); 43 //*/ 44 45 assert(!vT.member(1029)); 46 assert(!vT.member(865)); 47 assert(vT.insert(865)); 48 assert(vT.member(865)); 49 assert(!vT.insert(865)); 50 assert(vT.member(865)); 51 assert(!vT.member(866)); 52 assert(!vT.remove(866)); 53 assert(vT.member(865)); 54 assert(vT.remove(865)); 55 assert(!vT.member(865));
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, succ. "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator auto M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. VEBtree vT = new VEBtree(M); //create the tree assert(vT.capacity == nPof2(M-1)); const auto m = vT.fill(40, rndGenInUse); //(try to) fill the tree with thousend values size_t n; Nullable!(size_t, maxSize) i = vT.max; // discover the thousend (or little less) values with the predecessor method while(!i.isNull) { ++n; i = vT.predecessor(i); if(n > m) break; } size_t o; i = vT.min; while(!i.isNull) { ++o; i = vT.successor(i.get); if(o - 1 > m) break; } // assert, that all members are discovered, iff when no predecessors are left assert(n == m); assert(o == m);
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. VEBtree vT = new VEBtree(M); vT.fill(1000, rndGenInUse); //fill the tree with some values Nullable!(size_t, maxSize) i = vT.max; // remove all members beginning from the maximum bool result; while(!i.isNull) { result = vT.remove(i); assert(result); const 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);
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, remove "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. VEBtree vT = new VEBtree(M); vT.fill(1000, rndGenInUse); //fill the tree with some values Nullable!(size_t, maxSize) i = vT.min; // remove all members beginning from the minimum bool result; while(!i.isNull) { result = vT.remove(i); assert(result); const 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);
const uint M = testedSize; 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); auto result = vT.remove(0xf000); assert(result); assert(vT.predecessor(0xf000) == 0x0f00); result = vT.remove(0x0f00); assert(result); assert(vT.predecessor(0x0f00) == 0x00f0); result = vT.remove(0x00f0); assert(result); assert(vT.predecessor(0x00f0) == 0x000f); result = vT.remove(0x000f); assert(result); assert(vT.predecessor(0x000f).isNull);
const uint M = testedSize; 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)); auto result = vT.remove(0xf000); assert(result); assert(!vT.member(0xf000)); result = vT.remove(0x0f00); assert(result); assert(!vT.member(0x0f00)); result = vT.remove(0x00f0); assert(result); assert(!vT.member(0x00f0)); result = vT.remove(0x000f); assert(result); assert(!vT.member(0x000f));
1 //stress test 2 auto currentSeed = unpredictableSeed(); 3 static if(vdebug){write("UT: rand, stress "); writeln("seed: ", currentSeed);} 4 rndGenInUse.seed(currentSeed); //initialize the random generator 5 // do not use more then "1 << 15", as for the red-black tree the insertion duration is almost 4 (!) minutes. 6 // last test says: see below. 7 const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 8 VEBtree vT = new VEBtree(M); 9 size_t[] arr; 10 const auto howMuchFilled = vT.fill(arr, rndGenInUse); 11 12 assert(arr.length == howMuchFilled); 13 14 VEBtree vT2 = new VEBtree(M); 15 16 assert(vT2.capacity == vT.capacity); 17 18 auto rbt = redBlackTree!size_t(0); 19 rbt.clear; 20 21 void fill1() 22 { 23 foreach(size_t i; arr) 24 { 25 vT2.insert(i); 26 } 27 28 foreach(size_t i; arr) 29 { 30 vT2.remove(i); 31 } 32 assert(vT2.empty); 33 34 } 35 36 void fill2() 37 { 38 foreach(size_t i; arr) 39 { 40 rbt.insert(i); 41 } 42 } 43 44 /* 45 this part is for speed test 46 */ 47 /* 48 compiled with ldc2 vebtree.d -O -main -unittest 49 results of stress tests: 50 size of tree: 16777216 51 howMuchFilled: 16252928 52 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 53 */ 54 /* 55 import std.stdio; 56 writeln("size of tree: ", vT2.capacity); 57 writeln("howMuchFilled: ", howMuchFilled); 58 //auto r = benchmark!(fill1, fill2)(1); 59 auto r = benchmark!(fill1)(1); 60 //auto r = benchmark!(fill1)(1); 61 auto f0Result = to!Duration(r[0]); 62 //auto f1Result = to!Duration(r[1]); 63 writeln("VEB: ", f0Result); //10ms 64 //writeln("rbt: ", f1Result); //40sec 65 //assert(f0Result < f1Result); 66 //*/
const uint currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator const uint M = uniform(2U, testedSize, 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 bool result; foreach(uint i; uniqueArr) { assert(vT.member(i)); result = vT.remove(i); assert(result); } // check, that no other elements are present. assert(vT.empty);
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, opslice "); writeln("seed: ", currentSeed);} 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. const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. VEBtree vT = new VEBtree(M); size_t[] arr; vT.fill(arr, rndGenInUse, 16); assert(setSymmetricDifference(vT[], sort(arr)).empty);
const uint currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, opslice[]. "); writeln("seed: ", currentSeed);} 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. const auto M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. VEBtree vT = new VEBtree(M); size_t[] arr; vT.fill(arr, rndGenInUse, 16); const auto begin = 5; const auto end = 100; const auto filterRes = sort(arr).filter!(a => a >= begin && a < end).array; assert(setSymmetricDifference(filterRes, vT[begin..end]).empty);
assert(isBidirectionalRange!VEBtree);
VEBtree vT = new VEBtree(14); auto result = vT.insert(2); assert(result); result = vT.insert(5); assert(result); result = vT.insert(10); assert(result); assert(vT[] == [2, 5, 10]);
/+
//another stress test
auto currentSeed = unpredictableSeed();
static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);}
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); }
/*
This part is for speed test.
*/
/*
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);
//*/
+/// This unittest is for check of adding of big numbers /* in debug mode about 1 min. const uint[] arr = [1, 2, 8, 2_147_483_647]; new VEBtree(arr); //*/
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.