aGrUM  0.14.3
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 124 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 138 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 136 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 134 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 137 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 147 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 143 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 135 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 133 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 132 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 34 of file multiPriorityQueue_tpl.h.

35  :
36  __indices(capacity >> 1, true, false),
37  __cmp(compare) {
38  __heap.reserve(capacity);
39 
40  // for debugging purposes
41  GUM_CONSTRUCTOR(MultiPriorityQueue);
42  }
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 46 of file multiPriorityQueue_tpl.h.

47  :
48  __indices(Size(list.size()) / 2, true, false) {
49  // fill the queue
50  __heap.reserve(list.size());
51  for (const auto& elt : list) {
52  insert(elt.first, elt.second);
53  }
54 
55  // for debugging purposes
56  GUM_CONSTRUCTOR(MultiPriorityQueue);
57  }
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:45
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 61 of file multiPriorityQueue_tpl.h.

62  :
63  __heap(from.__heap),
64  __indices(from.__indices), __nb_elements(from.__nb_elements),
65  __cmp(from.__cmp) {
66  // for debugging purposes
67  GUM_CONS_CPY(MultiPriorityQueue);
68 
69  // fill the heap structure
70  for (const auto& val_and_index : __indices) {
71  const Val* val = &(val_and_index.first);
72  const std::vector< Size >& vect = val_and_index.second;
73  for (auto index : vect) {
74  __heap[index].second = val;
75  }
76  }
77  }
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 82 of file multiPriorityQueue_tpl.h.

83  :
84  __indices(from.__indices),
85  __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
86  // for debugging purposes
87  GUM_CONS_CPY(MultiPriorityQueue);
88 
89  // fill the heap structure
90  if (__nb_elements) {
91  __heap.reserve(from.__heap.size());
92  for (const auto& elt : from.__heap) {
93  __heap.push_back(elt);
94  }
95  for (const auto& val_and_index : __indices) {
96  const Val* val = &(val_and_index.first);
97  const std::vector< Size >& vect = val_and_index.second;
98  for (auto index : vect) {
99  __heap[index].second = val;
100  }
101  }
102  }
103  }
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 107 of file multiPriorityQueue_tpl.h.

108  :
109  __heap(std::move(from.__heap)),
110  __indices(std::move(from.__indices)),
111  __nb_elements(std::move(from.__nb_elements)), __cmp(std::move(from.__cmp)) {
112  // for debugging purposes
113  GUM_CONS_MOV(MultiPriorityQueue);
114  }
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 118 of file multiPriorityQueue_tpl.h.

118  {
119  // for debugging purposes
120  GUM_DESTRUCTOR(MultiPriorityQueue);
121  }
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 357 of file multiPriorityQueue_tpl.h.

357  {
358  return reinterpret_cast< const HashTable< Val, std::vector< Size > >& >(
359  __indices);
360  }
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 245 of file multiPriorityQueue_tpl.h.

246  {
247  return Size(__heap.capacity());
248  }
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:45

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

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

262  {
263  __nb_elements = 0;
264  __heap.clear();
265  __indices.clear();
266  }
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 497 of file multiPriorityQueue_tpl.h.

498  {
499  return __indices.exists(val);
500  }
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 482 of file multiPriorityQueue_tpl.h.

482  {
483  std::pair< Val, Priority > new_elt =
484  std::make_pair< Val, Priority >(std::forward< Args >(args)...);
485  return insert(std::move(new_elt.first), std::move(new_elt.second));
486  }
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 490 of file multiPriorityQueue_tpl.h.

491  {
492  return (__nb_elements == 0);
493  }
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 331 of file multiPriorityQueue_tpl.h.

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

331  {
332  try {
333  eraseByPos(__indices[val][0]);
334  } catch (NotFound&) {}
335  }
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 270 of file multiPriorityQueue_tpl.h.

270  {
271  if (index >= __nb_elements) return;
272 
273  // remove the element from the hashtable
274  const Val& del_val = *(__heap[index].second);
275  std::vector< Size >& vect_index = __indices[del_val];
276  if (vect_index.size() == 1)
277  __indices.erase(del_val);
278  else {
279  for (auto& v_index : vect_index) {
280  if (v_index == index) {
281  v_index = vect_index.back();
282  vect_index.pop_back();
283  break;
284  }
285  }
286  }
287 
288  // put the last element at the "index" location
289  std::pair< Priority, const Val* > last = std::move(__heap.back());
290  __heap.pop_back();
291  --__nb_elements;
292 
293  if (!__nb_elements || (index == __nb_elements)) return;
294 
295  // restore the heap property
296  Size i = index;
297 
298  for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
299  // let j be the max child
300  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
301  ++j;
302 
303  // if "last" is lower than heap[j], "last" must be stored at index i
304  if (__cmp(last.first, __heap[j].first)) break;
305 
306  // else pull up the jth node
307  __heap[i] = std::move(__heap[j]);
308  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
309  for (auto& v_index : vect_index) {
310  if (v_index == j) {
311  v_index = i;
312  break;
313  }
314  }
315  }
316 
317  // put "last" back into the heap
318  __heap[i] = std::move(last);
319  std::vector< Size >& last_indices = __indices[*(__heap[i].second)];
320  for (auto& v_index : last_indices) {
321  if (v_index == __nb_elements) {
322  v_index = i;
323  break;
324  }
325  }
326  }
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:45
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 339 of file multiPriorityQueue_tpl.h.

339  {
340  eraseByPos(0);
341  }
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 364 of file multiPriorityQueue_tpl.h.

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

365  {
366  // create the entry in the indices hashtable
367  const Val* new_val;
368  std::vector< Size >* new_vect;
369  if (!__indices.exists(val)) {
370  auto& new_elt = __indices.insert(val, std::vector< Size >());
371  new_val = &(new_elt.first);
372  new_vect = &(new_elt.second);
373  } else {
374  new_val = &(__indices.key(val));
375  new_vect = &(__indices[val]);
376  }
377 
378  try {
379  new_vect->push_back(0);
380  } catch (...) {
381  if (new_vect->empty()) { __indices.erase(val); }
382  throw;
383  }
384 
385  try {
386  __heap.push_back(std::pair< Priority, const Val* >(priority, new_val));
387  } catch (...) {
388  if (new_vect->size() == 1) { __indices.erase(val); }
389  throw;
390  }
391 
392  std::pair< Priority, const Val* > new_heap_val =
393  std::move(__heap[__nb_elements]);
394  ++__nb_elements;
395 
396  // restore the heap property
397  Size i = __nb_elements - 1;
398 
399  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
400  i = j, j = (j - 1) >> 1) {
401  __heap[i] = std::move(__heap[j]);
402  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
403  for (auto& index : vect_index) {
404  if (index == j) {
405  index = i;
406  break;
407  }
408  }
409  }
410 
411  // put the new bucket into the heap
412  __heap[i].first = std::move(new_heap_val.first);
413  __heap[i].second = new_val;
414  new_vect->back() = i;
415 
416  return i;
417  }
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:45
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 422 of file multiPriorityQueue_tpl.h.

423  {
424  // create the entry in the indices hashtable
425  const Val* new_val;
426  std::vector< Size >* new_vect;
427  if (!__indices.exists(val)) {
428  auto& new_elt = __indices.insert(std::move(val), std::vector< Size >());
429  new_val = &(new_elt.first);
430  new_vect = &(new_elt.second);
431  } else {
432  new_val = &(__indices.key(val));
433  new_vect = &(__indices[val]);
434  }
435 
436  try {
437  new_vect->push_back(0);
438  } catch (...) {
439  if (new_vect->empty()) { __indices.erase(*new_val); }
440  throw;
441  }
442 
443  try {
444  __heap.push_back(
445  std::pair< Priority, const Val* >(std::move(priority), new_val));
446  } catch (...) {
447  if (new_vect->size() == 1) { __indices.erase(*new_val); }
448  throw;
449  }
450 
451  std::pair< Priority, const Val* > new_heap_val =
452  std::move(__heap[__nb_elements]);
453  ++__nb_elements;
454 
455  // restore the heap property
456  Size i = __nb_elements - 1;
457 
458  for (Size j = (i - 1) >> 1; i && __cmp(new_heap_val.first, __heap[j].first);
459  i = j, j = (j - 1) >> 1) {
460  __heap[i] = std::move(__heap[j]);
461  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
462  for (auto& index : vect_index) {
463  if (index == j) {
464  index = i;
465  break;
466  }
467  }
468  }
469 
470  // put the new bucket into the heap
471  __heap[i].first = std::move(new_heap_val.first);
472  __heap[i].second = new_val;
473  new_vect->back() = i;
474 
475  return i;
476  }
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:45
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 127 of file multiPriorityQueue_tpl.h.

127  {
128  // for debugging purposes
129  GUM_OP_CPY(MultiPriorityQueue);
130 
131  try {
132  // set the comprison function
133  __cmp = from.__cmp;
134 
135  // copy the indices and the heap
136  __indices = from.__indices;
137  __heap = from.__heap;
138  __nb_elements = from.__nb_elements;
139 
140  // restore the link between __indices and __heap
141  for (const auto& val_and_index : __indices) {
142  const Val* val = &(val_and_index.first);
143  const std::vector< Size >& vect = val_and_index.second;
144  for (auto index : vect) {
145  __heap[index].second = val;
146  }
147  }
148  } catch (...) {
149  __heap.clear();
150  __indices.clear();
151  __nb_elements = 0;
152 
153  throw;
154  }
155 
156  return *this;
157  }
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 163 of file multiPriorityQueue_tpl.h.

164  {
165  // for debugging purposes
166  GUM_OP_CPY(MultiPriorityQueue);
167 
168  try {
169  // set the comprison function
170  __cmp = from.__cmp;
171 
172  // copy the indices and the heap
173  __indices = from.__indices;
174  __nb_elements = from.__nb_elements;
175 
176  // restore the link between __indices and __heap
177  __heap.clear();
178  __heap.reserve(from.__heap.size());
179  for (const auto& elt : from.__heap) {
180  __heap.push_back(elt);
181  }
182  for (const auto& val_and_index : __indices) {
183  const Val* val = &(val_and_index.first);
184  const std::vector< Size >& vect = val_and_index.second;
185  for (auto index : vect) {
186  __heap[index].second = val;
187  }
188  }
189  } catch (...) {
190  __heap.clear();
191  __indices.clear();
192  __nb_elements = 0;
193 
194  throw;
195  }
196 
197  return *this;
198  }
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 204 of file multiPriorityQueue_tpl.h.

204  {
205  // avoid self assignment
206  if (this != &from) {
207  // for debugging purposes
208  GUM_OP_MOV(MultiPriorityQueue);
209 
210  __cmp = std::move(from.__cmp);
211  __indices = std::move(from.__indices);
212  __heap = std::move(from.__heap);
213  __nb_elements = std::move(from.__nb_elements);
214  }
215 
216  return *this;
217  }
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 505 of file multiPriorityQueue_tpl.h.

505  {
506  if (index >= __nb_elements) {
507  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
508  }
509 
510  return *(__heap[index].second);
511  }
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:52

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

345  {
346  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
347 
348  Val v = *(__heap[0].second);
349  eraseByPos(0);
350 
351  return v;
352  }
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:52

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

669  {
670  return __heap[__indices[elt][0]].first;
671  }
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 253 of file multiPriorityQueue_tpl.h.

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

253  {
254  if (new_size < __nb_elements) return;
255 
256  __heap.reserve(new_size);
257  __indices.resize(new_size / 2);
258  }
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 657 of file multiPriorityQueue_tpl.h.

658  {
659  std::vector< Size >& vect_index = __indices[elt];
660 
661  for (auto index : vect_index) {
662  setPriorityByPos(index, new_priority);
663  }
664  }
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 533 of file multiPriorityQueue_tpl.h.

534  {
535  // check whether the element the priority of which should be changed exists
536  if (index >= __nb_elements) {
537  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
538  }
539 
540  // get the element itself
541  const Val* val = __heap[index].second;
542 
543  // restore the heap property
544  Size i = index;
545 
546  // move val upward if needed
547  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
548  i = j, j = (j - 1) >> 1) {
549  __heap[i] = std::move(__heap[j]);
550  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
551  for (auto& idx : vect_index) {
552  if (idx == j) {
553  idx = i;
554  break;
555  }
556  }
557  }
558 
559  // move val downward if needed
560  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
561  // let j be the max child
562  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
563  ++j;
564 
565  // if "val" is lower than heap[j], "val" must be stored at index i
566  if (__cmp(new_priority, __heap[j].first)) break;
567 
568  // else pull up the jth node
569  __heap[i] = std::move(__heap[j]);
570  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
571  for (auto& idx : vect_index) {
572  if (idx == j) {
573  idx = i;
574  break;
575  }
576  }
577  }
578 
579  // update the index of val
580  __heap[i].first = new_priority;
581  __heap[i].second = val;
582  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
583  for (auto& idx : vect_index) {
584  if (idx == index) {
585  idx = i;
586  break;
587  }
588  }
589 
590  return i;
591  }
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:45
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:52

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

596  {
597  // check whether the element the priority of which should be changed exists
598  if (index >= __nb_elements) {
599  GUM_ERROR(NotFound, "not enough elements in the MultiPriorityQueue");
600  }
601 
602  // get the element itself
603  const Val* val = __heap[index].second;
604 
605  // restore the heap property
606  Size i = index;
607 
608  // move val upward if needed
609  for (Size j = (i - 1) >> 1; i && __cmp(new_priority, __heap[j].first);
610  i = j, j = (j - 1) >> 1) {
611  __heap[i] = std::move(__heap[j]);
612  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
613  for (auto& idx : vect_index) {
614  if (idx == j) {
615  idx = i;
616  break;
617  }
618  }
619  }
620 
621  // move val downward if needed
622  for (Size j = (i << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
623  // let j be the max child
624  if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1].first, __heap[j].first))
625  ++j;
626 
627  // if "val" is lower than heap[j], "val" must be stored at index i
628  if (__cmp(new_priority, __heap[j].first)) break;
629 
630  // else pull up the jth node
631  __heap[i] = std::move(__heap[j]);
632  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
633  for (auto& idx : vect_index) {
634  if (idx == j) {
635  idx = i;
636  break;
637  }
638  }
639  }
640 
641  // update the index of val
642  __heap[i].first = std::move(new_priority);
643  __heap[i].second = val;
644  std::vector< Size >& vect_index = __indices[*(__heap[i].second)];
645  for (auto& idx : vect_index) {
646  if (idx == index) {
647  idx = i;
648  break;
649  }
650  }
651 
652  return i;
653  }
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:45
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:52

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

239  {
240  return __nb_elements;
241  }
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 221 of file multiPriorityQueue_tpl.h.

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

221  {
222  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
223 
224  return *(__heap[0].second);
225  }
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:52
+ 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 230 of file multiPriorityQueue_tpl.h.

230  {
231  if (!__nb_elements) { GUM_ERROR(NotFound, "empty priority queue"); }
232 
233  return __heap[0].first;
234  }
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:52

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

Referenced by gum::operator<<().

515  {
516  bool deja = false;
517  std::stringstream stream;
518  stream << "[";
519 
520  for (Size i = 0; i != __nb_elements; ++i, deja = true) {
521  if (deja) stream << " , ";
522 
523  stream << "(" << __heap[i].first << " , " << *(__heap[i].second) << ")";
524  }
525 
526  stream << "]";
527 
528  return stream.str();
529  }
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:45
+ 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 127 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 480 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 483 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: