8000 to_array conversion function. · fragglet/c-algorithms@436aa10 · GitHub
[go: up one dir, main page]
Skip to content

Commit 436aa10

Browse files
fraggletfragglet
committed
to_array conversion function.
1 parent cf167e5 commit 436aa10

File tree

3 files changed

+115
-6
lines changed

3 files changed

+115
-6
lines changed

‎src/avltree.c

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,7 @@ struct _AVLTreeNode {
5151
struct _AVLTree {
5252
AVLTreeNode *root_node;
5353
AVLTreeCompareFunc compare_func;
54+
int num_nodes;
5455
};
5556

5657
AVLTree *avltree_new(AVLTreeCompareFunc compare_func)
@@ -60,6 +61,7 @@ AVLTree *avltree_new(AVLTreeCompareFunc compare_func)
6061
new_tree = (AVLTree *) malloc(sizeof(AVLTree));
6162
new_tree->root_node = NULL;
6263
new_tree->compare_func = compare_func;
64+
new_tree->num_nodes = 0;
6365

6466
return new_tree;
6567
}
@@ -377,6 +379,10 @@ AVLTreeNode *avltree_insert(AVLTree *tree, void *key, void *value)
377379
node = node->parent;
378380
}
379381

382+
/* Keep track of the number of entries */
383+
384+
++tree->num_nodes;
385+
380386
return new_node;
381387
}
382388

@@ -515,6 +521,10 @@ void avltree_remove_node(AVLTree *tree, AVLTreeNode *node)
515521

516522
free(node);
517523

524+
/* Keep track of the number of nodes */
525+
526+
--tree->num_nodes;
527+
518528
/* Rebalance the tree */
519529

520530
rover = balance_startpoint;
@@ -632,3 +642,47 @@ AVLTreeNode *avltree_node_parent(AVLTreeNode *node)
632642
return node->parent;
633643
}
634644

645+
int avltree_num_entries(AVLTree *tree)
646+
{
647+
return tree->num_nodes;
648+
}
649+
650+
static void avltree_to_array_add_subtree(AVLTreeNode *subtree,
651+
void **array,
652+
int *index)
653+
{
654+
if (subtree == NULL) {
655+
return;
656+
}
657+
658+
/* Add left subtree first */
659+
660+
avltree_to_array_add_subtree(subtree->left_child, array, index);
661+
662+
/* Add this node */
663+
664+
array[*index] = subtree->key;
665+
++*index;
666+
667+
/* Finally add right subtree */
668+
669+
avltree_to_array_add_subtree(subtree->right_child, array, index);
670+
}
671+
672+
void **avltree_to_array(AVLTree *tree)
673+
{
674+
void **array;
675+
int index;
676+
677+
/* Allocate the array */
678+
679+
array = calloc(sizeof(void *), tree->num_nodes);
680+
index = 0;
681+
682+
/* Add all keys */
683+
684+
avltree_to_array_add_subtree(tree->root_node, array, &index);
685+
686+
return array;
687+
}
688+

‎src/avltree.h

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -251,6 +251,28 @@ AVLTreeNode *avltree_node_parent(AVLTreeNode *node);
251251

252252
int avltree_subtree_height(AVLTreeNode *node);
253253

254+
/**
255+
* Convert the keys in an AVL tree into a C array. This allows
256+
* the tree to be used as an ordered set.
257+
*
258+
* @param tree The tree.
259+
* @return A newly allocated C array containing all the keys
260+
* in the tree, in order. The length of the array
261+
* is equal to the number of entries in the tree
262+
* (see @ref avltree_num_entries).
263+
*/
264+
265+
void **avltree_to_array(AVLTree *tree);
266+
267+
/**
268+
* Retrieve the number of entries in the tree.
269+
*
270+
* @param tree The tree.
271+
* @return The number of key-value pairs stored in the tree.
272+
*/
273+
274+
int avltree_num_entries(AVLTree *tree);
275+
254276
#ifdef __cplusplus
255277
}
256278
#endif

‎test/test-avltree.c

Lines changed: 39 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -46,16 +46,16 @@ int find_subtree_height(AVLTreeNode *node)
4646

4747
if (node == NULL) {
4848
return 0;
49-
}
49+
}
5050

5151
left_height = find_subtree_height(avltree_node_left_child(node));
5252
right_height = find_subtree_height(avltree_node_right_child(node));
5353

5454
if (left_height > right_height) {
5555
return left_height + 1;
56-
} else {
56+
} else {
5757
return right_height + 1;
58-
}
58+
}
5959
}
6060

6161
/* Validates a subtree, returning its height */
@@ -70,7 +70,7 @@ int validate_subtree(AVLTreeNode *node)
7070

7171
if (node == NULL) {
7272
return 0;
73-
}
73+
}
7474

7575
left_node = avltree_node_left_child(node);
7676
right_node = avltree_node_right_child(node);
@@ -112,9 +112,9 @@ int validate_subtree(AVLTreeNode *node)
112112

113113
if (left_height > right_height) {
114114
return left_height + 1;
115-
} else {
115+
} else {
116116
return right_height + 1;
117-
}
117+
}
118118
}
119119

120120
void validate_tree(AVLTree *tree)
@@ -135,6 +135,7 @@ void test_avltree_new(void)
135135

136136
assert(tree != NULL);
137137
assert(avltree_root_node(tree) == NULL);
138+
assert(avltree_num_entries(tree) == 0);
138139
}
139140

140141
void test_avltree_insert_lookup(void)
@@ -155,6 +156,7 @@ void test_avltree_insert_lookup(void)
155156

156157
avltree_insert(tree, key, NULL);
157158

159+
assert(avltree_num_entries(tree) == i+1);
158160
validate_tree(tree);
159161
}
160162

@@ -232,6 +234,8 @@ void test_avltree_remove(void)
232234
assert(avltree_remove(tree, &i) != 0);
233235

234236
validate_tree(tree);
237+
238+
assert(avltree_num_entries(tree) == 1000 - (i+1));
235239
}
236240

237241
/* All entries removed, should be empty now */
@@ -240,12 +244,41 @@ void test_avltree_remove(void)
240244

241245
}
242246

247+
void test_avltree_to_array(void)
248+
{
249+
AVLTree *tree;
250+
int entries[] = { 89, 23, 42, 4, 16, 15, 8, 99, 50, 30 };
251+
int sorted[] = { 4, 8, 15, 16, 23, 30, 42, 50, 89, 99 };
252+
int num_entries = sizeof(entries) / sizeof(int);
253+
int i;
254+
int **array;
255+
256+
/* Add all entries to the tree */
257+
258+
tree = avltree_new((AVLTreeCompareFunc) int_compare);
259+
260+
for (i=0; i<num_entries; ++i) {
261+
avltree_insert(tree, &entries[i], NULL);
262+
}
263+
264+
assert(avltree_num_entries(tree) == num_entries);
265+
266+
/* Convert to an array and check the contents */
267+
268+
array = (int **) avltree_to_array(tree);
269+
270+
for (i=0; i<num_entries; ++i) {
271+
assert(*array[i] == sorted[i]);
272+
}
273+
}
274+
243275
int main(int argc, char *argv[])
244276
{
245277
test_avltree_new();
246278
test_avltree_free();
247279
test_avltree_insert_lookup();
248280
test_avltree_remove();
281+
test_avltree_to_array();
249282

250283
return 0;
251284
}

0 commit comments

Comments
 (0)
0