// Arup Guha
// 11/13/2009
// Solution to Fall 2009  COP 3223 Program #5: Spell Checker!
#include <stdio.h>

#define MAXWORDS 30000
#define MAXLENGTH 30

// Functions required by the assignment.
int substring(char shortstr[], char longstr[]);
int subsequence(char shortstr[], char longstr[]);
int permutation(char string1[], char string2[]);
int matchscore(char string1[],char string2[]);

// Extra auxiliary functions created to help flow of main.
int readFile(char dictionary[][MAXLENGTH], FILE* ifp);
int correct(char dictionary[][MAXLENGTH], int numwords, char word[]);
void output(char dictionary[][MAXLENGTH], int numwords, char word[]);

int main() {
    
    char dictionary[MAXWORDS][MAXLENGTH];
    char word[MAXLENGTH], answer[MAXLENGTH];
    FILE *ifp;
       
    printf("Welcome to the Spell Checker!\n");
    
    // Read in the dictionary.
    ifp = fopen("dictionary.txt", "r"); 
    int numwords = readFile(dictionary, ifp);
    fclose(ifp);
    printf("The dictionary has been loaded.\n");
    
    // Since we always want to ask them at least one word.
    strcpy(answer, "yes");
    
    // Loop so long as the user would like.
    while (tolower(answer[0]) == 'y') {
    
        printf("\nPlease enter the word you would like checked.\n");
        scanf("%s", word);
        
        // See if it's in the dictionary first.
        if (correct(dictionary, numwords, word))
            printf("\nGreat, %s is in the dictionary!\n\n", word);            
        
        // Or output the suggestions.
        else 
            output(dictionary, numwords, word);
          
        // See if they want to enter another word.
        printf("Would you like to enter another word? (yes/no)\n");
        scanf("%s", answer);      
    }
}

// Returns 1 iff word exists in dictionary.
int correct(char dictionary[][MAXLENGTH], int numwords, char word[]) {
    
    int i;
    
    // Uses basic linear search, even though the dictionary is sorted.
    // Binary Search is taught in COP 3502, not this class.
    for (i=0; i<numwords; i++) {
        
        // Found the word return true!
        if (strcmp(dictionary[i], word) == 0)
            return 1;     

    }
    
    // If we get here, the word wasn't in the dictionary.
    return 0;
}

void output(char dictionary[][MAXLENGTH], int numwords, char word[]) {
     
     int i;
     
     int testlen = strlen(word);
     
     // Output a title/header.
     printf("\nHere are possible words you could have meant:\n\n");
     
     // Go through each word to see if it is a suggestion.
     for (i=0; i<numwords; i++) {
     
         int thislen = strlen(dictionary[i]);
         
         // This disqualifies a string, if you carefully read the rules, so
         // just get this case out of the way.
         if (abs(testlen-thislen) > 2)
             continue;
         
         // Check both substrings.
         if (substring(word, dictionary[i]) || substring(dictionary[i], word)) {
             printf("%s\n", dictionary[i]);
             continue;
         }
         
         // Check for subsequence.                     
         if (subsequence(word, dictionary[i]) || subsequence(dictionary[i], word)) {
             printf("%s\n", dictionary[i]);
             continue;                  
         }    
         
         // Notice the short-circuiting here, we only call permutation if
         // the lengths of the two strings are equal.
         if (testlen == thislen && permutation(word, dictionary[i])) {
             printf("%s\n", dictionary[i]);
             continue;      
         }
         
         // Note: No continue needed here since this is the last condition!
         if (testlen == thislen && matchscore(word, dictionary[i]) < 3)
             printf("%s\n", dictionary[i]);
     }
     
     printf("\n");
}
        
int readFile(char dictionary[][MAXLENGTH], FILE* ifp) {
    
    int numwords, i;
    
    // Read in the number of words.
    fscanf(ifp, "%d", &numwords);    
    
    // Read in each word.
    for (i=0; i<numwords; i++) 
        fscanf(ifp, "%s", dictionary[i]);
      
    // Return the number of words.
    return numwords;
}

int substring(char shortstr[], char longstr[]) {
    
    int start, i;
    
    // Check for a match starting at index start in longstr.
    /*** Note: Calculating strlen(longstr)-strlen(shortstr) returns an
               unsigned int. This is what I initially had, but the loop
               ran when it should not have. I fixed this issue by writing
               what is below, which is theoretically equivalent to
               start < strlen(longstr)-strlen(shortstr), but actually is not,
               since in the expression above, all values calculated are 
               positive.
    ***/
    for (start=0; start+strlen(shortstr) <= strlen(longstr); start++) {

        int match = 1;
        
        // Try checking each corresponding letter in this setting.
        for (i=0; i<strlen(shortstr); i++)
            if (shortstr[i] != longstr[start+i])
                match = 0;
                
        // If they all worked, match would be 1 at this point.
        if (match)
            return 1; 
    }    
    
    // If we get here, we never found a matching substring.
    return 0;
}

int subsequence(char shortstr[], char longstr[]) {

    // i will index shortstr, j will index longstr
    int i=0, j=0;    
    
    // Stop when we get to the end of either string.
    while (i < strlen(shortstr) && j < strlen(longstr)) {
    
        // Got a match, advance to the next letter on both strings.
        if (shortstr[i] == longstr[j]) {
            i++;
            j++;
        }
        
        // We have to match shortstr, so just go to the next letter in
        // longstr.
        else
            j++;      
    }
    
    // We only get a subsequence if we iterated to the end of the short
    // string.
    return i == strlen(shortstr);
}

int permutation(char string1[], char string2[]) {
    
    int i,j;
    
    // This is as big as the arrary needs to be since no string will be 
    // longer than 19 characters.
    int used[19];
    
    for (i=0; i<19; i++) used[i] = 0;
        
    // Go through each letter in the first string.
    for (i=0; i<strlen(string1); i++) {
        
        // Look for a matching letter in string 2.
        int found = 0;
        for (j=0; j<strlen(string2); j++) {
            
            // The letters match AND we haven't used this letter in string2 yet.
            if (string1[i] == string2[j] && used[j] == 0) {
                used[j] = 1;
                found = 1;
            }
        }
        
        // We couldn't find a match for letter i in string1.
        if (!found)
            return 0;
        
    }    
    
    // If we get here, they are permutations iff they are the same length.
    return (strlen(string1) == strlen(string2));
    
}

int matchscore(char string1[],char string2[]) {
    
    int i;
    int score = 0;
    
    // Go through and count up all non-matching characters.
    for (i=0; i<strlen(string1) && i<strlen(string2); i++)
        if (string1[i] != string2[i])
            score++;
            
    // Not in the program specs, but we're just adding in the difference
    // in length between the two strings, since these characters are clearly
    // not matched. Should not affect the way the assignment runs because in
    // the assignment we are guaranteed that this function is only called with
    // equal length strings.
    score += abs(strlen(string1) - strlen(string2));
    
    return score;
}