|
111
|
1 /* Fibonacci heap for GNU compiler.
|
|
145
|
2 Copyright (C) 1998-2020 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),
|
|
145
|
59 m_right (this), m_data (NULL), m_degree (0), m_mark (0)
|
|
111
|
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:
|
|
145
|
148 /* Default constructor. ALLOCATOR is optional and is primarily useful
|
|
|
149 when heaps are going to be merged (in that case they need to be allocated
|
|
|
150 in same alloc pool). */
|
|
|
151 fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
|
|
|
152 m_nodes (0), m_min (NULL), m_root (NULL),
|
|
|
153 m_global_min_key (global_min_key),
|
|
|
154 m_allocator (allocator), m_own_allocator (false)
|
|
111
|
155 {
|
|
145
|
156 if (!m_allocator)
|
|
|
157 {
|
|
|
158 m_allocator = new pool_allocator ("Fibonacci heap",
|
|
|
159 sizeof (fibonacci_node_t));
|
|
|
160 m_own_allocator = true;
|
|
|
161 }
|
|
111
|
162 }
|
|
|
163
|
|
|
164 /* Destructor. */
|
|
|
165 ~fibonacci_heap ()
|
|
|
166 {
|
|
145
|
167 /* Actual memory will be released by the destructor of m_allocator. */
|
|
|
168 if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
|
|
|
169 while (m_min != NULL)
|
|
|
170 {
|
|
|
171 fibonacci_node_t *n = extract_minimum_node ();
|
|
|
172 n->~fibonacci_node_t ();
|
|
|
173 if (!m_own_allocator)
|
|
|
174 m_allocator->remove (n);
|
|
|
175 }
|
|
|
176 if (m_own_allocator)
|
|
|
177 delete m_allocator;
|
|
111
|
178 }
|
|
|
179
|
|
|
180 /* Insert new node given by KEY and DATA associated with the key. */
|
|
|
181 fibonacci_node_t *insert (K key, V *data);
|
|
|
182
|
|
|
183 /* Return true if no entry is present. */
|
|
145
|
184 bool empty () const
|
|
111
|
185 {
|
|
|
186 return m_nodes == 0;
|
|
|
187 }
|
|
|
188
|
|
|
189 /* Return the number of nodes. */
|
|
145
|
190 size_t nodes () const
|
|
111
|
191 {
|
|
|
192 return m_nodes;
|
|
|
193 }
|
|
|
194
|
|
|
195 /* Return minimal key presented in the heap. */
|
|
145
|
196 K min_key () const
|
|
111
|
197 {
|
|
|
198 if (m_min == NULL)
|
|
|
199 gcc_unreachable ();
|
|
|
200
|
|
|
201 return m_min->m_key;
|
|
|
202 }
|
|
|
203
|
|
|
204 /* For given NODE, set new KEY value. */
|
|
|
205 K replace_key (fibonacci_node_t *node, K key)
|
|
|
206 {
|
|
|
207 K okey = node->m_key;
|
|
|
208
|
|
|
209 replace_key_data (node, key, node->m_data);
|
|
|
210 return okey;
|
|
|
211 }
|
|
|
212
|
|
|
213 /* For given NODE, decrease value to new KEY. */
|
|
|
214 K decrease_key (fibonacci_node_t *node, K key)
|
|
|
215 {
|
|
|
216 gcc_assert (key <= node->m_key);
|
|
|
217 return replace_key (node, key);
|
|
|
218 }
|
|
|
219
|
|
|
220 /* For given NODE, set new KEY and DATA value. */
|
|
|
221 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
|
|
|
222
|
|
|
223 /* Extract minimum node in the heap. If RELEASE is specified,
|
|
|
224 memory is released. */
|
|
|
225 V *extract_min (bool release = true);
|
|
|
226
|
|
|
227 /* Return value associated with minimum node in the heap. */
|
|
145
|
228 V *min () const
|
|
111
|
229 {
|
|
|
230 if (m_min == NULL)
|
|
|
231 return NULL;
|
|
|
232
|
|
|
233 return m_min->m_data;
|
|
|
234 }
|
|
|
235
|
|
|
236 /* Replace data associated with NODE and replace it with DATA. */
|
|
|
237 V *replace_data (fibonacci_node_t *node, V *data)
|
|
|
238 {
|
|
|
239 return replace_key_data (node, node->m_key, data);
|
|
|
240 }
|
|
|
241
|
|
|
242 /* Delete NODE in the heap. */
|
|
|
243 V *delete_node (fibonacci_node_t *node, bool release = true);
|
|
|
244
|
|
|
245 /* Union the heap with HEAPB. */
|
|
|
246 fibonacci_heap *union_with (fibonacci_heap *heapb);
|
|
|
247
|
|
|
248 private:
|
|
|
249 /* Insert new NODE given by KEY and DATA associated with the key. */
|
|
|
250 fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
|
|
|
251
|
|
|
252 /* Insert new NODE that has already filled key and value. */
|
|
|
253 fibonacci_node_t *insert_node (fibonacci_node_t *node);
|
|
|
254
|
|
|
255 /* Insert it into the root list. */
|
|
|
256 void insert_root (fibonacci_node_t *node);
|
|
|
257
|
|
|
258 /* Remove NODE from PARENT's child list. */
|
|
|
259 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
|
|
|
260
|
|
|
261 /* Process cut of node Y and do it recursivelly. */
|
|
|
262 void cascading_cut (fibonacci_node_t *y);
|
|
|
263
|
|
|
264 /* Extract minimum node from the heap. */
|
|
|
265 fibonacci_node_t * extract_minimum_node ();
|
|
|
266
|
|
|
267 /* Remove root NODE from the heap. */
|
|
|
268 void remove_root (fibonacci_node_t *node);
|
|
|
269
|
|
|
270 /* Consolidate heap. */
|
|
|
271 void consolidate ();
|
|
|
272
|
|
|
273 /* Number of nodes. */
|
|
|
274 size_t m_nodes;
|
|
|
275 /* Minimum node of the heap. */
|
|
|
276 fibonacci_node_t *m_min;
|
|
|
277 /* Root node of the heap. */
|
|
|
278 fibonacci_node_t *m_root;
|
|
|
279 /* Global minimum given in the heap construction. */
|
|
|
280 K m_global_min_key;
|
|
145
|
281
|
|
|
282 /* Allocator used to hold nodes. */
|
|
|
283 pool_allocator *m_allocator;
|
|
|
284 /* True if alocator is owned by the current heap only. */
|
|
|
285 bool m_own_allocator;
|
|
111
|
286 };
|
|
|
287
|
|
|
288 /* Remove fibonacci heap node. */
|
|
|
289
|
|
|
290 template<class K, class V>
|
|
|
291 fibonacci_node<K,V> *
|
|
|
292 fibonacci_node<K,V>::remove ()
|
|
|
293 {
|
|
|
294 fibonacci_node<K,V> *ret;
|
|
|
295
|
|
|
296 if (this == m_left)
|
|
|
297 ret = NULL;
|
|
|
298 else
|
|
|
299 ret = m_left;
|
|
|
300
|
|
|
301 if (m_parent != NULL && m_parent->m_child == this)
|
|
|
302 m_parent->m_child = ret;
|
|
|
303
|
|
|
304 m_right->m_left = m_left;
|
|
|
305 m_left->m_right = m_right;
|
|
|
306
|
|
|
307 m_parent = NULL;
|
|
|
308 m_left = this;
|
|
|
309 m_right = this;
|
|
|
310
|
|
|
311 return ret;
|
|
|
312 }
|
|
|
313
|
|
|
314 /* Link the node with PARENT. */
|
|
|
315
|
|
|
316 template<class K, class V>
|
|
|
317 void
|
|
|
318 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
|
|
|
319 {
|
|
|
320 if (parent->m_child == NULL)
|
|
|
321 parent->m_child = this;
|
|
|
322 else
|
|
|
323 parent->m_child->insert_before (this);
|
|
|
324 m_parent = parent;
|
|
|
325 parent->m_degree++;
|
|
|
326 m_mark = 0;
|
|
|
327 }
|
|
|
328
|
|
|
329 /* Put node B after this node. */
|
|
|
330
|
|
|
331 template<class K, class V>
|
|
|
332 void
|
|
|
333 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
|
|
|
334 {
|
|
|
335 fibonacci_node<K,V> *a = this;
|
|
|
336
|
|
|
337 if (a == a->m_right)
|
|
|
338 {
|
|
|
339 a->m_right = b;
|
|
|
340 a->m_left = b;
|
|
|
341 b->m_right = a;
|
|
|
342 b->m_left = a;
|
|
|
343 }
|
|
|
344 else
|
|
|
345 {
|
|
|
346 b->m_right = a->m_right;
|
|
|
347 a->m_right->m_left = b;
|
|
|
348 a->m_right = b;
|
|
|
349 b->m_left = a;
|
|
|
350 }
|
|
|
351 }
|
|
|
352
|
|
|
353 /* Insert new node given by KEY and DATA associated with the key. */
|
|
|
354
|
|
|
355 template<class K, class V>
|
|
|
356 fibonacci_node<K,V>*
|
|
|
357 fibonacci_heap<K,V>::insert (K key, V *data)
|
|
|
358 {
|
|
|
359 /* Create the new node. */
|
|
145
|
360 fibonacci_node<K,V> *node = new (m_allocator->allocate ())
|
|
|
361 fibonacci_node_t (key, data);
|
|
111
|
362
|
|
|
363 return insert_node (node);
|
|
|
364 }
|
|
|
365
|
|
|
366 /* Insert new NODE given by DATA associated with the key. */
|
|
|
367
|
|
|
368 template<class K, class V>
|
|
|
369 fibonacci_node<K,V>*
|
|
|
370 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
|
|
|
371 {
|
|
|
372 /* Set the node's data. */
|
|
|
373 node->m_data = data;
|
|
|
374 node->m_key = key;
|
|
|
375
|
|
|
376 return insert_node (node);
|
|
|
377 }
|
|
|
378
|
|
|
379 /* Insert new NODE that has already filled key and value. */
|
|
|
380
|
|
|
381 template<class K, class V>
|
|
|
382 fibonacci_node<K,V>*
|
|
|
383 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
|
|
|
384 {
|
|
|
385 /* Insert it into the root list. */
|
|
|
386 insert_root (node);
|
|
|
387
|
|
|
388 /* If their was no minimum, or this key is less than the min,
|
|
|
389 it's the new min. */
|
|
|
390 if (m_min == NULL || node->m_key < m_min->m_key)
|
|
|
391 m_min = node;
|
|
|
392
|
|
|
393 m_nodes++;
|
|
|
394
|
|
|
395 return node;
|
|
|
396 }
|
|
|
397
|
|
|
398 /* For given NODE, set new KEY and DATA value. */
|
|
|
399
|
|
|
400 template<class K, class V>
|
|
|
401 V*
|
|
|
402 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
|
|
|
403 V *data)
|
|
|
404 {
|
|
|
405 K okey;
|
|
|
406 fibonacci_node<K,V> *y;
|
|
|
407 V *odata = node->m_data;
|
|
|
408
|
|
|
409 /* If we wanted to, we do a real increase by redeleting and
|
|
|
410 inserting. */
|
|
|
411 if (node->compare_data (key) > 0)
|
|
|
412 {
|
|
|
413 delete_node (node, false);
|
|
|
414
|
|
|
415 node = new (node) fibonacci_node_t ();
|
|
|
416 insert (node, key, data);
|
|
|
417
|
|
|
418 return odata;
|
|
|
419 }
|
|
|
420
|
|
|
421 okey = node->m_key;
|
|
|
422 node->m_data = data;
|
|
|
423 node->m_key = key;
|
|
|
424 y = node->m_parent;
|
|
|
425
|
|
|
426 /* Short-circuit if the key is the same, as we then don't have to
|
|
|
427 do anything. Except if we're trying to force the new node to
|
|
|
428 be the new minimum for delete. */
|
|
|
429 if (okey == key && okey != m_global_min_key)
|
|
|
430 return odata;
|
|
|
431
|
|
|
432 /* These two compares are specifically <= 0 to make sure that in the case
|
|
|
433 of equality, a node we replaced the data on, becomes the new min. This
|
|
|
434 is needed so that delete's call to extractmin gets the right node. */
|
|
|
435 if (y != NULL && node->compare (y) <= 0)
|
|
|
436 {
|
|
|
437 cut (node, y);
|
|
|
438 cascading_cut (y);
|
|
|
439 }
|
|
|
440
|
|
|
441 if (node->compare (m_min) <= 0)
|
|
|
442 m_min = node;
|
|
|
443
|
|
|
444 return odata;
|
|
|
445 }
|
|
|
446
|
|
|
447 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
|
|
|
448 is true. */
|
|
|
449
|
|
|
450 template<class K, class V>
|
|
|
451 V*
|
|
|
452 fibonacci_heap<K,V>::extract_min (bool release)
|
|
|
453 {
|
|
|
454 fibonacci_node<K,V> *z;
|
|
|
455 V *ret = NULL;
|
|
|
456
|
|
|
457 /* If we don't have a min set, it means we have no nodes. */
|
|
|
458 if (m_min != NULL)
|
|
|
459 {
|
|
|
460 /* Otherwise, extract the min node, free the node, and return the
|
|
|
461 node's data. */
|
|
|
462 z = extract_minimum_node ();
|
|
|
463 ret = z->m_data;
|
|
|
464
|
|
|
465 if (release)
|
|
145
|
466 {
|
|
|
467 z->~fibonacci_node_t ();
|
|
|
468 m_allocator->remove (z);
|
|
|
469 }
|
|
111
|
470 }
|
|
|
471
|
|
|
472 return ret;
|
|
|
473 }
|
|
|
474
|
|
|
475 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
|
|
|
476
|
|
|
477 template<class K, class V>
|
|
|
478 V*
|
|
|
479 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
|
|
|
480 {
|
|
|
481 V *ret = node->m_data;
|
|
|
482
|
|
|
483 /* To perform delete, we just make it the min key, and extract. */
|
|
|
484 replace_key (node, m_global_min_key);
|
|
|
485 if (node != m_min)
|
|
|
486 {
|
|
|
487 fprintf (stderr, "Can't force minimum on fibheap.\n");
|
|
|
488 abort ();
|
|
|
489 }
|
|
|
490 extract_min (release);
|
|
|
491
|
|
|
492 return ret;
|
|
|
493 }
|
|
|
494
|
|
|
495 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
|
|
|
496
|
|
|
497 template<class K, class V>
|
|
|
498 fibonacci_heap<K,V>*
|
|
|
499 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
|
|
|
500 {
|
|
|
501 fibonacci_heap<K,V> *heapa = this;
|
|
|
502
|
|
|
503 fibonacci_node<K,V> *a_root, *b_root;
|
|
|
504
|
|
145
|
505 /* Both heaps must share allocator. */
|
|
|
506 gcc_checking_assert (m_allocator == heapb->m_allocator);
|
|
|
507
|
|
111
|
508 /* If one of the heaps is empty, the union is just the other heap. */
|
|
|
509 if ((a_root = heapa->m_root) == NULL)
|
|
|
510 {
|
|
|
511 delete (heapa);
|
|
|
512 return heapb;
|
|
|
513 }
|
|
|
514 if ((b_root = heapb->m_root) == NULL)
|
|
|
515 {
|
|
|
516 delete (heapb);
|
|
|
517 return heapa;
|
|
|
518 }
|
|
|
519
|
|
|
520 /* Merge them to the next nodes on the opposite chain. */
|
|
|
521 a_root->m_left->m_right = b_root;
|
|
|
522 b_root->m_left->m_right = a_root;
|
|
|
523 std::swap (a_root->m_left, b_root->m_left);
|
|
|
524 heapa->m_nodes += heapb->m_nodes;
|
|
|
525
|
|
|
526 /* And set the new minimum, if it's changed. */
|
|
|
527 if (heapb->m_min->compare (heapa->m_min) < 0)
|
|
|
528 heapa->m_min = heapb->m_min;
|
|
|
529
|
|
|
530 /* Set m_min to NULL to not to delete live fibonacci nodes. */
|
|
|
531 heapb->m_min = NULL;
|
|
|
532 delete (heapb);
|
|
|
533
|
|
|
534 return heapa;
|
|
|
535 }
|
|
|
536
|
|
|
537 /* Insert it into the root list. */
|
|
|
538
|
|
|
539 template<class K, class V>
|
|
|
540 void
|
|
|
541 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
|
|
|
542 {
|
|
|
543 /* If the heap is currently empty, the new node becomes the singleton
|
|
|
544 circular root list. */
|
|
|
545 if (m_root == NULL)
|
|
|
546 {
|
|
|
547 m_root = node;
|
|
|
548 node->m_left = node;
|
|
|
549 node->m_right = node;
|
|
|
550 return;
|
|
|
551 }
|
|
|
552
|
|
|
553 /* Otherwise, insert it in the circular root list between the root
|
|
|
554 and it's right node. */
|
|
|
555 m_root->insert_after (node);
|
|
|
556 }
|
|
|
557
|
|
|
558 /* Remove NODE from PARENT's child list. */
|
|
|
559
|
|
|
560 template<class K, class V>
|
|
|
561 void
|
|
|
562 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
|
|
|
563 fibonacci_node<K,V> *parent)
|
|
|
564 {
|
|
|
565 node->remove ();
|
|
|
566 parent->m_degree--;
|
|
|
567 insert_root (node);
|
|
|
568 node->m_parent = NULL;
|
|
|
569 node->m_mark = 0;
|
|
|
570 }
|
|
|
571
|
|
|
572 /* Process cut of node Y and do it recursivelly. */
|
|
|
573
|
|
|
574 template<class K, class V>
|
|
|
575 void
|
|
|
576 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
|
|
|
577 {
|
|
|
578 fibonacci_node<K,V> *z;
|
|
|
579
|
|
|
580 while ((z = y->m_parent) != NULL)
|
|
|
581 {
|
|
|
582 if (y->m_mark == 0)
|
|
|
583 {
|
|
|
584 y->m_mark = 1;
|
|
|
585 return;
|
|
|
586 }
|
|
|
587 else
|
|
|
588 {
|
|
|
589 cut (y, z);
|
|
|
590 y = z;
|
|
|
591 }
|
|
|
592 }
|
|
|
593 }
|
|
|
594
|
|
|
595 /* Extract minimum node from the heap. */
|
|
|
596
|
|
|
597 template<class K, class V>
|
|
|
598 fibonacci_node<K,V>*
|
|
|
599 fibonacci_heap<K,V>::extract_minimum_node ()
|
|
|
600 {
|
|
|
601 fibonacci_node<K,V> *ret = m_min;
|
|
|
602 fibonacci_node<K,V> *x, *y, *orig;
|
|
|
603
|
|
|
604 /* Attach the child list of the minimum node to the root list of the heap.
|
|
|
605 If there is no child list, we don't do squat. */
|
|
|
606 for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
|
|
|
607 {
|
|
|
608 if (orig == NULL)
|
|
|
609 orig = x;
|
|
|
610 y = x->m_right;
|
|
|
611 x->m_parent = NULL;
|
|
|
612 insert_root (x);
|
|
|
613 }
|
|
|
614
|
|
|
615 /* Remove the old root. */
|
|
|
616 remove_root (ret);
|
|
|
617 m_nodes--;
|
|
|
618
|
|
|
619 /* If we are left with no nodes, then the min is NULL. */
|
|
|
620 if (m_nodes == 0)
|
|
|
621 m_min = NULL;
|
|
|
622 else
|
|
|
623 {
|
|
|
624 /* Otherwise, consolidate to find new minimum, as well as do the reorg
|
|
|
625 work that needs to be done. */
|
|
|
626 m_min = ret->m_right;
|
|
|
627 consolidate ();
|
|
|
628 }
|
|
|
629
|
|
|
630 return ret;
|
|
|
631 }
|
|
|
632
|
|
|
633 /* Remove root NODE from the heap. */
|
|
|
634
|
|
|
635 template<class K, class V>
|
|
|
636 void
|
|
|
637 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
|
|
|
638 {
|
|
|
639 if (node->m_left == node)
|
|
|
640 m_root = NULL;
|
|
|
641 else
|
|
|
642 m_root = node->remove ();
|
|
|
643 }
|
|
|
644
|
|
|
645 /* Consolidate heap. */
|
|
|
646
|
|
|
647 template<class K, class V>
|
|
|
648 void fibonacci_heap<K,V>::consolidate ()
|
|
|
649 {
|
|
145
|
650 const int D = 1 + 8 * sizeof (long);
|
|
|
651 fibonacci_node<K,V> *a[D];
|
|
111
|
652 fibonacci_node<K,V> *w, *x, *y;
|
|
|
653 int i, d;
|
|
|
654
|
|
145
|
655 memset (a, 0, sizeof (a));
|
|
|
656
|
|
111
|
657 while ((w = m_root) != NULL)
|
|
|
658 {
|
|
|
659 x = w;
|
|
|
660 remove_root (w);
|
|
|
661 d = x->m_degree;
|
|
145
|
662 gcc_checking_assert (d < D);
|
|
111
|
663 while (a[d] != NULL)
|
|
|
664 {
|
|
|
665 y = a[d];
|
|
|
666 if (x->compare (y) > 0)
|
|
|
667 std::swap (x, y);
|
|
|
668 y->link (x);
|
|
|
669 a[d] = NULL;
|
|
|
670 d++;
|
|
|
671 }
|
|
|
672 a[d] = x;
|
|
|
673 }
|
|
|
674 m_min = NULL;
|
|
|
675 for (i = 0; i < D; i++)
|
|
|
676 if (a[i] != NULL)
|
|
|
677 {
|
|
|
678 insert_root (a[i]);
|
|
|
679 if (m_min == NULL || a[i]->compare (m_min) < 0)
|
|
|
680 m_min = a[i];
|
|
|
681 }
|
|
|
682 }
|
|
|
683
|
|
|
684 #endif // GCC_FIBONACCI_HEAP_H
|
