aGrUM  0.15.0
gum::Heap< Val, Cmp, Alloc > Class Template Reference

Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering. More...

#include <agrum/core/heap.h>

Public Member Functions

Constructors / Destructors
 Heap (Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
 Basic constructor: creates an empty heap. More...
 
 Heap (std::initializer_list< Val > list)
 Initializer list constructor. More...
 
 Heap (const Heap< Val, Cmp, Alloc > &from)
 Copy constructor. More...
 
template<typename OtherAlloc >
 Heap (const Heap< Val, Cmp, OtherAlloc > &from)
 Generalized copy constructor. More...
 
 Heap (Heap< Val, Cmp, Alloc > &&from) noexcept
 Move constructor. More...
 
 ~Heap ()
 Class destructor. More...
 
Operators
Heap< Val, Cmp, Alloc > & operator= (const Heap< Val, Cmp, Alloc > &from)
 Copy operator. More...
 
template<typename OtherAlloc >
Heap< Val, Cmp, Alloc > & operator= (const Heap< Val, Cmp, OtherAlloc > &from)
 Generalized copy operator. More...
 
Heap< Val, Cmp, Alloc > & operator= (Heap< Val, Cmp, Alloc > &&from) noexcept
 Move operator. More...
 
const Val & operator[] (Size index_elt) const
 Returns the element at index index_elt from the heap. More...
 
Accessors / Modifiers
const Val & top () const
 Returns the element at the top of the heap. More...
 
Val pop ()
 Removes the top element from the heap and return it. More...
 
void eraseTop ()
 Removes the top of the heap (but does not return it). More...
 
void eraseByPos (Size index)
 Removes the element positioned at "index" from the heap. More...
 
void erase (const Val &val)
 Removes a given element from the heap (but does not return it). More...
 
Size insert (const Val &val)
 inserts a new element (actually a copy) in the heap and returns its index More...
 
Size insert (Val &&val)
 Inserts a new element (by moving it) in the heap and returns its index. More...
 
template<typename... Args>
Size emplace (Args &&... args)
 Emplace a new element in the heap and returns its index. More...
 
Size size () const noexcept
 Returns the number of elements in the heap. More...
 
bool empty () const noexcept
 Indicates whether the heap is empty. More...
 
bool contains (const Val &) const
 Indicates whether the heap contains a given value. More...
 
std::string toString () const
 
Fine tuning
Size capacity () const noexcept
 Returns the size of the internal structure storing the heap. More...
 
void resize (Size new_size)
 Changes the size of the the internal structure storing the heap. More...
 

Public Types

using value_type = Val
 Types for STL compliance. More...
 
using reference = Val &
 Types for STL compliance. More...
 
using const_reference = const Val &
 Types for STL compliance. More...
 
using pointer = Val *
 Types for STL compliance. More...
 
using const_pointer = const Val *
 Types for STL compliance. More...
 
using size_type = std::size_t
 Types for STL compliance. More...
 
using difference_type = std::ptrdiff_t
 Types for STL compliance. More...
 
using allocator_type = Alloc
 Types for STL compliance. More...
 

Detailed Description

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
class gum::Heap< Val, Cmp, Alloc >

Heap data structure

This structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering.

Given this ordering, we do have access in O(1) to the "smallest" element contained by the structure. Insertions and deletions of elements are processed in O(ln n), where n is the number of elements in the heap. In addition to the classical pop, top and push functions, Heap provide direct accessors to the elements in the heap (see operator[]). However, these can only be accessed in read-only mode.

Usage example:
// create a heap of integers, the top element is the smallest element
Heap<int> heap1;
// create a heap of floats, the top element is the greatest
Heap<float> heap2 (std::greater<float>());
// insert elements into the heap
heap1.insert (8);
heap1.insert (10);
heap1.insert (2);
heap1.insert (23);
heap1.insert (24);
heap1.insert (10);
heap1.insert (10);
// copy a heap into another
Heap<int> heap2 = heap1;
// get the number of elements of the heap
std::cerr << heap2.size() << std::endl;
// get the top element but do not remove it
std::cerr << heap2.top() << std::endl;
// get and remove the top element of the heap
std::cerr << heap2.pop() << std::endl;
// remove the top element but do not return it (faster than above)
heap2.eraseTop();
// erase in heap1 value 8
heap1.eraseByVal (8);
// erase element at position 3 (see function erase for the
// meaning of position 3)
heap1.erase (3);
// get the element at position 3
heap1[3];
// check whether element 24 belongs to the heap
heap1.contains (24);
Template Parameters
ValThe gum::Heap values type.
CmpThe comperator used to sort elements in the gum::Heap.
AllocThe allocator of elements stored in the gum::Heap.

Definition at line 48 of file heap.h.

Member Typedef Documentation

◆ allocator_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 135 of file heap.h.

◆ const_pointer

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::const_pointer = const Val*

Types for STL compliance.

Definition at line 132 of file heap.h.

◆ const_reference

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::const_reference = const Val&

Types for STL compliance.

Definition at line 130 of file heap.h.

◆ difference_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 134 of file heap.h.

◆ pointer

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::pointer = Val*

Types for STL compliance.

Definition at line 131 of file heap.h.

◆ reference

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::reference = Val&

Types for STL compliance.

Definition at line 129 of file heap.h.

◆ size_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::size_type = std::size_t

Types for STL compliance.

Definition at line 133 of file heap.h.

◆ value_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
using gum::Heap< Val, Cmp, Alloc >::value_type = Val

Types for STL compliance.

Definition at line 128 of file heap.h.

Constructor & Destructor Documentation

◆ Heap() [1/5]

template<typename Val , typename Cmp , typename Alloc >
gum::Heap< Val, Cmp, Alloc >::Heap ( Cmp  compare = Cmp(),
Size  capacity = GUM_HEAP_DEFAULT_CAPACITY 
)
explicit

Basic constructor: creates an empty heap.

Parameters
comparea function taking two elements in argument, say e1 and e2, and returning a Boolean indicating wether e1 < e2, i.e., whether e1 should be nearer than e2 to the top of the heap.
capacitythe size of the internal data structures containing the elements (could be for instance vectors or hashtables).

Definition at line 39 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap.

39  : __cmp(compare) {
40  __heap.reserve(capacity);
41 
42  // for debugging purposes
43  GUM_CONSTRUCTOR(Heap);
44  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
Size capacity() const noexcept
Returns the size of the internal structure storing the heap.
Definition: heap_tpl.h:185

◆ Heap() [2/5]

template<typename Val , typename Cmp , typename Alloc >
gum::Heap< Val, Cmp, Alloc >::Heap ( std::initializer_list< Val >  list)
explicit

Initializer list constructor.

Parameters
listThe initializer list.

Definition at line 48 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::insert().

48  {
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  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
Size insert(const Val &val)
inserts a new element (actually a copy) in the heap and returns its index
Definition: heap_tpl.h:270
+ Here is the call graph for this function:

◆ Heap() [3/5]

template<typename Val , typename Cmp , typename Alloc >
gum::Heap< Val, Cmp, Alloc >::Heap ( const Heap< Val, Cmp, Alloc > &  from)

Copy constructor.

Parameters
fromThe gum::Heap to copy.

Definition at line 60 of file heap_tpl.h.

60  :
61  __heap(from.__heap), __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
62  // for debugging purposes
63  GUM_CONS_CPY(Heap);
64  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374

◆ Heap() [4/5]

template<typename Val , typename Cmp , typename Alloc >
template<typename OtherAlloc >
gum::Heap< Val, Cmp, Alloc >::Heap ( const Heap< Val, Cmp, OtherAlloc > &  from)

Generalized copy constructor.

Template Parameters
OtherAllocThe other gum::Heap allocator.
Parameters
fromThe gum::Heap to copy.

Definition at line 69 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

69  :
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374

◆ Heap() [5/5]

template<typename Val , typename Cmp , typename Alloc >
gum::Heap< Val, Cmp, Alloc >::Heap ( Heap< Val, Cmp, Alloc > &&  from)
noexcept

Move constructor.

Parameters
fromThe gum::Heap to move.

Definition at line 83 of file heap_tpl.h.

83  :
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374

◆ ~Heap()

template<typename Val , typename Cmp , typename Alloc >
gum::Heap< Val, Cmp, Alloc >::~Heap ( )

Class destructor.

Definition at line 92 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::operator=().

92  {
93  // for debugging purposes
94  GUM_DESTRUCTOR(Heap);
95  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
+ Here is the call graph for this function:

Member Function Documentation

◆ __restoreHeap()

template<typename Val , typename Cmp , typename Alloc >
Size gum::Heap< Val, Cmp, Alloc >::__restoreHeap ( )
private

After inserting an element at the end of the heap, restore heap property.

Definition at line 254 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::emplace(), and gum::Heap< Val, Cmp, Alloc >::insert().

254  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
+ Here is the caller graph for this function:

◆ capacity()

template<typename Val , typename Cmp , typename Alloc >
INLINE Size gum::Heap< Val, Cmp, Alloc >::capacity ( ) const
noexcept

Returns the size of the internal structure storing the heap.

Returns
Returns the size of the internal structure storing the heap.

Definition at line 185 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap.

185  {
186  return Size(__heap.size());
187  }
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48

◆ contains()

template<typename Val , typename Cmp , typename Alloc >
INLINE bool gum::Heap< Val, Cmp, Alloc >::contains ( const Val &  val) const

Indicates whether the heap contains a given value.

Returns
Indicates whether the heap contains a given value.

Definition at line 304 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

304  {
305  for (Size i = 0; i < __nb_elements; ++i)
306  if (__heap[i] == val) return true;
307 
308  return false;
309  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48

◆ emplace()

template<typename Val , typename Cmp , typename Alloc >
template<typename... Args>
Size gum::Heap< Val, Cmp, Alloc >::emplace ( Args &&...  args)

Emplace a new element in the heap and returns its index.

Template Parameters
Argsthe type of the new element to emplace.
Parameters
argsThe new element to emplace.
Returns
The emplaced element position in the gum::Heap.

Definition at line 289 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

289  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
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
+ Here is the call graph for this function:

◆ empty()

template<typename Val , typename Cmp , typename Alloc >
INLINE bool gum::Heap< Val, Cmp, Alloc >::empty ( ) const
noexcept

Indicates whether the heap is empty.

Returns
Indicates whether the heap is empty.

Definition at line 298 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements.

298  {
299  return (__nb_elements == 0);
300  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377

◆ erase()

template<typename Val , typename Cmp , typename Alloc >
INLINE void gum::Heap< Val, Cmp, Alloc >::erase ( const Val &  val)

Removes a given element from the heap (but does not return it).

If the element cannot be found, the function returns without throwing any exception.

Parameters
valThe element we wish to remove. If the heap contains several times this element, then the one with the smallest index is removed.

Definition at line 225 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::eraseByPos().

225  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:197
+ Here is the call graph for this function:

◆ eraseByPos()

template<typename Val , typename Cmp , typename Alloc >
void gum::Heap< Val, Cmp, Alloc >::eraseByPos ( Size  index)

Removes the element positioned at "index" from the heap.

If the element cannot be found, the function returns without throwing any exception.

Parameters
indexrepresents the position of the element to be removed. This is computed as follows: suppose that the heap is a complete binary tree, that is, a binary tree where all levels are completely filled except, maybe, the last one and, in this case, the elements of this level are all to the left of the tree. Then parsing the tree from top to bottom and, for each level, from left to right, and assigning index 0 to the root of the tree and, incrementing the index by 1 each time we jump to another node, we get a unique index for each element. This is precisely what the index passed in argument of the function represents.
indexThe index of the element to remove

Definition at line 197 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::erase(), gum::Heap< Val, Cmp, Alloc >::eraseTop(), and gum::Heap< Val, Cmp, Alloc >::pop().

197  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
+ Here is the caller graph for this function:

◆ eraseTop()

template<typename Val , typename Cmp , typename Alloc >
INLINE void gum::Heap< Val, Cmp, Alloc >::eraseTop ( )

Removes the top of the heap (but does not return it).

If the heap is empty, it does nothing (in particular, it does not throw any exception).

Definition at line 236 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::eraseByPos().

236  {
237  // if the heap is empty, do nothing
238  if (!__nb_elements) return;
239  eraseByPos(0);
240  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:197
+ Here is the call graph for this function:

◆ insert() [1/2]

template<typename Val , typename Cmp , typename Alloc >
INLINE Size gum::Heap< Val, Cmp, Alloc >::insert ( const Val &  val)

inserts a new element (actually a copy) in the heap and returns its index

Parameters
valThe element to insert.
Returns
The inserted element position in the gum::Heap.

Definition at line 270 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

Referenced by gum::Heap< Val, Cmp, Alloc >::Heap().

270  {
271  // create a new element at the end of the heap
272  __heap.push_back(val);
273  ++__nb_elements;
274  return __restoreHeap();
275  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
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
+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ insert() [2/2]

template<typename Val , typename Cmp , typename Alloc >
Size gum::Heap< Val, Cmp, Alloc >::insert ( Val &&  val)

Inserts a new element (by moving it) in the heap and returns its index.

Parameters
valThe element to insert.
Returns
The inserted element position in the gum::Heap.

Definition at line 279 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

279  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
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
+ Here is the call graph for this function:

◆ operator=() [1/3]

template<typename Val , typename Cmp , typename Alloc >
Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator= ( const Heap< Val, Cmp, Alloc > &  from)

Copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters
fromThe gum::Heap to copy.

Definition at line 100 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::operator=(), and gum::Heap< Val, Cmp, Alloc >::~Heap().

100  {
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;
114  __nb_elements = from.__nb_elements;
115 
116  // for debugging purposes
117  GUM_OP_CPY(Heap);
118  }
119 
120  return *this;
121  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
+ Here is the caller graph for this function:

◆ operator=() [2/3]

template<typename Val , typename Cmp , typename Alloc >
template<typename OtherAlloc >
Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator= ( const Heap< Val, Cmp, OtherAlloc > &  from)

Generalized copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Template Parameters
OtherAllocThe other gum::Heap allocator.
Parameters
fromThe gum::Heap to copy.

Definition at line 127 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::operator=().

127  {
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;
146  __nb_elements = from.__nb_elements;
147 
148  // for debugging purposes
149  GUM_OP_CPY(Heap);
150  }
151 
152  return *this;
153  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:39
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
+ Here is the call graph for this function:

◆ operator=() [3/3]

template<typename Val , typename Cmp , typename Alloc >
Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator= ( Heap< Val, Cmp, Alloc > &&  from)
noexcept

Move operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters
fromThe gum::Heap to move.

Definition at line 158 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

158  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
Cmp __cmp
Comparison function.
Definition: heap.h:380
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374

◆ operator[]()

template<typename Val , typename Cmp , typename Alloc >
INLINE const Val & gum::Heap< Val, Cmp, Alloc >::operator[] ( Size  index_elt) const

Returns the element at index index_elt from the heap.

Parameters
index_eltThe index of the element to return.
Returns
Returns the element at index index_elt from the heap.
Exceptions
NotFoundexception is thrown if there is no element at position "index_elt".

Definition at line 313 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and GUM_ERROR.

313  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ pop()

template<typename Val , typename Cmp , typename Alloc >
INLINE Val gum::Heap< Val, Cmp, Alloc >::pop ( )

Removes the top element from the heap and return it.

Returns
Returns the top element from the heap.
Exceptions
NotFoundexception is thrown if the heap is empty.

Definition at line 244 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, gum::Heap< Val, Cmp, Alloc >::eraseByPos(), and GUM_ERROR.

244  {
245  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
246 
247  Val v = __heap[0];
248  eraseByPos(0);
249  return v;
250  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
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
+ Here is the call graph for this function:

◆ resize()

template<typename Val , typename Cmp , typename Alloc >
INLINE void gum::Heap< Val, Cmp, Alloc >::resize ( Size  new_size)

Changes the size of the the internal structure storing the heap.

If the new size does not enable the heap to contain the elements it currently contains, then the resizing does not occur.

Parameters
new_sizeThe gum::Heap new size.

Definition at line 191 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

191  {
192  if (new_size > __nb_elements) __heap.reserve(new_size);
193  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374

◆ size()

template<typename Val , typename Cmp , typename Alloc >
INLINE Size gum::Heap< Val, Cmp, Alloc >::size ( ) const
noexcept

Returns the number of elements in the heap.

Returns
Returns the number of elements in the heap.

Definition at line 179 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements.

179  {
180  return __nb_elements;
181  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377

◆ top()

template<typename Val , typename Cmp , typename Alloc >
INLINE const Val & gum::Heap< Val, Cmp, Alloc >::top ( ) const

Returns the element at the top of the heap.

Returns
Returns the element at the top of the heap.
Exceptions
NotFoundexception is thrown if the heap is empty.

Definition at line 171 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and GUM_ERROR.

171  {
172  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
173 
174  return __heap[0];
175  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ toString()

template<typename Val , typename Cmp , typename Alloc >
std::string gum::Heap< Val, Cmp, Alloc >::toString ( ) const
Returns
Displays the content of the heap.
Returns a std::string representing the content of the heap.

Definition at line 324 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::operator<<().

324  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:374
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
+ Here is the caller graph for this function:

Member Data Documentation

◆ __cmp

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
Cmp gum::Heap< Val, Cmp, Alloc >::__cmp
private

◆ __heap

◆ __nb_elements


The documentation for this class was generated from the following files: