aGrUM  0.15.1
gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc > Class Template Reference

A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowedA priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure. More...

#include <agrum/core/multiPriorityQueue.h>

+ Collaboration diagram for gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >:

Public Member Functions

template<typename... Args>
INLINE Size emplace (Args &&... args)
 
Constructors / Destructors
 MultiPriorityQueue (Cmp compare=Cmp(), Size capacity=GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY)
 Basic constructor. More...
 
 MultiPriorityQueue (std::initializer_list< std::pair< Val, Priority > > list)
 Initializer list constructor. More...
 
 MultiPriorityQueue (const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
 Copy constructor. More...
 
template<typename OtherAlloc >
 MultiPriorityQueue (const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &from)
 generalized copy constructor More...
 
 MultiPriorityQueue (MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&from)
 Move constructor. More...
 
 ~MultiPriorityQueue ()
 Class destructor. More...
 
Operators
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & operator= (const MultiPriorityQueue< Val, Priority, Cmp, Alloc > &from)
 Copy operator. More...
 
template<typename OtherAlloc >
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & operator= (const MultiPriorityQueue< Val, Priority, Cmp, OtherAlloc > &from)
 Generalized copy operator. More...
 
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & operator= (MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&from)
 Move operator. More...
 
const Val & operator[] (Size index_elt) const
 Returns the element at index "index_elt" from the priority queue. More...
 
Accessors / Modifiers
Size size () const noexcept
 Returns the number of elements in the priority queue. More...
 
bool empty () const noexcept
 Indicates whether the priority queue is empty. More...
 
bool contains (const Val &val) const
 Indicates whether the priority queue contains a given value. More...
 
const Val & top () const
 Returns the element at the top of the priority queue. More...
 
const Priority & topPriority () const
 Returns the priority of the top element. More...
 
Val pop ()
 Removes the top element from the priority queue and return it. More...
 
Size insert (const Val &val, const Priority &priority)
 Inserts a new (a copy) element in the priority queue. More...
 
Size insert (Val &&val, Priority &&priority)
 Inserts (by move) a new element in the priority queue. More...
 
template<typename... Args>
Size emplace (Args &&... args)
 Emplace a new element into the priority queue. More...
 
void eraseTop ()
 Removes the top of the priority queue (but does not return it). More...
 
void eraseByPos (Size index)
 Removes the element at position "index" from the priority queue. More...
 
void erase (const Val &val)
 Removes a given element from the priority queue (but does not return it). More...
 
Size setPriorityByPos (Size index, const Priority &new_priority)
 Modifies the priority of the element at position "index" of the queue. More...
 
Size setPriorityByPos (Size index, Priority &&new_priority)
 Modifies the priority of the element at position "index" of the queue. More...
 
void setPriority (const Val &elt, const Priority &new_priority)
 Modifies the priority of each instance of a given element. More...
 
const Priority & priority (const Val &elt) const
 Returns the priority of an instance of the value passed in argument. More...
 
void clear ()
 Removes all the elements from the queue. More...
 
const HashTable< Val, std::vector< Size > > & allValues () const
 Returns a gum::HashTable the keys of which are the values stored in the queue. More...
 
std::string toString () const
 Displays the content of the queue. More...
 
Fine tuning
Size capacity () const noexcept
 Return the size of the internal structure storing the priority queue. More...
 
void resize (Size new_size)
 Changes the size of the internal structure storing the priority queue. More...
 

Public Types

using IndexAlloc = typename Alloc::template rebind< std::pair< Val, std::vector< Size > > >::other
 The allocator for the indices. More...
 
using HeapAlloc = typename Alloc::template rebind< std::pair< Priority, const Val *> >::other
 The allocator for the heap. More...
 
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 difference_type = std::ptrdiff_t
 types for STL compliance More...
 
using allocator_type = Alloc
 types for STL compliance More...
 

Friends

template<typename V , typename P , typename C , typename A >
class MultiPriorityQueue
 Making all MultiPriorityQueue friend with themselves. More...
 

Detailed Description

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
class gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >

A MultiPriorityQueue is a heap in which each element has a mutable priority and duplicates are allowed

A priority queue is quite similar to a heap except that a priority (a score) is assigned to each element in the structure.

The elements are sorted according to a weak order on the scores. The priority of any element can be changed at any moment by the user. The priority queue then restores a heap property accordingly.

Usage example:
// create a priority queue of strings, the priorities of which are
// integers the element at the top of the queue has the smallest priority
MultiPriorityQueue<std::string> queue1;
// insert elements into the queue
queue1.insert (8, "AAA");
queue1.insert (10, "BBB");
queue1.insert (2, "CCC");
queue1.insert (23, "DDD");
queue1.insert (24, "EEE");
queue1.insert (10, "AAA");
// copy the queue
MultiPriorityQueue<std::string> queue2 = queue1;
// initializer list constructor
MultiPriorityQueue<std::string,int>
queue3 { std::pair<std::string,int> ( "aa", 3 ),
std::pair<std::string,int> ( "bb", 2 ) };
// create a priority queue of strings, the priorities of which are
// pairs of ints
MultiPriorityQueue< std::string, std::pair<int,int> > queue3;
// get the top element, then remove it
std::cerr << queue2.top() << std::endl;
queue2.eraseTop();
// get the top element, then remove it
std::cerr << queue2.pop() << std::endl;
// output the content of the queue
std::cerr << queue1 << std::endl;
// change the priority of the element at position 3
Size new_pos=queue1.setPriorityByPos (3,100);
// change the priority of all instances of element "AAA"
queue1.setPriority ("AAA",100);
Template Parameters
ValThe values type stored in the gum::MultiPriorityQueue.
PriorityThe priorities type.
CmpThe priorities comparator.
AllocThe values allocator.

Definition at line 127 of file multiPriorityQueue.h.

Member Typedef Documentation

◆ allocator_type

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

types for STL compliance

Definition at line 141 of file multiPriorityQueue.h.

◆ const_pointer

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

types for STL compliance

Definition at line 139 of file multiPriorityQueue.h.

◆ const_reference

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

types for STL compliance

Definition at line 137 of file multiPriorityQueue.h.

◆ difference_type

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

types for STL compliance

Definition at line 140 of file multiPriorityQueue.h.

◆ HeapAlloc

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::HeapAlloc = typename Alloc::template rebind< std::pair< Priority, const Val* > >::other

The allocator for the heap.

Definition at line 150 of file multiPriorityQueue.h.

◆ IndexAlloc

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
using gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::IndexAlloc = typename Alloc::template rebind< std::pair< Val, std::vector< Size > > >::other

The allocator for the indices.

Definition at line 146 of file multiPriorityQueue.h.

◆ pointer

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

types for STL compliance

Definition at line 138 of file multiPriorityQueue.h.

◆ reference

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

types for STL compliance

Definition at line 136 of file multiPriorityQueue.h.

◆ value_type

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

types for STL compliance

Definition at line 135 of file multiPriorityQueue.h.

Constructor & Destructor Documentation

◆ MultiPriorityQueue() [1/5]

template<typename Val , typename Priority , typename Cmp, typename Alloc >
gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue ( Cmp  compare = Cmp(),
Size  capacity = GUM_MULTIPLE_PRIORITY_QUEUE_DEFAULT_CAPACITY 
)
explicit

Basic constructor.

Creates an empty priority queue.

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 37 of file multiPriorityQueue_tpl.h.

38  :
39  __indices(capacity >> 1, true, false),
40  __cmp(compare) {
41  __heap.reserve(capacity);
42 
43  // for debugging purposes
44  GUM_CONSTRUCTOR(MultiPriorityQueue);
45  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Cmp __cmp
Comparison function.
Size capacity() const noexcept
Return the size of the internal structure storing the priority queue.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ MultiPriorityQueue() [2/5]

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

Initializer list constructor.

The elements of the initializer list are pairs <Val,Priority>. The comparison function is the default one, i.e., std::less<Priority>.

Parameters
listThe initializer list.

Definition at line 49 of file multiPriorityQueue_tpl.h.

50  :
51  __indices(Size(list.size()) / 2, true, false) {
52  // fill the queue
53  __heap.reserve(list.size());
54  for (const auto& elt : list) {
55  insert(elt.first, elt.second);
56  }
57 
58  // for debugging purposes
59  GUM_CONSTRUCTOR(MultiPriorityQueue);
60  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size insert(const Val &val, const Priority &priority)
Inserts a new (a copy) element in the priority queue.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ MultiPriorityQueue() [3/5]

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

Copy constructor.

Parameters
fromThe gum::MultiPriorityQueue to copy.

Definition at line 64 of file multiPriorityQueue_tpl.h.

65  :
66  __heap(from.__heap),
67  __indices(from.__indices), __nb_elements(from.__nb_elements),
68  __cmp(from.__cmp) {
69  // for debugging purposes
70  GUM_CONS_CPY(MultiPriorityQueue);
71 
72  // fill the heap structure
73  for (const auto& val_and_index : __indices) {
74  const Val* val = &(val_and_index.first);
75  const std::vector< Size >& vect = val_and_index.second;
76  for (auto index : vect) {
77  __heap[index].second = val;
78  }
79  }
80  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ MultiPriorityQueue() [4/5]

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

generalized copy constructor

Generalized Copy constructor.

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

Definition at line 85 of file multiPriorityQueue_tpl.h.

86  :
87  __indices(from.__indices),
88  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
89  // for debugging purposes
90  GUM_CONS_CPY(MultiPriorityQueue);
91 
92  // fill the heap structure
93  if (__nb_elements) {
94  __heap.reserve(from.__heap.size());
95  for (const auto& elt : from.__heap) {
96  __heap.push_back(elt);
97  }
98  for (const auto& val_and_index : __indices) {
99  const Val* val = &(val_and_index.first);
100  const std::vector< Size >& vect = val_and_index.second;
101  for (auto index : vect) {
102  __heap[index].second = val;
103  }
104  }
105  }
106  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ MultiPriorityQueue() [5/5]

template<typename Val, typename Priority, typename Cmp, typename Alloc>
gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::MultiPriorityQueue ( MultiPriorityQueue< Val, Priority, Cmp, Alloc > &&  from)

Move constructor.

Parameters
fromThe gum::MultiPriorityQueue to move.

Definition at line 110 of file multiPriorityQueue_tpl.h.

111  :
112  __heap(std::move(from.__heap)),
113  __indices(std::move(from.__indices)),
114  __nb_elements(std::move(from.__nb_elements)), __cmp(std::move(from.__cmp)) {
115  // for debugging purposes
116  GUM_CONS_MOV(MultiPriorityQueue);
117  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ ~MultiPriorityQueue()

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

Class destructor.

Definition at line 121 of file multiPriorityQueue_tpl.h.

121  {
122  // for debugging purposes
123  GUM_DESTRUCTOR(MultiPriorityQueue);
124  }
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.

Member Function Documentation

◆ allValues()

template<typename Val , typename Priority , typename Cmp , typename Alloc >
INLINE const HashTable< Val, std::vector< Size > > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::allValues ( ) const

Returns a gum::HashTable the keys of which are the values stored in the queue.

The keys of the gum::HashTable correspond to the values stored in the priority queue and, for each key, the corresponding value is the list of indices in the queue where we can find the key.

Returns
Returns a gum::HashTable the keys of which are the values stored in the queue.

Definition at line 360 of file multiPriorityQueue_tpl.h.

360  {
361  return reinterpret_cast< const HashTable< Val, std::vector< Size > >& >(
362  __indices);
363  }
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ capacity()

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

Return the size of the internal structure storing the priority queue.

Returns
Return the size of the internal structure storing the priority queue.

Definition at line 248 of file multiPriorityQueue_tpl.h.

249  {
250  return Size(__heap.capacity());
251  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48

◆ clear()

template<typename Val , typename Priority , typename Cmp , typename Alloc >
void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::clear ( )

Removes all the elements from the queue.

Definition at line 265 of file multiPriorityQueue_tpl.h.

Referenced by gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::clear().

265  {
266  __nb_elements = 0;
267  __heap.clear();
268  __indices.clear();
269  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
void clear()
Removes all the elements in the hash table.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
+ Here is the caller graph for this function:

◆ contains()

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

Indicates whether the priority queue contains a given value.

Parameters
valThe value to check if it is in the priority queue.
Returns
Returns true if the priority queue cotains the given value.

Definition at line 500 of file multiPriorityQueue_tpl.h.

501  {
502  return __indices.exists(val);
503  }
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ emplace() [1/2]

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
template<typename... Args>
Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::emplace ( Args &&...  args)

Emplace a new element into the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Template Parameters
ArgsThe emplace arguments types.
Parameters
argsThe emplace arguments.
Returns
the index of the element inserted into the priority queue.

◆ emplace() [2/2]

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
template<typename... Args>
INLINE Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::emplace ( Args &&...  args)

Definition at line 485 of file multiPriorityQueue_tpl.h.

485  {
486  std::pair< Val, Priority > new_elt =
487  std::make_pair< Val, Priority >(std::forward< Args >(args)...);
488  return insert(std::move(new_elt.first), std::move(new_elt.second));
489  }
Size insert(const Val &val, const Priority &priority)
Inserts a new (a copy) element in the priority queue.

◆ empty()

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

Indicates whether the priority queue is empty.

Returns
Indicates whether the priority queue is empty.

Definition at line 493 of file multiPriorityQueue_tpl.h.

494  {
495  return (__nb_elements == 0);
496  }
Size __nb_elements
The number of elements in the heap.

◆ erase()

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

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

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

If the queue contains several times this element, then the one with the smallest index is removed.

Parameters
valthe element we wish to remove.

Definition at line 334 of file multiPriorityQueue_tpl.h.

Referenced by gum::VariableSelector::__removeVar(), and gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::eraseByPos().

334  {
335  try {
336  eraseByPos(__indices[val][0]);
337  } catch (NotFound&) {}
338  }
void eraseByPos(Size index)
Removes the element at position "index" from the priority queue.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
+ Here is the caller graph for this function:

◆ eraseByPos()

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

Removes the element at position "index" from the priority queue.

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

The priority is computed as follows: suppose that the queue is a complete binary tree where all levels are completely filled except, eventually, the last one. In this case, the elements of the last level are all on the left of the tree.

We assign 0 to the root, then parsing the tree from top to bottom then from left to right we increment the index and assigned it to the current node. Doing so, we get a unique index for each element. This is precisely what the index passed in argument of the function represents.

Parameters
indexrepresents the position of the element to be removed.

Definition at line 273 of file multiPriorityQueue_tpl.h.

273  {
274  if (index >= __nb_elements) return;
275 
276  // remove the element from the hashtable
277  const Val& del_val = *(__heap[index].second);
278  std::vector< Size >& vect_index = __indices[del_val];
279  if (vect_index.size() == 1)
280  __indices.erase(del_val);
281  else {
282  for (auto& v_index : vect_index) {
283  if (v_index == index) {
284  v_index = vect_index.back();
285  vect_index.pop_back();
286  break;
287  }
288  }
289  }
290 
291  // put the last element at the "index" location
292  std::pair< Priority, const Val* > last = std::move(__heap.back());
293  __heap.pop_back();
294  --__nb_elements;
295 
296  if (!__nb_elements || (index == __nb_elements)) return;
297 
298  // restore the heap property
299  Size i = index;
300 
301  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
302  // let j be the max child
303  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
304  ++j;
305 
306  // if "last" is lower than heap[j], "last" must be stored at index i
307  if (__cmp(last.first, __heap[j].first)) break;
308 
309  // else pull up the jth node
310  __heap[i] = std::move(__heap[j]);
311  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
312  for (auto& v_index : vect_index) {
313  if (v_index == j) {
314  v_index = i;
315  break;
316  }
317  }
318  }
319 
320  // put "last" back into the heap
321  __heap[i] = std::move(last);
322  std::vector< Size >& last_indices = __indices[*(__heap[i].second)];
323  for (auto& v_index : last_indices) {
324  if (v_index == __nb_elements) {
325  v_index = i;
326  break;
327  }
328  }
329  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
void erase(const Key &key)
Removes a given element from the hash table.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ eraseTop()

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

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

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

Definition at line 342 of file multiPriorityQueue_tpl.h.

342  {
343  eraseByPos(0);
344  }
void eraseByPos(Size index)
Removes the element at position "index" from the priority queue.

◆ insert() [1/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc >
Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::insert ( const Val &  val,
const Priority &  priority 
)

Inserts a new (a copy) element in the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Parameters
valThe value to insert.
priorityThe value priority.
Returns
Returns the index of the element inserted into the priority queue.

Definition at line 367 of file multiPriorityQueue_tpl.h.

Referenced by gum::VariableSelector::__addVar(), gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::insert(), and gum::VariableSelector::VariableSelector().

368  {
369  // create the entry in the indices hashtable
370  const Val* new_val;
371  std::vector< Size >* new_vect;
372  if (!__indices.exists(val)) {
373  auto& new_elt = __indices.insert(val, std::vector< Size >());
374  new_val = &(new_elt.first);
375  new_vect = &(new_elt.second);
376  } else {
377  new_val = &(__indices.key(val));
378  new_vect = &(__indices[val]);
379  }
380 
381  try {
382  new_vect->push_back(0);
383  } catch (...) {
384  if (new_vect->empty()) { __indices.erase(val); }
385  throw;
386  }
387 
388  try {
389  __heap.push_back(std::pair< Priority, const Val* >(priority, new_val));
390  } catch (...) {
391  if (new_vect->size() == 1) { __indices.erase(val); }
392  throw;
393  }
394 
395  std::pair< Priority, const Val* > new_heap_val =
396  std::move(__heap[__nb_elements]);
397  ++__nb_elements;
398 
399  // restore the heap property
400  Size i = __nb_elements - 1;
401 
402  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
403  i = j, j = (j - 1) >> 1) {
404  __heap[i] = std::move(__heap[j]);
405  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
406  for (auto& index : vect_index) {
407  if (index == j) {
408  index = i;
409  break;
410  }
411  }
412  }
413 
414  // put the new bucket into the heap
415  __heap[i].first = std::move(new_heap_val.first);
416  __heap[i].second = new_val;
417  new_vect->back() = i;
418 
419  return i;
420  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
void erase(const Key &key)
Removes a given element from the hash table.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
const Key & key(const Key &key) const
Returns a reference on a given key.
const Priority & priority(const Val &elt) const
Returns the priority of an instance of the value passed in argument.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
+ Here is the caller graph for this function:

◆ insert() [2/2]

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

Inserts (by move) a new element in the priority queue.

See method gum::MultiPriorityQueue::eraseByPos(Size) for more details about the index.

Parameters
valThe value to insert.
priorityThe value priority.
Returns
Returns the index of the element inserted into the priority queue.

Definition at line 425 of file multiPriorityQueue_tpl.h.

426  {
427  // create the entry in the indices hashtable
428  const Val* new_val;
429  std::vector< Size >* new_vect;
430  if (!__indices.exists(val)) {
431  auto& new_elt = __indices.insert(std::move(val), std::vector< Size >());
432  new_val = &(new_elt.first);
433  new_vect = &(new_elt.second);
434  } else {
435  new_val = &(__indices.key(val));
436  new_vect = &(__indices[val]);
437  }
438 
439  try {
440  new_vect->push_back(0);
441  } catch (...) {
442  if (new_vect->empty()) { __indices.erase(*new_val); }
443  throw;
444  }
445 
446  try {
447  __heap.push_back(
448  std::pair< Priority, const Val* >(std::move(priority), new_val));
449  } catch (...) {
450  if (new_vect->size() == 1) { __indices.erase(*new_val); }
451  throw;
452  }
453 
454  std::pair< Priority, const Val* > new_heap_val =
455  std::move(__heap[__nb_elements]);
456  ++__nb_elements;
457 
458  // restore the heap property
459  Size i = __nb_elements - 1;
460 
461  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
462  i = j, j = (j - 1) >> 1) {
463  __heap[i] = std::move(__heap[j]);
464  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
465  for (auto& index : vect_index) {
466  if (index == j) {
467  index = i;
468  break;
469  }
470  }
471  }
472 
473  // put the new bucket into the heap
474  __heap[i].first = std::move(new_heap_val.first);
475  __heap[i].second = new_val;
476  new_vect->back() = i;
477 
478  return i;
479  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
void erase(const Key &key)
Removes a given element from the hash table.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
const Key & key(const Key &key) const
Returns a reference on a given key.
const Priority & priority(const Val &elt) const
Returns the priority of an instance of the value passed in argument.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ operator=() [1/3]

template<typename Val, typename Priority, typename Cmp, typename Alloc>
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator= ( const MultiPriorityQueue< Val, Priority, 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 priority queue becomes empty. An exception is then thrown.

Parameters
fromThe gum::MultiPriorityQueue to copy.

Definition at line 130 of file multiPriorityQueue_tpl.h.

130  {
131  // for debugging purposes
132  GUM_OP_CPY(MultiPriorityQueue);
133 
134  try {
135  // set the comprison function
136  __cmp = from.__cmp;
137 
138  // copy the indices and the heap
139  __indices = from.__indices;
140  __heap = from.__heap;
141  __nb_elements = from.__nb_elements;
142 
143  // restore the link between __indices and __heap
144  for (const auto& val_and_index : __indices) {
145  const Val* val = &(val_and_index.first);
146  const std::vector< Size >& vect = val_and_index.second;
147  for (auto index : vect) {
148  __heap[index].second = val;
149  }
150  }
151  } catch (...) {
152  __heap.clear();
153  __indices.clear();
154  __nb_elements = 0;
155 
156  throw;
157  }
158 
159  return *this;
160  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ operator=() [2/3]

template<typename Val, typename Priority, typename Cmp, typename Alloc >
template<typename OtherAlloc >
MultiPriorityQueue< Val, Priority, Cmp, Alloc > & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::operator= ( const MultiPriorityQueue< Val, Priority, 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 priority queue becomes empty. An exception is then thrown.

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

Definition at line 166 of file multiPriorityQueue_tpl.h.

167  {
168  // for debugging purposes
169  GUM_OP_CPY(MultiPriorityQueue);
170 
171  try {
172  // set the comprison function
173  __cmp = from.__cmp;
174 
175  // copy the indices and the heap
176  __indices = from.__indices;
177  __nb_elements = from.__nb_elements;
178 
179  // restore the link between __indices and __heap
180  __heap.clear();
181  __heap.reserve(from.__heap.size());
182  for (const auto& elt : from.__heap) {
183  __heap.push_back(elt);
184  }
185  for (const auto& val_and_index : __indices) {
186  const Val* val = &(val_and_index.first);
187  const std::vector< Size >& vect = val_and_index.second;
188  for (auto index : vect) {
189  __heap[index].second = val;
190  }
191  }
192  } catch (...) {
193  __heap.clear();
194  __indices.clear();
195  __nb_elements = 0;
196 
197  throw;
198  }
199 
200  return *this;
201  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ operator=() [3/3]

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

Move operator.

Parameters
fromThe gum::MultiPriorityQueue to copy.

Definition at line 207 of file multiPriorityQueue_tpl.h.

207  {
208  // avoid self assignment
209  if (this != &from) {
210  // for debugging purposes
211  GUM_OP_MOV(MultiPriorityQueue);
212 
213  __cmp = std::move(from.__cmp);
214  __indices = std::move(from.__indices);
215  __heap = std::move(from.__heap);
216  __nb_elements = std::move(from.__nb_elements);
217  }
218 
219  return *this;
220  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
friend class MultiPriorityQueue
Making all MultiPriorityQueue friend with themselves.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ operator[]()

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

Returns the element at index "index_elt" from the priority queue.

Parameters
index_eltThe index of the element to return.
Returns
Returns the element at index "index_elt" from the priority queue.
Exceptions
NotFoundRaised if the element does not exist.

Definition at line 508 of file multiPriorityQueue_tpl.h.

508  {
509  if (index >= __nb_elements) {
510  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
511  }
512 
513  return *(__heap[index].second);
514  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ pop()

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

Removes the top element from the priority queue and return it.

Returns
Returns the top element from the priority queue.
Exceptions
NotFoundRaised if the queue is empty.

Definition at line 348 of file multiPriorityQueue_tpl.h.

348  {
349  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
350 
351  Val v = *(__heap[0].second);
352  eraseByPos(0);
353 
354  return v;
355  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
void eraseByPos(Size index)
Removes the element at position "index" from the priority queue.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ priority()

template<typename Val, typename Priority , typename Cmp , typename Alloc >
INLINE const Priority & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::priority ( const Val &  elt) const

Returns the priority of an instance of the value passed in argument.

Of course, this method is really meaningful only when there is only one instance of the given element within the PriorityQueue.

Parameters
eltThe element for which the priority is returned.
Returns
Returns the priority of an instance of the value passed in argument.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 671 of file multiPriorityQueue_tpl.h.

672  {
673  return __heap[__indices[elt][0]].first;
674  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ resize()

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

Changes the size of the internal structure storing the priority queue.

Parameters
new_sizeThe internal structure new size.
Returns
Changes the size of the internal structure storing the priority queue.

Definition at line 256 of file multiPriorityQueue_tpl.h.

Referenced by gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::resize().

256  {
257  if (new_size < __nb_elements) return;
258 
259  __heap.reserve(new_size);
260  __indices.resize(new_size / 2);
261  }
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
+ Here is the caller graph for this function:

◆ setPriority()

template<typename Val, typename Priority, typename Cmp , typename Alloc >
void gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriority ( const Val &  elt,
const Priority &  new_priority 
)

Modifies the priority of each instance of a given element.

Parameters
eltThe value to update.
new_priorityThe values new priority.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 660 of file multiPriorityQueue_tpl.h.

661  {
662  std::vector< Size >& vect_index = __indices[elt];
663 
664  for (auto index : vect_index) {
665  setPriorityByPos(index, new_priority);
666  }
667  }
Size setPriorityByPos(Size index, const Priority &new_priority)
Modifies the priority of the element at position "index" of the queue.
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.

◆ setPriorityByPos() [1/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >
Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriorityByPos ( Size  index,
const Priority &  new_priority 
)

Modifies the priority of the element at position "index" of the queue.

Parameters
indexThe index of the element to update.
new_priorityThe element's new priority.
Returns
Returns the elements new priority.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 536 of file multiPriorityQueue_tpl.h.

537  {
538  // check whether the element the priority of which should be changed exists
539  if (index >= __nb_elements) {
540  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
541  }
542 
543  // get the element itself
544  const Val* val = __heap[index].second;
545 
546  // restore the heap property
547  Size i = index;
548 
549  // move val upward if needed
550  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
551  i = j, j = (j - 1) >> 1) {
552  __heap[i] = std::move(__heap[j]);
553  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
554  for (auto& idx : vect_index) {
555  if (idx == j) {
556  idx = i;
557  break;
558  }
559  }
560  }
561 
562  // move val downward if needed
563  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
564  // let j be the max child
565  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
566  ++j;
567 
568  // if "val" is lower than heap[j], "val" must be stored at index i
569  if (__cmp(new_priority, __heap[j].first)) break;
570 
571  // else pull up the jth node
572  __heap[i] = std::move(__heap[j]);
573  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
574  for (auto& idx : vect_index) {
575  if (idx == j) {
576  idx = i;
577  break;
578  }
579  }
580  }
581 
582  // update the index of val
583  __heap[i].first = new_priority;
584  __heap[i].second = val;
585  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
586  for (auto& idx : vect_index) {
587  if (idx == index) {
588  idx = i;
589  break;
590  }
591  }
592 
593  return i;
594  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ setPriorityByPos() [2/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >
Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::setPriorityByPos ( Size  index,
Priority &&  new_priority 
)

Modifies the priority of the element at position "index" of the queue.

Parameters
indexThe index of the element to update.
new_priorityThe element's new priority.
Returns
Returns the elements new priority.
Exceptions
NotFoundRaised if the element cannot be found.

Definition at line 598 of file multiPriorityQueue_tpl.h.

599  {
600  // check whether the element the priority of which should be changed exists
601  if (index >= __nb_elements) {
602  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
603  }
604 
605  // get the element itself
606  const Val* val = __heap[index].second;
607 
608  // restore the heap property
609  Size i = index;
610 
611  // move val upward if needed
612  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
613  i = j, j = (j - 1) >> 1) {
614  __heap[i] = std::move(__heap[j]);
615  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
616  for (auto& idx : vect_index) {
617  if (idx == j) {
618  idx = i;
619  break;
620  }
621  }
622  }
623 
624  // move val downward if needed
625  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
626  // let j be the max child
627  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
628  ++j;
629 
630  // if "val" is lower than heap[j], "val" must be stored at index i
631  if (__cmp(new_priority, __heap[j].first)) break;
632 
633  // else pull up the jth node
634  __heap[i] = std::move(__heap[j]);
635  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
636  for (auto& idx : vect_index) {
637  if (idx == j) {
638  idx = i;
639  break;
640  }
641  }
642  }
643 
644  // update the index of val
645  __heap[i].first = std::move(new_priority);
646  __heap[i].second = val;
647  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
648  for (auto& idx : vect_index) {
649  if (idx == index) {
650  idx = i;
651  break;
652  }
653  }
654 
655  return i;
656  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
Cmp __cmp
Comparison function.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
HashTable< Val, std::vector< Size >, IndexAlloc > __indices
A hashtable for quickly finding the elements by their value.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ size()

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

Returns the number of elements in the priority queue.

Returns
Returns the number of elements in the priority queue.

Definition at line 241 of file multiPriorityQueue_tpl.h.

242  {
243  return __nb_elements;
244  }
Size __nb_elements
The number of elements in the heap.

◆ top()

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

Returns the element at the top of the priority queue.

Returns
Returns the element at the top of the priority queue.
Exceptions
NotFoundRaised if the queue is empty.

Definition at line 224 of file multiPriorityQueue_tpl.h.

Referenced by gum::VariableSelector::select().

224  {
225  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
226 
227  return *(__heap[0].second);
228  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
+ Here is the caller graph for this function:

◆ topPriority()

template<typename Val , typename Priority , typename Cmp , typename Alloc >
INLINE const Priority & gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::topPriority ( ) const

Returns the priority of the top element.

Exceptions
NotFoundRaised if the queue is empty.

Definition at line 233 of file multiPriorityQueue_tpl.h.

233  {
234  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
235 
236  return __heap[0].first;
237  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55

◆ toString()

template<typename Val , typename Priority , typename Cmp , typename Alloc >
std::string gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::toString ( ) const

Displays the content of the queue.

Returns
Returns the content of the queue.

Definition at line 518 of file multiPriorityQueue_tpl.h.

Referenced by gum::operator<<().

518  {
519  bool deja = false;
520  std::stringstream stream;
521  stream << "[";
522 
523  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
524  if (deja) stream << " , ";
525 
526  stream << "(" << __heap[i].first << " , " << *(__heap[i].second) << ")";
527  }
528 
529  stream << "]";
530 
531  return stream.str();
532  }
std::vector< std::pair< Priority, const Val *>, HeapAlloc > __heap
An array storing all the elements of the heap as well as their score.
Size __nb_elements
The number of elements in the heap.
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
+ Here is the caller graph for this function:

Friends And Related Function Documentation

◆ MultiPriorityQueue

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
template<typename V , typename P , typename C , typename A >
friend class MultiPriorityQueue
friend

Making all MultiPriorityQueue friend with themselves.

Definition at line 130 of file multiPriorityQueue.h.

Member Data Documentation

◆ __cmp

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

◆ __heap

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
std::vector< std::pair< Priority, const Val* >, HeapAlloc > gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::__heap
private

◆ __indices

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
HashTable< Val, std::vector< Size >, IndexAlloc > gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::__indices
private

A hashtable for quickly finding the elements by their value.

Definition at line 483 of file multiPriorityQueue.h.

Referenced by gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::operator=().

◆ __nb_elements

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >, typename Alloc = std::allocator< Val >>
Size gum::MultiPriorityQueue< Val, Priority, Cmp, Alloc >::__nb_elements {0}
private

The number of elements in the heap.

Definition at line 486 of file multiPriorityQueue.h.

Referenced by gum::MultiPriorityQueue< gum::LeafPair *, double, std::less< double > >::operator=().


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