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

/* Forward function prototypes */
static void recursive_rmq_cleanup(rmq_node*);
static rmq_node *meld(rmq *q, rmq_node*, rmq_node*);

bool rmq_create(rmq *q, rmq_cmp cmp)
{
	memset(q, '\0', sizeof(rmq));
	q->cmp = cmp;
	return true;
}

bool rmq_cleanup(rmq *q)
{
	recursive_rmq_cleanup(q->root);
	memset(q, '\0', sizeof(rmq));
	return true;
}

static void recursive_rmq_cleanup(rmq_node *n)
{
	if(n == NULL) return;
	recursive_rmq_cleanup(n->left);
	recursive_rmq_cleanup(n->right);
	free(n);
}

bool rmq_insert(rmq *q, void *priority, const void *data, rmq_item *rmqi)
{
	rmq_node *n;
	if((n = calloc(1, sizeof(rmq_node))) == NULL) {
		fprintf(stderr, "rmq_insert : out of memory\n");
		exit(-1);
	}
	n->priority = priority;
	n->data = data;
	q->root = meld(q, q->root, n);
	q->size++;
	*rmqi = n;
	return true;
}

static rmq_node *meld(rmq *q, rmq_node *q1, rmq_node *q2)
{
	if(q1 == NULL) return q2;
	if(q2 == NULL) return q1;
	if(q->cmp(q1->priority, q2->priority) > 0) {
		rmq_node *t = q1;
		q1 = q2;
		q2 = t;
	}
	if(rand() % 2 == 0)
		q1->left = meld(q, q1->left, q2);
	else
		q1->right = meld(q, q1->right, q2);
	
	return q1;
}

bool rmq_find_min(rmq *q, rmq_item *rmqi)
{
	*rmqi = q->root;
	return (q->root != NULL);
}

const void *rmq_delete_min(rmq *q)
{
	if(q->root == NULL) return NULL;
	rmq_node *r = q->root;
	const void *data = r->data;
	q->root = meld(q, q->root->left, q->root->right);
	free(r);
	q->size--;
	return data;
}

size_t rmq_size(rmq *q)
{
	return q->size;
}

const void *rmq_get_data(rmq_item rmqi)
{
	return (rmqi != NULL) ? rmqi->data : NULL;
}