temelia/src/interval_tree.c

/*!
 Temelia - Interval tree implementation source file.

 There are two ways to implement this data structure,
 with red-black trees and with some kind of heap. Because red-black tree is already
 implemented, here you can find the heap implementation of the interval tree.

 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/interval_tree.h"
#include "include/queue.h"
#include <string.h>

struct _interval_node_t
{
	int inf, sup;
	void *key;
};

struct _interval_tree_t
{
	interval_tree_node_t *data;
	int size;
};

static interval_tree_t _interval_tree_new(int inf, int sup);
static void _interval_node_add(interval_tree_t tree, int index, int inf, int sup);

static void _interval_tree_preorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context);

static void _interval_tree_inorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context);

static void _interval_tree_reverse_inorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context);

static void _interval_tree_postorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context);

static void _interval_tree_show_indented(interval_tree_t interval, int index,
		void key_handler(void *key, int level, void *context), void *context,
		int level);

/*
 * @brief Returns the smallest power of 2 such x <= power(2,k).
 */
static int _next_power_2(int x);

static void _interval_tree_insert(interval_tree_t interval_tree, int index,
		int inf, int sup, void *key);

static void _interval_tree_search(interval_tree_t interval_tree, int index,
		int inf, int sup, void key_handler(void *key, void *context),
		void *context);

interval_tree_node_t interval_tree_node_new(int inf, int sup, void *key)
{
	interval_tree_node_t interval;

	interval = (struct _interval_node_t *) _new(sizeof(struct _interval_node_t));

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

	/*
	 * Set the node's key, infinimum and supremum to given values.
	 */
	interval->key = key;
	interval->inf = inf;
	interval->sup = sup;

	return interval;
}

void interval_tree_node_delete(interval_tree_node_t interval)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);

	interval->key = NULL;
	interval->inf = interval->sup = 0;

	_delete(interval);
}

int interval_tree_node_get_inf(interval_tree_node_t interval)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER, -1);

	return interval->inf;
}

int interval_tree_node_get_sup(interval_tree_node_t interval)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER, -1);

	return interval->sup;
}

void *interval_tree_node_get_key(interval_tree_node_t interval)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER, NULL);

	return interval->key;
}

interval_tree_t interval_tree_new(int inf, int sup)
{
	_ASSERT(inf,>, sup, INVALID_INPUT, NULL);

	return _interval_tree_new(inf, sup);
}

void interval_tree_delete(interval_tree_t interval_tree)
{
	int i = 0;

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

	for (; i < interval_tree->size; i++)
		interval_tree_node_delete(interval_tree->data[i]);

	_delete(interval_tree->data);
	_delete(interval_tree);
}

int interval_tree_is_empty(interval_tree_t interval_tree)
{
	int i;

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

	/*
	 * Check if the current node has non-NULL children pointers.
	 */
	for (i = 0; i < interval_tree->size; i++)
		if (interval_tree->data[i] && interval_tree->data[i]->key)
			return 0;

	return 1;
}

interval_tree_node_t *interval_tree_get_data(interval_tree_t interval_tree)
{
	_ASSERT(interval_tree, ==, NULL, NULL_POINTER, NULL);

	return interval_tree->data;
}

int interval_tree_get_size(interval_tree_t interval_tree)
{
	_ASSERT(interval_tree, ==, NULL, NULL_POINTER, -1);

	return interval_tree->size;
}

void interval_tree_search(interval_tree_t interval_tree, int inf, int sup,
		void key_handler(void *key, void *context), void *context)
{
	_ASSERT(interval_tree, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);
	_ASSERT(sup,>, interval_tree->data[0]->sup, INVALID_INPUT,);
	_ASSERT(inf, <, interval_tree->data[0]->inf, INVALID_INPUT,);

	/*
	 * The algorithm is :
	 * 		search (node, left, right, inf, sup)
	 * 		{
	 * 			if (inf <= left && right <= sup)
	 * 				callback function (key stored in current node)
	 * 			else
	 * 				let mid be (left+right)/2
	 * 				if (inf <= mid)
	 * 					search(left node, left, mid, inf, sup);
	 * 				if (sup >= mid+1)
	 * 					search(right node, mid + 1, right, inf, sup);
	 * 				callback function (key stored in current node)
	 * 		}
	 */

	_interval_tree_search(interval_tree, 0, inf, sup, key_handler, context);
}

void interval_tree_insert(interval_tree_t interval_tree, int inf, int sup,
		void *key)
{
	_ASSERT(interval_tree, ==, NULL, NULL_POINTER,);
	_ASSERT(sup,>, interval_tree->data[0]->sup, INVALID_INPUT,);
	_ASSERT(inf, <, interval_tree->data[0]->inf, INVALID_INPUT,);

	/* 	The algorithm is :
	 * 		search (node, left, right, inf, sup)
	 * 		{
	 * 			if (inf <= left && right <= sup)
	 * 				change key's value, stored in current node, to new key
	 * 			else
	 * 				let mid be (left+right)/2
	 * 				if (inf <= mid)
	 * 					search(left node, left, mid, inf, sup);
	 * 				if (sup >= mid+1)
	 * 					search(right node, mid + 1, right, inf, sup);
	 * 				change key's value, stored in current node, to new key
	 */

	_interval_tree_insert(interval_tree, 0, inf, sup, key);
}

void interval_tree_remove(interval_tree_t interval_tree, int inf, int sup)
{
	interval_tree_insert(interval_tree, inf, sup, NULL);
}

interval_tree_node_t interval_tree_get_node(interval_tree_t interval_tree, int index)
{
	_ASSERT(interval_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(index, <, 0, INVALID_INPUT, NULL);
	_ASSERT(index,>, interval_tree->size, INVALID_INPUT, NULL);

	return interval_tree->data[index];
}

void interval_tree_preorder(interval_tree_t interval, void key_handler(void *x,
		void *context), void *context)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_interval_tree_preorder(interval, 0, key_handler, context);
}

void interval_tree_inorder(interval_tree_t interval, void key_handler(void *x,
		void *context), void *context)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_interval_tree_inorder(interval, 0, key_handler, context);
}

void interval_tree_reverse_inorder(interval_tree_t interval, void key_handler(
		void *x, void *context), void *context)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_interval_tree_reverse_inorder(interval, 0, key_handler, context);
}

void interval_tree_postorder(interval_tree_t interval, void key_handler(void *x,
		void *context), void *context)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_interval_tree_postorder(interval, 0, key_handler, context);
}

void interval_tree_level_order(interval_tree_t interval, void key_handler(
		void *x, void *context), void *context)
{
	queue_t Q = queue_new(DEFAULT_SIZE);
	int *current_node, *aux, node;

	aux = (int *) _new(sizeof(int));
	*aux = 0;
	queue_push_back(Q, aux);

	while (!queue_is_empty(Q))
	{
		current_node = queue_get_front(Q);
		queue_pop_front(Q);
		key_handler(interval->data[*current_node]->key, context);

		node = 2 * (*current_node) + 1;
		if (node < interval->size && interval->data[node])
		{
			aux = (int *) _new(sizeof(int));
			*aux = node;
			queue_push_back(Q, aux);
		}

		node++;
		if (node < interval->size && interval->data[node])
		{
			aux = (int *) _new(sizeof(int));
			*aux = node;
			queue_push_back(Q, aux);
		}

		_delete(current_node);
	}

	queue_delete(Q);
}

void interval_tree_show_indented(interval_tree_t interval, void key_handler(
		void *x, int level, void *context), void *context)
{
	_ASSERT(interval, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_interval_tree_show_indented(interval, 0, key_handler, context, 0);
}

static void _interval_node_add(interval_tree_t tree, int index, int inf, int sup)
{
	tree->data[index] = interval_tree_node_new(inf, sup, NULL);

	if (inf < sup)
	{
		_interval_node_add(tree, 2 * index + 1, inf, (inf + sup) / 2);
		_interval_node_add(tree, 2 * index + 2, (inf + sup) / 2 + 1, sup);
	}
}

static interval_tree_t _interval_tree_new(int inf, int sup)
{
	interval_tree_t tree;

	tree = (struct _interval_tree_t *) _new(sizeof(struct _interval_tree_t));
	_ASSERT(tree, ==, NULL, NULL_POINTER, NULL);

	tree->size = 2 * _next_power_2(sup - inf + 1) - 1;
	tree->data = (interval_tree_node_t *) _new(tree->size * sizeof(interval_tree_node_t));
	memset(tree->data, 0, tree->size * sizeof(interval_tree_node_t));

	_ASSERT(tree->data, ==, NULL, NULL_POINTER, NULL);

	_interval_node_add(tree, 0, inf, sup);

	return tree;
}

static void _interval_tree_preorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context)
{
	if (index < interval->size)
	{
		if (interval->data[index])
			key_handler(interval->data[index]->key, context);

		_interval_tree_preorder(interval, 2 * index + 1, key_handler, context);
		_interval_tree_preorder(interval, 2 * index + 2, key_handler, context);
	}
}

static void _interval_tree_inorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context)
{
	if (index < interval->size)
	{
		_interval_tree_inorder(interval, 2 * index + 1, key_handler, context);

		if (interval->data[index])
			key_handler(interval->data[index]->key, context);

		_interval_tree_inorder(interval, 2 * index + 2, key_handler, context);
	}
}

static void _interval_tree_reverse_inorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context)
{
	if (index < interval->size)
	{
		_interval_tree_inorder(interval, 2 * index + 2, key_handler, context);

		if (interval->data[index])
			key_handler(interval->data[index]->key, context);

		_interval_tree_inorder(interval, 2 * index + 1, key_handler, context);
	}
}

static void _interval_tree_postorder(interval_tree_t interval, int index,
		void key_handler(void *x, void *context), void *context)
{
	if (index < interval->size)
	{
		_interval_tree_inorder(interval, 2 * index + 1, key_handler, context);
		_interval_tree_inorder(interval, 2 * index + 2, key_handler, context);

		if (interval->data[index])
			key_handler(interval->data[index]->key, context);
	}
}

void _interval_tree_show_indented(interval_tree_t interval, int index,
		void key_handler(void *key, int level, void *context), void *context,
		int level)
{
	if (index < interval->size)
	{
		_interval_tree_show_indented(interval, 2 * index + 2, key_handler,
				context, level + 1);

		if (interval->data[index])
			key_handler(interval->data[index]->key, level, context);

		_interval_tree_show_indented(interval, 2 * index + 1, key_handler,
				context, level + 1);
	}
}

static int _next_power_2(int x)
{
	int ok = 1;
	int y = 1;

	if (x == 0)
		return 1;

	while (x > 1)
	{
		if (x % 2 == 1)
			ok = 0;
		y *= 2;
		x /= 2;
	}

	if (!ok)
		y *= 2;

	return y;
}

static void _interval_tree_insert(interval_tree_t interval_tree, int index,
		int inf, int sup, void *key)
{
	int _inf = 0, _sup = 0, _mid = 0;

	if (index >= interval_tree->size || interval_tree->data[index] == NULL)
		return;

	_inf = interval_tree->data[index]->inf;
	_sup = interval_tree->data[index]->sup;

	if (inf <= _inf && _sup <= sup)
		interval_tree->data[index]->key = key;
	else
	{
		_mid = (_inf + _sup) / 2;
		if (inf <= _mid)
			_interval_tree_insert(interval_tree, 2 * index + 1, inf, sup, key);
		if (sup >= _mid + 1)
			_interval_tree_insert(interval_tree, 2 * index + 2, inf, sup, key);
		interval_tree->data[index]->key = key;
	}
}

static void _interval_tree_search(interval_tree_t interval_tree, int index,
		int inf, int sup, void key_handler(void *key, void *context),
		void *context)
{
	int _inf = 0, _sup = 0, _mid = 0;

	if (index >= interval_tree->size || interval_tree->data[index] == NULL)
		return;

	_inf = interval_tree->data[index]->inf;
	_sup = interval_tree->data[index]->sup;

	if (inf <= _inf && _sup <= sup)
		key_handler(interval_tree->data[index]->key, context);
	else
	{
		_mid = _inf + (_sup - _inf) / 2;
		if (inf <= _mid)
			_interval_tree_search(interval_tree, 2 * index + 1, inf, sup,
					key_handler, context);
		if (sup >= _mid + 1)
			_interval_tree_search(interval_tree, 2 * index + 2, inf, sup,
					key_handler, context);
		key_handler(interval_tree->data[index]->key, context);
	}
}