[gcc]
[official-gcc.git] / gcc / fibonacci_heap.h
blob1345027f27848ece2a6ae4f28f7b10e84a5279d5
1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2016 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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.
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.
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/>. */
22 /* Fibonacci heaps are somewhat complex, but, there's an article in
23 DDJ that explains them pretty well:
25 http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
27 Introduction to algorithms by Corman and Rivest also goes over them.
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).
33 Amortized and real worst case time for operations:
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. */
40 #ifndef GCC_FIBONACCI_HEAP_H
41 #define GCC_FIBONACCI_HEAP_H
43 /* Forward definition. */
45 template<class K, class V>
46 class fibonacci_heap;
48 /* Fibonacci heap node class. */
50 template<class K, class V>
51 class fibonacci_node
53 typedef fibonacci_node<K,V> fibonacci_node_t;
54 friend class fibonacci_heap<K,V>;
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)
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)
70 /* Compare fibonacci node with OTHER node. */
71 int compare (fibonacci_node_t *other)
73 if (m_key < other->m_key)
74 return -1;
75 if (m_key > other->m_key)
76 return 1;
77 return 0;
80 /* Compare the node with a given KEY. */
81 int compare_data (K key)
83 return fibonacci_node_t (key).compare (this);
86 /* Remove fibonacci heap node. */
87 fibonacci_node_t *remove ();
89 /* Link the node with PARENT. */
90 void link (fibonacci_node_t *parent);
92 /* Return key associated with the node. */
93 K get_key ()
95 return m_key;
98 /* Return data associated with the node. */
99 V *get_data ()
101 return m_data;
104 private:
105 /* Put node B after this node. */
106 void insert_after (fibonacci_node_t *b);
108 /* Insert fibonacci node B after this node. */
109 void insert_before (fibonacci_node_t *b)
111 m_left->insert_after (b);
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;
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
140 /* Fibonacci heap class. */
141 template<class K, class V>
142 class fibonacci_heap
144 typedef fibonacci_node<K,V> fibonacci_node_t;
145 friend class fibonacci_node<K,V>;
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)
154 /* Destructor. */
155 ~fibonacci_heap ()
157 while (m_min != NULL)
158 delete (extract_minimum_node ());
161 /* Insert new node given by KEY and DATA associated with the key. */
162 fibonacci_node_t *insert (K key, V *data);
164 /* Return true if no entry is present. */
165 bool empty ()
167 return m_nodes == 0;
170 /* Return the number of nodes. */
171 size_t nodes ()
173 return m_nodes;
176 /* Return minimal key presented in the heap. */
177 K min_key ()
179 if (m_min == NULL)
180 gcc_unreachable ();
182 return m_min->m_key;
185 /* For given NODE, set new KEY value. */
186 K replace_key (fibonacci_node_t *node, K key)
188 K okey = node->m_key;
190 replace_key_data (node, key, node->m_data);
191 return okey;
194 /* For given NODE, decrease value to new KEY. */
195 K decrease_key (fibonacci_node_t *node, K key)
197 gcc_assert (key <= node->m_key);
198 return replace_key (node, key);
201 /* For given NODE, set new KEY and DATA value. */
202 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
204 /* Extract minimum node in the heap. If RELEASE is specified,
205 memory is released. */
206 V *extract_min (bool release = true);
208 /* Return value associated with minimum node in the heap. */
209 V *min ()
211 if (m_min == NULL)
212 return NULL;
214 return m_min->m_data;
217 /* Replace data associated with NODE and replace it with DATA. */
218 V *replace_data (fibonacci_node_t *node, V *data)
220 return replace_key_data (node, node->m_key, data);
223 /* Delete NODE in the heap. */
224 V *delete_node (fibonacci_node_t *node, bool release = true);
226 /* Union the heap with HEAPB. */
227 fibonacci_heap *union_with (fibonacci_heap *heapb);
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);
233 /* Insert new NODE that has already filled key and value. */
234 fibonacci_node_t *insert_node (fibonacci_node_t *node);
236 /* Insert it into the root list. */
237 void insert_root (fibonacci_node_t *node);
239 /* Remove NODE from PARENT's child list. */
240 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
242 /* Process cut of node Y and do it recursivelly. */
243 void cascading_cut (fibonacci_node_t *y);
245 /* Extract minimum node from the heap. */
246 fibonacci_node_t * extract_minimum_node ();
248 /* Remove root NODE from the heap. */
249 void remove_root (fibonacci_node_t *node);
251 /* Consolidate heap. */
252 void consolidate ();
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;
264 /* Remove fibonacci heap node. */
266 template<class K, class V>
267 fibonacci_node<K,V> *
268 fibonacci_node<K,V>::remove ()
270 fibonacci_node<K,V> *ret;
272 if (this == m_left)
273 ret = NULL;
274 else
275 ret = m_left;
277 if (m_parent != NULL && m_parent->m_child == this)
278 m_parent->m_child = ret;
280 m_right->m_left = m_left;
281 m_left->m_right = m_right;
283 m_parent = NULL;
284 m_left = this;
285 m_right = this;
287 return ret;
290 /* Link the node with PARENT. */
292 template<class K, class V>
293 void
294 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
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;
305 /* Put node B after this node. */
307 template<class K, class V>
308 void
309 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
311 fibonacci_node<K,V> *a = this;
313 if (a == a->m_right)
315 a->m_right = b;
316 a->m_left = b;
317 b->m_right = a;
318 b->m_left = a;
320 else
322 b->m_right = a->m_right;
323 a->m_right->m_left = b;
324 a->m_right = b;
325 b->m_left = a;
329 /* Insert new node given by KEY and DATA associated with the key. */
331 template<class K, class V>
332 fibonacci_node<K,V>*
333 fibonacci_heap<K,V>::insert (K key, V *data)
335 /* Create the new node. */
336 fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
338 return insert_node (node);
341 /* Insert new NODE given by DATA associated with the key. */
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)
347 /* Set the node's data. */
348 node->m_data = data;
349 node->m_key = key;
351 return insert_node (node);
354 /* Insert new NODE that has already filled key and value. */
356 template<class K, class V>
357 fibonacci_node<K,V>*
358 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
360 /* Insert it into the root list. */
361 insert_root (node);
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;
368 m_nodes++;
370 return node;
373 /* For given NODE, set new KEY and DATA value. */
375 template<class K, class V>
377 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
378 V *data)
380 K okey;
381 fibonacci_node<K,V> *y;
382 V *odata = node->m_data;
384 /* If we wanted to, we do a real increase by redeleting and
385 inserting. */
386 if (node->compare_data (key) > 0)
388 delete_node (node, false);
390 node = new (node) fibonacci_node_t ();
391 insert (node, key, data);
393 return odata;
396 okey = node->m_key;
397 node->m_data = data;
398 node->m_key = key;
399 y = node->m_parent;
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;
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)
412 cut (node, y);
413 cascading_cut (y);
416 if (node->compare (m_min) <= 0)
417 m_min = node;
419 return odata;
422 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
423 is true. */
425 template<class K, class V>
427 fibonacci_heap<K,V>::extract_min (bool release)
429 fibonacci_node<K,V> *z;
430 V *ret = NULL;
432 /* If we don't have a min set, it means we have no nodes. */
433 if (m_min != NULL)
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;
440 if (release)
441 delete (z);
444 return ret;
447 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
449 template<class K, class V>
451 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
453 V *ret = node->m_data;
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)
459 fprintf (stderr, "Can't force minimum on fibheap.\n");
460 abort ();
462 extract_min (release);
464 return ret;
467 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
469 template<class K, class V>
470 fibonacci_heap<K,V>*
471 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
473 fibonacci_heap<K,V> *heapa = this;
475 fibonacci_node<K,V> *a_root, *b_root;
477 /* If one of the heaps is empty, the union is just the other heap. */
478 if ((a_root = heapa->m_root) == NULL)
480 delete (heapa);
481 return heapb;
483 if ((b_root = heapb->m_root) == NULL)
485 delete (heapb);
486 return heapa;
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;
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;
499 /* Set m_min to NULL to not to delete live fibonacci nodes. */
500 heapb->m_min = NULL;
501 delete (heapb);
503 return heapa;
506 /* Insert it into the root list. */
508 template<class K, class V>
509 void
510 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
512 /* If the heap is currently empty, the new node becomes the singleton
513 circular root list. */
514 if (m_root == NULL)
516 m_root = node;
517 node->m_left = node;
518 node->m_right = node;
519 return;
522 /* Otherwise, insert it in the circular root list between the root
523 and it's right node. */
524 m_root->insert_after (node);
527 /* Remove NODE from PARENT's child list. */
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)
534 node->remove ();
535 parent->m_degree--;
536 insert_root (node);
537 node->m_parent = NULL;
538 node->m_mark = 0;
541 /* Process cut of node Y and do it recursivelly. */
543 template<class K, class V>
544 void
545 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
547 fibonacci_node<K,V> *z;
549 while ((z = y->m_parent) != NULL)
551 if (y->m_mark == 0)
553 y->m_mark = 1;
554 return;
556 else
558 cut (y, z);
559 y = z;
564 /* Extract minimum node from the heap. */
566 template<class K, class V>
567 fibonacci_node<K,V>*
568 fibonacci_heap<K,V>::extract_minimum_node ()
570 fibonacci_node<K,V> *ret = m_min;
571 fibonacci_node<K,V> *x, *y, *orig;
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)
577 if (orig == NULL)
578 orig = x;
579 y = x->m_right;
580 x->m_parent = NULL;
581 insert_root (x);
584 /* Remove the old root. */
585 remove_root (ret);
586 m_nodes--;
588 /* If we are left with no nodes, then the min is NULL. */
589 if (m_nodes == 0)
590 m_min = NULL;
591 else
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 ();
599 return ret;
602 /* Remove root NODE from the heap. */
604 template<class K, class V>
605 void
606 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
608 if (node->m_left == node)
609 m_root = NULL;
610 else
611 m_root = node->remove ();
614 /* Consolidate heap. */
616 template<class K, class V>
617 void fibonacci_heap<K,V>::consolidate ()
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;
625 while ((w = m_root) != NULL)
627 x = w;
628 remove_root (w);
629 d = x->m_degree;
630 while (a[d] != NULL)
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++;
639 a[d] = x;
641 m_min = NULL;
642 for (i = 0; i < D; i++)
643 if (a[i] != NULL)
645 insert_root (a[i]);
646 if (m_min == NULL || a[i]->compare (m_min) < 0)
647 m_min = a[i];
651 #endif // GCC_FIBONACCI_HEAP_H