temelia/src/avl_tree.c

/*!
 Temelia - AVL tree implementation source file.

 Some operations are adapted from the article:
 http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai

 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/avl_tree.h"
#include "include/stack.h"
#include <stdlib.h>

/*!
 * Because AVL trees works with nodes height, I keep additional two parameters in a node.
 * User should not access this structure directly.
 */
struct _avl_tree_node_t
{
	/*! user's key */
	void *key;

	/*! node's height */
	int height;
};

#define GET_AVL_MEMBER(x, member) (((avl_tree_node_t)(x))->member)

/*!
 *   Internal functions used to make the layer between AVL and BST invisible for the user.
 * Because I don't have OOP in C i'm abusing pointers in order to change functions behavior.
 */
extern stack_t compare_stack;
extern stack_t iterating_handlers;

//! Encapsulates a key into an avl tree node.
static avl_tree_node_t _avl_tree_node_new(void *key, int height);

//! Compares two avl tree nodes. For comparing the keys, library uses a global
//! pointer where the function given by the user is stored.

static int _avl_tree_internal_compare(void *x, void *y, void *context);

//! Wrapper printing functions over user input.
static void
_avl_tree_internal_printing_level(void *x, int level, void *context);

static void _avl_tree_internal_handling(void *x, void *context);

static avl_tree_t _avl_tree_balance(avl_tree_t x);

static void _avl_tree_node_delete_node(avl_tree_node_t node);

static void _avl_tree_debug(avl_tree_t avl, void key_handler(void *x,
		int height, int level, void *context), void *context, int level);

void *avl_tree_node_get_key(avl_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->key;
}

int avl_tree_node_get_height(avl_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	return node->height;
}

avl_tree_t avl_tree_new(void *key)
{
	LOGGER("[avl tree new] key %p\n", key);
	return _binary_tree_new(_avl_tree_node_new(key, 1));
}

void avl_tree_delete_node(avl_tree_t avl)
{
	LOGGER("[avl tree delete node] node %p\n", avl);

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

	if (_binary_tree_get_key(avl))
		_avl_tree_node_delete_node(_binary_tree_get_key(avl));
	_delete(avl);
}

void avl_tree_delete(avl_tree_t avl)
{
	LOGGER("[avl tree delete] node %p\n", avl);

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

	if (_binary_tree_get_left_child(avl))
		avl_tree_delete(_binary_tree_get_left_child(avl));

	if (_binary_tree_get_right_child(avl))
		avl_tree_delete(_binary_tree_get_right_child(avl));

	avl_tree_delete_node(avl);
}

int avl_tree_compare_trees(avl_tree_t avl1, avl_tree_t avl2, int compare(
		void *x, void *y, void *context), void *context)
{
	int result;

	LOGGER(
			"[avl tree compare trees] tree1 %p, tree2 %p, compare %p, context %p\n",
			avl1, avl2, compare, context);

	_ASSERT(avl1, ==, NULL, NULL_POINTER, -1);
	_ASSERT(avl2, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	stack_push(compare_stack, compare);

	result = _binary_tree_compare_trees(avl1, avl2, _avl_tree_internal_compare,
			context);

	stack_pop(compare_stack);

	return result;
}

int avl_tree_is_empty(avl_tree_t avl)
{
	LOGGER("[avl tree is empty] node %p\n", avl);

	_ASSERT(avl, ==, NULL, NULL_POINTER, -1);

	return (_binary_tree_get_parent(avl) == NULL)
			&& (_binary_tree_get_left_child(avl) == NULL)
			&& (_binary_tree_get_right_child(avl) == NULL)
			&& (GET_AVL_MEMBER(_binary_tree_get_key(avl), key) == NULL);
}

int avl_tree_is_leaf(avl_tree_t avl)
{
	return _binary_tree_leaf(avl);
}

int avl_tree_get_size(avl_tree_t avl)
{
	return _binary_tree_get_size(avl);
}

avl_tree_t avl_tree_get_root(avl_tree_t avl)
{
	return _binary_tree_get_root(avl);
}

void *avl_tree_get_key(avl_tree_t avl)
{
	return _binary_tree_get_key(avl);
}

avl_tree_t avl_tree_get_parent(avl_tree_t avl)
{
	return _binary_tree_get_parent(avl);
}

avl_tree_t avl_tree_get_left_child(avl_tree_t avl)
{
	return _binary_tree_get_left_child(avl);
}

avl_tree_t avl_tree_get_right_child(avl_tree_t avl)
{
	return _binary_tree_get_right_child(avl);
}

int avl_tree_get_height(avl_tree_t avl)
{
	avl_tree_node_t node;

	_ASSERT(avl, ==, NULL, NULL_POINTER, -1);

	node = _binary_tree_get_key(avl);

	return node->height;
}

int avl_tree_get_depth(avl_tree_t avl)
{
	return _binary_tree_get_depth(avl);
}

avl_tree_t avl_tree_search(avl_tree_t avl, void *key, int compare(void *x,
		void *y, void *context), void *context)
{
	/*
	 * Encapsulate key into a node and search for that node in the tree.
	 * After the search is completed, free the memory allocated for the auxiliary node
	 * and return whatever search returns.
	 */

	avl_tree_node_t search_node = _avl_tree_node_new(key, 0);
	avl_tree_t result;

	stack_push(compare_stack, compare);

	result = _binary_search_tree_search(avl, search_node,
			_avl_tree_internal_compare, context);
	_avl_tree_node_delete_node(search_node);

	stack_pop(compare_stack);

	return result;
}

avl_tree_t avl_tree_insert(avl_tree_t *avl, void *key, int compare(void *x,
		void *y, void *context), void *context, int adjust_root)
{
	avl_tree_t add = NULL, add_returned;
	avl_tree_node_t add_node = NULL;
	avl_tree_node_t root;

	_ASSERT(avl, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(*avl, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(key, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	root = (avl_tree_node_t) (*avl)->key;

	// NULL key in the root means empty tree
	if (root->key == NULL)
	{
		root->key = key;
		return *avl;
	}

	stack_push(compare_stack, compare);
	// Add the node as in a binary search tree and then start tree balancing.

	// If the key already exists, I have to free the memory allocated by
	// the encapsulation layer.
	add_node = _avl_tree_node_new(key, 1);
	add = _binary_search_tree_insert(*avl, add_node,
			_avl_tree_internal_compare, context);

	if (add == NULL)
	{
		_avl_tree_node_delete_node(add_node);
		return NULL;
	}

	add_returned = add;

	add = add->parent;

	while (add)
	{
		LOGGER("[avl_tree_insert] moving from %p to it's parent %p\n", add,
				add->parent);
		add = _avl_tree_balance(add);
		if (add)
			add = add->parent;
	}

	while (adjust_root && (*avl)->parent)
		*avl = (*avl)->parent;

	stack_pop(compare_stack);

	return add_returned;
}

int avl_tree_remove(avl_tree_t *avl, void *key, int compare(void *x, void *y,
		void *context), void *context, int adjust_root)
{
	avl_tree_t replaced = NULL, my_deleted = NULL;
	avl_tree_node_t key_encapsulated = NULL;

	_ASSERT(avl, ==, NULL, NULL_POINTER, -1);
	_ASSERT(*avl, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);

	if (compare(key, GET_AVL_MEMBER((*avl)->key, key), context) == 0
			&& (*avl)->parent == NULL && (*avl)->left == NULL && (*avl)->right
			== NULL)
	{
		avl_tree_delete(*avl);
		*avl = NULL;
		return 0;
	}

	stack_push(compare_stack, compare);

	/*
	 * Remove the node as in a binary search tree and then start tree balancing.
	 */
	key_encapsulated = _avl_tree_node_new(key, 0);
	replaced = _binary_search_tree_remove(avl, key_encapsulated,
			_avl_tree_internal_compare, context, &my_deleted);

	_avl_tree_node_delete_node(key_encapsulated);

	_ASSERT(my_deleted, ==, NULL, ELEMENT_NOT_FOUND, -1);

	avl_tree_delete_node(my_deleted);

	while (replaced)
	{
		LOGGER("[avl_tree_remove] moving from %p to it's parent %p\n",
				replaced, replaced->parent);
		replaced = _avl_tree_balance(replaced);
		if (replaced)
			replaced = replaced->parent;
	}

	while (adjust_root && (*avl)->parent)
		*avl = (*avl)->parent;

	stack_pop(compare_stack);

	return 0;
}

avl_tree_t avl_tree_get_min(avl_tree_t avl)
{
	return _binary_search_tree_get_min(avl);
}

avl_tree_t avl_tree_get_max(avl_tree_t avl)
{
	return _binary_search_tree_get_max(avl);
}

void avl_tree_preorder(avl_tree_t avl,
		void key_handler(void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_preorder(avl, _avl_tree_internal_handling, context);
	stack_pop(iterating_handlers);
}

void avl_tree_inorder(avl_tree_t avl, void key_handler(void *x, void *context),
		void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_inorder(avl, _avl_tree_internal_handling, context);
	stack_pop(iterating_handlers);
}

void avl_tree_reverse_inorder(avl_tree_t avl, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_reverse_inorder(avl, _avl_tree_internal_handling, context);
	stack_pop(iterating_handlers);
}

void avl_tree_postorder(avl_tree_t avl,
		void key_handler(void *x, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_postorder(avl, _avl_tree_internal_handling, context);
	stack_pop(iterating_handlers);
}

void avl_tree_level_order(avl_tree_t avl, void key_handler(void *x,
		void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_level_order(avl, _avl_tree_internal_handling, context);
	stack_pop(iterating_handlers);
}

void avl_tree_show_indented(avl_tree_t avl, void key_handler(void *x,
		int level, void *context), void *context)
{
	stack_push(iterating_handlers, key_handler);
	_binary_tree_show_indented(avl, _avl_tree_internal_printing_level, context,
			0);
	stack_pop(iterating_handlers);
}

static avl_tree_node_t _avl_tree_node_new(void *key, int height)
{
	avl_tree_node_t node;

	node = (avl_tree_node_t) _new(sizeof(struct _avl_tree_node_t));
	node->key = key;
	node->height = height;

	return node;
}

static int _avl_tree_internal_compare(void *x, void *y, void *context)
{
	/*
	 * This is the callback function and can compare AVL tree nodes
	 *
	 * For comparing key from nodes, I save the user comparison function in a global pointers stack
	 */
	int (*user_comparison_function)(void *, void *, void *);

	user_comparison_function = stack_top(compare_stack);
	_ASSERT(user_comparison_function, ==, NULL, NULL_POINTER, -1);

	return user_comparison_function(GET_AVL_MEMBER(x, key),
			GET_AVL_MEMBER(y, key), context);
}

static void _avl_tree_internal_printing_level(void *x, int level, void *context)
{
	void (*user_printing_function_level)(void *, int, void *);

	user_printing_function_level = stack_top(iterating_handlers);

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

	user_printing_function_level(GET_AVL_MEMBER(x, key), level, context);
}

static void _avl_tree_internal_handling(void *x, void *context)
{
	void (*user_handling_function)(void *, void *);

	user_handling_function = stack_top(iterating_handlers);

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

	user_handling_function(GET_AVL_MEMBER(x, key), context);
}

/*
 * Code taken from infoarena.ro
 */
static void geth(avl_tree_t node)
{
	avl_tree_t left, right;
	int left_height, right_height;

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

	if (left && left->key)
		left_height = ((avl_tree_node_t) node->left->key)->height;
	else
		left_height = 0;

	if (right && right->key)
		right_height = ((avl_tree_node_t) node->right->key)->height;
	else
		right_height = 0;

	((avl_tree_node_t) node->key)->height = 1 + MAX(left_height, right_height);
}

static avl_tree_t rotleft(avl_tree_t x)
{
	avl_tree_t y, px, b;

	_ASSERT(x, ==, NULL, NULL_POINTER, NULL);
	y = x->left;
	_ASSERT(y, ==, NULL, NULL_POINTER, x);

	LOGGER("[avl tree rotate LEFT] %p %p\n", x, y);

	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;
	}

	geth(x);
	geth(y);

	return y;
}

static avl_tree_t rotright(avl_tree_t x)
{
	avl_tree_t y, px, b;

	_ASSERT(x, ==, NULL, NULL_POINTER, NULL);
	y = x->right;
	_ASSERT(y, ==, NULL, NULL_POINTER, x);

	LOGGER("[avl tree rotate RIGHT] %p %p\n", x, y);

	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;
	}

	geth(x);
	geth(y);

	return y;
}

static avl_tree_t _avl_tree_balance(avl_tree_t x)
{
	avl_tree_t left, right, aux_left, aux_right;
	avl_tree_node_t key;
	int left_height, right_height;

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

	left = avl_tree_get_left_child(x);
	right = avl_tree_get_right_child(x);

	key = x->key;

	if (left && left->key)
		left_height = GET_AVL_MEMBER(left->key, height);
	else
		left_height = 0;

	if (right && right->key)
		right_height = GET_AVL_MEMBER(right->key, height);
	else
		right_height = 0;

	key->height = 1 + MAX(left_height, right_height);

	LOGGER("[_avl_tree_balance] node %d, left %d, right %d\n", key->height,
			left_height, right_height);

	if (left_height > right_height + 1)
	{
		aux_left = avl_tree_get_left_child(left);
		aux_right = avl_tree_get_right_child(left);

		if (aux_left && aux_left->key && aux_right && aux_right->key
				&& GET_AVL_MEMBER(aux_left->key, height)
						< GET_AVL_MEMBER(aux_right->key, height))
			x->left = rotright(x->left);

		x = rotleft(x);
	}
	else if (right_height > left_height + 1)
	{
		aux_left = avl_tree_get_left_child(right);
		aux_right = avl_tree_get_right_child(right);

		if (aux_left && aux_left->key && aux_right && aux_right->key
				&& GET_AVL_MEMBER(aux_left->key, height)
						< GET_AVL_MEMBER(aux_right->key, height))
			x->right = rotleft(x->right);

		x = rotright(x);
	}

	return x;
}

static void _avl_tree_node_delete_node(avl_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER,);

	_delete(node);
}

void avl_tree_debug(avl_tree_t avl, void key_handler(void *x, int height,
		int level, void *context), void *context)
{
	_avl_tree_debug(avl, key_handler, context, 0);
}

static void _avl_tree_debug(avl_tree_t avl, void key_handler(void *x,
		int height, int level, void *context), void *context, int level)
{
	_ASSERT(avl, ==, NULL, NOT_EXCEPTION,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_avl_tree_debug(avl->right, key_handler, context, level + 1);
	key_handler(GET_AVL_MEMBER(avl->key, key),
			GET_AVL_MEMBER(avl->key, height), level, context);
	_avl_tree_debug(avl->left, key_handler, context, level + 1);
}