Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::PriorityQueue< T, C, Impl > Class Template Reference

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...
 
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...
 
PriorityQueueoperator= (PriorityQueue other)
 Copy and move assignment. More...
 
PriorityQueueoperator= (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

const C & m_cmp
 
SpecImplm_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
TDenotes value type of inserted elements.
CDenotes comparison functor determining value ordering.
ImplDenotes underlying heap class.

Definition at line 65 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 79 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 77 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 78 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 67 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 72 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 76 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
cmpComparison functor determining priority ordering.
initialSizeThe initial capacity preference (ignored if not supported by underlying heap).

Definition at line 86 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 92 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 98 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
firstBegin iterator of the initializing range.
lastPast-the-end iterator of the initializing range.
cmpComparison functor determining priority ordering.

Definition at line 111 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
initList whose elements should be used during initalization.
cmpComparison functor determining priority ordering.

Definition at line 122 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 128 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 229 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
posA element for which the value is to be decreased.
valueA new value for the node.

Definition at line 212 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 235 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
otherA queue to be merged in.

Definition at line 222 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 133 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
ilistList whose elements should be assigned.
Returns
Reference to the assigned priority queue.

Definition at line 143 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 199 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 170 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
firstBegin iterator of the range being inserted.
lastPast-the-end iterator of the range being inserted.

Definition at line 181 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
ilistList whose elements should be used during insertion.

Definition at line 191 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 240 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 150 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 161 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
posThe handle
Returns
The priority

Definition at line 250 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 156 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 71 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 73 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 70 of file PriorityQueue.h.


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