/*
 *  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"

//Stefan: nice use of macros  : )
#define left(i) 2*i
#define right(i) 2*i+1
#define parent(i) i/2

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_PI__malloc( Q->maxSize * sizeof(heapNode) );
   oldData = Q->data;

   //Stefan: should this be Q->maxSize, or oldSize?  Copying old data into
   // new array, so oldSize is the amount of data.. does the data need to
   // be re-arranged to make sure it still has heap invariant within the new
   // size?
   memcpy( newData, oldData, Q->maxSize * sizeof(heapNode) );
   Q->data = newData;

   VMS_PI__free(oldData);
 }


PrioQueueStruc * 
makePrioQ() 
 { PrioQueueStruc *newQ;
 
   newQ= VMS_int__malloc( sizeof(PrioQueueStruc) );
   newQ->maxSize= 1024;
   newQ->data= VMS_int__malloc( newQ->maxSize * sizeof(heapNode) );
   newQ->size= 0;
   
   return newQ;
 }

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 removePrioQ (int key, PrioQueueStruc *Q) {
//Sefan: TODO
}

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