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.

	PriorityQueue (const PriorityQueue &other)
	Copy constructor.

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

	PriorityQueue (PriorityQueue &&other)
	Move constructor.

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

	~PriorityQueue ()
	Destroys the underlying data structure.

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

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

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

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

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

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

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

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

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

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

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

void	swap (PriorityQueue &other)
	Swaps the contents.

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

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

Private Types
using	SpecImpl = Impl< T, C >

Private Attributes
const C &	m_cmp

SpecImpl *	m_impl
	Underlying heap data structure.

size_type	m_size
	Number of entries.

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

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 60 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 74 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 72 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 73 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 62 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 67 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 71 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 81 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 85 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 89 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 100 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 109 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 113 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 204 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 189 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 210 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 197 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 116 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 126 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 176 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 149 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 160 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 170 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 213 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 133 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 142 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 221 of file PriorityQueue.h.

Friends And Related Symbol 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 139 of file PriorityQueue.h.

Member Data Documentation

◆ m_cmp

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

const C& ogdf::PriorityQueue< T, C, Impl >::m_cmp

private

Definition at line 66 of file PriorityQueue.h.

◆ 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 68 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 65 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

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()

◆ 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 Symbol Documentation

◆ swap

Member Data Documentation

◆ m_cmp

◆ m_impl

◆ m_size

Open
Graph Drawing
Framework