/*
 *  Copyright 2009 OpenSourceStewardshipFoundation.org
 *  Licensed under GNU General Public License version 2
 *
 * Author: hausers@cs.tu-berlin.de
 */

#include <limits.h>
#include <stdio.h>
#include <string.h>

#include "PriorityQueue.h"
#ifndef DEBUG
#include "../../VMS_Implementations/VMS_impl/vmalloc.h"
#endif

#define left(i) 2*i
#define right(i) 2*i+1
#define parent(i) i/2

#ifdef DEBUG
#include <stdlib.h>
#define VMS__malloc malloc
#define VMS__free free
#endif 

void swap (PrioQueueStruc *Q, int a, int b) {
	void *valTmp;
	int keyTmp;
	keyTmp= Q->data[a].key;
	valTmp= Q->data[a].val;
	Q->data[a].key= Q->data[b].key;
	Q->data[a].val= Q->data[b].val;
	Q->data[b].key= keyTmp;
	Q->data[b].val= valTmp;
	
}

bool increaseKey (PrioQueueStruc *Q, int i, int key) {
	if (key < Q->data[i].key) return false; // increasing not possible

	Q->data[i].key= key;
	while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
		swap(Q,i,parent(i));
		i= parent(i);
	}	
	return true;
}

void heapify (PrioQueueStruc *Q, int i) {
	int largest;
	int l,r;
	l= left(i);
	r= right(i);
	if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
	else largest= i;
	if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
	if (largest != i) {
		swap(Q,i,largest);
		heapify(Q,largest);
	}
}

void enlargePrioQ (PrioQueueStruc *Q)  {
	size_t oldSize, newSize;
	heapNode *oldData,*newData;

	oldSize= Q->size;
	newSize= 2*oldSize;

	Q->maxSize= newSize;
	newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
	oldData= Q->data;

	memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
	Q->data= newData;

	VMS__free(oldData);
}


PrioQueueStruc* makeVMSPrioQ () {
	PrioQueueStruc *retQ;
	retQ= VMS__malloc(sizeof(PrioQueueStruc));
	retQ->maxSize= 1024;
	retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
	retQ->size= 0;
	return retQ;
}

void* getFirstPrioQ (PrioQueueStruc *Q) {
	return Q->data[0].val;
}

void* popPrioQ (PrioQueueStruc *Q) {
	void *max;
	if (Q->size < 1) max= NULL;
	else {
		max= Q->data[0].val;
		swap(Q,0,Q->size-1);
		Q->size--;
		heapify(Q,0);
	}	
	return max;
}

bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
	if (Q->size == Q->maxSize) enlargePrioQ(Q);

	Q->size++;
	Q->data[Q->size-1].key= INT_MIN;
	Q->data[Q->size-1].val= val;

	return increaseKey(Q,Q->size-1,key);
}

void printPrioQ (PrioQueueStruc *Q) {
	int i;
	printf("{");
	if (Q->size>0) printf("%s",(char *)Q->data[0].val);
	for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
	printf("} ... ");

}

void freePrioQ (PrioQueueStruc *Q) {
	VMS__free(Q->data);
	VMS__free(Q);
}