/[svn]/linuxsampler/trunk/src/common/RTAVLTreeTest.cpp
ViewVC logotype

Contents of /linuxsampler/trunk/src/common/RTAVLTreeTest.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3288 - (show annotations) (download)
Fri Jun 23 11:56:17 2017 UTC (3 years, 4 months ago) by schoenebeck
File size: 15767 byte(s)
- Just minor update to RTAVLTree unit tests.

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

  ViewVC Help
Powered by ViewVC