#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "getinput.h"

#define MAXWORD 20 /* maximum word length */
#define NDISTINCT 10000 /* maximum number of distinct words */

struct word_t {
     char word[MAXWORD]; /* the word itself */
     int count; /* the number of times we've encountered this word */
     struct word_t *left; /* less than word */
     struct word_t *right; /* greater than word */
};

struct word_t *walloc(void) {

     return (struct word_t *) malloc(sizeof(struct word_t));
}

struct word_t *addword(char *word, struct word_t *root) {
     int cond;
     
     if (root == NULL) {
	  root = walloc();
	  strcpy(root->word, word);
	  root->count = 1;
     } else if ((cond = strcmp(word, root->word)) > 0)
	  root->right = addword(word, root->right);
     else if (cond < 0)
	  root->left = addword(word, root->left);
     else
	  root->count++;

     return root;
}

/* store the tree nodes into a flat list */
void treestore(struct word_t *root, struct word_t *list[NDISTINCT], int *itn) {

     if (root != NULL) {
	  treestore(root->left, list, itn);
	  if (*itn < NDISTINCT)
	       list[(*itn)++] = root;
	  treestore(root->right, list, itn);
     }
}

/* a shell sort for the list of tree nodes */
void sortlist(struct word_t *list[], int size) {
     int gap, i, j;
     struct word_t *temp;

     for (gap = size / 2; gap > 0; gap /= 2)
	  for (i = gap; i < size; i++) {
	       temp = list[i];
	       for (j = i-gap; j >= 0 &&
			 list[j]->count >= temp->count; j -= gap) 
		    list[j+gap] = list[j];
	       list[j+gap] = temp;
	  }
}
		    
int main(void) {
     struct word_t *wdtree; /* top of the binary word tree */
     struct word_t *wdlist[NDISTINCT]; /* tree nodes as flat list */
     char word[MAXWORD]; /* temporary storage */
     int itn = 0; /* index of tree nodes */
     int cond;

     /* get the words */
     wdtree = NULL;
     while ((cond = getword(word, MAXWORD)) != EOF) {
	  if (isalpha(cond))
	       wdtree = addword(word, wdtree);
     }
     treestore(wdtree, wdlist, &itn);
     sortlist(wdlist, itn);

     /* print words */
     for (cond = 0; cond < itn; cond++)
	  printf("%d: %s\n", wdlist[cond]->count, wdlist[cond]->word);

     return 0;
}