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 | |
16 | BinaryHeap 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 | |
34 | void 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 | |
45 | static 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 | |
68 | static 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 | |
92 | static 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 | |
109 | static 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 | |
137 | int 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 | |
164 | void* BinaryHeap_get_min(BinaryHeap h){ |
165 | /* return the min item */ |
166 | return h->heap[0]; |
167 | } |
168 | |
169 | void* (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 | |
175 | void* (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 | |
208 | int 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 | } |
225 | void* 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 | |
237 | void 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 | } |
273 | void 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 | |