src/common/RTAVLTreeTest.cpp

/*
 * Copyright (c) 2015 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>

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

    int value;
    RTAVLNode::parent;
    RTAVLNode::children;
    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) {
        std::cout << "*** Insert " << child.value << " as left child of " << this->value << " ***\n";
        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) {
        std::cout << "*** Insert " << child.value << " as right child of " << this->value << " ***\n";
        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) {
    std::cout << "+++ Insert " << node.value << " into tree +++\n";
    tree.insert(node);
    tree.dumpTree();
    assertTreeLinks(tree);
    assertTreeSize(tree);
    assertTreeBalance(tree);
    printMaximas(tree);
}

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

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

    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]);

    std::cout << std::endl;
}

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

    std::cout << "*** Create empty tree ***\n";
    MyTree tree;
    tree.dumpTree();

    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);
        
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        }
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        }
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);

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

    std::cout << std::endl;
}

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

    std::cout << "*** Create empty tree ***\n";
    MyTree tree;
    tree.dumpTree();

    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);
        
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        }
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        }
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        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);
        
        assert(usedNodes.size() + freeNodes.size() == MAX_NODES);
        assert(tree.size() == usedNodes.size());
    }

    std::cout << std::endl;
}

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