#include "autocomplete.h"

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

static int TotalWords=0;
static int TotalMemory=0;

typedef struct table{
    struct table *nextLevel[26];
    char *completions[10];
    int lastIndex;
}
table;

static struct table Root = { {NULL}, {NULL}, 0 };

void AutoComplete_AddWord(const char *word)
{
    // Begin at root
    struct table* current = &Root;

    // Flags for inserted words and new words
    int haveInsert=0;
    int index;
    int newword = 0;

    int level;

    // We do 4 levels because we count the root table as a level.
    // So the project documentation asks for 3 levels, but because
    // we're counting root, it becomes 4 levels for this code.

    // If the word is less than 4 letters long, then we need to end
    // the loop with word[level]!='\0'
    for (level=0; level<4 && word[level] != '\0'; level++)
    {
        // Grab the index
        index=word[level] - 'a';

        // If the index is invalid (not a regular letter), then replace it
        // with an x
        if(index>26 || index<0)
        {
            index = 'x'-'a';
        }

        // If the next table pointer for this letter has not been allocated
        // then we need to allocate it
        if(current->nextLevel[index]==NULL)
        {
            // allocate the memory
            current->nextLevel[index] = (table*)malloc(sizeof(struct table)); // allocated memory(first word) is put into next layer

            // Add it to our memory used variable
            TotalMemory+=sizeof(struct table); //add newly allocated

            // Initialize the newly allocated memory
            int i;
            for(i=0;i<26;i++)
            {
                current -> nextLevel[index] -> nextLevel[i] = NULL; //set all pointer to null

                // lastIndex is set to 1 because we copy the word into completions list later
                current -> nextLevel[index] -> lastIndex = 1; //initialize lat index

                if(i<10)
                {
                    current -> nextLevel[index] -> completions[i]=NULL;
                } //set completions list to null

                // We're going to copy this word into completions right here
                // and we're going to flag this as a new word.
                current->nextLevel[index]->completions[0] = _strdup(word);
                newword = 1;

                // Add the memory from strdup
                TotalMemory += strlen(word);
            }
        }

        int i;

        // We need to check to see if this is a duplicate word so long as this is not a new word
        for(i=0; i< current->lastIndex && newword == 0; i++)
        {
            if(!strcmp(current-> completions[i], word)) //is word in completiion list
            {
                return; //word found
            }
        }

        // Add this word to the completions list for the current table level
        if(current->lastIndex <10)
        {
            current -> completions[current->lastIndex] = _strdup(word);
            current->lastIndex++;
            haveInsert=1; //flag as insert word into completed words

            TotalMemory += strlen(word); //keeping track of strdup - allocated memory
        }

        // Move to the next table level
        current = current->nextLevel[index];
    }

    TotalWords++; //add a word
}

int AutoComplete_AddDictionary(const char *filename)
{
    char array[100];

    FILE *file = fopen(filename, "r");

    if(file==NULL)
    {
        //printf("%s not found",filename);
        return 1;
    }

    while(!feof(file))
    {
        //end of file not reached
        fscanf(file,"%s",&array[0]);

        // For every word encountered in the file, send it to our
        // add word function to add our word to autocomplete's internal dictionary
        AutoComplete_AddWord(array);
    }

    fclose( file );
    return 0;
}

int AutoComplete_TotalMemory()
{
    return TotalMemory;
}

int AutoComplete_TotalWords()
{
    return TotalWords;
}


char **AutoComplete_SuggestCompletion(const char *word, int *number)
{
    // Begin at the root level
    struct table *current = &Root;

    int i;
    int index;

    // Go through 4 levels (3 + root)
    for(i=0; i<4 && word[i] != '\0'; i++) //iterations dependent upon num of typed ldetters
    {
        // Grab the index
        index = word[i] - 'a';
        if(index <0 || index>26)
        {
            index = 'x'-'a'; //retrieve indexs 0 to 26, if higher replace with x
        }

        // If the next level is NULL, then we don't need to proceed, and can suggest based upon
        // what is already there.
        if(current != NULL && current->nextLevel[index] != NULL )
        {
            current = current->nextLevel[index]; //move onto next level
        }

    }

    int numWords = current -> lastIndex; //use lastindex to find out how many words can guess out

    // If we don't have suggestions, return NULL
    if( numWords == 0 )
        return NULL;

    // Set the number of results equal to the lesser of the two: requested number and retrieved results.
    if(*number<numWords)
    {
        numWords=*number; //num of max suggestions wanted
    }
    if( *number > numWords )
    {
        *number = numWords;
    }

    char** suggested = (char**)malloc(sizeof(char*)*numWords); //allocate list of pointers

    for(i=0;i<numWords;i++)
    {
        suggested[i]=_strdup(current->completions[i]); //copy suggested completions at current node
    }

    return suggested;
}