A priorityQueue is a heap in which each element has a mutable priority. More...

#include <agrum/base/core/priorityQueue.h>

Inheritance diagram for gum::PriorityQueue< Val, Priority, Cmp >:

Collaboration diagram for gum::PriorityQueue< Val, Priority, Cmp >:

Public Types
using	Implementation = PriorityQueueImplementation< Val, Priority, Cmp, std::is_scalar< Val >::value >

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

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

Private Attributes
std::vector< std::pair< int, const Val * > >	_heap_
	An array storing all the elements of the heap as well as their score.
HashTable< Val, Size >	_indices_
	A hashtable for quickly finding the elements by their value.
Size	_nb_elements_
	The number of elements in the heap.
std::less< int >	_cmp_
	Comparison function.

Detailed Description

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>
class gum::PriorityQueue< Val, Priority, Cmp >

A priorityQueue is a heap in which each element has a mutable priority.

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. Duplicate elements are not allowed in priority queues; if you wish an element to appear several times with different priorities, prefer using class MultiplePriorityQueue.

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

PriorityQueue<std::string> queue1;

// insert elements into the queue

queue1.insert ("AAA", 8);

queue1.insert ("BBB", 10);

queue1.insert ("CCC", 2);

queue1.insert ("DDD", 23);

queue1.insert ("EEE", 24);

// copy the queue

PriorityQueue<std::string> queue2 = queue1;

// initializer list constructor

PriorityQueue<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

PriorityQueue< 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);

gum::PriorityQueueImplementation::setPriority
void setPriority(const Val &elt, const Priority &new_priority)
Modifies the priority of each instance of a given element.
Definition priorityQueue_tpl.h:488

gum::PriorityQueueImplementation::eraseTop
void eraseTop()
Removes the top of the priority queue (but does not return it).
Definition priorityQueue_tpl.h:254

gum::PriorityQueueImplementation::pop
Val pop()
Removes the top element from the priority queue and return it.
Definition priorityQueue_tpl.h:260

gum::PriorityQueueImplementation::top
const Val & top() const
returns the element at the top of the priority queue
Definition priorityQueue_tpl.h:165

gum::PriorityQueueImplementation::insert
Size insert(const Val &val, const Priority &priority)
Inserts a new (a copy) element in the priority queue.
Definition priorityQueue_tpl.h:279

gum::PriorityQueueImplementation::setPriorityByPos
Size setPriorityByPos(Size index, const Priority &new_priority)
Modifies the priority of the element at position "index" of the queue.
Definition priorityQueue_tpl.h:400

gum::PriorityQueue
A priorityQueue is a heap in which each element has a mutable priority.
Definition priorityQueue.h:884

gum::PriorityQueue::PriorityQueue
PriorityQueue(Cmp compare=Cmp(), Size capacity=GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY)
Basic constructor.
Definition priorityQueue_tpl.h:986

gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition types.h:74

Template Parameters

Val	The values type.
Priority	The priorities type.
Cmp	The priorities comparator.

Definition at line 883 of file priorityQueue.h.

Member Typedef Documentation

◆ const_pointer

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::const_pointer = const Val*

Types for STL compliance.

Definition at line 892 of file priorityQueue.h.

◆ const_reference

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::const_reference = const Val&

Types for STL compliance.

Definition at line 890 of file priorityQueue.h.

◆ difference_type

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 893 of file priorityQueue.h.

◆ Implementation

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::Implementation = PriorityQueueImplementation< Val, Priority, Cmp, std::is_scalar< Val >::value >

Definition at line 896 of file priorityQueue.h.

◆ pointer

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::pointer = Val*

Types for STL compliance.

Definition at line 891 of file priorityQueue.h.

◆ reference

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::reference = Val&

Types for STL compliance.

Definition at line 889 of file priorityQueue.h.

◆ value_type

template<typename Val, typename Priority = int, typename Cmp = std::less< Priority >>

using gum::PriorityQueue< Val, Priority, Cmp >::value_type = Val

Types for STL compliance.

Definition at line 888 of file priorityQueue.h.

Constructor & Destructor Documentation

◆ PriorityQueue() [1/4]

template<typename Val, typename Priority, typename Cmp>

INLINE gum::PriorityQueue< Val, Priority, Cmp >::PriorityQueue	(	Cmp	compare = Cmp(),
		Size	capacity = GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY )

explicit

Basic constructor.

Creates an empty priority queue.

Parameters

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

Definition at line 986 of file priorityQueue_tpl.h.

                                                                                  :
      PriorityQueue< Val, Priority, Cmp >::Implementation(cmp, capacity) {
    // for debugging purposes
    GUM_CONSTRUCTOR(PriorityQueue);
  }

References PriorityQueue(), and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::capacity().

Referenced by PriorityQueue(), PriorityQueue(), PriorityQueue(), PriorityQueue(), and ~PriorityQueue().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ PriorityQueue() [2/4]

template<typename Val, typename Priority, typename Cmp>

INLINE gum::PriorityQueue< Val, Priority, Cmp >::PriorityQueue ( 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

list	The initializer list.

Definition at line 994 of file priorityQueue_tpl.h.

                                                            :
      PriorityQueue< Val, Priority, Cmp >::Implementation{list} {
    // for debugging purposes
    GUM_CONSTRUCTOR(PriorityQueue);
  }

References PriorityQueue().

Here is the call graph for this function:

◆ PriorityQueue() [3/4]

template<typename Val, typename Priority, typename Cmp>

INLINE gum::PriorityQueue< Val, Priority, Cmp >::PriorityQueue ( const PriorityQueue< Val, Priority, Cmp > & from )

Copy constructor.

Parameters

from	The gum::PriorityQueue to copy.

Definition at line 1003 of file priorityQueue_tpl.h.

                                                       :
      PriorityQueue< Val, Priority, Cmp >::Implementation(from) {
    // for debugging purposes
    GUM_CONS_CPY(PriorityQueue);
  }

References PriorityQueue(), and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::PriorityQueue< Val, Priority, Cmp >.

Here is the call graph for this function:

◆ PriorityQueue() [4/4]

template<typename Val, typename Priority, typename Cmp>

INLINE gum::PriorityQueue< Val, Priority, Cmp >::PriorityQueue ( PriorityQueue< Val, Priority, Cmp > && from )

Move constructor.

Parameters

from	The gum::PriorityQueue to move.

Definition at line 1012 of file priorityQueue_tpl.h.

                                                  :
      PriorityQueue< Val, Priority, Cmp >::Implementation(std::move(from)) {
    // for debugging purposes
    GUM_CONS_MOV(PriorityQueue);
  }

References PriorityQueue(), and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::PriorityQueue< Val, Priority, Cmp >.

Here is the call graph for this function:

◆ ~PriorityQueue()

template<typename Val, typename Priority, typename Cmp>

INLINE gum::PriorityQueue< Val, Priority, Cmp >::~PriorityQueue ( )

Class destructor.

Definition at line 1021 of file priorityQueue_tpl.h.

                                                             {
    // for debugging purposes
    GUM_DESTRUCTOR(PriorityQueue);
  }

References PriorityQueue().

Here is the call graph for this function:

Member Function Documentation

◆ allValues()

INLINE const HashTable< Val, Size > & gum::PriorityQueueImplementation< Val, int, std::less< int > >::allValues ( ) const

noexceptinherited

Returns a hashtable the keys of which are the values stored in the queue.

The keys of the hashtable correspond to the values stored in the priority queue and, for each key, the corresponding value is the index in the queue where we can find the key.

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

Definition at line 399 of file priorityQueue_tpl.h.

                                                                                                {
    return reinterpret_cast< const HashTable< Val, Size >& >(_indices_);
  }

◆ capacity()

INLINE Size gum::PriorityQueueImplementation< Val, int, std::less< int > >::capacity ( ) const

noexceptinherited

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

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

Definition at line 419 of file priorityQueue_tpl.h.

                                                                                              {
    return Size(_heap_.capacity());
  }

Referenced by gum::PriorityQueue< Val, Priority, Cmp >::PriorityQueue().

Here is the caller graph for this function:

◆ clear()

INLINE void gum::PriorityQueueImplementation< Val, int, std::less< int > >::clear ( )

inherited

Removes all the elements from the queue.

Definition at line 386 of file priorityQueue_tpl.h.

                                                                            {
    _nb_elements_ = 0;
    _heap_.clear();
    _indices_.clear();
  }

References _heap_, and _nb_elements_.

◆ contains()

INLINE bool gum::PriorityQueueImplementation< Val, int, std::less< int > >::contains ( const Val & val ) const

inherited

Indicates whether the priority queue contains a given value.

Parameters

val	The value to look for.

Returns: Returns true if val is in the priority queue.

Definition at line 222 of file priorityQueue_tpl.h.

                                                                                           {
    return _indices_.exists(val);
  }

References _nb_elements_.

◆ emplace()

INLINE Size gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::emplace ( Args &&... args )

inherited

Definition at line 350 of file priorityQueue_tpl.h.

                                                                                            {
    std::pair< Val, Priority > new_elt
        = std::make_pair< Val, Priority >(std::forward< Args >(args)...);
    return insert(std::move(new_elt.first), std::move(new_elt.second));
  }

◆ empty()

INLINE bool gum::PriorityQueueImplementation< Val, int, std::less< int > >::empty ( ) const

noexceptinherited

Indicates whether the priority queue is empty.

Returns: Returns true if the priority queue is empty.

Definition at line 215 of file priorityQueue_tpl.h.

                                                                                           {
    return (_nb_elements_ == 0);
  }

References _heap_, _indices_, and _nb_elements_.

◆ erase()

INLINE void gum::PriorityQueueImplementation< Val, int, std::less< int > >::erase ( const Val & val )

inherited

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

val	the element we wish to remove.

Definition at line 325 of file priorityQueue_tpl.h.

                                                                                          {
    try {
      eraseByPos(_indices_[val]);
    } catch (NotFound const&) {}
  }

◆ eraseByPos()

void gum::PriorityQueueImplementation< Val, int, std::less< int > >::eraseByPos ( Size index )

inherited

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

index represents the position of the element to be removed.

Definition at line 311 of file priorityQueue_tpl.h.

                                                                                    {
    if (index >= _nb_elements_) return;
 
    // remove the element from the hashtable
    _indices_.erase(*(_heap_[index].second));
 
    // put the last element at the "index" location
    std::pair< Priority, const Val* > last = std::move(_heap_[_nb_elements_ - 1]);
    _heap_.pop_back();
    --_nb_elements_;
 
    if (!_nb_elements_ || (index == _nb_elements_)) return;
 
    // restore the heap property
    Size i = index;
 
    for (Size j = (index << 1) + 1; j < _nb_elements_; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < _nb_elements_) && _cmp_(_heap_[j + 1].first, _heap_[j].first)) ++j;
 
      // if "last" is lower than heap[j], "last" must be stored at index i
      if (_cmp_(last.first, _heap_[j].first)) break;
 
      // else pull up the jth node
      _heap_[i]                      = std::move(_heap_[j]);
      _indices_[*(_heap_[i].second)] = i;
    }
 
    // put "last" back into the heap
    _heap_[i]                      = std::move(last);
    _indices_[*(_heap_[i].second)] = i;
  }

◆ eraseTop()

INLINE void gum::PriorityQueueImplementation< Val, int, std::less< int > >::eraseTop ( )

inherited

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 291 of file priorityQueue_tpl.h.

                                                                               {
    eraseByPos(0);
  }

References _cmp_, _heap_, _indices_, and _nb_elements_.

◆ insert()

INLINE Size gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::insert	(	const Val &	val,
		const int &	priority )

inherited

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

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

Parameters

val	The value to insert.
priority	The value's priority in the queue.

Returns: Returns the index of the element inserted into the priority queue.

Exceptions

DuplicateElement Raised if the element already exists.

Definition at line 254 of file priorityQueue_tpl.h.

                                                                                               {
    // create the entry in the indices hashtable (if the element already exists,
    //  _indices_.insert will raise a Duplicateelement exception)
    typename HashTable< Val, Size >::value_type& new_elt = _indices_.insert(val, 0);
 
    try {
      _heap_.push_back(std::pair< Priority, const Val* >(priority, &new_elt.first));
    } catch (...) {
      _indices_.erase(val);
      throw;
    }
 
    std::pair< Priority, const Val* > new_heap_val = std::move(_heap_[_nb_elements_]);
    ++_nb_elements_;
 
    // restore the heap property
    Size i = _nb_elements_ - 1;
 
    for (Size j = (i - 1) >> 1; i && _cmp_(new_heap_val.first, _heap_[j].first);
         i = j, j = (j - 1) >> 1) {
      _heap_[i]                      = std::move(_heap_[j]);
      _indices_[*(_heap_[i].second)] = i;
    }
 
    // put the new bucket into the heap
    _heap_[i].first  = std::move(new_heap_val.first);
    _heap_[i].second = &(new_elt.first);
    new_elt.second   = i;
 
    return i;
  }

◆ operator=() [1/2]

template<typename Val, typename Priority, typename Cmp>

INLINE PriorityQueue< Val, Priority, Cmp > & gum::PriorityQueue< Val, Priority, Cmp >::operator= ( const PriorityQueue< Val, Priority, Cmp > & 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

from	The gum::PriorityQueue to copy.

Returns: Returns this gum::PriorityQueue.

Definition at line 1028 of file priorityQueue_tpl.h.

                                                       {
    Implementation::operator=(from);
    return *this;
  }

References gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::operator=(), and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::PriorityQueue< Val, Priority, Cmp >.

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename Val, typename Priority, typename Cmp>

INLINE PriorityQueue< Val, Priority, Cmp > & gum::PriorityQueue< Val, Priority, Cmp >::operator= ( PriorityQueue< Val, Priority, Cmp > && from )

Move operator.

Parameters

from	The gum::PriorityQueue to move.

Returns: Returns this gum::PriorityQueue.

Definition at line 1037 of file priorityQueue_tpl.h.

                                                                                             {
    Implementation::operator=(std::move(from));
    return *this;
  }

References gum::PriorityQueueImplementation< Val, Priority, Cmp, Gen >::operator=(), and gum::PriorityQueueImplementation< Val, int, std::less< int >, std::is_scalar< Val >::value >::PriorityQueue< Val, Priority, Cmp >.

Here is the call graph for this function:

◆ operator[]()

INLINE const Val & gum::PriorityQueueImplementation< Val, int, std::less< int > >::operator[] ( Size index_elt ) const

inherited

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

Parameters

index_elt The index of the element to return.

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

Exceptions

NotFound Raised if the element does not exist.

Definition at line 197 of file priorityQueue_tpl.h.

                                                                                         {
    if (index >= _nb_elements_) {
      GUM_ERROR(NotFound, "not enough elements in the PriorityQueueImplementation")
    }
 
    return *(_heap_[index].second);
  }

References _heap_, and _indices_.

◆ pop()

INLINE Val gum::PriorityQueueImplementation< Val, int, std::less< int > >::pop ( )

inherited

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

Returns: Returns the top element from the priority queue.

Exceptions

NotFound Raised if the queue is empty.

Definition at line 240 of file priorityQueue_tpl.h.

                                                                         {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }
 
    Val v = *(_heap_[0].second);
    eraseByPos(0);
 
    return v;
  }

References _heap_, and _indices_.

◆ priority()

INLINE const int & gum::PriorityQueueImplementation< Val, int, std::less< int > >::priority ( const Val & elt ) const

inherited

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

Parameters

elt	The element for which the priority is returned.

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

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 374 of file priorityQueue_tpl.h.

                                                                                           {
    return _heap_[_indices_[elt]].first;
  }

Referenced by gum::DefaultPartialOrderedEliminationSequenceStrategy::_nodeToEliminate_().

Here is the caller graph for this function:

◆ priorityByPos()

INLINE const int & gum::PriorityQueueImplementation< Val, int, std::less< int > >::priorityByPos ( Size index ) const

inherited

Returns the priority of the value passed in argument.

Parameters

index The index of the value of which the priority is returned.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 381 of file priorityQueue_tpl.h.

                                                                                            {
    if (index > _nb_elements_) {
      GUM_ERROR(NotFound, "not enough elements in the PriorityQueueImplementation")
    }
    return _heap_[index].first;
  }

◆ resize()

INLINE void gum::PriorityQueueImplementation< Val, int, std::less< int > >::resize ( Size new_size )

inherited

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

Parameters

new_size The internal structure new size.

Definition at line 426 of file priorityQueue_tpl.h.

                                                                                          {
    if (new_size < _nb_elements_) return;
 
    _heap_.reserve(new_size);
    _indices_.resize(new_size / 2);
  }

References _cmp_, _heap_, and _indices_.

◆ setPriority()

void gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::setPriority	(	const Val &	elt,
		const int &	new_priority )

inherited

Modifies the priority of each instance of a given element.

Parameters

elt	The value to update.
new_priority	The values new priority.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 355 of file priorityQueue_tpl.h.

                                    {
    setPriorityByPos(_indices_[elt], new_priority);
  }

◆ setPriorityByPos()

Size gum::PriorityQueueImplementation< Val, int, std::less< int > >::setPriorityByPos	(	Size	index,
		const int &	new_priority )

inherited

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

Parameters

index	The index of the element to update.
new_priority	The element's new priority.

Returns: Returns the elements new priority.

Exceptions

NotFound Raised if the element cannot be found.

Definition at line 336 of file priorityQueue_tpl.h.

                                    {
    // check whether the element the priority of which should be changed exists
    if (index >= _nb_elements_) {
      GUM_ERROR(NotFound, "not enough elements in the PriorityQueueImplementation")
    }
 
    // get the element itself
    const Val* val = _heap_[index].second;
 
    // restore the heap property
    Size i = index;
 
    // move val upward if needed
    for (Size j = (i - 1) >> 1; i && _cmp_(new_priority, _heap_[j].first);
         i = j, j = (j - 1) >> 1) {
      _heap_[i]                      = std::move(_heap_[j]);
      _indices_[*(_heap_[i].second)] = i;
    }
 
    // move val downward if needed
    for (Size j = (i << 1) + 1; j < _nb_elements_; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < _nb_elements_) && _cmp_(_heap_[j + 1].first, _heap_[j].first)) ++j;
 
      // if "val" is lower than heap[j], "val" must be stored at index i
      if (_cmp_(new_priority, _heap_[j].first)) break;
 
      // else pull up the jth node
      _heap_[i]                      = std::move(_heap_[j]);
      _indices_[*(_heap_[i].second)] = i;
    }
 
    // update the index of val
    _heap_[i].first  = new_priority;
    _heap_[i].second = val;
    _indices_[*val]  = i;
 
    return i;
  }

References _heap_, and _indices_.

◆ size()

INLINE Size gum::PriorityQueueImplementation< Val, int, std::less< int > >::size ( ) const

noexceptinherited

Returns the number of elements in the priority queue.

Returns: Returns the number of elements in the priority queue.

Definition at line 209 of file priorityQueue_tpl.h.

                                                                                          {
    return _nb_elements_;
  }

◆ top()

INLINE const Val & gum::PriorityQueueImplementation< Val, int, std::less< int > >::top ( ) const

inherited

returns the element at the top of the priority queue

Exceptions

NotFound Raised if the queue is empty

Definition at line 226 of file priorityQueue_tpl.h.

                                                                                      {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }
 
    return *(_heap_[0].second);
  }

References _cmp_, _heap_, and _nb_elements_.

◆ topPriority()

INLINE const int & gum::PriorityQueueImplementation< Val, int, std::less< int > >::topPriority ( ) const

inherited

Returns the priority of the top element.

Returns: Returns the priority of the top element.

Exceptions

NotFound Raised if the queue is empty.

Definition at line 233 of file priorityQueue_tpl.h.

                                                                                {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }
 
    return _heap_[0].first;
  }

References _heap_, and _indices_.

◆ toString()

std::string gum::PriorityQueueImplementation< Val, int, std::less< int > >::toString ( ) const

inherited

Displays the content of the queue.

Returns: Returns the content of the queue.

Definition at line 405 of file priorityQueue_tpl.h.

                                                                                   {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";
 
    for (Size i = 0; i != _nb_elements_; ++i, deja = true) {
      if (deja) stream << " , ";
 
      stream << "(" << _heap_[i].first << " , " << *(_heap_[i].second) << ")";
    }
 
    stream << "]";
 
    return stream.str();
  }

Member Data Documentation

◆ _cmp_

std::less< int > gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::_cmp_

privateinherited

Comparison function.

Definition at line 441 of file priorityQueue.h.

Referenced by eraseTop(), resize(), and top().

◆ _heap_

std::vector< std::pair< int, const Val* > > gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::_heap_

privateinherited

An array storing all the elements of the heap as well as their score.

Definition at line 432 of file priorityQueue.h.

Referenced by PriorityQueueImplementation(), clear(), empty(), eraseTop(), operator[](), pop(), resize(), setPriorityByPos(), top(), and topPriority().

◆ _indices_

HashTable< Val, Size > gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::_indices_

privateinherited

A hashtable for quickly finding the elements by their value.

Definition at line 435 of file priorityQueue.h.

435{HashTableConst::default_size, true, true};

Referenced by PriorityQueueImplementation(), empty(), eraseTop(), operator[](), pop(), resize(), setPriorityByPos(), and topPriority().

◆ _nb_elements_

Size gum::PriorityQueueImplementation< Val, int, std::less< int >, Gen >::_nb_elements_

privateinherited

The number of elements in the heap.

Definition at line 438 of file priorityQueue.h.

438{0};

Referenced by ~PriorityQueueImplementation(), clear(), contains(), empty(), eraseTop(), and top().

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

agrum/base/core/priorityQueue.h
agrum/base/core/priorityQueue_tpl.h

Public Types

Public Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_pointer

◆ const_reference

◆ difference_type

◆ Implementation

◆ pointer

◆ reference

◆ value_type

Constructor & Destructor Documentation

◆ PriorityQueue() [1/4]

◆ PriorityQueue() [2/4]

◆ PriorityQueue() [3/4]

◆ PriorityQueue() [4/4]

◆ ~PriorityQueue()

Member Function Documentation

◆ allValues()

◆ capacity()

◆ clear()

◆ contains()

◆ emplace()

◆ empty()

◆ erase()

◆ eraseByPos()

◆ eraseTop()

◆ insert()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]()

◆ pop()

◆ priority()

◆ priorityByPos()

◆ resize()

◆ setPriority()

◆ setPriorityByPos()

◆ size()

◆ top()

◆ topPriority()

◆ toString()

Member Data Documentation

◆ _cmp_

◆ _heap_

◆ _indices_

◆ _nb_elements_