priority_queue< T, Size, KeyGreater > Class Template Reference

Priority Queue. More...

#include <priority_queue.hpp>

Inheritance diagram for priority_queue< T, Size, KeyGreater >:

Collaboration diagram for priority_queue< T, Size, KeyGreater >:

Public Types
using	value_type = typename std::decay< T >::type
using	iterator = value_type *
using	const_iterator = const value_type *
using	size_type = int

Public Member Functions
constexpr	priority_queue ()=default
bool	insert (value_type &&item) noexcept
	inserts a value into the queue. inserts are ordered by their priority. this function takes O(log n) time to do so. More...
value_type	pop_front () noexcept
	takes the first item in the queue and returns it. The item is deleted from the queue. It panics if the queue is empty. More...
iterator	erase (const_iterator iterator)
	removes an item from the queue by iterator. Performance: O(log n) More...
constexpr size_type	size () const noexcept
constexpr size_type	max_size () const noexcept
constexpr bool	empty () const noexcept
	returns if the queue is empty. in this case both begin() and end() point to nullptr More...
constexpr iterator	begin () noexcept
	if queue != empty() it returns a pointer to the beginning of the queue. The item with the highest priority More...
constexpr iterator	end () noexcept
	iterator that points past the last element in the queue. More...
constexpr const_iterator	begin () const noexcept
	if queue != empty() it returns a pointer to the beginning of the queue. The item with the highest priority More...
constexpr const_iterator	end () const noexcept
	iterator that points past the last element in the queue. More...
constexpr void	clear () noexcept
	remove all items from the queue. More...

Private Member Functions
constexpr size_type	parent_index (size_type i) const
constexpr size_type	left_index (size_type i) const
constexpr size_type	right_index (size_type i) const
constexpr size_type	biggest_child (size_type current) const
void	init_iterators ()

Private Attributes
value_type	elements [Size]
iterator	last = nullptr
iterator	first = nullptr

Detailed Description

template<class T, int Size, class KeyGreater = std::greater<T>>
class priority_queue< T, Size, KeyGreater >

Priority Queue.

This container arranges nodes in a binary tree, with the highest priority (highest value) at the root of the tree. Note that this tree is not lineair sorted! This means that searching the tree will take linear time. Secondly, This class is designed to be used in memory limited environments (read embedded systems). Hence this class operates without allocating any heap memory.

Since only static memory is used, the maximum size of the container needs to determine beforehand. Its up to the implementor to choose a size big enough to accommodate for all use-cases.

The interface of this container should look familiar. It tries to mimic, where possible, the same interface as the containers you would find in the std library.

Performance

• inserting = O(log N)
• deleting = O(log N)
• search = O(N)
• get Min = O(1)
• space = O(N)

Member Typedef Documentation

const_iterator

template<class T , int Size, class KeyGreater = std::greater<T>>

using priority_queue< T, Size, KeyGreater >::const_iterator = const value_type *

iterator

template<class T , int Size, class KeyGreater = std::greater<T>>

using priority_queue< T, Size, KeyGreater >::iterator = value_type *

size_type

template<class T , int Size, class KeyGreater = std::greater<T>>

using priority_queue< T, Size, KeyGreater >::size_type = int

value_type

template<class T , int Size, class KeyGreater = std::greater<T>>

using priority_queue< T, Size, KeyGreater >::value_type = typename std::decay<T>::type

Constructor & Destructor Documentation

priority_queue()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr priority_queue< T, Size, KeyGreater >::priority_queue ( )

constexprdefault

Member Function Documentation

begin() [1/2]

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr const_iterator priority_queue< T, Size, KeyGreater >::begin ( ) const

inlineconstexprnoexcept

if queue != empty() it returns a pointer to the beginning of the queue. The item with the highest priority

Returns

the iterator to the beginning of the queue. nullptr in the case the queue is empty

begin() [2/2]

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr iterator priority_queue< T, Size, KeyGreater >::begin ( )

inlineconstexprnoexcept

if queue != empty() it returns a pointer to the beginning of the queue. The item with the highest priority

Returns

the iterator to the beginning of the queue. nullptr in the case the queue is empty

Here is the caller graph for this function:

biggest_child()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::biggest_child ( size_type  current ) const

inlineconstexprprivate

Here is the call graph for this function:

Here is the caller graph for this function:

clear()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr void priority_queue< T, Size, KeyGreater >::clear ( )

inlineconstexprnoexcept

remove all items from the queue.

Performance : O(1)

Here is the caller graph for this function:

empty()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr bool priority_queue< T, Size, KeyGreater >::empty ( ) const

inlineconstexprnoexcept

returns if the queue is empty. in this case both begin() and end() point to nullptr

Returns

true if there are no items in the queue. false otherwise.

Here is the caller graph for this function:

end() [1/2]

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr const_iterator priority_queue< T, Size, KeyGreater >::end ( ) const

inlineconstexprnoexcept

iterator that points past the last element in the queue.

Returns

the iterator to the next element after last in the queue. nullptr in the case the queue is empty

end() [2/2]

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr iterator priority_queue< T, Size, KeyGreater >::end ( )

inlineconstexprnoexcept

iterator that points past the last element in the queue.

Returns

the iterator to the next element after last in the queue. nullptr in the case the queue is empty

Here is the caller graph for this function:

erase()

template<class T , int Size, class KeyGreater = std::greater<T>>

iterator priority_queue< T, Size, KeyGreater >::erase ( const_iterator  iterator )

inline

removes an item from the queue by iterator. Performance: O(log n)

Returns

the iterator following the last removed iterator. Note that the following iterator means the iterator which is next to the current iterator in memory, not the child of the current iterator from a binary tree perspective.

Here is the call graph for this function:

Here is the caller graph for this function:

init_iterators()

template<class T , int Size, class KeyGreater = std::greater<T>>

void priority_queue< T, Size, KeyGreater >::init_iterators ( )

inlineprivate

Here is the caller graph for this function:

insert()

template<class T , int Size, class KeyGreater = std::greater<T>>

bool priority_queue< T, Size, KeyGreater >::insert ( value_type &&  item )

inlinenoexcept

inserts a value into the queue. inserts are ordered by their priority. this function takes O(log n) time to do so.

Be aware that this container cannot grow past its max size of max_size(). this function will return false in this case!

Returns

true when insert was successful. false when there is no capacity to insert item.

Here is the call graph for this function:

Here is the caller graph for this function:

left_index()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::left_index ( size_type  i ) const

inlineconstexprprivate

Here is the caller graph for this function:

max_size()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::max_size ( ) const

inlineconstexprnoexcept

Returns

the maximum size this queue can grow.

Here is the caller graph for this function:

parent_index()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::parent_index ( size_type  i ) const

inlineconstexprprivate

Here is the caller graph for this function:

pop_front()

template<class T , int Size, class KeyGreater = std::greater<T>>

value_type priority_queue< T, Size, KeyGreater >::pop_front ( )

inlinenoexcept

takes the first item in the queue and returns it. The item is deleted from the queue. It panics if the queue is empty.

after this operation the priority in the queue is maintained.

Performance: O(log n)

Returns

the first item in the queue.

Here is the call graph for this function:

right_index()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::right_index ( size_type  i ) const

inlineconstexprprivate

Here is the caller graph for this function:

size()

template<class T , int Size, class KeyGreater = std::greater<T>>

constexpr size_type priority_queue< T, Size, KeyGreater >::size ( ) const

inlineconstexprnoexcept

Returns

number of allocated items in the queue.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

elements

template<class T , int Size, class KeyGreater = std::greater<T>>

value_type priority_queue< T, Size, KeyGreater >::elements[Size]

private

first

template<class T , int Size, class KeyGreater = std::greater<T>>

iterator priority_queue< T, Size, KeyGreater >::first = nullptr

private

last

template<class T , int Size, class KeyGreater = std::greater<T>>

iterator priority_queue< T, Size, KeyGreater >::last = nullptr

private

---

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

• applications/zpc/components/zwave/zwave_tx/src/priority_queue.hpp