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/BitStore.h>
#include <gf2/BitRef.h>
 
namespace gf2 {
 
// --------------------------------------------------------------------------------------------------------------------
// `BitsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore 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 Store*, 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(BitsIter const&) = default;
    BitsIter& operator=(BitsIter&&) = default;
    BitsIter& operator=(BitsIter const&) = default;
 
    // Iterators must be comparable (this is needed so that any range-for loop will work).
    constexpr bool operator==(BitsIter const& 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` 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<BitStore Store>
class SetBitsIter {
private:
    const 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(Store const* 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(SetBitsIter const&) = default;
    SetBitsIter& operator=(SetBitsIter&&) = default;
    SetBitsIter& operator=(SetBitsIter const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(SetBitsIter const& 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 = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr SetBitsIter& operator--() {
        if (m_index.has_value()) m_index = previous_set(*m_store, *m_index);
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr SetBitsIter operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `UnsetBitsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store>
class UnsetBitsIter {
private:
    const 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(Store const* 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(UnsetBitsIter const&) = default;
    UnsetBitsIter& operator=(UnsetBitsIter&&) = default;
    UnsetBitsIter& operator=(UnsetBitsIter const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(UnsetBitsIter const& 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 = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr UnsetBitsIter& operator--() {
        if (m_index.has_value()) m_index = previous_unset(*m_store, *m_index);
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr UnsetBitsIter operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `WordsIter` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store>
class WordsIter {
private:
    const 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_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(Store const* 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(WordsIter const&) = default;
    WordsIter& operator=(WordsIter&&) = default;
    WordsIter& operator=(WordsIter const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(WordsIter const& 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