aGrUM  0.13.2
heap_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
26 #include <sstream>
27 #include <string>
28 
29 // to ease IDE parser
30 #include <agrum/core/heap.h>
31 
32 namespace gum {
33 
34  // basic constructor. Creates an empty heap
35  template < typename Val, typename Cmp, typename Alloc >
36  Heap< Val, Cmp, Alloc >::Heap(Cmp compare, Size capacity) : __cmp(compare) {
37  __heap.reserve(capacity);
38 
39  // for debugging purposes
40  GUM_CONSTRUCTOR(Heap);
41  }
42 
43  // initializer list constructor
44  template < typename Val, typename Cmp, typename Alloc >
45  Heap< Val, Cmp, Alloc >::Heap(std::initializer_list< Val > list) {
46  __heap.reserve(list.size());
47  for (const auto& elt : list) {
48  insert(elt);
49  }
50 
51  // for debugging purposes
52  GUM_CONSTRUCTOR(Heap);
53  }
54 
55  // copy constructor
56  template < typename Val, typename Cmp, typename Alloc >
58  __heap(from.__heap), __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
59  // for debugging purposes
60  GUM_CONS_CPY(Heap);
61  }
62 
63  // generalized copy constructor
64  template < typename Val, typename Cmp, typename Alloc >
65  template < typename OtherAlloc >
67  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
68  __heap.reserve(__nb_elements);
69 
70  // copy the elements of from.__heap
71  for (unsigned i = 0; i < __nb_elements; ++i)
72  __heap.push_back(from.__heap[i]);
73 
74  // for debugging purposes
75  GUM_CONS_CPY(Heap);
76  }
77 
78  // move constructor
79  template < typename Val, typename Cmp, typename Alloc >
81  __heap(std::move(from.__heap)), __nb_elements(std::move(from.__nb_elements)),
82  __cmp(std::move(from.__cmp)) {
83  // for debugging purposes
84  GUM_CONS_MOV(Heap);
85  }
86 
87  // destructor
88  template < typename Val, typename Cmp, typename Alloc >
90  // for debugging purposes
91  GUM_DESTRUCTOR(Heap);
92  }
93 
94  // copy operator
95  template < typename Val, typename Cmp, typename Alloc >
98  // avoid self assignment
99  if (this != &from) {
100  try {
101  __heap = from.__heap;
102  } catch (...) {
103  __heap.clear();
104  __nb_elements = 0;
105 
106  throw;
107  }
108 
109  // set the comparison function
110  __cmp = from.__cmp;
112 
113  // for debugging purposes
114  GUM_OP_CPY(Heap);
115  }
116 
117  return *this;
118  }
119 
120  // generalized copy operator
121  template < typename Val, typename Cmp, typename Alloc >
122  template < typename OtherAlloc >
125  // avoid self assignment
126  if (this != &from) {
127  try {
128  __heap.clear();
129 
130  if (__heap.capacity() < from.__nb_elements)
131  __heap.reserve(from.__nb_elements);
132 
133  for (unsigned int i = 0; i < from.__nb_elements; ++i) {
134  __heap.push_back(from.__heap[i]);
135  }
136  } catch (...) {
137  __heap.clear();
138  __nb_elements = 0;
139  throw;
140  }
141 
142  __cmp = from.__cmp;
144 
145  // for debugging purposes
146  GUM_OP_CPY(Heap);
147  }
148 
149  return *this;
150  }
151 
152  // move operator
153  template < typename Val, typename Cmp, typename Alloc >
156  // avoid self assignment
157  if (this != &from) {
158  __heap = std::move(from.__heap);
159  __nb_elements = std::move(from.__nb_elements);
160  __cmp = std::move(from.__cmp);
161  }
162 
163  return *this;
164  }
165 
166  // returns the element at the top of the heap
167  template < typename Val, typename Cmp, typename Alloc >
168  INLINE const Val& Heap< Val, Cmp, Alloc >::top() const {
169  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
170 
171  return __heap[0];
172  }
173 
174  // returns the number of elements in the heap
175  template < typename Val, typename Cmp, typename Alloc >
176  INLINE Size Heap< Val, Cmp, Alloc >::size() const noexcept {
177  return __nb_elements;
178  }
179 
180  // return the size of the array storing the heap
181  template < typename Val, typename Cmp, typename Alloc >
182  INLINE Size Heap< Val, Cmp, Alloc >::capacity() const noexcept {
183  return Size(__heap.size());
184  }
185 
186  // changes the size of the array storing the heap
187  template < typename Val, typename Cmp, typename Alloc >
188  INLINE void Heap< Val, Cmp, Alloc >::resize(Size new_size) {
189  if (new_size > __nb_elements) __heap.reserve(new_size);
190  }
191 
192  // removes the element at position 'index' from the heap
193  template < typename Val, typename Cmp, typename Alloc >
195  if (index >= __nb_elements) return;
196 
197  // remove the element and put the last element in its place
198  Val last = std::move(__heap[__nb_elements - 1]);
199  __heap.pop_back();
200  --__nb_elements;
201 
202  if (!__nb_elements || (index == __nb_elements)) return;
203 
204  // restore the heap property
205  Size i = index;
206 
207  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
208  // let j be the max child
209  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1], __heap[j])) ++j;
210 
211  // if "last" is smaller than __heap[j], "last" must be stored at index i
212  if (__cmp(last, __heap[j])) break;
213 
214  __heap[i] = std::move(__heap[j]);
215  }
216 
217  __heap[i] = std::move(last);
218  }
219 
220  // removes a given element from the heap (but does not return it)
221  template < typename Val, typename Cmp, typename Alloc >
222  INLINE void Heap< Val, Cmp, Alloc >::erase(const Val& val) {
223  // find val in the heap
224  for (Size i = 0; i < __nb_elements; ++i)
225  if (__heap[i] == val) {
226  eraseByPos(i);
227  break;
228  }
229  }
230 
231  // removes the top of the heap (but does not return it)
232  template < typename Val, typename Cmp, typename Alloc >
234  // if the heap is empty, do nothing
235  if (!__nb_elements) return;
236  eraseByPos(0);
237  }
238 
239  // removes the top element from the heap and return it
240  template < typename Val, typename Cmp, typename Alloc >
242  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
243 
244  Val v = __heap[0];
245  eraseByPos(0);
246  return v;
247  }
248 
249  // after inserting an element at the end of the heap, restore heap property
250  template < typename Val, typename Cmp, typename Alloc >
252  // get the element at the end of the heap
253  Size i = __nb_elements - 1;
254  Val v = std::move(__heap[i]);
255 
256  // restore the heap property
257  for (Size j = (i - 1) >> 1; i && __cmp(v, __heap[j]); i = j, j = (j - 1) >> 1)
258  __heap[i] = std::move(__heap[j]);
259 
260  __heap[i] = std::move(v);
261 
262  return i;
263  }
264 
265  // inserts a new (a copy) element in the heap
266  template < typename Val, typename Cmp, typename Alloc >
267  INLINE Size Heap< Val, Cmp, Alloc >::insert(const Val& val) {
268  // create a new element at the end of the heap
269  __heap.push_back(val);
270  ++__nb_elements;
271  return __restoreHeap();
272  }
273 
274  // inserts a new (a copy) element in the heap
275  template < typename Val, typename Cmp, typename Alloc >
277  // create a new element at the end of the heap
278  __heap.push_back(std::move(val));
279  ++__nb_elements;
280  return __restoreHeap();
281  }
282 
283  // emplace a new element in the heap
284  template < typename Val, typename Cmp, typename Alloc >
285  template < typename... Args >
287  // create a new element at the end of the heap
288  __heap.emplace_back(std::forward< Args >(args)...);
289  ++__nb_elements;
290  return __restoreHeap();
291  }
292 
293  // indicates whether the heap is empty
294  template < typename Val, typename Cmp, typename Alloc >
295  INLINE bool Heap< Val, Cmp, Alloc >::empty() const noexcept {
296  return (__nb_elements == 0);
297  }
298 
299  // indicates whether the heap contains a given value
300  template < typename Val, typename Cmp, typename Alloc >
301  INLINE bool Heap< Val, Cmp, Alloc >::contains(const Val& val) const {
302  for (Size i = 0; i < __nb_elements; ++i)
303  if (__heap[i] == val) return true;
304 
305  return false;
306  }
307 
308  // returns the element at index elt from the heap
309  template < typename Val, typename Cmp, typename Alloc >
310  INLINE const Val& Heap< Val, Cmp, Alloc >::operator[](Size index) const {
311  // check if the element exists
312  if (index >= __nb_elements) {
313  GUM_ERROR(NotFound, "not enough elements in the heap");
314  }
315 
316  return __heap[index];
317  }
318 
319  // displays the content of the heap
320  template < typename Val, typename Cmp, typename Alloc >
321  std::string Heap< Val, Cmp, Alloc >::toString() const {
322  bool deja = false;
323  std::stringstream stream;
324  stream << "[";
325 
326  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
327  if (deja) stream << " , ";
328 
329  stream << __heap[i];
330  }
331 
332  stream << "]";
333 
334  return stream.str();
335  }
336 
337  // A \c << operator for Heap
338  template < typename Val, typename Cmp, typename Alloc >
339  INLINE std::ostream& operator<<(std::ostream& stream,
340  const Heap< Val, Cmp, Alloc >& heap) {
341  stream << heap.toString();
342  return stream;
343  }
344 
345 } /* namespace gum */
bool contains(const Val &) const
Indicates whether the heap contains a given value.
Definition: heap_tpl.h:301
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
bool empty() const noexcept
Indicates whether the heap is empty.
Definition: heap_tpl.h:295
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
const Val & operator[](Size index_elt) const
Returns the element at index index_elt from the heap.
Definition: heap_tpl.h:310
Val pop()
Removes the top element from the heap and return it.
Definition: heap_tpl.h:241
STL namespace.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
Heaps definition.
~Heap()
Class destructor.
Definition: heap_tpl.h:89
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:573
std::string toString() const
Definition: heap_tpl.h:321
Size emplace(Args &&...args)
Emplace a new element in the heap and returns its index.
Definition: heap_tpl.h:286
Cmp __cmp
Comparison function.
Definition: heap.h:377
void erase(const Val &val)
Removes a given element from the heap (but does not return it).
Definition: heap_tpl.h:222
Size size() const noexcept
Returns the number of elements in the heap.
Definition: heap_tpl.h:176
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
Size __restoreHeap()
After inserting an element at the end of the heap, restore heap property.
Definition: heap_tpl.h:251
Size insert(const Val &val)
inserts a new element (actually a copy) in the heap and returns its index
Definition: heap_tpl.h:267
void eraseTop()
Removes the top of the heap (but does not return it).
Definition: heap_tpl.h:233
Heap< Val, Cmp, Alloc > & operator=(const Heap< Val, Cmp, Alloc > &from)
Copy operator.
Definition: heap_tpl.h:97
Size capacity() const noexcept
Returns the size of the internal structure storing the heap.
Definition: heap_tpl.h:182
const Val & top() const
Returns the element at the top of the heap.
Definition: heap_tpl.h:168
Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which el...
Definition: heap.h:45
void resize(Size new_size)
Changes the size of the the internal structure storing the heap.
Definition: heap_tpl.h:188
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:194
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66