red_black_tree.c 3.46 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include "unittest.h"
#include "structures/red_black_tree.h"
#include <assert.h>
#include <stdio.h>

	
static void
test_red_black_tree_initialization(const_pointer data)
{
	struct RBTree* tree = rb_tree_new(cry_int_compare);

	assert(tree->nodes == 0);
	assert(rb_tree_lookup(tree, "unknown_key") == 0);

15
	rb_tree_clear(tree, 0);
16
17
18
19
20
21
22
23
24
25
26
27
28
	cry_free(tree);
}


static void
test_red_black_tree_insertion(const_pointer data)
{
	struct RBTree* tree = rb_tree_new(cry_int_compare);
	const int* keys = cry_cast(const int*, data);

	assert(tree->nodes == 0);

	while(*keys > 0) {
29
		assert(rb_tree_insert(tree, keys) != 0);
30
31
32
33
34
35
36
37
38
39
40
		++keys;
	}

	assert(tree->nodes == 10);

	keys = cry_cast(const int*, data);

        while(*keys > 0) {
		struct RBNode* node = rb_tree_lookup(tree, keys);

		assert(node != 0);
41
		assert(node->entry == keys);
42
43
44
45
                
		++keys;
        }

46
	rb_tree_clear(tree, 0);
47
48
49
50
51
52
53
54
55
56
57
58
59
60
	cry_free(tree);
}


static void
test_red_black_tree_removal(const_pointer list)
{
	struct RBTree* tree = rb_tree_new(cry_int_compare);
	const int* keys = cry_cast(const int*, list);
	struct RBNode* data = 0;

	assert(tree->nodes == 0);

	while(*keys > 0) {
61
		assert(rb_tree_insert(tree, keys) != 0);
62
63
64
65
66
67
68
69
70
		++keys;
	}

	assert(tree->nodes == 10);

	keys = cry_cast(const int*, list);

	// remove 3
	data = rb_tree_remove(tree, keys + 4);
71
72
	assert(data != 0 && data->entry == keys + 4);
	rb_node_free(data, 0);      
73
74
75

       	// remove 12
	data = rb_tree_remove(tree, keys + 2);
76
77
	assert(data != 0 && data->entry == keys + 2);
	rb_node_free(data, 0);      
78
79
80

       	// remove 17
	data = rb_tree_remove(tree, keys + 9);
81
82
	assert(data != 0 && data->entry == keys + 9);
	rb_node_free(data, 0);      
83
84
85

       	// remove 18
	data = rb_tree_remove(tree, keys + 7);
86
87
	assert(data != 0 && data->entry == keys + 7);
	rb_node_free(data, 0);      
88
89
90

       	// remove 15
	data = rb_tree_remove(tree, keys + 3);
91
92
	assert(data != 0 && data->entry == keys + 3);
	rb_node_free(data, 0);      
93
94
95

	// remove 16
	data = rb_tree_remove(tree, keys + 8);
96
97
	assert(data != 0 && data->entry == keys + 8);
	rb_node_free(data, 0);      
98
99
100
101
102
103
104
105
106
107
108
109
110
	
	// contains 4
	assert(rb_tree_lookup(tree, keys) != 0);

	// contains 7
	assert(rb_tree_lookup(tree, keys + 1) != 0);

	// contains 5
	assert(rb_tree_lookup(tree, keys + 5) != 0);

	// contains 14
	assert(rb_tree_lookup(tree, keys + 6) != 0);

111
	rb_tree_clear(tree, 0);
112
113
114
115
	cry_free(tree);
}


116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
static void
test_red_black_tree_traversal(const_pointer list)
{
	struct RBTree* tree = rb_tree_new(cry_int_compare);
	const int* keys = cry_cast(const int*, list);
	struct RBNode* data = 0;

	assert(tree->nodes == 0);

	while(*keys > 0) {
		assert(rb_tree_insert(tree, keys) != 0);
		++keys;
	}

	assert(tree->nodes == 10);

	keys = cry_cast(const int*, list);

        data = rb_node_first(tree);

        while(data != 0) {
                data = rb_node_next(data);
        }

        data = rb_node_last(tree);

        while(data != 0) {
                data = rb_node_prev(data);
        }


	rb_tree_clear(tree, 0);
	cry_free(tree);
}


152
153
154
155
156
157
158
159

void 
cry_test_red_black_trees(void)
{
        int keys[] = {4, 7, 12, 15, 3, 5, 14, 18, 16, 17, -1 };

	cry_unittest_run("structures.red_black_tree.insertion", test_red_black_tree_insertion, keys, 10);
	cry_unittest_run("structures.red_black_tree.removal", test_red_black_tree_removal, keys, 10);
160
161
        cry_unittest_run("structures.red_black_tree.initialization", test_red_black_tree_initialization, 0, 10);
        cry_unittest_run("structures.red_black_tree.traversal", test_red_black_tree_traversal, keys, 10);
162
}