Mercurial > data_structures

view src/bst_test.c @ 8:6605a342e8f8

find changesets by author, revision, files, or words in the commit message
bst working, but not elegant
author Eris Caffee <discordia@eldalin.com>
date Thu, 27 Sep 2012 10:57:41 -0500
parents b38243d51aea
children 68f85ffc6029
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 bool le(void *a, void * b)
11 {
12 return *((int *) a) <= *((int *) b);
13 }
14
15 bool eq(void *a, void * b)
16 {
17 return *((int *) a) == *((int *) b);
18 }
19
20 void print(void * d)
21 {
22 printf("%d\n", *((int *) d) );
23 }
24
25 void free_data(void * d)
26 {
27 free(d);
28 }
29
30 int main(int argc, char ** argv)
31 {
32 struct bst * bst = bst_new(le, eq);
33 if (NULL == bst)
34 {
35 perror("bst_new");
36 exit(EXIT_FAILURE);
37 }
38
39 ////////////////////////////////////////
40 printf ("======================\nGenerating\n");
41 //srand(time());
42 int * ip;
43 for (int i = 0 ; i < MAX_NUMS ; ++i)
44 {
45 ip = malloc(sizeof(int));
46 if (NULL == ip)
47 {
48 perror("malloc");
49 exit(EXIT_FAILURE);
50 }
51
52 *ip = rand();
53 printf("%d\n", *ip);
54 if (NULL == bst_insert(bst, ip))
55 {
56 perror("bst_insert");
57 exit(EXIT_FAILURE);
58 }
59 }
60 printf ("======================\n");
61
62
63 ////////////////////////////////////////
64 bst_walk_inorder(bst, print);
65
66 ////////////////////////////////////////
67 int i = 1;
68 int * p = (int *) bst_search(bst, &i);
69 if (NULL == p)
70 printf("%d NOT FOUND\n", i);
71 else
72 printf("%d FOUND\n", i);
73
74 i = *ip;
75 p = (int *) bst_search(bst, &i);
76 if (NULL == p)
77 printf("%d NOT FOUND\n", i);
78 else
79 printf("%d FOUND\n", i);
80
81 i = *ip;
82 p = (int *) bst_search_iterative(bst, &i);
83 if (NULL == p)
84 printf("%d NOT FOUND\n", i);
85 else
86 printf("%d FOUND\n", i);
87
88
89 int * min = bst_minimum(bst);
90 if (NULL == min)
91 printf("tree has no minimum. empty?\n");
92 else
93 printf("%d MINIMUM\n", *min);
94
95 int * max = bst_maximum(bst);
96 if (NULL == max)
97 printf("tree has no maximum. empty?\n");
98 else
99 printf("%d MAXIMUM\n", *max);
100
101 ////////////////////////////////////////
102 printf("\n\nWalking inorder with iterators\n");
103 struct bst_iterator * it = bst_begin(bst);
104 if (NULL == it)
105 {
106 perror("bst_begin");
107 exit(EXIT_FAILURE);
108 }
109 do
110 printf("%d\n", *((int *) bst_value(it)));
111 while (bst_next(it));
112 free(it);
113
114
115 ////////////////////////////////////////
116 printf("\n\nWalking reverse inorder with iterators\n");
117 it = bst_end(bst);
118 if (NULL == it)
119 {
120 perror("bst_end");
121 exit(EXIT_FAILURE);
122 }
123 do
124 printf("%d\n", *((int *) bst_value(it)));
125 while (bst_prev(it));
126 free(it);
127
128
129 ////////////////////////////////////////
130 printf("========================================\nRemoving third element\n");
131 it = bst_begin(bst);
132 if (NULL == it)
133 {
134 perror("bst_begin");
135 exit(EXIT_FAILURE);
136 }
137 bst_next(it);
138 bst_next(it);
139 void * d = bst_remove(it);
140 if (NULL == d)
141 printf("Unable to remove element!\n");
142 else
143 free(d);
144 free(it);
145 it = bst_begin(bst);
146 do
147 printf("%d\n", *((int *) bst_value(it)));
148 while (bst_next(it));
149 free(it);
150
151
152
153 ////////////////////////////////////////
154 bst_walk_inorder(bst, free_data);
155 bst_delete(bst);
156
157 exit(EXIT_SUCCESS);
158 }