aGrUM  0.13.2
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 45 of file heap.h.

Member Typedef Documentation

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 132 of file heap.h.

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 129 of file heap.h.

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 127 of file heap.h.

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 131 of file heap.h.

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 128 of file heap.h.

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 126 of file heap.h.

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 130 of file heap.h.

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 125 of file heap.h.

Constructor & Destructor Documentation

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 36 of file heap_tpl.h.

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

36  : __cmp(compare) {
37  __heap.reserve(capacity);
38 
39  // for debugging purposes
40  GUM_CONSTRUCTOR(Heap);
41  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
Size capacity() const noexcept
Returns the size of the internal structure storing the heap.
Definition: heap_tpl.h:182
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 45 of file heap_tpl.h.

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

45  {
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  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
Size insert(const Val &val)
inserts a new element (actually a copy) in the heap and returns its index
Definition: heap_tpl.h:267

+ Here is the call graph for this function:

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 57 of file heap_tpl.h.

57  :
58  __heap(from.__heap), __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
59  // for debugging purposes
60  GUM_CONS_CPY(Heap);
61  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
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 66 of file heap_tpl.h.

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

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

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

Class destructor.

Definition at line 89 of file heap_tpl.h.

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

89  {
90  // for debugging purposes
91  GUM_DESTRUCTOR(Heap);
92  }
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36

+ Here is the call graph for this function:

Member Function Documentation

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 251 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().

251  {
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  }
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
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371

+ Here is the caller graph for this function:

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 182 of file heap_tpl.h.

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

182  {
183  return Size(__heap.size());
184  }
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
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 301 of file heap_tpl.h.

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

301  {
302  for (Size i = 0; i < __nb_elements; ++i)
303  if (__heap[i] == val) return true;
304 
305  return false;
306  }
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
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
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 286 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().

286  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
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

+ Here is the call graph for this function:

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 295 of file heap_tpl.h.

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

295  {
296  return (__nb_elements == 0);
297  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
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 222 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().

222  {
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  }
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
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:194

+ Here is the call graph for this function:

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 194 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().

194  {
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  }
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
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371

+ Here is the caller graph for this function:

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 233 of file heap_tpl.h.

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

233  {
234  // if the heap is empty, do nothing
235  if (!__nb_elements) return;
236  eraseByPos(0);
237  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
void eraseByPos(Size index)
Removes the element positioned at "index" from the heap.
Definition: heap_tpl.h:194

+ Here is the call graph for this function:

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 267 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().

267  {
268  // create a new element at the end of the heap
269  __heap.push_back(val);
270  ++__nb_elements;
271  return __restoreHeap();
272  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
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

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

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 276 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().

276  {
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  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
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

+ Here is the call graph for this function:

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 97 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().

97  {
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;
111  __nb_elements = from.__nb_elements;
112 
113  // for debugging purposes
114  GUM_OP_CPY(Heap);
115  }
116 
117  return *this;
118  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371

+ Here is the caller graph for this function:

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 124 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=().

124  {
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;
143  __nb_elements = from.__nb_elements;
144 
145  // for debugging purposes
146  GUM_OP_CPY(Heap);
147  }
148 
149  return *this;
150  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
Heap(Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
Basic constructor: creates an empty heap.
Definition: heap_tpl.h:36
Cmp __cmp
Comparison function.
Definition: heap.h:377
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371

+ Here is the call graph for this function:

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 155 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.

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

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

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

241  {
242  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
243 
244  Val v = __heap[0];
245  eraseByPos(0);
246  return v;
247  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
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

+ Here is the call graph for this function:

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 188 of file heap_tpl.h.

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

188  {
189  if (new_size > __nb_elements) __heap.reserve(new_size);
190  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
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 176 of file heap_tpl.h.

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

176  {
177  return __nb_elements;
178  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
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 168 of file heap_tpl.h.

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

168  {
169  if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }
170 
171  return __heap[0];
172  }
Size __nb_elements
The number of elements in the heap.
Definition: heap.h:374
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
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 321 of file heap_tpl.h.

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

Referenced by gum::operator<<().

321  {
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  }
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
std::vector< Val, Alloc > __heap
An array storing all the elements of the heap.
Definition: heap.h:371

+ Here is the caller graph for this function:

Member Data Documentation

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

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