red_black_tree.c 2.72 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 116 117 118 119 120 121 122 123 124 125
	cry_free(tree);
}



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);
	cry_unittest_run("structures.red_black_tree.initialization", test_red_black_tree_initialization, 0, 10);
}