temelia/src/binary_tree_common.c

/*!
 Temelia - Binary tree <common part> implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/binary_tree_common.h"
#include "include/queue.h"
#include <stdlib.h>

static binary_search_tree_t __binary_search_tree_remove(
		binary_search_tree_t *bst, binary_search_tree_t deleted);

/*
 * Forward declaration
 *
 * common.c: line 166
 */
extern int temelia_inited;
void temelia_init();

_binary_tree_t _binary_tree_new(void *key)
{
	_binary_tree_t tree;

	if (!temelia_inited)
		temelia_init();

	tree = (struct _bt_node_t *) _new(sizeof(struct _bt_node_t));

	/*
	 * Encapsulates the key into a node with NULL children.
	 */
	tree->key = key;
	tree->parent = tree->left = tree->right = NULL;

	return tree;
}

void _binary_tree_delete_node(_binary_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);

	/*
	 * Sets the internal pointers to NULL.
	 */
	node->key = node->parent = node->left = node->right = NULL;

	_delete(node);
}

void _binary_tree_delete(_binary_tree_t tree)
{
	_ASSERT(tree, ==, NULL, NULL_POINTER,);

	/*
	 * delete(node)
	 * 	delete the left child
	 * 	delete the right child
	 * 	delete the current node
	 */
	_binary_tree_delete(tree->left);
	_binary_tree_delete(tree->right);
	_binary_tree_delete_node(tree);
}

int _binary_tree_compare_trees(_binary_tree_t bt1, _binary_tree_t bt2,
		int compare(void *x, void *y, void *context), void *context)
{
	int left, right, aux;

	/*
	 * Two NULL trees are equal.
	 */
	if (bt1 == NULL && bt2 == NULL)
		return 0;

	/*
	 * If the first tree is NULL then
	 * 		return compare(NULL, root key of the second tree)
	 * else if the second tree is NULL then
	 * 		return compare(root key of the first tree, NULL)
	 * else
	 * 		left = compare(left1, left2);
	 * 		right = compare(left1, right2);
	 * 		if left trees differ
	 * 			return left;
	 * 		if root's keys differ
	 * 			return comparison result of the keys
	 * 		return the right
	 */
	_ASSERT(bt1, ==, NULL, NULL_POINTER,
			/* compare(NULL, _binary_tree_get_key(bt2), context) */ -1);
	_ASSERT (bt2, ==, NULL, NULL_POINTER,
			/* compare(_binary_tree_get_key(bt1), NULL, context) */ 1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, 0);

	left = right = aux = 0;

	left = _binary_tree_compare_trees(bt1->left, bt1->left, compare, context);
	right
			= _binary_tree_compare_trees(bt1->right, bt2->right, compare,
					context);

	if (left)
		return left;

	aux = compare(bt1->key, bt2->key, context);

	if (aux)
		return aux;

	return right;
}

int _binary_tree_is_empty(_binary_tree_t tree)
{
	_ASSERT(tree, ==, NULL, NULL_POINTER, -1);

	/*
	 * An empty tree has all it's internal pointers equal to NULL
	 */
	return ((tree->left == NULL) && (tree->parent == NULL) && (tree->right
			== NULL) && (tree->key == NULL));
}

int _binary_tree_leaf(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	/*
	 * A node is leaf only if it's children are NULL.
	 */
	return ((node->left == NULL) && (node->right == NULL));
}

int _binary_tree_get_size(_binary_tree_t tree)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION, 0);

	/*
	 * size(NULL) = 0
	 * size(node) = 1 + size(left child) + size(right child)
	 */
	return _binary_tree_get_size(tree->left) + _binary_tree_get_size(
			tree->right) + 1;
}

_binary_tree_t _binary_tree_get_root(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	while (node->parent != NULL)
		node = node->parent;

	return node;
}

void *_binary_tree_get_key(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->key;
}

void _binary_tree_set_key(_binary_tree_t node, void *key)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);

	node->key = key;
}

_binary_tree_t _binary_tree_get_parent(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->parent;
}

void _binary_tree_set_parent(_binary_tree_t node, _binary_tree_t parent,
		int dir)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);
	_ASSERT(parent, ==, NULL, NULL_POINTER,);

	if (dir == -1)
		_binary_tree_set_left_child(parent, node);
	else if (dir == 1)
		_binary_tree_set_right_child(parent, node);
	else
		temelia_errno = INVALID_INPUT;
}

_binary_tree_t _binary_tree_get_left_child(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->left;
}

void _binary_tree_set_left_child(_binary_tree_t node, _binary_tree_t child)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);

	node->left = child;

	// If NULL left child is given, don't set the parent link.
	if (child)
		child->parent = node;
}

_binary_tree_t _binary_tree_get_right_child(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->right;
}

void _binary_tree_set_right_child(_binary_tree_t node, _binary_tree_t child)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);

	node->right = child;

	// If NULL right child is given, don't set the parent link.
	if (child)
		child->parent = node;
}

void _binary_tree_join(_binary_tree_t parent, _binary_tree_t left,
		_binary_tree_t right)
{
	_ASSERT(right, ==, NULL, NULL_POINTER,);
	_ASSERT(left, ==, NULL, NULL_POINTER,);
	_ASSERT(parent, ==, NULL, NULL_POINTER,);

	/*
	 * Creates links between parent<->left and parent<->right
	 * 	                            parent
	 * 	parent, left, right =>      /    \
	 *                              left   right
	 */
	_binary_tree_set_left_child(parent, left);
	_binary_tree_set_right_child(parent, right);
	_binary_tree_set_parent(left, parent, -1);
	_binary_tree_set_parent(right, parent, 1);
}

void _binary_tree_split(_binary_tree_t parent, _binary_tree_t *left,
		_binary_tree_t *right)
{
	_ASSERT(parent, ==, NULL, NULL_POINTER,);
	_ASSERT(left, ==, NULL, NULL_POINTER,);
	_ASSERT(right, ==, NULL, NULL_POINTER,);

	/*
	 * Splits the tree into 3 trees
	 *      parent
	 *      /    \       => parent, left, right
	 *    left   right
	 */
	*left = parent->left;
	parent->left = NULL;

	*right = parent->right;
	parent->right = NULL;
}

_binary_tree_t _binary_tree_create_node(_binary_tree_t parent,
		_binary_tree_t left, _binary_tree_t right, void *key, int dir)
{
	_binary_tree_t new_node = _binary_tree_new(key);

	_ASSERT(parent, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(new_node, ==, NULL, NULL_POINTER, NULL);

#ifndef RELEASE
	if (left && _binary_tree_get_parent(left) != parent)
		LOGGER(
				"[_binary_tree_create_node] invalid parent pointer %p for left child %p\n",
				parent, left);
	if (right && _binary_tree_get_parent(right) != parent)
		LOGGER(
				"[_binary_tree_create_node] invalid parent pointer %p for left child %p\n",
				parent, right);
#endif

	_binary_tree_set_left_child(new_node, left);
	_binary_tree_set_right_child(new_node, right);

	/*
	 * dir == -1
	 * parent, left, right, key =>       parent
	 *                                  /
	 *                          new_node(key)
	 *                          /          \
	 *                        left        right
	 *
	 * dir == 1
	 * parent, left, right, key =>         parent
	 *                                         \
	 *                                       new_node(key)
	 *                                       /       \
	 *                                       left   right
	 */

	if (dir == -1)
		_binary_tree_set_left_child(parent, new_node);
	else if (dir == 1)
		_binary_tree_set_right_child(parent, new_node);
	else
	{
		temelia_errno = INVALID_INPUT;
		return NULL;
	}
	return new_node;
}

int _binary_tree_get_height(_binary_tree_t tree)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION, 0);

	return 1 + MAX(_binary_tree_get_height(tree->left),
			_binary_tree_get_height(tree->right));
}

int _binary_tree_get_depth(_binary_tree_t node)
{
	_ASSERT(node, ==, NULL, NOT_EXCEPTION, -1);

	return 1 + _binary_tree_get_depth(_binary_tree_get_parent(node));
}

void _binary_tree_preorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	key_handler(tree->key, context);
	_binary_tree_preorder(tree->left, key_handler, context);
	_binary_tree_preorder(tree->right, key_handler, context);
}

void _binary_tree_inorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_binary_tree_inorder(tree->left, key_handler, context);
	key_handler(tree->key, context);
	_binary_tree_inorder(tree->right, key_handler, context);
}

void _binary_tree_reverse_inorder(_binary_tree_t tree, void key_handler(
		void *key, void *context), void *context)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_binary_tree_reverse_inorder(tree->right, key_handler, context);
	key_handler(tree->key, context);
	_binary_tree_reverse_inorder(tree->left, key_handler, context);
}

void _binary_tree_postorder(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_binary_tree_postorder(tree->left, key_handler, context);
	_binary_tree_postorder(tree->right, key_handler, context);
	key_handler(tree->key, context);
}

void _binary_tree_level_order(_binary_tree_t tree, void key_handler(void *key,
		void *context), void *context)
{
	queue_t Q = queue_new(DEFAULT_SIZE);
	_binary_tree_node_t current_node;
	queue_push_back(Q, tree);

	while (!queue_is_empty(Q))
	{
		current_node = queue_get_front(Q);
		queue_pop_front(Q);
		key_handler(current_node->key, context);

		if (current_node->left)
			queue_push_back(Q, current_node->left);

		if (current_node->right)
			queue_push_back(Q, current_node->right);
	}

	queue_delete(Q);
}

void _binary_tree_show_indented(_binary_tree_t tree, void key_handler(
		void *key, int level, void *context), void *context, int level)
{
	_ASSERT(tree, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_binary_tree_show_indented(tree->right, key_handler, context, level + 1);
	key_handler(tree->key, level, context);
	_binary_tree_show_indented(tree->left, key_handler, context, level + 1);
}

_binary_search_tree_node_t _binary_search_tree_search(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context)
{
	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	// If the key is in the current tree node, return node's reference.
	if (!compare(bst->key, key, context))
		return bst;
	// If the current key is greater then root's key, search the key in the left sub-tree
	if (compare(key, bst->key, context) < 0)
		return _binary_search_tree_search(bst->left, key, compare, context);
	// Else search in the right sub-tree.
	return _binary_search_tree_search(bst->right, key, compare, context);
}

_binary_search_tree_node_t _binary_search_tree_insert(binary_search_tree_t bst,
		void *key, int compare(void *x, void *y, void *context), void *context)
{
	int direction = 0;
	_binary_search_tree_node_t aux, pred;

	LOGGER(
			"[{internal} binary search tree insert] bst %p, key %p, compare %p, context %p\n",
			bst, key, compare, context);

	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	if (_binary_tree_is_empty(bst))
		return NULL;

	aux = bst;
	while (aux)
	{
		pred = aux;
		// If key already exists, return NULL.
		if (!compare(key, aux->key, context))
			return NULL;
		// If key is lower than node's key then go to left node.
		if (compare(key, aux->key, context) < 0)
		{
			aux = aux->left;
			direction = -1;
		}
		// Else go to right node.
		else
		{
			aux = aux->right;
			direction = 1;
		}
	}
	/*
	 * Creates the new node in the computed direction; set it a parent and NULL children.
	 */
	return _binary_tree_create_node(pred, NULL, NULL, key, direction);
}

_binary_search_tree_node_t _binary_search_tree_remove(
		binary_search_tree_t *bst, void *key, int compare(void *x, void *y,
				void *context), void *context, binary_search_tree_t *my_deleted)
{
	void *aux;
	binary_tree_node_t deleted, replaced;

	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT (*bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	deleted = _binary_search_tree_search(*bst, key, compare, context);
	*my_deleted = NULL;
	_ASSERT(deleted, ==, NULL, ELEMENT_NOT_FOUND, NULL);

	// There are 4 cases :
	// 1) deleted node is leaf : simply remove it.
	// 2) deleted node has 1 child : change child's parent to deleted node's parent.
	// 3) deleted node has 2 children : swap between the right child and parent; and rebuild the links.
	// 4) deleted node is the root.

	if (deleted->left != NULL && deleted->right != NULL)
	{
		replaced = _binary_search_tree_next(*bst, deleted);
		aux = deleted->key;
		deleted->key = replaced->key;
		replaced->key = aux;
		*my_deleted = replaced;
		return __binary_search_tree_remove(bst, replaced);
	}

	*my_deleted = deleted;
	return __binary_search_tree_remove(bst, deleted);
}

_binary_search_tree_node_t _binary_search_tree_get_min(binary_search_tree_t bst)
{
	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);

	// The minimum key is in the most left node of tree.
	while (bst->left)
		bst = bst->left;
	return bst;
}

_binary_search_tree_node_t _binary_search_tree_get_max(binary_search_tree_t bst)
{

	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);

	// The minimum key is in the most right node of tree.
	while (bst->right)
		bst = bst->right;
	return bst;
}

_binary_search_tree_node_t _binary_search_tree_next(binary_search_tree_t bst,
		_binary_search_tree_node_t node)
{
	_binary_search_tree_node_t parent;

	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(node->key, ==, _binary_search_tree_get_max(bst), INVALID_INPUT, NULL);

	/*
	 * If the current node has a right child
	 * then the next key is the minimum key of the right child tree.
	 * Else move to the tree until node == parent(node)->right
	 * and then return the parent; that's because it would have node as
	 * left child and the next key would be in the parent.
	 */

	if (node->right)
		return _binary_search_tree_get_min(node->right);

	parent = node->parent;

	while (parent->right == node)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

_binary_search_tree_node_t _binary_search_tree_prev(binary_search_tree_t bst,
		_binary_search_tree_node_t node)
{
	_binary_search_tree_node_t parent;
	_ASSERT(bst, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(node, ==, node, NULL_POINTER, NULL);
	_ASSERT(node, ==, _binary_search_tree_get_max(bst), INVALID_INPUT, NULL);

	/*
	 * If the current node has a left child
	 * then the prev (previous) key is the maximum key of the left child tree.
	 * Else move to the tree until node == parent(node)->left
	 * and then return the parent; that's because it would have node as
	 * right child and the previous key would be in the parent.
	 */

	if (node->left)
		return _binary_search_tree_get_max(node->left);
	parent = node->parent;

	while (parent->left == node)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

static binary_search_tree_t __binary_search_tree_remove(
		binary_search_tree_t *bst, binary_search_tree_t deleted)
{
	int dir = 0;
	binary_search_tree_t parent = NULL, replaced = NULL;

	parent = deleted->parent;

	if (deleted->left)
		replaced = deleted->left;
	else
		replaced = deleted->right;

	if (parent)
	{
		if (parent->left == deleted)
			dir = -1;
		else
			dir = 1;
	}
	else if (replaced)
	{
		replaced->parent = NULL;
		*bst = replaced;
	}

	if (replaced)
		_binary_tree_set_parent(replaced, parent, dir);
	else if (parent)
	{
		if (dir == -1)
			parent->left = NULL;
		else
			parent->right = NULL;
	}

	return replaced;
}

_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left(
		_binary_search_tree_node_t x)
{
	_binary_search_tree_node_t y, px, b;

	_ASSERT(x, ==, NULL, NULL_POINTER, NULL);

	/*     Y              X
	 *    / \            / \
	 *   X   a   <=     c   Y
	 *  / \                / \
	 * c   b              b   a
	 */

	y = x->right;

	_ASSERT(y, ==, NULL, NULL_POINTER, x);

	b = y->left;
	x->right = b;
	y->left = x;

	px = x->parent;
	x->parent = y;
	if (b)
		b->parent = x;
	y->parent = px;

	if (px != NULL)
	{
		if (px->left == x)
			px->left = y;
		else
			px->right = y;
	}

	return y;
}

_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_right(
		_binary_search_tree_node_t x)
{
	_binary_search_tree_node_t y, px, b;

	_ASSERT(x, ==, NULL, NULL_POINTER, NULL);

	/*     X              Y
	 *    / \            / \
	 *   Y   a   =>     c   X
	 *  / \                / \
	 * c   b              b   a
	 */

	y = x->left;

	_ASSERT(y, ==, NULL, NULL_POINTER, x);

	b = y->right;
	x->left = b;
	y->right = x;

	px = x->parent;
	x->parent = y;
	if (b)
		b->parent = x;
	y->parent = px;

	if (px != NULL)
	{
		if (px->left == x)
			px->left = y;
		else
			px->right = y;
	}

	return y;
}

_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_left_double(
		_binary_search_tree_node_t x)
{
	_ASSERT(x, ==, NULL, INVALID_INPUT, NULL);

	x->right = _self_balanced_binary_search_tree_rotate_right(x->right);

	return _self_balanced_binary_search_tree_rotate_left(x);
}

_binary_search_tree_node_t _self_balanced_binary_search_tree_rotate_right_double(
		_binary_search_tree_node_t x)
{
	_ASSERT(x, ==, NULL, INVALID_INPUT, NULL);

	x->left = _self_balanced_binary_search_tree_rotate_left(x->left);

	return _self_balanced_binary_search_tree_rotate_right(x);
}