/* Copyright (c) 2008, Geoffrey Foster
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Geoffrey Foster ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL Geoffrey Foster BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "min_heap.h"

#define MIN_HEAP_SIZE 100
#define HEAP_INDEX_ERROR ((size_t)(-1))

#define LEFT_CHILD(node) ((node) * 2 + 1)
#define RIGHT_CHILD(node) ((node) * 2 + 2)
#define PARENT(node) (((node) == 0) ? -1 : ((node) - 1) / 2)

/* Forward function prototypes */
static void min_heap_grow(min_heap *h);
static void min_heap_shrink(min_heap *h);
static void min_heap_node_swap(min_heap_node *n1, min_heap_node *n2);

bool min_heap_create(min_heap *h, min_heap_cmp cmp)
{
	memset(h, '\0', sizeof(min_heap));
	if((h->min_heap_data = calloc(MIN_HEAP_SIZE, sizeof(min_heap_node))) == NULL) {
		fprintf(stderr, "min_heap_create : out of memory\n");
		exit(-1);
	}
	h->max_size = MIN_HEAP_SIZE;
	h->cmp = cmp;
	
	return true;
}

bool min_heap_cleanup(min_heap *h)
{
	free(h->min_heap_data);
	memset(h, '\0', sizeof(min_heap));
	return true;
}

static void min_heap_grow(min_heap *h)
{
	if((h->min_heap_data = realloc(h->min_heap_data, 2 * h->max_size * sizeof(min_heap_node))) == NULL) {
		fprintf(stderr, "min_heap_grow : out of memory\n");
		exit(-1);
	}
	h->max_size = 2 * h->max_size;
}

static void min_heap_shrink(min_heap *h)
{
	if((h->min_heap_data = realloc(h->min_heap_data, h->max_size / 2 * sizeof(min_heap_node))) == NULL) {
		fprintf(stderr, "min_heap_shrink : memory error\n");
	}
	h->max_size = h->max_size / 2;
}

static void min_heap_node_swap(min_heap_node *n1, min_heap_node *n2)
{
	void *priority = n1->priority;
	const void *data = n1->data;
	
	n1->priority = n2->priority;
	n1->data = n2->data;
	n2->priority = priority;
	n2->data = data;
}

bool min_heap_insert(min_heap *h, void *priority, const void *data, min_heap_item *hi)
{
	if(h->n == h->max_size)
		min_heap_grow(h);
	
	size_t index = h->n;
	h->min_heap_data[index].data = data;
	h->min_heap_data[index].priority = priority;
	
	size_t parent;
	while((parent = PARENT(index)) != HEAP_INDEX_ERROR) {
		if(h->cmp(h->min_heap_data[parent].priority, h->min_heap_data[index].priority) <= 0)
			break;
		min_heap_node_swap(h->min_heap_data + parent, h->min_heap_data + index);
		index = parent;
	}
	
	h->n++;
	
	*hi = &h->min_heap_data[index];
	return true;
}

bool min_heap_find_min(min_heap *h, min_heap_item *hi)
{
	if(h->n == 0) {
		*hi = NULL;
		return false;
	} else {
		*hi = h->min_heap_data;
		return true;
	}
}

const void *min_heap_delete_min(min_heap *h)
{
	if(h->n == 0)
		return NULL;
	
	const void *data = min_heap_get_data(h->min_heap_data);
	
	/* decrease size of min_heap */
	h->n--;
	
	/* if there is at least 1 item still in the min_heap */
	if(h->n > 0) {
		/* move the last item to the front */
		h->min_heap_data[0].priority = h->min_heap_data[h->n].priority;
		h->min_heap_data[0].data = h->min_heap_data[h->n].data;
		
		size_t index = 0;
		size_t left, right, min;
		bool done = false;
		while(!done) {
			left = LEFT_CHILD(index);
			right = RIGHT_CHILD(index);
			if(left < h->n && right < h->n) {
				min = (h->cmp(h->min_heap_data[left].priority, h->min_heap_data[right].priority) <= 0) ? left : right;
			} else if(left < h->n) {
				min = left;
			} else if(right < h->n) {
				min = right;
			} else {
				done = true;
				break;
			}
			
			if(h->cmp(h->min_heap_data[min].priority, h->min_heap_data[index].priority) < 0) {
				min_heap_node_swap(h->min_heap_data + min, h->min_heap_data + index);
				index = min;
			} else
				done = true;
		}
	}
	
	return data;
}

size_t min_heap_size(min_heap *h)
{
	return h->n;
}

const void *min_heap_get_data(min_heap_item hi)
{
	return hi->data;
}