· 7 years ago · Dec 19, 2018, 10:42 AM
1//#pragma warning(disable:4996)
2// C program to implement basic operations (search, insert and delete)
3// on a BST that handles duplicates by storing count with every node
4#include<stdio.h>
5#include<stdlib.h>
6#include <string.h>
7
8#define MAX_STRING_SIZE 100
9#define HASHSIZE 101 /* comment here */
10#define FILE_OUTPUT "calendar.txt"
11#define ALLOCSIZE 10000 /*size of available space*/
12
13static char allocbuf[ALLOCSIZE]; /* storage for alloc*/
14static char *allocp = allocbuf; /* next free position*/
15static struct map *hashtab[HASHSIZE]; /* pointer table */
16unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
17char *strdup(char *);
18
19char *alloc(int n) { /* return a pointer to n characters*/
20 if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
21 allocp += n;
22 return allocp - n; /*old p*/
23 } else /*not enough room*/
24 return 0;
25}
26
27typedef struct map { /* creating a map structure */
28 struct map *next;
29 char *value;
30 char *KEY;
31} map;
32
33typedef struct node {
34 int KEY;
35 char *value;
36 int node_count;
37 struct node *left, *right;
38 int unique_count;
39} node;
40
41
42// A utility function to create a new BST node
43
44node *newNode(int KEY, char *value) {
45 //Allocate a new overall structure
46 node *temp = (node *) malloc(sizeof (node));
47
48 //Copy the integer key
49 temp->KEY = KEY;
50 temp->value = value;
51
52 temp->left = temp->right = NULL;
53 temp->node_count = 1;
54 return temp;
55}
56
57// A utility function to do inorder traversal of BST
58
59void inorder(node *root, int *pin_count) {
60 if (root != NULL) {
61 inorder(root->left, pin_count);
62 printf("%d(%d)\n", root->KEY, root->node_count);
63 inorder(root->right, pin_count);
64 }
65}
66
67/* A utility function to find deepest keys of BST */
68
69/* This is done by extracting the key with the lowest count,
70since count member of node struct gets incremented each time it is read. */
71void unique_key(node *root, int *p_unique_count, int p_unique_key_arr[], char *p_value_arr[]) {
72 int count = 0;
73 char *p;
74
75 if (root != NULL) {
76 unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
77 if (root->node_count == 1) {
78
79 if ((p = alloc(strlen(root[count].value) + 1)) == NULL) {
80 return;
81 } else {
82 root[count].unique_count = *p_unique_count;
83 p_unique_key_arr[*p_unique_count] = root[count].KEY;
84
85 strcpy(p, root[count].value);
86 p_value_arr[*p_unique_count] = p;
87 //printf("%s\n",p_value_arr[*p_unique_count][*p_unique_count]);
88
89 printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
90 (*p_unique_count)++;
91 count++;
92 }
93 }
94 unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
95 }
96}
97
98/* A utility function to insert a new node with given key in BST */
99node* insert_node(node* node, int key, char *value) {
100 /* If the tree is empty, return a new node */
101 if (node == NULL)
102 return newNode(key, value);
103
104 // If key already exists in BST, icnrement count and return
105 if (key == node->KEY) {
106 (node->node_count)++;
107 // return node;
108 }
109
110 /* Otherwise, recur down the tree */
111 if (key < node->KEY)
112 node->left = insert_node(node->left, key, value);
113 else
114 node->right = insert_node(node->right, key, value);
115
116 /* return the (unchanged) node pointer */
117 return node;
118}
119
120/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
121map *lookup(char *s) {
122 map *np;
123
124 for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
125 if (strcmp(s, np->KEY) == 0) {
126 return np;
127 }
128 }
129 return NULL;
130}
131
132/* insert function takes a pointer to a char - KEY, value and returns a pointer to map structure */
133map *insert_map(char* KEY, char* value) {
134 /* install: put (name, defn) in */
135 /* Install uses lookup to determine whether the KEY being installed
136 is already present. Proceeds to create a new entry or update*/
137 map *np;
138 unsigned hashval;
139
140 if ((np = lookup(KEY)) == NULL) {
141 np = (map *) malloc(sizeof (*np));
142 if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
143 return NULL;
144 }
145 hashval = hash(KEY);
146 np->next = hashtab[hashval];
147 hashtab[hashval] = np;
148 } else {
149 free((void *) np->value);
150 }
151 if ((np->value = strdup(value)) == NULL) { //map has no field value
152 return NULL;
153 }
154
155 return np;
156}
157
158/* uninstall function removes a key and calendar from table maintained by lookup and install */
159map *remove_map(char *KEY) {
160 map *found;
161
162 found = lookup(KEY);
163
164 if (found == NULL) /* not found and nothing to do */ {
165 printf("Nothing to delete.");
166 return NULL;
167 } else {
168 if (found->next != NULL) {
169 found->next = found->next->next;
170 found = found->next;
171 } else {
172 hashtab[hash(KEY)] = NULL;
173 free((void *) found);
174 }
175 }
176 return found;
177}
178
179/* simple implementation of strdup*/
180char *strdup(char *s) {
181
182 char *d = malloc(strlen(s) + 1); // Space for length plus null
183 if (d == NULL) return NULL; // No memory
184 strcpy(d, s); // Copy the characters
185 return d; // Return the new string
186}
187
188unsigned hash(char *s) {
189 /* hashing function: form hash value for string s */
190 /* used by both lookup and install*/
191 unsigned hashval;
192
193 for (hashval = 0; *s != '\0'; s++) {
194 hashval = *s + 31 * hashval;
195 }
196 return hashval % HASHSIZE;
197}
198
199// Driver Program to test above functions
200
201int main() {
202 FILE *output_stream;
203 output_stream = fopen("calendar.txt", "w+");
204 int unique_count = 0;
205 int in_count = 0;
206 char *value[100];
207 int unique_key_arr[10]; // Make dynamic
208 char *value_arr[10]; // an array of pointers [unique][chars]
209 char *KEY;
210 char *KEY_arr[10];
211
212 //unique *data = NULL;
213
214 /* READ CALENDER_OPERATIONS*/
215 /* Pass all operations down to BST*/
216
217 /* Let us create following BST. Passing values along with key */
218 node *root = NULL;
219 //node *root = (node*)malloc(sizeof(node));
220 node *test = (node*) malloc(sizeof (node));
221
222 //this is for storing commands
223 root = insert_node(root, 2082018, "C 1200 79 Meeting");
224 root = insert_node(root, 3082018, "C 1300 60 Lunchoo");
225 root = insert_node(root, 4082018, "C 1400 30 Dinnero");
226 root = insert_node(root, 5082018, "C 0600 90 Workooo");
227 root = insert_node(root, 6082018, "D 4300 30 Diyoooo");
228 root = insert_node(root, 7082018, "C 5608 30 Dinnero");
229 root = insert_node(root, 8082018, "C 1409 35 toooooo");
230 root = insert_node(root, 9082018, "C 1600 60 playooo");
231 root = insert_node(root, 9082018, "U 1800 88 eoooooo");
232
233 printf("Inorder traversal of the given tree \n");
234 inorder(root, &in_count);
235
236 printf("\nDeepest unique keys of the given tree \n");
237 unique_key(root, &unique_count, unique_key_arr, value_arr);
238 printf("\n");
239
240 printf("\nDeepest unique keys of the given tree in main\n");
241 for (int i = 0; i < unique_count; i++) {
242 printf("%d [%s]\n", unique_key_arr[i], value_arr[i]);
243 if (*value_arr[i] == 'C') { //Compare first char of pointer type
244 printf("I am Create\n");
245 } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
246 printf("I am Update\n");
247 } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
248 printf("I am Delete\n");
249 }
250 }
251
252
253 printf("\n");
254
255 /* Map is for storing calendar. This should contain the unique elements
256 * from the BST above. Based on the first char inside `value_arr`, we
257 * should insert or delete a map. Number of operations to perform
258 depends on variable `unique_count`. Use strcpy()*/
259
260
261 printf("\nDeepest unique keys to map structure\n");
262 for (int i = 0; i < unique_count; i++) {
263 char* p; //pointer for value
264 char* p2; //pointer for key
265
266 if (*value_arr[i] == 'C' || *value_arr[i] == 'U') { //Compare first char of pointer type
267
268 if ((p = alloc(strlen(value_arr[i]) + 1)) == NULL) {
269 return -1;
270 } else {
271 strcpy(p, value_arr[i]); //copying value to pointer to char
272 value[i] = p; //p passed to value array
273 }
274 if ((p2 = alloc(strlen(KEY) + 1)) == NULL) {
275 return -1;
276 } else {
277 //Convert integer to pointer to char
278 sprintf(p2, "%d", unique_key_arr[i]);
279 KEY_arr[i] = p2; //integer with unique key passed to array
280 }
281
282 printf("I am here %s, %s\n", KEY_arr[i], value[i]);
283 }
284 }
285
286 map * table[10]; //pointer to type map structure
287
288 printf("Before insert %d\n", unique_count);
289 for (int i = 0; i < 8; i++) {
290 printf("%s, %s\n",KEY_arr[i], value[i]);
291 table[i] = insert_map(KEY_arr[i], value[i]);
292 }
293 printf("Hello1\n"); //<-- Program execution does not reach here
294
295 //This is equivalent to create
296 // (insert_map(KEY, value[0])
297 // (insert_map("2082018", "1200 79 Meeting")), /* No leading 0's*/
298 // (insert_map("3082018", "1300 60 Lunch" )),
299 // (insert_map("4082018", "1400 30 Dinner")),
300 // (insert_map("5082018", "0600 90 Work" )),
301 // (insert_map("6082018", "1200 79 Party")),
302 // (insert_map("7082018", "1300 60 Event")),
303 // (insert_map("8082018", "1400 30 Training")),
304 // (insert_map("9082018", "0600 90 Study"))
305 // };
306
307 printf("\nContents of calendar (hard coded atm) \n");
308 for (int i = 0; i < unique_count; i++) {
309 //printf("%s->%s \n", table[i]->KEY, table[i]->value);
310 }
311 printf("\n");
312
313 remove_map("4082018");
314 //uninstall("key3");
315
316 map *result;
317
318 char *keys[8] = {
319 "3082018",
320 "4082018",
321 "5082018",
322 "6082018",
323 "7082018",
324 "8082018",
325 "9082018",
326 "10082018"
327 };
328
329 for (int i = 0; i < 8; i++) {
330 if ((result = lookup(keys[i])) == NULL) {
331 printf("key not found\n");
332 } else {
333 printf("%s->%s \n", result->KEY, result->value);
334 fprintf(output_stream, "%s->%s \n", result->KEY, result->value);
335 }
336 }
337 printf("\n");
338
339 return 0;
340}