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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
45template<class K, class V>
46class fibonacci_heap;
47
48/* Fibonacci heap node class.  */
49
50template<class K, class V>
51class fibonacci_node
52{
53  typedef fibonacci_node<K,V> fibonacci_node_t;
54  friend class fibonacci_heap<K,V>;
55
56public:
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
104private:
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. */
141template<class K, class V>
142class fibonacci_heap
143{
144  typedef fibonacci_node<K,V> fibonacci_node_t;
145  friend class fibonacci_node<K,V>;
146
147public:
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
229private:
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
263template<class K, class V>
264fibonacci_node<K,V> *
265fibonacci_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
289template<class K, class V>
290void
291fibonacci_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
304template<class K, class V>
305void
306fibonacci_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
328template<class K, class V>
329fibonacci_node<K,V>*
330fibonacci_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
340template<class K, class V>
341fibonacci_node<K,V>*
342fibonacci_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.  */
362template<class K, class V>
363V*
364fibonacci_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.  */
410template<class K, class V>
411V*
412fibonacci_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
434template<class K, class V>
435V*
436fibonacci_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
454template<class K, class V>
455fibonacci_heap<K,V>*
456fibonacci_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
492template<class K, class V>
493void
494fibonacci_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
513template<class K, class V>
514void
515fibonacci_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
527template<class K, class V>
528void
529fibonacci_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.  */
549template<class K, class V>
550fibonacci_node<K,V>*
551fibonacci_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
587template<class K, class V>
588void
589fibonacci_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
599template<class K, class V>
600void 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
635