// 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.

#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);

// Questions for Exam 2
int substring(trie* root, char* substr, int k, int n);
void printunique(trie* root, char word[], int k, int used[]);

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);

    int sum = 0;

    // Read in each word and insert it.
    for (i=0; i<n; i++) {
        char word[100];
        fscanf(ifp, "%s", word);
        sum += strlen(word);
        insert(myDictionary, word);
        if (i%10000 == 0) printf("%d word is %s\n", i, word);
    }


    for (i=0; i<10; i++) {
        printf("Enter a substring to search for.\n");
        char word[100];
        scanf("%s", word);
        if (substring(myDictionary, word, 0, strlen(word)))
            printf("Found substring %s\n", word);
        else
            printf("Sorry %s is not a substring.\n", word);
    }
/*
    char word[100];
    int used[26];
    for (int i=0;i<26; i++) used[i] = 0;
    printunique(myDictionary, word, 0, used);
*/
    // Clean up.
    fclose(ifp);
    freeDictionary(myDictionary);
    return 0;
}

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);
    }
}

// Exam 2 Wednesday Class
int substring(trie* root, char* substr, int k, int n) {

    // Always good to have this.
    if (root == NULL) return 0;

    // We matched the whole substring.
    if (k == n) return 1;

    // We haven't found this substring yet.
    int res = 0;

    // Try each next letter.
    for (int i=0; i<26; i++) {

		// The kth letter matches try future letters.
        if (i == substr[k]-'a')
            res = res || substring(root->next[i], substr, k+1, n);

		// So the kth letter doesn't match, but this matches the 0th so go to the 1st.
        else if (k > 0 && i == substr[0]-'a')
			res = res || substring(root->next[i], substr, 1, n);

		// We have nothing matched now.
		else
            res = res || substring(root->next[i], substr, 0, n);
    }

   return res;
}

// Exam 2 Thursday Class
void printunique(trie* root, char word[], int k, int used[]) {

    // Be safe...
    if (root == NULL) return;

    // We finished a word with all unique letters. Print it!!!
    if (root->isWord) {
        word[k] = '\0';
        printf("%s\n", word);
    }

    // Try each next letter.
    for (int i=0; i<26; i++) {

        // Oops we've used this letter, skip this branch.
        if (used[i]) continue;

        // Mark letter i as used and put it in the string word.
        used[i] = 1;
        word[k] = (char)('a'+i);

        // Recurse down this branch.
        printunique(root->next[i], word, k+1, used);

        // Undo so we can use this letter in the future.
        used[i] = 0;
    }

}