· 7 years ago · Dec 19, 2018, 09:32 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 //unique *temp = (unique *)malloc(n * sizeof(unique));
74 char *p;
75
76 if (root != NULL) {
77 unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
78 if (root->node_count == 1) {
79
80 p = alloc(strlen(root[count].value) + 1);
81
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 unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
94 }
95}
96
97/* A utility function to insert a new node with given key in BST */
98node* insert_node(node* node, int key, char *value) {
99 /* If the tree is empty, return a new node */
100 if (node == NULL)
101 return newNode(key, value);
102
103 // If key already exists in BST, icnrement count and return
104 if (key == node->KEY) {
105 (node->node_count)++;
106 // return node;
107 }
108
109 /* Otherwise, recur down the tree */
110 if (key < node->KEY)
111 node->left = insert_node(node->left, key, value);
112 else
113 node->right = insert_node(node->right, key, value);
114
115 /* return the (unchanged) node pointer */
116 return node;
117}
118
119/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
120map *lookup(char *s) {
121 map *np;
122
123 for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
124 if (strcmp(s, np->KEY) == 0) {
125 return np;
126 }
127 }
128 return NULL;
129}
130
131/* install function takes a pointer to a char - KEY, calendar and returns a pointer to map structure */
132map *insert_map(char* KEY, char* value) {
133 /* install: put (name, defn) in */
134 /* Install uses lookup to determine whether the KEY being installed
135 is already present. Proceeds to create a new entry or update*/
136 map *np;
137 unsigned hashval;
138
139 if ((np = lookup(KEY)) == NULL) {
140 np = (map *) malloc(sizeof (*np));
141 if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
142 return NULL;
143 }
144 hashval = hash(KEY);
145 np->next = hashtab[hashval];
146 hashtab[hashval] = np;
147 } else {
148 free((void *) np->value);
149 }
150 if ((np->value = strdup(value)) == NULL) { //map has no field value
151 return NULL;
152 }
153
154 return np;
155}
156
157/* uninstall function removes a key and calendar from table maintained by lookup and install */
158map *remove_map(char *KEY) {
159 map *found;
160
161 found = lookup(KEY);
162
163 if (found == NULL) /* not found and nothing to do */ {
164 printf("Nothing to delete.");
165 return NULL;
166 } else {
167 if (found->next != NULL) {
168 found->next = found->next->next;
169 found = found->next;
170 } else {
171 hashtab[hash(KEY)] = NULL;
172 free((void *) found);
173 }
174 }
175 return found;
176}
177
178/* simple implementation of strdup*/
179char *strdup(char *s) {
180
181 char *d = malloc(strlen(s) + 1); // Space for length plus null
182 if (d == NULL) return NULL; // No memory
183 strcpy(d, s); // Copy the characters
184 return d; // Return the new string
185}
186
187unsigned hash(char *s) {
188 /* hashing function: form hash value for string s */
189 /* used by both lookup and install*/
190 unsigned hashval;
191
192 for (hashval = 0; *s != '\0'; s++) {
193 hashval = *s + 31 * hashval;
194 }
195 return hashval % HASHSIZE;
196}
197
198// Driver Program to test above functions
199
200int main() {
201 FILE *output_stream;
202 output_stream = fopen("calendar.txt", "w+");
203 int unique_count = 0;
204 int in_count = 0;
205 char *value[100];
206 int unique_key_arr[10]; // Make dynamic
207 char *value_arr[10]; // an array of pointers [unique][chars]
208 char *KEY;
209 char *KEY_arr[10];
210
211 //unique *data = NULL;
212
213 /* READ CALENDER_OPERATIONS*/
214 /* Pass all operations down to BST*/
215
216 /* Let us create following BST. Passing values along with key */
217 node *root = NULL;
218 //node *root = (node*)malloc(sizeof(node));
219 node *test = (node*) malloc(sizeof (node));
220
221 //this is for storing commands
222 root = insert_node(root, 2082018, "C 1200 79 Meeting");
223 root = insert_node(root, 3082018, "C 1300 60 Lunchoo");
224 root = insert_node(root, 4082018, "C 1400 30 Dinnero");
225 root = insert_node(root, 5082018, "C 0600 90 Workooo");
226 root = insert_node(root, 6082018, "D 4300 30 Diyoooo");
227 root = insert_node(root, 7082018, "C 5608 30 Dinnero");
228 root = insert_node(root, 8082018, "C 1409 35 toooooo");
229 root = insert_node(root, 9082018, "C 1600 60 playooo");
230 root = insert_node(root, 9082018, "U 1800 88 eoooooo");
231
232 printf("Inorder traversal of the given tree \n");
233 inorder(root, &in_count);
234
235 printf("\nDeepest unique keys of the given tree \n");
236 unique_key(root, &unique_count, unique_key_arr, value_arr);
237 printf("\n");
238
239 printf("\nDeepest unique keys of the given tree in main\n");
240 for (int i = 0; i < unique_count; i++) {
241 printf("%d [%s]\n", unique_key_arr[i], value_arr[i]);
242 if (*value_arr[i] == 'C') { //Compare first char of pointer type
243 printf("I am Create\n");
244 } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
245 printf("I am Update\n");
246 } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
247 printf("I am Delete\n");
248 }
249 }
250
251
252 printf("\n");
253
254 /* Map is for storing calendar. This should contain the unique elements
255 * from the BST above. Based on the first char inside `value_arr`, we
256 * should insert or delete a map. Number of operations to perform
257 depends on variable `unique_count`. Use strcpy()*/
258
259
260 printf("\nDeepest unique keys to map structure\n");
261 for (int i = 0; i < unique_count; i++) {
262 char* p; //pointer for value
263 char* p2; //pointer for key
264
265 if (*value_arr[i] == 'C' || *value_arr[i] == 'U') { //Compare first char of pointer type
266
267 p = alloc(strlen(value_arr[i]) + 1); //allocate space accordingly
268 p2 = alloc(strlen(KEY) + 1);
269
270 //Convert integer to pointer to char
271 sprintf(p2, "%d", unique_key_arr[i]);
272 KEY_arr[i] = p2; //integer with unique key passed to array
273
274 strcpy(p, value_arr[i]); //copying value to pointer to char
275 value[i] = p; //p passed to value array
276
277 printf("I am here %s, %s\n", KEY_arr[i], value[i]);
278 }
279 }
280
281 map* table = (map*)malloc(sizeof(map)); //pointer to type map structure
282
283 printf("Before insert\n");
284 for (int i=0; i < unique_count; i++) { <-- Program termination
285 //table[i] = (insert_map(KEY_arr[i], value[i]));
286 strcpy(table->KEY, KEY_arr[i]);
287 strcpy(table->value, value[i]);
288 }
289
290
291 printf("\nContents of calendar (hard coded atm) \n");
292 for (int i = 0; i < unique_count; i++) {
293 //printf("%s->%s \n", table[i]->KEY, table[i]->value);
294 }
295 printf("\n");
296
297 remove_map("4082018");
298 //uninstall("key3");
299
300 map *result;
301
302 char *keys[8] = {
303 "3082018",
304 "4082018",
305 "5082018",
306 "6082018",
307 "7082018",
308 "8082018",
309 "9082018",
310 "10082018"
311 };
312
313 for (int i = 0; i < 8; i++) {
314 if ((result = lookup(keys[i])) == NULL) {
315 printf("key not found\n");
316 } else {
317 printf("%s->%s \n", result->KEY, result->value);
318 fprintf(output_stream, "%s->%s \n", result->KEY, result->value);
319 }
320 }
321 printf("\n");
322
323 return 0;
324}