gcc/fibonacci_heap.h

   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