/*
 * bbTree (balanced binary tree)
 */
#include <malloc.h>
#include <stdio.h>
#include <string.h>

#include <helper.h>
#include <bbtree.h>

/*
 * statisch Funktionen
 */
static
	s_bbTreeNode *
bbTreeNodeNew(void * value)
{
	s_bbTreeNode * new = (s_bbTreeNode*)malloc(sizeof(s_bbTreeNode));

	new->value  = value;
	new->left   = NULL;
	new->right  = NULL;
	new->height = 0;

	return new;
}

static
	void
bbTreeNodeFree(s_bbTreeNode * t)
{
	if (t == NULL)
		return;

	while (t->left != NULL) {
		bbTreeNodeFree(t->left);
		t->left = NULL;
	}

	while (t->right != NULL) {
		bbTreeNodeFree(t->right);
		t->right = NULL;
	}

	free (t);
}

static
	void
bbTreeNodeRotLeft(s_bbTreeNode * node)
{
	s_bbTreeNode * left  = node->left;
	s_bbTreeNode * right = node->right;
	void *         value = node->value;

	node->right  = right->right;
	node->left   = right;
	right->right = right->left;
	right->left  = left;

	node->value  = right->value;
	right->value = value;

	node->right->height =
		1 + MAX(BBTREE_LEFT_HEIGHT(node->left),
				BBTREE_RIGHT_HEIGHT(node->left));
}

static
	void
bbTreeNodeRotRight(s_bbTreeNode * node)
{
	s_bbTreeNode * left  = node->left;
	s_bbTreeNode * right = node->right;
	void *         value = node->value;

	node->left  = left->left;
	node->right = left;
	left->left  = left->right;
	left->right = right;

	node->value = left->value;
	left->value = value;

	node->right->height =
		1 + MAX(BBTREE_LEFT_HEIGHT(node->right),
				BBTREE_RIGHT_HEIGHT(node->right));
}

static
	void
bbTreeNodeBalance(s_bbTreeNode * node)
{
	if (BBTREE_AVL(node) == -2) {
		/* left is to long */
		if (BBTREE_AVL(node->left) == 1)
			bbTreeNodeRotLeft(node->left);
		bbTreeNodeRotRight(node);
	}

	if (BBTREE_AVL(node) == -2) {
		/* right is to long */
		if (BBTREE_AVL(node->right) == 1)
			bbTreeNodeRotRight(node->right);
		bbTreeNodeRotLeft(node);
	}
}

/*
 * This function returns either, NULL if a new node was inserted, or
 * a node containing the old value if an existing node was modified.
 */
static
	s_bbTreeNode *
bbTreeNodeInsert(s_bbTreeNode ** _node, t_bbTreeCmp cmp, void * value)
{
	s_bbTreeNode * node = *_node;
	s_bbTreeNode * ret;

	if (node == NULL) {
		/* This happens only when bbTree::root is NULL
		 * on bbTreeInsert call */
		*_node = bbTreeNodeNew(value);
		return NULL;
	}

	if (cmp(value, node->value) == 0) {
		/* The key is already in the tree.
		 * In this case a node containing the old value is returned. */
		ret = bbTreeNodeNew(node->value);
		node->value = value;
		return ret;
	}

	if (cmp(value, node->value) < 0) {
		if (node->left == NULL) {
			node->left = bbTreeNodeNew(value);
			ret = NULL;

			if (BBTREE_AVL(node) == -2 || BBTREE_AVL(node) == 2)
				bbTreeNodeBalance(node);

			node->height = 1 + MAX(
					BBTREE_LEFT_HEIGHT(node), BBTREE_RIGHT_HEIGHT(node));
		}
		else {
			ret = bbTreeNodeInsert(&node->left, cmp, value);
		}
	}

	if (cmp(value, node->value) > 0) {
		if (node->right == NULL) {
			node->right = bbTreeNodeNew(value);
			ret = NULL;

			if (BBTREE_AVL(node) == -2 || BBTREE_AVL(node) == 2)
				bbTreeNodeBalance(node);

			node->height = 1 + MAX(
					BBTREE_LEFT_HEIGHT(node), BBTREE_RIGHT_HEIGHT(node));
		}
		else {
			ret = bbTreeNodeInsert(&node->right, cmp, value);
		}
	}

	/* if we come here a new node was inserted a returned node 
	 * containing {NULL, NULL} as value reflects this fact. */
	return ret;
}

static
	s_bbTreeNode *
bbTreeNodeSeek(s_bbTreeNode * node, t_bbTreeCmp cmp, void * value)
{
	if (node == NULL)
		return NULL;

	if (cmp(value, node->value) == 0)
		return node;

	if (cmp(value, node->value) < 0)
		return bbTreeNodeSeek (node->left, cmp, value);

	if (cmp(value, node->value) > 0)
		return bbTreeNodeSeek (node->right, cmp, value);

	return NULL;
}

static
	s_bbTreeNode *
bbTreeNodeMax(s_bbTreeNode * node)
{
	if (node != NULL && node->right != NULL)
		return bbTreeNodeMax(node->right);

	return node;
}

static
	s_bbTreeNode *
bbTreeNodeMin(s_bbTreeNode * node)
{
	if (node != NULL && node->left != NULL)
		return bbTreeNodeMin(node->left);

	return node;
}

static
	int
bbTreeNodeSize(s_bbTreeNode * node)
{
	int size = 0;

	if (node == NULL)
		return 0;

	size += bbTreeNodeSize(node->left);
	size += bbTreeNodeSize(node->right);

	return size + 1;
}
/*
 * This functions removes nodes from the tree and returns a pointer
 * to the removed node or NULL if no node was found.
 * !!!FIXME!!!: This function isn't thread save because of the static
 * valiables. Don't use with multiple threads.
 */
static
	s_bbTreeNode *
bbTreeNodeRemove(s_bbTreeNode ** _node, t_bbTreeCmp cmp, void * value)
{
	s_bbTreeNode * ret  = NULL;
	s_bbTreeNode * node = *_node;

	if (node == NULL)
		return NULL;

	if (cmp (value, node->value) == 0) {
		/* found the element left */
		if (node->left == NULL && node->right == NULL) {
			/* found a leaf */
			ret = bbTreeNodeNew(node->value);
			free(node);
			*_node = NULL;
		}
		else if (node->left != NULL && node->left != NULL) {
			/* left & right subtree exists use either max(left) or min(right) */
			s_bbTreeNode * maxLeft;

			maxLeft     = bbTreeNodeMax(node->left);
			node->value = maxLeft->value;
			ret = bbTreeNodeRemove(&node->left, cmp, maxLeft->value);

			if (BBTREE_AVL(node) == -2 || BBTREE_AVL(node) == 2)
				bbTreeNodeBalance (node);

			node->height = 1 + MAX(
					BBTREE_LEFT_HEIGHT(node), BBTREE_RIGHT_HEIGHT(node));
		}
		else if ((node->left == NULL) != (node->right == NULL) /* ^^ */) {
			/* there is only one subtree */
			/* This subtree must be a leaf, because the tree is balanced */
			ret = bbTreeNodeNew(node->value);

			if (node->left != NULL) {
				/* found left node */
				node->value = node->left->value;
				free(node->left);
				node->left = NULL;
			}
			else {
				/* found right node */
				node->value = node->right->value;
				free(node->right);
				node->right = NULL;
			}
		}

		return ret;
	}

	if (cmp(value, node->value) < 0)
		ret = bbTreeNodeRemove(&node->left, cmp, value);

	if (cmp(value, node->value) > 0)
		ret = bbTreeNodeRemove(&node->right, cmp, value);

	return ret;
}

static
	void
bbTreeNodeInOrder(const s_bbTreeNode * node, void *** ret)
{
	if (node != NULL && node->left != NULL)
		bbTreeNodeInOrder(node->left, ret);

	if (node != NULL)
		**ret = node->value; (*ret)++;

	if (node != NULL && node->right != NULL)
		bbTreeNodeInOrder(node->right, ret);
}

/*
 * Interface (non-static functions)
 */
	s_bbTree *
bbTreeNew(t_bbTreeCmp cmp)
{
	s_bbTree * new = (s_bbTree*)malloc(sizeof(s_bbTree));

	new->root = NULL;
	new->cmp  = cmp;

	return new;
}

	void
bbTreeFree(s_bbTree * t)
{
	bbTreeNodeFree(t->root);

	free(t);
}

	void *
bbTreeInsert(s_bbTree * t, void * value)
{
	s_bbTreeNode * oldNode = bbTreeNodeInsert(&t->root, t->cmp, value);

	if (oldNode != NULL) {
		value = oldNode->value;
		free(oldNode);

		return value;
	}

	return NULL;
}

	void *
bbTreeSeek(s_bbTree * t, void * value)
{
	s_bbTreeNode * seek = bbTreeNodeSeek(t->root, t->cmp, value);

	return (seek != NULL) ? seek->value : NULL;
}

	void *
bbTreeRemove(s_bbTree * t, void * value)
{
	s_bbTreeNode * oldNode = bbTreeNodeRemove(&t->root, t->cmp, value);

	if (oldNode != NULL) {
		value = oldNode->value;
		free(oldNode);

		return value;
	}

	return NULL;
}

	void *
bbTreeMax(s_bbTree * t)
{
	s_bbTreeNode * max = bbTreeNodeMax(t->root);

	return max == NULL ? max : max->value;
}

	void *
bbTreeMin(s_bbTree * t)
{
	s_bbTreeNode * max = bbTreeNodeMin(t->root);

	return max == NULL ? max : max->value;
}

	int
bbTreeSize(s_bbTree * t)
{
	return bbTreeNodeSize(t->root);
}

	void **
bbTreeInOrder(s_bbTree * t, void ** buffer)
{
	void ** tmp = buffer;

	bbTreeNodeInOrder(t->root, &tmp);

	return buffer;
}