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 {
 
// --------------------------------------------------------------------------------------------------------------------
// `Bits` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store, bool is_const>
class Bits {
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.
    Bits(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.
    Bits() = default;
    Bits(Bits&&) = default;
    Bits(Bits const&) = default;
    Bits& operator=(Bits&&) = default;
    Bits& operator=(Bits const&) = default;
 
    // Iterators must be comparable (this is needed so that any range-for loop will work).
    constexpr bool operator==(Bits 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 Bits(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 Bits(m_store, m_store->size()); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr Bits& operator++() {
        ++m_index;
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr Bits operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr Bits& operator--() {
        --m_index;
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr Bits operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `SetBits` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store>
class SetBits {
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.
    SetBits(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.
    SetBits() = default;
    SetBits(SetBits&&) = default;
    SetBits(SetBits const&) = default;
    SetBits& operator=(SetBits&&) = default;
    SetBits& operator=(SetBits const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(SetBits 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 SetBits(m_store, m_store->first_set()); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return SetBits(m_store, std::nullopt); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr SetBits& 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 SetBits operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr SetBits& 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 SetBits operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `UnsetBits` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store>
class UnsetBits {
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.
    UnsetBits(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.
    UnsetBits() = default;
    UnsetBits(UnsetBits&&) = default;
    UnsetBits(UnsetBits const&) = default;
    UnsetBits& operator=(UnsetBits&&) = default;
    UnsetBits& operator=(UnsetBits const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(UnsetBits 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 UnsetBits(m_store, m_store->first_unset()); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return UnsetBits(m_store, std::nullopt); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr UnsetBits& 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 UnsetBits operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr UnsetBits& 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 UnsetBits operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
// --------------------------------------------------------------------------------------------------------------------
// `Words` ...
// --------------------------------------------------------------------------------------------------------------------

template<BitStore Store>
class Words {
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
    Words(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.
    Words() = default;
    Words(Words&&) = default;
    Words(Words const&) = default;
    Words& operator=(Words&&) = default;
    Words& operator=(Words const&) = default;
 
    // Iterators must be comparable (this is how the range-for loops work).
    constexpr bool operator==(Words 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 Words(m_store, 0); }
 
    // Any call to `end` returns a new iterator that is not initialized.
    constexpr auto end() const { return Words(m_store, m_store->words()); }
 
    // Increment the iterator, returning the new value (the `i++` operator).
    constexpr Words& operator++() {
        ++m_index;
        return *this;
    }
 
    // Increment the iterator, returning the previous value (the `++i` operator).
    constexpr Words operator++(int) {
        auto prev = *this;
        ++*this;
        return prev;
    }
 
    // Decrement the iterator, returning the new value (the `--i` operator).
    constexpr Words& operator--() {
        --m_index;
        return *this;
    }
 
    // Decrement the iterator, returning the previous value (the `--i` operator).
    constexpr Words operator--(int) {
        auto prev = *this;
        --*this;
        return prev;
    }
};
 
} // namespace gf2