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

comparison PriorityQueue.c @ 11:0de14128ff68

find changesets by author, revision, files, or words in the commit message
comments added for Stefan, and formatting changes
author Sean <seanhalle@yahoo.com>
date Thu, 17 May 2012 20:35:19 +0200
parents ee94893d2843
children
comparison
equal deleted inserted replaced
6:8df39d77eff9 7:36c4709e5e54
9 #include <stdio.h> 9 #include <stdio.h>
10 #include <string.h> 10 #include <string.h>
11 11
12 #include "PriorityQueue.h" 12 #include "PriorityQueue.h"
13 13
14 //Stefan: nice use of macros : )
14 #define left(i) 2*i 15 #define left(i) 2*i
15 #define right(i) 2*i+1 16 #define right(i) 2*i+1
16 #define parent(i) i/2 17 #define parent(i) i/2
17 18
18 void swap (PrioQueueStruc *Q, int a, int b) { 19 void swap (PrioQueueStruc *Q, int a, int b) {
25 Q->data[b].key= keyTmp; 26 Q->data[b].key= keyTmp;
26 Q->data[b].val= valTmp; 27 Q->data[b].val= valTmp;
27 28
28 } 29 }
29 30
30 bool increaseKey (PrioQueueStruc *Q, int i, int key) { 31 bool
31 if (key < Q->data[i].key) return false; // increasing not possible 32 increaseKey( PrioQueueStruc *Q, int i, int key )
33 {
34 if( key < Q->data[i].key )
35 return false; // increasing not possible
32 36
33 Q->data[i].key= key; 37 Q->data[i].key= key;
34 while (i>0 && Q->data[parent(i)].key < Q->data[i].key) { 38 while( i > 0 && Q->data[parent(i)].key < Q->data[i].key )
35 swap(Q,i,parent(i)); 39 { swap( Q, i, parent(i) );
36 i= parent(i); 40 i = parent(i);
37 } 41 }
38 return true; 42 return true;
39 } 43 }
40 44
41 void heapify (PrioQueueStruc *Q, int i) { 45 void heapify (PrioQueueStruc *Q, int i) {
42 int largest; 46 int largest;
43 int l,r; 47 int l,r;
44 l= left(i); 48 l= left(i);
50 swap(Q,i,largest); 54 swap(Q,i,largest);
51 heapify(Q,largest); 55 heapify(Q,largest);
52 } 56 }
53 } 57 }
54 58
55 void enlargePrioQ (PrioQueueStruc *Q) { 59 void
56 size_t oldSize, newSize; 60 enlargePrioQ( PrioQueueStruc *Q )
57 heapNode *oldData,*newData; 61 { size_t oldSize, newSize;
62 heapNode *oldData,*newData;
58 63
59 oldSize= Q->size; 64 oldSize = Q->size;
60 newSize= 2*oldSize; 65 newSize = 2*oldSize;
61 66
62 Q->maxSize= newSize; 67 Q->maxSize = newSize;
63 newData= VMS_PI__malloc(Q->maxSize*sizeof(heapNode)); 68 newData = VMS_PI__malloc( Q->maxSize * sizeof(heapNode) );
64 oldData= Q->data; 69 oldData = Q->data;
65 70
66 memcpy(newData,oldData,Q->maxSize*sizeof(heapNode)); 71 //Stefan: should this be Q->maxSize, or oldSize? Copying old data into
67 Q->data= newData; 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;
68 77
69 VMS_PI__free(oldData); 78 VMS_PI__free(oldData);
70 } 79 }
71 80
72 81
73 PrioQueueStruc* makePrioQ () { 82 PrioQueueStruc *
74 PrioQueueStruc *retQ; 83 makePrioQ()
75 retQ= VMS_int__malloc(sizeof(PrioQueueStruc)); 84 { PrioQueueStruc *newQ;
76 retQ->maxSize= 1024; 85
77 retQ->data= VMS_int__malloc(retQ->maxSize*sizeof(heapNode)); 86 newQ= VMS_int__malloc( sizeof(PrioQueueStruc) );
78 retQ->size= 0; 87 newQ->maxSize= 1024;
79 return retQ; 88 newQ->data= VMS_int__malloc( newQ->maxSize * sizeof(heapNode) );
80 } 89 newQ->size= 0;
90
91 return newQ;
92 }
81 93
82 void* getFirstPrioQ (PrioQueueStruc *Q) { 94 void* getFirstPrioQ (PrioQueueStruc *Q) {
83 return Q->data[0].val; 95 return Q->data[0].val;
84 } 96 }
85 97
91 swap(Q,0,Q->size-1); 103 swap(Q,0,Q->size-1);
92 Q->size--; 104 Q->size--;
93 heapify(Q,0); 105 heapify(Q,0);
94 } 106 }
95 return max; 107 return max;
96 } 108 }
97 109
98 bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) { 110 bool
99 if (Q->size == Q->maxSize) enlargePrioQ(Q); 111 insertPrioQ (void *val, int key, PrioQueueStruc *Q)
112 {
113 if( Q->size == Q->maxSize ) enlargePrioQ(Q);
100 114
101 Q->size++; 115 Q->size++;
102 Q->data[Q->size-1].key= INT_MIN; 116 Q->data[Q->size-1].key= INT_MIN;
103 Q->data[Q->size-1].val= val; 117 Q->data[Q->size-1].val= val;
104 118
105 return increaseKey(Q,Q->size-1,key); 119 return increaseKey(Q, Q->size-1, key);
106 } 120 }
107 121
108 void printPrioQ (PrioQueueStruc *Q) { 122 void printPrioQ (PrioQueueStruc *Q) {
109 int i; 123 int i;
110 printf("{"); 124 printf("{");
111 if (Q->size>0) printf("%s",(char *)Q->data[0].val); 125 if (Q->size>0) printf("%s",(char *)Q->data[0].val);