gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > Class Template Reference

The internal class for representing priority queues. More...

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

Collaboration diagram for gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >:

Public Member Functions
template<typename... Args>
INLINE Size	emplace (Args &&... args)
template<typename Val, typename Priority, typename Cmp, typename Alloc>
	PriorityQueueImplementation (const PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true > &from)
template<typename OtherAlloc >
	PriorityQueueImplementation (const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, true > &from)
template<typename Val, typename Priority, typename Cmp, typename Alloc>
	PriorityQueueImplementation (PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true > &&from)
template<typename OtherAlloc >
PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true > &	operator= (const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, true > &from)
Operators
PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &	operator= (const PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &from)
	Copy operator. More...
template<typename OtherAlloc >
PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &	operator= (const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, Gen > &from)
	Generalized copy operator. More...
PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &	operator= (PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &&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...
void	setPriority (const Val &elt, 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...
const Priority &	priorityByPos (Size index) const
	Returns the priority of the value passed in argument. More...
void	clear ()
	Removes all the elements from the queue. More...
const HashTable< Val, Size > &	allValues () const noexcept
	Returns a 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
	Returns 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	IndexAllocator = typename Alloc::template rebind< std::pair< Val, Size > >::other
using	HeapAllocator = typename Alloc::template rebind< std::pair< Priority, const Val *> >::other
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
class	PriorityQueue< Val, Priority, Cmp, Alloc >
	All gum::PriorityQueue are friends with themselves. More...
template<typename V , typename P , typename C , typename A , bool g>
class	PriorityQueueImplementation
	All gum::PriorityQueueImplementation are friends with themselves. More...

Detailed Description

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>
class gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >

The internal class for representing priority queues.

Priority Queues have different implementations depending on the nature of the values they store. Basically, scalar values can lead to optimization of the code whereas general types like classes cannot. The current class is used for general types (and therefore for classes). The user shall not use directly the implementation but rather use the PriorityQueue class. The latter will be assigned the best implementation at compile time.

Template Parameters

Val	The values type.
Priority	The priorities type.
Cmp	The priorities comparator.
Alloc	The values allocator.
Gen	Used for metaprogramation, for scalar and non-scalar priority queues.

Definition at line 79 of file priorityQueue.h.

Member Typedef Documentation

allocator_type

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::allocator_type = Alloc

Types for STL compliance.

Definition at line 96 of file priorityQueue.h.

const_pointer

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::const_pointer = const Val*

Types for STL compliance.

Definition at line 94 of file priorityQueue.h.

const_reference

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::const_reference = const Val&

Types for STL compliance.

Definition at line 92 of file priorityQueue.h.

difference_type

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 95 of file priorityQueue.h.

HeapAllocator

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::HeapAllocator = typename Alloc::template rebind< std::pair< Priority, const Val* > >::other

Definition at line 104 of file priorityQueue.h.

IndexAllocator

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::IndexAllocator = typename Alloc::template rebind< std::pair< Val, Size > >::other

Definition at line 100 of file priorityQueue.h.

pointer

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::pointer = Val*

Types for STL compliance.

Definition at line 93 of file priorityQueue.h.

reference

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::reference = Val&

Types for STL compliance.

Definition at line 91 of file priorityQueue.h.

value_type

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

using gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::value_type = Val

Types for STL compliance.

Definition at line 90 of file priorityQueue.h.

Constructor & Destructor Documentation

PriorityQueueImplementation() [1/8]

template<typename Val , typename Priority , typename Cmp, typename Alloc >

INLINE gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::PriorityQueueImplementation ( Cmp  compare, Size  capacity  )

explicitprivate

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

                    :
      _indices_(capacity >> 1, true, true),
      _cmp_(compare) {
    _heap_.reserve(capacity);

    GUM_CONSTRUCTOR(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [2/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc >

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::PriorityQueueImplementation ( std::initializer_list< std::pair< Val, Priority > >  list )

explicitprivate

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

                                                           :
      _indices_(Size(list.size()) / 2, true, true) {
    // fill the queue
    _heap_.reserve(list.size());
    for (const auto& elt: list) {
      insert(elt.first, elt.second);
    }

    GUM_CONSTRUCTOR(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [3/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation ( const PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &  from )

private

Copy constructor.

Parameters

from	The gum::PriorityQueueImplementation to copy.

Definition at line 65 of file priorityQueue_tpl.h.

                                                                                :
      _heap_(from._heap_),
      _indices_(from._indices_), _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    // fill the heap structure
    for (const auto& elt: _indices_) {
      _heap_[elt.second].second = &(elt.first);
    }

    GUM_CONS_CPY(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [4/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc , bool Gen>

template<typename OtherAlloc >

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation ( const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, Gen > &  from )

private

Generalized copy constructor.

Template Parameters

OtherAlloc

The other gum::PriorityQueueImplementation allocator.

Parameters

from	The gum::PriorityQueueImplementation to copy.

Definition at line 80 of file priorityQueue_tpl.h.

                                                                                     :
      _indices_(from._indices_),
      _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    // fill the heap structure
    if (_nb_elements_) {
      _heap_.reserve(from._heap_.size());
      for (const auto& elt: from._heap_) {
        _heap_.push_back(elt);
      }
      for (const auto& elt: _indices_) {
        _heap_[elt.second].second = &(elt.first);
      }
    }

    GUM_CONS_CPY(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [5/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation ( PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &&  from )

private

Move constructor.

Parameters

from	The gum::PriorityQueueImplementation to move.

Definition at line 100 of file priorityQueue_tpl.h.

                                                                           :
      _heap_(std::move(from._heap_)),
      _indices_(std::move(from._indices_)), _nb_elements_(std::move(from._nb_elements_)),
      _cmp_(std::move(from._cmp_)) {
    GUM_CONS_MOV(PriorityQueueImplementation)
  }

~PriorityQueueImplementation()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::~PriorityQueueImplementation ( )

private

Class destructor.

Definition at line 110 of file priorityQueue_tpl.h.

                                                                                              {
    GUM_DESTRUCTOR(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [6/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename Val, typename Priority, typename Cmp, typename Alloc>

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation

(

const PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true > &

from

)

Definition at line 600 of file priorityQueue_tpl.h.

                                                                                 :
      _heap_(from._heap_),
      _indices_(from._indices_), _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    // for debugging purposes
    GUM_CONS_CPY(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [7/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename OtherAlloc >

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation

(

const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, true > &

from

)

Definition at line 611 of file priorityQueue_tpl.h.

                                                                                      :
      _indices_(from._indices_),
      _nb_elements_(from._nb_elements_), _cmp_(from._cmp_) {
    // fill the heap structure
    if (_nb_elements_) {
      _heap_.reserve(from._heap_.size());
      for (const auto& elt: from._heap_) {
        _heap_.push_back(elt);
      }
    }

    // for debugging purposes
    GUM_CONS_CPY(PriorityQueueImplementation);
  }

PriorityQueueImplementation() [8/8]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename Val, typename Priority, typename Cmp, typename Alloc>

gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::PriorityQueueImplementation

(

PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true > &&

from

)

Definition at line 629 of file priorityQueue_tpl.h.

                                                                            :
      _heap_(std::move(from._heap_)),
      _indices_(std::move(from._indices_)), _nb_elements_(std::move(from._nb_elements_)),
      _cmp_(std::move(from._cmp_)) {
    // for debugging purposes
    GUM_CONS_MOV(PriorityQueueImplementation);
  }

Member Function Documentation

allValues()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const HashTable< Val, Size > & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::allValues ( ) const

noexcept

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

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

capacity()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::capacity ( ) const

noexcept

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

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

clear()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE void gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::clear

(

)

Removes all the elements from the queue.

Definition at line 244 of file priorityQueue_tpl.h.

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

contains()

template<typename Val, typename Priority , typename Cmp , typename Alloc , bool Gen>

INLINE bool gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::contains

(

const Val &

val

)

const

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

                                                                                                 {
    return _indices_.exists(val);
  }

emplace() [1/2]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename... Args>

Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::emplace

(

Args &&...

args

)

Emplace a new element into the priority queue.

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

Template Parameters

Args	The emplace arguments types.

Parameters

args	The emplace arguments.

Returns

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

Exceptions

DuplicateElement

Raised if the element already exists.

emplace() [2/2]

template<typename Val , typename Priority , typename Cmp , typename Alloc >

template<typename... Args>

INLINE Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::emplace

(

Args &&...

args

)

Definition at line 394 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()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE bool gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::empty ( ) const

noexcept

Indicates whether the priority queue is empty.

Returns

Returns true if the priority queue is empty.

Definition at line 403 of file priorityQueue_tpl.h.

                                                                                         {
    return (_nb_elements_ == 0);
  }

erase()

template<typename Val, typename Priority , typename Cmp , typename Alloc , bool Gen>

INLINE void gum::PriorityQueueImplementation< 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

val	the element we wish to remove.

Definition at line 287 of file priorityQueue_tpl.h.

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

eraseByPos()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

void gum::PriorityQueueImplementation< 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

index

represents the position of the element to be removed.

Definition at line 252 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()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE void gum::PriorityQueueImplementation< 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 295 of file priorityQueue_tpl.h.

                                                                                      {
    eraseByPos(0);
  }

insert() [1/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc , bool Gen>

INLINE Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::insert	(	const Val &	val,
		const Priority &	priority
	)

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 319 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, IndexAllocator >::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;
  }

insert() [2/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc , bool Gen>

INLINE Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::insert	(	Val &&	val,
		Priority &&	priority
	)

Inserts (by move) a new 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 356 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, IndexAllocator >::value_type& new_elt
       = _indices_.insert(std::move(val), 0);

    try {
      _heap_.push_back(std::pair< Priority, const Val* >(std::move(priority), &(new_elt.first)));
    } catch (...) {
      _indices_.erase(new_elt.first);
      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/4]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=

(

const PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &

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::PriorityQueueImplementation to copy.

Returns

Returns this gum::PriorityQueueImplementation.

Definition at line 117 of file priorityQueue_tpl.h.

                                                                                   {
    // avoid self assignment
    if (this != &from) {
      GUM_OP_CPY(PriorityQueueImplementation)

      try {
        // set the comparison function
        _cmp_ = from._cmp_;

        // copy the indices and the heap
        _indices_     = from._indices_;
        _heap_        = from._heap_;
        _nb_elements_ = from._nb_elements_;

        // restore the link between  _indices_ and  _heap_
        for (const auto& elt: _indices_) {
          _heap_[elt.second].second = &(elt.first);
        }
      } catch (...) {
        _heap_.clear();
        _indices_.clear();
        _nb_elements_ = 0;

        throw;
      }
    }

    return *this;
  }

operator=() [2/4]

template<typename Val, typename Priority, typename Cmp, typename Alloc , bool Gen>

template<typename OtherAlloc >

PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=

(

const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, Gen > &

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.

Template Parameters

OtherAlloc

The other gum::PriorityQueueImplementation allocator.

Parameters

from	The gum::PriorityQueueImplementation to copy.

Returns

Returns this gum::PriorityQueueImplementation.

Definition at line 152 of file priorityQueue_tpl.h.

                                                                                        {
    GUM_OP_CPY(PriorityQueueImplementation);

    try {
      // set the comprison function
      _cmp_ = from._cmp_;

      // copy the indices and the heap
      _indices_     = from._indices_;
      _nb_elements_ = from._nb_elements_;

      _heap_.clear();
      if (_nb_elements_) {
        _heap_.reserve(from._heap_.size());
        for (const auto& elt: from._heap_) {
          _heap_.push_back(elt);
        }
        for (const auto& elt: _indices_) {
          _heap_[elt.second].second = &(elt.first);
        }
      }
    } catch (...) {
      _heap_.clear();
      _indices_.clear();
      _nb_elements_ = 0;

      throw;
    }

    return *this;
  }

operator=() [3/4]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

INLINE PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=

(

PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen > &&

from

)

Move operator.

Parameters

from	The gum::PriorityQueueImplementation to move.

Returns

Returns this gum::PriorityQueueImplementation.

Definition at line 188 of file priorityQueue_tpl.h.

                                                                              {
    // avoid self assignment
    if (this != &from) {
      GUM_OP_MOV(PriorityQueueImplementation)

      _indices_     = std::move(from._indices_);
      _heap_        = std::move(from._heap_);
      _cmp_         = std::move(from._cmp_);
      _nb_elements_ = std::move(from._nb_elements_);
    }

    return *this;
  }

operator=() [4/4]

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename OtherAlloc >

PriorityQueueImplementation< Val, Priority, Cmp, Alloc, true >& gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::operator=

(

const PriorityQueueImplementation< Val, Priority, Cmp, OtherAlloc, true > &

from

)

Definition at line 679 of file priorityQueue_tpl.h.

                                                                                         {
    // for debugging purposes
    GUM_OP_CPY(PriorityQueueImplementation);

    try {
      // set the comprison function
      _cmp_ = from._cmp_;

      // copy the indices and the heap
      _indices_     = from._indices_;
      _nb_elements_ = from._nb_elements_;

      _heap_.clear();
      if (_nb_elements_) {
        _heap_.reserve(from._heap_.size());
        for (const auto& elt: from._heap_) {
          _heap_.push_back(elt);
        }
      }
    } catch (...) {
      _heap_.clear();
      _indices_.clear();
      _nb_elements_ = 0;

      throw;
    }

    return *this;
  }

operator[]()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Val & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::operator[]

(

Size

index_elt

)

const

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

                                                                                               {
    if (index >= _nb_elements_) {
      GUM_ERROR(NotFound, "not enough elements in the PriorityQueueImplementation")
    }

    return *(_heap_[index].second);
  }

pop()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Val gum::PriorityQueueImplementation< 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

NotFound

Raised if the queue is empty.

Definition at line 301 of file priorityQueue_tpl.h.

                                                                                {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }

    Val v = *(_heap_[0].second);
    eraseByPos(0);

    return v;
  }

priority()

template<typename Val, typename Priority , typename Cmp , typename Alloc , bool Gen>

INLINE const Priority & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::priority

(

const Val &

elt

)

const

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

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

priorityByPos()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Priority & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::priorityByPos

(

Size

index

)

const

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

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

resize()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE void gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::resize

(

Size

new_size

)

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

Parameters

new_size

The internal structure new size.

Definition at line 235 of file priorityQueue_tpl.h.

                                                                                                 {
    if (new_size < _nb_elements_) return;

    _heap_.reserve(new_size);
    _indices_.resize(new_size / 2);
  }

setPriority() [1/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc , bool Gen>

void gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::setPriority	(	const Val &	elt,
		const Priority &	new_priority
	)

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

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

setPriority() [2/2]

template<typename Val, typename Priority, typename Cmp , typename Alloc , bool Gen>

void gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::setPriority	(	const Val &	elt,
		Priority &&	new_priority
	)

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

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

setPriorityByPos() [1/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >

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

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 445 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;
  }

setPriorityByPos() [2/2]

template<typename Val , typename Priority, typename Cmp , typename Alloc >

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

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 489 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  = std::move(new_priority);
    _heap_[i].second = val;
    _indices_[*val]  = i;

    return i;
  }

size()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE Size gum::PriorityQueueImplementation< 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 222 of file priorityQueue_tpl.h.

                                                                                                 {
    return _nb_elements_;
  }

top()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Val & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::top

(

)

const

returns the element at the top of the priority queue

Exceptions

NotFound

Raised if the queue is empty

Definition at line 205 of file priorityQueue_tpl.h.

                                                                                             {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }

    return *(_heap_[0].second);
  }

topPriority()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

INLINE const Priority & gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::topPriority

(

)

const

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

                                                                                                {
    if (!_nb_elements_) { GUM_ERROR(NotFound, "empty priority queue") }

    return _heap_[0].first;
  }

toString()

template<typename Val , typename Priority , typename Cmp , typename Alloc >

std::string gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc >::toString

(

)

const

Displays the content of the queue.

Returns

Returns the content of the queue.

Definition at line 427 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();
  }

Friends And Related Function Documentation

PriorityQueueImplementation

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

template<typename V , typename P , typename C , typename A , bool g>

friend class PriorityQueueImplementation

friend

All gum::PriorityQueueImplementation are friends with themselves.

Definition at line 85 of file priorityQueue.h.

PriorityQueue< Val, Priority, Cmp, Alloc >

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

friend class PriorityQueue< Val, Priority, Cmp, Alloc >

friend

All gum::PriorityQueue are friends with themselves.

Definition at line 81 of file priorityQueue.h.

Member Data Documentation

_cmp_

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

Cmp gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::_cmp_

private

Comparison function.

Definition at line 459 of file priorityQueue.h.

_heap_

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

std::vector< std::pair< Priority, const Val* >, HeapAllocator > gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::_heap_

private

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

Definition at line 450 of file priorityQueue.h.

_indices_

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

HashTable< Val, Size, IndexAllocator > gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::_indices_ {HashTableConst::default_size, true, true}

private

A hashtable for quickly finding the elements by their value.

Definition at line 453 of file priorityQueue.h.

_nb_elements_

template<typename Val, typename Priority, typename Cmp, typename Alloc, bool Gen>

Size gum::PriorityQueueImplementation< Val, Priority, Cmp, Alloc, Gen >::_nb_elements_ {0}

private

The number of elements in the heap.

Definition at line 456 of file priorityQueue.h.

---

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

• agrum/tools/core/priorityQueue.h
• agrum/tools/core/priorityQueue_tpl.h