1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "BinaryHeap.h"
15
16BinaryHeap BinaryHeap_new(int (*cmp)(void*item1, void*item2)){
17 BinaryHeap h;
18 int max_len = 1<<8, i;
19
20 h = MALLOC(sizeof(struct BinaryHeap_struct));
21 h->max_len = max_len;
22 h->len = 0;
23 h->heap = MALLOC(sizeof(void*)*max_len);
24 h->id_to_pos = MALLOC(sizeof(int)*max_len);
25 for (i = 0; i < max_len; i++) (h->id_to_pos)[i] = -1;
26
27 h->pos_to_id = MALLOC(sizeof(int)*max_len);
28 h->id_stack = IntStack_new();
29 h->cmp = cmp;
30 return h;
31}
32
33
34void BinaryHeap_delete(BinaryHeap h, void (*del)(void* item)){
35 int i;
36 if (!h) return;
37 FREE(h->id_to_pos);
38 FREE(h->pos_to_id);
39 IntStack_delete(h->id_stack);
40 if (del) for (i = 0; i < h->len; i++) del((h->heap)[i]);
41 FREE(h->heap);
42 FREE(h);
43}
44
45static BinaryHeap BinaryHeap_realloc(BinaryHeap h){
46 int max_len0 = h->max_len, max_len = h->max_len, i;
47 max_len = max_len + MAX(0.2*max_len, 10);
48 h->max_len = max_len;
49
50 h->heap = REALLOC(h->heap, sizeof(void*)*max_len);
51 if (!(h->heap)) return NULL;
52
53 h->id_to_pos = REALLOC(h->id_to_pos, sizeof(int)*max_len);
54 if (!(h->id_to_pos)) return NULL;
55
56 h->pos_to_id = REALLOC(h->pos_to_id, sizeof(int)*max_len);
57 if (!(h->pos_to_id)) return NULL;
58
59 for (i = max_len0; i < max_len; i++) (h->id_to_pos)[i] = -1;
60 return h;
61
62}
63
64#define ParentPos(pos) (pos - 1)/2
65#define ChildrenPos1(pos) (2*(pos)+1)
66#define ChildrenPos2(pos) (2*(pos)+2)
67
68static void swap(BinaryHeap h, int parentPos, int nodePos){
69 int parentID, nodeID;
70 void *tmp;
71 void **heap = h->heap;
72 int *id_to_pos = h->id_to_pos, *pos_to_id = h->pos_to_id;
73
74 assert(parentPos < h->len);
75 assert(nodePos < h->len);
76
77 parentID = pos_to_id[parentPos];
78 nodeID = pos_to_id[nodePos];
79
80 tmp = heap[parentPos];
81 heap[parentPos] = heap[nodePos];
82 heap[nodePos] = tmp;
83
84 pos_to_id[parentPos] = nodeID;
85 id_to_pos[nodeID] = parentPos;
86
87 pos_to_id[nodePos] = parentID;
88 id_to_pos[parentID] = nodePos;
89
90}
91
92static int siftUp(BinaryHeap h, int nodePos){
93 int parentPos;
94
95 void **heap = h->heap;
96
97
98 if (nodePos != 0) {
99 parentPos = ParentPos(nodePos);
100
101 if ((h->cmp)(heap[parentPos], heap[nodePos]) == 1) {/* if smaller than parent, swap */
102 swap(h, parentPos, nodePos);
103 nodePos = siftUp(h, parentPos);
104 }
105 }
106 return nodePos;
107}
108
109static int siftDown(BinaryHeap h, int nodePos){
110 int childPos, childPos1, childPos2;
111
112 void **heap = h->heap;
113
114
115 childPos1 = ChildrenPos1(nodePos);
116 childPos2 = ChildrenPos2(nodePos);
117 if (childPos1 > h->len - 1) return nodePos;/* no child */
118 if (childPos1 == h->len - 1) {
119 childPos = childPos1;/* one child */
120 } else {/* two child */
121 if ((h->cmp)(heap[childPos1], heap[childPos2]) == 1){ /* pick the smaller of the two child */
122 childPos = childPos2;
123 } else {
124 childPos = childPos1;
125 }
126 }
127
128 if ((h->cmp)(heap[nodePos], heap[childPos]) == 1) {
129 /* if larger than child, swap */
130 swap(h, nodePos, childPos);
131 nodePos = siftDown(h, childPos);
132 }
133
134 return nodePos;
135}
136
137int BinaryHeap_insert(BinaryHeap h, void *item){
138 int len = h->len, id = len, flag, pos;
139
140 /* insert an item, and return its ID. This ID can be used later to extract the item */
141 if (len > h->max_len - 1) {
142 if (BinaryHeap_realloc(h) == NULL) return BinaryHeap_error_malloc;
143 }
144
145 /* check if we have IDs in the stack to reuse. If no, then assign the last pos as the ID */
146 id = IntStack_pop(h->id_stack, &flag);
147 if (flag) id = len;
148
149 h->heap[len] = item;
150 h->id_to_pos[id] = len;
151 h->pos_to_id[len] = id;
152
153 (h->len)++;
154
155 pos = siftUp(h, len);
156 assert(h->id_to_pos[id] == pos);
157 assert(h->pos_to_id[pos] == id);
158
159
160 return id;
161}
162
163
164void* BinaryHeap_get_min(BinaryHeap h){
165 /* return the min item */
166 return h->heap[0];
167}
168
169void* BinaryHeap_extract_min(BinaryHeap h){
170 /* return and remove the min item */
171 if (h->len == 0) return NULL;
172 return BinaryHeap_extract_item(h, (h->pos_to_id)[0]);
173}
174
175void* BinaryHeap_extract_item(BinaryHeap h, int id){
176 /* extract an item with ID out and delete it */
177 void *item;
178 int *id_to_pos = h->id_to_pos;
179 int pos;
180
181 if (id >= h->max_len) return NULL;
182
183 pos = id_to_pos[id];
184
185 if (pos < 0) return NULL;
186
187 assert(pos < h->len);
188
189 item = (h->heap)[pos];
190
191 IntStack_push(h->id_stack, id);
192
193 if (pos < h->len - 1){/* move the last item to occupy the position of extracted item */
194 swap(h, pos, h->len - 1);
195 (h->len)--;
196 pos = siftUp(h, pos);
197 pos = siftDown(h, pos);
198 } else {
199 (h->len)--;
200 }
201
202 (h->id_to_pos)[id] = -1;
203
204 return item;
205
206}
207
208int BinaryHeap_reset(BinaryHeap h, int id, void *item){
209 /* reset value of an item with specified id */
210 int pos;
211
212 if (id >= h->max_len) return -1;
213 pos = h->id_to_pos[id];
214 if (pos < 0) return -1;
215
216 h->heap[pos] = item;
217
218 pos = siftUp(h, pos);
219
220 pos = siftDown(h, pos);
221
222 return pos;
223
224}
225void* BinaryHeap_get_item(BinaryHeap h, int id){
226 /* get an item with ID out, without deleting */
227 int pos;
228
229 if (id >= h->max_len) return NULL;
230
231 pos = h->id_to_pos[id];
232
233 if (pos < 0) return NULL;
234 return (h->heap)[pos];
235}
236
237void BinaryHeap_sanity_check(BinaryHeap h){
238 int i, key_spare, parentPos, *id_to_pos = h->id_to_pos, *pos_to_id = h->pos_to_id;
239 void **heap = h->heap;
240 int *mask;
241
242 /* check that this is a binary heap: children is smaller than parent */
243 for (i = 1; i < h->len; i++){
244 parentPos = ParentPos(i);
245 assert((h->cmp)(heap[i], heap[parentPos]) >= 0);
246 }
247
248 mask = MALLOC(sizeof(int)*(h->len + IntStack_get_length(h->id_stack)));
249 for (i = 0; i < h->len + IntStack_get_length(h->id_stack); i++) mask[i] = -1;
250
251 /* check that spare keys has negative id_to_pos mapping */
252 for (i = 0; i <= h->id_stack->last; i++){
253 key_spare = h->id_stack->stack[i];
254 assert(h->id_to_pos[key_spare] < 0);
255 mask[key_spare] = 1;/* mask spare ID */
256 }
257
258 /* check that
259 pos_to_id[id_to_pos[i]] = i, for i not in the id_stack & i < length(id_stack)+len
260 id_to_pos[pos_to_id[i]] = i, 0 <= i < len
261 */
262 for (i = 1; i < h->len; i++){
263 assert(mask[pos_to_id[i]] == -1);/* that id is in use so can't be spare */
264 mask[pos_to_id[i]] = 1;
265 assert(id_to_pos[pos_to_id[i]] == i);
266 }
267
268 /* all IDs, spare or in use, are ccounted for and give a contiguous set */
269 for (i = 0; i < h->len + IntStack_get_length(h->id_stack); i++) assert(mask[i] =- 1);
270
271 FREE(mask);
272}
273void BinaryHeap_print(BinaryHeap h, void (*pnt)(void*)){
274 int i, k = 2;
275
276 for (i = 0; i < h->len; i++){
277 pnt(h->heap[i]);
278 fprintf(stderr, "(%d) ",(h->pos_to_id)[i]);
279 if (i == k-2) {
280 fprintf(stderr, "\n");
281 k *= 2;
282 }
283 }
284 fprintf(stderr, "\nSpare keys =");
285 for (i = 0; i <= h->id_stack->last; i++){
286 fprintf(stderr,"%d(%d) ",h->id_stack->stack[i], h->id_to_pos[h->id_stack->stack[i]]);
287 }
288 fprintf(stderr, "\n");
289}
290
291
292