Iterators.h

Go to the documentation of this file.

#pragma once
// SPDX-FileCopyrightText: 2025 Nessan Fitzmaurice <nzznfitz+gh@icloud.com>
// SPDX-License-Identifier: MIT

 
#include <gf2/unsigned_word.h>
#include <gf2/store_word.h>
#include <optional>
 
namespace gf2 {
 
// clang-format off
// Forward declare some classes of interest:
template<typename Store> class BitStore;
template<typename Store> class BitRef;
// clang-format on
 
// --------------------------------------------------------------------------------------------------------------------
// `BitsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<typename Store, bool is_const>
class BitsIter {
public:
    // We keep a pointer to the parent bit-store which is either const or non-const.
    using store_pointer = std::conditional_t<is_const, const BitStore<Store>*, BitStore<Store>*>;
 
    // The value type is either a `bool` or a `BitRef` depending on the constness of the iterator.
    using value_type = std::conditional_t<is_const, bool, BitRef<Store>>;
 
    // The difference type is always a `std::ptrdiff_t` (required by the iterator concept).
    using difference_type = std::ptrdiff_t;
 
private:
    store_pointer m_store = nullptr;
    usize         m_index = 0;
 
public:
    // Our constructor captures a (const or non-const) pointer to the store and the index for the bit of interest.
    BitsIter(store_pointer store, usize idx) : m_store(store), m_index{idx} {}
 
    // Iterator are required to act like value types so must be default constructible, moveable, and copyable.
    BitsIter() = default;
    BitsIter(BitsIter&&) = default;
    BitsIter(const BitsIter&) = default;
    BitsIter& operator=(BitsIter&&) = default;
    BitsIter& operator=(const BitsIter&) = default;
 
    // Iterators must be comparable (this is needed so that any range-for loop will work).
    constexpr bool operator==(const BitsIter& other) const {
        return m_store == other.m_store && m_index == other.m_index;
    }
 
    // Returns the item that the iterator is currently pointing to.
    // The `decltype(auto)` will either be a `bool` or a `BitRef<Word>` depending on the constness of the pointer.
    constexpr decltype(auto) operator*() const { return m_store->operator[](m_index); }
 
    // Any call to `begin()` returns a new iterator pointing to the first bit in the store.
    constexpr auto begin() const { return BitsIter(m_store, 0); }
 
    // Any call to `end()` returns a new iterator pointing to the bit after the last bit in the store.
    constexpr auto end() const { return BitsIter(m_store, m_store->size()); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr BitsIter& operator++() {
        ++m_index;
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr BitsIter operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr BitsIter& operator--() {
        --m_index;
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr BitsIter operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `SetBitsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<typename Store>
class SetBitsIter {
private:
    const BitStore<Store>* m_store = nullptr;      // The store we're iterating over
    std::optional<usize>   m_index = std::nullopt; // Search after this index.
 
public:
    // The value type is a `usize` (the index of the set bit).
    using value_type = usize;
 
    // The difference type is always a `std::ptrdiff_t` (required by the iterator concept).
    using difference_type = std::ptrdiff_t;
 
    // Our constructor captures a pointer to the store and sets the index to uninitialized.
    SetBitsIter(const BitStore<Store>* store, std::optional<usize> idx = std::nullopt) : m_store(store), m_index{idx} {
        // Empty body ...
    }
 
    // Iterator are required to act like value types so must be default constructible, moveable, and copyable.
    SetBitsIter() = default;
    SetBitsIter(SetBitsIter&&) = default;
    SetBitsIter(const SetBitsIter&) = default;
    SetBitsIter& operator=(SetBitsIter&&) = default;
    SetBitsIter& operator=(const SetBitsIter&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(const SetBitsIter& other) const {
        return m_store == other.m_store && m_index == other.m_index;
    }
 
    // What is the iterator currently pointing to? (this is what the range-for loop will use).
    constexpr value_type operator*() const { return *m_index; }
 
    // Any call to `begin` returns a new iterator pointing to the first set bit in the store.
    constexpr auto begin() const { return SetBitsIter(m_store, m_store->first_set()); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return SetBitsIter(m_store, std::nullopt); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr SetBitsIter& operator++() {
        if (m_index.has_value()) m_index = m_store->next_set(*m_index);
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr SetBitsIter operator++(int) {
        auto prev = m_index;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr SetBitsIter& operator--() {
        if (m_index.has_value()) m_index = m_store->previous_set(*m_index);
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr SetBitsIter operator--(int) {
        auto prev = m_index;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `UnsetBitsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<typename Store>
class UnsetBitsIter {
private:
    const BitStore<Store>* m_store = nullptr;      // The store we're iterating over
    std::optional<usize>   m_index = std::nullopt; // Search after this index.
 
public:
    // The value type is a `usize` (the index of the unset bit).
    using value_type = usize;
 
    // The difference type is always a `std::ptrdiff_t` (required by the iterator concept).
    using difference_type = std::ptrdiff_t;
 
    // Our constructor captures a pointer to the store and sets the index to uninitialized.
    UnsetBitsIter(const BitStore<Store>* store, std::optional<usize> idx = std::nullopt) :
        m_store(store), m_index{idx} {
        // Empty body ...
    }
 
    // Iterator are required to act like value types so must be default constructible, moveable, and copyable.
    UnsetBitsIter() = default;
    UnsetBitsIter(UnsetBitsIter&&) = default;
    UnsetBitsIter(const UnsetBitsIter&) = default;
    UnsetBitsIter& operator=(UnsetBitsIter&&) = default;
    UnsetBitsIter& operator=(const UnsetBitsIter&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(const UnsetBitsIter& other) const {
        return m_store == other.m_store && m_index == other.m_index;
    }
 
    // What is the iterator currently pointing to? (this is what the range-for loop will use).
    constexpr value_type operator*() const { return *m_index; }
 
    // Any call to `begin` returns a new iterator pointing to the first unset bit in the store.
    constexpr auto begin() const { return UnsetBitsIter(m_store, m_store->first_unset()); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return UnsetBitsIter(m_store, std::nullopt); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr UnsetBitsIter& operator++() {
        if (m_index.has_value()) m_index = m_store->next_unset(*m_index);
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr UnsetBitsIter operator++(int) {
        auto prev = m_index;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr UnsetBitsIter& operator--() {
        if (m_index.has_value()) m_index = m_store->previous_unset(*m_index);
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr UnsetBitsIter operator--(int) {
        auto prev = m_index;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `WordsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<typename Store>
class WordsIter {
private:
    const BitStore<Store>* m_store = nullptr;
    usize                  m_index = 0;
 
public:
    // The value type is the word type of the store with any const qualification dropped.
    using value_type = typename store_word<Store>::word_type;
 
    // The difference type is always a `std::ptrdiff_t` (required by the iterator concept).
    using difference_type = std::ptrdiff_t;
 
    // Our constructor captures a pointer to the store and sets the index to 0
    WordsIter(const BitStore<Store>* store, usize idx = 0) : m_store(store), m_index{idx} {
        // Empty body ...
    }
 
    // Iterator are required to act like value types so must be default constructible, moveable, and copyable.
    WordsIter() = default;
    WordsIter(WordsIter&&) = default;
    WordsIter(const WordsIter&) = default;
    WordsIter& operator=(WordsIter&&) = default;
    WordsIter& operator=(const WordsIter&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(const WordsIter& other) const {
        return m_store == other.m_store && m_index == other.m_index;
    }
 
    // What is the iterator currently pointing to? (this is what the range-for loop will use).
    constexpr value_type operator*() const { return m_store->word(m_index); }
 
    // Any call to `begin` returns a new iterator pointing to the first unset bit in the store.
    constexpr auto begin() const { return WordsIter(m_store, 0); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return WordsIter(m_store, m_store->words()); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr WordsIter& operator++() {
        ++m_index;
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr WordsIter operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr WordsIter& operator--() {
        --m_index;
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr WordsIter operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
} // namespace gf2