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

#include "bst_wcount.h"


void inorder_tree_walk(btnode *x)
{
    if (x != NULL) {
	inorder_tree_walk(x->left);
	printf("%5d\t%s\n", x->count, x->key);
	inorder_tree_walk(x->right);
    }
}

btnode *tree_search(btnode *x, char *key)
{
    if (x == NULL || strcmp(x->key, key) == 0)
	return x;
    if (strcmp(key, x->key) < 0)
	return tree_search(x->left, key);
    else
	return tree_search(x->right, key);
    return x;
}

btnode *iterative_tree_search(btnode *x, char *key)
{
    while (x != NULL && strcmp(x->key, key) != 0) {
	if (strcmp(key, x->key) < 0)
	    x = x->left;
	else
	    x = x->right;
    }
    return x;
}

btnode *tree_minimum(btnode *x)
{
    while (x->left != NULL) x = x->left;
    return x;
}

btnode *tree_maximum(btnode *x)
{
    while (x->right != NULL) x = x->right;
    return x;
}


btnode *tree_successor(btnode *x)
{
    btnode *y;
    if (x->right != NULL) return tree_minimum(x->right);
    y = x->parent;
    while (y != NULL && x == y->right) {
	x = y;
	y = y->parent;
    }
    return y;
}


btnode *tree_predecessor(btnode *x)
{
    btnode *y;
    if (x->left != NULL) return tree_maximum(x->left);
    y = x->parent;
    while (y != NULL && x == y->left) {
	x = y;
	y = y->parent;
    }
    return y;
}

void tree_insert(bstree *T, btnode *z)
{
    btnode *x, *y;
    y = NULL;
    x = T->ROOT;
    while (x != NULL) {
	y = x;
	if (strcmp(z->key, x->key) < 0) x = x->left;
	else x = x->right;
    }
    z->parent = y;
    if (y == NULL) T->ROOT = z; /* tree T was empty */
    else if (strcmp(z->key, y->key) < 0) y->left = z;
    else y->right = z;
}


void transplant(bstree *T, btnode *u, btnode *v)
{
    if (u->parent == NULL) /* u is ROOT */
	T->ROOT = v;
    else if (u == u->parent->left) /* u left child */
	u->parent->left = v;
    else u->parent->right = v;
    if (v != NULL) v->parent = u->parent;
}

void tree_delete(bstree *T, btnode *z)
{
    btnode *y;
    if (z->left == NULL)
	transplant(T, z, z->right);
    else if (z->right == NULL)
	transplant(T, z, z->left);
    else {
	y = tree_minimum(z->right);
	if (y->parent != z) {
	    transplant(T, y, y->right);
	    y->right = z->right;
	    y->right->parent = y;
	}
	transplant(T, z, y);
	y->left = z->left;
	y->left->parent = y;
    }
}


btnode *make_btnode(char *key)
{
    btnode *e = (btnode*) malloc(sizeof(btnode));
    int len = strlen(key);
    e->key = (char *) malloc((len+1) * sizeof(char));
    strcpy(e->key, key);
    e->count = 1;
    return e;
}


/* Usage: ./bst_count <filename> */

int main(int argc, char **argv)
{
    int i;
    char word[1000];
    FILE *infile;
    bstree T;
    btnode *e;
    if (argc != 2) {
	printf("\nUsage: %s <filename>\n\n", argv[0]);
	return 1;
    }
    infile = fopen(argv[1], "r");
    if (infile == NULL) {
	printf("\nFailed to open file: %s \n\n", argv[1]);
	return 2;
    }
    T.ROOT = (btnode *)0;
    while (fscanf(infile, "%s", word) == 1) {
	e = iterative_tree_search(T.ROOT, word);
	if (e != NULL) {
	    e->count++;
	} 
	else {
	    e = make_btnode(word);
	    tree_insert(&T, e);
	}
    }
    fclose(infile);
    inorder_tree_walk(T.ROOT);
    return 0;
}