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