/*
 *  heaters.c
 *  Project
 *
 *  Created by Geoffrey Foster on 09/04/08.
 *  Copyright 2008 Geoffrey Foster. All rights reserved.
 *
 */

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

/* Forward function prototypes */
static void recursive_heater_cleanup(heater_node *n);
static void rebalance(heater *h, heater_node *n);
static void left_rotate(heater_node *n);
static void right_rotate(heater_node *n);
static void heater_delete_item(heater *h, heater_item hi);

bool heater_create(heater *h, heater_cmp cmp)
{
	memset(h, '\0', sizeof(heater));
	h->cmp = cmp;
	return true;
}

bool heater_cleanup(heater *h)
{
	recursive_heater_cleanup(h->root);
	memset(h, '\0', sizeof(heater));
	return true;
}

/* Recursively cleanup the heater sub-tree rooted at n */
static void recursive_heater_cleanup(heater_node *n)
{
	if(n == NULL)
		return;
	recursive_heater_cleanup(n->left);
	recursive_heater_cleanup(n->right);
	free(n);
}

bool heater_insert(heater *h, void *priority, const void *data, heater_item *hi)
{
	int ret = 0;
	heater_node *n, *p;
	
	/* find the parent p of e */
	p = NULL;
	n = h->root;
	double k = (double)rand()/((double)(RAND_MAX) + (double)(1));
	while(n != NULL) {
		p = n;
		//ret = h->cmp(priority, n->priority);
		if(k <= n->k) {
			n = n->left;
		} else {
			n = n->right;
		}
	}
	
	/* allocate a new node n */
	if((n = malloc(sizeof(heater_node))) == NULL) {
		fprintf(stderr, "heater_insert : out of memory\n");
		exit(-1);
	}
	memset(n, '\0', sizeof(heater_node));
	n->priority = priority;
	n->data = data;
	*hi = n;
	
	/* make p the parent of n */
	n->parent = p;
	if(p == NULL)
		h->root = n;
	else if(k <= p->k)
		p->left = n;
	else
		p->right = n;
	
	/* assign k value and rebalance */
	n->k = k;
	rebalance(h, n);
	
	/* increment size */
	h->size++;
	
	return true;
}

static void rebalance(heater *h, heater_node *n)
{
	while(n->parent != NULL && h->cmp(n->parent->priority, n->priority) > 0) {
		if(n->parent->right == n) {
			left_rotate(n->parent);
		} else {
			right_rotate(n->parent);
		}
	}
	if(n->parent == NULL) {
		h->root = n;
	}
}

/* Do a left rotation at n */
static void left_rotate(heater_node *n)
{
	heater_node *x;
	
	x = n->right;
	
	x->parent = n->parent;
	if(x->parent != NULL) {
		if(x->parent->left == n) {
			x->parent->left = x;
		} else {
			x->parent->right = x;
		}
	}
	
	n->right = x->left;
	if(n->right != NULL) {
		n->right->parent = n;
	}
	
	n->parent = x;
	x->left = n;
}


/* Do a left rotation at n */
static void right_rotate(heater_node *n)
{
	heater_node *x;
	
	x = n->left;
	
	x->parent = n->parent;
	if(x->parent != NULL) {
		if(x->parent->left == n) {
			x->parent->left = x;
		} else {
			x->parent->right = x;
		}
	}
	
	n->left = x->right;
	if(n->left != NULL) {
		n->left->parent = n;
	}
	
	n->parent = x;
	x->right = n;
}

bool heater_find_min(heater *h, heater_item *hi)
{
	*hi = h->root;
	return (h->root != NULL);
}

const void *heater_delete_min(heater *h)
{
	const void *data = (h->root) ? h->root->data : NULL;
	heater_delete_item(h, h->root);
	return data;
}

/* Delete the item hi from the treap */
static void heater_delete_item(heater *h, heater_item hi)
{
	heater_node *n = hi;
	
	/* rotate n downwards until it becomes a leaf */
	while(n->left != NULL || n->right != NULL) {
		if(n->left != NULL) {
			if(n->right == NULL || h->cmp(n->left->priority, n->right->priority) < 0) {
				right_rotate(n);
			} else {
				left_rotate(n);
			}
		} else {
			left_rotate(n);
		}
		if(h->root == n) {
			h->root = n->parent;
		}
	}
	
	/* splice n out */ 
	if(n->parent == NULL) {
		h->root = NULL;
		if(heater_size(h) != 1) {
			fprintf(stderr, "heater_delete : internal error #1\n");
			exit(-1);
		}
	} else {
		if(n->parent->left == n) {
			n->parent->left = NULL;
		} else {
			n->parent->right = NULL;
		}
	}
	
	free(n);
	h->size--;
}

//void heater_decrease_key(heater *h);

size_t heater_size(heater *h)
{
	return h->size;
}

const void *heater_get_data(heater_item hi)
{
	return hi->data;
}