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 > requires ValidCapacity<N>
	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>>
requires ValidCapacity<N>
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 86 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.