1 enum baseSize = 1 << _;
2 foreach (b; (CHAR_BIT * size_t.sizeof * testMultiplier).iota.parallel)
3 {
4 auto currentSeed = unpredictableSeed();
5 size_t M;
6
7 auto vT = generateVEBtree!(1 << _)(currentSeed, 2UL, baseSize, M);
8 assert(vT.universe == M);
9 const errorString = generateDebugString("UT: node test: ", b, baseSize, currentSeed, M);
10
11 assert(vT.value_ == 0, errorString);
12 assert(vT.ptr_ is null, errorString);
13 assert(vT.capacity == baseSize, errorString);
14 assert(vT.empty == true, errorString);
15 assert(vT.front == NIL, errorString);
16 assert(vT.back == NIL, errorString);
17 assert(vT[].front == 0, errorString);
18 assert(vT[].back == vT.universe, errorString);
19 assert(vT().front == NIL, errorString);
20 assert(vT().back == NIL, errorString);
21 assert(vT.length == 0, errorString);
22 assert(vT.universe == M, errorString);
23
24 size_t N = uniform(0UL, 2 * M); // independent parameter for testing
25 // make an array of length N
26 size_t[] testArray, cacheArray;
27 testArray = new size_t[N];
28 cacheArray.reserve(N);
29 // fill the array with all possible values
30 foreach (ref el; testArray)
31 {
32 el = (2 * M).iota.choice;
33 }
34
35 foreach (testNumber; testArray)
36 {
37 assert(vT.universe == M, errorString);
38 const insertResult = vT.insert(testNumber);
39
40 if (insertResult)
41 {
42 assert(!vT.empty, errorString);
43 cacheArray ~= testNumber;
44 }
45 }
46
47 import std.algorithm.sorting : sort;
48
49 cacheArray.sort;
50
51 if (cacheArray.empty)
52 {
53 assert(vT.empty, errorString);
54 }
55 else
56 {
57 assert(!vT.empty, errorString);
58 }
59
60 foreach (el; cacheArray)
61 {
62 assert(bt(&vT.value_, el), errorString);
63 }
64 import std.algorithm.iteration : uniq;
65 import std.algorithm.searching : count;
66
67 assert(vT.length == cacheArray.uniq.count, errorString);
68 assert(vT.universe == M, errorString);
69 if (cacheArray.length)
70 {
71 assert(vT.front == cacheArray.front, errorString);
72 assert(vT.back == cacheArray.back, errorString);
73 }
74 else
75 {
76 assert(vT.front == NIL, errorString);
77 assert(vT.back == NIL, errorString);
78 }
79
80 auto currElement = vT.front;
81 foreach (el; cacheArray.uniq)
82 {
83 assert(currElement == el, errorString);
84 currElement = vT.next(currElement);
85 }
86 currElement = vT.back;
87 foreach (el; cacheArray.uniq.array.retro)
88 {
89 assert(currElement == el, errorString);
90 currElement = vT.prev(currElement);
91 }
92
93 foreach (key; 0 .. vT.universe)
94 {
95 import std.algorithm.searching : canFind;
96
97 if (cacheArray.uniq.array.canFind(key))
98 {
99 assert(key in vT, errorString);
100 }
101 else
102 {
103 assert(!(key in vT), errorString);
104 }
105 }
106 auto deepCopy = vT.dup;
107
108 assert(deepCopy.value_ == vT.value_, errorString);
109 assert(vT == cacheArray.uniq, errorString);
110 assert(vT.prev(vT.front) == NIL, errorString);
111 assert(vT.next(vT.back) == NIL, errorString);
112 assert(vT == deepCopy, errorString);
113 assert(vT == deepCopy(), errorString);
114
115 if (cacheArray.length)
116 {
117 auto val = cacheArray.uniq.array.randomCover.front;
118 vT.remove(val);
119 assert((deepCopy.value_ ^ vT.value_) == (size_t(1) << val), errorString);
120 import std.algorithm.iteration : each;
121 import std.algorithm.searching : count, find;
122 import std.algorithm.mutation : remove;
123
124 cacheArray.count(val).iota.each!(i => cacheArray = cacheArray.remove(
125 cacheArray.length - cacheArray.find(val).length));
126 }
127 else
128 {
129 assert((deepCopy.value_ ^ vT.value_) == 0, errorString);
130 }
131
132 foreach (key; 0 .. vT.capacity)
133 {
134 import std.algorithm.searching : canFind;
135
136 if (cacheArray.uniq.array.canFind(key))
137 {
138 assert(vT.remove(key), errorString);
139 }
140 else
141 {
142 assert(!(vT.remove(key)), errorString);
143 }
144 }
145 assert(vT.value_ == 0, errorString);
146 assert(vT.empty, errorString);
147 }import std.range : iota;
foreach (b; (CHAR_BIT * size_t.sizeof * testMultiplier).iota.parallel)
{
auto currentSeed = unpredictableSeed();
size_t M;
auto vT = generateVEBtree!(1 << _)
(currentSeed, CHAR_BIT * size_t.sizeof, CHAR_BIT * size_t.sizeof * CHAR_BIT * size_t.sizeof, M);
const errorString =
generateDebugString("UT: tree test of capacity and universe: ", b, 1 << _, currentSeed, M);
assert(vT.universe == M, errorString);
assert(vT.capacity == (vT.universe - 1).nextPow2,
to!string("vT.capacity: " ~ to!string(
vT.capacity) ~ " vT.universe: " ~ to!string(vT.universe)));
assert(!(vT.ptr_ is null), errorString);
assert(vT.capacity == (vT.universe - 1).nextPow2, errorString);
}
1 import std.range : iota;
2 foreach (b; (CHAR_BIT * size_t.sizeof * testMultiplier).iota.parallel)
3 {
4 auto currentSeed = unpredictableSeed();
5 size_t M;
6 auto vT = generateVEBtree!(1 << _)
7 (currentSeed, CHAR_BIT * size_t.sizeof, CHAR_BIT * size_t.sizeof * CHAR_BIT * size_t.sizeof, M);
8 const errorString =
9 generateDebugString("UT: tree test, general case: ", b, 1 << _, currentSeed, M);
10 size_t N = uniform(0UL, 2 * M); // independent parameter for testing
11
12 // make an array of length N
13 size_t[] testArray, cacheArray;
14 testArray = new size_t[N];
15 cacheArray.reserve(N);
16 // fill the array with all possible values
17 foreach (ref el; testArray)
18 el = (2 * M).iota.choice;
19
20 auto rbt = redBlackTree!size_t();
21
22 foreach (val; testArray)
23 {
24 assert(vT.universe == M, errorString);
25 assert(vT.length == rbt.length, errorString);
26
27 bool insertExpectation;
28 if (val < vT.capacity && !(val in vT))
29 {
30 insertExpectation = true;
31 }
32 const insertResult = vT.insert(val);
33
34 assert(insertResult == insertExpectation, errorString);
35
36 if (insertResult)
37 {
38
39 assert(val in vT, errorString);
40 assert(!vT.empty, errorString);
41 rbt.insert(val);
42 assert(vT.front == rbt.front, errorString);
43 assert(vT.back == rbt.back,
44 "val:" ~ to!string(val) ~ " vT.back: " ~ to!string(
45 vT.back) ~ " rbt.back: " ~ to!string(rbt.back));
46
47 cacheArray ~= val;
48 }
49 else
50 {
51 if (!(val in rbt))
52 {
53 assert(!(val in vT), errorString);
54 }
55 else
56 {
57 assert(val in vT, errorString);
58 }
59 }
60 }
61
62 import std.algorithm.sorting : sort;
63 cacheArray.sort;
64
65 foreach (i, el; cacheArray)
66 {
67 assert(el in vT, errorString);
68 if (i + 1 != cacheArray.length)
69 {
70 assert(vT.next(el) == cacheArray[i + 1],errorString);
71 }
72 else
73 {
74 assert(vT.next(el) == NIL, errorString);
75 }
76 }
77
78 foreach (i, el; vT)
79 assert(el == cacheArray[i], errorString);
80
81 assert(vT == cacheArray, errorString);
82
83 auto vT2 = vT.dup;
84 assert(vT == vT2);
85
86 if(cacheArray.length)
87 {
88 auto rndNum = cacheArray.choice;
89 vT2.remove(rndNum);
90 assert(!(rndNum in vT2));
91 assert(rndNum in vT);
92 assert(vT != vT2);
93 rndNum = uniform(0UL, vT2.capacity);
94 if(!(rndNum in vT))
95 {
96 assert(!(rndNum in vT), errorString ~ format!"rndNum: %d"(rndNum));
97 assert(vT2.insert(rndNum), errorString);
98 }
99 assert(vT != vT2);
100 //auto vT3 = vT2;
101 //vT3.insert(rndNum);
102 //assert(rndNum in vT3);
103 //assert(rndNum in vT2);
104 //assert(vT2.length == vT3.length);
105 }
106
107 const rangeExclusive = vT();
108 assert(vT == rangeExclusive);
109
110 auto rangeInclusive = vT[];
111 import std.range : enumerate;
112 foreach(i, el; rangeInclusive.enumerate)
113 {
114 if(i == 0)
115 {
116 if(!(0 in vT))
117 {
118 continue;
119 }
120 }
121 else if(i + 1 != rangeInclusive.length)
122 {
123 assert(el in vT, errorString ~ format!" el: %d"(el));
124 }
125 else if(i + 1 == rangeInclusive.length)
126 {
127 assert(el == vT.universe || el == vT.capacity);
128 if(el == vT.universe)
129 {
130 assert(vT.back <= vT.universe || vT.back == NIL, errorString ~ format!" length: %d"(vT.length));
131 }
132 else
133 {
134 assert(vT.back > vT.universe, errorString);
135 assert(vT.back < vT.capacity, errorString);
136 }
137 }
138 else
139 {
140 assert(0);
141 }
142 }
143
144 import std.range : retro, enumerate;
145 foreach (i, el; cacheArray.retro.enumerate)
146 {
147 assert(el in vT, errorString);
148 if (i + 1 != cacheArray.length)
149 {
150 assert(vT.prev(el) == cacheArray[($ - 1) - (i + 1)], errorString);
151 }
152 else
153 {
154 assert(vT.prev(el) == NIL, errorString);
155 }
156 }
157
158 foreach (val; testArray)
159 {
160 assert(vT.length == rbt.length, errorString);
161 if (val in rbt)
162 {
163 assert(val in vT, errorString);
164 rbt.removeKey(val);
165 assert(vT.remove(val), errorString);
166 }
167 else
168 {
169 assert(!(val in vT), errorString);
170 assert(!vT.remove(val), errorString);
171 }
172 assert(!(val in rbt), errorString);
173 assert(!(val in vT), errorString);
174 }
175 assert(vT.length == 0, errorString);
176 assert(rbt.length == 0, errorString);
177 }