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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 2871 by schoenebeck, Sun Apr 10 18:22:23 2016 UTC revision 3288 by schoenebeck, Fri Jun 23 11:56:17 2017 UTC
# Line 1  Line 1 
1  /*  /*
2   * Copyright (c) 2015 Christian Schoenebeck   * Copyright (c) 2015 - 2017 Christian Schoenebeck
3   *   *
4   * http://www.linuxsampler.org   * http://www.linuxsampler.org
5   *   *
# Line 15  Line 15 
15  #include <time.h>  #include <time.h>
16  #include <assert.h>  #include <assert.h>
17    
18    #ifndef TEST_ASSERT
19    # define TEST_ASSERT assert
20    #endif
21    
22  class IntNode : public RTAVLNode {  class IntNode : public RTAVLNode {
23  public:  public:
24      enum Dir_t {      enum Dir_t {
# Line 23  public: Line 27  public:
27      };      };
28    
29      int value;      int value;
30      RTAVLNode::parent;      using RTAVLNode::parent;
31      RTAVLNode::children;      using RTAVLNode::children;
32      RTAVLNode::reset;      using RTAVLNode::reset;
33    
34      inline bool operator==(const IntNode& other) const {      inline bool operator==(const IntNode& other) const {
35          return this->value == other.value;          return this->value == other.value;
# Line 44  public: Line 48  public:
48      }      }
49    
50      void appendLeft(IntNode& child) {      void appendLeft(IntNode& child) {
51            #if !SILENT_TEST
52          std::cout << "*** Insert " << child.value << " as left child of " << this->value << " ***\n";          std::cout << "*** Insert " << child.value << " as left child of " << this->value << " ***\n";
53            #endif
54          IntNode& root = *this;          IntNode& root = *this;
55          IntNode& l    = child;          IntNode& l    = child;
56          root.children[LEFT] = &l;          root.children[LEFT] = &l;
# Line 54  public: Line 60  public:
60      }      }
61    
62      void appendRight(IntNode& child) {      void appendRight(IntNode& child) {
63            #if !SILENT_TEST
64          std::cout << "*** Insert " << child.value << " as right child of " << this->value << " ***\n";          std::cout << "*** Insert " << child.value << " as right child of " << this->value << " ***\n";
65            #endif
66          IntNode& root = *this;          IntNode& root = *this;
67          IntNode& r    = child;          IntNode& r    = child;
68          root.children[RIGHT] = &r;          root.children[RIGHT] = &r;
# Line 155  static void printMaximas(MyTree& tree) { Line 163  static void printMaximas(MyTree& tree) {
163  }  }
164    
165  static void insert(MyTree& tree, IntNode& node) {  static void insert(MyTree& tree, IntNode& node) {
166        #if !SILENT_TEST
167      std::cout << "+++ Insert " << node.value << " into tree +++\n";      std::cout << "+++ Insert " << node.value << " into tree +++\n";
168        #endif
169      tree.insert(node);      tree.insert(node);
170        #if !NO_TREE_DUMP && !SILENT_TEST
171      tree.dumpTree();      tree.dumpTree();
172        #endif
173      assertTreeLinks(tree);      assertTreeLinks(tree);
174      assertTreeSize(tree);      assertTreeSize(tree);
175      assertTreeBalance(tree);      assertTreeBalance(tree);
176        #if !SILENT_TEST
177      printMaximas(tree);      printMaximas(tree);
178        #endif
179  }  }
180    
181  static void erase(MyTree& tree, IntNode& node) {  static void erase(MyTree& tree, IntNode& node) {
182        #if !SILENT_TEST
183      std::cout << "--- Erase " << node.value << " from tree ---\n";      std::cout << "--- Erase " << node.value << " from tree ---\n";
184        #endif
185      tree.erase(node);      tree.erase(node);
186        #if !NO_TREE_DUMP && !SILENT_TEST
187      tree.dumpTree();      tree.dumpTree();
188        #endif
189      assertTreeLinks(tree);      assertTreeLinks(tree);
190      assertTreeSize(tree);      assertTreeSize(tree);
191      assertTreeBalance(tree);      assertTreeBalance(tree);
192        #if !SILENT_TEST
193      printMaximas(tree);      printMaximas(tree);
194        #endif
195  }  }
196    
197  /// Automated test case which aborts this process with exit(-1) in case an error is detected.  /// Automated test case which aborts this process with exit(-1) in case an error is detected.
198  static void testTreeInsertAndEraseWithSelectedNumbers() {  static void testTreeInsertAndEraseWithSelectedNumbers() {
199        #if !SILENT_TEST
200      std::cout << "UNIT TEST: InsertAndEraseWithSelectedNumbers\n";      std::cout << "UNIT TEST: InsertAndEraseWithSelectedNumbers\n";
201      std::cout << "*** Create empty tree ***\n";      std::cout << "*** Create empty tree ***\n";
202        #endif
203      MyTree tree;      MyTree tree;
204        #if !NO_TREE_DUMP && !SILENT_TEST
205      tree.dumpTree();      tree.dumpTree();
206        #endif
207    
208      const int MAX_NODES = 20;      const int MAX_NODES = 20;
209      IntNode nodes[MAX_NODES];      IntNode nodes[MAX_NODES];
# Line 232  static void testTreeInsertAndEraseWithSe Line 256  static void testTreeInsertAndEraseWithSe
256      erase(tree, nodes[17]);      erase(tree, nodes[17]);
257      erase(tree, nodes[2]);      erase(tree, nodes[2]);
258    
259        #if !SILENT_TEST
260      std::cout << std::endl;      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.  /// Automated test case which aborts this process with exit(-1) in case an error is detected.
265  static void testTreeInsertAndEraseWithRandomNumbers() {  static void testTreeInsertAndEraseWithRandomNumbers() {
266        #if !SILENT_TEST
267      std::cout << "UNIT TEST: InsertAndEraseWithRandomNumbers\n";      std::cout << "UNIT TEST: InsertAndEraseWithRandomNumbers\n";
268        #endif
269      srand(time(NULL));      srand(time(NULL));
270    
271        #if !SILENT_TEST
272      std::cout << "*** Create empty tree ***\n";      std::cout << "*** Create empty tree ***\n";
273        #endif
274      MyTree tree;      MyTree tree;
275        #if !NO_TREE_DUMP && !SILENT_TEST
276      tree.dumpTree();      tree.dumpTree();
277        #endif
278    
279      const int MAX_NODES = 30;      const int MAX_NODES = 30;
280      IntNode nodes[MAX_NODES];      IntNode nodes[MAX_NODES];
# Line 263  static void testTreeInsertAndEraseWithRa Line 295  static void testTreeInsertAndEraseWithRa
295          usedNodes.push_back(freeNodes[idx]);          usedNodes.push_back(freeNodes[idx]);
296          freeNodes.erase(freeNodes.begin()+idx);          freeNodes.erase(freeNodes.begin()+idx);
297                    
298          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
299          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
300      } while (!freeNodes.empty());      } while (!freeNodes.empty());
301    
302      // randomly erase and re-insert elements into the tree for a certain while      // randomly erase and re-insert elements into the tree for a certain while
# Line 288  static void testTreeInsertAndEraseWithRa Line 320  static void testTreeInsertAndEraseWithRa
320              freeNodes.push_back(usedNodes[idx]);              freeNodes.push_back(usedNodes[idx]);
321              usedNodes.erase(usedNodes.begin()+idx);              usedNodes.erase(usedNodes.begin()+idx);
322          }          }
323          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
324          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
325      }      }
326    
327      // randomly erase from tree until tree is completely empty      // randomly erase from tree until tree is completely empty
# Line 302  static void testTreeInsertAndEraseWithRa Line 334  static void testTreeInsertAndEraseWithRa
334          freeNodes.push_back(usedNodes[idx]);          freeNodes.push_back(usedNodes[idx]);
335          usedNodes.erase(usedNodes.begin()+idx);          usedNodes.erase(usedNodes.begin()+idx);
336                    
337          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
338          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
339      }      }
340    
341      // randomly erase and re-insert elements into the tree for a certain while      // randomly erase and re-insert elements into the tree for a certain while
# Line 327  static void testTreeInsertAndEraseWithRa Line 359  static void testTreeInsertAndEraseWithRa
359              freeNodes.push_back(usedNodes[idx]);              freeNodes.push_back(usedNodes[idx]);
360              usedNodes.erase(usedNodes.begin()+idx);              usedNodes.erase(usedNodes.begin()+idx);
361          }          }
362          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
363          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
364      }      }
365    
366      // randomly erase from tree until tree is completely empty      // randomly erase from tree until tree is completely empty
# Line 341  static void testTreeInsertAndEraseWithRa Line 373  static void testTreeInsertAndEraseWithRa
373          freeNodes.push_back(usedNodes[idx]);          freeNodes.push_back(usedNodes[idx]);
374          usedNodes.erase(usedNodes.begin()+idx);          usedNodes.erase(usedNodes.begin()+idx);
375    
376          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
377          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
378      }      }
379    
380        #if !SILENT_TEST
381      std::cout << std::endl;      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.  /// Automated test case which aborts this process with exit(-1) in case an error is detected.
386  static void testTwinsWithRandomNumbers() {  static void testTwinsWithRandomNumbers() {
387        #if !SILENT_TEST
388      std::cout << "UNIT TEST: TwinsWithRandomNumbers\n";      std::cout << "UNIT TEST: TwinsWithRandomNumbers\n";
389        #endif
390      srand(time(NULL));      srand(time(NULL));
391    
392        #if !SILENT_TEST
393      std::cout << "*** Create empty tree ***\n";      std::cout << "*** Create empty tree ***\n";
394        #endif
395      MyTree tree;      MyTree tree;
396        #if !NO_TREE_DUMP && !SILENT_TEST
397      tree.dumpTree();      tree.dumpTree();
398        #endif
399    
400      const int MAX_NODES = 30;      const int MAX_NODES = 30;
401      IntNode nodes[MAX_NODES];      IntNode nodes[MAX_NODES];
# Line 379  static void testTwinsWithRandomNumbers() Line 419  static void testTwinsWithRandomNumbers()
419          usedNodes.push_back(freeNodes[idx]);          usedNodes.push_back(freeNodes[idx]);
420          freeNodes.erase(freeNodes.begin()+idx);          freeNodes.erase(freeNodes.begin()+idx);
421                    
422          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
423          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
424      } while (!freeNodes.empty());      } while (!freeNodes.empty());
425            
426      // randomly erase and re-insert elements into the tree for a certain while      // randomly erase and re-insert elements into the tree for a certain while
# Line 404  static void testTwinsWithRandomNumbers() Line 444  static void testTwinsWithRandomNumbers()
444              freeNodes.push_back(usedNodes[idx]);              freeNodes.push_back(usedNodes[idx]);
445              usedNodes.erase(usedNodes.begin()+idx);              usedNodes.erase(usedNodes.begin()+idx);
446          }          }
447          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
448          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
449      }      }
450    
451      // randomly erase from tree until tree is completely empty      // randomly erase from tree until tree is completely empty
# Line 418  static void testTwinsWithRandomNumbers() Line 458  static void testTwinsWithRandomNumbers()
458          freeNodes.push_back(usedNodes[idx]);          freeNodes.push_back(usedNodes[idx]);
459          usedNodes.erase(usedNodes.begin()+idx);          usedNodes.erase(usedNodes.begin()+idx);
460                    
461          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
462          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
463      }      }
464    
465      // randomly erase and re-insert elements into the tree for a certain while      // randomly erase and re-insert elements into the tree for a certain while
# Line 443  static void testTwinsWithRandomNumbers() Line 483  static void testTwinsWithRandomNumbers()
483              freeNodes.push_back(usedNodes[idx]);              freeNodes.push_back(usedNodes[idx]);
484              usedNodes.erase(usedNodes.begin()+idx);              usedNodes.erase(usedNodes.begin()+idx);
485          }          }
486          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
487          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
488      }      }
489    
490      // randomly erase from tree until tree is completely empty      // randomly erase from tree until tree is completely empty
# Line 457  static void testTwinsWithRandomNumbers() Line 497  static void testTwinsWithRandomNumbers()
497          freeNodes.push_back(usedNodes[idx]);          freeNodes.push_back(usedNodes[idx]);
498          usedNodes.erase(usedNodes.begin()+idx);          usedNodes.erase(usedNodes.begin()+idx);
499                    
500          assert(usedNodes.size() + freeNodes.size() == MAX_NODES);          TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
501          assert(tree.size() == usedNodes.size());          TEST_ASSERT(tree.size() == usedNodes.size());
502      }      }
503    
504        #if !SILENT_TEST
505      std::cout << std::endl;      std::cout << std::endl;
506        #endif
507  }  }
508    
509    #if !NO_MAIN
510    
511  int main() {  int main() {
512      testTreeDumpWithManualTreeBuilt();      testTreeDumpWithManualTreeBuilt();
513      testTreeInsertAndEraseWithSelectedNumbers();      testTreeInsertAndEraseWithSelectedNumbers();
# Line 472  int main() { Line 516  int main() {
516      std::cout << "\nAll tests passed successfully. :-)\n";      std::cout << "\nAll tests passed successfully. :-)\n";
517      return 0;      return 0;
518  }  }
519    
520    #endif // !NO_MAIN
Legend:
Removed from v.2871  
changed lines
  Added in v.3288
  ViewVC Help
Powered by ViewVC