/****************************************
* Section : 10
* Roll No. : 20CS10000 / 20CS30000
* Name : Aritra Hazra
* Assignment No : 6
* Description : Mini Spelling Checker
* Date : 08-Jun-2021
****************************************/

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

// returns the length of a string as an integer
int stringLength ( char *str )
{
  int len;
  for ( len = 0; str[len] != '\0'; len++) ; // iterating through the str
  return len;
}

// Returns true if shortstr is a substring of longstr, and false otherwise
int substring ( char *shortStr, char *longStr )
{
  int flag = 0, longId, shortId;
  
  for ( longId = 0; longStr[longId] != '\0'; longId++ ) { // iterating from each longStr index
    for ( shortId = 0; (shortStr[shortId] != '\0') &&
                       (longStr[longId+shortId] != '\0'); shortId++ ) { // iteratind through each shortStr index
      if ( shortStr[shortId] != longStr[longId+shortId] ) // mismatch character found
        break;
    }
    if ( shortStr[shortId] == '\0') { // successful match as shortStr finished
      flag = 1;
      break;
    }
    if ( longStr[longId+shortId] == '\0' ) // shortStr length is more than remaining longStr to compare with
      break;
  }
  
  return flag;
}

// Returns true if shortstr is a subsequence of longstr, and false otherwise
int subsequence ( char *shortStr, char *longStr )
{
  int flag = 0, shortId, longId;
  
  for ( longId = 0, shortId = 0; longStr[longId] != '\0'; longId++ ) { // iterating over longStr
    if ( shortStr[shortId] == longStr[longId] ) { // shortStr character matches with longStr character
      shortId++;
    }
    if ( shortStr[shortId] == '\0' ) { // successful match as ShortStr finished
      flag = 1;
      break;
    }
  }
  
  return flag;
}

// selection sort a copied string (do not modify directly into the string) and returns the sorted string
char *sortString (char *str)
{
  int i, j, minId;
  char temp;
  char *sortStr = (char *)malloc((stringLength(str)+1)*sizeof(char));
  for ( i = 0; str[i] !='\0'; i++ ) { // copying into a temporary string from the original str
    sortStr[i] = str[i];
  }
  sortStr[i] = '\0';
  
  // selection sort of the temporary string
  for ( i = 0; sortStr[i+2] != '\0'; i++ ) {
    for ( j = i+1, minId = i; sortStr[j+1] != '\0'; j++ ) {
      if ( sortStr[minId] > sortStr[j] ) { // selecting min index
        minId = j;
      }
    }
    // swapping the character in min index with first place character of the running string array
    temp = sortStr[i];
    sortStr[i] = sortStr[minId];
    sortStr[minId] = temp;
  }
  
  return sortStr;
}

// Returns true if string1 and string2 are permutatations of each other, false otherwise
int permutation ( char *string1, char *string2 )
{
  int flag = 0, i;
  char *sortStr1 = sortString(string1); // sort first string
  char *sortStr2 = sortString(string2); // sort second string
  
  // compare two sorted string to be exactly equal
  for ( i = 0; (sortStr1[i] == sortStr2[i]) &&
               (sortStr1[i] != '\0') && (sortStr2[i] != '\0'); i++ ) ;
  
  if ( (sortStr1[i] == '\0') && (sortStr2[i] == '\0') ) { // both sorted strings are equal indicating permutations of each other
    flag = 1;
  }
  
  return flag;
}

// Precondition: string1 and string2 are the same length and only contain lowercase letters
// Postcondition: returns the score of the match score between these two strings
int matchscore ( char *string1, char *string2 )
{
  int score = 0, i;
  
  for ( i = 0; string1[i] != '\0'; i++ ) { // check for number of character differences 
    if ( string1[i] != string2[i] ) { // compute score
      score++;
    }
  }
  
  return score;
}

// prints the suggested words from dictionary based on the following rules:
// (1) If either string is a substring of the other, and the lengths of the two strings are within 2 of one another.
// (2) If either string is a subsequence of the other and the lengths of the two strings are within 2 of one another.
// (3) If the strings are permutations of one the other. (Only try this test if the two strings are of the same length.)
// (4) If the matchscore between the two strings is less than 3. (Only try this test if the two strings are of the same length.)
void wordSuggest ( char *word, int wordLen, char **dict, int noWords )
{
  int i, dictWordLen;
  
  for ( i = 0; i < noWords; i++ ) {
    dictWordLen = stringLength(dict[i]);
    if ( ( (substring(word, dict[i]) || substring(dict[i], word)) &&
           ( ((wordLen >= dictWordLen) && (wordLen - dictWordLen <= 2)) ||
             ((wordLen < dictWordLen) && (dictWordLen - wordLen <= 2)) ) ) // Condition-(1)
        ||
         ( (subsequence(word, dict[i]) || subsequence(dict[i], word)) &&
           ( ((wordLen >= dictWordLen) && (wordLen - dictWordLen <= 2)) ||
             ((wordLen < dictWordLen) && (dictWordLen - wordLen <= 2)) ) ) // Condition-(2)
        ||
         ( (wordLen == dictWordLen) && (permutation(word, dict[i])) ) // Condition-(3)
        ||
         ( (wordLen == dictWordLen) && (matchscore(word, dict[i]) < 3) ) )  // Condition-(4)
    {
      printf("%s\n", dict[i]);
    }
  }
}

int main()
{
  int noWords, maxLenWord, i, wordLen;
  char **dictionary;
  char *word;
  char choice;
  int matchFlag;
  
  // take from user the number of words and max word length
  printf("++ Welcome to Mini Spell Checker ++\n");
  printf("\n-- Load Dictionary Words --\n");
  scanf("%u%u", &noWords, &maxLenWord);
  // dynamically allocate memory to store the dictionary of words
  dictionary = (char **)malloc(noWords * sizeof(char *));
  for ( i = 0; i < noWords; i++ ) {
    dictionary[i] = (char *)malloc((maxLenWord + 1) * sizeof(char)); // allocate memory
    scanf("%s", dictionary[i]); // scan dictionary words
  }
  printf("\n-- Dictionary of Words Loaded --\n");
  
  // dynamically allocate momory for the user entered word while checking the spelling
  word = (char *)malloc((maxLenWord + 1) * sizeof(char));
  
  do {
    // take from user the test word for spell-check
    printf("\n** Enter Your Word: ");
    scanf("%s", word);
    
    wordLen = stringLength(word); // determine word length
    for ( i = 0, matchFlag = 0; (i < noWords) && (!matchFlag); i++ ) {
      // check if the word matches with any word in dictionary
      if ( wordLen == stringLength(dictionary[i]) ) {
        if ( !matchscore(word, dictionary[i]) ) {
          matchFlag = 1;
        }
      }
    }
    if ( matchFlag ) { // word found in the dictionary of words
      printf("\n** GREAT! Your word \"%s\" is in Dictionary!\n", word);
    }
    else { // word not found in the dictionary of words
      printf("\n** SORRY! Your word \"%s\" is NOT in Dictionary!", word);
      printf("\n** Some Possible Suggestions:\n");
      wordSuggest(word, wordLen, dictionary, noWords); // call for suggestions from dictionary
    }
    
    // take choice from user whether to repeat the spell-check
    printf("\n-- Would You Like to Enter Another Word? [Y/N]: ");
    scanf(" %c", &choice);
  } while( (choice == 'y') || (choice == 'Y') );
  
  printf("\n++ Thank You for using Mini Spell-Checker ++\n");
  
  return 0;
}