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