1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/PriorityQueue.c	Thu Feb 09 11:48:03 2012 +0100
     1.3 @@ -0,0 +1,129 @@
     1.4 +/*
     1.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     1.6 + *  Licensed under GNU General Public License version 2
     1.7 + *
     1.8 + * Author: hausers@cs.tu-berlin.de
     1.9 + */
    1.10 +
    1.11 +#include <limits.h>
    1.12 +#include <stdio.h>
    1.13 +#include <string.h>
    1.14 +
    1.15 +#include "PriorityQueue.h"
    1.16 +#ifndef DEBUG
    1.17 +#include "../VMS/vmalloc.h"
    1.18 +#endif
    1.19 +
    1.20 +#define left(i) 2*i
    1.21 +#define right(i) 2*i+1
    1.22 +#define parent(i) i/2
    1.23 +
    1.24 +#ifdef DEBUG
    1.25 +#include <stdlib.h>
    1.26 +#define VMS__malloc malloc
    1.27 +#define VMS__free free
    1.28 +#endif 
    1.29 +
    1.30 +void swap (PrioQueueStruc *Q, int a, int b) {
    1.31 +	void *valTmp;
    1.32 +	int keyTmp;
    1.33 +	keyTmp= Q->data[a].key;
    1.34 +	valTmp= Q->data[a].val;
    1.35 +	Q->data[a].key= Q->data[b].key;
    1.36 +	Q->data[a].val= Q->data[b].val;
    1.37 +	Q->data[b].key= keyTmp;
    1.38 +	Q->data[b].val= valTmp;
    1.39 +	
    1.40 +}
    1.41 +
    1.42 +bool increaseKey (PrioQueueStruc *Q, int i, int key) {
    1.43 +	if (key < Q->data[i].key) return false; // increasing not possible
    1.44 +
    1.45 +	Q->data[i].key= key;
    1.46 +	while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
    1.47 +		swap(Q,i,parent(i));
    1.48 +		i= parent(i);
    1.49 +	}	
    1.50 +	return true;
    1.51 +}
    1.52 +
    1.53 +void heapify (PrioQueueStruc *Q, int i) {
    1.54 +	int largest;
    1.55 +	int l,r;
    1.56 +	l= left(i);
    1.57 +	r= right(i);
    1.58 +	if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
    1.59 +	else largest= i;
    1.60 +	if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
    1.61 +	if (largest != i) {
    1.62 +		swap(Q,i,largest);
    1.63 +		heapify(Q,largest);
    1.64 +	}
    1.65 +}
    1.66 +
    1.67 +void enlargePrioQ (PrioQueueStruc *Q)  {
    1.68 +	size_t oldSize, newSize;
    1.69 +	heapNode *oldData,*newData;
    1.70 +
    1.71 +	oldSize= Q->size;
    1.72 +	newSize= 2*oldSize;
    1.73 +
    1.74 +	Q->maxSize= newSize;
    1.75 +	newData= VMS__malloc(Q->maxSize*sizeof(heapNode));
    1.76 +	oldData= Q->data;
    1.77 +
    1.78 +	memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
    1.79 +	Q->data= newData;
    1.80 +
    1.81 +	VMS__free(oldData);
    1.82 +}
    1.83 +
    1.84 +
    1.85 +PrioQueueStruc* makeVMSPrioQ () {
    1.86 +	PrioQueueStruc *retQ;
    1.87 +	retQ= VMS__malloc(sizeof(PrioQueueStruc));
    1.88 +	retQ->maxSize= 1024;
    1.89 +	retQ->data= VMS__malloc(retQ->maxSize*sizeof(heapNode));
    1.90 +	retQ->size= 0;
    1.91 +	return retQ;
    1.92 +}
    1.93 +
    1.94 +void* getFirstPrioQ (PrioQueueStruc *Q) {
    1.95 +	return Q->data[0].val;
    1.96 +}
    1.97 +
    1.98 +void* popPrioQ (PrioQueueStruc *Q) {
    1.99 +	void *max;
   1.100 +	if (Q->size < 1) max= NULL;
   1.101 +	else {
   1.102 +		max= Q->data[0].val;
   1.103 +		swap(Q,0,Q->size-1);
   1.104 +		Q->size--;
   1.105 +		heapify(Q,0);
   1.106 +	}	
   1.107 +	return max;
   1.108 +}
   1.109 +
   1.110 +bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
   1.111 +	if (Q->size == Q->maxSize) enlargePrioQ(Q);
   1.112 +
   1.113 +	Q->size++;
   1.114 +	Q->data[Q->size-1].key= INT_MIN;
   1.115 +	Q->data[Q->size-1].val= val;
   1.116 +
   1.117 +	return increaseKey(Q,Q->size-1,key);
   1.118 +}
   1.119 +
   1.120 +void printPrioQ (PrioQueueStruc *Q) {
   1.121 +	int i;
   1.122 +	printf("{");
   1.123 +	if (Q->size>0) printf("%s",(char *)Q->data[0].val);
   1.124 +	for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
   1.125 +	printf("} ... ");
   1.126 +
   1.127 +}
   1.128 +
   1.129 +void freePrioQ (PrioQueueStruc *Q) {
   1.130 +	VMS__free(Q->data);
   1.131 +	VMS__free(Q);
   1.132 +}