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

#define MAXLEN 8
#define MINLEN 2

typedef struct _treenode {
   char *word;             /* String to be stored in the node */
   struct _treenode *L;    /* Pointer to left child */
   struct _treenode *R;    /* Pointer to right child */
   struct _treenode *P;    /* Pointer to parent */
   int balfac;             /* Balance factor */
} treenode;

typedef treenode *AVLtree;

typedef AVLtree *dict;

AVLtree AVLinsert ( AVLtree T, char *item )
{
   treenode *p, *q, *r;
   int cmpres;

   if (T == NULL) {
      T = (AVLtree)malloc(sizeof(treenode));
      T -> L = T -> R = T -> P = NULL;
      T -> word = (char *)malloc((strlen(item) + 1) * sizeof(char));
      strcpy(T -> word, item);
      T -> balfac = 0;
      return T;
   }

   p = T; q = p -> P;
   while (p != NULL) {
      cmpres = strcmp(item, p -> word);
      if (cmpres == 0) return T;
      q = p;
      p = (cmpres < 0) ? p -> L : p -> R;
   }
   p = (treenode *)malloc(sizeof(treenode));
   p -> L = p -> R = NULL; p -> P = q;
   p -> word = (char *)malloc((strlen(item) + 1) * sizeof(char));
   strcpy(p -> word, item);
   p -> balfac = 0;
   if (cmpres < 0) {
      q -> L = p; q -> balfac -= 1;
   } else {
      q -> R = p; q -> balfac += 1;
   }

   while (1) {
      /* Balance-factor adjustment has reached root */
      if (q == NULL) return T;

      /* Height increase absorbed at q */
      if (q -> balfac == 0) return T;

      /* Propagate height increase one more level up */
      if ((q -> balfac == -1) || (q -> balfac == 1)) {
         p = q; q = q -> P;
         if (q != NULL) {
            if (p == q -> L) q -> balfac -= 1; else q -> balfac += 1;
         }
         continue;
      }

      /* Violation of AVL property: Case 1 */
      if (q -> balfac == -2) {
         if (p -> balfac == -1) {    /* Single rotation */
            if (q -> P == NULL) T = p;
            else {
               if (q == q -> P ->  L) q -> P -> L = p;
               else q -> P -> R = p;
            }
            q -> L = p -> R;
            if (p -> R != NULL) p -> R -> P = q;
            p -> R = q;
            p -> P = q -> P;
            q -> P = p;
            p -> balfac = q -> balfac = 0;
         } else {                    /* Double rotation */
            r = p -> R;
            if (q -> P == NULL) T = r;
            else {
               if (q == q -> P ->  L) q -> P -> L = r;
               else q -> P -> R = r;
            }
            p -> R = r -> L;
            if (r -> L != NULL) r -> L -> P = p;
            q -> L = r -> R;
            if (r -> R != NULL) r -> R -> P = q;
            r -> L = p;
            r -> R = q;
            r -> P = q -> P;
            p -> P = q -> P = r;
            if (r -> balfac == 0) { p -> balfac = q -> balfac = 0; }
            else if (r -> balfac == -1) { p -> balfac = 0; q -> balfac = 1; }
            else { p -> balfac = -1; q -> balfac = 0; }
            r -> balfac = 0;
         }
         return T;
      }

      /* Violation of AVL property: Case 2 */
      if (q -> balfac == 2) {
         if (p -> balfac == 1) {    /* Single rotation */
            if (q -> P == NULL) T = p;
            else {
               if (q == q -> P ->  L) q -> P -> L = p;
               else q -> P -> R = p;
            }
            q -> R = p -> L;
            if (p -> L != NULL) p -> L -> P = q;
            p -> L = q;
            p -> P = q -> P;
            q -> P = p;
            p -> balfac = q -> balfac = 0;
         } else {                    /* Double rotation */
            r = p -> L;
            if (q -> P == NULL) T = r;
            else {
               if (q == q -> P ->  L) q -> P -> L = r;
               else q -> P -> R = r;
            }
            p -> L = r -> R;
            if (r -> R != NULL) r -> R -> P = p;
            q -> R = r -> L;
            if (r -> L != NULL) r -> L -> P = q;
            r -> L = q;
            r -> R = p;
            r -> P = q -> P;
            p -> P = q -> P = r;
            if (r -> balfac == 0) { p -> balfac = q -> balfac = 0; }
            else if (r -> balfac == -1) { p -> balfac = 1; q -> balfac = 0; }
            else { p -> balfac = 0; q -> balfac = -1; }
            r -> balfac = 0;
         }
         return T;
      }
   }
}

dict builddict ( char *dfname )
{
   FILE *fp;
   char word[100];
   dict D;
   int l;

   D = (dict)malloc((MAXLEN + 1) * sizeof(AVLtree));
   for (l=0; l<=MAXLEN; ++l) D[l] = NULL;
   fp = fopen(dfname,"r");
   while (!feof(fp)) {
      fscanf(fp, "%s", word);
      l = strlen(word);
      if ((l < MINLEN) || (l > MAXLEN))
         fprintf(stderr, "Invalid length %d of word \"%s\"\n", l, word);
      else D[l] = AVLinsert(D[l],word);
   }
   fclose(fp);
   return D;
}

void AVLprint ( AVLtree T )
{
   if (T == NULL) return;
   AVLprint(T -> L);
   /* printf("\t%s %d (%s,%s) %s\n", T -> word, T -> balfac,
                          (T -> L == NULL) ? "NULL" : T -> L -> word,
                          (T -> R == NULL) ? "NULL" : T -> R -> word,
                          (T -> P == NULL) ? "NULL" : T -> P -> word); */
   printf("\t%s\n", T -> word);
   AVLprint(T -> R);
}

int AVLheight ( AVLtree T )
{
   if (T == NULL) return -1;
   if (T -> balfac > 0) return 1 + AVLheight(T -> R);
   return 1 + AVLheight(T -> L);
}

void destroytree ( AVLtree T )
{
   if (T == NULL) return;
   destroytree(T -> L);
   destroytree(T -> R);
   free(T -> word);
   free(T);
}

void destroy ( dict D )
{
   int l;

   for (l = MINLEN; l <= MAXLEN; ++l) destroytree(D[l]);
   free(D);
}

int AVLsearch ( AVLtree T, char word[] )
{
   int cmpres;

   while (T != NULL) {
      cmpres = strcmp(word, T -> word);
      if (cmpres == 0) return 1;
      if (cmpres < 0) T = T -> L; else T = T -> R;
   }
   return 0;
}

int search ( dict D, char word[] )
{
   int l;

   l = strlen(word);
   if ((l < MINLEN) || (l > MAXLEN)) {
      fprintf(stderr, "Invalid length %d of word \"%s\"\n", l, word);
      return 0;
   }
   return AVLsearch(D[l],word);
}

void findcorrections ( dict D, char word[] )
{
   int i, k, l;
   char newword[100], c, ch;

   printf("Spell check suggestions:\n");
   l = strlen(word);

   /* Delete one letter */
   if (l > MINLEN) {
      printf("\tGroup 1: "); newword[l-1] = '\0';
      for (k = 0; k < l; ++k) {
         for (i=0; i<k; ++i) newword[i] = word[i];
         for (i=k+1; i<l; ++i) newword[i-1] = word[i];
         if (AVLsearch(D[l-1],newword)) printf("%s ", newword);
      }
      printf("\n");
   }

   /* Insert one letter */
   if (l < MAXLEN) {
      printf("\tGroup 2: "); newword[l+1] = '\0';
      for (k = 0; k <= l; ++k) {
         for (i=0; i<k; ++i) newword[i] = word[i];
         for (i=k; i<l; ++i) newword[i+1] = word[i];
         for (c='A'; c<='Z'; ++c) {
            newword[k] = c;
            if (AVLsearch(D[l+1],newword)) printf("%s ", newword);
         }
      }
      printf("\n");
   }

   /* Change one letter */
   printf("\tGroup 3: ");
   strcpy(newword,word);
   for (k=0; k<l; ++k) {
      ch = newword[k];
      for (c='A'; c<='Z'; ++c) {
         newword[k] = c;
         if (AVLsearch(D[l],newword)) printf("%s ", newword);
      }
      newword[k] = ch;
   }
   printf("\n");

   /* Swap two letters */
   printf("\tGroup 4: ");
   strcpy(newword,word);
   for (k=0; k<=l-2; ++k) for (i=k+1; i<=l-1; ++i) {
      c = newword[k]; newword[k] = newword[i]; newword[i] = c;
      if (AVLsearch(D[l],newword)) printf("%s ", newword);
      c = newword[k]; newword[k] = newword[i]; newword[i] = c;
   }
   printf("\n");
}

int isvowel ( char c )
{
   if (c == 'A') return 1;
   if (c == 'E') return 1;
   if (c == 'I') return 1;
   if (c == 'O') return 1;
   if (c == 'U') return 1;
   return 0;
}

void randsearch ( dict D )
{
   char DIST[101] = "AAAAAAAAABBCCDDDDDDEEEEEEEEEEEFFFFGGGHHIIIIIIIIIJKLLLLMMNNNNOOOOOOOOPPQRRRRRRSSSSSTTTTTTUUUUVVWWXYYZ";
   char word[100];
   int i, l, vow1, vow2;

   l = MINLEN + rand() % (MAXLEN - MINLEN + 1);
   word[0] = DIST[rand() % 100];
   vow1 = isvowel(word[0]);
   for (i=1; i<l; ++i) {
      word[i] = DIST[rand() % 100];
      vow2 = isvowel(word[i]);
      if ((vow1 == vow2) && (rand() % 32)) { --i; continue; }
      vow1 = vow2;
   }
   word[l] = '\0';
   printf("\nSearching for word \"%s\"", word);
   for (i=l; i<=MAXLEN; ++i) printf(" ");
   printf(": ");
   fflush(stdout);
   if (search(D,word)) { printf("Found\n"); return; }
   printf("Not found\n");
   findcorrections(D,word);
}

int main ()
{
   dict D;
   int i, l;

   srand((unsigned int)time(NULL));
   D = builddict("wordlist.txt");
   /* for (l=MINLEN; l<=MAXLEN; ++l) {
      printf("%d-letter words:\n", l);
      AVLprint(D[l]);
   } */
   for (l = MINLEN; l <= MAXLEN; ++l)
      printf("Height of D[%d] = %d\n", l, AVLheight(D[l]));
   for (i=0; i<10; ++i) randsearch(D);
   destroy(D);
   exit(0);
}