/*
 Here is your template for data structures assignment 5 due 6PM Oct 13.
 Your task is to build a binary tree of the words from Voyage of the
 Beagle and, other than the run time, reproduce EXACTLY this result ...

   $ time a.out computer search of vbgle for whales < vbgle10.txt
   total_nodes 12816
   total_words 210333
   most frequent word <the> count is 16930
   <computer> count is 4
   <search> count is 13
   <of> count is 9465
   vbgle is NOT in the tree
   <for> count is 1111
   <whales> count is 6
   
   real 0m0.154s	user 0m0.150s	sys 0m0.000s

 The printing of the statistics is already done for you and relies on
 your use of EXACTLY those command line arguments and the implementation
 of your tree_search() function to return a pointer to the pointer leading
 to the node found by a search.  Versions of the tree() function from
 the K&R and other books do NOT do this but may serve as examples of the
 general binary tree ideas.  In particular, I DO NOT want you to make new
 nodes inside of the tree_search() function but rather up in main().  This
 is to illustrate that tree_search() is only responsible for searching and
 that other operations can be done based on its returned result.
*/

#include <stdio.h>
#include <malloc.h>
struct tnode {			// specify the "shape" of a tnode structure ...
	struct tnode *left;	// the left and right branch pointers
	struct tnode *right;
	int count;		// the word count as before
	char *word;		// a pointer to the word
} *root;			// declare the root pointer variable

struct tnode **tree_search(struct tnode **, char *);
void tree_stats(struct tnode *);
int get_word(char *);

int total_nodes, total_words, high;
struct tnode *most_frequent;

int main(int argc, char *argv[]) {
	struct tnode **tpp;
	char word_buff[100];	// the reusable word buffer
	int i;
	while(get_word(word_buff)) {
		tpp = tree_search(&root, word_buff);
		/***** YOUR CODE TO ADD NEW NODES AND COUNT REPEATS *****/
	}
	tree_stats(root);
	printf("total_nodes %d\n", total_nodes);
	printf("total_words %d\n", total_words);
	if(most_frequent)
		printf("most frequent word <%s> count is %d\n",
			most_frequent->word, most_frequent->count);
	for(i = 1; i < argc; i++) {
		tpp = tree_search(&root, argv[i]);
		if((*tpp) == NULL)
			printf("%s is NOT in the tree\n", argv[i]);
		else
			printf("<%s> count is %d\n", argv[i], (*tpp)->count);
	}
	return(0);
}

// binary tree search returning a pointer to the pointer leading to a hit
struct tnode **tree_search(struct tnode **tpp, char *w) {
	/***** YOUR RECURSIVE OR ITERATIVE CODE TO DO THE BINARY SRCH *****/
	return(tpp);
}

// gather stats to check tree correctness
void tree_stats(struct tnode *tp) {
	/***** YOUR RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
}

#include <ctype.h>
/* Leave this routine EXACTLY as it stands */
int get_word(char *s) {
	int c;
	do {
		c = getchar();
		if(c == EOF)
			return(0);
	} while(!isalpha(c) && !isdigit(c));
	do {
		if(isupper(c))
			c = tolower(c);
		*s++ = c;
		c = getchar();
	} while(isalpha(c) || isdigit(c));
	*s = 0;
	return(1);
}