Priority queue interface wrapper for heaps. More...

#include <ogdf/basic/PriorityQueue.h>

Inheritance diagram for ogdf::PriorityQueue< T, C, Impl >:

Public Types
using	const_reference = const value_type &

using	handle = typename SpecImpl::Handle

using	reference = value_type &

using	size_type = std::size_t

using	value_type = T

Public Member Functions
	PriorityQueue (const C &cmp=C(), int initialSize=128)
	Creates empty priority queue. More...

	PriorityQueue (const PriorityQueue &other)
	Copy constructor. More...

template<class InputIt >
	PriorityQueue (InputIt first, InputIt last, const C &cmp=C())
	Creates priority queue with contents of the given range. More...

	PriorityQueue (PriorityQueue &&other)
	Move constructor. More...

	PriorityQueue (std::initializer_list< value_type > init, const C &cmp=C())
	Creates priority queue with contents of the given initializer list. More...

	~PriorityQueue ()
	Destroys the underlying data structure. More...

void	clear ()
	Removes all the entries from the queue. More...

const C &	comparator () const
	Returns the comparator used for ordering elements. More...

void	decrease (handle pos, const T &value)
	Decreases value of the element specified by `handle` to `value`. More...

bool	empty () const
	Checks whether the queue is empty. More...

void	merge (PriorityQueue &other)
	Merges in enqueued values of `other` queue. More...

PriorityQueue &	operator= (PriorityQueue other)
	Copy and move assignment. More...

PriorityQueue &	operator= (std::initializer_list< value_type > ilist)
	Assigns the priority queue contents of the given initializer list. More...

void	pop ()
	Removes the top element from the heap. More...

handle	push (const value_type &value)
	Inserts a new element with given `value` into the queue. More...

template<class InputIt >
void	push (InputIt first, InputIt last)
	Inserts new elements specified by the given range. More...

void	push (std::initializer_list< value_type > ilist)
	Inserts new elements specified by the given initializer list. More...

size_type	size () const
	Returns the number of enqueued elements. More...

void	swap (PriorityQueue &other)
	Swaps the contents. More...

const T &	top () const
	Returns reference to the top element in the queue. More...

const T &	value (handle pos) const
	Returns the priority of that handle. More...

Private Types
using	SpecImpl = Impl< T, C >

Private Attributes
SpecImpl *	m_impl
	Underlying heap data structure. More...

size_type	m_size
	Number of entries. More...

Friends
void	swap (PriorityQueue &a, PriorityQueue &b)
	Swaps the contents. More...

Detailed Description

template<typename T, class C = std::less<T>, template< typename, class > class Impl = PairingHeap>
class ogdf::PriorityQueue< T, C, Impl >

Priority queue interface wrapper for heaps.

Priority queue offers interface similar to the STL's std::priority_queue class but allows to choose from variety of different data structures to be used as underlying implementation. Also, unlike STL's version it provides extra methods for fast decreasing key of given element and merging-in other priority queue.

Template Parameters

T	Denotes value type of inserted elements.
C	Denotes comparison functor determining value ordering.
Impl	Denotes underlying heap class.

Definition at line 62 of file PriorityQueue.h.

Member Typedef Documentation

◆ const_reference

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::const_reference = const value_type&

Definition at line 75 of file PriorityQueue.h.

◆ handle

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::handle = typename SpecImpl::Handle

Definition at line 73 of file PriorityQueue.h.

◆ reference

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::reference = value_type&

Definition at line 74 of file PriorityQueue.h.

◆ size_type

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::size_type = std::size_t

Definition at line 64 of file PriorityQueue.h.

◆ SpecImpl

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::SpecImpl = Impl<T, C>

private

Definition at line 68 of file PriorityQueue.h.

◆ value_type

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

using ogdf::PriorityQueue< T, C, Impl >::value_type = T

Definition at line 72 of file PriorityQueue.h.

Constructor & Destructor Documentation

◆ PriorityQueue() [1/5]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

ogdf::PriorityQueue< T, C, Impl >::PriorityQueue	(	const C &	cmp = `C()`,
		int	initialSize = `128`
	)

inlineexplicit

Creates empty priority queue.

Parameters

cmp	Comparison functor determining priority ordering.
initialSize	The initial capacity preference (ignored if not supported by underlying heap).

Definition at line 82 of file PriorityQueue.h.

◆ PriorityQueue() [2/5]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

ogdf::PriorityQueue< T, C, Impl >::PriorityQueue ( const PriorityQueue< T, C, Impl > & other )

inline

Copy constructor.

Definition at line 86 of file PriorityQueue.h.

◆ PriorityQueue() [3/5]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

ogdf::PriorityQueue< T, C, Impl >::PriorityQueue ( PriorityQueue< T, C, Impl > && other )

inline

Move constructor.

Definition at line 90 of file PriorityQueue.h.

◆ PriorityQueue() [4/5]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

template<class InputIt >

ogdf::PriorityQueue< T, C, Impl >::PriorityQueue	(	InputIt	first,
		InputIt	last,
		const C &	cmp = `C()`
	)

inline

Creates priority queue with contents of the given range.

Parameters

first	Begin iterator of the initializing range.
last	Past-the-end iterator of the initializing range.
cmp	Comparison functor determining priority ordering.

Definition at line 101 of file PriorityQueue.h.

◆ PriorityQueue() [5/5]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

ogdf::PriorityQueue< T, C, Impl >::PriorityQueue	(	std::initializer_list< value_type >	init,
		const C &	cmp = `C()`
	)

inline

Creates priority queue with contents of the given initializer list.

Parameters

init	List whose elements should be used during initalization.
cmp	Comparison functor determining priority ordering.

Definition at line 110 of file PriorityQueue.h.

◆ ~PriorityQueue()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

ogdf::PriorityQueue< T, C, Impl >::~PriorityQueue ( )

inline

Destroys the underlying data structure.

Definition at line 114 of file PriorityQueue.h.

Member Function Documentation

◆ clear()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::clear ( )

inline

Removes all the entries from the queue.

Definition at line 205 of file PriorityQueue.h.

◆ comparator()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

const C& ogdf::PriorityQueue< T, C, Impl >::comparator ( ) const

inline

Returns the comparator used for ordering elements.

Definition at line 225 of file PriorityQueue.h.

◆ decrease()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::decrease	(	handle	pos,
		const T &	value
	)

inline

Decreases value of the element specified by handle to value.

Behaviour of this function is undefined if handle does not belong to a the queue or new value is greater than old one.

Parameters

pos	A element for which the value is to be decreased.
value	A new value for the node.

Definition at line 190 of file PriorityQueue.h.

◆ empty()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

bool ogdf::PriorityQueue< T, C, Impl >::empty ( ) const

inline

Checks whether the queue is empty.

Definition at line 211 of file PriorityQueue.h.

◆ merge()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::merge ( PriorityQueue< T, C, Impl > & other )

inline

Merges in enqueued values of other queue.

After merge other queue becomes empty and is valid for further usage.

Parameters

other A queue to be merged in.

Definition at line 198 of file PriorityQueue.h.

◆ operator=() [1/2]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

PriorityQueue& ogdf::PriorityQueue< T, C, Impl >::operator= ( PriorityQueue< T, C, Impl > other )

inline

Copy and move assignment.

Definition at line 117 of file PriorityQueue.h.

◆ operator=() [2/2]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

PriorityQueue& ogdf::PriorityQueue< T, C, Impl >::operator= ( std::initializer_list< value_type > ilist )

inline

Assigns the priority queue contents of the given initializer list.

Parameters

ilist List whose elements should be assigned.

Returns: Reference to the assigned priority queue.

Definition at line 127 of file PriorityQueue.h.

◆ pop()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::pop ( )

inline

Removes the top element from the heap.

Behaviour of this function is undefined if the heap is empty.

Definition at line 177 of file PriorityQueue.h.

◆ push() [1/3]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

handle ogdf::PriorityQueue< T, C, Impl >::push ( const value_type & value )

inline

Inserts a new element with given value into the queue.

Definition at line 150 of file PriorityQueue.h.

◆ push() [2/3]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

template<class InputIt >

void ogdf::PriorityQueue< T, C, Impl >::push	(	InputIt	first,
		InputIt	last
	)

inline

Inserts new elements specified by the given range.

Parameters

first	Begin iterator of the range being inserted.
last	Past-the-end iterator of the range being inserted.

Definition at line 161 of file PriorityQueue.h.

◆ push() [3/3]

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::push ( std::initializer_list< value_type > ilist )

inline

Inserts new elements specified by the given initializer list.

Parameters

ilist List whose elements should be used during insertion.

Definition at line 171 of file PriorityQueue.h.

◆ size()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

size_type ogdf::PriorityQueue< T, C, Impl >::size ( ) const

inline

Returns the number of enqueued elements.

Definition at line 214 of file PriorityQueue.h.

◆ swap()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void ogdf::PriorityQueue< T, C, Impl >::swap ( PriorityQueue< T, C, Impl > & other )

inline

Swaps the contents.

Definition at line 134 of file PriorityQueue.h.

◆ top()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

const T& ogdf::PriorityQueue< T, C, Impl >::top ( ) const

inline

Returns reference to the top element in the queue.

Definition at line 143 of file PriorityQueue.h.

◆ value()

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

const T& ogdf::PriorityQueue< T, C, Impl >::value ( handle pos ) const

inline

Returns the priority of that handle.

Parameters

pos	The handle

Returns: The priority

Definition at line 222 of file PriorityQueue.h.

Friends And Related Function Documentation

◆ swap

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

void swap	(	PriorityQueue< T, C, Impl > &	a,
		PriorityQueue< T, C, Impl > &	b
	)

friend

Swaps the contents.

Definition at line 140 of file PriorityQueue.h.

Member Data Documentation

◆ m_impl

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

SpecImpl* ogdf::PriorityQueue< T, C, Impl >::m_impl

private

Underlying heap data structure.

Definition at line 69 of file PriorityQueue.h.

◆ m_size

template<typename T , class C = std::less<T>, template< typename, class > class Impl = PairingHeap>

size_type ogdf::PriorityQueue< T, C, Impl >::m_size

private

Number of entries.

Definition at line 67 of file PriorityQueue.h.

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

include/ogdf/basic/PriorityQueue.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Types

Private Attributes

Friends

Detailed Description

template<typename T, class C = std::less<T>, template< typename, class > class Impl = PairingHeap> class ogdf::PriorityQueue< T, C, Impl >

Member Typedef Documentation

◆ const_reference

◆ handle

◆ reference

◆ size_type

◆ SpecImpl

◆ value_type

Constructor & Destructor Documentation

◆ PriorityQueue() [1/5]

◆ PriorityQueue() [2/5]

◆ PriorityQueue() [3/5]

◆ PriorityQueue() [4/5]

◆ PriorityQueue() [5/5]

◆ ~PriorityQueue()

Member Function Documentation

◆ clear()

◆ comparator()

◆ decrease()

◆ empty()

◆ merge()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop()

◆ push() [1/3]

◆ push() [2/3]

◆ push() [3/3]

◆ size()

◆ swap()

◆ top()

◆ value()

Friends And Related Function Documentation

◆ swap

Member Data Documentation

◆ m_impl

◆ m_size

Open
Graph Drawing
Framework

template<typename T, class C = std::less<T>, template< typename, class > class Impl = PairingHeap>
class ogdf::PriorityQueue< T, C, Impl >