/**
 *  Binary Search Tree (BST) ANSI C implementation
 *  Copyright (C) 2010 Matous Jan Fialka, <http://mjf.cz/>
 *  Released under the terms of The MIT License
 */

#include <stdlib.h>

#ifndef NULL
#define NULL ((void *)0)
#endif

#define nil NULL

typedef struct bstnode bstnode;
typedef struct bst bst;

struct bstnode {
	void *data;
	bstnode *left;
	bstnode *parent;
	bstnode *right;
};

struct bst {
	bstnode *root;
};

bst *
bst_create(void)
{
	bst *tree;

	tree = (bst *) malloc(sizeof(bst));
	if(tree) {
		tree->root = nil;
	}
	return tree;
}

void
bst_preorder_walk(bstnode * node, void (*call) ())
{
	if(node) {
		call(node->data);
		bst_preorder_walk(node->left, call);
		bst_preorder_walk(node->right, call);
	}
}

void
bst_inorder_walk(bstnode * node, void (*call) ())
{
	if(node) {
		bst_inorder_walk(node->left, call);
		call(node->data);
		bst_inorder_walk(node->right, call);
	}
}

void
bst_postorder_walk(bstnode * node, void (*call) ())
{
	if(node) {
		bst_postorder_walk(node->left, call);
		bst_postorder_walk(node->right, call);
		call(node->data);
	}
}

bstnode *
bst_search(bstnode * node, void *data, int (*compare) ())
{
	int comparison;

	if(!node) {
		return node;
	}
	comparison = compare(data, node->data);
	if(comparison == 0) {
		return node;
	}
	if(comparison < 0) {
		return bst_search(node->left, data, compare);
	}
	return bst_search(node->right, data, compare);
}

bstnode *
bst_iterative_search(bstnode * node, void *data, int (*compare) ())
{
	int comparison;

	while(node) {
		comparison = compare(data, node->data);
		if(comparison == 0) {
			break;
		}
		if(comparison < 0) {
			node = node->left;
			continue;
		}
		node = node->right;
	}
	return node;
}

bstnode *
bst_minimum(bstnode * node)
{
	while(node->left) {
		node = node->left;
	}
	return node;
}

bstnode *
bst_maximum(bstnode * node)
{
	while(node->right) {
		node = node->right;
	}
	return node;
}

bstnode *
bst_successor(bstnode * node)
{
	bstnode *parent;

	if(node->right) {
		return bst_minimum(node->right);
	}
	parent = node->parent;
	while(parent && node == parent->right) {
		node = parent;
		parent = parent->parent;
	}
	return parent;
}

bstnode *
bst_create_node(void *data)
{
	bstnode *node;

	node = malloc(sizeof(bstnode));
	if(node) {
		node->data = data;
		node->parent = nil;
		node->left = nil;
		node->right = nil;
	}
	return node;
}

void
bst_insert(bst * tree, bstnode * node, int (*compare) ())
{
	bstnode *parent;
	bstnode *root;

	parent = nil;
	root = tree->root;
	while(root) {
		parent = root;
		if(compare(node->data, root->data) < 0) {
			root = root->left;
		} else {
			root = root->right;
		}
	}
	node->parent = parent;
	if(!parent) {
		tree->root = node;
	} else {
		if(compare(node->data, parent->data) < 0) {
			parent->left = node;
		} else {
			parent->right = node;
		}
	}
}

bstnode *
bst_delete(bst * tree, bstnode * node, int (*compare) ())
{
	bstnode *parent;
	bstnode *root;

	if(!node->left || !node->right) {
		parent = node;
	} else {
		parent = bst_successor(node);
	}
	if(parent->left) {
		root = parent->left;
	} else {
		root = parent->right;
	}
	if(root) {
		root->parent = parent->parent;
	}
	if(!parent->parent) {
		tree->root = root;
	} else {
		if(parent == parent->parent->left) {
			parent->parent->left = root;
		} else {
			parent->parent->right = root;
		}
	}
	if(compare(parent, node) != 0) {
		node->data = parent->data;
	}
	return parent;
}