123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268 |
- /*!
- 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;
- }
|