aGrUM  0.13.2
heap.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  ***************************************************************************/
28 #ifndef GUM_HEAP_H
29 #define GUM_HEAP_H
30 
31 #include <functional>
32 #include <initializer_list>
33 #include <utility>
34 #include <vector>
35 
36 #include <agrum/agrum.h>
37 
38 namespace gum {
39 
40 #define GUM_HEAP_DEFAULT_CAPACITY 10
41 
42  // templates provided by this file
43 
44  template < typename Val, typename Cmp, typename Alloc >
45  class Heap;
46  template < typename Val, typename Cmp, typename Alloc >
47  std::ostream& operator<<(std::ostream&, const Heap< Val, Cmp, Alloc >&);
48 
49  // ===========================================================================
50  // === SIMPLE HEAP DATA STRUCTURE ===
51  // ===========================================================================
52 
118  template < typename Val,
119  typename Cmp = std::less< Val >,
120  typename Alloc = std::allocator< Val > >
121  class Heap {
122  public:
125  using value_type = Val;
126  using reference = Val&;
127  using const_reference = const Val&;
128  using pointer = Val*;
129  using const_pointer = const Val*;
130  using size_type = std::size_t;
131  using difference_type = std::ptrdiff_t;
132  using allocator_type = Alloc;
134 
135  // ============================================================================
137  // ============================================================================
139 
148  explicit Heap(Cmp compare = Cmp(), Size capacity = GUM_HEAP_DEFAULT_CAPACITY);
149 
154  explicit Heap(std::initializer_list< Val > list);
155 
160  Heap(const Heap< Val, Cmp, Alloc >& from);
161 
167  template < typename OtherAlloc >
168  Heap(const Heap< Val, Cmp, OtherAlloc >& from);
169 
174  Heap(Heap< Val, Cmp, Alloc >&& from) noexcept;
175 
179  ~Heap();
180 
182  // ============================================================================
184  // ============================================================================
186 
197  Heap< Val, Cmp, Alloc >& operator=(const Heap< Val, Cmp, Alloc >& from);
198 
210  template < typename OtherAlloc >
211  Heap< Val, Cmp, Alloc >& operator=(const Heap< Val, Cmp, OtherAlloc >& from);
212 
223  Heap< Val, Cmp, Alloc >& operator=(Heap< Val, Cmp, Alloc >&& from) noexcept;
224 
233  const Val& operator[](Size index_elt) const;
234 
236  // ============================================================================
238  // ============================================================================
240 
246  const Val& top() const;
247 
253  Val pop();
254 
261  void eraseTop();
262 
280  void eraseByPos(Size index);
281 
291  void erase(const Val& val);
292 
300  Size insert(const Val& val);
301 
309  Size insert(Val&& val);
310 
318  template < typename... Args >
319  Size emplace(Args&&... args);
320 
325  Size size() const noexcept;
326 
331  bool empty() const noexcept;
332 
337  bool contains(const Val&) const;
338 
343  std::string toString() const;
344 
346  // ============================================================================
348  // ============================================================================
350 
355  Size capacity() const noexcept;
356 
365  void resize(Size new_size);
366 
368 
369  private:
371  std::vector< Val, Alloc > __heap;
372 
375 
377  Cmp __cmp;
378 
381  };
382 
383 } /* namespace gum */
384 
385 
386 extern template class gum::Heap< int >;
387 extern template class gum::Heap< long >;
388 extern template class gum::Heap< float >;
389 extern template class gum::Heap< double >;
390 
391 
392 // always include the implementation of the templates
393 #include <agrum/core/heap_tpl.h>
394 
395 #endif /* GUM_HEAP_H */
bool contains(const Val &) const
Indicates whether the heap contains a given value.
Definition: heap_tpl.h:301
Val & reference
Types for STL compliance.
Definition: heap.h:126
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
#define GUM_HEAP_DEFAULT_CAPACITY
Definition: heap.h:40
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: heap.h:131
Val pop()
Removes the top element from the heap and return it.
Definition: heap_tpl.h:241
STL namespace.
std::size_t size_type
Types for STL compliance.
Definition: heap.h:130
const Val & const_reference
Types for STL compliance.
Definition: heap.h:127
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
template implementations of heaps
std::string toString() const
Definition: heap_tpl.h:321
const Val * const_pointer
Types for STL compliance.
Definition: heap.h:129
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
Val * pointer
Types for STL compliance.
Definition: heap.h:128
Size __restoreHeap()
After inserting an element at the end of the heap, restore heap property.
Definition: heap_tpl.h:251
Val value_type
Types for STL compliance.
Definition: heap.h:125
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
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
Alloc allocator_type
Types for STL compliance.
Definition: heap.h:132