Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
BinomialQueue.h
1 /*
2  * BinomialQueue class
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2021, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef INCLUDE_ELM_DATA_BINOMIALQUEUE_H_
22 #define INCLUDE_ELM_DATA_BINOMIALQUEUE_H_
23 
24 #include <elm/assert.h>
25 #include <elm/compare.h>
26 #include <elm/data/custom.h>
27 
28 namespace elm {
29 
30 template <class T, class C = Comparator<T>, class A = DefaultAlloc>
31 class BinomialQueue: public C, public A {
32  const static unsigned NOT_IN_HEAP = type_info<unsigned>::max;
33 
34  class Node {
35  public:
36  Node(const T& xx)
37  : next(nullptr), child(nullptr),
38  degree(NOT_IN_HEAP), x(xx) { }
39  Node *next, *child;
40  unsigned degree;
41  T x;
42  };
43 
44 public:
45  BinomialQueue(const C& c = single<C>(), const A& a = single<A>())
46  : C(c), A(a), _head(nullptr), _min(nullptr) { }
47 
48  inline bool isEmpty() const { return _head == nullptr && _min == nullptr; }
49 
50  const T& head() const {
51  Node *prev;
52  Node *node = min(prev);
53  return node->x;
54  }
55 
56  T get() {
57  Node *p;
58  Node *n = min(p);
59  if(p != nullptr)
60  p->next = n->next;
61  else
62  _head = n->next;
63  join(reverse(n->child));
64  auto x = n->x;
65  A::free(n);
66  return x;
67  }
68 
69  void put(const T& x) {
70  auto n = new(A::allocate(sizeof(Node))) Node(x);
71  n->degree = 0;
72  if(_min != nullptr && higher(n->x, _min->x)) {
73  auto m = _min;
74  m->child = nullptr;
75  m->next = nullptr;
76  m->degree = 0;
77  join(m);
78  _min = n;
79  }
80  else {
81  join(n);
82  }
83  }
84 
85 # ifdef TEST_BINOMIAL_QUEUE
86  void dump(io::Output& out);
87  void dump_rec(io::Output& out, Node *node);
88 # endif
89 private:
90 
91  inline bool higher(const T& x, const T& y) const { return C::doCompare(x, y) <= 0; }
92 
93  inline void link(Node *root, Node *child) {
94  child->next = root->child;
95  root->child = child;
96  root->degree++;
97  }
98 
99  Node *min(Node*& prev) {
100  ASSERTP(_head != nullptr, "no head in empty queue");
101  prev = nullptr;
102  Node *n = _head, *p = _head, *c = _head->next;
103  while(c != nullptr) {
104  if(higher(c->x, n->x)) {
105  n = c;
106  prev = p;
107  }
108  p = c;
109  c = c->next;
110  }
111  return n;
112  }
113 
114  Node *merge(Node *a, Node *b) {
115  Node *h = nullptr, **p = &h;
116  while(a != nullptr && b != nullptr) {
117  if(a->degree < b->degree) {
118  *p = a;
119  a = a->next;
120  }
121  else {
122  *p = b;
123  b = b->next;
124  }
125  p = &(*p)->next;
126  }
127  if(a != nullptr)
128  *p = a;
129  else
130  *p = b;
131  return h;
132  }
133 
134  void join(Node *h2) {
135  if(h2 == nullptr)
136  return;
137  if(_head == nullptr) {
138  _head = h2;
139  return;
140  }
141  Node *h1 = merge(_head, h2);
142  Node *p = nullptr, *x = h1, *n = x->next;
143  while(n != nullptr) {
144  if(x->degree != n->degree || (n->next != nullptr && n->next->degree == x->degree)) {
145  p = x;
146  x = n;
147  }
148  else if(higher(x->x, n->x)) {
149  x->next = n->next;
150  link(x, n);
151  }
152  else {
153  if(p != nullptr)
154  p->next = n;
155  else
156  h1 = n;
157  link(n, x);
158  x = n;
159  }
160  n = x->next;
161  }
162  _head = h1;
163  }
164 
165  Node *reverse(Node *h) {
166  if(h == nullptr)
167  return nullptr;
168  Node *t = nullptr;
169  while(h->next != nullptr) {
170  auto n = h->next;
171  h->next = t;
172  t = h;
173  h = n;
174  }
175  h->next = t;
176  return h;
177  }
178 
179  Node *_head, *_min;
180 };
181 
182 } // elm
183 
184 #endif /* INCLUDE_ELM_DATA_BINOMIALQUEUE_H_ */
185 
elm::t::out
typename type_info< T >::out_t out
Definition: type_info.h:284
elm::io::p
Printable< T, M > p(const T &data, const M &man)
Definition: Output.h:302
elm::BinomialQueue
Definition: BinomialQueue.h:31
elm::type_info
Definition: type_info.h:56
elm::Comparator::t
T t
Definition: compare.h:36
elm::BinomialQueue::BinomialQueue
BinomialQueue(const C &c=single< C >(), const A &a=single< A >())
Definition: BinomialQueue.h:45
elm::BinomialQueue::head
const T & head() const
Definition: BinomialQueue.h:50
elm::BinomialQueue::isEmpty
bool isEmpty() const
Definition: BinomialQueue.h:48
elm
Definition: adapter.h:26
elm::io::Output
Definition: Output.h:179
elm::BinomialQueue::put
void put(const T &x)
Definition: BinomialQueue.h:69
elm::BinomialQueue::get
T get()
Definition: BinomialQueue.h:56