Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > PriorityQueue

annotate PriorityQueue.c @ 3:500d0e2fabfb

find changesets by author, revision, files, or words in the commit message
made pure C and added .brch__defaul and eol handling
author Me@portablequad
date Sat, 11 Feb 2012 20:27:13 -0800
parents 4d8a1e0f4336
children
rev   line source
hausers@0 1 /*
hausers@0 2 * Copyright 2009 OpenSourceStewardshipFoundation.org
hausers@0 3 * Licensed under GNU General Public License version 2
hausers@0 4 *
hausers@0 5 * Author: hausers@cs.tu-berlin.de
hausers@0 6 */
hausers@0 7
hausers@0 8 #include "PriorityQueue.h"
hausers@0 9
hausers@0 10 #define left(i) 2*i
hausers@0 11 #define right(i) 2*i+1
hausers@0 12 #define parent(i) i/2
hausers@0 13
hausers@0 14 void swap (PrioQueueStruc *Q, int a, int b) {
hausers@0 15 void *valTmp;
hausers@0 16 int keyTmp;
hausers@0 17 keyTmp= Q->data[a].key;
hausers@0 18 valTmp= Q->data[a].val;
hausers@0 19 Q->data[a].key= Q->data[b].key;
hausers@0 20 Q->data[a].val= Q->data[b].val;
hausers@0 21 Q->data[b].key= keyTmp;
hausers@0 22 Q->data[b].val= valTmp;
hausers@0 23
hausers@0 24 }
hausers@0 25
hausers@0 26 bool increaseKey (PrioQueueStruc *Q, int i, int key) {
hausers@0 27 if (key < Q->data[i].key) return false; // increasing not possible
hausers@0 28
hausers@0 29 Q->data[i].key= key;
hausers@0 30 while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
hausers@0 31 swap(Q,i,parent(i));
hausers@0 32 i= parent(i);
hausers@0 33 }
hausers@0 34 return true;
hausers@0 35 }
hausers@0 36
hausers@0 37 void heapify (PrioQueueStruc *Q, int i) {
hausers@0 38 int largest;
hausers@0 39 int l,r;
hausers@0 40 l= left(i);
hausers@0 41 r= right(i);
hausers@0 42 if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
hausers@0 43 else largest= i;
hausers@0 44 if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
hausers@0 45 if (largest != i) {
hausers@0 46 swap(Q,i,largest);
hausers@0 47 heapify(Q,largest);
hausers@0 48 }
hausers@0 49 }
hausers@0 50
hausers@0 51 void enlargePrioQ (PrioQueueStruc *Q) {
hausers@0 52 size_t oldSize, newSize;
hausers@0 53 heapNode *oldData,*newData;
hausers@0 54
hausers@0 55 oldSize= Q->size;
hausers@0 56 newSize= 2*oldSize;
hausers@0 57
hausers@0 58 Q->maxSize= newSize;
Me@3 59 newData= malloc(Q->maxSize*sizeof(heapNode));
hausers@0 60 oldData= Q->data;
hausers@0 61
hausers@0 62 memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
hausers@0 63 Q->data= newData;
hausers@0 64
Me@3 65 free(oldData);
hausers@0 66 }
hausers@0 67
hausers@0 68
Me@3 69 PrioQueueStruc* makePrioQ () {
hausers@0 70 PrioQueueStruc *retQ;
Me@3 71 retQ= malloc(sizeof(PrioQueueStruc));
hausers@0 72 retQ->maxSize= 1024;
Me@3 73 retQ->data= malloc(retQ->maxSize*sizeof(heapNode));
hausers@0 74 retQ->size= 0;
hausers@0 75 return retQ;
hausers@0 76 }
hausers@0 77
hausers@0 78 void* getFirstPrioQ (PrioQueueStruc *Q) {
hausers@0 79 return Q->data[0].val;
hausers@0 80 }
hausers@0 81
hausers@0 82 void* popPrioQ (PrioQueueStruc *Q) {
hausers@0 83 void *max;
hausers@0 84 if (Q->size < 1) max= NULL;
hausers@0 85 else {
hausers@0 86 max= Q->data[0].val;
hausers@0 87 swap(Q,0,Q->size-1);
hausers@0 88 Q->size--;
hausers@0 89 heapify(Q,0);
hausers@0 90 }
hausers@0 91 return max;
hausers@0 92 }
hausers@0 93
hausers@0 94 bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
hausers@0 95 if (Q->size == Q->maxSize) enlargePrioQ(Q);
hausers@0 96
hausers@0 97 Q->size++;
hausers@0 98 Q->data[Q->size-1].key= INT_MIN;
hausers@0 99 Q->data[Q->size-1].val= val;
hausers@0 100
hausers@0 101 return increaseKey(Q,Q->size-1,key);
hausers@0 102 }
hausers@0 103
hausers@0 104 void printPrioQ (PrioQueueStruc *Q) {
hausers@0 105 int i;
hausers@0 106 printf("{");
hausers@0 107 if (Q->size>0) printf("%s",(char *)Q->data[0].val);
hausers@0 108 for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
hausers@0 109 printf("} ... ");
hausers@0 110
hausers@0 111 }
hausers@0 112
hausers@0 113 void freePrioQ (PrioQueueStruc *Q) {
Me@3 114 free(Q->data);
Me@3 115 free(Q);
hausers@0 116 }