hausers@0: /*
hausers@0:  *  Copyright 2009 OpenSourceStewardshipFoundation.org
hausers@0:  *  Licensed under GNU General Public License version 2
hausers@0:  *
hausers@0:  * Author: hausers@cs.tu-berlin.de
hausers@0:  */
hausers@0: 
hausers@0: #include <limits.h>
hausers@0: #include <stdio.h>
hausers@0: #include <string.h>
hausers@0: 
hausers@0: #include "PriorityQueue.h"
hausers@0: #ifndef DEBUG
hausers@1: #include "../../VMS_Implementations/VMS_impl/vmalloc.h"
hausers@0: #endif
hausers@0: 
hausers@0: #define left(i) 2*i
hausers@0: #define right(i) 2*i+1
hausers@0: #define parent(i) i/2
hausers@0: 
hausers@0: #ifdef DEBUG
hausers@0: #include <stdlib.h>
hausers@0: #define VMS__malloc malloc
hausers@0: #define VMS__free free
hausers@0: #endif 
hausers@0: 
hausers@0: void swap (PrioQueueStruc *Q, int a, int b) {
hausers@0: 	void *valTmp;
hausers@0: 	int keyTmp;
hausers@0: 	keyTmp= Q->data[a].key;
hausers@0: 	valTmp= Q->data[a].val;
hausers@0: 	Q->data[a].key= Q->data[b].key;
hausers@0: 	Q->data[a].val= Q->data[b].val;
hausers@0: 	Q->data[b].key= keyTmp;
hausers@0: 	Q->data[b].val= valTmp;
hausers@0: 	
hausers@0: }
hausers@0: 
hausers@0: bool increaseKey (PrioQueueStruc *Q, int i, int key) {
hausers@0: 	if (key < Q->data[i].key) return false; // increasing not possible
hausers@0: 
hausers@0: 	Q->data[i].key= key;
hausers@0: 	while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
hausers@0: 		swap(Q,i,parent(i));
hausers@0: 		i= parent(i);
hausers@0: 	}	
hausers@0: 	return true;
hausers@0: }
hausers@0: 
hausers@0: void heapify (PrioQueueStruc *Q, int i) {
hausers@0: 	int largest;
hausers@0: 	int l,r;
hausers@0: 	l= left(i);
hausers@0: 	r= right(i);
hausers@0: 	if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
hausers@0: 	else largest= i;
hausers@0: 	if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
hausers@0: 	if (largest != i) {
hausers@0: 		swap(Q,i,largest);
hausers@0: 		heapify(Q,largest);
hausers@0: 	}
hausers@0: }
hausers@0: 
hausers@0: void enlargePrioQ (PrioQueueStruc *Q)  {
hausers@0: 	size_t oldSize, newSize;
hausers@0: 	heapNode *oldData,*newData;
hausers@0: 
hausers@0: 	oldSize= Q->size;
hausers@0: 	newSize= 2*oldSize;
hausers@0: 
hausers@0: 	Q->maxSize= newSize;
hausers@0: 	newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
hausers@0: 	oldData= Q->data;
hausers@0: 
hausers@0: 	memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
hausers@0: 	Q->data= newData;
hausers@0: 
hausers@0: 	VMS__free(oldData);
hausers@0: }
hausers@0: 
hausers@0: 
Me@4: PrioQueueStruc* makePrioQ () {
hausers@0: 	PrioQueueStruc *retQ;
hausers@0: 	retQ= VMS__malloc(sizeof(PrioQueueStruc));
hausers@0: 	retQ->maxSize= 1024;
hausers@0: 	retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
hausers@0: 	retQ->size= 0;
hausers@0: 	return retQ;
hausers@0: }
hausers@0: 
hausers@0: void* getFirstPrioQ (PrioQueueStruc *Q) {
hausers@0: 	return Q->data[0].val;
hausers@0: }
hausers@0: 
hausers@0: void* popPrioQ (PrioQueueStruc *Q) {
hausers@0: 	void *max;
hausers@0: 	if (Q->size < 1) max= NULL;
hausers@0: 	else {
hausers@0: 		max= Q->data[0].val;
hausers@0: 		swap(Q,0,Q->size-1);
hausers@0: 		Q->size--;
hausers@0: 		heapify(Q,0);
hausers@0: 	}	
hausers@0: 	return max;
hausers@0: }
hausers@0: 
hausers@0: bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
hausers@0: 	if (Q->size == Q->maxSize) enlargePrioQ(Q);
hausers@0: 
hausers@0: 	Q->size++;
hausers@0: 	Q->data[Q->size-1].key= INT_MIN;
hausers@0: 	Q->data[Q->size-1].val= val;
hausers@0: 
hausers@0: 	return increaseKey(Q,Q->size-1,key);
hausers@0: }
hausers@0: 
hausers@0: void printPrioQ (PrioQueueStruc *Q) {
hausers@0: 	int i;
hausers@0: 	printf("{");
hausers@0: 	if (Q->size>0) printf("%s",(char *)Q->data[0].val);
hausers@0: 	for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
hausers@0: 	printf("} ... ");
hausers@0: 
hausers@0: }
hausers@0: 
hausers@0: void freePrioQ (PrioQueueStruc *Q) {
hausers@0: 	VMS__free(Q->data);
hausers@0: 	VMS__free(Q);
hausers@0: }