aGrUM  0.15.1
heap_tpl.h
Go to the documentation of this file.
1 
29 #include <sstream>
30 #include <string>
31 
32 // to ease IDE parser
33 #include <agrum/core/heap.h>
34 
35 namespace gum {
36 
37  // basic constructor. Creates an empty heap
38  template < typename Val, typename Cmp, typename Alloc >
39  Heap< Val, Cmp, Alloc >::Heap(Cmp compare, Size capacity) : __cmp(compare) {
40  __heap.reserve(capacity);
41 
42  // for debugging purposes
43  GUM_CONSTRUCTOR(Heap);
44  }
45 
46  // initializer list constructor
47  template < typename Val, typename Cmp, typename Alloc >
48  Heap< Val, Cmp, Alloc >::Heap(std::initializer_list< Val > list) {
49  __heap.reserve(list.size());
50  for (const auto& elt : list) {
51  insert(elt);
52  }
53 
54  // for debugging purposes
55  GUM_CONSTRUCTOR(Heap);
56  }
57 
58  // copy constructor
59  template < typename Val, typename Cmp, typename Alloc >
61  __heap(from.__heap), __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
62  // for debugging purposes
63  GUM_CONS_CPY(Heap);
64  }
65 
66  // generalized copy constructor
67  template < typename Val, typename Cmp, typename Alloc >
68  template < typename OtherAlloc >
70  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
71  __heap.reserve(__nb_elements);
72 
73  // copy the elements of from.__heap
74  for (unsigned i = 0; i < __nb_elements; ++i)
75  __heap.push_back(from.__heap[i]);
76 
77  // for debugging purposes
78  GUM_CONS_CPY(Heap);
79  }
80 
81  // move constructor
82  template < typename Val, typename Cmp, typename Alloc >
84  __heap(std::move(from.__heap)), __nb_elements(std::move(from.__nb_elements)),
85  __cmp(std::move(from.__cmp)) {
86  // for debugging purposes
87  GUM_CONS_MOV(Heap);
88  }
89 
90  // destructor
91  template < typename Val, typename Cmp, typename Alloc >
93  // for debugging purposes
94  GUM_DESTRUCTOR(Heap);
95  }
96 
97  // copy operator
98  template < typename Val, typename Cmp, typename Alloc >
101  // avoid self assignment
102  if (this != &from) {
103  try {
104  __heap = from.__heap;
105  } catch (...) {
106  __heap.clear();
107  __nb_elements = 0;
108 
109  throw;
110  }
111 
112  // set the comparison function
113  __cmp = from.__cmp;
115 
116  // for debugging purposes
117  GUM_OP_CPY(Heap);
118  }
119 
120  return *this;
121  }
122 
123  // generalized copy operator
124  template < typename Val, typename Cmp, typename Alloc >
125  template < typename OtherAlloc >
128  // avoid self assignment
129  if (this != &from) {
130  try {
131  __heap.clear();
132 
133  if (__heap.capacity() < from.__nb_elements)
134  __heap.reserve(from.__nb_elements);
135 
136  for (unsigned int i = 0; i < from.__nb_elements; ++i) {
137  __heap.push_back(from.__heap[i]);
138  }
139  } catch (...) {
140  __heap.clear();
141  __nb_elements = 0;
142  throw;
143  }
144 
145  __cmp = from.__cmp;
147 
148  // for debugging purposes
149  GUM_OP_CPY(Heap);
150  }
151 
152  return *this;
153  }
154 
155  // move operator
156  template < typename Val, typename Cmp, typename Alloc >
159  // avoid self assignment
160  if (this != &from) {
161  __heap = std::move(from.__heap);
162  __nb_elements = std::move(from.__nb_elements);
163  __cmp = std::move(from.__cmp);
164  }
165 
166  return *this;
167  }
168 
169  // returns the element at the top of the heap
170  template < typename Val, typename Cmp, typename Alloc >
171  INLINE const Val& Heap< Val, Cmp, Alloc >::top() const {
172  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
173 
174  return __heap[0];
175  }
176 
177  // returns the number of elements in the heap
178  template < typename Val, typename Cmp, typename Alloc >
179  INLINE Size Heap< Val, Cmp, Alloc >::size() const noexcept {
180  return __nb_elements;
181  }
182 
183  // return the size of the array storing the heap
184  template < typename Val, typename Cmp, typename Alloc >
185  INLINE Size Heap< Val, Cmp, Alloc >::capacity() const noexcept {
186  return Size(__heap.size());
187  }
188 
189  // changes the size of the array storing the heap
190  template < typename Val, typename Cmp, typename Alloc >
191  INLINE void Heap< Val, Cmp, Alloc >::resize(Size new_size) {
192  if (new_size > __nb_elements) __heap.reserve(new_size);
193  }
194 
195  // removes the element at position 'index' from the heap
196  template < typename Val, typename Cmp, typename Alloc >
198  if (index >= __nb_elements) return;
199 
200  // remove the element and put the last element in its place
201  Val last = std::move(__heap[__nb_elements - 1]);
202  __heap.pop_back();
203  --__nb_elements;
204 
205  if (!__nb_elements || (index == __nb_elements)) return;
206 
207  // restore the heap property
208  Size i = index;
209 
210  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
211  // let j be the max child
212  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1], __heap[j])) ++j;
213 
214  // if "last" is smaller than __heap[j], "last" must be stored at index i
215  if (__cmp(last, __heap[j])) break;
216 
217  __heap[i] = std::move(__heap[j]);
218  }
219 
220  __heap[i] = std::move(last);
221  }
222 
223  // removes a given element from the heap (but does not return it)
224  template < typename Val, typename Cmp, typename Alloc >
225  INLINE void Heap< Val, Cmp, Alloc >::erase(const Val& val) {
226  // find val in the heap
227  for (Size i = 0; i < __nb_elements; ++i)
228  if (__heap[i] == val) {
229  eraseByPos(i);
230  break;
231  }
232  }
233 
234  // removes the top of the heap (but does not return it)
235  template < typename Val, typename Cmp, typename Alloc >
237  // if the heap is empty, do nothing
238  if (!__nb_elements) return;
239  eraseByPos(0);
240  }
241 
242  // removes the top element from the heap and return it
243  template < typename Val, typename Cmp, typename Alloc >
245  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
246 
247  Val v = __heap[0];
248  eraseByPos(0);
249  return v;
250  }
251 
252  // after inserting an element at the end of the heap, restore heap property
253  template < typename Val, typename Cmp, typename Alloc >
255  // get the element at the end of the heap
256  Size i = __nb_elements - 1;
257  Val v = std::move(__heap[i]);
258 
259  // restore the heap property
260  for (Size j = (i - 1) >> 1; i && __cmp(v, __heap[j]); i = j, j = (j - 1) >> 1)
261  __heap[i] = std::move(__heap[j]);
262 
263  __heap[i] = std::move(v);
264 
265  return i;
266  }
267 
268  // inserts a new (a copy) element in the heap
269  template < typename Val, typename Cmp, typename Alloc >
270  INLINE Size Heap< Val, Cmp, Alloc >::insert(const Val& val) {
271  // create a new element at the end of the heap
272  __heap.push_back(val);
273  ++__nb_elements;
274  return __restoreHeap();
275  }
276 
277  // inserts a new (a copy) element in the heap
278  template < typename Val, typename Cmp, typename Alloc >
280  // create a new element at the end of the heap
281  __heap.push_back(std::move(val));
282  ++__nb_elements;
283  return __restoreHeap();
284  }
285 
286  // emplace a new element in the heap
287  template < typename Val, typename Cmp, typename Alloc >
288  template < typename... Args >
290  // create a new element at the end of the heap
291  __heap.emplace_back(std::forward< Args >(args)...);
292  ++__nb_elements;
293  return __restoreHeap();
294  }
295 
296  // indicates whether the heap is empty
297  template < typename Val, typename Cmp, typename Alloc >
298  INLINE bool Heap< Val, Cmp, Alloc >::empty() const noexcept {
299  return (__nb_elements == 0);
300  }
301 
302  // indicates whether the heap contains a given value
303  template < typename Val, typename Cmp, typename Alloc >
304  INLINE bool Heap< Val, Cmp, Alloc >::contains(const Val& val) const {
305  for (Size i = 0; i < __nb_elements; ++i)
306  if (__heap[i] == val) return true;
307 
308  return false;
309  }
310 
311  // returns the element at index elt from the heap
312  template < typename Val, typename Cmp, typename Alloc >
313  INLINE const Val& Heap< Val, Cmp, Alloc >::operator[](Size index) const {
314  // check if the element exists
315  if (index >= __nb_elements) {
316  GUM_ERROR(NotFound, "not enough elements in the heap");
317  }
318 
319  return __heap[index];
320  }
321 
322  // displays the content of the heap
323  template < typename Val, typename Cmp, typename Alloc >
324  std::string Heap< Val, Cmp, Alloc >::toString() const {
325  bool deja = false;
326  std::stringstream stream;
327  stream << "[";
328 
329  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
330  if (deja) stream << " , ";
331 
332  stream << __heap[i];
333  }
334 
335  stream << "]";
336 
337  return stream.str();
338  }
339 
340  // A \c << operator for Heap
341  template < typename Val, typename Cmp, typename Alloc >
342  INLINE std::ostream& operator<<(std::ostream& stream,
343  const Heap< Val, Cmp, Alloc >& heap) {
344  stream << heap.toString();
345  return stream;
346  }
347 
348 } /* namespace gum */
bool contains(const Val &) const
Indicates whether the heap contains a given value.
Definition: heap_tpl.h:304
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
bool empty() const noexcept
Indicates whether the heap is empty.
Definition: heap_tpl.h:298
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
const Val & operator[](Size index_elt) const
Returns the element at index index_elt from the heap.
Definition: heap_tpl.h:313
Val pop()
Removes the top element from the heap and return it.
Definition: heap_tpl.h:244
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Size emplace(Args &&... args)
Emplace a new element in the heap and returns its index.
Definition: heap_tpl.h:289
~Heap()
Class destructor.
Definition: heap_tpl.h:92
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:586
Cmp __cmp
Comparison function.
Definition: heap.h:380
void erase(const Val &val)
Removes a given element from the heap (but does not return it).
Definition: heap_tpl.h:225
std::string toString() const
Definition: heap_tpl.h:324
Size size() const noexcept
Returns the number of elements in the heap.
Definition: heap_tpl.h:179
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
Size __restoreHeap()
After inserting an element at the end of the heap, restore heap property.
Definition: heap_tpl.h:254
Size insert(const Val &val)
inserts a new element (actually a copy) in the heap and returns its index
Definition: heap_tpl.h:270
void eraseTop()
Removes the top of the heap (but does not return it).
Definition: heap_tpl.h:236
Heap< Val, Cmp, Alloc > & operator=(const Heap< Val, Cmp, Alloc > &from)
Copy operator.
Definition: heap_tpl.h:100
Size capacity() const noexcept
Returns the size of the internal structure storing the heap.
Definition: heap_tpl.h:185
Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which el...
Definition: heap.h:48
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
void resize(Size new_size)
Changes the size of the the internal structure storing the heap.
Definition: heap_tpl.h:191
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:197
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
const Val & top() const
Returns the element at the top of the heap.
Definition: heap_tpl.h:171