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.
const_reference	operator[] (const Val &val) const
	returns the "internal" value stored into the queue corresponding to val
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.
optional_ref< const value_type >	tryGet (const Val &key) const
	Returns a pointer to the "internal" value stored into the queue corresponding to val if it exists, or nullptr if val does not exist.
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, bool internal_val=false)
	Removes a given element from the priority queue (but does not return it).
void	setPriority (const Val &elt, const Priority &new_priority, bool internal_val=false)
	Modifies the priority of each instance of a given element.
void	setPriority (const Val &elt, Priority &&new_priority, bool internal_val=false)
	Modifies the priority of each instance of a given element.
const Priority &	priority (const Val &elt, bool internal_val=false) 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 &	getNodeFromInternalValue_ (const Val &val) const
	returns the node in the hash table corresponding to a given internal value
AVLNode &	getNodeFromExternalValue_ (const Val &val) const
	returns the node of the hash table corresponding to a given external value
optional_ref< AVLNode >	tryGetNodeFromExternalValue_ (const Val &val) const
	returns an optional reference on the node of the hash table corresponding to a given external 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 146 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 154 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 152 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 155 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 156 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 157 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 153 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 151 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 158 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 159 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 150 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,
		bool	internal_val = false )

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.
internal_val	This parameter is used for speeding-up computations: when val is an element stored in memory within the queue, we can speed-up computations. In this case, set internal_val to true. Otherwise (internal_val = false), we first search for val within the queue and, once a corresponding value is found, we erase it.

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:

getNodeFromExternalValue_()

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

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

private

returns the node of the hash table corresponding to a given external value

By external value, we mean that the value is not stored into an AVLNode element of the hash table

Exceptions

NotFound

is raised if the node cannot be found

getNodeFromInternalValue_()

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

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

private

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

By internal value, we mean that this is the value stored into an AVLNode element of the hash table

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:

operator[]()

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

const_reference gum::SortedPriorityQueue< Val, Priority, Cmp >::operator[]

(

const Val &

val

)

const

returns the "internal" value stored into the queue corresponding to val

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,
		bool	internal_val = false ) 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.

Parameters

internal_val

This parameter is used for speeding-up computations: when val is an element stored in memory within the queue, we can speed-up computations. In this case, set internal_val to true. Otherwise (internal_val = false), we first search for val within the queue and, once a corresponding value is found, we return its priority

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,
		bool	internal_val = false )

Modifies the priority of each instance of a given element.

Parameters

elt	The value to update.
new_priority	The values new priority.
internal_val	This parameter is used for speeding-up computations: when val is an element stored in memory within the queue, we can speed-up computations. In this case, set internal_val to true. Otherwise (internal_val = false), we first search for val within the queue and, once a corresponding value is found, we change its 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,
		bool	internal_val = false )

Modifies the priority of each instance of a given element.

Parameters

elt	The value to update.
new_priority	The values new priority.
internal_val	This parameter is used for speeding-up computations: when val is an element stored in memory within the queue, we can speed-up computations. In this case, set internal_val to true. Otherwise (internal_val = false), we first search for val within the queue and, once a corresponding value is found, we change its 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 gum::operator<<(), and toString().

Here is the call graph for this function:

Here is the caller graph for this function:

tryGet()

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

optional_ref< const value_type > gum::SortedPriorityQueue< Val, Priority, Cmp >::tryGet ( const Val & key ) const

nodiscard

Returns a pointer to the "internal" value stored into the queue corresponding to val if it exists, or nullptr if val does not exist.

This avoids the double lookup of exists() + operator[].

Parameters

val	The value to search for.

Returns

A pointer to the mapped value, or nullptr if not found.

References tryGet().

Referenced by tryGet().

Here is the call graph for this function:

Here is the caller graph for this function:

tryGetNodeFromExternalValue_()

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

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

private

returns an optional reference on the node of the hash table corresponding to a given external value

By external value, we mean that the value is not stored into an AVLNode element of the hash table

Exceptions

NotFound

is raised if the node cannot be found

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 548 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 545 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 551 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 592 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 594 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 593 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 595 of file sortedPriorityQueue.h.

---

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

• agrum/base/core/sortedPriorityQueue.h