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.
MyType &	operator= (MyType &queue)
	Assignment operator.
MyType &	Pop ()
	Remove the top element from the priority queue.
MyType &	Push (const ValType &val)
	Add new element to the priority queue.
const ContainerType &	Storage ()
	Get the internal data storage reference.
MyType &	Swap (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:

ValType	Data type of values in the queue.
CompType	Binary comparison predicate inducing strict weak ordering on ValType values.
ContainerType	Underlying 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: .

---

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: .

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: .

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: .

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: .

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: .

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:

• Saf/Collection/PriorityQueue.h