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

view 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
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 */
7
8 #include "PriorityQueue.h"
9
10 #define left(i) 2*i
11 #define right(i) 2*i+1
12 #define parent(i) i/2
13
14 void swap (PrioQueueStruc *Q, int a, int b) {
15 void *valTmp;
16 int keyTmp;
17 keyTmp= Q->data[a].key;
18 valTmp= Q->data[a].val;
19 Q->data[a].key= Q->data[b].key;
20 Q->data[a].val= Q->data[b].val;
21 Q->data[b].key= keyTmp;
22 Q->data[b].val= valTmp;
23
24 }
25
26 bool increaseKey (PrioQueueStruc *Q, int i, int key) {
27 if (key < Q->data[i].key) return false; // increasing not possible
28
29 Q->data[i].key= key;
30 while (i>0 && Q->data[parent(i)].key < Q->data[i].key) {
31 swap(Q,i,parent(i));
32 i= parent(i);
33 }
34 return true;
35 }
36
37 void heapify (PrioQueueStruc *Q, int i) {
38 int largest;
39 int l,r;
40 l= left(i);
41 r= right(i);
42 if (l < Q->size && Q->data[l].key > Q->data[i].key) largest= l;
43 else largest= i;
44 if (r < Q->size && Q->data[r].key > Q->data[largest].key) largest= r;
45 if (largest != i) {
46 swap(Q,i,largest);
47 heapify(Q,largest);
48 }
49 }
50
51 void enlargePrioQ (PrioQueueStruc *Q) {
52 size_t oldSize, newSize;
53 heapNode *oldData,*newData;
54
55 oldSize= Q->size;
56 newSize= 2*oldSize;
57
58 Q->maxSize= newSize;
59 newData= malloc(Q->maxSize*sizeof(heapNode));
60 oldData= Q->data;
61
62 memcpy(newData,oldData,Q->maxSize*sizeof(heapNode));
63 Q->data= newData;
64
65 free(oldData);
66 }
67
68
69 PrioQueueStruc* makePrioQ () {
70 PrioQueueStruc *retQ;
71 retQ= malloc(sizeof(PrioQueueStruc));
72 retQ->maxSize= 1024;
73 retQ->data= malloc(retQ->maxSize*sizeof(heapNode));
74 retQ->size= 0;
75 return retQ;
76 }
77
78 void* getFirstPrioQ (PrioQueueStruc *Q) {
79 return Q->data[0].val;
80 }
81
82 void* popPrioQ (PrioQueueStruc *Q) {
83 void *max;
84 if (Q->size < 1) max= NULL;
85 else {
86 max= Q->data[0].val;
87 swap(Q,0,Q->size-1);
88 Q->size--;
89 heapify(Q,0);
90 }
91 return max;
92 }
93
94 bool insertPrioQ (void *val, int key, PrioQueueStruc *Q) {
95 if (Q->size == Q->maxSize) enlargePrioQ(Q);
96
97 Q->size++;
98 Q->data[Q->size-1].key= INT_MIN;
99 Q->data[Q->size-1].val= val;
100
101 return increaseKey(Q,Q->size-1,key);
102 }
103
104 void printPrioQ (PrioQueueStruc *Q) {
105 int i;
106 printf("{");
107 if (Q->size>0) printf("%s",(char *)Q->data[0].val);
108 for (i= 1; i<Q->size; i++) printf(",%s",(char *)Q->data[i].val);
109 printf("} ... ");
110
111 }
112
113 void freePrioQ (PrioQueueStruc *Q) {
114 free(Q->data);
115 free(Q);
116 }