gcc/fibonacci_heap.h

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 1998-2015 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): m_parent (NULL), m_child (NULL), m_left (this),
  65     m_right (this), m_key (key),
  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 it into the root list.  */
 234   void insert_root (fibonacci_node_t *node);
 235
 236   /* Remove NODE from PARENT's child list.  */
 237   void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
 238
 239   /* Process cut of node Y and do it recursivelly.  */
 240   void cascading_cut (fibonacci_node_t *y);
 241
 242   /* Extract minimum node from the heap.  */
 243   fibonacci_node_t * extract_minimum_node ();
 244
 245   /* Remove root NODE from the heap.  */
 246   void remove_root (fibonacci_node_t *node);
 247
 248   /* Consolidate heap.  */
 249   void consolidate ();
 250
 251   /* Number of nodes.  */
 252   size_t m_nodes;
 253   /* Minimum node of the heap.  */
 254   fibonacci_node_t *m_min;
 255   /* Root node of the heap.  */
 256   fibonacci_node_t *m_root;
 257   /* Global minimum given in the heap construction.  */
 258   K m_global_min_key;
 259 };
 260
 261 /* Remove fibonacci heap node.  */
 262
 263 template<class K, class V>
 264 fibonacci_node<K,V> *
 265 fibonacci_node<K,V>::remove ()
 266 {
 267   fibonacci_node<K,V> *ret;
 268
 269   if (this == m_left)
 270     ret = NULL;
 271   else
 272     ret = m_left;
 273
 274   if (m_parent != NULL && m_parent->m_child == this)
 275     m_parent->m_child = ret;
 276
 277   m_right->m_left = m_left;
 278   m_left->m_right = m_right;
 279
 280   m_parent = NULL;
 281   m_left = this;
 282   m_right = this;
 283
 284   return ret;
 285 }
 286
 287 /* Link the node with PARENT.  */
 288
 289 template<class K, class V>
 290 void
 291 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
 292 {
 293   if (parent->m_child == NULL)
 294     parent->m_child = this;
 295   else
 296     parent->m_child->insert_before (this);
 297   m_parent = parent;
 298   parent->m_degree++;
 299   m_mark = 0;
 300 }
 301
 302 /* Put node B after this node.  */
 303
 304 template<class K, class V>
 305 void
 306 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
 307 {
 308   fibonacci_node<K,V> *a = this;
 309
 310   if (a == a->m_right)
 311     {
 312       a->m_right = b;
 313       a->m_left = b;
 314       b->m_right = a;
 315       b->m_left = a;
 316     }
 317   else
 318     {
 319       b->m_right = a->m_right;
 320       a->m_right->m_left = b;
 321       a->m_right = b;
 322       b->m_left = a;
 323     }
 324 }
 325
 326 /* Insert new node given by KEY and DATA associated with the key.  */
 327
 328 template<class K, class V>
 329 fibonacci_node<K,V>*
 330 fibonacci_heap<K,V>::insert (K key, V *data)
 331 {
 332   /* Create the new node.  */
 333   fibonacci_node<K,V> *node = new fibonacci_node_t ();
 334
 335   return insert (node, key, data);
 336 }
 337
 338 /* Insert new NODE given by KEY and DATA associated with the key.  */
 339
 340 template<class K, class V>
 341 fibonacci_node<K,V>*
 342 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
 343 {
 344   /* Set the node's data.  */
 345   node->m_data = data;
 346   node->m_key = key;
 347
 348   /* Insert it into the root list.  */
 349   insert_root (node);
 350
 351   /* If their was no minimum, or this key is less than the min,
 352      it's the new min.  */
 353   if (m_min == NULL || node->m_key < m_min->m_key)
 354     m_min = node;
 355
 356   m_nodes++;
 357
 358   return node;
 359 }
 360
 361 /* For given NODE, set new KEY and DATA value.  */
 362 template<class K, class V>
 363 V*
 364 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
 365                                        V *data)
 366 {
 367   K okey;
 368   fibonacci_node<K,V> *y;
 369   V *odata = node->m_data;
 370
 371   /* If we wanted to, we do a real increase by redeleting and
 372      inserting.  */
 373   if (node->compare_data (key) > 0)
 374     {
 375       delete_node (node, false);
 376
 377       node = new (node) fibonacci_node_t ();
 378       insert (node, key, data);
 379
 380       return odata;
 381     }
 382
 383   okey = node->m_key;
 384   node->m_data = data;
 385   node->m_key = key;
 386   y = node->m_parent;
 387
 388   /* Short-circuit if the key is the same, as we then don't have to
 389      do anything.  Except if we're trying to force the new node to
 390      be the new minimum for delete.  */
 391   if (okey == key && okey != m_global_min_key)
 392     return odata;
 393
 394   /* These two compares are specifically <= 0 to make sure that in the case
 395      of equality, a node we replaced the data on, becomes the new min.  This
 396      is needed so that delete's call to extractmin gets the right node.  */
 397   if (y != NULL && node->compare (y) <= 0)
 398     {
 399       cut (node, y);
 400       cascading_cut (y);
 401     }
 402
 403   if (node->compare (m_min) <= 0)
 404     m_min = node;
 405
 406   return odata;
 407 }
 408
 409 /* Extract minimum node in the heap.  */
 410 template<class K, class V>
 411 V*
 412 fibonacci_heap<K,V>::extract_min (bool release)
 413 {
 414   fibonacci_node<K,V> *z;
 415   V *ret = NULL;
 416
 417   /* If we don't have a min set, it means we have no nodes.  */
 418   if (m_min != NULL)
 419     {
 420       /* Otherwise, extract the min node, free the node, and return the
 421        node's data.  */
 422       z = extract_minimum_node ();
 423       ret = z->m_data;
 424
 425       if (release)
 426         delete (z);
 427     }
 428
 429   return ret;
 430 }
 431
 432 /* Delete NODE in the heap, if RELEASE is specified memory is released.  */
 433
 434 template<class K, class V>
 435 V*
 436 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
 437 {
 438   V *ret = node->m_data;
 439
 440   /* To perform delete, we just make it the min key, and extract.  */
 441   replace_key (node, m_global_min_key);
 442   if (node != m_min)
 443     {
 444       fprintf (stderr, "Can't force minimum on fibheap.\n");
 445       abort ();
 446     }
 447   extract_min (release);
 448
 449   return ret;
 450 }
 451
 452 /* Union the heap with HEAPB.  */
 453
 454 template<class K, class V>
 455 fibonacci_heap<K,V>*
 456 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
 457 {
 458   fibonacci_heap<K,V> *heapa = this;
 459
 460   fibonacci_node<K,V> *a_root, *b_root;
 461
 462   /* If one of the heaps is empty, the union is just the other heap.  */
 463   if ((a_root = heapa->m_root) == NULL)
 464     {
 465       delete (heapa);
 466       return heapb;
 467     }
 468   if ((b_root = heapb->m_root) == NULL)
 469     {
 470       delete (heapb);
 471       return heapa;
 472     }
 473
 474   /* Merge them to the next nodes on the opposite chain.  */
 475   a_root->m_left->m_right = b_root;
 476   b_root->m_left->m_right = a_root;
 477   std::swap (a_root->m_left, b_root->m_left);
 478   heapa->m_nodes += heapb->m_nodes;
 479
 480   /* And set the new minimum, if it's changed.  */
 481   if (heapb->min->compare (heapa->min) < 0)
 482     heapa->m_min = heapb->m_min;
 483
 484   delete (heapb);
 485   return heapa;
 486 }
 487
 488 /* Insert it into the root list.  */
 489
 490 template<class K, class V>
 491 void
 492 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
 493 {
 494   /* If the heap is currently empty, the new node becomes the singleton
 495      circular root list.  */
 496   if (m_root == NULL)
 497     {
 498       m_root = node;
 499       node->m_left = node;
 500       node->m_right = node;
 501       return;
 502     }
 503
 504   /* Otherwise, insert it in the circular root list between the root
 505      and it's right node.  */
 506   m_root->insert_after (node);
 507 }
 508
 509 /* Remove NODE from PARENT's child list.  */
 510
 511 template<class K, class V>
 512 void
 513 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
 514                           fibonacci_node<K,V> *parent)
 515 {
 516   node->remove ();
 517   parent->m_degree--;
 518   insert_root (node);
 519   node->m_parent = NULL;
 520   node->m_mark = 0;
 521 }
 522
 523 /* Process cut of node Y and do it recursivelly.  */
 524
 525 template<class K, class V>
 526 void
 527 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
 528 {
 529   fibonacci_node<K,V> *z;
 530
 531   while ((z = y->m_parent) != NULL)
 532     {
 533       if (y->m_mark == 0)
 534         {
 535           y->m_mark = 1;
 536           return;
 537         }
 538       else
 539         {
 540           cut (y, z);
 541           y = z;
 542         }
 543     }
 544 }
 545
 546 /* Extract minimum node from the heap.  */
 547 template<class K, class V>
 548 fibonacci_node<K,V>*
 549 fibonacci_heap<K,V>::extract_minimum_node ()
 550 {
 551   fibonacci_node<K,V> *ret = m_min;
 552   fibonacci_node<K,V> *x, *y, *orig;
 553
 554   /* Attach the child list of the minimum node to the root list of the heap.
 555      If there is no child list, we don't do squat.  */
 556   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
 557     {
 558       if (orig == NULL)
 559         orig = x;
 560       y = x->m_right;
 561       x->m_parent = NULL;
 562       insert_root (x);
 563     }
 564
 565   /* Remove the old root.  */
 566   remove_root (ret);
 567   m_nodes--;
 568
 569   /* If we are left with no nodes, then the min is NULL.  */
 570   if (m_nodes == 0)
 571     m_min = NULL;
 572   else
 573     {
 574       /* Otherwise, consolidate to find new minimum, as well as do the reorg
 575        work that needs to be done.  */
 576       m_min = ret->m_right;
 577       consolidate ();
 578     }
 579
 580   return ret;
 581 }
 582
 583 /* Remove root NODE from the heap.  */
 584
 585 template<class K, class V>
 586 void
 587 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
 588 {
 589   if (node->m_left == node)
 590     m_root = NULL;
 591   else
 592     m_root = node->remove ();
 593 }
 594
 595 /* Consolidate heap.  */
 596
 597 template<class K, class V>
 598 void fibonacci_heap<K,V>::consolidate ()
 599 {
 600   int D = 1 + 8 * sizeof (long);
 601   auto_vec<fibonacci_node<K,V> *> a (D);
 602   a.safe_grow_cleared (D);
 603   fibonacci_node<K,V> *w, *x, *y;
 604   int i, d;
 605
 606   while ((w = m_root) != NULL)
 607     {
 608       x = w;
 609       remove_root (w);
 610       d = x->m_degree;
 611       while (a[d] != NULL)
 612         {
 613           y = a[d];
 614           if (x->compare (y) > 0)
 615             std::swap (x, y);
 616           y->link (x);
 617           a[d] = NULL;
 618           d++;
 619         }
 620       a[d] = x;
 621     }
 622   m_min = NULL;
 623   for (i = 0; i < D; i++)
 624     if (a[i] != NULL)
 625       {
 626         insert_root (a[i]);
 627         if (m_min == NULL || a[i]->compare (m_min) < 0)
 628           m_min = a[i];
 629       }
 630 }
 631
 632 #endif  // GCC_FIBONACCI_HEAP_H