/* Robert S Laramee
 * CS391S/T
 * 8 April 1997
 * Assignment #1
 *
 * see end of program for required documentation
 */

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

typedef struct dict_template {

    char word[50];
    char signature[50];

} dict_struct;

dict_struct dictionary[73000];

/* a function to swap two characters in a word, a helper function for the
 * version of quicksort used to sort the words into their corresponding
 * signatures
 */

static void swap_them(char *char_1, char *char_2)
{
      register char temp_char;

      temp_char = *char_1;
      *char_1 = *char_2;
      *char_2 = temp_char;
}

/* This is the version of quicksort used to sort the individual words
 * into signatures.
 */

void quicksort(char array[], unsigned word_length) {

      unsigned i, j, left, right;

      while (word_length > 1) {

            swap_them(&array[0], &array[word_length/2]);

            for (i = 0, j = word_length; ; ) {
                  do  --j;
                  while (array[j] > array[0]);
                  do  ++i;
                  while (i < j && array[i] < array[0]);

                  if (i >= j) {
                        break;
                  }
                  swap_them(&array[i], &array[j]);
            }
            swap_them(&array[j], &array[0]);
            left = j;
            right = word_length - ++j;
 
           if (left < right) {
                  quicksort(array, left);
                  array += j;
                  word_length = right;
            } else {
                  quicksort(array + j, right);
                  word_length = left;
            }
      }
}

/* This is the quicksort algorithm used to sort the entire bunch
 * of signatures.
 */

void QuickSort(dict_struct Dictionary[], int left, int right) {

    int i = left;
    int j = right;
    char mid[50] = Dictionary[(left+right)/2].signature;

    if (left >= right) return;

    do {
        while (strcmp(Dictionary[i].signature,mid) < 0)
            i++;
        while (strcmp(mid, Dictionary[j].signature) < 0)
            j--;

        if (i <= j) {

            dict_struct temp[1];

            temp[0] = Dictionary[i];
            Dictionary[i++] = Dictionary[j];
            Dictionary[j--] = temp[0];
        }
    } while (i <= j);

    QuickSort(Dictionary, left, j);
    QuickSort(Dictionary, i, right);
}

void main(void) {

    FILE *dict_file_ptr, *output_file_ptr;
    char input_array[50];
    char current_signature[50];
    int i = 0;
    int j = 0;
    int number_of_words = 0;

    /*  Open the dictionary file.
     */

    if ((dict_file_ptr = fopen("dict", "r")) == NULL) {
         printf("Error cannot open file 'dict' for reading. \n");
    }

    /* Read in the words from the dictionary and then sort the
     * letters to get a signature
     */

    while (fgets(input_array, 50, dict_file_ptr) != NULL) {
        dictionary[number_of_words].word = input_array;
        quicksort(input_array, strlen(input_array) - 1);
        dictionary[number_of_words].signature = input_array;
        number_of_words++;
    }
    /* Now sort the entire bunch of signatures using quicksort.
     */

    QuickSort(dictionary, 0, number_of_words);

    /*  Open the output file (text).
     */

    if ((output_file_ptr = fopen("anagram.out", "w")) == NULL) {
         printf("Error cannot open file 'anagram.out' for writing. \n");
    }

    /*  Start outputting to file.  
     */
    int a, b;
    for (int a = 0; a <= number_of_words; a++) {

    while (strcmp(dictionary[a].signature,dictionary[a + 1].signature) !=0) 
       { a++;}
     
       current_signature = dictionary[a].signature;
       b = 0;

       while (strcmp(current_signature, dictionary[a].signature) == 0) {
           b = 1;
           for (int tmp = 0; tmp <= (strlen(current_signature)); tmp++) {
               if (current_signature[tmp] != '\n' 
                && current_signature[tmp] != NULL)
                   putc(dictionary[a].word[tmp], output_file_ptr);
	       }
           a++;
           putc(' ',output_file_ptr);
       }
       if (b == 1) {
           a--;
       }
       putc('\n',output_file_ptr);
    }
    /*  Close both files
     */

    if (fclose(output_file_ptr)) {
        printf("Problem closing anagram.out file...\n");
    }
    if (fclose(dict_file_ptr)) {
        printf("Problem closing dict file...\n");
    }
}

/* The quicksort algorithm was used in both sorts.  This is because
 * it take nlog(n) time.  It was chosen over Insertion sort because
 * that takes n squared time.  It was also chosen over Counting sort
 * because counting sort requires a lot of extra memeory.  And we
 * would need a lot of extra memory in this program.
 *
 * Running Time:
 * el1> time anagram
 * 6.742u 0.786s 0:07.76 96.9% 0+52k 1+9io 0pf+0w
 *
 * Machine
 * el1> machine
 * alpha
 *
 * Number of words:
 * el1> wc anagram.out
 *       3496      7774     60032 anagram.out
 *
 * Anagram classes that contain more than 5 words in them:
 * el1> cat anagram.out | awk 'NF > 5'.
 * bread beard debar ardeb barde debra
 * caret cater trace react crate recta
 * plate pleat palet leapt petal lepta
 * steal teals stale stela least setal slate
 * vela vale elva veal leva lave
 * lair lira rial aril liar rail
 * risen serin resin siren reins rinse
 * lustre ulster sutler rustle result luster
 */