red_black_tree.c 2.77 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
#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);

	rb_tree_clear(tree, 0, 0);
	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) {
		assert(rb_tree_insert(tree, keys, cry_cast(int*, keys)) != 0);
		++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);
		assert(node->key == keys);
                
		++keys;
        }

	rb_tree_clear(tree, 0, 0);
	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) {
		assert(rb_tree_insert(tree, keys, cry_cast(int*, keys)) != 0);
		++keys;
	}

	assert(tree->nodes == 10);

	keys = cry_cast(const int*, list);

	// remove 3
	data = rb_tree_remove(tree, keys + 4);
	assert(data != 0 && data->key == keys + 4);
	rb_node_free(data, 0, 0);      

       	// remove 12
	data = rb_tree_remove(tree, keys + 2);
	assert(data != 0 && data->key == keys + 2);
	rb_node_free(data, 0, 0);      

       	// remove 17
	data = rb_tree_remove(tree, keys + 9);
	assert(data != 0 && data->key == keys + 9);
	rb_node_free(data, 0, 0);      

       	// remove 18
	data = rb_tree_remove(tree, keys + 7);
	assert(data != 0 && data->key == keys + 7);
	rb_node_free(data, 0, 0);      

       	// remove 15
	data = rb_tree_remove(tree, keys + 3);
	assert(data != 0 && data->key == keys + 3);
	rb_node_free(data, 0, 0);      

	// remove 16
	data = rb_tree_remove(tree, keys + 8);
	assert(data != 0 && data->key == keys + 8);
	rb_node_free(data, 0, 0);      
	
	// 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);

	rb_tree_clear(tree, 0, 0);
	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);
}