Simple Application Framework  1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Public Member Functions | Protected Types
Saf::Collection::PriorityQueue< ValType, CompType, ContainerType > Class Template Reference

Priority queue container. More...

#include <PriorityQueue.h>

List of all members.

Public Member Functions

 PriorityQueue ()
 Constructor.
 PriorityQueue (const MyType &queue)
 Copy constructor.
 PriorityQueue (const ContainerType &cont)
 Construct using the supplied container.
Size Elements () const
 Get the number of elements in the priority queue.
bool IsEmpty () const
 Check whether the priority queue is empty.
MyTypeoperator= (MyType &queue)
 Assignment operator.
MyTypePop ()
 Remove the top element from the priority queue.
MyTypePush (const ValType &val)
 Add new element to the priority queue.
const ContainerType & Storage ()
 Get the internal data storage reference.
MyTypeSwap (MyType &queue)
 Swap the content of two priority queues.
ValType & Top ()
 Get reference to the largest element in the priority queue.
const ValType & Top () const
 Get reference to the largest element in the priority queue.

Protected Types

typedef PriorityQueue< ValType,
CompType, ContainerType > 
MyType

Detailed Description

template<class ValType, class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
class Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >

Priority queue container.

This class implements a priority queue that stores a sequence of elements and allows to efficiently extract the element with the largest value according to the CompType predicate.

Technically, an underlying container is used to store the data. It must allow new elements to be added to its back (a PushBack() method) and random access to its elements because they are organized in a max-heap fashion internally. Consequently, the classes DynArray and Deque are examples of containers that can be used to implement a PriorityQueue.

Template Parameters:
ValTypeData type of values in the queue.
CompTypeBinary comparison predicate inducing strict weak ordering on ValType values.
ContainerTypeUnderlying container storing the data.
See also:
DynArray, Deque, Algo::Struct::Heap.

Member Typedef Documentation

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
typedef PriorityQueue<ValType,CompType,ContainerType> Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::MyType [protected]

Constructor & Destructor Documentation

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::PriorityQueue ( ) [inline]

Constructor.

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::PriorityQueue ( const MyType queue) [inline]

Copy constructor.

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::PriorityQueue ( const ContainerType &  cont) [inline, explicit]

Construct using the supplied container.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\mathrm{cont.Elements()}) $.

Member Function Documentation

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
Size Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Elements ( ) const [inline]

Get the number of elements in the priority queue.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
bool Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::IsEmpty ( ) const [inline]

Check whether the priority queue is empty.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
MyType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::operator= ( MyType queue) [inline]

Assignment operator.

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
MyType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Pop ( ) [inline]

Remove the top element from the priority queue.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
MyType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Push ( const ValType &  val) [inline]

Add new element to the priority queue.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(\log \mathrm{Elements()}) $.
template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
const ContainerType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Storage ( ) [inline]

Get the internal data storage reference.

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
MyType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Swap ( MyType queue) [inline]

Swap the content of two priority queues.

Properties:

  • Worst-case time complexity: $ \mathcal{O}(1) $.
template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
ValType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Top ( ) [inline]

Get reference to the largest element in the priority queue.

template<class ValType , class CompType = Algo::Predicate::Less<ValType>, class ContainerType = DynArray<ValType>>
const ValType& Saf::Collection::PriorityQueue< ValType, CompType, ContainerType >::Top ( ) const [inline]

Get reference to the largest element in the priority queue.


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