:github_url: https://github.com/svenevs/exhale-companion


.. _program_listing_file_ckpttncpp_bpqueue.hpp:

Program Listing for File bpqueue.hpp
====================================

|exhale_lsh| :ref:`Return to documentation for file <file_ckpttncpp_bpqueue.hpp>` (``ckpttncpp/bpqueue.hpp``)

.. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS

.. code-block:: cpp

   #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};
   }