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

comparison PriorityQueue.c @ 0:9ecc993a29ea

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