Mercurial > data_structures

view src/rbtree_test.c @ 12:d359966ed8de

find changesets by author, revision, files, or words in the commit message
Added trie
author Eris Caffee <discordia@eldalin.com>
date Mon, 01 Oct 2012 15:50:30 -0500
parents 8b09943f1a70
children
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4
5 #include "rbtree.h"
6
7 void print_val(void * data)
8 {
9 printf("%d", *((int *) data));
10 }
11
12 void print_val2(void * data)
13 {
14 printf("%d\n", *((int *) data));
15 }
16
17 bool le(void * a, void * b)
18 {
19 return *((int *) a) <= *((int *) b);
20 }
21
22 bool eq(void * a, void * b)
23 {
24 return *((int *) a) == *((int *) b);
25 }
26
27 #define MAX_NUMS 128
28
29 int main (int argc, char ** argv)
30 {
31 int sorted[100] = {
32 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567,
33 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336,
34 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537,
35 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276,
36 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124,
37 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676,
38 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492,
39 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383,
40 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926,
41 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067,
42 };
43
44 struct rbtree * rbtree = rbtree_new(le, eq);
45 if (NULL == rbtree)
46 {
47 perror("rbtree_new");
48 exit(EXIT_FAILURE);
49 }
50
51 for (int i = 0; i < MAX_NUMS; ++i)
52 {
53 int * ip = malloc(sizeof(int));
54 if (NULL == ip)
55 {
56 perror("malloc");
57 exit(EXIT_FAILURE);
58 }
59 *ip = rand();
60 // Be sure to set MAX_NUMS = 100 if you want to use the sorted array
61 // *ip = sorted[i];
62 int * ip2;
63 if (NULL == (ip2 = rbtree_insert(rbtree, ip)))
64 {
65 printf("rbtree_insert failed\n");
66 free(ip);
67 }
68 printf("inserting %d\n", *ip2);
69 }
70
71
72 // print the tree structure
73 rbtree_dump(rbtree, print_val);
74 fprintf(stderr, "black depth is %u\n", rbtree_black_depth(rbtree));
75
76 // Print the tree in value order
77 struct rbtree_iterator * it;
78 struct rbtree_iterator * next;
79 for (next = it = rbtree_begin(rbtree); NULL != next; next = rbtree_next(it))
80 printf("%d\n", *((int *) rbtree_value(it)));
81 free(it);
82
83 // Free the whole tree
84 void * d;
85 it = rbtree_begin(rbtree);
86 while (d = rbtree_remove(it))
87 {
88 printf("removed %d\n", *((int *) d));
89 free(d);
90 }
91 free(it);
92 printf("After deletion the size is %u\n", rbtree_size(rbtree));
93 rbtree_dump(rbtree, print_val);
94
95
96
97 rbtree_delete(rbtree);
98
99
100 //////////////////////////////////////////
101 // New tree to test beadth first walk
102
103 printf("Walking a tree breadth first\n");
104 rbtree = rbtree_new(le, eq);
105 if (NULL == rbtree)
106 {
107 perror("rbtree_new");
108 exit(EXIT_FAILURE);
109 }
110
111 for (int i = 0; i < 10; ++i)
112 {
113 int * ip = malloc(sizeof(int));
114 if (NULL == ip)
115 {
116 perror("malloc");
117 exit(EXIT_FAILURE);
118 }
119 *ip = rand();
120 int * ip2;
121 if (NULL == (ip2 = rbtree_insert(rbtree, ip)))
122 {
123 printf("rbtree_insert failed\n");
124 free(ip);
125 }
126 }
127
128
129 // print the tree structure
130 rbtree_dump(rbtree, print_val);
131 rbtree_walk_breadth_first(rbtree, print_val2);
132
133 // Free the whole tree
134 it = rbtree_begin(rbtree);
135 while (d = rbtree_remove(it))
136 free(d);
137 free(it);
138 rbtree_delete(rbtree);
139
140 exit(EXIT_SUCCESS);
141 }