#include <ckpttn/bpqueue.hpp>
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.
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
Constructors, destructors, conversion operators
Public functions
- auto operator=(const BPQueue&) -> BPQueue & -> auto deleted constexpr
- auto operator=(BPQueue&&) noexcept -> BPQueue & -> auto defaulted constexpr
- 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 append_direct(Item& it) noexcept -> void -> auto constexpr
- Append item with internal 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>
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>:: 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>:: append_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>:: 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>:: 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 |
---|