Branch data     Line data    Source code

       1                 :            : #pragma once
       2                 :            : 
       3                 :            : #include <algorithm>
       4                 :            : #include <cassert>
       5                 :            : #include <cstddef>
       6                 :            : #include <numeric>
       7                 :            : #include <utility>
       8                 :            : 
       9                 :            : template <typename Type, std::size_t Capacity>
      10                 :            :     requires std::unsigned_integral<Type>  //
      11                 :            :           && (0U < Capacity)               //
      12                 :            :           && (Capacity - 1U <= std::numeric_limits<Type>::max())
      13                 :            : class IndexCoordinator
      14                 :            : {
      15                 :            :    public:
      16                 :          1 :     IndexCoordinator()
      17                 :          1 :         : size_(0U)
      18                 :            :     {
      19                 :          1 :         std::iota(std::begin(value_), std::end(value_), 0U);
      20                 :          1 :         std::iota(std::begin(where_), std::end(where_), 0U);
      21                 :          1 :     }
      22                 :            : 
      23                 :          3 :     auto constexpr capacity() const noexcept -> std::size_t
      24                 :            :     {
      25                 :          3 :         return Capacity;
      26                 :            :     }
      27                 :            : 
      28                 :            :     /// @brief number of used values
      29                 :          5 :     auto size() const noexcept -> std::size_t
      30                 :            :     {
      31                 :          5 :         return size_;
      32                 :            :     }
      33                 :            : 
      34                 :            :     /// @brief take one value
      35                 :            :     /// @return one value in the range [0, Capacity)
      36                 :          2 :     [[nodiscard]] auto take() -> Type
      37                 :            :     {
      38                 :          2 :         assert(size_ < Capacity);
      39                 :          2 :         return value_[size_++];
      40                 :            :     }
      41                 :            : 
      42                 :            :     /// @brief give `value` back
      43                 :            :     /// @param value `value` was generated by `take()`
      44                 :          2 :     auto give(Type value) -> void
      45                 :            :     {
      46                 :            :         assert(value < Capacity);
      47                 :            : 
      48                 :          2 :         assert(0U < size_);
      49                 :          2 :         assert(where_[value] < size_);
      50                 :            : 
      51                 :          2 :         --size_;
      52                 :            : 
      53                 :          2 :         assert(value_[where_[value]] == value);
      54                 :          2 :         assert(where_[value_[size_]] == size_);
      55                 :            : 
      56                 :          2 :         auto const lhs_value = value;
      57                 :          2 :         auto const rhs_value = value_[size_];
      58                 :          2 :         auto const lhs_where = where_[value];
      59                 :          2 :         auto const rhs_where = size_;
      60                 :            : 
      61                 :            :         using std::swap;
      62                 :          2 :         swap(where_[lhs_value], where_[rhs_value]);
      63                 :          2 :         swap(value_[lhs_where], value_[rhs_where]);
      64                 :            : 
      65                 :          2 :         assert(value_[size_] == value);
      66                 :          2 :         assert(where_[value] == size_);
      67                 :          2 :     }
      68                 :            : 
      69                 :            :    private:
      70                 :            :     std::size_t size_ = 0U;
      71                 :            : 
      72                 :            :     Type value_[Capacity];
      73                 :            :     Type where_[Capacity];
      74                 :            : };