// Art's asn05 solution handout for class
#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 **i_tree_search(struct tnode **, char *);	// iterative version
struct tnode **r_tree_search(struct tnode **, char *);	// recursive version
void tree_stats(struct tnode *);
int get_word(char *);

int total_nodes, total_words, high_count, deepest_level;
struct tnode *most_frequent, *deepest;
double avg_node_depth, weighted_avg_node_depth;
#define	MAXLEV	60		// a generous max tree depth estimate
int counts[MAXLEV], nodes[MAXLEV];

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);
		if((*tpp) == NULL) {
			(*tpp) = calloc(1, sizeof(struct tnode));
			(*tpp)->word = (char *)strdup(word_buff);
		}	// calloc has cleared count, left and right
		(*tpp)->count++;
	}
	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);
	if(deepest)
		printf("deepest word <%s> count is %d level is %d\n",
			deepest->word, deepest->count, deepest_level);
	printf("avg_node_depth %f\n", avg_node_depth/total_nodes);
	printf("weighted_avg_node_depth %f\n",
		weighted_avg_node_depth/total_words);
	for(i = 1; i <= deepest_level; i++)
		printf("level %d: %d nodes %d counts %f per node\n",
			i, nodes[i], counts[i], (float)counts[i]/nodes[i]);
	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 using recursion - usually slightly slower than iterative
struct tnode **r_tree_search(struct tnode **tpp, char *w) {
	if(*tpp) {		// the recursive method has no explicit loop
		int cmp = strcmp((*tpp)->word, w);
		if(cmp > 0)
			tpp = r_tree_search(&(*tpp)->left, w);
		else if(cmp < 0)
			tpp = r_tree_search(&(*tpp)->right, w);
	}
	return(tpp);
}

// redone using iteration
struct tnode **i_tree_search(struct tnode **tpp, char *w) {
	while(*tpp) {		// the iterative method loops down the tree
		int cmp = strcmp((*tpp)->word, w);
		if(cmp)
			tpp = (cmp > 0 ? &(*tpp)->left : &(*tpp)->right);
		else
			break;
	}
	return(tpp);
}

int level = 0;  /* a variable to track tree_walk recursion level */
// gather stats to check tree correctness
void tree_stats(struct tnode *tp) {
	if(tp) {
		int i;
		level++;
		tree_stats(tp->left);
		total_nodes++;
		total_words += tp->count;
		if(tp->count > high_count) {
			most_frequent = tp;
			high_count = tp->count;
		}
		if(level > deepest_level) {
			deepest = tp;
			deepest_level = level;
		}
		if(level < 7) {
			for(i = 1; i < level; i++)
				printf("       ");
			printf("%s %d\n", tp->word, tp->count);
		}
		counts[level] += tp->count;
		nodes[level]++;
		avg_node_depth += level;
		weighted_avg_node_depth += tp->count * level;
		tree_stats(tp->right);
		level--;
	}
}

#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);
}