Template Class DialQueue

• Defined in File DialQueue.h

Class Documentation

template<class T, std::integral K = std::uint32_t>
class DialQueue

a monotone queue of items with integer keys K on a circular window of buckets, the keys beyond it in a radix heap

Public Types

using Item = T

the type of the items

using Key = K

the type of the keys

Public Functions

explicit DialQueue(std::size_t c = 1023)

an empty queue whose window has room for the keys up to c above the last one extracted: W, the least power of 2 above c, buckets

Pre:

c >= 0

void push(const T &x, K k)

pushes x with the key k

Pre:

k is not smaller than the last key extracted (any key before the first extraction and after clear())

const T &top(void)

an item of least key, the last pushed among those of its bucket that did not come through the overflow (equal keys in no given order)

Pre:

the queue is not empty

K topKey(void)

the least key

Pre:

the queue is not empty

T pop(void)

removes top() and returns it

Pre:

the queue is not empty

inline bool empty(void) const

inline std::size_t size(void) const

void clear(void)

removes the items, the buckets keeping their memory; any key may be pushed next

inline std::size_t window(void) const

the number of buckets of the window