Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > PriorityQueue
view PriorityQueue.c @ 11:0de14128ff68
comments added for Stefan, and formatting changes
| author | Sean <seanhalle@yahoo.com> |
|---|---|
| date | Thu, 17 May 2012 20:35:19 +0200 |
| parents | ee94893d2843 |
| children |
line source
1 /*
2 * Copyright 2009 OpenSourceStewardshipFoundation.org
3 * Licensed under GNU General Public License version 2
4 *
5 * Author: hausers@cs.tu-berlin.de
6 */
8 #include <limits.h>
9 #include <stdio.h>
10 #include <string.h>
12 #include "PriorityQueue.h"
14 //Stefan: nice use of macros : )
15 #define left(i) 2*i
16 #define right(i) 2*i+1
17 #define parent(i) i/2
19 void swap (PrioQueueStruc *Q, int a, int b) {
20 void *valTmp;
21 int keyTmp;
22 keyTmp= Q->data[a].key;
23 valTmp= Q->data[a].val;
24 Q->data[a].key= Q->data[b].key;
25 Q->data[a].val= Q->data[b].val;
26 Q->data[b].key= keyTmp;
27 Q->data[b].val= valTmp;
29 }
31 bool
32 increaseKey( PrioQueueStruc *Q, int i, int key )
33 {
34 if( key < Q->data[i].key )
35 return false; // increasing not possible
37 Q->data[i].key= key;
38 while( i > 0 && Q->data[parent(i)].key < Q->data[i].key )
39 { swap( Q, i, parent(i) );
40 i = parent(i);
41 }
42 return true;
43 }
45 void heapify (PrioQueueStruc *Q, int i) {
46 int largest;
47 int l,r;
48 l= left(i);
49 r= right(i);
50 if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
51 else largest= i;
52 if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
53 if (largest != i) {
54 swap(Q,i,largest);
55 heapify(Q,largest);
56 }
57 }
59 void
60 enlargePrioQ( PrioQueueStruc *Q )
61 { size_t oldSize, newSize;
62 heapNode *oldData,*newData;
64 oldSize = Q->size;
65 newSize = 2*oldSize;
67 Q->maxSize = newSize;
68 newData = VMS_PI__malloc( Q->maxSize * sizeof(heapNode) );
69 oldData = Q->data;
71 //Stefan: should this be Q->maxSize, or oldSize? Copying old data into
72 // new array, so oldSize is the amount of data.. does the data need to
73 // be re-arranged to make sure it still has heap invariant within the new
74 // size?
75 memcpy( newData, oldData, Q->maxSize * sizeof(heapNode) );
76 Q->data = newData;
78 VMS_PI__free(oldData);
79 }
82 PrioQueueStruc *
83 makePrioQ()
84 { PrioQueueStruc *newQ;
86 newQ= VMS_int__malloc( sizeof(PrioQueueStruc) );
87 newQ->maxSize= 1024;
88 newQ->data= VMS_int__malloc( newQ->maxSize * sizeof(heapNode) );
89 newQ->size= 0;
91 return newQ;
92 }
94 void* getFirstPrioQ (PrioQueueStruc *Q) {
95 return Q->data[0].val;
96 }
98 void* popPrioQ (PrioQueueStruc *Q) {
99 void *max;
100 if (Q->size < 1) max= NULL;
101 else {
102 max= Q->data[0].val;
103 swap(Q,0,Q->size-1);
104 Q->size--;
105 heapify(Q,0);
106 }
107 return max;
108 }
110 bool
111 insertPrioQ (void *val, int key, PrioQueueStruc *Q)
112 {
113 if( Q->size == Q->maxSize ) enlargePrioQ(Q);
115 Q->size++;
116 Q->data[Q->size-1].key= INT_MIN;
117 Q->data[Q->size-1].val= val;
119 return increaseKey(Q, Q->size-1, key);
120 }
122 void printPrioQ (PrioQueueStruc *Q) {
123 int i;
124 printf("{");
125 if (Q->size>0) printf("%s",(char *)Q->data[0].val);
126 for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
127 printf("} ... ");
129 }
131 void removePrioQ (int key, PrioQueueStruc *Q) {
132 //Sefan: TODO
133 }
135 void freePrioQ (PrioQueueStruc *Q) {
136 VMS_int__free(Q->data);
137 VMS_int__free(Q);
138 }