template<typename Tp, typename Int = int32_t, typename Sequence = std::vector<Dllist<std::pair<Tp, std::make_unsigned_t<Int>>>>>
BPQueue class

Bounded priority queue.

Template parameters
Tp
Int
Sequence

Bounded Priority Queue with integer keys in [a..b]. Implemented by an array (bucket) of doubly-linked lists. Efficient if the keys are bounded by a small integer value.

Note that this class does not own PQ nodes. This feature allows these nodes sharable in both doubly linked list class and this class. In the Fiduccia-Mattheyses algorithm, nodes are either attached to the gain buckets (PQ) or to the waiting_list (doubly-linked list), but cannot be in both at the same time.

Another improvement is to increase the size of the array by one element, i.e. (b - a + 2). The extra dummy array element (called sentinel) is used to reduce the boundary checking during updates.

All the member functions assume that the keys are inside the bounds.

Priority Queue (BPQueue) with integer keys [0..4]:

Key 4: ┌─┐
       │7│ -> ...
       └─┘

Key 3: ┌─┐
       │2│ -> │9│ -> ...
       └─┘

Key 2: (empty)

Key 1: ┌─┐
       │5│ -> │1│ -> │8│ -> ...
       └─┘

Key 0: (empty)

Sentinel: (dummy element for boundary checks)

Max key: 4

Constructors, destructors, conversion operators

BPQueue(Int a, Int b) constexpr
Construct a new BPQueue object.

Public functions

auto is_empty() const noexcept -> bool -> auto constexpr
Whether the BPQueue is empty.
auto set_key(Item& it, Int gain) noexcept -> void -> auto constexpr
Set the key object.
auto get_max() const noexcept -> Int -> auto constexpr
Get the max value.
auto clear() noexcept -> void -> auto constexpr
Clear reset the PQ.
auto appendleft_direct(Item& it) noexcept -> void -> auto constexpr
Append item with internal key.
auto appendleft(Item& it, Int k) noexcept -> void -> auto constexpr
Append item with external key.
auto append(Item& it, Int k) noexcept -> void -> auto constexpr
Append item with external key.
auto popleft() noexcept -> Item & -> auto constexpr
Pop node with the highest key.
auto decrease_key(Item& it, UInt delta) noexcept -> void -> auto constexpr
Decrease key by delta.
auto increase_key(Item& it, UInt delta) noexcept -> void -> auto constexpr
Increase key by delta.
auto modify_key(Item& it, Int delta) noexcept -> void -> auto constexpr
Modify key by delta.
auto detach(Item& it) noexcept -> void -> auto constexpr
Detach the item from BPQueue.
auto begin() -> BpqIterator< Tp, Int > -> auto constexpr
Iterator point to the begin.
auto end() -> BpqIterator< Tp, Int > -> auto constexpr
Iterator point to the end.

Function documentation

template<typename Tp, typename Int, typename Sequence>
BPQueue<Tp, Int, Sequence>::BPQueue(Int a, Int b) constexpr

Construct a new BPQueue object.

Parameters
a in lower bound
b in upper bound

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::is_empty() const noexcept -> bool constexpr

Whether the BPQueue is empty.

Returns true

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::set_key(Item& it, Int gain) noexcept -> void constexpr

Set the key object.

Parameters
it out the item
gain in the key of it

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::get_max() const noexcept -> Int constexpr

Get the max value.

Returns Int maximum value

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::appendleft_direct(Item& it) noexcept -> void constexpr

Append item with internal key.

Parameters
it in/out the item

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::appendleft(Item& it, Int k) noexcept -> void constexpr

Append item with external key.

Parameters
it in/out the item
k in the key

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::append(Item& it, Int k) noexcept -> void constexpr

Append item with external key.

Parameters
it in/out the item
k in the key

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::popleft() noexcept -> Item & constexpr

Pop node with the highest key.

Returns Dllink&

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::decrease_key(Item& it, UInt delta) noexcept -> void constexpr

Decrease key by delta.

Parameters
it in/out the item
delta in the change of the key

Note that the order of items with same key will not be preserved. For the Fiduccia-Mattheyses algorithm, this is a prefered behavior.

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::increase_key(Item& it, UInt delta) noexcept -> void constexpr

Increase key by delta.

Parameters
it in/out the item
delta in the change of the key

Note that the order of items with same key will not be preserved. For the Fiduccia-Mattheyses algorithm, this is a prefered behavior.

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::modify_key(Item& it, Int delta) noexcept -> void constexpr

Modify key by delta.

Parameters
it in/out the item
delta in the change of the key

Note that the order of items with same key will not be preserved. For Fiduccia-Mattheyses algorithm, this is a prefered behavior.

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::detach(Item& it) noexcept -> void constexpr

Detach the item from BPQueue.

Parameters
it in/out the item

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::begin() -> BpqIterator< Tp, Int > constexpr

Iterator point to the begin.

Returns BpqIterator

template<typename Tp, typename Int, typename Sequence>
auto BPQueue<Tp, Int, Sequence>::end() -> BpqIterator< Tp, Int > constexpr

Iterator point to the end.

Returns BpqIterator