gcc/fibonacci_heap.h

   1 /* Vector API for GNU compiler.
   2    Copyright (C) 1998-2014 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, *temp;
 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   temp = a_root->m_left;
 478   a_root->m_left = b_root->m_left;
 479   b_root->m_left = temp;
 480   heapa->m_nodes += heapb->m_nodes;
 481
 482   /* And set the new minimum, if it's changed.  */
 483   if (heapb->min->compare (heapa->min) < 0)
 484     heapa->m_min = heapb->m_min;
 485
 486   delete (heapb);
 487   return heapa;
 488 }
 489
 490 /* Insert it into the root list.  */
 491
 492 template<class K, class V>
 493 void
 494 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
 495 {
 496   /* If the heap is currently empty, the new node becomes the singleton
 497      circular root list.  */
 498   if (m_root == NULL)
 499     {
 500       m_root = node;
 501       node->m_left = node;
 502       node->m_right = node;
 503       return;
 504     }
 505
 506   /* Otherwise, insert it in the circular root list between the root
 507      and it's right node.  */
 508   m_root->insert_after (node);
 509 }
 510
 511 /* Remove NODE from PARENT's child list.  */
 512
 513 template<class K, class V>
 514 void
 515 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
 516                           fibonacci_node<K,V> *parent)
 517 {
 518   node->remove ();
 519   parent->m_degree--;
 520   insert_root (node);
 521   node->m_parent = NULL;
 522   node->m_mark = 0;
 523 }
 524
 525 /* Process cut of node Y and do it recursivelly.  */
 526
 527 template<class K, class V>
 528 void
 529 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
 530 {
 531   fibonacci_node<K,V> *z;
 532
 533   while ((z = y->m_parent) != NULL)
 534     {
 535       if (y->m_mark == 0)
 536         {
 537           y->m_mark = 1;
 538           return;
 539         }
 540       else
 541         {
 542           cut (y, z);
 543           y = z;
 544         }
 545     }
 546 }
 547
 548 /* Extract minimum node from the heap.  */
 549 template<class K, class V>
 550 fibonacci_node<K,V>*
 551 fibonacci_heap<K,V>::extract_minimum_node ()
 552 {
 553   fibonacci_node<K,V> *ret = m_min;
 554   fibonacci_node<K,V> *x, *y, *orig;
 555
 556   /* Attach the child list of the minimum node to the root list of the heap.
 557      If there is no child list, we don't do squat.  */
 558   for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
 559     {
 560       if (orig == NULL)
 561         orig = x;
 562       y = x->m_right;
 563       x->m_parent = NULL;
 564       insert_root (x);
 565     }
 566
 567   /* Remove the old root.  */
 568   remove_root (ret);
 569   m_nodes--;
 570
 571   /* If we are left with no nodes, then the min is NULL.  */
 572   if (m_nodes == 0)
 573     m_min = NULL;
 574   else
 575     {
 576       /* Otherwise, consolidate to find new minimum, as well as do the reorg
 577        work that needs to be done.  */
 578       m_min = ret->m_right;
 579       consolidate ();
 580     }
 581
 582   return ret;
 583 }
 584
 585 /* Remove root NODE from the heap.  */
 586
 587 template<class K, class V>
 588 void
 589 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
 590 {
 591   if (node->m_left == node)
 592     m_root = NULL;
 593   else
 594     m_root = node->remove ();
 595 }
 596
 597 /* Consolidate heap.  */
 598
 599 template<class K, class V>
 600 void fibonacci_heap<K,V>::consolidate ()
 601 {
 602   int D = 1 + 8 * sizeof (long);
 603   auto_vec<fibonacci_node<K,V> *> a (D);
 604   a.safe_grow_cleared (D);
 605   fibonacci_node<K,V> *w, *x, *y;
 606   int i, d;
 607
 608   while ((w = m_root) != NULL)
 609     {
 610       x = w;
 611       remove_root (w);
 612       d = x->m_degree;
 613       while (a[d] != NULL)
 614         {
 615           y = a[d];
 616           if (x->compare (y) > 0)
 617             std::swap (x, y);
 618           y->link (x);
 619           a[d] = NULL;
 620           d++;
 621         }
 622       a[d] = x;
 623     }
 624   m_min = NULL;
 625   for (i = 0; i < D; i++)
 626     if (a[i] != NULL)
 627       {
 628         insert_root (a[i]);
 629         if (m_min == NULL || a[i]->compare (m_min) < 0)
 630           m_min = a[i];
 631       }
 632 }
 633
 634 #endif  // GCC_FIBONACCI_HEAP_H