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	/*
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