Graphviz  2.41.20170921.2350
test_red_black_tree.c
Go to the documentation of this file.
1 /* $Id$Revision: */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /**********************************************************
5 * See the LICENSE file for copyright information. *
6 **********************************************************/
7 
8 #include "config.h"
9 
10 #include"red_black_tree.h"
11 #include<stdio.h>
12 #include<ctype.h>
13 
14 
15 /* this file has functions to test a red-black tree of integers */
16 
17 void IntDest(void* a) {
18  free((int*)a);
19 }
20 
21 
22 
23 int IntComp(const void* a,const void* b) {
24  if( *(int*)a > *(int*)b) return(1);
25  if( *(int*)a < *(int*)b) return(-1);
26  return(0);
27 }
28 
29 void IntPrint(const void* a) {
30  printf("%i",*(int*)a);
31 }
32 
33 void InfoPrint(void* a) {
34  ;
35 }
36 
37 void InfoDest(void *a){
38  ;
39 }
40 
41 int main() {
42  stk_stack* enumResult;
43  int option=0;
44  int newKey,newKey2;
45  int* newInt;
46  rb_red_blk_node* newNode;
47  rb_red_blk_tree* tree;
48 
50  while(option!=8) {
51  printf("choose one of the following:\n");
52  printf("(1) add to tree\n(2) delete from tree\n(3) query\n");
53  printf("(4) find predecessor\n(5) find successor\n(6) enumerate\n");
54  printf("(7) print tree\n(8) quit\n");
55  do option=fgetc(stdin); while(-1 != option && isspace(option));
56  option-='0';
57  switch(option)
58  {
59  case 1:
60  {
61  printf("type key for new node\n");
62  scanf("%i",&newKey);
63  newInt=(int*) malloc(sizeof(int));
64  *newInt=newKey;
65  RBTreeInsert(tree,newInt,0);
66  }
67  break;
68 
69  case 2:
70  {
71  printf("type key of node to remove\n");
72  scanf("%i",&newKey);
73  if ( ( newNode=RBExactQuery(tree,&newKey ) ) ) RBDelete(tree,newNode);/*assignment*/
74  else printf("key not found in tree, no action taken\n");
75  }
76  break;
77 
78  case 3:
79  {
80  printf("type key of node to query for\n");
81  scanf("%i",&newKey);
82  if ( ( newNode = RBExactQuery(tree,&newKey) ) ) {/*assignment*/
83  printf("data found in tree at location %i\n",(int)newNode);
84  } else {
85  printf("data not in tree\n");
86  }
87  }
88  break;
89  case 4:
90  {
91  printf("type key of node to find predecessor of\n");
92  scanf("%i",&newKey);
93  if ( ( newNode = RBExactQuery(tree,&newKey) ) ) {/*assignment*/
94  newNode=TreePredecessor(tree,newNode);
95  if(tree->nil == newNode) {
96  printf("there is no predecessor for that node (it is a minimum)\n");
97  } else {
98  printf("predecessor has key %i\n",*(int*)newNode->key);
99  }
100  } else {
101  printf("data not in tree\n");
102  }
103  }
104  break;
105  case 5:
106  {
107  printf("type key of node to find successor of\n");
108  scanf("%i",&newKey);
109  if ( (newNode = RBExactQuery(tree,&newKey) ) ) {
110  newNode=TreeSuccessor(tree,newNode);
111  if(tree->nil == newNode) {
112  printf("there is no successor for that node (it is a maximum)\n");
113  } else {
114  printf("successor has key %i\n",*(int*)newNode->key);
115  }
116  } else {
117  printf("data not in tree\n");
118  }
119  }
120  break;
121  case 6:
122  {
123  printf("type low and high keys to see all keys between them\n");
124  scanf("%i %i",&newKey,&newKey2);
125  enumResult=RBEnumerate(tree,&newKey,&newKey2);
126  while ( (newNode = StackPop(enumResult)) ) {
127  tree->PrintKey(newNode->key);
128  printf("\n");
129  }
130  free(enumResult);
131  }
132  break;
133  case 7:
134  {
135  RBTreePrint(tree);
136  }
137  break;
138  case 8:
139  {
140  RBTreeDestroy(tree);
141  return 0;
142  }
143  break;
144  default:
145  printf("Invalid input; Please try again.\n");
146  }
147  }
148  return 0;
149 }
150 
151 
152 
153 
int IntComp(const void *a, const void *b)
void InfoPrint(void *a)
rb_red_blk_node * nil
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree *tree, void *key, void *info)
void InfoDest(void *a)
void IntDest(void *a)
void IntPrint(const void *a)
void(* PrintKey)(const void *a)
rb_red_blk_node * TreeSuccessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void RBDelete(rb_red_blk_tree *tree, rb_red_blk_node *z)
stk_stack * RBEnumerate(rb_red_blk_tree *tree, void *low, void *high)
DATA_TYPE StackPop(stk_stack *theStack)
Definition: stack.c:55
rb_red_blk_tree * RBTreeCreate(int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
void RBTreePrint(rb_red_blk_tree *tree)
rb_red_blk_node * TreePredecessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void RBTreeDestroy(rb_red_blk_tree *tree)
rb_red_blk_node * RBExactQuery(rb_red_blk_tree *tree, void *q)
int main(int argc, char **argv)
Definition: dot.c:95