temelia/src/tree.c

/*!
 Temelia - Multipath tree 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/common.h"

#include "include/linked_list.h"
#include "include/vector.h"

#include "include/tree.h"
#include <stdlib.h>

struct _tree_node_t
{
	/*! user's key */
	void *key;

	/*! reference to parent */
	struct _tree_node_t *parent;

	/*! vector/linked list of references to children */
	void *children;

	/*! tree backbone type */
	int var_children_size;
};

static void _tree_delete_handler(void *key, void *context);

tree_t tree_new(void *key, int var_children_size)
{
	tree_t tree;

	LOGGER("[tree new] key=\"%p\" var_children_size=\"%d\"\n", key,
			var_children_size);

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

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

	LOGGER("[tree new] tree=\"%p\"\n", tree);

	if (var_children_size)
	{
		tree->children = linked_list_new();
		LOGGER("[tree new] linked list tree->children=\"%p\"\n", tree->children);
	}
	else
	{
		tree->children = vector_new(DEFAULT_SIZE);
		LOGGER("[tree new] vector tree->children=\"%p\"\n", tree->children);
	}

	// If memory allocation failed return NULL.
	if (tree->children == NULL)
	{
		LOGGER("[tree new] children memory allocation failed\n");
		_delete(tree);
		return NULL;
	}

	tree->key = key;
	tree->parent = NULL;
	tree->var_children_size = var_children_size;

	return tree;
}

void tree_delete_node(tree_t node)
{
	LOGGER("[tree delete node] node=\"%p\"\n", node);

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

	node->key = NULL;
	node->parent = NULL;

	if (node->var_children_size)
		linked_list_delete(node->children);
	else
		vector_delete(node->children);

	_delete(node);
}

void tree_delete(tree_t tree)
{
	LOGGER("[tree delete] tree=\"%p\"\n", tree);

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

	if (tree->var_children_size)
		linked_list_iterate(tree->children, _tree_delete_handler, NULL, 1);
	else
		vector_iterate(tree->children, _tree_delete_handler, NULL);

	tree_delete_node(tree);
}

int tree_get_type(tree_t tree)
{
	LOGGER("[tree get type] tree=\"%p\"\n", tree);

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

	return tree->var_children_size;
}

void tree_set_type(tree_t tree, int variable_children)
{
	LOGGER("[tree set type] tree=\"%p\" variable_children=\"%d\"\n", tree,
			variable_children);

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

	tree->var_children_size = variable_children;
}

void tree_set_key(tree_t node, void *key)
{
	LOGGER("[tree set key] node=\"%p\" key=\"%p\"\n", node, key);

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

	node->key = key;
}

void *tree_get_key(tree_t node)
{
	LOGGER("[tree get key] node=\"%p\" key=\"%p\"\n", node, node->key);

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

	return node->key;
}

tree_t tree_get_parent(tree_t node)
{
	LOGGER("[tree get parent] node=\"%p\" parent=\"%p\"\n", node, node->parent);

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

	return node->parent;
}

void tree_set_parent(tree_t parent, tree_t child)
{
	int added;

	LOGGER("[tree set parent] parent=\"%p\" child=\"%p\"\n", parent, child);

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

	child->parent = parent;

	added = 0;

	if (parent->var_children_size)
	{
		if (linked_list_search_key(parent->children, child, compare_pointers,
				NULL) == NULL)
		{
			linked_list_push_back(parent->children, child);
			added = 1;
		}
	}
	else
	{
		if (vector_search(parent->children, child, compare_pointers, NULL)
				== -1)
		{
			vector_push_back(parent->children, child);
			added = 1;
		}
	}

	LOGGER("[tree set parent] ");
	if (added)
		LOGGER("added child to");
	else
		LOGGER("child already exists into the");
	LOGGER(" parent children list/vector\n");
	LOGGER("[tree set parent] successfully finished");
}

void tree_add_child(tree_t node, tree_t child)
{
	LOGGER("[tree add child] node=\"%p\" child=\"%p\"\n", node, child);

	_ASSERT(node, ==, NULL, NULL_POINTER,);
	_ASSERT(child, ==, NULL, NULL_POINTER,);

	child->parent = node;

	if (node->var_children_size)
		linked_list_push_back(node->children, child);
	else
		vector_push_back(node->children, child);
}

tree_t tree_remove_child(tree_t node, int index)
{
	tree_t child;

	LOGGER("[tree remove child] node=\"%p\" index=\"%d\"\n", node, index);

	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(index, <, 0, INVALID_INPUT, NULL);

	if (node->var_children_size)
		_ASSERT(index, >=, linked_list_get_size(node->children), INVALID_INPUT, NULL);
	else
		_ASSERT(index, >=, vector_get_size(node->children), INVALID_INPUT, NULL);

	if (node->var_children_size)
	{
		child = linked_list_get_key_at(node->children, index);
		linked_list_remove_key(node->children, child, compare_pointers, NULL, 1);
	}
	else
		child = vector_remove_key_at(node->children, index);

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

	child->parent = NULL;

	return child;
}

void tree_remove_from_parent(tree_t node)
{
	tree_t parent;

	LOGGER("[tree remove from parent] node=\"%p\"\n", node);

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

	parent = node->parent;
	node->parent = NULL;

	if (node->var_children_size)
		linked_list_remove_key(parent->children, node, compare_pointers, NULL,
				1);
	else
		vector_remove_key(parent->children, node, compare_pointers, NULL);
}

void *tree_get_children(tree_t node)
{
	LOGGER("[tree get children] internal_representation=\"%p\"\n", node);

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

	return node->children;
}

int tree_get_children_number(tree_t node)
{
	LOGGER("[tree get children number] node=\"%p\"\n", node);

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

	if (node->var_children_size)
		return linked_list_get_size(node->children);
	return vector_get_size(node->children);
}

tree_t tree_get_child(tree_t node, int index)
{
	LOGGER("[tree get child] node=\"%p\" index=\"%d\"\n", node, index);

	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(index, <, 0, INVALID_INPUT, NULL);

	if (node->var_children_size)
		_ASSERT(index, >=, linked_list_get_size(node->children), INVALID_INPUT, NULL);
	else
		_ASSERT(index, >=, vector_get_size(node->children), INVALID_INPUT, NULL);

	if (node->var_children_size)
		return linked_list_get_key_at(node->children, index);
	return vector_get_key_at(node->children, index);
}

int tree_is_empty(tree_t node)
{
	LOGGER("[tree is empty] node=\"%p\"\n", node);

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

	if (node->parent == NULL && node->key == NULL)
	{
		if (node->var_children_size)
			return linked_list_get_size(node->children) == 0;
		return vector_get_size(node->children) == 0;
	}

	return 0;
}

int tree_is_leaf(tree_t node)
{
	LOGGER("[tree is leaf] node=\"%p\"\n", node);

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

	if (node->var_children_size)
		return linked_list_get_size(node->children) == 0;
	return vector_get_size(node->children) == 0;
}

int tree_get_height(tree_t node)
{
	int max_height, height, i;
	void *it;

	LOGGER("[tree get height] node=\"%p\"\n", node);
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	max_height = 0;

	if (node->var_children_size)
	{
		if (linked_list_get_size(node->children) == 0)
			return 0;

		// Find the child with the maximum height.
		for (it = linked_list_get_begin(node->children); it != NULL; it
				= linked_list_iterator_get_next(it))
		{
			height = tree_get_height(linked_list_iterator_get_key(it));
			max_height = MAX(max_height, height);
		}
	}
	else
	{
		if (vector_get_size(node->children) == 0)
			return 0;

		for (i = 0; i < vector_get_size(node->children); i++)
		{
			height = tree_get_height(vector_get_key_at(node->children, i));
			max_height = MAX(max_height, height);
		}
	}

	return 1 + max_height;
}

tree_t tree_get_root(tree_t node)
{
	LOGGER("[tree get root] node=\"%p\"\n", node);

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

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

	return node;
}

int tree_get_size(tree_t tree)
{
	int tree_size, i;
	linked_list_iterator_t it;

	LOGGER("[tree get size] tree=\"%p\"\n", tree);

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

	tree_size = 0;

	if (tree->var_children_size)
	{
		if (linked_list_get_size(tree->children) == 0)
			return 1;

		for (it = linked_list_get_begin(tree->children); it != NULL; it
				= linked_list_iterator_get_next(it))
			tree_size += tree_get_size(linked_list_iterator_get_key(it));
	}
	else
	{
		if (vector_get_size(tree->children) == 0)
			return 1;

		for (i = 0; i < vector_get_size(tree->children); i++)
			tree_size += tree_get_size(vector_get_key_at(tree->children, i));
	}

	return tree_size + 1;
}

void _tree_delete_handler(void *key, void *context)
{
	tree_delete(key);
}