// Arup Guha
// 4/8/2022
// Used base code from mytrie2.c and modified it for the answer to
// COP 3502 Quiz 4 Question 3

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

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


struct trie* init();
void insert(struct trie* tree, char word[], int k, int wordlen);
void printAll(struct trie* tree, char cur[], int curlen);
int sumWordLengths(trie* root);
void freeDictionary(struct trie* tree);

int main() {

    struct trie* myDictionary = init(NULL);

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

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

    // Check if our function works!
    int functionSum = sumWordLengths(myDictionary);
    printf("Sum via trie function is %d.\n", functionSum);
    printf("Known  sum via strlen is %d.\n", sumLen);

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

// Solution to quiz question!
int sumWordLengths(trie* root) {

    // Nothing to see here!
    if (root == NULL) return 0;

    // Adds up contributions of all future letters in valid words from this point.
    int res = 0, i;
    for (i=0; i<26; i++)
        res += sumWordLengths(root->next[i]);

    // For every word that starts here, the latter term counts 1 for its first letter, and that is
    // all we're missing in our count! The exception is if the word ends here, then we don't count it.
    return res + (root->numWords - root->isWord);
}

struct trie* init() {

    // Create the struct, not a word.
    struct trie* myTree = malloc(sizeof(struct trie));
    myTree->isWord = 0;
    myTree->numWords = 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;
}

    int isWord;
    int numWords;
    struct trie* next[26];

void insert(struct trie* tree, char word[], int k, int wordlen) {

    // We need to always add this to this node.
    tree->numWords++;

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

    // Recursively insert in the appropriate subtrie.
    insert(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[], int curlen) {

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

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

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