Template Class BucketQueue

Nested Relationships

Nested Types

Class Documentation

template<class T, std::integral K = int>
class BucketQueue

a two-level bucket queue: least f first, then largest g, then LIFO

Public Types

using Item = T

the type of the items

using Key = K

the type of the keys

using value_type = T
using size_type = std::size_t
using difference_type = std::ptrdiff_t
using reference = const T&
using const_reference = const T&
using iterator = const_iterator

Public Functions

void push(const T &x, K f, K g)

pushes x with the keys f and g

Pre:

f >= 0 and g >= 0

const T &top(void)

an item of least f and, among those, of largest g, the last pushed

Pre:

the queue is not empty

K topF(void)

the f of top()

Pre:

the queue is not empty

K topG(void)

the g of top()

Pre:

the queue is not empty

T pop(void)

removes top() and returns it

Pre:

the queue is not empty

Entry popEntry(void)

removes top() and returns it with its keys f and g, finding the top once instead of three times through topF(), topG() and pop()

Pre:

the queue is not empty

bool empty(void) const
std::size_t size(void) const

the number of items, the stale ones included

void clear(void)

removes all the items and frees the layers

inline const_iterator begin(void) const
inline const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const
class const_iterator

Public Types

using iterator_category = std::forward_iterator_tag
using value_type = T
using difference_type = std::ptrdiff_t
using reference = const T&
using pointer = const T*

Public Functions

const_iterator(void) = default
inline const_iterator(const BucketQueue *q, std::size_t f)
inline reference operator*(void) const
inline pointer operator->(void) const
inline const_iterator &operator++(void)
inline const_iterator operator++(int)
inline bool operator==(const const_iterator &o) const
struct Entry

an item with its keys

Public Members

T item
K f
K g