/*
 * Copyright (c) Alex Holden <alex@linuxhacker.org> 2000.
 *
 * This code is public domain; you can do whatever you want with it, though I
 * would prefer you to contribute any bug fixes back to me if possible.
 * This software comes with NO WARRANTY WHATSOEVER, not even the implied
 * warranties of merchantability and fitness for a particular purpose.
 *
 * heap.c: Implements heap structures.
 *
 * This file (and it's associated header file) implements a heap structure.
 * A heap is a special kind of binary tree where lower elements are always
 * lower than higher elements (except in a bottom heavy arrangement, which is
 * the other way around). When you add nodes to the heap, they are kept roughly
 * in order (but not fully sorted). When you remove the root node from the
 * heap, you always get either the highest valued node or the lowest, depending
 * on whether you're using it in top heavy or bottom heavy mode. So if you add
 * some nodes to the heap then remove them again they come back sorted, but
 * without the overhead which would be involved in fully sorting the data every
 * time you add or remove an node. This is called a heap sort. It is somewhat
 * slower than a quicksort, but has the advantage that you don't have to fully
 * sort the data every time you add a new node, which makes it better in cases
 * where you want to be able to keep adding and removing nodes, and always get
 * back the highest (or lowest) node. Another name for a heap is a priority
 * queue, because you can add nodes of varying priorities to the queue in any
 * order you want, and always be able to pop the highest priority node straight
 * off the top of the queue.
 *
 * This implementation uses a fixed size heap array for efficiency, so it is
 * not useful without modification for applications where you don't know the
 * maximum number of nodes you need to store in advance. If you want to add the 
 * ability to dynamically resize the heap, I would suggest you reallocate the
 * array in blocks so that you only need to do the reallocation (which on some
 * platforms can be very slow and leads to memory fragmentation) relatively
 * infrequently, rather than every time a node is added or removed.
 *
 * The nodes are simply pointers. When you do heap_init(), you specify a
 * callback function which knows how to decide which is the larger (or smaller)
 * of the two nodes. The prototype of the callback function should be:
 * int cmp(void *a, void *b);
 * If you want a top heavy heap, the compare function should return true if
 * a is higher than b. If you want a bottom heavy heap, the compare function
 * should return true if b is higher than a.
 */

#include <sys/types.h>
#include <stdlib.h>

#include "teatotal.h"
#include "heap.h"

/*
 * Create a new heap with space for "size" nodes. Returns a pointer to the
 * newly allocated heap, or NULL if it fails.
 */
heap *heap_init(int size, heap_comparefunc cmp)
{
	heap *ret;

	/* Allocate the heap structure */
	if(!(ret = malloc(sizeof(heap)))) return NULL;

	/* Allocate the heap array */
	if(!(ret->hp = malloc(sizeof(void *) * size))) {
		free(ret);
		return NULL;
	}

	/* Set up the structure entries */
	ret->size = size;
	ret->nodes = 0;
	ret->cmp = cmp;

	/* Return the address of the new heap structure */
	return ret;
}

/*
 * Free a heap structure. If "freenodes" is true, also call free() on every
 * node in the heap.
 */
void heap_destroy(heap *hp, int freenodes)
{
	int i;

	/* Free the nodes if requested */
	if(freenodes) for(i = 0; i < hp->nodes; i++) free(hp->hp[i]);

	/* Free the heap array */
	free(hp->hp);

	/* Free the heap structure */
	free(hp);
}

/*
 * Adds a node to the specified heap. The node must be a pointer to something
 * which can be compared with the callback function which was specified to
 * heap_init(). Returns the number of unused nodes in the array on success or
 * -1 if there wasn't enough space to add the node.
 */
int heap_add_node(heap *hp, void *node)
{
	int n, p;
	void *tmp;

	/* Check that there is room for another node in the heap */
	if(hp->nodes == hp->size) return -1;

	/* Add the new node at the end of the heap array */
	hp->hp[hp->nodes] = node;

	/* If there are now at least 2 nodes, re-order the heap */
	if(hp->nodes) {
		/* Start at the end of the array */
		n = hp->nodes;
		do {
			/* Find the parent of the current node */
			p = (n - 1) / 2;
			/* If the current node is greater than it's parent */
			if(hp->cmp(hp->hp[n], hp->hp[p])) {
				/* Then swap them around */
				tmp = hp->hp[p];
				hp->hp[p] = hp->hp[n];
				hp->hp[n] = tmp;
			}
		/* Set current node to parent node, unless we're at the root */
		} while((n = p));
	}

	/* Increment the node count */
	hp->nodes++;

	/* Return the number of free nodes remaining in the heap */
	return(hp->size - hp->nodes);
}

/*
 * Removes the top node from the specified heap, reorders the heap, and returns
 * the node. Returns NULL if the heap is empty.
 */
void *heap_remove_node(heap *hp)
{
	int n, c, g;
	void *node, *tmp;

	/* Check that the heap isn't empty */
	if(!hp->nodes) return NULL;

	/* Get the top node */
	node = hp->hp[0];

	/* Shift the bottom node to the top node location */
	hp->hp[0] = hp->hp[hp->nodes - 1];

	/* If there are at least two nodes remaining in the heap, re-order it */
	if(hp->nodes > 2) {
		/* Start at the root of the heap */
		n = 0;
		while(1) {
			/* Find the left child of the current node */
			c = (n * 2) + 1;

			/* Initialise the greater node to the current node */
			g = n;

			/* If not at the end of the tree and the left child is
			 * larger than the current node, set the greater node
			 * pointer to the left child node */
			if((c < hp->nodes) && hp->cmp(hp->hp[c], hp->hp[n]))
				g = c;

			/* Find the right child of the current node */
			c++;

			/* If not at the end of the tree and the right child is
			 * larger than the current greatest node, set the
			 * greater node pointer to the right child */
			if((c < hp->nodes) && hp->cmp(hp->hp[c], hp->hp[g]))
				g = c;

			/* If the current node isn't the greatest node, swap
			 * the two around */
			if(n != g) {
				tmp = hp->hp[n];
				hp->hp[n] = hp->hp[g];
				hp->hp[g] = tmp;
			/* Otherwise, we've finished re-ordering */
			} else break;

			/* Keep on going down the tree */
			n = g;
		}
	}

	/* Decrement the count of nodes in the heap */
	hp->nodes--;

	/* Return the node which was on top before we removed it */
	return node;
}