// Arup Guha
// 11/5/2015
// An example trie (just insertion) written in class (COP 3502)
/*** Edited on 11/5/2021 to add Quiz Question Solutions ***/

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

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

struct trie* init();
void insert(struct trie* tree, char word[], int k);
int search(struct trie* tree, char word[], int k) ;
int numWords(trie* root);
void freeDictionary(struct trie* tree);
int matchesWithErrors(trie* root, char* word, int k, int numerrors);

int main() {

    struct trie* myDictionary = init();

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

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

    // Test.
    printf("has %d words\n", numWords(myDictionary));

    char word[100];
    strcpy(word, "train");
    int ans = matchesWithErrors(myDictionary, word, 0, 2);
    printf("matches to train off by 2 are %d\n", ans);

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

/*** Solution for Version A ***/
int numWords(trie* root) {
	
	// No words here.
    if (root == NULL) return 0;
	
	// Add the contribution of this node.
    int res = root->isWord;
	
	// Recursively add the rest and return.
    for (int i=0; i<26; i++)
        res += numWords(root->next[i]);
    return res;
}

/*** Solution for Version B ***/
int matchesWithErrors(trie* root, char* word, int k, int numerrors) {

	// Probably not necessary but speeds up the search by avoiding paths doomed to fail.
    if (numerrors < 0) return 0;
	
	// If the node's not there, we can't get an answer.
    if (root == NULL) return 0;
	
	// We're at the end of our search; this node must be a word and we must have 0 errors left to make.
    if (k == strlen(word)) return numerrors == 0 && root->isWord;

    int res = 0;
	
	// Try all 26 letters next.
    for (int i=0; i<26; i++) {
		
		// We match this letter correctly so we still have to make numerrors in the future.
        if ((word[k]-'a') == i)
            res += matchesWithErrors(root->next[i], word, k+1, numerrors);
		
		// We mismatched this letter, so we have numerrors-1 errors to make in the future.
        else
            res += matchesWithErrors(root->next[i], word, k+1, numerrors-1);
    }

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

// Inserts word[k..] into teh trie rooted at tree.
void insert(struct trie* tree, char word[], int k) {

    // Down to the end, insert the word.
    if (k == strlen(word)) {
        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();

	// Recursively insert...
    insert(tree->next[nextIndex], word, k+1);
}

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