yields a deep copy of the node. I. e. copies all data in children and allocates another tree
insert method. this method is called from class with a universe size given. It performs recursion calls untill the universe size is reduced to the base size. Then the overloaded insert method is called.
the opApply method grants the correct foreach behavior
opApply method in case of present source for iterating over key value pairs
member method for the case universe size < base size. Overloads by passing only one parameter, which is the bit number of interest. Returns whether the appropriate bit inside the bitvector is set.
()-slicing. Yields a "random access range" with the content of the tree. Keys can be isNull.
comparison operator for the recursive node of the same kind.
method exists only, when in data mode. Then, yields a pointer to the data, associated with the key. If no data is associated or the key is not in the tree, yields null.
[]-slicing. Yields a "random access range" with the content of the tree, always containing zero and universe as keys
operator is used for re assigning data, if the key already exists.
predecessor method. this method is called from class with a universe size given. It performs recursion calls until the universe size is reduced to the base size. Then the overloaded predecessor method is called.
remove method. this method is called from class with a universe size given. It performs recursion calls untill the universe size is reduced to the base size. Then the overloaded remove method is called.
successor method. this method is called from class with a universe size given. It performs recursion calls until the universe size is reduced to the base size. Then the overloaded successor method is called.
dummy toHash method.
method returning either the higher part of the stored value (intermediate node) or the highest bit set (bit vector mode). If the node does not contain any value (min > max or value == 0) Nullable.null is returned.
yields the next power of two, based un universe size
method to check whether the current node holds a value
method returning either the lower part of the stored value (intermediate node) or the lowest bit set (bit vector mode). If the node does not contain any value (min > max or value == 0) Nullable.null is returned.
yields the current inserted elements under the node, including the two elements of the node itself.
yields the universe size of a node. The root has the unvierse size, defined on tree creation
auto vN = vebRoot(baseSize); assert(vN.empty); static assert(vN.sizeof == 4 * size_t.sizeof); assert(vN.isLeaf); assert(vN.empty); *vN.val = 3; assert(vN.front == 0); assert(1 in vN); assert(!(2 in vN)); assert(vN.isLeaf); assert(vN.ptrArr == null); vN.nullify; assert(vN.empty); assert(*vN.val == 0);
auto vT = vebRoot(100); assert(vT.empty); auto result = vT.insert(2); assert(result); assert(!vT.empty); assert(2 in vT); assert(vT.length == 1); auto vT2 = vT; auto vT3 = vT.dup(); assert(2 in vT2); assert(vT2.length == 1); auto result2 = vT2.insert(3); assert(vT2.length == 2); assert(result2); assert(3 in vT2); assert(3 in vT); assert(!(3 in vT3)); assert(vT2.length == 2);
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: vT, [], () "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. auto vT = vebRoot(M); //create the tree assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); assert(vT[].front == 0); assert(vT[].back == vT.universe);
auto p = vebRoot(100); assert(p.empty); p.insert(5); p.insert(100); assert(!p.empty); assert(p.successor(0) == 5); assert(p.successor(4) == 5); assert(p.successor(5) == 100); auto s = p[]; static assert(isBidirectionalRange!(typeof(s))); assert(s.front == 0); assert(p.front == 5); s.popFront; assert(!s.empty); assert(s.front == 5); s.popFront; assert(s.front == 100); s.popFront; assert(s.empty); auto pp = vebRoot(100); assert(pp.empty); pp.insert(5); assert(!pp.empty); assert(pp.successor(0) == 5); assert(pp.successor(4) == 5); assert(pp.successor(5).isNull); assert(pp[].successor(5) == 100); auto ss = pp(); static assert(isBidirectionalRange!(typeof(ss))); assert(ss.front == 5); ss.popFront; assert(ss.empty); assert(ss.front.isNull);
1 2 auto vT = vebRoot(1000); 3 assert(vT.capacity == 1024); 4 assert(vT.front.isNull); 5 assert(vT.insert(2)); 6 assert(vT.insert(5)); 7 assert(!(8 in vT)); 8 assert(vT.insert(88)); 9 assert(88 in vT); 10 assert(vT.predecessor(4) == 2); 11 assert(!(8 in vT)); 12 assert(vT.insert(8)); 13 assert(8 in vT); 14 assert(vT.predecessor(75) == 8); 15 16 assert(vT.predecessor(90) == 88); 17 18 assert(vT.predecessor(7) == 5); 19 assert(vT.predecessor(4) == 2); 20 assert(vT.predecessor(2).isNull); 21 22 //TODO: reactivate this by slicing assert(vT[].predecessor(2) == 0); 23 24 assert(vT.predecessor(2).isNull); 25 26 assert(vT.successor(6) == 8); 27 assert(vT.successor(5) == 8); 28 29 assert(vT.successor(4) == 5); 30 assert(vT.successor(1) == 2); 31 assert(vT.successor(75) == 88); 32 assert(vT.successor(90).isNull); 33 //TODO: reactivate this by slicing assert(vT[].successor(90) == vT.universe); 34 35 assert(!(1029 in vT)); 36 37 assert(vT.successor(1025).isNull); 38 assert(vT.successor(1025).isNull); 39 40 auto vT2 = vebRoot(500); 41 assert(vT2.empty); 42 vT2.insert(50); 43 vT2.insert(500); 44 assert(vT2.back == 500); 45 assert(vT2.front == 50); 46 assert(vT2.successor(40) == 50); 47 assert(vT2.successor(50) == 500); 48 49 vT2 = vebRoot(500); 50 assert(vT2.empty); 51 vT2.insert(50); 52 vT2.insert(500); 53 assert(vT2.back == 500); 54 assert(vT2.front == 50); 55 assert(vT2.successor(40) == 50); 56 assert(vT2.successor(50) == 500); 57 58 /* about 20 seconds in debug mode. 59 auto vT3 = vebRoot(halfSizeT.max); 60 assert(vT3.insert(5)); 61 assert(vT3.member(5)); 62 assert(vT3.capacity == cast(ulong)halfSizeT.max + 1UL); 63 //*/ 64 65 assert(!(1029 in vT)); 66 assert(!(865 in vT)); 67 assert(vT.insert(865)); 68 assert(865 in vT); 69 assert(!vT.insert(865)); 70 assert(865 in vT); 71 assert(!(866 in vT)); 72 assert(!vT.remove(866)); 73 assert(865 in vT); 74 assert(vT.remove(865)); 75 assert(!(865 in vT));
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, succ "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator size_t M = uniform(2U,testedSize, rndGenInUse); //set universe size to some integer. auto vT = vebRoot(M); //create the tree assert(vT.capacity == nextPow2(M-1)); auto filled = M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum; assert(filled == vT.length); size_t n; auto i = vT.back; // discover the thousend (or little less) values with the predecessor method while(!i.isNull) { ++n; i = vT.predecessor(i); if(n > filled) break; } size_t o; i = vT.front; while(!i.isNull) { ++o; i = vT.successor(i.get); if(o - 1 > filled) break; } // assert, that all members are discovered, iff when no predecessors are left assert(n == filled); assert(o == filled);
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, pred "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. auto vT = vebRoot(M); assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); auto i = vT.back; // remove all members beginning from the maximum bool result; while(!i.isNull) { result = vT.remove(i); assert(result); 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 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. auto vT = vebRoot(M); assert(M.iota.map!(i => vT.insert(uniform(0, vT.universe, rndGenInUse))).sum == vT.length); auto i = vT.front; // remove all members beginning from the minimum bool result; while(!i.isNull) { result = vT.remove(i); assert(result); 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);
size_t M = testedSize; auto vT = vebRoot(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);
size_t M = testedSize; auto vT = vebRoot(M); vT.insert(0xf000); assert(0xf000 in vT); vT.insert(0x0f00); assert(0x0f00 in vT); vT.insert(0x00f0); assert(0x00f0 in vT); vT.insert(0x000f); assert(0x000f in vT); auto result = vT.remove(0xf000); assert(result); assert(!(0xf000 in vT)); result = vT.remove(0x0f00); assert(result); assert(!(0x0f00 in vT)); result = vT.remove(0x00f0); assert(result); assert(!(0x00f0 in vT)); result = vT.remove(0x000f); assert(result); assert(!(0x000f in vT));
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 size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. 8 auto vT = vebRoot(M); 9 10 size_t[] arr; 11 arr.length = 31 * vT.capacity/typeof(vT).sizeof; 12 (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) 13 .enumerate 14 .tee!(el => arr[el.index] = el.value) 15 .each!(el => vT.insert(el.value)); 16 17 auto vT2 = vebRoot(M); 18 19 assert(vT2.capacity == vT.capacity); 20 21 auto rbt = redBlackTree!size_t(0); 22 rbt.clear; 23 24 void fill1() 25 { 26 foreach(size_t i; arr) 27 { 28 vT2.insert(i); 29 } 30 31 foreach(size_t i; arr) 32 { 33 vT2.remove(i); 34 } 35 assert(vT2.empty); 36 37 } 38 39 void fill2() 40 { 41 foreach(size_t i; arr) 42 { 43 rbt.insert(i); 44 } 45 } 46 47 /* 48 this part is for speed test 49 */ 50 /* 51 compiled with ldc2 vebtree.d -O -main -unittest 52 results of stress tests: 53 size of tree: 16777216 54 howMuchFilled: 16252928 55 VEB: 2 secs, 382 ms, 588 μs, and 8 hnsecs 56 */ 57 /* 58 59 writeln("size of tree: ", vT2.capacity); 60 writeln("howMuchFilled: ", howMuchFilled); 61 //auto r = benchmark!(fill1, fill2)(1); 62 auto r = benchmark!(fill1)(1); 63 64 auto f0Result = to!Duration(r[0]); 65 //auto f1Result = to!Duration(r[1]); 66 writeln("VEB: ", f0Result); //10ms 67 //writeln("rbt: ", f1Result); //40sec 68 //assert(f0Result < f1Result); 69 //*/
auto currentSeed = unpredictableSeed(); static if(vdebug){write("UT: rand, member "); writeln("seed: ", currentSeed);} rndGenInUse.seed(currentSeed); //initialize the random generator size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. size_t[] sourceArr; sourceArr.length = M; // generate a random array as the source for the tree iota(M).each!(i => sourceArr[i] = uniform(0U, M, rndGenInUse)); // make the array values unique. auto uniqueArr = sourceArr.sort.uniq; // constructor to test auto vT = vebRoot(sourceArr.length); uniqueArr.each!(el => vT.insert(el)); // check, that all values are filled bool result; foreach(i; uniqueArr) { assert(i in vT); 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 << 16", as for the red-black tree the insertion duration is almost 4 (!) minutes. size_t M = uniform(2U, allowedArraySize, rndGenInUse); // set universe size to some integer. auto vT = vebRoot(M); size_t[] arr; arr.length = 16 * vT.capacity/typeof(vT).sizeof; (vT.capacity - 1).iota.randomCover(rndGenInUse).take(arr.length) .enumerate .tee!(el => arr[el.index] = el.value) .each!(el => vT.insert(el.value)); assert(setSymmetricDifference(vT(), arr.sort).empty);
static assert(!isInputRange!(VEBroot!())); static assert(isIterable!(VEBroot!())); static assert(isBidirectionalRange!(typeof(VEBroot!()[]))); static assert(is(typeof(vebRoot!(size_t)(4)[2]))); static assert(!is(typeof(vebRoot(4)[2])));
auto vT = vebRoot(14); auto result = vT.insert(2); assert(result); result = vT.insert(5); assert(result); result = vT.insert(10); assert(result); assert(vT[] == [0, 2, 5, 10, 14]); assert(vT() == [2, 5, 10]);
1 /* 2 //another stress test 3 auto currentSeed = unpredictableSeed(); 4 static if(vdebug){write("UT: stress test 2 "); writeln("seed: ", currentSeed);} 5 rndGenInUse.seed(currentSeed); //initialize the random generator 6 7 void fill16(){ auto vT = vebRoot(1 << 16); } 8 void fill17(){ auto vT = vebRoot(1 << 17); } 9 void fill18(){ auto vT = vebRoot(1 << 18); } 10 void fill19(){ auto vT = vebRoot(1 << 19); } 11 void fill20(){ auto vT = vebRoot(1 << 20); } 12 void fill21(){ auto vT = vebRoot(1 << 21); } 13 void fill22(){ auto vT = vebRoot(1 << 22); } 14 void fill23(){ auto vT = vebRoot(1 << 23); } 15 void fill24(){ auto vT = vebRoot(1 << 24); } 16 void fill25(){ auto vT = vebRoot(1 << 25); } 17 void fill26(){ auto vT = vebRoot(1 << 26); } 18 void fill27(){ auto vT = vebRoot(1 << 27); } 19 void fill28(){ auto vT = vebRoot(1 << 28); } 20 void fill29(){ auto vT = vebRoot(1 << 29); } 21 void fill30(){ auto vT = vebRoot(1 << 30); } 22 23 auto r = benchmark!(fill16, fill17, fill18, fill19, fill20, fill21, fill22, fill23, fill24, fill25, fill26, fill27, 24 fill28, fill29, fill30)(1); 25 //auto r = benchmark!(fill1)(1); 26 auto f16Result = to!Duration(r[0]); 27 auto f17Result = to!Duration(r[1]); 28 auto f18Result = to!Duration(r[2]); 29 auto f19Result = to!Duration(r[3]); 30 auto f20Result = to!Duration(r[4]); 31 auto f21Result = to!Duration(r[5]); 32 auto f22Result = to!Duration(r[6]); 33 auto f23Result = to!Duration(r[7]); 34 auto f24Result = to!Duration(r[8]); 35 auto f25Result = to!Duration(r[9]); 36 auto f26Result = to!Duration(r[10]); 37 auto f27Result = to!Duration(r[11]); 38 auto f28Result = to!Duration(r[12]); 39 auto f29Result = to!Duration(r[13]); 40 auto f30Result = to!Duration(r[14]); 41 42 writeln("VEB with M of ", 1 << 16, ": ", f16Result); 43 writeln("VEB with M of ", 1 << 17, ": ", f17Result); 44 writeln("VEB with M of ", 1 << 18, ": ", f18Result); 45 writeln("VEB with M of ", 1 << 19, ": ", f19Result); 46 writeln("VEB with M of ", 1 << 20, ": ", f20Result); 47 writeln("VEB with M of ", 1 << 21, ": ", f21Result); 48 writeln("VEB with M of ", 1 << 22, ": ", f22Result); 49 writeln("VEB with M of ", 1 << 23, ": ", f23Result); 50 writeln("VEB with M of ", 1 << 24, ": ", f24Result); 51 writeln("VEB with M of ", 1 << 25, ": ", f25Result); 52 writeln("VEB with M of ", 1 << 26, ": ", f26Result); 53 writeln("VEB with M of ", 1 << 27, ": ", f27Result); 54 writeln("VEB with M of ", 1 << 28, ": ", f28Result); 55 writeln("VEB with M of ", 1 << 29, ": ", f29Result); 56 writeln("VEB with M of ", 1 << 30, ": ", f30Result); 57 //*/
1 //stress test 2 auto currentSeed = unpredictableSeed(); 3 static if(vdebug){write("UT: rand, ranges "); 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 size_t M = uniform(2U, testedSize, rndGenInUse); // set universe size to some integer. 8 auto vT = vebRoot(M); 9 /*testing the range methods*/ 10 assert(vT.empty); 11 12 size_t[] sourceArr; 13 sourceArr.length = uniform(2U, M, rndGenInUse); 14 iota(sourceArr.length).each!(i => sourceArr[i] = uniform(0U, sourceArr.length, rndGenInUse)); 15 16 auto uniqueArr = sourceArr.sort.uniq; 17 18 // constructor to test 19 20 auto vTnew = vebRoot(sourceArr.length); 21 uniqueArr.each!(el => vTnew.insert(el)); 22 23 assert(!vTnew.empty); 24 assert(vTnew.length == uniqueArr.walkLength); 25 auto vT2 = vTnew; 26 static assert(isIterable!(typeof(vTnew))); 27 auto slice = vTnew(); 28 assert(slice.front == uniqueArr.front); 29 assert(vTnew() == uniqueArr); 30 assert(!vTnew.empty); 31 assert(!vT2.empty); 32 33 size_t N = 100; 34 auto vT3 = vebRoot(N); 35 assert(vT3.empty); 36 auto unique3 = N.iota.map!(i => uniform(0U, N, rndGenInUse)).array.sort.uniq.array; 37 unique3.each!(u => vT3.insert(u)); 38 unique3.each!(u => assert(u in vT3)); 39 assert(vT3.length == unique3.length); 40 auto sl3 = vT3[]; 41 42 if(unique3.front == 0 && unique3.back == vT3.universe) 43 { 44 assert(sl3.length == unique3.length); 45 } 46 else if(unique3.front == 0 || unique3.back == vT3.universe) 47 { 48 assert(sl3.length == unique3.length + 1); 49 } 50 else 51 { 52 assert(sl3.length == unique3.length + 2); 53 } 54 assert(sl3.length); 55 assert(!sl3.empty); 56 57 unique3.each!(u => vT3.remove(u)); 58 assert(vT3.empty); 59 60 //* Works. Duration in debug mode: about 35 seconds. 61 //auto vTT = vebRoot((size_t(1) << 27) - 1); 62 //assert(vTT.insert(42)); 63 //assert(42 in vTT); 64 //*/
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.