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: 
seanhalle@11: //Stefan: nice use of macros  : )
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: 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: 
seanhalle@11: bool 
seanhalle@11: increaseKey( PrioQueueStruc *Q, int i, int key ) 
seanhalle@11:  {
seanhalle@11:    if( key < Q->data[i].key ) 
seanhalle@11:        return false; // increasing not possible
hausers@0: 
seanhalle@11:    Q->data[i].key= key;
seanhalle@11:    while( i > 0 && Q->data[parent(i)].key < Q->data[i].key )
seanhalle@11:     { swap( Q, i, parent(i) );
seanhalle@11:       i = parent(i);
seanhalle@11:     }
seanhalle@11:    return true;
seanhalle@11:  }
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: 
seanhalle@11: void 
seanhalle@11: enlargePrioQ( PrioQueueStruc *Q )
seanhalle@11:  { size_t oldSize, newSize;
seanhalle@11:    heapNode *oldData,*newData;
hausers@0: 
seanhalle@11:    oldSize = Q->size;
seanhalle@11:    newSize = 2*oldSize;
hausers@0: 
seanhalle@11:    Q->maxSize = newSize;
seanhalle@11:    newData = VMS_PI__malloc( Q->maxSize * sizeof(heapNode) );
seanhalle@11:    oldData = Q->data;
hausers@0: 
seanhalle@11:    //Stefan: should this be Q->maxSize, or oldSize?  Copying old data into
seanhalle@11:    // new array, so oldSize is the amount of data.. does the data need to
seanhalle@11:    // be re-arranged to make sure it still has heap invariant within the new
seanhalle@11:    // size?
seanhalle@11:    memcpy( newData, oldData, Q->maxSize * sizeof(heapNode) );
seanhalle@11:    Q->data = newData;
hausers@0: 
seanhalle@11:    VMS_PI__free(oldData);
seanhalle@11:  }
hausers@0: 
hausers@0: 
seanhalle@11: PrioQueueStruc * 
seanhalle@11: makePrioQ() 
seanhalle@11:  { PrioQueueStruc *newQ;
seanhalle@11:  
seanhalle@11:    newQ= VMS_int__malloc( sizeof(PrioQueueStruc) );
seanhalle@11:    newQ->maxSize= 1024;
seanhalle@11:    newQ->data= VMS_int__malloc( newQ->maxSize * sizeof(heapNode) );
seanhalle@11:    newQ->size= 0;
seanhalle@11:    
seanhalle@11:    return newQ;
seanhalle@11:  }
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;
seanhalle@11:  }
hausers@0: 
seanhalle@11: bool
seanhalle@11: insertPrioQ (void *val, int key, PrioQueueStruc *Q) 
seanhalle@11:  {
seanhalle@11:    if( Q->size == Q->maxSize ) enlargePrioQ(Q);
hausers@0: 
seanhalle@11:    Q->size++;
seanhalle@11:    Q->data[Q->size-1].key= INT_MIN;
seanhalle@11:    Q->data[Q->size-1].val= val;
hausers@0: 
seanhalle@11:    return increaseKey(Q, Q->size-1, key);
seanhalle@11:  }
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@9: void removePrioQ (int key, PrioQueueStruc *Q) {
hausers@9: //Sefan: TODO
hausers@9: }
hausers@9: 
hausers@0: void freePrioQ (PrioQueueStruc *Q) {
Me@5: 	VMS_int__free(Q->data);
Me@5: 	VMS_int__free(Q);
hausers@0: }