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

#define MAXWORD 20 /* maximum word length allowed */

struct lines_t {
     int line;
     struct lines_t *left; /* less than line */
     struct lines_t *right; /* greater than line */
};

struct word_t {
     char name[MAXWORD];
     struct lines_t *lines;
     struct word_t *left; /* less than name */
     struct word_t *right; /* greater than root */
};

/* return 1 if s is not a noise word */
int notnoise(char *s) {
     static const char *noise[] = { "is", "are", "was", "were",
				    "this", "that", "those", "these",
				    "am", "aren't", "isn't", "not",
				    "they", "them", "you", "to",
				    "\0" };
     char **t = (char **) noise;

     /* return 0 if s matches any of the noise words */
     while (strcmp(*t, "\0")) {
	  if (strcmp(*t, s) == 0)
	       return 0;
	  t++;
     }

     return 1;
}

struct word_t *walloc(void) {

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

struct lines_t *lalloc(void) {

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

struct lines_t *addline(int line, struct lines_t *root) {

     if (root == NULL) {
	  root = lalloc();
	  root->line = line;
     } else if (line > root->line)
	  root->right = addline(line, root->right);
     else if (line < root->line)
	  root->left = addline(line, root->left);
     /*ignore repeat offendors */

     return root;
}

struct word_t *addword(char *word, int line, struct word_t *root) {
     int cond;

     if (root == NULL) {
	  root = walloc();
	  strcpy(root->name, word);
	  root->lines = addline(line, root->lines);
     } else if ((cond=strcmp(word, root->name)) > 0)
	  root->right = addword(word, line, root->right);
     else if (cond < 0)
	  root->left = addword(word, line, root->left);
     else /* same word, possibly different line */
	  root->lines = addline(line, root->lines);

     return root;
}

void printlines(struct lines_t *root) {

     if (root != NULL) {
	  printlines(root->left);
	  printf("%d, ", root->line);
	  printlines(root->right);
     }
}

void printwords(struct word_t *root) {

     if (root != NULL) {
	  printwords(root->left);
	  printf("%s: ", root->name);
	  printlines(root->lines);
	  printf("\n");
	  printwords(root->right);
     }
}

int main(void) {
     struct word_t *wtree;
     char word[MAXWORD];
     int cond;
     int line;

     /* get words */
     wtree = NULL;
     line = 1;
     while ((cond=getword(word, MAXWORD)) != EOF) {
	  if (cond == '\n')
	       line++;
	  else if (notnoise(word)) {
	       wtree = addword(word, line, wtree);
	  }
     }

     /* print words */
     printwords(wtree);

     return 0;
}