// Arup Guha
// 11/5/2015
// An example trie (just insertion) written in class (COP 3502)
// Edited on 7/1/2015 in lecture to remove inefficient calls to strlen.
// and added wrapper functions for search, insert.

/*** Added code for COP 3502H Spr 24 Exam 2 Question 10 ***/

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

typedef struct trie {
    int isWord;
    struct trie* next[26];
} trie;


// For inserting.
void insert(struct trie* tree, char word[]);
void insertRec(struct trie* tree, char word[], int k, int wordlen);

// For searching.
int search(struct trie* tree, char word[]) ;
int searchRec(struct trie* tree, char word[], int k, int wordlen);

// Start, printing, freeing.
struct trie* init();
void printAll(struct trie* tree, char cur[]) ;
void freeDictionary(struct trie* tree);

int numfit(struct trie* root, char* mold);
int numfitrec(struct trie* root, char* mold, int k, int n) ;

int main(void) {

    struct trie* myDictionary = init();

    // Read in number of words.
    int i, n;
    FILE* ifp = fopen("dictionary.txt", "r");
    fscanf(ifp, "%d", &n);
    char** reg = malloc(sizeof(char*)*n);

    // Read in each word and insert it.
    for (i=0; i<n; i++) {
        char word[100];
        fscanf(ifp, "%s", word);
        insert(myDictionary, word);
        reg[i] = malloc((strlen(word)+1)*sizeof(char));
        strcpy(reg[i], word);
    }

    // Test test question.
    char mold[100];
    printf("Enter mold to fit.\n");
    scanf("%s", mold);
    printf("%d words fit the mold via trie.\n", numfit(myDictionary, mold));
    int mlen = strlen(mold);

    // Just double check the answer.
    int doublecheck = 0;
    for (int i=0; i<n; i++) {

        if (mlen != strlen(reg[i])) continue;

        int ok = 1;
        for (int j=0; j<mlen; j++)
            if (mold[j] != '*' && mold[j] != reg[i][j])
                ok = 0;
        doublecheck += ok;
    }
    printf("My safety check is %d\n", doublecheck);

    // Free array dictionary.
    for (int i=0; i<n; i++)
        free(reg[i]);
    free(reg);

    // Clean up.
    fclose(ifp);
    freeDictionary(myDictionary);
    return 0;
}

// Wrapper function.
int numfit(trie* root, char* mold) {
    return numfitrec(root, mold, 0, strlen(mold));
}

// Finds all the answers from the node root for the substring mold[k..n-1].
int numfitrec(trie* root, char* mold, int k, int n) {

    // Too far.
    if (root == NULL) return 0;

    // We're where we need to be. See if it's a word.
    if (k == n) return root->isWord;

    int res = 0;

    // Here we have to try all 26 branches and add results.
    if (mold[k] == '*') {
        for (int i=0; i<26; i++)
            res += numfitrec(root->next[i], mold, k+1, n);
    }

    // Here we just go down the path for this letter (mold[k]).
    else
        res += numfitrec(root->next[mold[k]-'a'], mold, k+1, n);

    // Ta da!
    return res;
}

struct trie* init() {

    // Create the struct, not a word.
    struct trie* myTree = malloc(sizeof(struct trie));
    myTree->isWord = 0;

    // Set each pointer to NULLL.
    int i;
    for (i=0; i<26; i++)
        myTree->next[i] = NULL;

    // Return a pointer to the new root.
    return myTree;
}

// Provide this function for the user...
void insert(struct trie* tree, char word[]) {
    insertRec(tree, word, 0, strlen(word));
}

// Recursive insert function that does all the work.
// k represents how many letters down the trie we have gone.
void insertRec(struct trie* tree, char word[], int k, int wordlen) {

    // Down to the end, insert the word.
    if (k == wordlen) {
        tree->isWord = 1;
        return;
    }

    // See if the next place to go exists, if not, create it.
    int nextIndex = word[k] - 'a';
    if (tree->next[nextIndex] == NULL)
        tree->next[nextIndex] = init();

    // Insert recursively down the path of this word, advancing one letter.
    insertRec(tree->next[nextIndex], word, k+1, wordlen);

}

// Wrapper function returns 1 iff word is in the trie pointed to by tree.
int search(struct trie* tree, char word[]) {
    return searchRec(tree, word, 0, strlen(word));
}

// Recursive search from level k of the trie for word.
int searchRec(struct trie* tree, char word[], int k, int wordlen) {

    // Down to the end, insert the word.
    if (k == wordlen)
        return tree->isWord;

    // If the next place doesn't exist, word is not a word.
    int nextIndex = word[k] - 'a';
    if (tree->next[nextIndex] == NULL)
        return 0;

    return searchRec(tree->next[nextIndex], word, k+1, wordlen);
}

// Just frees all the memory pointed to by tree (directly and indirectly)
void freeDictionary(struct trie* tree) {

    int i;
    for (i=0; i<26; i++)
        if (tree->next[i] != NULL)
            freeDictionary(tree->next[i]);

    free(tree);
}

// Prints all words stored in the trie in alphabetical order.
void printAll(struct trie* tree, char cur[]) {

    // Stop!
    if (tree == NULL) return;

    // Print this node, if it's a word.
    if (tree->isWord)
        printf("%s\n", cur);

    // Safer if we store this.
    int len = strlen(cur);

    // Recursively print all words in each subtree,
    // in alpha order.
    int i;
    for (i=0; i<26; i++) {
        cur[len] = (char)('a'+i);
        cur[len+1] = '\0';
        printAll(tree->next[i], cur);
    }
}