Template Class bpqueue

Page Contents

Template Parameter Order

  1. typename _Tp

  2. typename Int

  3. typename _Sequence

Class Documentation

template<typename _Tp, typename Int = int32_t, typename _Sequence = std::vector<dllink<std::pair<_Tp, std::make_unsigned_t<Int>>>>>
class bpqueue

bounded priority queue

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

Note that this class does not own the PQ nodes. This feature makes the nodes sharable between doubly linked list class and this class. In the FM algorithm, the node either attached to the gain buckets (PQ) or in the waitinglist (doubly linked list), but not in both of them in the same time.

Another improvement is to make the array size one element bigger i.e. (b - a + 2). The extra dummy array element (which is called sentinel) is used to reduce the boundary checking during updating.

All the member functions assume that the keys are within the bound.

: support std::pmr

Public Types

using value_type = typename _Sequence::value_type
using reference = typename _Sequence::reference
using const_reference = typename _Sequence::const_reference
using size_type = typename _Sequence::size_type
using container_type = _Sequence

Public Functions

inline constexpr bpqueue(Int a, Int b)

Construct a new bpqueue object.

Parameters

  • a – [in] lower bound

  • b – [in] upper bound

bpqueue(const bpqueue&) = delete
~bpqueue() = default
constexpr auto operator=(const bpqueue&) -> bpqueue& = delete
constexpr bpqueue(bpqueue&&) noexcept = default
constexpr auto operator=(bpqueue&&) noexcept -> bpqueue& = default
inline constexpr auto is_empty() const noexcept -> bool

whether the bpqueue is empty.

Returns

true

Returns

false

inline constexpr auto set_key(Item &it, Int gain) noexcept -> void

Set the key object.

Parameters

  • it – [out] the item

  • gain – [in] the key of it

inline constexpr auto get_max() const noexcept -> Int

Get the max value.

Returns

T maximum value

inline constexpr auto clear() noexcept -> void

clear reset the PQ

inline constexpr auto append_direct(Item &it) noexcept -> void

append item with internal key

Parameters

it – [inout] the item

inline constexpr auto append(Item &it, Int k) noexcept -> void

append item with external key

Parameters

  • it – [inout] the item

  • k – [in] the key

inline constexpr auto popleft() noexcept -> Item&

append from list

pop node with the highest key

Parameters

nodes – [inout]

Returns

dllink&

inline constexpr auto decrease_key(Item &it, UInt delta) noexcept -> void

decrease key by delta

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

Parameters

  • it – [inout] the item

  • delta – [in] the change of the key

inline constexpr auto increase_key(Item &it, UInt delta) noexcept -> void

increase key by delta

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

Parameters

  • it – [inout] the item

  • delta – [in] the change of the key

inline constexpr auto modify_key(Item &it, Int delta) noexcept -> void

modify key by delta

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

Parameters

  • it – [inout] the item

  • delta – [in] the change of the key

inline constexpr auto detach(Item &it) noexcept -> void

detach the item from bpqueue

Parameters

it – [inout] the item

inline constexpr auto begin() -> bpq_iterator<_Tp, Int>

iterator point to begin

Returns

bpq_iterator

inline constexpr auto end() -> bpq_iterator<_Tp, Int>

iterator point to end

Returns

bpq_iterator