Program Listing for File bpqueue.hpp

↰ Return to documentation for file (ckpttncpp/bpqueue.hpp)

#pragma once

#include "dllist.hpp" // import dllink
#include <cassert>
#include <gsl/span>
// #include <type_traits>
#include <vector>

// Forward declaration for begin() end()
template <typename _Tp, typename Int>
class bpq_iterator;

template <typename _Tp, typename Int = int32_t,
    typename _Sequence = std::vector<dllink<std::pair<_Tp, std::make_unsigned_t<Int>>>>>
//          class Allocator = typename std::allocator<dllink<std::pair<_Tp,
//          Int>> > >
class bpqueue
{
    using UInt = std::make_unsigned_t<Int>;

    friend bpq_iterator<_Tp, Int>;
    using Item = dllink<std::pair<_Tp, UInt>>;

    static_assert(std::is_same_v<Item, typename _Sequence::value_type>,
        "value_type must be the same as the underlying container");

  public:
    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;

  private:
    Item sentinel {};

    _Sequence bucket;
    UInt max {};
    Int offset;
    UInt high;

    // using alloc_t = decltype(bucket.get_allocator());

  public:
    constexpr bpqueue(Int a, Int b)
        : bucket(static_cast<UInt>(b - a) + 2U)
        , offset(a - 1)
        , high(static_cast<UInt>(b - offset))
    {
        assert(a <= b);
        static_assert(
            std::is_integral<Int>::value, "bucket's key must be an integer");
        bucket[0].append(this->sentinel); // sentinel
    }

    bpqueue(const bpqueue&) = delete; // don't copy
    ~bpqueue() = default;
    constexpr auto operator=(const bpqueue&)
        -> bpqueue& = delete; // don't assign
    constexpr bpqueue(bpqueue&&) noexcept = default;
    constexpr auto operator=(bpqueue&&) noexcept
        -> bpqueue& = default; // don't assign

    [[nodiscard]] constexpr auto is_empty() const noexcept -> bool
    {
        return this->max == 0U;
    }

    constexpr auto set_key(Item& it, Int gain) noexcept -> void
    {
        it.data.second = static_cast<UInt>(gain - this->offset);
    }

    [[nodiscard]] constexpr auto get_max() const noexcept -> Int
    {
        return this->offset + Int(this->max);
    }

    constexpr auto clear() noexcept -> void
    {
        while (this->max > 0)
        {
            this->bucket[this->max].clear();
            this->max -= 1;
        }
    }

    constexpr auto append_direct(Item& it) noexcept -> void
    {
        assert(static_cast<Int>(it.data.second) > this->offset);
        this->append(it, Int(it.data.second));
    }

    constexpr auto append(Item& it, Int k) noexcept -> void
    {
        assert(k > this->offset);
        it.data.second = UInt(k - this->offset);
        if (this->max < it.data.second)
        {
            this->max = it.data.second;
        }
        this->bucket[it.data.second].append(it);
    }

    // constexpr auto appendfrom(gsl::span<Item> nodes) noexcept -> void
    // {
    //     for (auto& it : nodes)
    //     {
    //         it.data.second -= this->offset;
    //         assert(it.data.second > 0);
    //         this->bucket[it.data.second].append(it);
    //     }
    //     this->max = this->high;
    //     while (this->bucket[this->max].is_empty())
    //     {
    //         this->max -= 1;
    //     }
    // }

    constexpr auto popleft() noexcept -> Item&
    {
        auto& res = this->bucket[this->max].popleft();
        while (this->bucket[this->max].is_empty())
        {
            this->max -= 1;
        }
        return res;
    }

    constexpr auto decrease_key(Item& it, UInt delta) noexcept -> void
    {
        // this->bucket[it.data.second].detach(it)
        it.detach();
        it.data.second -= delta;
        assert(it.data.second > 0);
        assert(it.data.second <= this->high);
        this->bucket[it.data.second].append(it); // FIFO
        if (this->max < it.data.second)
        {
            this->max = it.data.second;
            return;
        }
        while (this->bucket[this->max].is_empty())
        {
            this->max -= 1;
        }
    }

    constexpr auto increase_key(Item& it, UInt delta) noexcept -> void
    {
        // this->bucket[it.data.second].detach(it)
        it.detach();
        it.data.second += delta;
        assert(it.data.second > 0);
        assert(it.data.second <= this->high);
        this->bucket[it.data.second].appendleft(it); // LIFO
        if (this->max < it.data.second)
        {
            this->max = it.data.second;
        }
    }

    constexpr auto modify_key(Item& it, Int delta) noexcept -> void
    {
        if (it.is_locked())
        {
            return;
        }
        if (delta > 0)
        {
            this->increase_key(it, UInt(delta));
        }
        else if (delta < 0)
        {
            this->decrease_key(it, UInt(-delta));
        }
    }

    constexpr auto detach(Item& it) noexcept -> void
    {
        // this->bucket[it.data.second].detach(it)
        it.detach();
        while (this->bucket[this->max].is_empty())
        {
            this->max -= 1;
        }
    }

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

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

    // constexpr auto& items()
    // {
    //     return *this;
    // }

    // constexpr const auto& items() const
    // {
    //     return *this;
    // }

    // using coro_t = boost::coroutines2::coroutine<dllink<T>&>;
    // using pull_t = typename coro_t::pull_type;

    // /**
    //  * @brief item generator
    //  *
    //  * @return pull_t
    //  */
    // auto items() -> pull_t
    // {
    //     auto func = [&](typename coro_t::push_type& yield) {
    //         auto curkey = this->max;
    //         while (curkey > 0)
    //         {
    //             for (const auto& item : this->bucket[curkey].items())
    //             {
    //                 yield(item);
    //             }
    //             curkey -= 1;
    //         }
    //     };
    //     return pull_t(func);
    // }
};

template <typename _Tp, typename Int = int32_t>
class bpq_iterator
{
    using UInt = std::make_unsigned_t<Int>;

    // using value_type = _Tp;
    // using key_type = Int;
    using Item = dllink<std::pair<_Tp, UInt>>;

  private:
    bpqueue<_Tp, Int>& bpq;
    UInt curkey;
    dll_iterator<std::pair<_Tp, UInt>>
        curitem;
    constexpr auto curlist() -> Item&
    {
        return this->bpq.bucket[this->curkey];
    }

  public:
    constexpr bpq_iterator(bpqueue<_Tp, Int>& bpq, UInt curkey)
        : bpq {bpq}
        , curkey {curkey}
        , curitem {bpq.bucket[curkey].begin()}
    {
    }

    constexpr auto operator++() -> bpq_iterator&
    {
        ++this->curitem;
        while (this->curitem == this->curlist().end())
        {
            do
            {
                this->curkey -= 1;
            } while (this->curlist().is_empty());
            this->curitem = this->curlist().begin();
        }
        return *this;
    }

    constexpr auto operator*() -> Item&
    {
        return *this->curitem;
    }

    friend constexpr auto operator==(
        const bpq_iterator& lhs, const bpq_iterator& rhs) -> bool
    {
        return lhs.curitem == rhs.curitem;
    }

    friend constexpr auto operator!=(
        const bpq_iterator& lhs, const bpq_iterator& rhs) -> bool
    {
        return !(lhs == rhs);
    }
};

template <typename _Tp, typename Int, class _Sequence>
inline constexpr auto bpqueue<_Tp, Int, _Sequence>::begin()
    -> bpq_iterator<_Tp, Int>
{
    return {*this, this->max};
}

template <typename _Tp, typename Int, class _Sequence>
inline constexpr auto bpqueue<_Tp, Int, _Sequence>::end()
    -> bpq_iterator<_Tp, Int>
{
    return {*this, 0};
}