|
0
|
1 /* A Fibonacci heap datatype.
|
|
|
2 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
|
|
|
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
|
|
|
4
|
|
|
5 This file is part of GNU CC.
|
|
|
6
|
|
|
7 GNU CC is free software; you can redistribute it and/or modify it
|
|
|
8 under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 2, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GNU CC is distributed in the hope that it will be useful, but
|
|
|
13 WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
|
15 General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GNU CC; see the file COPYING. If not, write to
|
|
|
19 the Free Software Foundation, 51 Franklin Street - Fifth Floor,
|
|
|
20 Boston, MA 02110-1301, USA. */
|
|
|
21
|
|
|
22 #ifdef HAVE_CONFIG_H
|
|
|
23 #include "config.h"
|
|
|
24 #endif
|
|
|
25 #ifdef HAVE_LIMITS_H
|
|
|
26 #include <limits.h>
|
|
|
27 #endif
|
|
|
28 #ifdef HAVE_STDLIB_H
|
|
|
29 #include <stdlib.h>
|
|
|
30 #endif
|
|
|
31 #ifdef HAVE_STRING_H
|
|
|
32 #include <string.h>
|
|
|
33 #endif
|
|
|
34 #include "libiberty.h"
|
|
|
35 #include "fibheap.h"
|
|
|
36
|
|
|
37
|
|
|
38 #define FIBHEAPKEY_MIN LONG_MIN
|
|
|
39
|
|
|
40 static void fibheap_ins_root (fibheap_t, fibnode_t);
|
|
|
41 static void fibheap_rem_root (fibheap_t, fibnode_t);
|
|
|
42 static void fibheap_consolidate (fibheap_t);
|
|
|
43 static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
|
|
|
44 static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
|
|
|
45 static void fibheap_cascading_cut (fibheap_t, fibnode_t);
|
|
|
46 static fibnode_t fibheap_extr_min_node (fibheap_t);
|
|
|
47 static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
|
|
|
48 static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
|
|
|
49 static fibnode_t fibnode_new (void);
|
|
|
50 static void fibnode_insert_after (fibnode_t, fibnode_t);
|
|
|
51 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
|
|
|
52 static fibnode_t fibnode_remove (fibnode_t);
|
|
|
53
|
|
|
54
|
|
|
55 /* Create a new fibonacci heap. */
|
|
|
56 fibheap_t
|
|
|
57 fibheap_new (void)
|
|
|
58 {
|
|
|
59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
|
|
|
60 }
|
|
|
61
|
|
|
62 /* Create a new fibonacci heap node. */
|
|
|
63 static fibnode_t
|
|
|
64 fibnode_new (void)
|
|
|
65 {
|
|
|
66 fibnode_t node;
|
|
|
67
|
|
|
68 node = (fibnode_t) xcalloc (1, sizeof *node);
|
|
|
69 node->left = node;
|
|
|
70 node->right = node;
|
|
|
71
|
|
|
72 return node;
|
|
|
73 }
|
|
|
74
|
|
|
75 static inline int
|
|
|
76 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
|
|
|
77 {
|
|
|
78 if (a->key < b->key)
|
|
|
79 return -1;
|
|
|
80 if (a->key > b->key)
|
|
|
81 return 1;
|
|
|
82 return 0;
|
|
|
83 }
|
|
|
84
|
|
|
85 static inline int
|
|
|
86 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
|
|
|
87 {
|
|
|
88 struct fibnode a;
|
|
|
89
|
|
|
90 a.key = key;
|
|
|
91 a.data = data;
|
|
|
92
|
|
|
93 return fibheap_compare (heap, &a, b);
|
|
|
94 }
|
|
|
95
|
|
|
96 /* Insert DATA, with priority KEY, into HEAP. */
|
|
|
97 fibnode_t
|
|
|
98 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
|
|
|
99 {
|
|
|
100 fibnode_t node;
|
|
|
101
|
|
|
102 /* Create the new node. */
|
|
|
103 node = fibnode_new ();
|
|
|
104
|
|
|
105 /* Set the node's data. */
|
|
|
106 node->data = data;
|
|
|
107 node->key = key;
|
|
|
108
|
|
|
109 /* Insert it into the root list. */
|
|
|
110 fibheap_ins_root (heap, node);
|
|
|
111
|
|
|
112 /* If their was no minimum, or this key is less than the min,
|
|
|
113 it's the new min. */
|
|
|
114 if (heap->min == NULL || node->key < heap->min->key)
|
|
|
115 heap->min = node;
|
|
|
116
|
|
|
117 heap->nodes++;
|
|
|
118
|
|
|
119 return node;
|
|
|
120 }
|
|
|
121
|
|
|
122 /* Return the data of the minimum node (if we know it). */
|
|
|
123 void *
|
|
|
124 fibheap_min (fibheap_t heap)
|
|
|
125 {
|
|
|
126 /* If there is no min, we can't easily return it. */
|
|
|
127 if (heap->min == NULL)
|
|
|
128 return NULL;
|
|
|
129 return heap->min->data;
|
|
|
130 }
|
|
|
131
|
|
|
132 /* Return the key of the minimum node (if we know it). */
|
|
|
133 fibheapkey_t
|
|
|
134 fibheap_min_key (fibheap_t heap)
|
|
|
135 {
|
|
|
136 /* If there is no min, we can't easily return it. */
|
|
|
137 if (heap->min == NULL)
|
|
|
138 return 0;
|
|
|
139 return heap->min->key;
|
|
|
140 }
|
|
|
141
|
|
|
142 /* Union HEAPA and HEAPB into a new heap. */
|
|
|
143 fibheap_t
|
|
|
144 fibheap_union (fibheap_t heapa, fibheap_t heapb)
|
|
|
145 {
|
|
|
146 fibnode_t a_root, b_root, temp;
|
|
|
147
|
|
|
148 /* If one of the heaps is empty, the union is just the other heap. */
|
|
|
149 if ((a_root = heapa->root) == NULL)
|
|
|
150 {
|
|
|
151 free (heapa);
|
|
|
152 return heapb;
|
|
|
153 }
|
|
|
154 if ((b_root = heapb->root) == NULL)
|
|
|
155 {
|
|
|
156 free (heapb);
|
|
|
157 return heapa;
|
|
|
158 }
|
|
|
159
|
|
|
160 /* Merge them to the next nodes on the opposite chain. */
|
|
|
161 a_root->left->right = b_root;
|
|
|
162 b_root->left->right = a_root;
|
|
|
163 temp = a_root->left;
|
|
|
164 a_root->left = b_root->left;
|
|
|
165 b_root->left = temp;
|
|
|
166 heapa->nodes += heapb->nodes;
|
|
|
167
|
|
|
168 /* And set the new minimum, if it's changed. */
|
|
|
169 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
|
|
|
170 heapa->min = heapb->min;
|
|
|
171
|
|
|
172 free (heapb);
|
|
|
173 return heapa;
|
|
|
174 }
|
|
|
175
|
|
|
176 /* Extract the data of the minimum node from HEAP. */
|
|
|
177 void *
|
|
|
178 fibheap_extract_min (fibheap_t heap)
|
|
|
179 {
|
|
|
180 fibnode_t z;
|
|
|
181 void *ret = NULL;
|
|
|
182
|
|
|
183 /* If we don't have a min set, it means we have no nodes. */
|
|
|
184 if (heap->min != NULL)
|
|
|
185 {
|
|
|
186 /* Otherwise, extract the min node, free the node, and return the
|
|
|
187 node's data. */
|
|
|
188 z = fibheap_extr_min_node (heap);
|
|
|
189 ret = z->data;
|
|
|
190 free (z);
|
|
|
191 }
|
|
|
192
|
|
|
193 return ret;
|
|
|
194 }
|
|
|
195
|
|
|
196 /* Replace both the KEY and the DATA associated with NODE. */
|
|
|
197 void *
|
|
|
198 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
|
|
|
199 fibheapkey_t key, void *data)
|
|
|
200 {
|
|
|
201 void *odata;
|
|
|
202 fibheapkey_t okey;
|
|
|
203 fibnode_t y;
|
|
|
204
|
|
|
205 /* If we wanted to, we could actually do a real increase by redeleting and
|
|
|
206 inserting. However, this would require O (log n) time. So just bail out
|
|
|
207 for now. */
|
|
|
208 if (fibheap_comp_data (heap, key, data, node) > 0)
|
|
|
209 return NULL;
|
|
|
210
|
|
|
211 odata = node->data;
|
|
|
212 okey = node->key;
|
|
|
213 node->data = data;
|
|
|
214 node->key = key;
|
|
|
215 y = node->parent;
|
|
|
216
|
|
|
217 if (okey == key)
|
|
|
218 return odata;
|
|
|
219
|
|
|
220 /* These two compares are specifically <= 0 to make sure that in the case
|
|
|
221 of equality, a node we replaced the data on, becomes the new min. This
|
|
|
222 is needed so that delete's call to extractmin gets the right node. */
|
|
|
223 if (y != NULL && fibheap_compare (heap, node, y) <= 0)
|
|
|
224 {
|
|
|
225 fibheap_cut (heap, node, y);
|
|
|
226 fibheap_cascading_cut (heap, y);
|
|
|
227 }
|
|
|
228
|
|
|
229 if (fibheap_compare (heap, node, heap->min) <= 0)
|
|
|
230 heap->min = node;
|
|
|
231
|
|
|
232 return odata;
|
|
|
233 }
|
|
|
234
|
|
|
235 /* Replace the DATA associated with NODE. */
|
|
|
236 void *
|
|
|
237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
|
|
|
238 {
|
|
|
239 return fibheap_replace_key_data (heap, node, node->key, data);
|
|
|
240 }
|
|
|
241
|
|
|
242 /* Replace the KEY associated with NODE. */
|
|
|
243 fibheapkey_t
|
|
|
244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
|
|
|
245 {
|
|
|
246 int okey = node->key;
|
|
|
247 fibheap_replace_key_data (heap, node, key, node->data);
|
|
|
248 return okey;
|
|
|
249 }
|
|
|
250
|
|
|
251 /* Delete NODE from HEAP. */
|
|
|
252 void *
|
|
|
253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
|
|
|
254 {
|
|
|
255 void *ret = node->data;
|
|
|
256
|
|
|
257 /* To perform delete, we just make it the min key, and extract. */
|
|
|
258 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
|
|
|
259 fibheap_extract_min (heap);
|
|
|
260
|
|
|
261 return ret;
|
|
|
262 }
|
|
|
263
|
|
|
264 /* Delete HEAP. */
|
|
|
265 void
|
|
|
266 fibheap_delete (fibheap_t heap)
|
|
|
267 {
|
|
|
268 while (heap->min != NULL)
|
|
|
269 free (fibheap_extr_min_node (heap));
|
|
|
270
|
|
|
271 free (heap);
|
|
|
272 }
|
|
|
273
|
|
|
274 /* Determine if HEAP is empty. */
|
|
|
275 int
|
|
|
276 fibheap_empty (fibheap_t heap)
|
|
|
277 {
|
|
|
278 return heap->nodes == 0;
|
|
|
279 }
|
|
|
280
|
|
|
281 /* Extract the minimum node of the heap. */
|
|
|
282 static fibnode_t
|
|
|
283 fibheap_extr_min_node (fibheap_t heap)
|
|
|
284 {
|
|
|
285 fibnode_t ret = heap->min;
|
|
|
286 fibnode_t x, y, orig;
|
|
|
287
|
|
|
288 /* Attach the child list of the minimum node to the root list of the heap.
|
|
|
289 If there is no child list, we don't do squat. */
|
|
|
290 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
|
|
|
291 {
|
|
|
292 if (orig == NULL)
|
|
|
293 orig = x;
|
|
|
294 y = x->right;
|
|
|
295 x->parent = NULL;
|
|
|
296 fibheap_ins_root (heap, x);
|
|
|
297 }
|
|
|
298
|
|
|
299 /* Remove the old root. */
|
|
|
300 fibheap_rem_root (heap, ret);
|
|
|
301 heap->nodes--;
|
|
|
302
|
|
|
303 /* If we are left with no nodes, then the min is NULL. */
|
|
|
304 if (heap->nodes == 0)
|
|
|
305 heap->min = NULL;
|
|
|
306 else
|
|
|
307 {
|
|
|
308 /* Otherwise, consolidate to find new minimum, as well as do the reorg
|
|
|
309 work that needs to be done. */
|
|
|
310 heap->min = ret->right;
|
|
|
311 fibheap_consolidate (heap);
|
|
|
312 }
|
|
|
313
|
|
|
314 return ret;
|
|
|
315 }
|
|
|
316
|
|
|
317 /* Insert NODE into the root list of HEAP. */
|
|
|
318 static void
|
|
|
319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
|
|
|
320 {
|
|
|
321 /* If the heap is currently empty, the new node becomes the singleton
|
|
|
322 circular root list. */
|
|
|
323 if (heap->root == NULL)
|
|
|
324 {
|
|
|
325 heap->root = node;
|
|
|
326 node->left = node;
|
|
|
327 node->right = node;
|
|
|
328 return;
|
|
|
329 }
|
|
|
330
|
|
|
331 /* Otherwise, insert it in the circular root list between the root
|
|
|
332 and it's right node. */
|
|
|
333 fibnode_insert_after (heap->root, node);
|
|
|
334 }
|
|
|
335
|
|
|
336 /* Remove NODE from the rootlist of HEAP. */
|
|
|
337 static void
|
|
|
338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
|
|
|
339 {
|
|
|
340 if (node->left == node)
|
|
|
341 heap->root = NULL;
|
|
|
342 else
|
|
|
343 heap->root = fibnode_remove (node);
|
|
|
344 }
|
|
|
345
|
|
|
346 /* Consolidate the heap. */
|
|
|
347 static void
|
|
|
348 fibheap_consolidate (fibheap_t heap)
|
|
|
349 {
|
|
|
350 fibnode_t a[1 + 8 * sizeof (long)];
|
|
|
351 fibnode_t w;
|
|
|
352 fibnode_t y;
|
|
|
353 fibnode_t x;
|
|
|
354 int i;
|
|
|
355 int d;
|
|
|
356 int D;
|
|
|
357
|
|
|
358 D = 1 + 8 * sizeof (long);
|
|
|
359
|
|
|
360 memset (a, 0, sizeof (fibnode_t) * D);
|
|
|
361
|
|
|
362 while ((w = heap->root) != NULL)
|
|
|
363 {
|
|
|
364 x = w;
|
|
|
365 fibheap_rem_root (heap, w);
|
|
|
366 d = x->degree;
|
|
|
367 while (a[d] != NULL)
|
|
|
368 {
|
|
|
369 y = a[d];
|
|
|
370 if (fibheap_compare (heap, x, y) > 0)
|
|
|
371 {
|
|
|
372 fibnode_t temp;
|
|
|
373 temp = x;
|
|
|
374 x = y;
|
|
|
375 y = temp;
|
|
|
376 }
|
|
|
377 fibheap_link (heap, y, x);
|
|
|
378 a[d] = NULL;
|
|
|
379 d++;
|
|
|
380 }
|
|
|
381 a[d] = x;
|
|
|
382 }
|
|
|
383 heap->min = NULL;
|
|
|
384 for (i = 0; i < D; i++)
|
|
|
385 if (a[i] != NULL)
|
|
|
386 {
|
|
|
387 fibheap_ins_root (heap, a[i]);
|
|
|
388 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
|
|
|
389 heap->min = a[i];
|
|
|
390 }
|
|
|
391 }
|
|
|
392
|
|
|
393 /* Make NODE a child of PARENT. */
|
|
|
394 static void
|
|
|
395 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
|
|
|
396 fibnode_t node, fibnode_t parent)
|
|
|
397 {
|
|
|
398 if (parent->child == NULL)
|
|
|
399 parent->child = node;
|
|
|
400 else
|
|
|
401 fibnode_insert_before (parent->child, node);
|
|
|
402 node->parent = parent;
|
|
|
403 parent->degree++;
|
|
|
404 node->mark = 0;
|
|
|
405 }
|
|
|
406
|
|
|
407 /* Remove NODE from PARENT's child list. */
|
|
|
408 static void
|
|
|
409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
|
|
|
410 {
|
|
|
411 fibnode_remove (node);
|
|
|
412 parent->degree--;
|
|
|
413 fibheap_ins_root (heap, node);
|
|
|
414 node->parent = NULL;
|
|
|
415 node->mark = 0;
|
|
|
416 }
|
|
|
417
|
|
|
418 static void
|
|
|
419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
|
|
|
420 {
|
|
|
421 fibnode_t z;
|
|
|
422
|
|
|
423 while ((z = y->parent) != NULL)
|
|
|
424 {
|
|
|
425 if (y->mark == 0)
|
|
|
426 {
|
|
|
427 y->mark = 1;
|
|
|
428 return;
|
|
|
429 }
|
|
|
430 else
|
|
|
431 {
|
|
|
432 fibheap_cut (heap, y, z);
|
|
|
433 y = z;
|
|
|
434 }
|
|
|
435 }
|
|
|
436 }
|
|
|
437
|
|
|
438 static void
|
|
|
439 fibnode_insert_after (fibnode_t a, fibnode_t b)
|
|
|
440 {
|
|
|
441 if (a == a->right)
|
|
|
442 {
|
|
|
443 a->right = b;
|
|
|
444 a->left = b;
|
|
|
445 b->right = a;
|
|
|
446 b->left = a;
|
|
|
447 }
|
|
|
448 else
|
|
|
449 {
|
|
|
450 b->right = a->right;
|
|
|
451 a->right->left = b;
|
|
|
452 a->right = b;
|
|
|
453 b->left = a;
|
|
|
454 }
|
|
|
455 }
|
|
|
456
|
|
|
457 static fibnode_t
|
|
|
458 fibnode_remove (fibnode_t node)
|
|
|
459 {
|
|
|
460 fibnode_t ret;
|
|
|
461
|
|
|
462 if (node == node->left)
|
|
|
463 ret = NULL;
|
|
|
464 else
|
|
|
465 ret = node->left;
|
|
|
466
|
|
|
467 if (node->parent != NULL && node->parent->child == node)
|
|
|
468 node->parent->child = ret;
|
|
|
469
|
|
|
470 node->right->left = node->left;
|
|
|
471 node->left->right = node->right;
|
|
|
472
|
|
|
473 node->parent = NULL;
|
|
|
474 node->left = node;
|
|
|
475 node->right = node;
|
|
|
476
|
|
|
477 return ret;
|
|
|
478 }
|
