temelia/release/include/heap.h

/*!
 Temelia - Heap interface.

 Copyright (C) 2008, 2009 Ceata (http://cod.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.
 */

#ifndef HEAP_H_
#define HEAP_H_

#include "platform.h"

struct _heap_t;
typedef struct _heap_t *heap_t;

/*!
 * @brief Returns an empty heap.
 * Complexity O(1)
 *
 * @param Heap's size
 */
DECLSPEC heap_t heap_new(int size);

/*!
 * @brief Frees the memory occupied by a heap.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC void heap_delete(heap_t heap);

/*!
 * @brief Tests if a heap is empty.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC int heap_is_empty(heap_t heap);

/*!
 * @brief Tests if a heap is full.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC int heap_is_full(heap_t heap);

/*!
 * @brief Return the minimum key, stored in the heap's root.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC void *heap_get_min_key(heap_t heap);

/*!
 * @brief Removes minimum key.
 * Complexity O(log(n))
 *
 * @param Heap
 * @param Pointer to comparison function
 * @param Context
 */
DECLSPEC void heap_remove_min_key(heap_t heap, int compare(void *x, void *y,
		void *context), void *context);

/*!
 * @brief Inserts a new key in heap.
 * Complexity O(log(n))
 *
 * @param Heap
 * @param Key
 * @param Pointer to comparison function
 * @param Context
 */
DECLSPEC void heap_insert(heap_t heap, void *key, int compare(void *x, void *y,
		void *context), void *context);

/*!
 * @brief Changes the key from position in heap.
 * Complexity O(1)
 *
 * @param Heap
 * @param Key's position
 * @param New key reference
 * @param Pointer to comparison function
 */
DECLSPEC 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);

/*!
 * @brief Changes a key value from heap.
 * Complexity O(n)
 *
 * @param Heap
 * @param Key
 * @param New key
 * @param Pointer to comparison function
 */
DECLSPEC 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);

/*!
 * @brief Breadth traverses a heap and handles the key from each node.
 * Complexity O(1)
 *
 * @param Heap
 * @param Pointer to print function.
 * @param Pointer to stream.
 */
DECLSPEC void heap_iterate(heap_t heap, void key_handler(void *x, void *context),
		void *context);

/*!
 * @brief Returns the number of keys from heap.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC int heap_get_size(heap_t heap);

/*!
 * @brief Returns heap's size.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC int heap_get_capacity(heap_t heap);

/*!
 * @brief Sets heap's capacity increment. If you don't want size auto-adjusting when
 * the heap is full, then set the capacity increment to 0.
 * Complexity O(1)
 *
 * @param Heap
 * @param New capacity increment value
 */
DECLSPEC void heap_set_capacity_increment(heap_t heap, int new_capacity_increment);

/*!
 * @brief Returns heap's capacity increment.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC int heap_get_capacity_increment(heap_t heap);

/*!
 * @brief Returns the internal representation of the current heap;
 * cast it to vector_t.
 * Complexity O(1)
 *
 * @param Heap
 */
DECLSPEC void *heap_get_data(heap_t heap);

/*!
 * @brief Creates a heap from an array.
 * Complexity O(n * log(n))
 *
 * @param Array data
 * @param Size
 * @param Pointer to comparison function
 */
DECLSPEC heap_t heap_create_heap(void **data, int size, int compare(void *x, void *y,
		void *context), void *context);

#endif /* HEAP_H_ */