The LevAWC Project
 All Data Structures Files Functions Variables Typedefs Enumerations Macros Pages
demo07.c
1 /*
2  * _____
3  * ANSI / ___/
4  * / /__
5  * \___/
6  *
7  * Filename: demo07.c
8  * Author : Dan Levin
9  * Date : Fri Feb 20 11:33:43 2015
10  * Version : 0.51
11  * ---
12  * Description: Usage demo of the AVL tree ADT - in LevAWC.
13  *
14  * Revision history: (this is where you document the diffs between versions...)
15  * Date Revision
16  * 130312 Created this program the first time..
17  * 150127 Converted this program, demo7.c, to be menu-driven.
18  * 150220 Moved some utility functions from here - to file ../utils.c
19  * 150220 Source ready for version 0.5!
20  * 150318 Source ready for version 0.51
21  *
22  */
23 
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <time.h>
27 #include "avltree.h"
28 #include "utils.h"
29 
30 #ifndef OK
31 #define OK 0
32 #endif
33 
34 #ifndef TRUE
35 #define TRUE 1
36 #endif
37 
38 #ifndef FALSE
39 #define FALSE 0
40 #endif
41 
42 #define NR_OF_ITEMS 9
43 
44 /* Some string macros for the main menu... */
45 #define MAIN_MENU_ROW "--- AVL SEARCH TREE DEMO ---\nMENU: 0=Exit 1=Add_Node 2=Rem_Node 3=Search 4=Print\nSelection "
46 
47 /* FUNCTION-DECLARATIONS */
48 /* Application-specific callbacks */
49 void my_destroy(void *data);
50 void print(const void *data);
51 int my_cmp(const void *key1, const void *key2);
52 
53 /* Functions handling menu selections */
54 void rem_node(AvlTree tree);
55 void ins_node(AvlTree tree);
56 void search_node(AvlTree tree);
57 void print_tree(AvlTree tree);
58 void final_status(AvlTree tree);
59 
60 /* Misc. application functions.. */
61 void create_nodes(AvlTree tree, int nr_of_nodes);
62 /* END-OF-FUNCTION-DECLARATIONS */
63 
64 /* FUNCTION-DEFINITIONS - the rest of the program */
65 /* --- Function: void my_destroy(void *data) --- */
66 void my_destroy(void *data)
67 {
68  free(data);
69 }
70 
71 /* --- Function: void print(const void *data) --- */
72 void print(const void *data)
73 {
74  printf(" %02d", *(int *)data);
75 }
76 
77 /* --- Function: int my_cmp(const int *key1, const int *key2) --- */
78 int my_cmp(const void *key1, const void *key2)
79 {
80  return (*(int *)key1 - *(int *)key2);
81 }
82 
83 /* --- Function: void create_nodes(AvlTree tree, int nr_of_nodes) --- */
84 void create_nodes(AvlTree tree, int nr_of_nodes)
85 {
86  int i=0, *pi, retval, dupctr=0;
87 
88  do
89  {
90  pi = (int *)malloc(sizeof(int));
91  MALCHK(pi);
92 
93  *pi = rand_int(1,99);
94 
95  if ((retval = AVLTREEinsert(tree, pi)) != OK) /* Insertion failed... */
96  {
97  if (retval == 1) /* Duplicate key value.. */
98  {
99  dupctr++;
100  my_destroy(pi); /* Free node - since duplicate.. */
101  }
102  else
103  {
104  prompt_and_pause("Fatal error - bailing out..!\n");
105  AVLTREEdestroy(tree);
106  exit(-1);
107  }
108  }
109  } while (++i < nr_of_nodes);
110 
111  my_clearscrn();
112  printf("--- INITIALIZING AN AVL TREE, %d NODES, RANDOM INTEGER DATA ---\n", NR_OF_ITEMS);
113  print_tree(tree);
114  printf("\n\n%d/%d successful insertions -- %d duplicate(s) rejected...", AVLTREEsize(tree), nr_of_nodes, dupctr);
115  prompt_and_pause("\n\n");
116 }
117 
118 /* --- Function: void ins_node(AvlTree tree, int nr_of_insertions) --- */
119 void ins_node(AvlTree tree)
120 {
121  int tmp, *pi, retval;
122  char mess[BUFSIZ];
123 
124  do
125  {
126  my_clearscrn();
127  printf("--- INSERT NODE ---\n");
128  print_tree(tree);
129 
130  tmp = read_int("\nEnter integer data for node to be inserted (-1=Quit): ", 0, 0);
131 
132  if (tmp == -1)
133  break;
134 
135  pi = (int *)malloc(sizeof(int));
136  MALCHK(pi);
137 
138  *pi = tmp;
139 
140  if ((retval = AVLTREEinsert(tree, pi)) != OK) /* Insertion failed... */
141  {
142  if (retval == 1) /* Duplicate key value.. */
143  {
144  sprintf(mess, "Error: Duplicate - node %d already present..!", *pi);
145  prompt_and_pause(mess);
146  my_destroy(pi); /* Free node - since being duplicate.. */
147  }
148  else
149  {
150  prompt_and_pause("\nFatal error - bailing out..:!\n");
151  AVLTREEdestroy(tree);
152  exit(-1);
153  }
154  }
155  else
156  {
157  sprintf(mess, "Node %d will be inserted..", *(int *)pi);
158  prompt_and_pause(mess);
159  }
160  } while (TRUE);
161 }
162 
163 /* --- Function: void rem_node(AvlTree tree, int nr_of_removes) --- */
164 void rem_node(AvlTree tree)
165 {
166  int tmp, *pi, retval;
167  char mess[BUFSIZ];
168 
169  do
170  {
171  my_clearscrn();
172  printf("--- REMOVE NODE ---\n");
173  print_tree(tree);
174 
175  tmp = read_int("\nEnter data for node to be removed (-1=Quit): ", 0, 0);
176 
177  if (tmp == -1)
178  break;
179 
180  pi = &tmp;
181  if ((retval = AVLTREEremove(tree, pi)) != OK) /* Node removal failed.. */
182  {
183  /* Removal didn't work - node NOT found... */
184  if (retval == -1)
185  {
186  sprintf(mess, "Error: Node %d not found..!", *(int *)pi);
187  prompt_and_pause(mess);
188  }
189  else /* Serious failure..(-2) */
190  {
191  printf("\nFatal failure - bailing out...");
192  AVLTREEdestroy(tree);
193  exit(retval);
194  }
195  }
196  else
197  {
198  /* Removal succesful - notify user.. */
199  sprintf(mess, "Node %d will be removed(=hidden)..!", *(int *)pi);
200  prompt_and_pause(mess);
201  /* Attention - don't have to free node space here - it will be hidden.. */
202  }
203  } while (TRUE);
204 }
205 
206 /* --- Function: void search_node(AvlTree tree) --- */
207 void search_node(AvlTree tree)
208 {
209  int tmp, *pi, retval;
210  char mess[BUFSIZ];
211 
212  do
213  {
214  my_clearscrn();
215  printf("--- SEARCH NODE ---\n");
216  print_tree(tree);
217 
218  tmp = read_int("\nEnter data for node to be found (-1=Quit): ", 0, 0);
219 
220  if (tmp == -1)
221  break;
222 
223  pi = &tmp;
224 
225  if ((retval = AVLTREElookup(tree, (void **)&pi)) != OK) /* Node search failed.. */
226  {
227  /* Searching didn't work - node NOT found... */
228  if (retval == -1)
229  {
230  sprintf(mess, "Node %d NOT found..!", *(int *)pi);
231  prompt_and_pause(mess);
232  }
233  else /* Serious failure..(-2) */
234  {
235  printf("Fatal failure - bailing out...");
236  AVLTREEdestroy(tree);
237  exit(retval);
238  }
239  }
240  else
241  {
242  /* Removal succesful - notify user.. */
243  sprintf(mess, "Node %d FOUND..!", *(int *)pi);
244  prompt_and_pause(mess);
245  }
246  } while (TRUE);
247 }
248 
249 /* --- Function: void print_tree(AvlTree tree) --- */
250 void print_tree(AvlTree tree)
251 {
252  AVLTREEprint(tree, print);
253  printf("INORDER: ");
254  AVLTREEinorder(tree, print);
255 }
256 
257 /* --- Function: void final_status(Slist list) --- */
258 void final_status(AvlTree tree)
259 {
260  /* Final list status... */
261  my_clearscrn();
262  printf("--- FINAL AVL TREE STATUS---\n");
263  print_tree(tree);
264 }
265 
266 int main(void)
267 {
268  /* Declare YOUR variables here ! */
269  AvlTree mytree;
270  int menu_choice;
271 
272  srand((unsigned int)time(NULL));
273 
274  if ((mytree = AVLTREEinit(my_cmp, my_destroy)) == NULL)
275  {
276  printf("\nFatal error - bailing out...\n!");
277  AVLTREEdestroy(mytree);
278  exit(-1);
279  }
280 
281  /* Initialize - and add nodes to the table... */
282  create_nodes(mytree, NR_OF_ITEMS);
283 
284  do
285  {
286  menu_choice = menu(MAIN_MENU_ROW, 0, 4);
287 
288  switch (menu_choice)
289  {
290  case 1:
291  ins_node(mytree);
292  break;
293  case 2:
294  rem_node(mytree);
295  break;
296  case 3:
297  search_node(mytree);
298  break;
299  case 4:
300  my_clearscrn();
301  printf("--- PRINT TREE ---\n");
302  print_tree(mytree);
303  prompt_and_pause("\n\n");
304  break;
305  default:
306  final_status(mytree);
307  break;
308  }
309  }
310  while (menu_choice);
311 
312  prompt_and_pause("\n\nLet's tidy up and destroy the tree..- Bye!");
313  AVLTREEdestroy(mytree);
314 
315  return 0;
316 }