The LimitedPriorityQueue class is similar to std::priority_queue but has a limited capacity and handles the comparison differently. More...

#include <limitedPriorityQueue.h>

Inheritance diagram for Ponca::LimitedPriorityQueue< T, N, CompareT >:

Collaboration diagram for Ponca::LimitedPriorityQueue< T, N, CompareT >:

Public Types
using	value_type = T

using	container_type = std::array< T, N >

using	compare = CompareT

using	iterator = typename container_type::iterator

using	const_iterator = typename container_type::const_iterator

using	Self = LimitedPriorityQueue< T, N, CompareT >

Public Member Functions
	LimitedPriorityQueue (const Self &other)

	LimitedPriorityQueue (int capacity)

template<class InputIt >
	LimitedPriorityQueue (int capacity, InputIt first, InputIt last)

LimitedPriorityQueue &	operator= (const Self &other)=default

iterator	begin ()

const_iterator	begin () const

const_iterator	cbegin () const

iterator	end ()

const_iterator	end () const

const_iterator	cend () const

const T &	top () const

const T &	bottom () const

T &	top ()

T &	bottom ()

bool	empty () const

bool	full () const

size_t	size () const

size_t	capacity () const

bool	push (T &&_value)

bool	push (const T &_value)

void	pop ()

void	reserve (int _capacity)

void	clear ()

const container_type &	container () const

Protected Member Functions
bool	pushImpl (const T &_value, T **_addr)

Protected Attributes
container_type	m_data {}

compare	m_comp

size_t	m_size {0}
	The current size of the Queue.

size_t	m_capacity {0}
	The capacity of the limited queue.

Detailed Description

template<class T, int N, class CompareT = std::less<T>>
class Ponca::LimitedPriorityQueue< T, N, CompareT >

The LimitedPriorityQueue class is similar to std::priority_queue but has a limited capacity and handles the comparison differently.

In case the capacity is reached, the container is full and push() do not insert a new element if its priority is lower than the current minimal one.

The comparison predicate must return true is the first argument has priority on the second one.

The element with the highest priority is the last one that is pop out, but is the first one that is iterated through.

Example 1: Using std::less as comparison predicate, we have the following situation:

full()      = false
empty()     = false
capacity()  = 6
size()      = 4
top()       = 1
bottom()    = 9

pop() removes the value 9
push(4) adds the value 4

begin            end
  v               v
+---+---+---+---+---+---+
| 1 | 3 | 8 | 9 |   |   |
+---+---+---+---+---+---+
  ^           ^
 top        bottom

Example 2: Using std::greater as comparison predicate, we have the following situation:

full()      = true
empty()     = false
capacity()  = 6
size()      = 6
top()       = 9
bottom()    = 2

begin                    end
  v                       v
+---+---+---+---+---+---+
| 9 | 8 | 6 | 4 | 3 | 2 |
+---+---+---+---+---+---+
  ^                   ^
 top                bottom

pop() removes the value 2
push(5) adds the value 5 and remove the value 2
push(0) do nothing

Template Parameters

T	The data type stored in the queue
N	The maximum capacity of the queue
CompareT	A binary predicate used to sort the queue. Default to less

Definition at line 84 of file limitedPriorityQueue.h.

Member Typedef Documentation

◆ compare

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::compare = CompareT

Definition at line 91 of file limitedPriorityQueue.h.

◆ const_iterator

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::const_iterator = typename container_type::const_iterator

Definition at line 93 of file limitedPriorityQueue.h.

◆ container_type

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::container_type = std::array<T, N>

Definition at line 90 of file limitedPriorityQueue.h.

◆ iterator

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::iterator = typename container_type::iterator

Definition at line 92 of file limitedPriorityQueue.h.

◆ Self

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::Self = LimitedPriorityQueue<T, N, CompareT>

Definition at line 94 of file limitedPriorityQueue.h.

◆ value_type

template<class T , int N, class CompareT = std::less<T>>

using Ponca::LimitedPriorityQueue< T, N, CompareT >::value_type = T

Definition at line 89 of file limitedPriorityQueue.h.

Constructor & Destructor Documentation

◆ LimitedPriorityQueue() [1/4]

template<class T , int N, class Cmp >

Ponca::LimitedPriorityQueue< T, N, Cmp >::LimitedPriorityQueue ( )

inline

Definition at line 163 of file limitedPriorityQueue.h.

◆ LimitedPriorityQueue() [2/4]

template<class T , int N, class Cmp >

Ponca::LimitedPriorityQueue< T, N, Cmp >::LimitedPriorityQueue ( const Self & other )

inline

Definition at line 169 of file limitedPriorityQueue.h.

◆ LimitedPriorityQueue() [3/4]

template<class T , int N, class Cmp >

Ponca::LimitedPriorityQueue< T, N, Cmp >::LimitedPriorityQueue ( int capacity )

inlineexplicit

Definition at line 176 of file limitedPriorityQueue.h.

◆ LimitedPriorityQueue() [4/4]

template<class T , int N, class Cmp >

template<class InputIt >

Ponca::LimitedPriorityQueue< T, N, Cmp >::LimitedPriorityQueue	(	int	capacity,
		InputIt	first,
		InputIt	last
	)

Definition at line 185 of file limitedPriorityQueue.h.

Member Function Documentation

◆ begin() [1/2]

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::begin ( )

inline

Definition at line 14 of file limitedPriorityQueue.hpp.

◆ begin() [2/2]

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::const_iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::begin ( ) const

inline

Definition at line 20 of file limitedPriorityQueue.hpp.

◆ bottom() [1/2]

template<class T , int N, class Cmp >

T & Ponca::LimitedPriorityQueue< T, N, Cmp >::bottom ( )

inline

Definition at line 70 of file limitedPriorityQueue.hpp.

◆ bottom() [2/2]

template<class T , int N, class Cmp >

const T & Ponca::LimitedPriorityQueue< T, N, Cmp >::bottom ( ) const

inline

Definition at line 58 of file limitedPriorityQueue.hpp.

◆ capacity()

template<class T , int N, class Cmp >

size_t Ponca::LimitedPriorityQueue< T, N, Cmp >::capacity ( ) const

inline

Definition at line 96 of file limitedPriorityQueue.hpp.

◆ cbegin()

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::const_iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::cbegin ( ) const

inline

Definition at line 26 of file limitedPriorityQueue.hpp.

◆ cend()

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::const_iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::cend ( ) const

inline

Definition at line 44 of file limitedPriorityQueue.hpp.

◆ clear()

template<class T , int N, class Cmp >

void Ponca::LimitedPriorityQueue< T, N, Cmp >::clear ( )

Definition at line 181 of file limitedPriorityQueue.hpp.

◆ container()

template<class T , int N, class Cmp >

const LimitedPriorityQueue< T, N, Cmp >::container_type & Ponca::LimitedPriorityQueue< T, N, Cmp >::container ( ) const

Definition at line 189 of file limitedPriorityQueue.hpp.

◆ empty()

template<class T , int N, class Cmp >

bool Ponca::LimitedPriorityQueue< T, N, Cmp >::empty ( ) const

inline

Definition at line 78 of file limitedPriorityQueue.hpp.

◆ end() [1/2]

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::end ( )

inline

Definition at line 32 of file limitedPriorityQueue.hpp.

◆ end() [2/2]

template<class T , int N, class Cmp >

LimitedPriorityQueue< T, N, Cmp >::const_iterator Ponca::LimitedPriorityQueue< T, N, Cmp >::end ( ) const

inline

Definition at line 38 of file limitedPriorityQueue.hpp.

◆ full()

template<class T , int N, class Cmp >

bool Ponca::LimitedPriorityQueue< T, N, Cmp >::full ( ) const

inline

Definition at line 84 of file limitedPriorityQueue.hpp.

◆ pop()

template<class T , int N, class Cmp >

void Ponca::LimitedPriorityQueue< T, N, Cmp >::pop ( )

Definition at line 165 of file limitedPriorityQueue.hpp.

◆ push() [1/2]

template<class T , int N, class Cmp >

bool Ponca::LimitedPriorityQueue< T, N, Cmp >::push ( const T & _value )

Definition at line 153 of file limitedPriorityQueue.hpp.

◆ push() [2/2]

template<class T , int N, class Cmp >

bool Ponca::LimitedPriorityQueue< T, N, Cmp >::push ( T && _value )

Definition at line 141 of file limitedPriorityQueue.hpp.

◆ pushImpl()

template<class T , int N, class Cmp >

bool Ponca::LimitedPriorityQueue< T, N, Cmp >::pushImpl	(	const T &	_value,
		T **	_addr
	)

inlineprotected

Definition at line 103 of file limitedPriorityQueue.hpp.

◆ reserve()

template<class T , int N, class Cmp >

void Ponca::LimitedPriorityQueue< T, N, Cmp >::reserve ( int _capacity )

Definition at line 171 of file limitedPriorityQueue.hpp.

◆ size()

template<class T , int N, class Cmp >

size_t Ponca::LimitedPriorityQueue< T, N, Cmp >::size ( ) const

inline

Definition at line 90 of file limitedPriorityQueue.hpp.

◆ top() [1/2]

template<class T , int N, class Cmp >

T & Ponca::LimitedPriorityQueue< T, N, Cmp >::top ( )

inline

Definition at line 64 of file limitedPriorityQueue.hpp.

◆ top() [2/2]

template<class T , int N, class Cmp >

const T & Ponca::LimitedPriorityQueue< T, N, Cmp >::top ( ) const

inline

Definition at line 52 of file limitedPriorityQueue.hpp.

Member Data Documentation

◆ m_capacity

template<class T , int N, class CompareT = std::less<T>>

size_t Ponca::LimitedPriorityQueue< T, N, CompareT >::m_capacity {0}

protected

The capacity of the limited queue.

Definition at line 152 of file limitedPriorityQueue.h.

◆ m_comp

template<class T , int N, class CompareT = std::less<T>>

compare Ponca::LimitedPriorityQueue< T, N, CompareT >::m_comp

protected

Definition at line 150 of file limitedPriorityQueue.h.

◆ m_data

template<class T , int N, class CompareT = std::less<T>>

container_type Ponca::LimitedPriorityQueue< T, N, CompareT >::m_data {}

protected

Definition at line 149 of file limitedPriorityQueue.h.

◆ m_size

template<class T , int N, class CompareT = std::less<T>>

size_t Ponca::LimitedPriorityQueue< T, N, CompareT >::m_size {0}

protected

The current size of the Queue.

Definition at line 151 of file limitedPriorityQueue.h.

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ compare

◆ const_iterator

◆ container_type

◆ iterator

◆ Self

◆ value_type

Constructor & Destructor Documentation

◆ LimitedPriorityQueue() [1/4]

◆ LimitedPriorityQueue() [2/4]

◆ LimitedPriorityQueue() [3/4]

◆ LimitedPriorityQueue() [4/4]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ bottom() [1/2]

◆ bottom() [2/2]

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear()

◆ container()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ full()

◆ pop()

◆ push() [1/2]

◆ push() [2/2]

◆ pushImpl()

◆ reserve()

◆ size()

◆ top() [1/2]

◆ top() [2/2]

Member Data Documentation

◆ m_capacity

◆ m_comp

◆ m_data

◆ m_size