temelia/src/heap.c

/*!
 Temelia - Heap 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/heap.h"
#include "include/vector.h"
#include "include/common.h"
#include <stdlib.h>

struct _heap_t
{
	/*! array of keys */
	vector_t data;
};

//Private functions

// Bubbles down key, in heap, from position p.
static void _heap_down(heap_t heap, int position, int(*compare)(void *x, void *y,
		void *context), void *context);

// Bubbles up key, in heap, from position p.
static void _heap_up(heap_t heap, int position, int(*compare)(void *x, void *y,
		void *context), void *context);

// Returns the index of key in heap.
static int _heap_find(heap_t heap, void *key, int(*compare)(void *x, void *y,
		void *context), void *context);

heap_t heap_new(int capacity)
{
	heap_t heap;

	_ASSERT(capacity, <=, 0, INVALID_INPUT, NULL);

	heap = (struct _heap_t *) _new(sizeof(struct _heap_t));
	heap->data = vector_new(capacity);

	return heap;
}

void heap_delete(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER,);

	vector_delete(heap->data);
	_delete(heap);
}

int heap_is_empty(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, -1);

	return vector_get_size(heap->data) == 0;
}

int heap_is_full(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, -1);

	return vector_get_capacity(heap->data) == vector_get_size(heap->data);
}

void *heap_get_min_key(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(vector_get_size(heap->data), <=, 0, INVALID_INPUT, NULL);

	return vector_get_key_at(heap->data, 0);
}

void heap_remove_min_key(heap_t heap,
		int compare(void *x, void *y, void *context), void *context)
{
	void *x;

	_ASSERT(heap, ==, NULL, NULL_POINTER,);
	_ASSERT(vector_get_size(heap->data), <=, 0, EMPTY,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);

	x = vector_get_key_at(heap->data, 0);
	vector_set_key_at(heap->data, 0, vector_get_key_at(heap->data,
			vector_get_size(heap->data) - 1));
	vector_set_size(heap->data, vector_get_size(heap->data) - 1);
	_heap_down(heap, 0, compare, context);
}

void heap_insert(heap_t heap, void *key, int compare(void *x, void *y,
		void *context), void *context)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER,);

	vector_push_back(heap->data, key);

	_heap_up(heap, vector_get_size(heap->data) - 1, compare, context);
}

void heap_change_key_by_position(heap_t heap, int position, void *new_key_value,
		int compare(void *x, void *y, void *context), void *context)
{
	void *tmp;

	_ASSERT(heap, ==, NULL, NULL_POINTER,);
	_ASSERT(position, <, 0, INVALID_INPUT,);
	_ASSERT(compare, ==, NULL, NULL_POINTER,);
	_ASSERT(vector_get_size(heap->data), <=, position, INVALID_INPUT,);

	tmp = vector_get_key_at(heap->data, position);
	vector_set_key_at(heap->data, position, new_key_value);

	if (compare(new_key_value, tmp, context) < 0)
		_heap_down(heap, position, compare, context);
	else
		_heap_up(heap, position, compare, context);
}

void heap_change_key_by_value(heap_t heap, void *key_value, void *new_key_value,
		int compare(void *x, void *y, void *context), void *context)
{
	heap_change_key_by_position(heap, _heap_find(heap, key_value,
			compare, context), new_key_value, compare, context);
}

void heap_iterate(heap_t heap, void key_handler(void *x, void *context),
		void *context)
{
	int i;

	_ASSERT(heap, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	for (i = 0; i < vector_get_size(heap->data); i++)
		key_handler(vector_get_key_at(heap->data, i), context);
}

int heap_get_size(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, -1);

	return vector_get_size(heap->data);
}

int heap_get_capacity(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, -1);

	return vector_get_capacity(heap->data);
}

void heap_set_capacity_increment(heap_t heap, int capacity_increment)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER,);
	_ASSERT(capacity_increment, <, 0, INVALID_INPUT,);

	vector_set_capacity_increment(heap->data, capacity_increment);
}

int heap_get_capacity_increment(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, -1);

	return vector_get_capacity_increment(heap->data);
}

void *heap_get_data(heap_t heap)
{
	_ASSERT(heap, ==, NULL, NULL_POINTER, NULL);

	return heap->data;
}

heap_t heap_create_heap(void **data, int size, int compare(void *x, void *y,
		void *context), void *context)
{
	int i;
	heap_t heap;

	_ASSERT(data, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(size, <=, 0, INVALID_INPUT, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	heap = heap_new(size);

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

	for (i = 0; i < size; i++)
		heap_insert(heap, data[i], compare, context);

	return heap;
}

static void _heap_down(heap_t heap, int position, int (*compare)(void *x, void *y,
		void *context), void *context)
{
	int child;
	void *aux;

	while (2 * position + 1 < vector_get_size(heap->data))
	{
		child = 2 * position + 1;
		if (child + 1 < vector_get_size(heap->data) && compare(
				vector_get_key_at(heap->data, child), vector_get_key_at(
						heap->data, child + 1), context) > 0)
			child++;

		if (compare(vector_get_key_at(heap->data, child), vector_get_key_at(
				heap->data, position), context) < 0)
		{
			aux = vector_get_key_at(heap->data, position);
			vector_set_key_at(heap->data, position, vector_get_key_at(heap->data,
					child));
			vector_set_key_at(heap->data, child, aux);
			position = child;
		}
		else
			break;
	}
}

static void _heap_up(heap_t heap, int position, int (*compare)(void *x, void *y,
		void *context), void *context)
{
	void *aux;

	if (position == 0)
		return;

	while (position > 0 && (compare(vector_get_key_at(heap->data, position),
			vector_get_key_at(heap->data, (position - 1) / 2), context) < 0))
	{
		aux = vector_get_key_at(heap->data, position);
		vector_set_key_at(heap->data, position, vector_get_key_at(heap->data,
				(position - 1) / 2));
		vector_set_key_at(heap->data, (position - 1) / 2, aux);

		position = (position - 1) / 2;
	}
}

static int _heap_find(heap_t heap, void *key, int (*compare)(void *x, void *y,
		void *context), void *context)
{
	int i;

	for (i = 0; i < vector_get_size(heap->data); i++)
		if (!compare(vector_get_key_at(heap->data, i), key, context))
			return i;
	return -1;
}