Base class for implementing a bounded priority deque. More...

#include <BoundedPriorityDeque.hpp>

Inheritance diagram for BoundedPriorityDequeBase< K, V >:

Public Member Functions
	BoundedPriorityDequeBase (size_t capacity=0)
	Primary constructor with default bounding capacity of zero.

BoundingPair< K, V >	top () const
	Get the highest-priority element.

BoundingPair< K, V >	bottom () const
	Get the lowest-priority element.

K	topK () const
	Get the key from the highest-priority element.

K	bottomK () const
	Get the key from the lowest-priority element.

void	emplace (K key, const V &value)
	constructs a BoundingPair<K, V> element and inserts it.

void	push (const BoundingPair< K, V > &element)
	Inserts an element into the vector.

BoundingPair< K, V >	operator[] (size_t offsetTop) const
	random accessor relative to the top of the deque.

BoundingPair< K, V >	pop ()
	remove the highest-priority element.

BoundingPair< K, V >	popBottom ()
	remove the lowest-priority element.

void	operator+= (const BoundedPriorityDequeBase< K, V > &rhs)
	Merges another BoundedPriorityDeque instance into the calling instance.

void	clear ()
	clears and resets the data structure.

size_t	size () const

size_t	capacity () const

bool	empty () const

bool	full () const

void	resize (size_t k)
	Sets the capacity and restores clean state.

Protected Member Functions
virtual bool	compare (K a, K b) const =0

size_t	nextIndex (size_t current) const
	Provides fast access to the next index of a given insertion position.

size_t	prevIndex (size_t current) const
	Provides fast access to the previous index of a given insertion position.

size_t	binarySearch (const BoundingPair< K, V > &target) const
	Efficiently locates the optimal insertion index.

void	insert (const BoundingPair< K, V > &element)
	Inserts an element into the _buffer.

void	_popTop ()
	Internal method with no return val.

void	_popBottom ()
	Internal method with no return val.

Protected Attributes
std::vector< BoundingPair< K, V > >	_buffer

size_t	_k

size_t	_size = 0

size_t	_head = 0

size_t	_tail = 0

Detailed Description

template<typename K, typename V>
class BoundedPriorityDequeBase< K, V >

Base class for implementing a bounded priority deque.

This class provides the basic functionalities of a bounded deque with methods for pushing, popping, and accessing elements while maintaining a defined capacity.

Template Parameters

K	Type of the key.
V	Type of the value.

Constructor & Destructor Documentation

◆ BoundedPriorityDequeBase()

template<typename K , typename V >

BoundedPriorityDequeBase< K, V >::BoundedPriorityDequeBase ( size_t capacity = 0 )

inlineexplicit

Primary constructor with default bounding capacity of zero.

Parameters

capacity The initially set bounding capacity of the data structure.

Member Function Documentation

◆ binarySearch()

template<typename K , typename V >

size_t BoundedPriorityDequeBase< K, V >::binarySearch ( const BoundingPair< K, V > & target ) const

inlineprotected

Efficiently locates the optimal insertion index.

Performs binary insertion search and locates insertion index in O(log n) time, adapted for a circular buffer with modulo arithmetic. No handling of duplicate values.

Parameters

target The element to be inserted.

Returns: The optimal insertion index for the targeted insertion element.

◆ bottom()

template<typename K , typename V >

BoundingPair< K, V > BoundedPriorityDequeBase< K, V >::bottom ( ) const

inline

Get the lowest-priority element.

Gets the next element to be pruned from the tail of the data structure.

Returns: the BoundingPair at the tail of the circular buffer.

◆ bottomK()

template<typename K , typename V >

K BoundedPriorityDequeBase< K, V >::bottomK ( ) const

inline

Get the key from the lowest-priority element.

Effective for comparing against the bottom element without the overhead of passing the full BoundingPair<K, V>.

Returns: the lowest-priority elements key.

◆ capacity()

template<typename K , typename V >

size_t BoundedPriorityDequeBase< K, V >::capacity ( ) const

inline

Returns: The bounding capacity of the data structure.

◆ clear()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::clear ( )

inline

clears and resets the data structure.

Resets the size and index pointers to there original values. No destructor calls for performance.

◆ compare()

template<typename K , typename V >

virtual bool BoundedPriorityDequeBase< K, V >::compare	(	K	a,
		K	b
	)		const

protectedpure virtual

Compares two keys.

Parameters

a	The first key.
b	The second key.

Returns: True if a is considered less than b in a min-oriented deque, or more in a max-oriented deque.

Implemented in BoundedMinPriorityDeque< K, V >, BoundedMaxPriorityDeque< K, V >, BoundedPriorityDequeKeyed< K, V, Comparator >, and BoundedPriorityDeque< V, Comparator, K >.

◆ emplace()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::emplace	(	K	key,
		const V &	value
	)

inline

constructs a BoundingPair<K, V> element and inserts it.

Parameters

key	The bounding key value
value	The data held by the bounding pair.

◆ empty()

template<typename K , typename V >

bool BoundedPriorityDequeBase< K, V >::empty ( ) const

inline

Returns: True if the dequeue is empty, else False.

◆ full()

template<typename K , typename V >

bool BoundedPriorityDequeBase< K, V >::full ( ) const

inline

Returns: True if the dequeue is full, else False.

◆ insert()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::insert ( const BoundingPair< K, V > & element )

inlineprotected

Inserts an element into the _buffer.

This is a utility method to allow shared insertion logic between the public push method and the operator+=() code, the latter of which needed a way to terminate the loop without running redundant capacity checks, so this function is essentially protection free insertion (think overwriting elements in the circular buffer), popping from the bottom if capacity is to be exceeded must be handled by the programmer in this case.

Parameters

element

◆ nextIndex()

template<typename K , typename V >

size_t BoundedPriorityDequeBase< K, V >::nextIndex ( size_t current ) const

inlineprotected

Provides fast access to the next index of a given insertion position.

Parameters

current The index queried for next index

Returns: The next index with circular wrap-around

◆ operator+=()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::operator+= ( const BoundedPriorityDequeBase< K, V > & rhs )

inline

Merges another BoundedPriorityDeque instance into the calling instance.

Compares the incoming dequeues next value to the calling dequeues lowest-priority elements key, terminates search early when the other buffers top element is lower-priority than 'this' bottom element. Is non-destructive to the incoming dequeues data.

Parameters

rhs	The BoundedPriorityDeque being merged into 'this' dequeue.

◆ operator[]()

template<typename K , typename V >

BoundingPair< K, V > BoundedPriorityDequeBase< K, V >::operator[] ( size_t offsetTop ) const

inline

random accessor relative to the top of the deque.

This accessor has a lot of uses. It primarily exists to facilitate efficient merges in operator+=() without removing const protections, but also could be useful for random access to the i-th element offset from the top, ie the 4th highest-priority item in O(1) time.

Parameters

offsetTop The unsigned long offset from the top element.

Returns: The BoundingPair<K, V> element offset from the top of deque.

◆ pop()

template<typename K , typename V >

BoundingPair< K, V > BoundedPriorityDequeBase< K, V >::pop ( )

inline

remove the highest-priority element.

Returns: The removed highest-priority element.

◆ popBottom()

template<typename K , typename V >

BoundingPair< K, V > BoundedPriorityDequeBase< K, V >::popBottom ( )

inline

remove the lowest-priority element.

Returns: The removed lowest-priority element.

◆ prevIndex()

template<typename K , typename V >

size_t BoundedPriorityDequeBase< K, V >::prevIndex ( size_t current ) const

inlineprotected

Provides fast access to the previous index of a given insertion position.

Parameters

current The index queried for previous index

Returns: The previous index with circular wrap-around

◆ push()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::push ( const BoundingPair< K, V > & element )

inline

Inserts an element into the vector.

If dequeue is at capacity and the insertion is valid, pops the bottom element. If straightforward insertion not possible, uses binary search to find the insertion index, then shifts the elements above or below the insertion index to make room for the item.

Parameters

element The element to be inserted.

◆ resize()

template<typename K , typename V >

void BoundedPriorityDequeBase< K, V >::resize ( size_t k )

inline

Sets the capacity and restores clean state.

Updates the capacity, then restores the _head of the _buffer back to index 0 leaving the buffer in a contiguous fresh state. This preserves the integrity of the higher-priority data when shrinking the buffer.

Parameters

k	The new capacity.

◆ size()

template<typename K , typename V >

size_t BoundedPriorityDequeBase< K, V >::size ( ) const

inline

Returns: The vectors logical size.

◆ top()

template<typename K , typename V >

BoundingPair< K, V > BoundedPriorityDequeBase< K, V >::top ( ) const

inline

Get the highest-priority element.

Returns: the BoundingPair at the head of the circular buffer.

◆ topK()

template<typename K , typename V >

K BoundedPriorityDequeBase< K, V >::topK ( ) const

inline

Get the key from the highest-priority element.

Introduced to help with merging checks in operator+=, but useful for checking the top of the dequeues key if an optimization threshold is trying to be achieved.

Returns: the lowest-priority elements key.

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

include/BoundedPriorityDeque.hpp

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BoundedPriorityDequeBase()

Member Function Documentation

◆ binarySearch()

◆ bottom()

◆ bottomK()

◆ capacity()

◆ clear()

◆ compare()

◆ emplace()

◆ empty()

◆ full()

◆ insert()

◆ nextIndex()

◆ operator+=()

◆ operator[]()

◆ pop()

◆ popBottom()

◆ prevIndex()

◆ push()

◆ resize()

◆ size()

◆ top()

◆ topK()