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

#include "bst_height.h"


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

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

btnode *iterative_tree_search(btnode *x, int key)
{
    while (x != NULL && x->key != key) {
	if (key < x->key)
	    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;
    int height = 0;
    y = NULL;
    x = T->ROOT;
    while (x != NULL) {
	height++;
	y = x;
	if (z->key < x->key) x = x->left;
	else x = x->right;
    }
    z->parent = y;
    if (y == NULL) T->ROOT = z; /* tree T was empty */
    else if (z->key < y->key) y->left = z;
    else y->right = z;
    if (height > T->height) T->height = height; 
}


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(int key)
{
    btnode *e = (btnode*) malloc(sizeof(btnode));
    e->key = key;
    return e;
}


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

int main(int argc, char **argv)
{
    int r, i, n, rep, key;
    bstree T;
    btnode *e;
    if (argc != 3) {
	printf("\nUsage: %s <size> <nrep>\n\n", argv[0]);
	return 1;
    }
    n = atoi(argv[1]);
    rep = atoi(argv[2]);
    srandom(time(NULL));

    for (r = 0; r < rep; r++) {
	T.ROOT = (btnode *) NULL;
	T.height = 0;
	for (i = 0; i < n; i++) {
	    key = random();
	    e = make_btnode(key);
	    tree_insert(&T, e);
	    printf("%d ", T.height);
	}
	printf("\n");
    }
    return 0;
}