aGrUM  0.14.1
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 
198 
210  template < typename OtherAlloc >
212 
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 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
387 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
388 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
389 extern template class gum::Heap< int >;
390 # endif
391 # endif
392 #endif
393 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
394 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
395 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
396 extern template class gum::Heap< long >;
397 # endif
398 # endif
399 #endif
400 
401 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
402 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
403 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
404 extern template class gum::Heap< double >;
405 # endif
406 # endif
407 #endif
408 
409 
410 // always include the implementation of the templates
411 #include <agrum/core/heap_tpl.h>
412 
413 #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
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
const Val & operator[](Size index_elt) const
Returns the element at index index_elt from the heap.
Definition: heap_tpl.h:310
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
Size emplace(Args &&... args)
Emplace a new element in the heap and returns its index.
Definition: heap_tpl.h:286
template implementations of heaps
~Heap()
Class destructor.
Definition: heap_tpl.h:89
const Val * const_pointer
Types for STL compliance.
Definition: heap.h:129
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
std::string toString() const
Definition: heap_tpl.h:321
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
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
Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which el...
Definition: heap.h:45
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.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
const Val & top() const
Returns the element at the top of the heap.
Definition: heap_tpl.h:168