| 227 | /** A bitset implementation backed by N integers of type I. */ |
| 228 | template<typename I, unsigned N> |
| 229 | class MultiIntBitSet |
| 230 | { |
| 231 | // Only binary, unsigned, integer, types allowed. |
| 232 | static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2); |
| 233 | // Cannot be empty. |
| 234 | static_assert(N > 0); |
| 235 | /** The number of bits per integer. */ |
| 236 | static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits; |
| 237 | /** Number of elements this set type supports. */ |
| 238 | static constexpr unsigned MAX_SIZE = LIMB_BITS * N; |
| 239 | // No overflow allowed here. |
| 240 | static_assert(MAX_SIZE / LIMB_BITS == N); |
| 241 | /** Array whose member integers store the bits of the set. */ |
| 242 | std::array<I, N> m_val; |
| 243 | /** Dummy type to return using end(). Only used for comparing with Iterator. */ |
| 244 | class IteratorEnd |
| 245 | { |
| 246 | friend class MultiIntBitSet; |
| 247 | constexpr IteratorEnd() = default; |
| 248 | public: |
| 249 | constexpr IteratorEnd(const IteratorEnd&) = default; |
| 250 | }; |
| 251 | /** Iterator type returned by begin(), which efficiently iterates all 1 positions. */ |
| 252 | class Iterator |
| 253 | { |
| 254 | friend class MultiIntBitSet; |
| 255 | const std::array<I, N>* m_ptr; /**< Pointer to array to fetch bits from. */ |
| 256 | I m_val; /**< The remaining bits of (*m_ptr)[m_idx]. */ |
| 257 | unsigned m_pos; /**< The last reported position. */ |
| 258 | unsigned m_idx; /**< The index in *m_ptr currently being iterated over. */ |
| 259 | constexpr Iterator(const std::array<I, N>& ref) noexcept : m_ptr(&ref), m_idx(0) |
| 260 | { |
| 261 | do { |
| 262 | m_val = (*m_ptr)[m_idx]; |
| 263 | if (m_val) { |
| 264 | m_pos = std::countr_zero(m_val) + m_idx * LIMB_BITS; |
| 265 | break; |
| 266 | } |
| 267 | ++m_idx; |
| 268 | } while(m_idx < N); |
| 269 | } |
| 270 | |
| 271 | public: |
| 272 | /** Do not allow external code to construct an Iterator. */ |
| 273 | Iterator() = delete; |
| 274 | // Copying is allowed. |
| 275 | constexpr Iterator(const Iterator&) noexcept = default; |
| 276 | constexpr Iterator& operator=(const Iterator&) noexcept = default; |
| 277 | /** Test whether we are done (can only compare with IteratorEnd). */ |
| 278 | friend constexpr bool operator==(const Iterator& a, const IteratorEnd&) noexcept |
| 279 | { |
| 280 | return a.m_idx == N; |
| 281 | } |
| 282 | /** Progress to the next 1 bit (only if != IteratorEnd). */ |
| 283 | constexpr Iterator& operator++() noexcept |
| 284 | { |
| 285 | Assume(m_idx < N); |
| 286 | m_val &= m_val - I{1U}; |