/* 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 <stdio.h>
#include <string.h>
#include "pairing_heap.h"

#define TREE_ARRAY_SIZE 10

/* Forward function prototypes */
static void grow_tree_array(pairing_heap*, size_t);
static void recursive_pairing_heap_cleanup(pairing_heap_node*);
static pairing_heap_node *compare_and_link(pairing_heap*, pairing_heap_node*, pairing_heap_node*);
static pairing_heap_node *combine_siblings(pairing_heap*, pairing_heap_node*);

bool pairing_heap_create(pairing_heap *ph, pairing_heap_cmp cmp)
{
	memset(ph, '\0', sizeof(pairing_heap));
	ph->cmp = cmp;
	if((ph->tree_array.array = calloc(TREE_ARRAY_SIZE, sizeof(pairing_heap_node*))) == NULL) {
		fprintf(stderr, "pairing_heap_create : out of memory\n");
		exit(-1);
	}
	ph->tree_array.n = TREE_ARRAY_SIZE;
	return true;
}

static void grow_tree_array(pairing_heap *ph, size_t index)
{
	if(index == ph->tree_array.n) {
		if((ph->tree_array.array = realloc(ph->tree_array.array, 2 * ph->tree_array.n * sizeof(pairing_heap_node*))) == NULL) {
			fprintf(stderr, "grow_tree_array : out of memory\n");
			exit(-1);
		}
		ph->tree_array.n *= 2;
	}
}

bool pairing_heap_cleanup(pairing_heap *ph)
{
	free(ph->tree_array.array);
	recursive_pairing_heap_cleanup(ph->root);
	return true;
}

static void recursive_pairing_heap_cleanup(pairing_heap_node *n)
{
	if(n == NULL) return;
	recursive_pairing_heap_cleanup(n->left);
	recursive_pairing_heap_cleanup(n->sibling);
	free(n);
}

bool pairing_heap_insert(pairing_heap *ph, void *priority, const void *data, pairing_heap_item *phi)
{
	pairing_heap_node *n;
	
	if((n = calloc(1, sizeof(pairing_heap_node))) == NULL) {
		fprintf(stderr, "pairing_heap_insert : out of memory\n");
		exit(-1);
	}
	
	n->data = data;
	n->priority = priority;
	*phi = n;
	if(ph->root == NULL)
		ph->root = n;
	else
		ph->root = compare_and_link(ph, ph->root, n);
	ph->size++;
	
	return true;
}

static pairing_heap_node *compare_and_link(pairing_heap *ph, pairing_heap_node *first, pairing_heap_node *second)
{
	if(second == NULL) return first;
	
	if(ph->cmp(first->priority, second->priority) <= 0) {
		/* attach the second as the leftmost child of the first */
		second->prev = first;
		first->sibling = second->sibling;
		if(first->sibling) first->sibling->prev = first;
		second->sibling = first->left;
		if(second->sibling) second->sibling->prev = second;
		first->left = second;
		return first;
	} else {
		/* attach the first as the leftmost child of the second */
		second->prev = first->prev;
		first->prev = second;
		first->sibling = second->left;
		if(first->sibling) first->sibling->prev = first;
		second->left = first;
		return second;
	}
}

bool pairing_heap_find_min(pairing_heap *ph, pairing_heap_item *phi)
{
	*phi = ph->root;
	return (ph->root != NULL);
}

const void *pairing_heap_delete_min(pairing_heap *ph)
{
	if(ph->root == NULL) return NULL;
	
	pairing_heap_node *root = ph->root;
	const void *data = root->data;
	if(ph->root->left != NULL)
		ph->root = combine_siblings(ph, root->left);
	else
		ph->root = NULL;
	free(root);
	return data;
}

static pairing_heap_node *combine_siblings(pairing_heap *ph, pairing_heap_node *first)
{
	size_t i, j, num_siblings;
	
	/* if there's only one tree then return it */
	if(first->sibling == NULL)
		return first;
	
	/* place each subtree in tree_array */
	for(num_siblings = 0; first != NULL; ++num_siblings) {
		grow_tree_array(ph, num_siblings);
		ph->tree_array.array[num_siblings] = first;
		first->prev->sibling = NULL; /* break links */
		first = first->sibling;
	}
	grow_tree_array(ph, num_siblings);
	ph->tree_array.array[num_siblings] = NULL;
	
	/* combine the subtrees two at a time going from left to right */
	for(i = 0; i + 1 < num_siblings; i += 2)
		ph->tree_array.array[i] = compare_and_link(ph, ph->tree_array.array[i], ph->tree_array.array[i + 1]);
	
	/* j has the result of the last compare_and_link,
	 if it's an odd number of trees, get the last one */
	j = i - 2;
	if(j == num_siblings - 3)
		ph->tree_array.array[j] = compare_and_link(ph, ph->tree_array.array[j], ph->tree_array.array[j + 2]);
	
	/* go right to left, merging the last tree with the next to last
	 the result becomes the new last */
	for( ; j >= 2; j -= 2)
		ph->tree_array.array[j - 2] = compare_and_link(ph, ph->tree_array.array[j - 2], ph->tree_array.array[j]);
	
	return ph->tree_array.array[0];
}

size_t pairing_heap_size(pairing_heap *ph)
{
	return ph->size;
}

const void *pairing_heap_get_data(pairing_heap_item phi)
{
	return (phi) ? phi->data : NULL;
}