1 |
/* |
2 |
* Copyright (c) 2015 Christian Schoenebeck |
3 |
* |
4 |
* http://www.linuxsampler.org |
5 |
* |
6 |
* This file is part of LinuxSampler and released under the same terms. |
7 |
* See README file for details. |
8 |
*/ |
9 |
|
10 |
// This file contains automated test cases against the RTAVLTree template class. |
11 |
|
12 |
#include "RTAVLTree.h" |
13 |
#include <sstream> |
14 |
#include <stdlib.h> |
15 |
#include <time.h> |
16 |
#include <assert.h> |
17 |
|
18 |
class IntNode : public RTAVLNode { |
19 |
public: |
20 |
enum Dir_t { |
21 |
LEFT, |
22 |
RIGHT |
23 |
}; |
24 |
|
25 |
int value; |
26 |
RTAVLNode::parent; |
27 |
RTAVLNode::children; |
28 |
RTAVLNode::reset; |
29 |
|
30 |
inline bool operator==(const IntNode& other) const { |
31 |
return this->value == other.value; |
32 |
} |
33 |
|
34 |
inline bool operator<(const IntNode& other) const { |
35 |
return this->value < other.value; |
36 |
} |
37 |
|
38 |
inline operator std::string() const { |
39 |
const int n = countTwins(); |
40 |
std::stringstream ss; |
41 |
if (n > 1) ss << n << "x"; |
42 |
ss << "[" << value << "(" << balance << ")]"; |
43 |
return ss.str(); |
44 |
} |
45 |
|
46 |
void appendLeft(IntNode& child) { |
47 |
std::cout << "*** Insert " << child.value << " as left child of " << this->value << " ***\n"; |
48 |
IntNode& root = *this; |
49 |
IntNode& l = child; |
50 |
root.children[LEFT] = &l; |
51 |
l.parent = &root; |
52 |
l.children[LEFT] = NULL; |
53 |
l.children[RIGHT] = NULL; |
54 |
} |
55 |
|
56 |
void appendRight(IntNode& child) { |
57 |
std::cout << "*** Insert " << child.value << " as right child of " << this->value << " ***\n"; |
58 |
IntNode& root = *this; |
59 |
IntNode& r = child; |
60 |
root.children[RIGHT] = &r; |
61 |
r.parent = &root; |
62 |
r.children[LEFT] = NULL; |
63 |
r.children[RIGHT] = NULL; |
64 |
} |
65 |
}; |
66 |
|
67 |
typedef RTAVLTree<IntNode> MyTree; |
68 |
|
69 |
/// This test case requires a visual check by humans, that means it will never detect errors on its own! |
70 |
static void testTreeDumpWithManualTreeBuilt() { |
71 |
std::cout << "UNIT TEST: ManualTreeBuilt\n"; |
72 |
std::cout << "*** Create empty tree ***\n"; |
73 |
MyTree tree; |
74 |
tree.dumpTree(); |
75 |
|
76 |
const int MAX_NODES = 10; |
77 |
IntNode nodes[MAX_NODES]; |
78 |
for (int i = 0; i < MAX_NODES; ++i) { |
79 |
nodes[i].value = i; |
80 |
nodes[i].reset(); |
81 |
} |
82 |
|
83 |
std::cout << "*** Insert " << nodes[0].value << " into tree ***\n"; |
84 |
tree.insert(nodes[0]); |
85 |
tree.dumpTree(); |
86 |
|
87 |
nodes[0].appendLeft(nodes[1]); |
88 |
tree.dumpTree(); |
89 |
|
90 |
nodes[1].appendLeft(nodes[2]); |
91 |
tree.dumpTree(); |
92 |
|
93 |
nodes[1].appendRight(nodes[3]); |
94 |
tree.dumpTree(); |
95 |
|
96 |
nodes[3].appendRight(nodes[4]); |
97 |
tree.dumpTree(); |
98 |
|
99 |
nodes[0].appendRight(nodes[5]); |
100 |
tree.dumpTree(); |
101 |
|
102 |
nodes[5].appendLeft(nodes[6]); |
103 |
tree.dumpTree(); |
104 |
|
105 |
nodes[6].appendLeft(nodes[7]); |
106 |
tree.dumpTree(); |
107 |
|
108 |
nodes[5].appendRight(nodes[8]); |
109 |
tree.dumpTree(); |
110 |
|
111 |
nodes[6].appendRight(nodes[9]); |
112 |
tree.dumpTree(); |
113 |
|
114 |
std::cout << std::endl; |
115 |
} |
116 |
|
117 |
static void assertTreeLinks(MyTree& tree) { |
118 |
IntNode* from; |
119 |
IntNode* to; |
120 |
int res = tree.assertTreeLinks(from, to); |
121 |
if (res != 0 || from || to) { |
122 |
std::string sFrom = from ? ((std::string)*from) : "NULL"; |
123 |
std::string sTo = to ? ((std::string)*to) : "NULL"; |
124 |
std::cout << "!!! Tree links inconsistency detected !!!\n" |
125 |
<< "!!! Invalid link from " << sFrom << " to " << sTo << " !!!\n"; |
126 |
exit(-1); |
127 |
} |
128 |
} |
129 |
|
130 |
static void assertTreeSize(MyTree& tree) { |
131 |
if (tree.count() != tree.size()) { |
132 |
std::cout << "!!! Tree size inconsistency detected !!!\n" |
133 |
<< "!!! size() says " << tree.size() << " whereas count() says " << tree.count() << " !!!\n"; |
134 |
exit(-1); |
135 |
} |
136 |
if (!tree.size() != tree.isEmpty()) { |
137 |
std::cout << "!!! Tree emptyness inconsistency detected !!!\n" |
138 |
<< "!!! isEmpty() says " << tree.isEmpty() << " whereas size() says " << tree.size() << " !!!\n"; |
139 |
exit(-1); |
140 |
} |
141 |
} |
142 |
|
143 |
static void assertTreeBalance(MyTree& tree) { |
144 |
IntNode* unbalanced = tree.assertTreeBalance(); |
145 |
if (unbalanced) { |
146 |
std::cout << "!!! Tree imbalance detected !!!\n" |
147 |
<< "!!! Node " << ((std::string)*unbalanced) << " is unbalanced !!!\n"; |
148 |
exit(-1); |
149 |
} |
150 |
} |
151 |
|
152 |
static void printMaximas(MyTree& tree) { |
153 |
if (tree.isEmpty()) return; |
154 |
std::cout << "LOW=" << tree.lowest().value << " HIGH=" << tree.highest().value << std::endl; |
155 |
} |
156 |
|
157 |
static void insert(MyTree& tree, IntNode& node) { |
158 |
std::cout << "+++ Insert " << node.value << " into tree +++\n"; |
159 |
tree.insert(node); |
160 |
tree.dumpTree(); |
161 |
assertTreeLinks(tree); |
162 |
assertTreeSize(tree); |
163 |
assertTreeBalance(tree); |
164 |
printMaximas(tree); |
165 |
} |
166 |
|
167 |
static void erase(MyTree& tree, IntNode& node) { |
168 |
std::cout << "--- Erase " << node.value << " from tree ---\n"; |
169 |
tree.erase(node); |
170 |
tree.dumpTree(); |
171 |
assertTreeLinks(tree); |
172 |
assertTreeSize(tree); |
173 |
assertTreeBalance(tree); |
174 |
printMaximas(tree); |
175 |
} |
176 |
|
177 |
/// Automated test case which aborts this process with exit(-1) in case an error is detected. |
178 |
static void testTreeInsertAndEraseWithSelectedNumbers() { |
179 |
std::cout << "UNIT TEST: InsertAndEraseWithSelectedNumbers\n"; |
180 |
std::cout << "*** Create empty tree ***\n"; |
181 |
MyTree tree; |
182 |
tree.dumpTree(); |
183 |
|
184 |
const int MAX_NODES = 20; |
185 |
IntNode nodes[MAX_NODES]; |
186 |
for (int i = 0; i < MAX_NODES; ++i) |
187 |
nodes[i].value = i; |
188 |
|
189 |
// fill up the tree with numbers ... |
190 |
|
191 |
insert(tree, nodes[6]); |
192 |
insert(tree, nodes[7]); |
193 |
insert(tree, nodes[9]); |
194 |
insert(tree, nodes[3]); |
195 |
insert(tree, nodes[5]); |
196 |
insert(tree, nodes[1]); |
197 |
insert(tree, nodes[8]); |
198 |
insert(tree, nodes[15]); |
199 |
insert(tree, nodes[12]); |
200 |
insert(tree, nodes[11]); |
201 |
insert(tree, nodes[10]); |
202 |
insert(tree, nodes[13]); |
203 |
insert(tree, nodes[17]); |
204 |
insert(tree, nodes[19]); |
205 |
insert(tree, nodes[16]); |
206 |
insert(tree, nodes[14]); |
207 |
insert(tree, nodes[18]); |
208 |
insert(tree, nodes[4]); |
209 |
insert(tree, nodes[2]); |
210 |
insert(tree, nodes[0]); |
211 |
|
212 |
// now start to erase ... |
213 |
|
214 |
erase(tree, nodes[18]); |
215 |
erase(tree, nodes[5]); |
216 |
erase(tree, nodes[6]); |
217 |
erase(tree, nodes[9]); |
218 |
erase(tree, nodes[13]); |
219 |
erase(tree, nodes[7]); |
220 |
erase(tree, nodes[3]); |
221 |
erase(tree, nodes[10]); |
222 |
erase(tree, nodes[19]); |
223 |
erase(tree, nodes[15]); |
224 |
erase(tree, nodes[11]); |
225 |
erase(tree, nodes[4]); |
226 |
erase(tree, nodes[0]); |
227 |
erase(tree, nodes[14]); |
228 |
erase(tree, nodes[1]); |
229 |
erase(tree, nodes[16]); |
230 |
erase(tree, nodes[8]); |
231 |
erase(tree, nodes[12]); |
232 |
erase(tree, nodes[17]); |
233 |
erase(tree, nodes[2]); |
234 |
|
235 |
std::cout << std::endl; |
236 |
} |
237 |
|
238 |
/// Automated test case which aborts this process with exit(-1) in case an error is detected. |
239 |
static void testTreeInsertAndEraseWithRandomNumbers() { |
240 |
std::cout << "UNIT TEST: InsertAndEraseWithRandomNumbers\n"; |
241 |
srand(time(NULL)); |
242 |
|
243 |
std::cout << "*** Create empty tree ***\n"; |
244 |
MyTree tree; |
245 |
tree.dumpTree(); |
246 |
|
247 |
const int MAX_NODES = 30; |
248 |
IntNode nodes[MAX_NODES]; |
249 |
std::vector<IntNode*> freeNodes; |
250 |
std::vector<IntNode*> usedNodes; |
251 |
for (int i = 0; i < MAX_NODES; ++i) { |
252 |
nodes[i].value = i; |
253 |
freeNodes.push_back(&nodes[i]); |
254 |
} |
255 |
|
256 |
// insert all MAX_NODES nodes into the tree (in randomly selected sequence) |
257 |
do { |
258 |
const double r = double(rand()) / double(RAND_MAX); |
259 |
const int idx = int(r * double(freeNodes.size())); |
260 |
|
261 |
insert(tree, *freeNodes[idx]); |
262 |
|
263 |
usedNodes.push_back(freeNodes[idx]); |
264 |
freeNodes.erase(freeNodes.begin()+idx); |
265 |
|
266 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
267 |
assert(tree.size() == usedNodes.size()); |
268 |
} while (!freeNodes.empty()); |
269 |
|
270 |
// randomly erase and re-insert elements into the tree for a certain while |
271 |
for (int run = 0; run < 300; ++run) { |
272 |
bool doInsert = |
273 |
freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1); |
274 |
if (doInsert) { |
275 |
const double r = double(rand()) / double(RAND_MAX); |
276 |
const int idx = int(r * double(freeNodes.size())); |
277 |
|
278 |
insert(tree, *freeNodes[idx]); |
279 |
|
280 |
usedNodes.push_back(freeNodes[idx]); |
281 |
freeNodes.erase(freeNodes.begin()+idx); |
282 |
} else { |
283 |
const double r = double(rand()) / double(RAND_MAX); |
284 |
const int idx = int(r * double(usedNodes.size())); |
285 |
|
286 |
erase(tree, *usedNodes[idx]); |
287 |
|
288 |
freeNodes.push_back(usedNodes[idx]); |
289 |
usedNodes.erase(usedNodes.begin()+idx); |
290 |
} |
291 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
292 |
assert(tree.size() == usedNodes.size()); |
293 |
} |
294 |
|
295 |
// randomly erase from tree until tree is completely empty |
296 |
while (!usedNodes.empty()) { |
297 |
const double r = double(rand()) / double(RAND_MAX); |
298 |
const int idx = int(r * double(usedNodes.size())); |
299 |
|
300 |
erase(tree, *usedNodes[idx]); |
301 |
|
302 |
freeNodes.push_back(usedNodes[idx]); |
303 |
usedNodes.erase(usedNodes.begin()+idx); |
304 |
|
305 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
306 |
assert(tree.size() == usedNodes.size()); |
307 |
} |
308 |
|
309 |
// randomly erase and re-insert elements into the tree for a certain while |
310 |
for (int run = 0; run < 300; ++run) { |
311 |
bool doInsert = |
312 |
freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1); |
313 |
if (doInsert) { |
314 |
const double r = double(rand()) / double(RAND_MAX); |
315 |
const int idx = int(r * double(freeNodes.size())); |
316 |
|
317 |
insert(tree, *freeNodes[idx]); |
318 |
|
319 |
usedNodes.push_back(freeNodes[idx]); |
320 |
freeNodes.erase(freeNodes.begin()+idx); |
321 |
} else { |
322 |
const double r = double(rand()) / double(RAND_MAX); |
323 |
const int idx = int(r * double(usedNodes.size())); |
324 |
|
325 |
erase(tree, *usedNodes[idx]); |
326 |
|
327 |
freeNodes.push_back(usedNodes[idx]); |
328 |
usedNodes.erase(usedNodes.begin()+idx); |
329 |
} |
330 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
331 |
assert(tree.size() == usedNodes.size()); |
332 |
} |
333 |
|
334 |
// randomly erase from tree until tree is completely empty |
335 |
while (!usedNodes.empty()) { |
336 |
const double r = double(rand()) / double(RAND_MAX); |
337 |
const int idx = int(r * double(usedNodes.size())); |
338 |
|
339 |
erase(tree, *usedNodes[idx]); |
340 |
|
341 |
freeNodes.push_back(usedNodes[idx]); |
342 |
usedNodes.erase(usedNodes.begin()+idx); |
343 |
|
344 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
345 |
assert(tree.size() == usedNodes.size()); |
346 |
} |
347 |
|
348 |
std::cout << std::endl; |
349 |
} |
350 |
|
351 |
/// Automated test case which aborts this process with exit(-1) in case an error is detected. |
352 |
static void testTwinsWithRandomNumbers() { |
353 |
std::cout << "UNIT TEST: TwinsWithRandomNumbers\n"; |
354 |
srand(time(NULL)); |
355 |
|
356 |
std::cout << "*** Create empty tree ***\n"; |
357 |
MyTree tree; |
358 |
tree.dumpTree(); |
359 |
|
360 |
const int MAX_NODES = 30; |
361 |
IntNode nodes[MAX_NODES]; |
362 |
std::vector<IntNode*> freeNodes; |
363 |
std::vector<IntNode*> usedNodes; |
364 |
for (int i = 0; i < MAX_NODES; ++i) { |
365 |
const double r = double(rand()) / double(RAND_MAX); |
366 |
const int value = int(r * double(MAX_NODES) * 0.66); |
367 |
|
368 |
nodes[i].value = value; |
369 |
freeNodes.push_back(&nodes[i]); |
370 |
} |
371 |
|
372 |
// insert all MAX_NODES nodes into the tree (in randomly selected sequence) |
373 |
do { |
374 |
const double r = double(rand()) / double(RAND_MAX); |
375 |
const int idx = int(r * double(freeNodes.size())); |
376 |
|
377 |
insert(tree, *freeNodes[idx]); |
378 |
|
379 |
usedNodes.push_back(freeNodes[idx]); |
380 |
freeNodes.erase(freeNodes.begin()+idx); |
381 |
|
382 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
383 |
assert(tree.size() == usedNodes.size()); |
384 |
} while (!freeNodes.empty()); |
385 |
|
386 |
// randomly erase and re-insert elements into the tree for a certain while |
387 |
for (int run = 0; run < 300; ++run) { |
388 |
bool doInsert = |
389 |
freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1); |
390 |
if (doInsert) { |
391 |
const double r = double(rand()) / double(RAND_MAX); |
392 |
const int idx = int(r * double(freeNodes.size())); |
393 |
|
394 |
insert(tree, *freeNodes[idx]); |
395 |
|
396 |
usedNodes.push_back(freeNodes[idx]); |
397 |
freeNodes.erase(freeNodes.begin()+idx); |
398 |
} else { |
399 |
const double r = double(rand()) / double(RAND_MAX); |
400 |
const int idx = int(r * double(usedNodes.size())); |
401 |
|
402 |
erase(tree, *usedNodes[idx]); |
403 |
|
404 |
freeNodes.push_back(usedNodes[idx]); |
405 |
usedNodes.erase(usedNodes.begin()+idx); |
406 |
} |
407 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
408 |
assert(tree.size() == usedNodes.size()); |
409 |
} |
410 |
|
411 |
// randomly erase from tree until tree is completely empty |
412 |
while (!usedNodes.empty()) { |
413 |
const double r = double(rand()) / double(RAND_MAX); |
414 |
const int idx = int(r * double(usedNodes.size())); |
415 |
|
416 |
erase(tree, *usedNodes[idx]); |
417 |
|
418 |
freeNodes.push_back(usedNodes[idx]); |
419 |
usedNodes.erase(usedNodes.begin()+idx); |
420 |
|
421 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
422 |
assert(tree.size() == usedNodes.size()); |
423 |
} |
424 |
|
425 |
// randomly erase and re-insert elements into the tree for a certain while |
426 |
for (int run = 0; run < 300; ++run) { |
427 |
bool doInsert = |
428 |
freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1); |
429 |
if (doInsert) { |
430 |
const double r = double(rand()) / double(RAND_MAX); |
431 |
const int idx = int(r * double(freeNodes.size())); |
432 |
|
433 |
insert(tree, *freeNodes[idx]); |
434 |
|
435 |
usedNodes.push_back(freeNodes[idx]); |
436 |
freeNodes.erase(freeNodes.begin()+idx); |
437 |
} else { |
438 |
const double r = double(rand()) / double(RAND_MAX); |
439 |
const int idx = int(r * double(usedNodes.size())); |
440 |
|
441 |
erase(tree, *usedNodes[idx]); |
442 |
|
443 |
freeNodes.push_back(usedNodes[idx]); |
444 |
usedNodes.erase(usedNodes.begin()+idx); |
445 |
} |
446 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
447 |
assert(tree.size() == usedNodes.size()); |
448 |
} |
449 |
|
450 |
// randomly erase from tree until tree is completely empty |
451 |
while (!usedNodes.empty()) { |
452 |
const double r = double(rand()) / double(RAND_MAX); |
453 |
const int idx = int(r * double(usedNodes.size())); |
454 |
|
455 |
erase(tree, *usedNodes[idx]); |
456 |
|
457 |
freeNodes.push_back(usedNodes[idx]); |
458 |
usedNodes.erase(usedNodes.begin()+idx); |
459 |
|
460 |
assert(usedNodes.size() + freeNodes.size() == MAX_NODES); |
461 |
assert(tree.size() == usedNodes.size()); |
462 |
} |
463 |
|
464 |
std::cout << std::endl; |
465 |
} |
466 |
|
467 |
int main() { |
468 |
testTreeDumpWithManualTreeBuilt(); |
469 |
testTreeInsertAndEraseWithSelectedNumbers(); |
470 |
testTreeInsertAndEraseWithRandomNumbers(); |
471 |
testTwinsWithRandomNumbers(); |
472 |
std::cout << "\nAll tests passed successfully. :-)\n"; |
473 |
return 0; |
474 |
} |