#include <stdio.h>
#include <stdlib.h>

typedef int trieValueT;

typedef struct trieNodeTag {
    char key;
    int words;
    int prefix;
    trieValueT value;
    struct trieNodeTag *next, *children;
} trieNodeT;

typedef struct trieCDT {
    trieNodeT *root;
} trieCDT;

typedef struct trieCDT *trieADT;

// Functions
void trieCreate(trieCDT *trie);
void trieAdd(trieNodeT *trie, char *key, int value);
trieNodeT* addChild(char key);
int trieIsMember(trieCDT trie, char keys[]);
int totalStringsWithPrefix(trieCDT trie, char keys[]);
void trieDestroy(trieNodeT *root);
void test1();
void startTesting();
void startTestingFromFile(char** stdip_v);

// To enable debug messages uncomment #define
#define TEST 1
// To test trie by providing input from file, uncomment 'TESTFROMFILE'
// Compile code and while executing provide file name at command line
// For e.g. > ./a.out ipFile.txt
//
//#define TESTFROMFILE 1
//
// To enable debug messages uncomment 'DEBUG'
//#define DEBUG 1

#ifdef DEBUG
#  define D(x) x
#else
#  define D(x)
#endif

int main(int argc, char* argv[])
{
    #ifdef TEST
        startTesting();
    #endif

    #ifdef TESTFROMFILE
        startTestingFromFile(argv);
    #endif

    return 0;
}

// Create root node of trie
void trieCreate(trieCDT *trie)
{
    trie->root = (trieNodeT*)calloc(1,sizeof(trieNodeT));

    if (trie->root == NULL) {
    printf("Can not alloc memory\n");
    return;
    }

    trie->root->key = '\0';
    trie->root->value = -1;
    trie->root->next = NULL;
    trie->root->children = NULL;
}

// This is recursive function for adding node in trie
// It covers 3 cases
// Case 1: When only root node is present in a trie. In this
//         case keep on adding node one level after another.
//
//         If input given is "Good" and if 'G' is not found then
//         insert 'G' and return 'G' node from where next insertion
//         has to be done as we have already found there is no
//         other 'G' exist.
//
// Case 2: When matching key node is already found return the matching
//         node and increment key
//
// Case 3: When key does not match to existing children i.e. for
//         "abcd", "abef" and "abgh"
//         .  ----> root
//         |
//         a
//         |
//         b
//         |
//         c ===> e ===> g        (LL, children of b)
//         |      |      |
//         d      f      h


void trieAdd(trieNodeT* trie, char *key, int value) {

    // Get root of children
    if (key == NULL) {
    return;
    } else if (trie->children == NULL && trie->next == NULL) {

        // Case 1
    trieNodeT* child = addChild(*key);
    trie->children = child;

    if (*key == '\0') {
        child->value = value;
        child->words++;
        return;
    }

    return trieAdd(child, ++key, value);
    }

    trieNodeT* level = trie->children;
    trieNodeT* current;
    for (current = level; current != NULL; current = current->next) {

    // Case 2
    if (current->key == *key) {
        current->prefix++;

        if (*key == '\0') {
        current->words++;
        return;
        }
        return trieAdd(current, ++key, value);
    }

    // This is last element in LL and key is not found
    // For e.g. for "abc" and "abd", c and d should be
    // child of b.
    // Since, c != d, Append d to c in LL signifying they
    // are both child of 'b' and are on same level
    //
    // Case 3
    if (current->next == NULL) {
        //Add key
        trieNodeT* child = addChild(*key);
        current->next = child;

        if (*key == '\0') {
            child->words++;
        child->value = value;
        return;
        }

        return trieAdd(child, ++key, value);
    }
    }
}

trieNodeT* addChild(char key)
{
    trieNodeT* child = (trieNodeT*)calloc(1,sizeof(trieNodeT));

    if (child == NULL) {
    printf("Can not alloc memory\n");
    return NULL;
    }
    child->key = key;
    child->value = -1;
    child->next = NULL;
    child->children = NULL;
    child->prefix = 1;
    child->words = 0;

    return child;
}

int totalStringsWithPrefix(trieCDT trie, char keys[])
{
    trieNodeT *level = trie.root->children;

    while (keys != NULL) {
    trieNodeT *found = NULL;
    trieNodeT *current;

    for (current = level; current != NULL; current = current->next) {
        if (current->key == *keys) {
        found = current;
        break;
        }
    }

    if (found == NULL) {
        return 0;
    } else if (*(keys + 1)  == '\0') {
        return found->prefix;
    }
    level = found -> children;
    keys++;
    }

    return 0;
}

int trieIsMember(trieCDT trie, char keys[])
{
    trieNodeT *level = trie.root->children;

    while (keys != NULL) {
    trieNodeT *found = NULL;
    trieNodeT *current;

    for (current = level; current != NULL; current = current->next) {
        if (current->key == *keys) {
        found = current;
        break;
        }
    }

    if (found == NULL) {
        return 0;
    } else if (*keys == '\0') {
        return 1;
    }
    level = found -> children;
    keys++;
    }

    return 0;
}

void trieDestroy(trieNodeT * root)
{
    if (root->children == NULL && root->next == NULL) {
        D(printf("Destroying %d\n", root->value));
    free (root);
    return;
    }

    // If root have next and children free them first
    if (root->next != NULL) {
    trieDestroy(root->next);
    }

    if (root->children != NULL) {
    trieDestroy(root->children);
    }

#ifdef DEBUG
    if (root->key != '\0') {
    printf("Destroying %c\n", root->key);
    } else {
    printf("Destroying Root %d\n", root->value);
    }
#endif

    free (root);
}

void test1()
{
    char s[] = "ABCD";
    char s1[] = "ABCDE";
    int i = 0;
    trieCDT trie;
    trieCreate(&trie);
    trieAdd(trie.root, "ABCD", 20);
    trieAdd(trie.root, "ABCDE", 30);

    if (trieIsMember(trie, s)) {
    printf("Found member 'ABCD'\n");
    }

    i = totalStringsWithPrefix(trie, "ABC");
    printf("Total words with prefix 'ABC' %d\n", i);

    trieDestroy(trie.root);
}

void startTesting()
{
    test1();
}

void startTestingFromFile(char** stdip_v)
{
    FILE *fp = NULL;
    char key[50];
    trieCDT trie;
    int i = 0;

    fp = fopen(stdip_v[1], "r");
    if(fp == NULL) {
    fprintf(stderr, "Can not read file!!\n");
    return;
    }

    trieCreate(&trie);

    while(fscanf(fp, "%s", key) != EOF) {
    trieAdd(trie.root, key, i);
    i++;

    if(!trieIsMember(trie, key)) {
        printf("Key '%s' NOT found in trie\n", key);
    }
    }

    printf("Total words inserted in trie %d\n", i);

    i = totalStringsWithPrefix(trie, "Abe");

    printf("Total prefixs with 'Abe' %d\n", i);

    trieDestroy(trie.root);
}