· 7 years ago · Dec 07, 2018, 08:16 PM
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
12static struct map *hashtab[HASHSIZE]; /* pointer table */
13unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
14char *strdup(char *);
15
16typedef struct map { /* creating a map structure */
17 struct map *next;
18 char *KEY;
19 char *duration;
20 char *time;
21 char *description;
22 //struct Value value;
23}map;
24
25typedef struct node {
26 int KEY;
27 char *value;
28 int node_count;
29 struct node *left, *right;
30 int unique_count;
31} node;
32
33// A utility function to create a new BST node
34
35node *newNode(int KEY, char *value)
36{
37 //Allocate a new overall structure
38 struct node *temp = (struct node *)malloc(sizeof(struct node));
39
40 //Copy the integer key
41 temp->KEY = KEY;
42
43 temp->value = (char *)malloc(sizeof(10));
44 //temp->value, value);
45
46 temp->value = value;
47
48 temp->left = temp->right = NULL;
49 temp->node_count = 1;
50 return temp;
51}
52
53// A utility function to do inorder traversal of BST
54void inorder(node *root, int *pin_count)
55{
56 if (root != NULL)
57 {
58 inorder(root->left, pin_count);
59 printf("key is %d(%d) and count is %d\n", root->KEY, root->node_count, (*pin_count)++);
60 inorder(root->right, pin_count);
61 }
62}
63
64/* A utility function to find deepest keys of BST */
65/* This is done by extracting the key with the lowest count,
66since count member of node struct gets incremented each time it is read. */
67void unique_key(node *root, int *p_unique_count, int p_unique_arr[], char *p_value_arr[]) {
68 int count = 0;
69 //unique *temp = (unique *)malloc(n * sizeof(unique));
70
71 if (root != NULL)
72 {
73 unique_key(root->left, p_unique_count, p_unique_arr, p_value_arr);
74 if (root->node_count == 1) {
75
76 root[count].unique_count = *p_unique_count;
77 p_unique_arr[*p_unique_count] = root[count].KEY;
78 printf("%s\n ", root[count].value);
79 strcpy(p_value_arr[*p_unique_count],root[count].value); // error here
80
81 printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
82 (*p_unique_count)++;
83 count++;
84 }
85 unique_key(root->right, p_unique_count, p_unique_arr, p_value_arr);
86 }
87}
88
89/* A utility function to insert a new node with given key in BST */
90node* insert_node(node* node, int key, char *value)
91{
92 /* If the tree is empty, return a new node */
93 if (node == NULL)
94 return newNode(key,value);
95
96 // If key already exists in BST, icnrement count and return
97 if (key == node->KEY)
98 {
99 (node->node_count)++;
100 // return node;
101 }
102
103 /* Otherwise, recur down the tree */
104 if (key < node->KEY)
105 node->left = insert_node(node->left, key, value);
106 else
107 node->right = insert_node(node->right, key, value);
108
109 /* return the (unchanged) node pointer */
110 return node;
111}
112
113/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
114map *lookup(char *s) {
115 map *np;
116
117 for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
118 if (strcmp(s, np->KEY) == 0) {
119 return np;
120 }
121 }
122 return NULL;
123}
124
125/* install function takes a pointer to a char - KEY, calendar and returns a pointer to map structure */
126map *insert_map(char *KEY, char *time, char *duration, char *description) {
127 /* install: put (name, defn) in */
128 /* Install uses lookup to determine whether the KEY being installed
129 is already present. Proceeds to create a new entry or update*/
130 map *np;
131 unsigned hashval;
132
133 if ((np = lookup(KEY)) == NULL) {
134 np = (map *) malloc(sizeof(*np));
135 if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
136 return NULL;
137 }
138 hashval = hash(KEY);
139 np->next = hashtab[hashval];
140 hashtab[hashval] = np;
141 }
142 else {
143 free((void *)np->time); //type cast cannot convert from 'Value' to 'Value*'
144 free((void *)np->description);
145 free((void *)np->duration);
146 }
147 if ((np->time = strdup(time)) == NULL) { //map has no field value
148 return NULL;
149 }
150 if ((np->description = strdup(description)) == NULL) { //map has no field value
151 return NULL;
152 }
153 if ((np->duration = strdup(duration)) == NULL) { //map has no field value
154 return NULL;
155 }
156
157 return np;
158}
159
160/* uninstall function removes a key and calendar from table maintained by lookup and install */
161map *remove_map(char *KEY) {
162 map *found;
163
164 found = lookup(KEY);
165
166 if (found == NULL) /* not found and nothing to do */ {
167 printf("Nothing to delete.");
168 return NULL;
169 }
170 else {
171 if (found->next != NULL) {
172 found->next = found->next->next;
173 found = found->next;
174 }
175 else {
176 hashtab[hash(KEY)] = NULL;
177 free((void *)found);
178 }
179 }
180 return found;
181}
182
183/* simple implementation of strdup*/
184char *strdup(char *s) {
185
186 char *d = malloc(strlen(s) + 1); // Space for length plus null
187 if (d == NULL) return NULL; // No memory
188 strcpy(d, s); // Copy the characters
189 return d; // Return the new string
190}
191
192unsigned hash(char *s) {
193 /* hashing function: form hash value for string s */
194 /* used by both lookup and install*/
195 unsigned hashval;
196
197 for (hashval = 0; *s != '\0'; s++) {
198 hashval = *s + 31 * hashval;
199 }
200 return hashval % HASHSIZE;
201}
202
203// Driver Program to test above functions
204int main()
205{
206 FILE *output_stream;
207 output_stream = fopen("calendar.txt", "w+");
208 int unique_count = 0;
209 int in_count =0;
210 int *data;
211 int unique_arr[7]; //dynamic
212 char *value_arr[10]; // an array of pointers
213
214 //unique *data = NULL;
215
216 /* READ CALENDER_OPERATIONS*/
217 /* Pass all operations down to BST*/
218
219 /* Let us create following BST. Passing values along with key */
220 node *root = NULL;
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 Diyooro");
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 eveoooo");
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_arr, value_arr);
238 printf("\n");
239
240 for(int i = 0; i < 7; i++) {
241 //printf("%d -> %s %s %s %s \n", data[i].KEY, data[i].command, data[i].time, data[i].duration, data[i].description);
242 printf("%d %s\n", unique_arr[i], value_arr[i]);
243 //free(data);
244 }
245 printf("\n");
246
247 //Map is for storing calendar
248 map *table[8] = {
249 //This is equivalent to create
250 (insert_map("2082018", "1200", "79", "Meeting")), /* No leading 0's*/
251 (insert_map("3082018", "1300", "60", "Lunch" )),
252 (insert_map("4082018", "1400", "30", "Dinner")),
253 (insert_map("5082018", "0600", "90", "Work" )),
254 (insert_map("6082018", "1200", "79", "Party")),
255 (insert_map("7082018", "1300", "60", "Event")),
256 (insert_map("8082018", "1400", "30", "Training")),
257 (insert_map("9082018", "0600", "90", "Study"))
258 };
259
260 int i;
261
262 for (i = 0; i < 8; i++) {
263 printf("%s->%s %s %s\n", table[i]->KEY, table[i]->time, table[i]->duration, table[i]->description);
264 }
265 printf("\n");
266
267 remove_map("4082018");
268 //uninstall("key3");
269
270 map *result;
271
272 char *keys[8] = {
273 "3082018",
274 "4082018",
275 "5082018",
276 "6082018",
277 "7082018",
278 "8082018",
279 "9082018",
280 "10082018"
281 };
282
283 for (i = 0; i < 8; i++) {
284 if ((result = lookup(keys[i])) == NULL) {
285 printf("key not found\n");
286 }
287 else {
288 printf("%s->%s %s %s\n", result->KEY, result->time, result->duration, result->description);
289 fprintf(output_stream, "%s->%s %s %s\n", result->KEY, result->time, result->duration, result->description);
290 }
291 }
292 printf("\n");
293
294 return 0;
295}