gum::SortedPriorityQueue< Val, Priority, Cmp > Class Template Reference

A priority queue in which we can iterate over the elements from the top to bottom or conversely. More...

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

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

Public Types
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.
using	iterator = SortedPriorityQueueIterator< Val, Priority, Cmp >
	Types for STL compliance.
using	iterator_safe = SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >
	Types for STL compliance.
using	reverse_iterator = SortedPriorityQueueReverseIterator< Val, Priority, Cmp >
	Types for STL compliance.
using	reverse_iterator_safe = SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >
	Types for STL compliance.

Public Member Functions
Constructors / Destructors
	SortedPriorityQueue (Cmp compare=Cmp(), Size capacity=GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY)
	Basic constructor.
	SortedPriorityQueue (std::initializer_list< std::pair< Val, Priority > > list)
	Initializer list constructor.
	SortedPriorityQueue (const SortedPriorityQueue< Val, Priority, Cmp > &from)
	Copy constructor.
	SortedPriorityQueue (SortedPriorityQueue< Val, Priority, Cmp > &&from) noexcept
	Move constructor.
	~SortedPriorityQueue ()
	Class destructor.
Operators
SortedPriorityQueue< Val, Priority, Cmp > &	operator= (const SortedPriorityQueue< Val, Priority, Cmp > &from)
	Copy operator.
SortedPriorityQueue< Val, Priority, Cmp > &	operator= (SortedPriorityQueue< Val, Priority, Cmp > &&from) noexcept
	Move operator.
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 noexcept
	Indicates whether the priority queue contains a given value.
const Val &	top () const
	returns the element at the top of the sorted priority queue
const Val &	bottom () const
	returns the element at the bottom of the sorted priority queue
const Priority &	topPriority () const
	Returns the priority of the top element.
const Priority &	bottomPriority () const
	Returns the priority of the bottom element.
value_type	pop ()
	Removes the top element from the priority queue and return it.
value_type	popTop ()
	Alias of pop.
value_type	popBottom ()
	Removes the bottom element from the priority queue and return it.
const_reference	insert (const Val &val, const Priority &priority)
	Inserts a new (a copy) element in the priority queue.
const_reference	insert (Val &&val, Priority &&priority)
	Inserts (by move) a new element in the priority queue.
template<typename... Args>
const_reference	emplace (Args &&... args)
	Emplace a new element into the priority queue.
void	eraseTop ()
	Removes the top of the priority queue (but does not return it).
void	eraseBottom ()
	Removes the bottom of the priority queue (but does not return it).
void	erase (const Val &val)
	Removes a given element from the priority queue (but does not return it).
void	setPriority (const Val &elt, const Priority &new_priority)
	Modifies the priority of each instance of a given element.
void	setPriority (const Val &elt, Priority &&new_priority)
	Modifies the priority of each instance of a given element.
const Priority &	priority (const Val &elt) const
	Returns the priority of an instance of the value passed in argument.
void	clear ()
	Removes all the elements from the queue.
std::string	toString () const
	Displays the content of the queue.
Iterators
iterator	begin () const
	returns a new iterator pointing to the minimal element of the tree
constexpr const iterator &	end () const
	returns an iterator pointing just after the maximal element
reverse_iterator	rbegin () const
	returns a new iterator pointing to the maximal element of the tree
constexpr const reverse_iterator &	rend () const
	returns an iterator pointing just before the minimal element
iterator_safe	beginSafe ()
	returns a new safe iterator pointing to the minimal element of the tree
constexpr const iterator_safe &	endSafe () const
	returns a safe iterator pointing just after the maximal element
reverse_iterator_safe	rbeginSafe ()
	returns a safe iterator pointing to the maximal element of the tree
constexpr const reverse_iterator_safe &	rendSafe () const
	returns a safe iterator pointing just before the minimal element
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 Member Functions
AVLNode &	getNode_ (const Val &val) const
	returns the node in the hash table corresponding to a given value

Private Attributes
SharedAVLTree< Val, TreeCmp >	_tree_
	A binary search tree storing all the values of the queue.
HashTable< AVLTreeNode< Val >, Priority >	_nodes_ {HashTableConst::default_size, true, true}
	A hashtable for quickly finding the elements by their value.
TreeCmp	_tree_cmp_
	Comparison function.
friend	iterator
	make the iterators access to the AVLNodes
friend	reverse_iterator
friend	iterator_safe
friend	reverse_iterator_safe

Detailed Description

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

A priority queue in which we can iterate over the elements from the top to bottom or conversely.

A sorted priority queue is quite similar to a binary search tree except that a priority (a score) is assigned to each element in the structure. The elements are sorted according to a weak order on theses scores. The priority of any element can be modified at any moment by the user. The sorted priority queue then restores a binary search tree property accordingly. Duplicate elements are not allowed in sorted priority queues.

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
SortedPriorityQueue<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
SortedPriorityQueue<std::string> queue2 = queue1;
 
// initializer list constructor
SortedPriorityQueue<std::string,int> queue3 {
  std::pair<std::string,int>("aa",3),
  std::pair<std::string,int>("bb",2)
};
 
// create a sorted priority queue of strings, the priorities of which are
// pairs of ints
SortedPriorityQueue< 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 instance of element "AAA"
queue1.setPriority ("AAA",100);

Template Parameters

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

Definition at line 139 of file sortedPriorityQueue.h.

Member Typedef Documentation

const_pointer

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

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

Types for STL compliance.

Definition at line 147 of file sortedPriorityQueue.h.

const_reference

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

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

Types for STL compliance.

Definition at line 145 of file sortedPriorityQueue.h.

difference_type

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

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

Types for STL compliance.

Definition at line 148 of file sortedPriorityQueue.h.

iterator

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

using gum::SortedPriorityQueue< Val, Priority, Cmp >::iterator = SortedPriorityQueueIterator< Val, Priority, Cmp >

Types for STL compliance.

Definition at line 149 of file sortedPriorityQueue.h.

iterator_safe

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

using gum::SortedPriorityQueue< Val, Priority, Cmp >::iterator_safe = SortedPriorityQueueIteratorSafe< Val, Priority, Cmp >

Types for STL compliance.

Definition at line 150 of file sortedPriorityQueue.h.

pointer

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

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

Types for STL compliance.

Definition at line 146 of file sortedPriorityQueue.h.

reference

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

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

Types for STL compliance.

Definition at line 144 of file sortedPriorityQueue.h.

reverse_iterator

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

using gum::SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator = SortedPriorityQueueReverseIterator< Val, Priority, Cmp >

Types for STL compliance.

Definition at line 151 of file sortedPriorityQueue.h.

reverse_iterator_safe

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

using gum::SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator_safe = SortedPriorityQueueReverseIteratorSafe< Val, Priority, Cmp >

Types for STL compliance.

Definition at line 152 of file sortedPriorityQueue.h.

value_type

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

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

Types for STL compliance.

Definition at line 143 of file sortedPriorityQueue.h.

Constructor & Destructor Documentation

SortedPriorityQueue() [1/4]

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

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

explicit

Basic constructor.

Creates an empty sorted 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)

References capacity(), and GUM_PRIORITY_QUEUE_DEFAULT_CAPACITY.

Referenced by SortedPriorityQueue(), SortedPriorityQueue(), ~SortedPriorityQueue(), operator=(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

SortedPriorityQueue() [2/4]

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

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

explicit

Initializer list constructor.

The elements of the initializer list are pairs <Val,Priority>.

Parameters

list	The initializer list.

SortedPriorityQueue() [3/4]

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

gum::SortedPriorityQueue< Val, Priority, Cmp >::SortedPriorityQueue

(

const SortedPriorityQueue< Val, Priority, Cmp > &

from

)

Copy constructor.

Parameters

from	The gum::SortedPriorityQueue to copy.

References SortedPriorityQueue().

Here is the call graph for this function:

SortedPriorityQueue() [4/4]

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

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

noexcept

Move constructor.

Parameters

from	The gum::SortedPriorityQueue to move.

References SortedPriorityQueue().

Here is the call graph for this function:

~SortedPriorityQueue()

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

gum::SortedPriorityQueue< Val, Priority, Cmp >::~SortedPriorityQueue

(

)

Class destructor.

References SortedPriorityQueue().

Here is the call graph for this function:

Member Function Documentation

begin()

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

iterator gum::SortedPriorityQueue< Val, Priority, Cmp >::begin

(

)

const

returns a new iterator pointing to the minimal element of the tree

References begin().

Referenced by begin().

Here is the call graph for this function:

Here is the caller graph for this function:

beginSafe()

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

iterator_safe gum::SortedPriorityQueue< Val, Priority, Cmp >::beginSafe

(

)

returns a new safe iterator pointing to the minimal element of the tree

References beginSafe().

Referenced by beginSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

bottom()

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

const Val & gum::SortedPriorityQueue< Val, Priority, Cmp >::bottom

(

)

const

returns the element at the bottom of the sorted priority queue

Exceptions

NotFound

Raised if the queue is empty

References bottom().

Referenced by bottom().

Here is the call graph for this function:

Here is the caller graph for this function:

bottomPriority()

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

const Priority & gum::SortedPriorityQueue< Val, Priority, Cmp >::bottomPriority

(

)

const

Returns the priority of the bottom element.

Returns

Returns the priority of the bottom element.

Exceptions

NotFound

Raised if the queue is empty.

References bottomPriority().

Referenced by bottomPriority().

Here is the call graph for this function:

Here is the caller graph for this function:

capacity()

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

Size gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References capacity().

Referenced by SortedPriorityQueue(), and capacity().

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::clear

(

)

Removes all the elements from the queue.

References clear().

Referenced by clear().

Here is the call graph for this function:

Here is the caller graph for this function:

contains()

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

bool gum::SortedPriorityQueue< Val, Priority, Cmp >::contains ( const Val & val ) const

noexcept

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.

References contains().

Referenced by contains().

Here is the call graph for this function:

Here is the caller graph for this function:

emplace()

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

template<typename... Args>

const_reference gum::SortedPriorityQueue< Val, Priority, Cmp >::emplace

(

Args &&...

args

)

Emplace a new element into the priority queue.

Template Parameters

Args	The emplace arguments types.

Parameters

args	The emplace arguments.

Returns

Returns a reference on the value stored into the queue.

Exceptions

DuplicateElement

Raised if the element already exists.

References emplace().

Referenced by emplace().

Here is the call graph for this function:

Here is the caller graph for this function:

empty()

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

bool gum::SortedPriorityQueue< Val, Priority, Cmp >::empty ( ) const

noexcept

Indicates whether the priority queue is empty.

Returns

Returns true if the priority queue is empty.

References empty().

Referenced by empty().

Here is the call graph for this function:

Here is the caller graph for this function:

end()

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

const iterator & gum::SortedPriorityQueue< Val, Priority, Cmp >::end ( ) const

constexpr

returns an iterator pointing just after the maximal element

References end().

Referenced by end().

Here is the call graph for this function:

Here is the caller graph for this function:

endSafe()

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

const iterator_safe & gum::SortedPriorityQueue< Val, Priority, Cmp >::endSafe ( ) const

constexpr

returns a safe iterator pointing just after the maximal element

References endSafe().

Referenced by endSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

erase()

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

Parameters

val	the element we wish to remove.

References erase().

Referenced by erase().

Here is the call graph for this function:

Here is the caller graph for this function:

eraseBottom()

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::eraseBottom

(

)

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

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

References eraseBottom().

Referenced by eraseBottom().

Here is the call graph for this function:

Here is the caller graph for this function:

eraseTop()

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::eraseTop

(

)

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

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

References eraseTop().

Referenced by eraseTop().

Here is the call graph for this function:

Here is the caller graph for this function:

getNode_()

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

AVLNode & gum::SortedPriorityQueue< Val, Priority, Cmp >::getNode_ ( const Val & val ) const

private

returns the node in the hash table corresponding to a given value

Exceptions

NotFound

is raised if the node cannot be found

insert() [1/2]

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

const_reference gum::SortedPriorityQueue< Val, Priority, Cmp >::insert	(	const Val &	val,
		const Priority &	priority )

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

Parameters

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

Returns

Returns a reference on the value stored into the queue.

Exceptions

DuplicateElement

Raised if the element already exists.

References insert(), and priority().

Referenced by insert(), and insert().

Here is the call graph for this function:

Here is the caller graph for this function:

insert() [2/2]

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

const_reference gum::SortedPriorityQueue< Val, Priority, Cmp >::insert	(	Val &&	val,
		Priority &&	priority )

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

Parameters

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

Returns

Returns a reference on the value stored into the queue.

Exceptions

DuplicateElement

Raised if the element already exists.

References insert(), and priority().

Here is the call graph for this function:

operator=() [1/2]

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

SortedPriorityQueue< Val, Priority, Cmp > & gum::SortedPriorityQueue< Val, Priority, Cmp >::operator=

(

const SortedPriorityQueue< 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 queue stays in a coherent state. Actually, the priority queue becomes empty. An exception is then thrown.

Parameters

from	The gum::SortedPriorityQueue to copy.

Returns

Returns this gum::SortedPriorityQueue.

References SortedPriorityQueue().

Here is the call graph for this function:

operator=() [2/2]

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

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

noexcept

Move operator.

Parameters

from	The gum::SortedPriorityQueue to move.

Returns

Returns this gum::SortedPriorityQueue.

References SortedPriorityQueue().

Here is the call graph for this function:

pop()

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

value_type gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References pop().

Referenced by pop().

Here is the call graph for this function:

Here is the caller graph for this function:

popBottom()

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

value_type gum::SortedPriorityQueue< Val, Priority, Cmp >::popBottom

(

)

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

Returns

Returns the bottom element from the priority queue.

Exceptions

NotFound

Raised if the queue is empty.

References popBottom().

Referenced by popBottom().

Here is the call graph for this function:

Here is the caller graph for this function:

popTop()

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

value_type gum::SortedPriorityQueue< Val, Priority, Cmp >::popTop

(

)

Alias of pop.

Returns

Returns the top element from the priority queue.

Exceptions

NotFound

Raised if the queue is empty.

References popTop().

Referenced by popTop().

Here is the call graph for this function:

Here is the caller graph for this function:

priority()

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

const Priority & gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References priority().

Referenced by insert(), insert(), and priority().

Here is the call graph for this function:

Here is the caller graph for this function:

rbegin()

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

reverse_iterator gum::SortedPriorityQueue< Val, Priority, Cmp >::rbegin

(

)

const

returns a new iterator pointing to the maximal element of the tree

References rbegin().

Referenced by rbegin().

Here is the call graph for this function:

Here is the caller graph for this function:

rbeginSafe()

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

reverse_iterator_safe gum::SortedPriorityQueue< Val, Priority, Cmp >::rbeginSafe

(

)

returns a safe iterator pointing to the maximal element of the tree

References rbeginSafe().

Referenced by rbeginSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

rend()

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

const reverse_iterator & gum::SortedPriorityQueue< Val, Priority, Cmp >::rend ( ) const

constexpr

returns an iterator pointing just before the minimal element

References rend().

Referenced by rend().

Here is the call graph for this function:

Here is the caller graph for this function:

rendSafe()

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

const reverse_iterator_safe & gum::SortedPriorityQueue< Val, Priority, Cmp >::rendSafe ( ) const

constexpr

returns a safe iterator pointing just before the minimal element

References rendSafe().

Referenced by rendSafe().

Here is the call graph for this function:

Here is the caller graph for this function:

resize()

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::resize

(

Size

new_size

)

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

Parameters

new_size

The internal structure new size.

References resize().

Referenced by resize().

Here is the call graph for this function:

Here is the caller graph for this function:

setPriority() [1/2]

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References setPriority().

Referenced by setPriority(), and setPriority().

Here is the call graph for this function:

Here is the caller graph for this function:

setPriority() [2/2]

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

void gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References setPriority().

Here is the call graph for this function:

size()

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

Size gum::SortedPriorityQueue< Val, Priority, Cmp >::size ( ) const

noexcept

Returns the number of elements in the priority queue.

Returns

Returns the number of elements in the priority queue.

top()

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

const Val & gum::SortedPriorityQueue< Val, Priority, Cmp >::top

(

)

const

returns the element at the top of the sorted priority queue

Exceptions

NotFound

Raised if the queue is empty

References top().

Referenced by top().

Here is the call graph for this function:

Here is the caller graph for this function:

topPriority()

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

const Priority & gum::SortedPriorityQueue< Val, Priority, Cmp >::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.

References topPriority().

Referenced by topPriority().

Here is the call graph for this function:

Here is the caller graph for this function:

toString()

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

std::string gum::SortedPriorityQueue< Val, Priority, Cmp >::toString

(

)

const

Displays the content of the queue.

Returns

Returns the content of the queue.

References toString().

Referenced by toString().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

_nodes_

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

HashTable< AVLTreeNode< Val >, Priority > gum::SortedPriorityQueue< Val, Priority, Cmp >::_nodes_ {HashTableConst::default_size, true, true}

private

A hashtable for quickly finding the elements by their value.

Definition at line 513 of file sortedPriorityQueue.h.

{HashTableConst::default_size, true, true};

_tree_

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

SharedAVLTree< Val, TreeCmp > gum::SortedPriorityQueue< Val, Priority, Cmp >::_tree_

private

A binary search tree storing all the values of the queue.

Basically, the tree does not store the priorities which are used to sort its nodes. However, these nodes are guaranteed to be the first element of the HashElt elements stored into the hash table. As such, using basic pointer arithmetic, we can determine where the priority associated with a value is located in memory. In addition, it is just after the value, which means that it has a high probability to be already in the CPU cache, so jumping from a value to a priority should be fast.

Definition at line 510 of file sortedPriorityQueue.h.

_tree_cmp_

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

TreeCmp gum::SortedPriorityQueue< Val, Priority, Cmp >::_tree_cmp_

private

Comparison function.

Definition at line 516 of file sortedPriorityQueue.h.

iterator

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

friend gum::SortedPriorityQueue< Val, Priority, Cmp >::iterator

private

make the iterators access to the AVLNodes

Definition at line 537 of file sortedPriorityQueue.h.

iterator_safe

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

friend gum::SortedPriorityQueue< Val, Priority, Cmp >::iterator_safe

private

Definition at line 539 of file sortedPriorityQueue.h.

reverse_iterator

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

friend gum::SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator

private

Definition at line 538 of file sortedPriorityQueue.h.

reverse_iterator_safe

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

friend gum::SortedPriorityQueue< Val, Priority, Cmp >::reverse_iterator_safe

private

Definition at line 540 of file sortedPriorityQueue.h.

---

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

• agrum/base/core/sortedPriorityQueue.h