1 /* Fibonacci heap for GNU compiler. 2 Copyright (C) 1998-2018 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 652