//#pragma warning(disable:4996)
// C program to implement basic operations (search, insert and delete)
// on a BST that handles duplicates by storing count with every node
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

#define MAX_STRING_SIZE 100
#define HASHSIZE 101  /* comment here */
#define FILE_OUTPUT "calendar.txt"
#define ALLOCSIZE 1000 /*size of available space*/

static char allocbuf[ALLOCSIZE]; /* storage for alloc*/
static char *allocp = allocbuf; /* next free position*/
static struct map *hashtab[HASHSIZE]; /* pointer table */
unsigned hash(char *); /* hashing function: form hash value for string s. used by both lookup and install*/
char *strdup(char *);

char *alloc(int n) { /* return a pointer to n characters*/
    if (allocbuf + ALLOCSIZE - allocp >= n) { /*it fits*/
        allocp += n;
        return allocp - n; /*old p*/
    } else /*not enough room*/
        return 0;
}

typedef struct map { /* creating a map structure */
    struct map *next;
    char *value;
    char *KEY;
} map;

typedef struct node {
    int KEY;
    char *value;
    int node_count;
    struct node *left, *right;
    int unique_count;
} node;


// A utility function to create a new BST node

node *newNode(int KEY, char *value) {
    //Allocate a new overall structure
    node *temp = (node *) malloc(sizeof (node));

    //Copy the integer key
    temp->KEY = KEY;
    temp->value = value;

    temp->left = temp->right = NULL;
    temp->node_count = 1;
    return temp;
}

// A utility function to do inorder traversal of BST

void inorder(node *root, int *pin_count) {
    if (root != NULL) {
        inorder(root->left, pin_count);
        printf("%d(%d)\n", root->KEY, root->node_count);
        inorder(root->right, pin_count);
    }
}

/* A utility function to find deepest keys of BST */

/* This is done by extracting the key with the lowest count,
since count member of node struct gets incremented each time it is read. */
void unique_key(node *root, int *p_unique_count, int p_unique_key_arr[], char *p_value_arr[]) {
    int count = 0;
    char *p;

    if (root != NULL) {
        unique_key(root->left, p_unique_count, p_unique_key_arr, p_value_arr);
        if (root->node_count == 1) {

            if ((p = alloc(strlen(root[count].value) + 1)) == NULL) {
                return;
            } else {
                root[count].unique_count = *p_unique_count;
                p_unique_key_arr[*p_unique_count] = root[count].KEY;

                strcpy(p, root[count].value);
                p_value_arr[*p_unique_count] = p;
                //printf("%s\n",p_value_arr[*p_unique_count][*p_unique_count]);

                printf("%d(%d) -> %s %d\n", root->KEY, root->node_count, root->value, root->unique_count);
                (*p_unique_count)++;
                count++;
            }
        }
        unique_key(root->right, p_unique_count, p_unique_key_arr, p_value_arr);
    }
}

/* A utility function to insert a new node with given key in BST */
node* insert_node(node* node, int key, char *value) {
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(key, value);

    // If key already exists in BST, icnrement count and return
    if (key == node->KEY) {
        (node->node_count)++;
        //  return node;
    }

    /* Otherwise, recur down the tree */
    if (key < node->KEY)
        node->left = insert_node(node->left, key, value);
    else
        node->right = insert_node(node->right, key, value);

    /* return the (unchanged) node pointer */
    return node;
}

/* lookup function takes a pointer to char - s as an argument and returns a pointer to map structure */
map *lookup(char *s) {
    map *np;

    for (np = hashtab[hash(s)]; np != NULL; np = np->next) {
        if (strcmp(s, np->KEY) == 0) {
            return np;
        }
    }
    return NULL;
}

/* insert function takes a pointer to a char - KEY, value and returns a pointer to map structure */
map *insert_map(char* KEY, char* value) {
    /* install: put (name, defn) in */
    /* Install uses lookup to determine whether the KEY being installed
       is already present. Proceeds to create a new entry or update*/
    map *np;
    unsigned hashval;

    if ((np = lookup(KEY)) == NULL) {
        np = (map *) malloc(sizeof (*np));
        if (np == NULL || (np->KEY = strdup(KEY)) == NULL) {
            return NULL;
        }
        hashval = hash(KEY);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else {
        free((void *) np->value);
    }
    if ((np->value = strdup(value)) == NULL) { //map has no field value
        return NULL;
    }

    return np;
}

/* uninstall function removes a key and calendar from table maintained by lookup and install */
map *remove_map(char *KEY) {
    map *found;

    found = lookup(KEY);

    if (found == NULL) /* not found and nothing to do */ {
        printf("Nothing to delete.");
        return NULL;
    } else {
        if (found->next != NULL) {
            found->next = found->next->next;
            found = found->next;
        } else {
            hashtab[hash(KEY)] = NULL;
            free((void *) found);
        }
    }
    return found;
}

/* simple implementation of strdup*/
char *strdup(char *s) {

    char *d = malloc(strlen(s) + 1); // Space for length plus null
    if (d == NULL) return NULL; // No memory
    strcpy(d, s); // Copy the characters
    return d; // Return the new string
}

unsigned hash(char *s) {
    /* hashing function: form hash value for string s */
    /* used by both lookup and install*/
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++) {
        hashval = *s + 31 * hashval;
    }
    return hashval % HASHSIZE;
}

// Driver Program to test above functions

int main() {
    FILE *output_stream;
    output_stream = fopen("calendar.txt", "w+");
    int unique_count = 0;
    int in_count, count_create = 0;
    int count_delete =0;
    char *value[100];
    int unique_key_arr[10]; // Make dynamic
    char *value_arr[10]; // an array of pointers [unique][chars]
    char KEY[7];
    char *KEY_arr_create[10];
    char *KEY_arr_delete[10];

    //unique *data = NULL;

    /* READ CALENDER_OPERATIONS*/
    /* Pass all operations down to BST*/

    /* Let us create following BST.  Passing values along with key */
    node *root = NULL;
    //node *root = (node*)malloc(sizeof(node));
    node *test = (node*) malloc(sizeof (node));

    //this is for storing commands
    root = insert_node(root, 2082018, "C 1200 79 Meeting");
    root = insert_node(root, 3082018, "C 1300 60 Lunch");
    root = insert_node(root, 4082018, "C 1400 30 Dinner");
    root = insert_node(root, 5082018, "C 0600 90 Work");
    root = insert_node(root, 6082018, "D 4300 30 Diy");
    root = insert_node(root, 7082018, "C 5608 30 Dinner");
    root = insert_node(root, 8082018, "C 1409 35 to");
    root = insert_node(root, 9082018, "C 1600 60 play");
    root = insert_node(root, 9082018, "U 1800 88 e");

    printf("Inorder traversal of the given tree \n");
    inorder(root, &in_count);

    printf("\nDeepest unique keys of the given tree \n");
    unique_key(root, &unique_count, unique_key_arr, value_arr);
    printf("\n");

    printf("\nDeepest unique keys of the given tree in main\n");
    for (int i = 0; i < unique_count; i++) {
        printf("%d [%s]\n", unique_key_arr[i], value_arr[i]);
        if (*value_arr[i] == 'C') { //Compare first char of pointer type
            printf("I am Create\n");
        } else if (*value_arr[i] == 'U') { //Compare first char of pointer type
            printf("I am Update\n");
        } else if (*value_arr[i] == 'D') { //Compare first char of pointer type
            printf("I am Delete\n");
        }
    }


    printf("\n");

    /* Map is for storing calendar. This should contain the unique elements
     * from the BST above. Based on the first char inside `value_arr`, we
     * should insert or delete a map. Number of operations to perform
      depends on variable `unique_count`. Use strcpy()*/


    printf("\nDeepest unique keys to map structure\n");
    for (int i = 0; i < unique_count; i++) {
        char* p; //pointer for value
        char* p2; //pointer for key

        if (*value_arr[i] == 'C' || *value_arr[i] == 'U') { //Compare first char of pointer type

            if ((p = alloc(strlen(value_arr[count_create]) + 1)) == NULL) {
                return -1;
            } else {
                strcpy(p, value_arr[count_create]); //copying value to pointer to char
                value[count_create] = p; //p passed to value array
            }
            if ((p2 = alloc(strlen(KEY) + 1)) == NULL) {
                return -1;
            } else {
                //Convert integer to pointer to char
                sprintf(p2, "%d", unique_key_arr[count_create]);
                KEY_arr_create[count_create] = p2; //integer with unique key passed to array
            }

            printf("I am here %s, %s\n", KEY_arr_create[count_create], value[count_create]);
            count_create++;
        }
        else {
            if ((p2 = alloc(strlen(KEY) + 1)) == NULL) {
                return -1;
            } else {
                //Convert integer to pointer to char
                sprintf(p2, "%d", unique_key_arr[count_delete]);
                KEY_arr_delete[count_delete] = p2; //integer with unique key passed to array
                count_delete++;
            }
        }
    }

    map * table[10]; //pointer to type map structure

    printf("\nBefore insert CREATE %d\n", count_create);
    for (int i = 0; i < count_create; i++) {
        printf("CREATE %s, %s\n",KEY_arr_create[i], value[i]);
        //table[i] = insert_map(KEY_arr_create[i], value[i]);
    }

    printf("\nBefore insert DELETE %d\n", count_delete);
    for (int i = 0; i < count_delete; i++) {
        printf("DELETE %s, %s\n",KEY_arr_delete[i], value[i]);
        //table[i] = insert_map(KEY_arr_delete[i], value[i]);
    }

    printf("\nContents of calendar (hard coded atm) \n");
    for (int i = 0; i < unique_count; i++) {
        //printf("%s->%s \n", table[i]->KEY, table[i]->value);
    }
    printf("\n");

    remove_map("4082018");
    //uninstall("key3");

    map *result;

    char *keys[8] = {
        "3082018",
        "4082018",
        "5082018",
        "6082018",
        "7082018",
        "8082018",
        "9082018",
        "10082018"
    };

    for (int i = 0; i < 8; i++) {
        if ((result = lookup(keys[i])) == NULL) {
            printf("key not found\n");
        } else {
            printf("%s->%s \n", result->KEY, result->value);
            fprintf(output_stream, "%s->%s \n", result->KEY, result->value);
        }
    }
    printf("\n");

    return 0;
}