src/common/RTAVLTreeTest.cpp

/*
 * Copyright (c) 2015 - 2017 Christian Schoenebeck
 *
 * http://www.linuxsampler.org
 *
 * This file is part of LinuxSampler and released under the same terms.
 * See README file for details.
 */

// This file contains automated test cases against the RTAVLTree template class.

#include "RTAVLTree.h"
#include <sstream>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#ifndef TEST_ASSERT
# define TEST_ASSERT assert
#endif

class IntNode : public RTAVLNode {
public:
    enum Dir_t {
        LEFT,
        RIGHT 
    };

    int value;
    using RTAVLNode::parent;
    using RTAVLNode::children;
    using RTAVLNode::reset;

    inline bool operator==(const IntNode& other) const {
        return this->value == other.value;
    }

    inline bool operator<(const IntNode& other) const {
        return this->value < other.value;
    }

    inline operator std::string() const {
        const int n = countTwins();
        std::stringstream ss;
        if (n > 1) ss << n << "x";
        ss << "[" << value << "(" << balance << ")]";
        return ss.str();
    }

    void appendLeft(IntNode& child) {
        #if !SILENT_TEST
        std::cout << "*** Insert " << child.value << " as left child of " << this->value << " ***\n";
        #endif
        IntNode& root = *this;
        IntNode& l    = child;
        root.children[LEFT] = &l;
        l.parent = &root;
        l.children[LEFT]  = NULL;
        l.children[RIGHT] = NULL;
    }

    void appendRight(IntNode& child) {
        #if !SILENT_TEST
        std::cout << "*** Insert " << child.value << " as right child of " << this->value << " ***\n";
        #endif
        IntNode& root = *this;
        IntNode& r    = child;
        root.children[RIGHT] = &r;
        r.parent = &root;
        r.children[LEFT]  = NULL;
        r.children[RIGHT] = NULL;
    }
};

typedef RTAVLTree<IntNode> MyTree;

/// This test case requires a visual check by humans, that means it will never detect errors on its own!
static void testTreeDumpWithManualTreeBuilt() {
    std::cout << "UNIT TEST: ManualTreeBuilt\n";
    std::cout << "*** Create empty tree ***\n";
    MyTree tree;
    tree.dumpTree();

    const int MAX_NODES = 10;
    IntNode nodes[MAX_NODES];
    for (int i = 0; i < MAX_NODES; ++i) {
        nodes[i].value = i;
        nodes[i].reset();
    }

    std::cout << "*** Insert " << nodes[0].value << " into tree ***\n";
    tree.insert(nodes[0]);
    tree.dumpTree();

    nodes[0].appendLeft(nodes[1]);
    tree.dumpTree();

    nodes[1].appendLeft(nodes[2]);
    tree.dumpTree();

    nodes[1].appendRight(nodes[3]);
    tree.dumpTree();
    
    nodes[3].appendRight(nodes[4]);
    tree.dumpTree();
    
    nodes[0].appendRight(nodes[5]);
    tree.dumpTree();
    
    nodes[5].appendLeft(nodes[6]);
    tree.dumpTree();
    
    nodes[6].appendLeft(nodes[7]);
    tree.dumpTree();
    
    nodes[5].appendRight(nodes[8]);
    tree.dumpTree();
    
    nodes[6].appendRight(nodes[9]);
    tree.dumpTree();
    
    std::cout << std::endl;
}

static void assertTreeLinks(MyTree& tree) {
    IntNode* from;
    IntNode* to;
    int res = tree.assertTreeLinks(from, to);
    if (res != 0 || from || to) {
        std::string sFrom = from ? ((std::string)*from) : "NULL";
        std::string sTo   = to ? ((std::string)*to) : "NULL";
        std::cout << "!!! Tree links inconsistency detected !!!\n"
                  << "!!! Invalid link from " << sFrom << " to " << sTo << " !!!\n";
        exit(-1);
    }
}

static void assertTreeSize(MyTree& tree) {
    if (tree.count() != tree.size()) {
        std::cout << "!!! Tree size inconsistency detected !!!\n"
                  << "!!! size() says " << tree.size() << " whereas count() says " << tree.count() << " !!!\n";
        exit(-1);
    }
    if (!tree.size() != tree.isEmpty()) {
        std::cout << "!!! Tree emptyness inconsistency detected !!!\n"
                  << "!!! isEmpty() says " << tree.isEmpty() << " whereas size() says " << tree.size() << " !!!\n";
        exit(-1);
    }
}

static void assertTreeBalance(MyTree& tree) {
    IntNode* unbalanced = tree.assertTreeBalance();
    if (unbalanced) {
        std::cout << "!!! Tree imbalance detected !!!\n"
                  << "!!! Node " << ((std::string)*unbalanced) << " is unbalanced !!!\n";
        exit(-1);
    }
}

static void printMaximas(MyTree& tree) {
    if (tree.isEmpty()) return;
    std::cout << "LOW=" << tree.lowest().value << " HIGH=" << tree.highest().value << std::endl;
}

static void insert(MyTree& tree, IntNode& node) {
    #if !SILENT_TEST
    std::cout << "+++ Insert " << node.value << " into tree +++\n";
    #endif
    tree.insert(node);
    #if !NO_TREE_DUMP && !SILENT_TEST
    tree.dumpTree();
    #endif
    assertTreeLinks(tree);
    assertTreeSize(tree);
    assertTreeBalance(tree);
    #if !SILENT_TEST
    printMaximas(tree);
    #endif
}

static void erase(MyTree& tree, IntNode& node) {
    #if !SILENT_TEST
    std::cout << "--- Erase " << node.value << " from tree ---\n";
    #endif
    tree.erase(node);
    #if !NO_TREE_DUMP && !SILENT_TEST
    tree.dumpTree();
    #endif
    assertTreeLinks(tree);
    assertTreeSize(tree);
    assertTreeBalance(tree);
    #if !SILENT_TEST
    printMaximas(tree);
    #endif
}

/// Automated test case which aborts this process with exit(-1) in case an error is detected.
static void testTreeInsertAndEraseWithSelectedNumbers() {
    #if !SILENT_TEST
    std::cout << "UNIT TEST: InsertAndEraseWithSelectedNumbers\n";
    std::cout << "*** Create empty tree ***\n";
    #endif
    MyTree tree;
    #if !NO_TREE_DUMP && !SILENT_TEST
    tree.dumpTree();
    #endif

    const int MAX_NODES = 20;
    IntNode nodes[MAX_NODES];
    for (int i = 0; i < MAX_NODES; ++i)
        nodes[i].value = i;

    // fill up the tree with numbers ...

    insert(tree, nodes[6]);
    insert(tree, nodes[7]);
    insert(tree, nodes[9]);
    insert(tree, nodes[3]);
    insert(tree, nodes[5]);
    insert(tree, nodes[1]);
    insert(tree, nodes[8]);
    insert(tree, nodes[15]);
    insert(tree, nodes[12]);
    insert(tree, nodes[11]);
    insert(tree, nodes[10]);
    insert(tree, nodes[13]);
    insert(tree, nodes[17]);
    insert(tree, nodes[19]);    
    insert(tree, nodes[16]);    
    insert(tree, nodes[14]);    
    insert(tree, nodes[18]);    
    insert(tree, nodes[4]);    
    insert(tree, nodes[2]);    
    insert(tree, nodes[0]);

    // now start to erase ...

    erase(tree, nodes[18]);
    erase(tree, nodes[5]);    
    erase(tree, nodes[6]);
    erase(tree, nodes[9]);    
    erase(tree, nodes[13]);    
    erase(tree, nodes[7]);
    erase(tree, nodes[3]);
    erase(tree, nodes[10]);
    erase(tree, nodes[19]);
    erase(tree, nodes[15]);
    erase(tree, nodes[11]);
    erase(tree, nodes[4]);
    erase(tree, nodes[0]);
    erase(tree, nodes[14]);
    erase(tree, nodes[1]);
    erase(tree, nodes[16]);
    erase(tree, nodes[8]);
    erase(tree, nodes[12]);
    erase(tree, nodes[17]);
    erase(tree, nodes[2]);

    #if !SILENT_TEST
    std::cout << std::endl;
    #endif
}

/// Automated test case which aborts this process with exit(-1) in case an error is detected.
static void testTreeInsertAndEraseWithRandomNumbers() {
    #if !SILENT_TEST
    std::cout << "UNIT TEST: InsertAndEraseWithRandomNumbers\n";
    #endif
    srand(time(NULL));

    #if !SILENT_TEST
    std::cout << "*** Create empty tree ***\n";
    #endif
    MyTree tree;
    #if !NO_TREE_DUMP && !SILENT_TEST
    tree.dumpTree();
    #endif

    const int MAX_NODES = 30;
    IntNode nodes[MAX_NODES];
    std::vector<IntNode*> freeNodes;
    std::vector<IntNode*> usedNodes;
    for (int i = 0; i < MAX_NODES; ++i) {
        nodes[i].value = i;
        freeNodes.push_back(&nodes[i]);
    }

    // insert all MAX_NODES nodes into the tree (in randomly selected sequence)
    do {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(freeNodes.size()));

        insert(tree, *freeNodes[idx]);

        usedNodes.push_back(freeNodes[idx]);
        freeNodes.erase(freeNodes.begin()+idx);
        
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    } while (!freeNodes.empty());

    // randomly erase and re-insert elements into the tree for a certain while
    for (int run = 0; run < 300; ++run) {
        bool doInsert =
            freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1);
        if (doInsert) {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(freeNodes.size()));

            insert(tree, *freeNodes[idx]);

            usedNodes.push_back(freeNodes[idx]);
            freeNodes.erase(freeNodes.begin()+idx);
        } else {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(usedNodes.size()));

            erase(tree, *usedNodes[idx]);

            freeNodes.push_back(usedNodes[idx]);
            usedNodes.erase(usedNodes.begin()+idx);
        }
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase from tree until tree is completely empty
    while (!usedNodes.empty()) {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(usedNodes.size()));

        erase(tree, *usedNodes[idx]);

        freeNodes.push_back(usedNodes[idx]);
        usedNodes.erase(usedNodes.begin()+idx);
        
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase and re-insert elements into the tree for a certain while
    for (int run = 0; run < 300; ++run) {
        bool doInsert =
            freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1);
        if (doInsert) {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(freeNodes.size()));

            insert(tree, *freeNodes[idx]);

            usedNodes.push_back(freeNodes[idx]);
            freeNodes.erase(freeNodes.begin()+idx);
        } else {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(usedNodes.size()));

            erase(tree, *usedNodes[idx]);

            freeNodes.push_back(usedNodes[idx]);
            usedNodes.erase(usedNodes.begin()+idx);
        }
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase from tree until tree is completely empty
    while (!usedNodes.empty()) {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(usedNodes.size()));

        erase(tree, *usedNodes[idx]);

        freeNodes.push_back(usedNodes[idx]);
        usedNodes.erase(usedNodes.begin()+idx);

        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    #if !SILENT_TEST
    std::cout << std::endl;
    #endif
}

/// Automated test case which aborts this process with exit(-1) in case an error is detected.
static void testTwinsWithRandomNumbers() {
    #if !SILENT_TEST
    std::cout << "UNIT TEST: TwinsWithRandomNumbers\n";
    #endif
    srand(time(NULL));

    #if !SILENT_TEST
    std::cout << "*** Create empty tree ***\n";
    #endif
    MyTree tree;
    #if !NO_TREE_DUMP && !SILENT_TEST
    tree.dumpTree();
    #endif

    const int MAX_NODES = 30;
    IntNode nodes[MAX_NODES];
    std::vector<IntNode*> freeNodes;
    std::vector<IntNode*> usedNodes;
    for (int i = 0; i < MAX_NODES; ++i) {
        const double r = double(rand()) / double(RAND_MAX);
        const int value = int(r * double(MAX_NODES) * 0.66);

        nodes[i].value = value;
        freeNodes.push_back(&nodes[i]);
    }

    // insert all MAX_NODES nodes into the tree (in randomly selected sequence)
    do {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(freeNodes.size()));

        insert(tree, *freeNodes[idx]);

        usedNodes.push_back(freeNodes[idx]);
        freeNodes.erase(freeNodes.begin()+idx);
        
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    } while (!freeNodes.empty());
    
    // randomly erase and re-insert elements into the tree for a certain while
    for (int run = 0; run < 300; ++run) {
        bool doInsert =
            freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1);
        if (doInsert) {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(freeNodes.size()));

            insert(tree, *freeNodes[idx]);

            usedNodes.push_back(freeNodes[idx]);
            freeNodes.erase(freeNodes.begin()+idx);
        } else {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(usedNodes.size()));

            erase(tree, *usedNodes[idx]);

            freeNodes.push_back(usedNodes[idx]);
            usedNodes.erase(usedNodes.begin()+idx);
        }
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase from tree until tree is completely empty
    while (!usedNodes.empty()) {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(usedNodes.size()));

        erase(tree, *usedNodes[idx]);

        freeNodes.push_back(usedNodes[idx]);
        usedNodes.erase(usedNodes.begin()+idx);
        
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase and re-insert elements into the tree for a certain while
    for (int run = 0; run < 300; ++run) {
        bool doInsert =
            freeNodes.empty() ? false : usedNodes.empty() ? true : (rand() & 1);
        if (doInsert) {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(freeNodes.size()));

            insert(tree, *freeNodes[idx]);

            usedNodes.push_back(freeNodes[idx]);
            freeNodes.erase(freeNodes.begin()+idx);
        } else {
            const double r = double(rand()) / double(RAND_MAX);
            const int idx = int(r * double(usedNodes.size()));

            erase(tree, *usedNodes[idx]);

            freeNodes.push_back(usedNodes[idx]);
            usedNodes.erase(usedNodes.begin()+idx);
        }
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    // randomly erase from tree until tree is completely empty
    while (!usedNodes.empty()) {
        const double r = double(rand()) / double(RAND_MAX);
        const int idx = int(r * double(usedNodes.size()));

        erase(tree, *usedNodes[idx]);

        freeNodes.push_back(usedNodes[idx]);
        usedNodes.erase(usedNodes.begin()+idx);
        
        TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
        TEST_ASSERT(tree.size() == usedNodes.size());
    }

    #if !SILENT_TEST
    std::cout << std::endl;
    #endif
}

#if !NO_MAIN

int main() {
    testTreeDumpWithManualTreeBuilt();
    testTreeInsertAndEraseWithSelectedNumbers();
    testTreeInsertAndEraseWithRandomNumbers();
    testTwinsWithRandomNumbers();
    std::cout << "\nAll tests passed successfully. :-)\n";
    return 0;
}

#endif // !NO_MAIN
1	schoenebeck	2871	/*
2	schoenebeck	3288	* Copyright (c) 2015 - 2017 Christian Schoenebeck
3	schoenebeck	2871	*
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	schoenebeck	3288	#ifndef TEST_ASSERT
19			# define TEST_ASSERT assert
20			#endif
21
22	schoenebeck	2871	class IntNode : public RTAVLNode {
23			public:
24			enum Dir_t {
25			LEFT,
26			RIGHT
27			};
28
29			int value;
30	schoenebeck	3288	using RTAVLNode::parent;
31			using RTAVLNode::children;
32			using RTAVLNode::reset;
33	schoenebeck	2871
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	schoenebeck	3288	#if !SILENT_TEST
52	schoenebeck	2871	std::cout << "* Insert " << child.value << " as left child of " << this->value << " *\n";
53	schoenebeck	3288	#endif
54	schoenebeck	2871	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	schoenebeck	3288	#if !SILENT_TEST
64	schoenebeck	2871	std::cout << "* Insert " << child.value << " as right child of " << this->value << " *\n";
65	schoenebeck	3288	#endif
66	schoenebeck	2871	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	schoenebeck	3288	#if !SILENT_TEST
167	schoenebeck	2871	std::cout << "+++ Insert " << node.value << " into tree +++\n";
168	schoenebeck	3288	#endif
169	schoenebeck	2871	tree.insert(node);
170	schoenebeck	3288	#if !NO_TREE_DUMP && !SILENT_TEST
171	schoenebeck	2871	tree.dumpTree();
172	schoenebeck	3288	#endif
173	schoenebeck	2871	assertTreeLinks(tree);
174			assertTreeSize(tree);
175			assertTreeBalance(tree);
176	schoenebeck	3288	#if !SILENT_TEST
177	schoenebeck	2871	printMaximas(tree);
178	schoenebeck	3288	#endif
179	schoenebeck	2871	}
180
181			static void erase(MyTree& tree, IntNode& node) {
182	schoenebeck	3288	#if !SILENT_TEST
183	schoenebeck	2871	std::cout << "--- Erase " << node.value << " from tree ---\n";
184	schoenebeck	3288	#endif
185	schoenebeck	2871	tree.erase(node);
186	schoenebeck	3288	#if !NO_TREE_DUMP && !SILENT_TEST
187	schoenebeck	2871	tree.dumpTree();
188	schoenebeck	3288	#endif
189	schoenebeck	2871	assertTreeLinks(tree);
190			assertTreeSize(tree);
191			assertTreeBalance(tree);
192	schoenebeck	3288	#if !SILENT_TEST
193	schoenebeck	2871	printMaximas(tree);
194	schoenebeck	3288	#endif
195	schoenebeck	2871	}
196
197			/// Automated test case which aborts this process with exit(-1) in case an error is detected.
198			static void testTreeInsertAndEraseWithSelectedNumbers() {
199	schoenebeck	3288	#if !SILENT_TEST
200	schoenebeck	2871	std::cout << "UNIT TEST: InsertAndEraseWithSelectedNumbers\n";
201			std::cout << "* Create empty tree *\n";
202	schoenebeck	3288	#endif
203	schoenebeck	2871	MyTree tree;
204	schoenebeck	3288	#if !NO_TREE_DUMP && !SILENT_TEST
205	schoenebeck	2871	tree.dumpTree();
206	schoenebeck	3288	#endif
207	schoenebeck	2871
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	schoenebeck	3288	#if !SILENT_TEST
260	schoenebeck	2871	std::cout << std::endl;
261	schoenebeck	3288	#endif
262	schoenebeck	2871	}
263
264			/// Automated test case which aborts this process with exit(-1) in case an error is detected.
265			static void testTreeInsertAndEraseWithRandomNumbers() {
266	schoenebeck	3288	#if !SILENT_TEST
267	schoenebeck	2871	std::cout << "UNIT TEST: InsertAndEraseWithRandomNumbers\n";
268	schoenebeck	3288	#endif
269	schoenebeck	2871	srand(time(NULL));
270
271	schoenebeck	3288	#if !SILENT_TEST
272	schoenebeck	2871	std::cout << "* Create empty tree *\n";
273	schoenebeck	3288	#endif
274	schoenebeck	2871	MyTree tree;
275	schoenebeck	3288	#if !NO_TREE_DUMP && !SILENT_TEST
276	schoenebeck	2871	tree.dumpTree();
277	schoenebeck	3288	#endif
278	schoenebeck	2871
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
299			TEST_ASSERT(tree.size() == usedNodes.size());
300	schoenebeck	2871	} 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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
324			TEST_ASSERT(tree.size() == usedNodes.size());
325	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
338			TEST_ASSERT(tree.size() == usedNodes.size());
339	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
363			TEST_ASSERT(tree.size() == usedNodes.size());
364	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
377			TEST_ASSERT(tree.size() == usedNodes.size());
378	schoenebeck	2871	}
379
380	schoenebeck	3288	#if !SILENT_TEST
381	schoenebeck	2871	std::cout << std::endl;
382	schoenebeck	3288	#endif
383	schoenebeck	2871	}
384
385			/// Automated test case which aborts this process with exit(-1) in case an error is detected.
386			static void testTwinsWithRandomNumbers() {
387	schoenebeck	3288	#if !SILENT_TEST
388	schoenebeck	2871	std::cout << "UNIT TEST: TwinsWithRandomNumbers\n";
389	schoenebeck	3288	#endif
390	schoenebeck	2871	srand(time(NULL));
391
392	schoenebeck	3288	#if !SILENT_TEST
393	schoenebeck	2871	std::cout << "* Create empty tree *\n";
394	schoenebeck	3288	#endif
395	schoenebeck	2871	MyTree tree;
396	schoenebeck	3288	#if !NO_TREE_DUMP && !SILENT_TEST
397	schoenebeck	2871	tree.dumpTree();
398	schoenebeck	3288	#endif
399	schoenebeck	2871
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
423			TEST_ASSERT(tree.size() == usedNodes.size());
424	schoenebeck	2871	} 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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
448			TEST_ASSERT(tree.size() == usedNodes.size());
449	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
462			TEST_ASSERT(tree.size() == usedNodes.size());
463	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
487			TEST_ASSERT(tree.size() == usedNodes.size());
488	schoenebeck	2871	}
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	schoenebeck	3288	TEST_ASSERT(usedNodes.size() + freeNodes.size() == MAX_NODES);
501			TEST_ASSERT(tree.size() == usedNodes.size());
502	schoenebeck	2871	}
503
504	schoenebeck	3288	#if !SILENT_TEST
505	schoenebeck	2871	std::cout << std::endl;
506	schoenebeck	3288	#endif
507	schoenebeck	2871	}
508
509	schoenebeck	3288	#if !NO_MAIN
510
511	schoenebeck	2871	int main() {
512			testTreeDumpWithManualTreeBuilt();
513			testTreeInsertAndEraseWithSelectedNumbers();
514			testTreeInsertAndEraseWithRandomNumbers();
515			testTwinsWithRandomNumbers();
516			std::cout << "\nAll tests passed successfully. :-)\n";
517			return 0;
518			}
519	schoenebeck	3288
520			#endif // !NO_MAIN