aGrUM  0.15.1
heap.h
Go to the documentation of this file.
1 
31 #ifndef GUM_HEAP_H
32 #define GUM_HEAP_H
33 
34 #include <functional>
35 #include <initializer_list>
36 #include <utility>
37 #include <vector>
38 
39 #include <agrum/agrum.h>
40 
41 namespace gum {
42 
43 #define GUM_HEAP_DEFAULT_CAPACITY 10
44 
45  // templates provided by this file
46 
47  template < typename Val, typename Cmp, typename Alloc >
48  class Heap;
49  template < typename Val, typename Cmp, typename Alloc >
50  std::ostream& operator<<(std::ostream&, const Heap< Val, Cmp, Alloc >&);
51 
52  // ===========================================================================
53  // === SIMPLE HEAP DATA STRUCTURE ===
54  // ===========================================================================
55 
121  template < typename Val,
122  typename Cmp = std::less< Val >,
123  typename Alloc = std::allocator< Val > >
124  class Heap {
125  public:
128  using value_type = Val;
129  using reference = Val&;
130  using const_reference = const Val&;
131  using pointer = Val*;
132  using const_pointer = const Val*;
133  using size_type = std::size_t;
134  using difference_type = std::ptrdiff_t;
135  using allocator_type = Alloc;
137 
138  // ============================================================================
140  // ============================================================================
142 
151  explicit Heap(Cmp compare = Cmp(), Size capacity = GUM_HEAP_DEFAULT_CAPACITY);
152 
157  explicit Heap(std::initializer_list< Val > list);
158 
163  Heap(const Heap< Val, Cmp, Alloc >& from);
164 
170  template < typename OtherAlloc >
171  Heap(const Heap< Val, Cmp, OtherAlloc >& from);
172 
177  Heap(Heap< Val, Cmp, Alloc >&& from) noexcept;
178 
182  ~Heap();
183 
185  // ============================================================================
187  // ============================================================================
189 
201 
213  template < typename OtherAlloc >
215 
227 
236  const Val& operator[](Size index_elt) const;
237 
239  // ============================================================================
241  // ============================================================================
243 
249  const Val& top() const;
250 
256  Val pop();
257 
264  void eraseTop();
265 
283  void eraseByPos(Size index);
284 
294  void erase(const Val& val);
295 
303  Size insert(const Val& val);
304 
312  Size insert(Val&& val);
313 
321  template < typename... Args >
322  Size emplace(Args&&... args);
323 
328  Size size() const noexcept;
329 
334  bool empty() const noexcept;
335 
340  bool contains(const Val&) const;
341 
346  std::string toString() const;
347 
349  // ============================================================================
351  // ============================================================================
353 
358  Size capacity() const noexcept;
359 
368  void resize(Size new_size);
369 
371 
372  private:
374  std::vector< Val, Alloc > __heap;
375 
378 
380  Cmp __cmp;
381 
384  };
385 
386 } /* namespace gum */
387 
388 
389 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
390 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
391 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
392 extern template class gum::Heap< int >;
393 # endif
394 # endif
395 #endif
396 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
397 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
398 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
399 extern template class gum::Heap< long >;
400 # endif
401 # endif
402 #endif
403 
404 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
405 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
406 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
407 extern template class gum::Heap< double >;
408 # endif
409 # endif
410 #endif
411 
412 
413 // always include the implementation of the templates
414 #include <agrum/core/heap_tpl.h>
415 
416 #endif /* GUM_HEAP_H */
bool contains(const Val &) const
Indicates whether the heap contains a given value.
Definition: heap_tpl.h:304
Val & reference
Types for STL compliance.
Definition: heap.h:129
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
#define GUM_HEAP_DEFAULT_CAPACITY
Definition: heap.h:43
const Val & operator[](Size index_elt) const
Returns the element at index index_elt from the heap.
Definition: heap_tpl.h:313
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: heap.h:134
Val pop()
Removes the top element from the heap and return it.
Definition: heap_tpl.h:244
STL namespace.
std::size_t size_type
Types for STL compliance.
Definition: heap.h:133
const Val & const_reference
Types for STL compliance.
Definition: heap.h:130
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
Size emplace(Args &&... args)
Emplace a new element in the heap and returns its index.
Definition: heap_tpl.h:289
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
~Heap()
Class destructor.
Definition: heap_tpl.h:92
const Val * const_pointer
Types for STL compliance.
Definition: heap.h:132
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
Val * pointer
Types for STL compliance.
Definition: heap.h:131
Size __restoreHeap()
After inserting an element at the end of the heap, restore heap property.
Definition: heap_tpl.h:254
Val value_type
Types for STL compliance.
Definition: heap.h:128
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
Alloc allocator_type
Types for STL compliance.
Definition: heap.h:135
const Val & top() const
Returns the element at the top of the heap.
Definition: heap_tpl.h:171