Mercurial > hg > CbC > GCC_original

comparison gcc/fibonacci_heap.h @ 16:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2017 Free Software Foundation, Inc.
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