vebRoot

auto vr = vebRoot!size_t(100);   
assert(vr.empty); 

size_t input = 42; 

vr.insert(3, input); 
assert(vr.front == 3); 
assert(*vr[3] == 42);

size_t input2 = 73; 
vr.insert(3, input2); 
assert(*vr[3] == 42);
*vr[3] = 73; 
assert(*vr[3] == 73);

assert(vr[8] is null); 
vr[15] = input2;
assert(vr[15] !is null); 
vr.remove(15); 
assert(vr[15] is null); 

1 auto currentSeed = unpredictableSeed();
2 static if(vdebug){write("UT: 3. use case       "); writeln("seed: ", currentSeed);} 
3 rndGenInUse.seed(currentSeed); //initialize the random generator
4 
5 size_t M = uniform(2U, baseSize, rndGenInUse); //set universe size to some integer (small). 
6 size_t N = uniform(1U, M, rndGenInUse); //set universe size to some integer (small). 
7 
8 auto vT = vebRoot!size_t(M); 
9 assert(vT.empty); 
10 
11 size_t[] testArray = new size_t[N]; 
12 size_t[] testValArray = new size_t[N]; 
13 testValArray.each!((ref el) => el = uniform(0UL, size_t.max, rndGenInUse)); 
14 
15 M.iota.randomCover(rndGenInUse).take(N)
16         .enumerate
17         .tee!(el => testArray[el.index] = el.value)
18         .each!(el => vT.insert(el.value, testValArray[el.index]));
19 
20 assert(vT.front == testArray.dup.sort.front); 
21 
22 assert(vT.length == testValArray.length); 
23 vT.each!((key, value) => assert(testValArray.canFind(value)));
24 assert(*vT[vT.back] == testValArray[testArray.maxIndex]); 
25 assert(vT().front == testArray.sort.front);  
26 assert(vT().back == testArray.sort.back); 
27 assert(vT[].front == 0); 
28 assert(vT[].back == vT.universe);
29 assert(vT.length == testArray.length); 
30 assert(vT() == testArray); 
31 assert(vT.capacity == baseSize); 
32 assert(vT.universe == M); 
33 assert(!vT.empty); 
34 testArray.each!(el => assert(el in vT)); 
35 size_t counter; 
36 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get))
37 {
38     assert(el.get == testArray.sort[counter]); 
39     ++counter; 
40 }
41 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get))
42 {
43     assert(el.get == testArray.sort[counter]); 
44     --counter; 
45 }
46 auto secondElementQ = vT.successor(testArray.sort[0]); 
47 if(!secondElementQ.isNull)
48 {
49     assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 
50 }
51 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 
52 assert(!vT.insert(randomElement)); 
53 
54 auto vTdeepCopy = vT.dup; 
55 foreach(el; testArray)
56 {
57     vT.remove(el); 
58 }
59 assert(vT.empty); 
60 assert(!vT.length);
61 assert(vTdeepCopy.length == testArray.length); 
62 auto vTdeepCopy2 = vTdeepCopy.dup; 
63 
64 vTdeepCopy2.remove(testArray[0]); 
65 assert(vTdeepCopy2.length + 1== testArray.length); 
66 
67 auto inclusiveSlice = vTdeepCopy[]; 
68 if(0 in vTdeepCopy)
69 {
70     assert(inclusiveSlice.length == testArray.length + 1); 
71 }
72 else
73 {
74     assert(inclusiveSlice.length == testArray.length + 2); 
75 }
76 auto exclusiveSlice = vTdeepCopy(); 
77 assert(exclusiveSlice.length == vTdeepCopy.length); 
78 foreach(el; vTdeepCopy)
79 {
80     assert(el in exclusiveSlice);
81 }
82 foreach(el; exclusiveSlice)
83 {
84     assert(el in vTdeepCopy); 
85 }
86 auto shallowCopyFromRoot = vTdeepCopy; 
87 static assert(is(typeof(vTdeepCopy) : VEBroot!T, T...)); 
88 assert(!vTdeepCopy.empty); 
89 assert(vTdeepCopy.length == vTdeepCopy().length); 
90 assert(shallowCopyFromRoot == vTdeepCopy().save); 
91 
92 inclusiveSlice = vTdeepCopy[]; 
93 auto shallowCopyFromSlice = inclusiveSlice.save;
94 assert(inclusiveSlice.front == shallowCopyFromSlice.front);
95 inclusiveSlice.popFront; 
96 assert(inclusiveSlice.front != shallowCopyFromSlice.front);
97 
98 if(0 in vTdeepCopy)
99 {
100     assert(inclusiveSlice.front == vTdeepCopy.successor(0));
101 }
102 else
103 {
104     assert(inclusiveSlice.front == vTdeepCopy.front); 
105 }
106 
107 assert(vTdeepCopy() == testArray);
108 auto vTdeepCopy3 = vT.dup; 
109 auto vTshallowCopy = vT; 
110 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 
111 vTdeepCopy.remove(vTdeepCopy.front.get); 
112 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 
113 
114 assert(vTshallowCopy == vT);
115 assert(vTdeepCopy3 == vT); 
116 
117 assert(vT() == vT); 
118 assert(vT == vT());

1 auto currentSeed = unpredictableSeed();
2 static if(vdebug){write("UT: 4. use case       "); writeln("seed: ", currentSeed);} 
3 rndGenInUse.seed(currentSeed); //initialize the random generator
4 
5 size_t M = uniform(baseSize + 1, testedSize, rndGenInUse); //set universe size to some integer (small). 
6 size_t N = uniform(1U, min(M, allowedArraySize), rndGenInUse); //set universe size to some integer (small). 
7 
8 auto vT = vebRoot!size_t(M); 
9 assert(vT.empty); 
10 
11 size_t[] testArray = new size_t[N]; 
12 size_t[] testValArray = new size_t[N]; 
13 testValArray.each!((ref el) => el = uniform(0UL, size_t.max, rndGenInUse)); 
14 
15 M.iota.randomCover(rndGenInUse).take(N)
16         .enumerate
17         .tee!(el => testArray[el.index] = el.value)
18         .each!(el => vT.insert(el.value, testValArray[el.index])); 
19 
20 assert(vT.front == testArray.dup.sort.front); 
21 
22 assert(vT.length == testValArray.length); 
23 assert(!vT.front.isNull);
24 assert(vT[vT.front.get] !is null); 
25 vT.each!((key, ref value) => assert(testValArray.canFind(value)));
26 
27 assert(*vT[vT.back] == testValArray[testArray.maxIndex]); 
28 assert(vT().front == testArray.sort.front);  
29 assert(vT().back == testArray.sort.back); 
30 assert(vT[].front == 0); 
31 assert(vT[].back == vT.universe);
32 assert(vT.length == testArray.length); 
33 assert(vT() == testArray); 
34 assert(vT.capacity == M.nextPow2); 
35 assert(vT.universe == M); 
36 assert(!vT.empty); 
37 
38 testArray.each!(el => assert(el in vT)); 
39 size_t counter; 
40 for(auto el = vT.front; el != vT.back; el = vT.successor(el.get))
41 {
42     assert(el.get == testArray.sort[counter]); 
43     ++counter; 
44 }
45 for(auto el = vT.back; el != vT.front; el = vT.predecessor(el.get))
46 {
47     assert(el.get == testArray.sort[counter]); 
48     --counter; 
49 }
50 auto secondElementQ = vT.successor(testArray.sort[0]); 
51 if(!secondElementQ.isNull)
52 {
53     assert(testArray.sort.lowerBound(secondElementQ.get).length == 1); 
54 }
55 auto randomElement = testArray[uniform(0, testArray.length, rndGenInUse)]; 
56 assert(!vT.insert(randomElement)); 
57 
58 auto vTdeepCopy = vT.dup; 
59 foreach(el; testArray)
60 {
61     vT.remove(el); 
62 }
63 assert(vT.empty); 
64 assert(!vT.length);
65 assert(vTdeepCopy.length == testArray.length); 
66 auto vTdeepCopy2 = vTdeepCopy.dup; 
67 
68 vTdeepCopy2.remove(testArray[0]); 
69 assert(vTdeepCopy2.length + 1 == testArray.length); 
70 
71 auto inclusiveSlice = vTdeepCopy[]; 
72 if(0 in vTdeepCopy)
73 {
74     assert(inclusiveSlice.length == testArray.length + 1); 
75 }
76 else
77 {
78     assert(inclusiveSlice.length == testArray.length + 2); 
79 }
80 auto exclusiveSlice = vTdeepCopy(); 
81 assert(exclusiveSlice.length == vTdeepCopy.length); 
82 foreach(el; vTdeepCopy)
83 {
84     assert(el in exclusiveSlice);
85 }
86 foreach(el; exclusiveSlice)
87 {
88     assert(el in vTdeepCopy); 
89 }
90 auto shallowCopyFromRoot = vTdeepCopy; 
91 static assert(is(typeof(vTdeepCopy) : VEBroot!T, T...)); 
92 assert(!vTdeepCopy.empty); 
93 assert(vTdeepCopy.length == vTdeepCopy().length); 
94 assert(shallowCopyFromRoot == vTdeepCopy().save); 
95 
96 inclusiveSlice = vTdeepCopy[]; 
97 auto shallowCopyFromSlice = inclusiveSlice.save;
98 assert(inclusiveSlice.front == shallowCopyFromSlice.front);
99 inclusiveSlice.popFront; 
100 assert(inclusiveSlice.front != shallowCopyFromSlice.front);
101 
102 if(0 in vTdeepCopy)
103 {
104     assert(inclusiveSlice.front == vTdeepCopy.successor(0));
105 }
106 else
107 {
108     assert(inclusiveSlice.front == vTdeepCopy.front); 
109 }
110 
111 assert(vTdeepCopy() == testArray);
112 auto vTdeepCopy3 = vT.dup; 
113 auto vTshallowCopy = vT; 
114 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 
115 vTdeepCopy.remove(vTdeepCopy.front.get); 
116 assert(shallowCopyFromRoot.front == vTdeepCopy.front); 
117 
118 assert(vTshallowCopy == vT);
119 assert(vTdeepCopy3 == vT); 
120 
121 assert(vT() == vT); 
122 assert(vT == vT());