|
111
|
1 /* Fibonacci heap for GNU compiler.
|
|
131
|
2 Copyright (C) 1998-2018 Free Software Foundation, Inc.
|
|
111
|
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
|
|
|
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify it under
|
|
|
9 the terms of the GNU General Public License as published by the Free
|
|
|
10 Software Foundation; either version 3, or (at your option) any later
|
|
|
11 version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
16 for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22 /* Fibonacci heaps are somewhat complex, but, there's an article in
|
|
|
23 DDJ that explains them pretty well:
|
|
|
24
|
|
|
25 http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
|
|
|
26
|
|
|
27 Introduction to algorithms by Corman and Rivest also goes over them.
|
|
|
28
|
|
|
29 The original paper that introduced them is "Fibonacci heaps and their
|
|
|
30 uses in improved network optimization algorithms" by Tarjan and
|
|
|
31 Fredman (JACM 34(3), July 1987).
|
|
|
32
|
|
|
33 Amortized and real worst case time for operations:
|
|
|
34
|
|
|
35 ExtractMin: O(lg n) amortized. O(n) worst case.
|
|
|
36 DecreaseKey: O(1) amortized. O(lg n) worst case.
|
|
|
37 Insert: O(1) amortized.
|
|
|
38 Union: O(1) amortized. */
|
|
|
39
|
|
|
40 #ifndef GCC_FIBONACCI_HEAP_H
|
|
|
41 #define GCC_FIBONACCI_HEAP_H
|
|
|
42
|
|
|
43 /* Forward definition. */
|
|
|
44
|
|
|
45 template<class K, class V>
|
|
|
46 class fibonacci_heap;
|
|
|
47
|
|
|
48 /* Fibonacci heap node class. */
|
|
|
49
|
|
|
50 template<class K, class V>
|
|
|
51 class fibonacci_node
|
|
|
52 {
|
|
|
53 typedef fibonacci_node<K,V> fibonacci_node_t;
|
|
|
54 friend class fibonacci_heap<K,V>;
|
|
|
55
|
|
|
56 public:
|
|
|
57 /* Default constructor. */
|
|
|
58 fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
|
|
|
59 m_right (this), m_degree (0), m_mark (0)
|
|
|
60 {
|
|
|
61 }
|
|
|
62
|
|
|
63 /* Constructor for a node with given KEY. */
|
|
|
64 fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
|
|
|
65 m_left (this), m_right (this), m_key (key), m_data (data),
|
|
|
66 m_degree (0), m_mark (0)
|
|
|
67 {
|
|
|
68 }
|
|
|
69
|
|
|
70 /* Compare fibonacci node with OTHER node. */
|
|
|
71 int compare (fibonacci_node_t *other)
|
|
|
72 {
|
|
|
73 if (m_key < other->m_key)
|
|
|
74 return -1;
|
|
|
75 if (m_key > other->m_key)
|
|
|
76 return 1;
|
|
|
77 return 0;
|
|
|
78 }
|
|
|
79
|
|
|
80 /* Compare the node with a given KEY. */
|
|
|
81 int compare_data (K key)
|
|
|
82 {
|
|
|
83 return fibonacci_node_t (key).compare (this);
|
|
|
84 }
|
|
|
85
|
|
|
86 /* Remove fibonacci heap node. */
|
|
|
87 fibonacci_node_t *remove ();
|
|
|
88
|
|
|
89 /* Link the node with PARENT. */
|
|
|
90 void link (fibonacci_node_t *parent);
|
|
|
91
|
|
|
92 /* Return key associated with the node. */
|
|
|
93 K get_key ()
|
|
|
94 {
|
|
|
95 return m_key;
|
|
|
96 }
|
|
|
97
|
|
|
98 /* Return data associated with the node. */
|
|
|
99 V *get_data ()
|
|
|
100 {
|
|
|
101 return m_data;
|
|
|
102 }
|
|
|
103
|
|
|
104 private:
|
|
|
105 /* Put node B after this node. */
|
|
|
106 void insert_after (fibonacci_node_t *b);
|
|
|
107
|
|
|
108 /* Insert fibonacci node B after this node. */
|
|
|
109 void insert_before (fibonacci_node_t *b)
|
|
|
110 {
|
|
|
111 m_left->insert_after (b);
|
|
|
112 }
|
|
|
113
|
|
|
114 /* Parent node. */
|
|
|
115 fibonacci_node *m_parent;
|
|
|
116 /* Child node. */
|
|
|
117 fibonacci_node *m_child;
|
|
|
118 /* Left sibling. */
|
|
|
119 fibonacci_node *m_left;
|
|
|
120 /* Right node. */
|
|
|
121 fibonacci_node *m_right;
|
|
|
122 /* Key associated with node. */
|
|
|
123 K m_key;
|
|
|
124 /* Data associated with node. */
|
|
|
125 V *m_data;
|
|
|
126
|
|
|
127 #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
|
|
|
128 /* Degree of the node. */
|
|
|
129 __extension__ unsigned long int m_degree : 31;
|
|
|
130 /* Mark of the node. */
|
|
|
131 __extension__ unsigned long int m_mark : 1;
|
|
|
132 #else
|
|
|
133 /* Degree of the node. */
|
|
|
134 unsigned int m_degree : 31;
|
|
|
135 /* Mark of the node. */
|
|
|
136 unsigned int m_mark : 1;
|
|
|
137 #endif
|
|
|
138 };
|
|
|
139
|
|
|
140 /* Fibonacci heap class. */
|
|
|
141 template<class K, class V>
|
|
|
142 class fibonacci_heap
|
|
|
143 {
|
|
|
144 typedef fibonacci_node<K,V> fibonacci_node_t;
|
|
|
145 friend class fibonacci_node<K,V>;
|
|
|
146
|
|
|
147 public:
|
|
|
148 /* Default constructor. */
|
|
|
149 fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
|
|
|
150 m_global_min_key (global_min_key)
|
|
|
151 {
|
|
|
152 }
|
|
|
153
|
|
|
154 /* Destructor. */
|
|
|
155 ~fibonacci_heap ()
|
|
|
156 {
|
|
|
157 while (m_min != NULL)
|
|
|
158 delete (extract_minimum_node ());
|
|
|
159 }
|
|
|
160
|
|
|
161 /* Insert new node given by KEY and DATA associated with the key. */
|
|
|
162 fibonacci_node_t *insert (K key, V *data);
|
|
|
163
|
|
|
164 /* Return true if no entry is present. */
|
|
|
165 bool empty ()
|
|
|
166 {
|
|
|
167 return m_nodes == 0;
|
|
|
168 }
|
|
|
169
|
|
|
170 /* Return the number of nodes. */
|
|
|
171 size_t nodes ()
|
|
|
172 {
|
|
|
173 return m_nodes;
|
|
|
174 }
|
|
|
175
|
|
|
176 /* Return minimal key presented in the heap. */
|
|
|
177 K min_key ()
|
|
|
178 {
|
|
|
179 if (m_min == NULL)
|
|
|
180 gcc_unreachable ();
|
|
|
181
|
|
|
182 return m_min->m_key;
|
|
|
183 }
|
|
|
184
|
|
|
185 /* For given NODE, set new KEY value. */
|
|
|
186 K replace_key (fibonacci_node_t *node, K key)
|
|
|
187 {
|
|
|
188 K okey = node->m_key;
|
|
|
189
|
|
|
190 replace_key_data (node, key, node->m_data);
|
|
|
191 return okey;
|
|
|
192 }
|
|
|
193
|
|
|
194 /* For given NODE, decrease value to new KEY. */
|
|
|
195 K decrease_key (fibonacci_node_t *node, K key)
|
|
|
196 {
|
|
|
197 gcc_assert (key <= node->m_key);
|
|
|
198 return replace_key (node, key);
|
|
|
199 }
|
|
|
200
|
|
|
201 /* For given NODE, set new KEY and DATA value. */
|
|
|
202 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
|
|
|
203
|
|
|
204 /* Extract minimum node in the heap. If RELEASE is specified,
|
|
|
205 memory is released. */
|
|
|
206 V *extract_min (bool release = true);
|
|
|
207
|
|
|
208 /* Return value associated with minimum node in the heap. */
|
|
|
209 V *min ()
|
|
|
210 {
|
|
|
211 if (m_min == NULL)
|
|
|
212 return NULL;
|
|
|
213
|
|
|
214 return m_min->m_data;
|
|
|
215 }
|
|
|
216
|
|
|
217 /* Replace data associated with NODE and replace it with DATA. */
|
|
|
218 V *replace_data (fibonacci_node_t *node, V *data)
|
|
|
219 {
|
|
|
220 return replace_key_data (node, node->m_key, data);
|
|
|
221 }
|
|
|
222
|
|
|
223 /* Delete NODE in the heap. */
|
|
|
224 V *delete_node (fibonacci_node_t *node, bool release = true);
|
|
|
225
|
|
|
226 /* Union the heap with HEAPB. */
|
|
|
227 fibonacci_heap *union_with (fibonacci_heap *heapb);
|
|
|
228
|
|
|
229 private:
|
|
|
230 /* Insert new NODE given by KEY and DATA associated with the key. */
|
|
|
231 fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
|
|
|
232
|
|
|
233 /* Insert new NODE that has already filled key and value. */
|
|
|
234 fibonacci_node_t *insert_node (fibonacci_node_t *node);
|
|
|
235
|
|
|
236 /* Insert it into the root list. */
|
|
|
237 void insert_root (fibonacci_node_t *node);
|
|
|
238
|
|
|
239 /* Remove NODE from PARENT's child list. */
|
|
|
240 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
|
|
|
241
|
|
|
242 /* Process cut of node Y and do it recursivelly. */
|
|
|
243 void cascading_cut (fibonacci_node_t *y);
|
|
|
244
|
|
|
245 /* Extract minimum node from the heap. */
|
|
|
246 fibonacci_node_t * extract_minimum_node ();
|
|
|
247
|
|
|
248 /* Remove root NODE from the heap. */
|
|
|
249 void remove_root (fibonacci_node_t *node);
|
|
|
250
|
|
|
251 /* Consolidate heap. */
|
|
|
252 void consolidate ();
|
|
|
253
|
|
|
254 /* Number of nodes. */
|
|
|
255 size_t m_nodes;
|
|
|
256 /* Minimum node of the heap. */
|
|
|
257 fibonacci_node_t *m_min;
|
|
|
258 /* Root node of the heap. */
|
|
|
259 fibonacci_node_t *m_root;
|
|
|
260 /* Global minimum given in the heap construction. */
|
|
|
261 K m_global_min_key;
|
|
|
262 };
|
|
|
263
|
|
|
264 /* Remove fibonacci heap node. */
|
|
|
265
|
|
|
266 template<class K, class V>
|
|
|
267 fibonacci_node<K,V> *
|
|
|
268 fibonacci_node<K,V>::remove ()
|
|
|
269 {
|
|
|
270 fibonacci_node<K,V> *ret;
|
|
|
271
|
|
|
272 if (this == m_left)
|
|
|
273 ret = NULL;
|
|
|
274 else
|
|
|
275 ret = m_left;
|
|
|
276
|
|
|
277 if (m_parent != NULL && m_parent->m_child == this)
|
|
|
278 m_parent->m_child = ret;
|
|
|
279
|
|
|
280 m_right->m_left = m_left;
|
|
|
281 m_left->m_right = m_right;
|
|
|
282
|
|
|
283 m_parent = NULL;
|
|
|
284 m_left = this;
|
|
|
285 m_right = this;
|
|
|
286
|
|
|
287 return ret;
|
|
|
288 }
|
|
|
289
|
|
|
290 /* Link the node with PARENT. */
|
|
|
291
|
|
|
292 template<class K, class V>
|
|
|
293 void
|
|
|
294 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
|
|
|
295 {
|
|
|
296 if (parent->m_child == NULL)
|
|
|
297 parent->m_child = this;
|
|
|
298 else
|
|
|
299 parent->m_child->insert_before (this);
|
|
|
300 m_parent = parent;
|
|
|
301 parent->m_degree++;
|
|
|
302 m_mark = 0;
|
|
|
303 }
|
|
|
304
|
|
|
305 /* Put node B after this node. */
|
|
|
306
|
|
|
307 template<class K, class V>
|
|
|
308 void
|
|
|
309 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
|
|
|
310 {
|
|
|
311 fibonacci_node<K,V> *a = this;
|
|
|
312
|
|
|
313 if (a == a->m_right)
|
|
|
314 {
|
|
|
315 a->m_right = b;
|
|
|
316 a->m_left = b;
|
|
|
317 b->m_right = a;
|
|
|
318 b->m_left = a;
|
|
|
319 }
|
|
|
320 else
|
|
|
321 {
|
|
|
322 b->m_right = a->m_right;
|
|
|
323 a->m_right->m_left = b;
|
|
|
324 a->m_right = b;
|
|
|
325 b->m_left = a;
|
|
|
326 }
|
|
|
327 }
|
|
|
328
|
|
|
329 /* Insert new node given by KEY and DATA associated with the key. */
|
|
|
330
|
|
|
331 template<class K, class V>
|
|
|
332 fibonacci_node<K,V>*
|
|
|
333 fibonacci_heap<K,V>::insert (K key, V *data)
|
|
|
334 {
|
|
|
335 /* Create the new node. */
|
|
|
336 fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
|
|
|
337
|
|
|
338 return insert_node (node);
|
|
|
339 }
|
|
|
340
|
|
|
341 /* Insert new NODE given by DATA associated with the key. */
|
|
|
342
|
|
|
343 template<class K, class V>
|
|
|
344 fibonacci_node<K,V>*
|
|
|
345 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
|
|
|
346 {
|
|
|
347 /* Set the node's data. */
|
|
|
348 node->m_data = data;
|
|
|
349 node->m_key = key;
|
|
|
350
|
|
|
351 return insert_node (node);
|
|
|
352 }
|
|
|
353
|
|
|
354 /* Insert new NODE that has already filled key and value. */
|
|
|
355
|
|
|
356 template<class K, class V>
|
|
|
357 fibonacci_node<K,V>*
|
|
|
358 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
|
|
|
359 {
|
|
|
360 /* Insert it into the root list. */
|
|
|
361 insert_root (node);
|
|
|
362
|
|
|
363 /* If their was no minimum, or this key is less than the min,
|
|
|
364 it's the new min. */
|
|
|
365 if (m_min == NULL || node->m_key < m_min->m_key)
|
|
|
366 m_min = node;
|
|
|
367
|
|
|
368 m_nodes++;
|
|
|
369
|
|
|
370 return node;
|
|
|
371 }
|
|
|
372
|
|
|
373 /* For given NODE, set new KEY and DATA value. */
|
|
|
374
|
|
|
375 template<class K, class V>
|
|
|
376 V*
|
|
|
377 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
|
|
|
378 V *data)
|
|
|
379 {
|
|
|
380 K okey;
|
|
|
381 fibonacci_node<K,V> *y;
|
|
|
382 V *odata = node->m_data;
|
|
|
383
|
|
|
384 /* If we wanted to, we do a real increase by redeleting and
|
|
|
385 inserting. */
|
|
|
386 if (node->compare_data (key) > 0)
|
|
|
387 {
|
|
|
388 delete_node (node, false);
|
|
|
389
|
|
|
390 node = new (node) fibonacci_node_t ();
|
|
|
391 insert (node, key, data);
|
|
|
392
|
|
|
393 return odata;
|
|
|
394 }
|
|
|
395
|
|
|
396 okey = node->m_key;
|
|
|
397 node->m_data = data;
|
|
|
398 node->m_key = key;
|
|
|
399 y = node->m_parent;
|
|
|
400
|
|
|
401 /* Short-circuit if the key is the same, as we then don't have to
|
|
|
402 do anything. Except if we're trying to force the new node to
|
|
|
403 be the new minimum for delete. */
|
|
|
404 if (okey == key && okey != m_global_min_key)
|
|
|
405 return odata;
|
|
|
406
|
|
|
407 /* These two compares are specifically <= 0 to make sure that in the case
|
|
|
408 of equality, a node we replaced the data on, becomes the new min. This
|
|
|
409 is needed so that delete's call to extractmin gets the right node. */
|
|
|
410 if (y != NULL && node->compare (y) <= 0)
|
|
|
411 {
|
|
|
412 cut (node, y);
|
|
|
413 cascading_cut (y);
|
|
|
414 }
|
|
|
415
|
|
|
416 if (node->compare (m_min) <= 0)
|
|
|
417 m_min = node;
|
|
|
418
|
|
|
419 return odata;
|
|
|
420 }
|
|
|
421
|
|
|
422 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
|
|
|
423 is true. */
|
|
|
424
|
|
|
425 template<class K, class V>
|
|
|
426 V*
|
|
|
427 fibonacci_heap<K,V>::extract_min (bool release)
|
|
|
428 {
|
|
|
429 fibonacci_node<K,V> *z;
|
|
|
430 V *ret = NULL;
|
|
|
431
|
|
|
432 /* If we don't have a min set, it means we have no nodes. */
|
|
|
433 if (m_min != NULL)
|
|
|
434 {
|
|
|
435 /* Otherwise, extract the min node, free the node, and return the
|
|
|
436 node's data. */
|
|
|
437 z = extract_minimum_node ();
|
|
|
438 ret = z->m_data;
|
|
|
439
|
|
|
440 if (release)
|
|
|
441 delete (z);
|
|
|
442 }
|
|
|
443
|
|
|
444 return ret;
|
|
|
445 }
|
|
|
446
|
|
|
447 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
|
|
|
448
|
|
|
449 template<class K, class V>
|
|
|
450 V*
|
|
|
451 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
|
|
|
452 {
|
|
|
453 V *ret = node->m_data;
|
|
|
454
|
|
|
455 /* To perform delete, we just make it the min key, and extract. */
|
|
|
456 replace_key (node, m_global_min_key);
|
|
|
457 if (node != m_min)
|
|
|
458 {
|
|
|
459 fprintf (stderr, "Can't force minimum on fibheap.\n");
|
|
|
460 abort ();
|
|
|
461 }
|
|
|
462 extract_min (release);
|
|
|
463
|
|
|
464 return ret;
|
|
|
465 }
|
|
|
466
|
|
|
467 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
|
|
|
468
|
|
|
469 template<class K, class V>
|
|
|
470 fibonacci_heap<K,V>*
|
|
|
471 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
|
|
|
472 {
|
|
|
473 fibonacci_heap<K,V> *heapa = this;
|
|
|
474
|
|
|
475 fibonacci_node<K,V> *a_root, *b_root;
|
|
|
476
|
|
|
477 /* If one of the heaps is empty, the union is just the other heap. */
|
|
|
478 if ((a_root = heapa->m_root) == NULL)
|
|
|
479 {
|
|
|
480 delete (heapa);
|
|
|
481 return heapb;
|
|
|
482 }
|
|
|
483 if ((b_root = heapb->m_root) == NULL)
|
|
|
484 {
|
|
|
485 delete (heapb);
|
|
|
486 return heapa;
|
|
|
487 }
|
|
|
488
|
|
|
489 /* Merge them to the next nodes on the opposite chain. */
|
|
|
490 a_root->m_left->m_right = b_root;
|
|
|
491 b_root->m_left->m_right = a_root;
|
|
|
492 std::swap (a_root->m_left, b_root->m_left);
|
|
|
493 heapa->m_nodes += heapb->m_nodes;
|
|
|
494
|
|
|
495 /* And set the new minimum, if it's changed. */
|
|
|
496 if (heapb->m_min->compare (heapa->m_min) < 0)
|
|
|
497 heapa->m_min = heapb->m_min;
|
|
|
498
|
|
|
499 /* Set m_min to NULL to not to delete live fibonacci nodes. */
|
|
|
500 heapb->m_min = NULL;
|
|
|
501 delete (heapb);
|
|
|
502
|
|
|
503 return heapa;
|
|
|
504 }
|
|
|
505
|
|
|
506 /* Insert it into the root list. */
|
|
|
507
|
|
|
508 template<class K, class V>
|
|
|
509 void
|
|
|
510 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
|
|
|
511 {
|
|
|
512 /* If the heap is currently empty, the new node becomes the singleton
|
|
|
513 circular root list. */
|
|
|
514 if (m_root == NULL)
|
|
|
515 {
|
|
|
516 m_root = node;
|
|
|
517 node->m_left = node;
|
|
|
518 node->m_right = node;
|
|
|
519 return;
|
|
|
520 }
|
|
|
521
|
|
|
522 /* Otherwise, insert it in the circular root list between the root
|
|
|
523 and it's right node. */
|
|
|
524 m_root->insert_after (node);
|
|
|
525 }
|
|
|
526
|
|
|
527 /* Remove NODE from PARENT's child list. */
|
|
|
528
|
|
|
529 template<class K, class V>
|
|
|
530 void
|
|
|
531 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
|
|
|
532 fibonacci_node<K,V> *parent)
|
|
|
533 {
|
|
|
534 node->remove ();
|
|
|
535 parent->m_degree--;
|
|
|
536 insert_root (node);
|
|
|
537 node->m_parent = NULL;
|
|
|
538 node->m_mark = 0;
|
|
|
539 }
|
|
|
540
|
|
|
541 /* Process cut of node Y and do it recursivelly. */
|
|
|
542
|
|
|
543 template<class K, class V>
|
|
|
544 void
|
|
|
545 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
|
|
|
546 {
|
|
|
547 fibonacci_node<K,V> *z;
|
|
|
548
|
|
|
549 while ((z = y->m_parent) != NULL)
|
|
|
550 {
|
|
|
551 if (y->m_mark == 0)
|
|
|
552 {
|
|
|
553 y->m_mark = 1;
|
|
|
554 return;
|
|
|
555 }
|
|
|
556 else
|
|
|
557 {
|
|
|
558 cut (y, z);
|
|
|
559 y = z;
|
|
|
560 }
|
|
|
561 }
|
|
|
562 }
|
|
|
563
|
|
|
564 /* Extract minimum node from the heap. */
|
|
|
565
|
|
|
566 template<class K, class V>
|
|
|
567 fibonacci_node<K,V>*
|
|
|
568 fibonacci_heap<K,V>::extract_minimum_node ()
|
|
|
569 {
|
|
|
570 fibonacci_node<K,V> *ret = m_min;
|
|
|
571 fibonacci_node<K,V> *x, *y, *orig;
|
|
|
572
|
|
|
573 /* Attach the child list of the minimum node to the root list of the heap.
|
|
|
574 If there is no child list, we don't do squat. */
|
|
|
575 for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
|
|
|
576 {
|
|
|
577 if (orig == NULL)
|
|
|
578 orig = x;
|
|
|
579 y = x->m_right;
|
|
|
580 x->m_parent = NULL;
|
|
|
581 insert_root (x);
|
|
|
582 }
|
|
|
583
|
|
|
584 /* Remove the old root. */
|
|
|
585 remove_root (ret);
|
|
|
586 m_nodes--;
|
|
|
587
|
|
|
588 /* If we are left with no nodes, then the min is NULL. */
|
|
|
589 if (m_nodes == 0)
|
|
|
590 m_min = NULL;
|
|
|
591 else
|
|
|
592 {
|
|
|
593 /* Otherwise, consolidate to find new minimum, as well as do the reorg
|
|
|
594 work that needs to be done. */
|
|
|
595 m_min = ret->m_right;
|
|
|
596 consolidate ();
|
|
|
597 }
|
|
|
598
|
|
|
599 return ret;
|
|
|
600 }
|
|
|
601
|
|
|
602 /* Remove root NODE from the heap. */
|
|
|
603
|
|
|
604 template<class K, class V>
|
|
|
605 void
|
|
|
606 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
|
|
|
607 {
|
|
|
608 if (node->m_left == node)
|
|
|
609 m_root = NULL;
|
|
|
610 else
|
|
|
611 m_root = node->remove ();
|
|
|
612 }
|
|
|
613
|
|
|
614 /* Consolidate heap. */
|
|
|
615
|
|
|
616 template<class K, class V>
|
|
|
617 void fibonacci_heap<K,V>::consolidate ()
|
|
|
618 {
|
|
|
619 int D = 1 + 8 * sizeof (long);
|
|
|
620 auto_vec<fibonacci_node<K,V> *> a (D);
|
|
|
621 a.safe_grow_cleared (D);
|
|
|
622 fibonacci_node<K,V> *w, *x, *y;
|
|
|
623 int i, d;
|
|
|
624
|
|
|
625 while ((w = m_root) != NULL)
|
|
|
626 {
|
|
|
627 x = w;
|
|
|
628 remove_root (w);
|
|
|
629 d = x->m_degree;
|
|
|
630 while (a[d] != NULL)
|
|
|
631 {
|
|
|
632 y = a[d];
|
|
|
633 if (x->compare (y) > 0)
|
|
|
634 std::swap (x, y);
|
|
|
635 y->link (x);
|
|
|
636 a[d] = NULL;
|
|
|
637 d++;
|
|
|
638 }
|
|
|
639 a[d] = x;
|
|
|
640 }
|
|
|
641 m_min = NULL;
|
|
|
642 for (i = 0; i < D; i++)
|
|
|
643 if (a[i] != NULL)
|
|
|
644 {
|
|
|
645 insert_root (a[i]);
|
|
|
646 if (m_min == NULL || a[i]->compare (m_min) < 0)
|
|
|
647 m_min = a[i];
|
|
|
648 }
|
|
|
649 }
|
|
|
650
|
|
|
651 #endif // GCC_FIBONACCI_HEAP_H
|
