Mercurial > data_structures

view src/bst_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 68f85ffc6029
children
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4 #include <time.h>
5
6 #include "bst.h"
7
8 #define MAX_NUMS 10
9
10 void print_val(void * data)
11 {
12 printf("%d", *((int *) data));
13 }
14
15 bool le(void *a, void * b)
16 {
17 return *((int *) a) <= *((int *) b);
18 }
19
20 bool eq(void *a, void * b)
21 {
22 return *((int *) a) == *((int *) b);
23 }
24
25 void print(void * d)
26 {
27 printf("%d\n", *((int *) d) );
28 }
29
30 void free_data(void * d)
31 {
32 free(d);
33 }
34
35 int main(int argc, char ** argv)
36 {
37 int sorted[100] = {
38 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567,
39 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336,
40 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537,
41 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276,
42 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124,
43 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676,
44 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492,
45 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383,
46 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926,
47 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067,
48 };
49
50 struct bst * bst = bst_new(le, eq);
51 if (NULL == bst)
52 {
53 perror("bst_new");
54 exit(EXIT_FAILURE);
55 }
56
57 ////////////////////////////////////////
58 printf ("======================\nGenerating\n");
59 //srand(time());
60 int * ip;
61 for (int i = 0 ; i < MAX_NUMS ; ++i)
62 {
63 ip = malloc(sizeof(int));
64 if (NULL == ip)
65 {
66 perror("malloc");
67 exit(EXIT_FAILURE);
68 }
69
70 *ip = rand();
71 // *ip = sorted[i];
72 printf("%d\n", *ip);
73 if (NULL == bst_insert(bst, ip))
74 {
75 perror("bst_insert");
76 exit(EXIT_FAILURE);
77 }
78 }
79 printf ("======================\n");
80
81
82 bst_dump(bst, print_val);
83
84 ////////////////////////////////////////
85 bst_walk_inorder(bst, print);
86
87 ////////////////////////////////////////
88 int i = 1;
89 int * p = (int *) bst_search(bst, &i);
90 if (NULL == p)
91 printf("%d NOT FOUND\n", i);
92 else
93 printf("%d FOUND\n", i);
94
95 i = *ip;
96 p = (int *) bst_search(bst, &i);
97 if (NULL == p)
98 printf("%d NOT FOUND\n", i);
99 else
100 printf("%d FOUND\n", i);
101
102 i = *ip;
103 p = (int *) bst_search_iterative(bst, &i);
104 if (NULL == p)
105 printf("%d NOT FOUND\n", i);
106 else
107 printf("%d FOUND\n", i);
108
109
110 int * min = bst_minimum(bst);
111 if (NULL == min)
112 printf("tree has no minimum. empty?\n");
113 else
114 printf("%d MINIMUM\n", *min);
115
116 int * max = bst_maximum(bst);
117 if (NULL == max)
118 printf("tree has no maximum. empty?\n");
119 else
120 printf("%d MAXIMUM\n", *max);
121
122 ////////////////////////////////////////
123 printf("\n\nWalking inorder with iterators\n");
124 struct bst_iterator * it = bst_begin(bst);
125 if (NULL == it)
126 {
127 perror("bst_begin");
128 exit(EXIT_FAILURE);
129 }
130 do
131 printf("%d\n", *((int *) bst_value(it)));
132 while (bst_next(it));
133 free(it);
134
135
136 ////////////////////////////////////////
137 printf("\n\nWalking reverse inorder with iterators\n");
138 it = bst_end(bst);
139 if (NULL == it)
140 {
141 perror("bst_end");
142 exit(EXIT_FAILURE);
143 }
144 do
145 printf("%d\n", *((int *) bst_value(it)));
146 while (bst_prev(it));
147 free(it);
148
149
150 ////////////////////////////////////////
151 printf("========================================\nRemoving third element\n");
152 it = bst_begin(bst);
153 if (NULL == it)
154 {
155 perror("bst_begin");
156 exit(EXIT_FAILURE);
157 }
158 bst_next(it);
159 bst_next(it);
160 void * d = bst_remove(it);
161 if (NULL == d)
162 printf("Unable to remove element!\n");
163 else
164 free(d);
165 free(it);
166 it = bst_begin(bst);
167 do
168 printf("%d\n", *((int *) bst_value(it)));
169 while (bst_next(it));
170 free(it);
171 printf("=================\n");
172 bst_dump(bst, print_val);
173 printf("=================\n");
174
175
176
177 ////////////////////////////////////////
178 it = bst_begin(bst);
179 while (d = bst_remove(it))
180 {
181 printf("removed %d\n", *((int *) d));
182 free(d);
183 }
184 free(it);
185 printf("After deletion the size is %d\n", bst_size(bst));
186 bst_dump(bst, print_val);
187
188 bst_delete(bst);
189
190 exit(EXIT_SUCCESS);
191 }