| 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 <limits.h>
|
|
hausers@0
|
9 #include <stdio.h>
|
|
hausers@0
|
10 #include <string.h>
|
|
hausers@0
|
11
|
|
hausers@0
|
12 #include "PriorityQueue.h"
|
|
hausers@0
|
13
|
|
seanhalle@11
|
14 //Stefan: nice use of macros : )
|
|
hausers@0
|
15 #define left(i) 2*i
|
|
hausers@0
|
16 #define right(i) 2*i+1
|
|
hausers@0
|
17 #define parent(i) i/2
|
|
hausers@0
|
18
|
|
hausers@0
|
19 void swap (PrioQueueStruc *Q, int a, int b) {
|
|
hausers@0
|
20 void *valTmp;
|
|
hausers@0
|
21 int keyTmp;
|
|
hausers@0
|
22 keyTmp= Q->data[a].key;
|
|
hausers@0
|
23 valTmp= Q->data[a].val;
|
|
hausers@0
|
24 Q->data[a].key= Q->data[b].key;
|
|
hausers@0
|
25 Q->data[a].val= Q->data[b].val;
|
|
hausers@0
|
26 Q->data[b].key= keyTmp;
|
|
hausers@0
|
27 Q->data[b].val= valTmp;
|
|
hausers@0
|
28
|
|
hausers@0
|
29 }
|
|
hausers@0
|
30
|
|
seanhalle@11
|
31 bool
|
|
seanhalle@11
|
32 increaseKey( PrioQueueStruc *Q, int i, int key )
|
|
seanhalle@11
|
33 {
|
|
seanhalle@11
|
34 if( key < Q->data[i].key )
|
|
seanhalle@11
|
35 return false; // increasing not possible
|
|
hausers@0
|
36
|
|
seanhalle@11
|
37 Q->data[i].key= key;
|
|
seanhalle@11
|
38 while( i > 0 && Q->data[parent(i)].key < Q->data[i].key )
|
|
seanhalle@11
|
39 { swap( Q, i, parent(i) );
|
|
seanhalle@11
|
40 i = parent(i);
|
|
seanhalle@11
|
41 }
|
|
seanhalle@11
|
42 return true;
|
|
seanhalle@11
|
43 }
|
|
hausers@0
|
44
|
|
hausers@0
|
45 void heapify (PrioQueueStruc *Q, int i) {
|
|
hausers@0
|
46 int largest;
|
|
hausers@0
|
47 int l,r;
|
|
hausers@0
|
48 l= left(i);
|
|
hausers@0
|
49 r= right(i);
|
|
hausers@0
|
50 if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
|
|
hausers@0
|
51 else largest= i;
|
|
hausers@0
|
52 if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
|
|
hausers@0
|
53 if (largest != i) {
|
|
hausers@0
|
54 swap(Q,i,largest);
|
|
hausers@0
|
55 heapify(Q,largest);
|
|
hausers@0
|
56 }
|
|
hausers@0
|
57 }
|
|
hausers@0
|
58
|
|
seanhalle@11
|
59 void
|
|
seanhalle@11
|
60 enlargePrioQ( PrioQueueStruc *Q )
|
|
seanhalle@11
|
61 { size_t oldSize, newSize;
|
|
seanhalle@11
|
62 heapNode *oldData,*newData;
|
|
hausers@0
|
63
|
|
seanhalle@11
|
64 oldSize = Q->size;
|
|
seanhalle@11
|
65 newSize = 2*oldSize;
|
|
hausers@0
|
66
|
|
seanhalle@11
|
67 Q->maxSize = newSize;
|
|
seanhalle@11
|
68 newData = VMS_PI__malloc( Q->maxSize * sizeof(heapNode) );
|
|
seanhalle@11
|
69 oldData = Q->data;
|
|
hausers@0
|
70
|
|
seanhalle@11
|
71 //Stefan: should this be Q->maxSize, or oldSize? Copying old data into
|
|
seanhalle@11
|
72 // new array, so oldSize is the amount of data.. does the data need to
|
|
seanhalle@11
|
73 // be re-arranged to make sure it still has heap invariant within the new
|
|
seanhalle@11
|
74 // size?
|
|
seanhalle@11
|
75 memcpy( newData, oldData, Q->maxSize * sizeof(heapNode) );
|
|
seanhalle@11
|
76 Q->data = newData;
|
|
hausers@0
|
77
|
|
seanhalle@11
|
78 VMS_PI__free(oldData);
|
|
seanhalle@11
|
79 }
|
|
hausers@0
|
80
|
|
hausers@0
|
81
|
|
seanhalle@11
|
82 PrioQueueStruc *
|
|
seanhalle@11
|
83 makePrioQ()
|
|
seanhalle@11
|
84 { PrioQueueStruc *newQ;
|
|
seanhalle@11
|
85
|
|
seanhalle@11
|
86 newQ= VMS_int__malloc( sizeof(PrioQueueStruc) );
|
|
seanhalle@11
|
87 newQ->maxSize= 1024;
|
|
seanhalle@11
|
88 newQ->data= VMS_int__malloc( newQ->maxSize * sizeof(heapNode) );
|
|
seanhalle@11
|
89 newQ->size= 0;
|
|
seanhalle@11
|
90
|
|
seanhalle@11
|
91 return newQ;
|
|
seanhalle@11
|
92 }
|
|
hausers@0
|
93
|
|
hausers@0
|
94 void* getFirstPrioQ (PrioQueueStruc *Q) {
|
|
hausers@0
|
95 return Q->data[0].val;
|
|
hausers@0
|
96 }
|
|
hausers@0
|
97
|
|
hausers@0
|
98 void* popPrioQ (PrioQueueStruc *Q) {
|
|
hausers@0
|
99 void *max;
|
|
hausers@0
|
100 if (Q->size < 1) max= NULL;
|
|
hausers@0
|
101 else {
|
|
hausers@0
|
102 max= Q->data[0].val;
|
|
hausers@0
|
103 swap(Q,0,Q->size-1);
|
|
hausers@0
|
104 Q->size--;
|
|
hausers@0
|
105 heapify(Q,0);
|
|
hausers@0
|
106 }
|
|
hausers@0
|
107 return max;
|
|
seanhalle@11
|
108 }
|
|
hausers@0
|
109
|
|
seanhalle@11
|
110 bool
|
|
seanhalle@11
|
111 insertPrioQ (void *val, int key, PrioQueueStruc *Q)
|
|
seanhalle@11
|
112 {
|
|
seanhalle@11
|
113 if( Q->size == Q->maxSize ) enlargePrioQ(Q);
|
|
hausers@0
|
114
|
|
seanhalle@11
|
115 Q->size++;
|
|
seanhalle@11
|
116 Q->data[Q->size-1].key= INT_MIN;
|
|
seanhalle@11
|
117 Q->data[Q->size-1].val= val;
|
|
hausers@0
|
118
|
|
seanhalle@11
|
119 return increaseKey(Q, Q->size-1, key);
|
|
seanhalle@11
|
120 }
|
|
hausers@0
|
121
|
|
hausers@0
|
122 void printPrioQ (PrioQueueStruc *Q) {
|
|
hausers@0
|
123 int i;
|
|
hausers@0
|
124 printf("{");
|
|
hausers@0
|
125 if (Q->size>0) printf("%s",(char *)Q->data[0].val);
|
|
hausers@0
|
126 for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
|
|
hausers@0
|
127 printf("} ... ");
|
|
hausers@0
|
128
|
|
hausers@0
|
129 }
|
|
hausers@0
|
130
|
|
hausers@9
|
131 void removePrioQ (int key, PrioQueueStruc *Q) {
|
|
hausers@9
|
132 //Sefan: TODO
|
|
hausers@9
|
133 }
|
|
hausers@9
|
134
|
|
hausers@0
|
135 void freePrioQ (PrioQueueStruc *Q) {
|
|
Me@5
|
136 VMS_int__free(Q->data);
|
|
Me@5
|
137 VMS_int__free(Q);
|
|
hausers@0
|
138 }
|
