// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 2018 - 2025 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_linear_index_iterator_h #define dealii_linear_index_iterator_h #include #include #include DEAL_II_NAMESPACE_OPEN /** * Many classes in deal.II, such as FullMatrix, TransposeTable, and * SparseMatrix, store their data in contiguous buffers (though the * interpretation of what the elements of these buffers represent * can, of course, be complex). For example, FullMatrix and TransposeTable * store their data in row major and column major order respectively, whereas * for SparseMatrix the mapping from buffer location to matrix entry * $\mathbf{A}(i, j)$ is more complicated. In any case, however, the * contiguous arrangements of elements enables random access iteration. * * LinearIndexIterator provides most of the functionality needed to write * iterators for these classes. LinearIndexIterator is essentially a * simplified version of boost::iterator_facade that assumes * AccessorType provides certain members (documented below) that * completely describe the state of the iterator. The intended use of this * class is for containers to define their own accessor classes and then use * the curiously recurring template pattern (CRTP) technique to define their * iterators. For example, here is a container that uses LinearIndexIterator * to define its own iterator classes: * * @code * template * class Container * { * protected: * // forward declaration for friendship * template * class Iterator; * * template * class Accessor * { * public: * // const iterators store a const pointer * using container_pointer_type * = std::conditional_t*, * Container*>; * * // This alias is assumed to exist. * using size_type = std::size_t; * * // constructor. * Accessor(const container_pointer_type container, * const std::ptrdiff_t index); * * // constructor. * Accessor(); * * // get a constant reference to the current value. * const T& value() const; * * protected: * container_pointer_type container; * std::ptrdiff_t linear_index; * * // LinearIndexIterator needs access to linear_index and container. * friend class LinearIndexIterator, * Accessor>; * }; * * template * class Iterator : public LinearIndexIterator, * Accessor> * { * // Constructor. * Iterator(Container * const container, const std::ptrdiff_t index); * * // implement additional constructors here, but all state should be * // contained in the Accessor, which is a member of the base class. * }; * * public: * using size_type = std::size_t; * using const_iterator = Iterator; * using iterator = Iterator; * * iterator begin (); * iterator end (); * * const_iterator begin () const; * const_iterator end () const; * }; * @endcode * * @tparam DerivedIterator As shown in the example above, concrete iterator * classes should use this class with the CRTP technique: this provides the * boiler-plate comparison and arithmetic operators for iterators. This is * necessary for, e.g., LinearIndexIterator::operator++() to return the * correct type. * * @tparam AccessorType LinearIndexIterator assumes that the * AccessorType template parameter has the following members * which completely describe the current state of the iterator: *
    *
  1. A pointer named container to the original container (e.g., * the relevant SparseMatrix). This should be a const pointer * for const iterators.
  2. *
  3. An array index named linear_index that stores the current * position in the container's storage buffer. linear_index does * not need to be an integer: it could be a class type (convertible to the * correct index type of the container) that implements * operator+=, operator<, and * operator==. For example, one could implement a strided * iterator by implementing operator+= and * operator- with multiplicative factors.
  4. *
* In addition, AccessorType should declare the relevant * LinearIndexIterator instantiation to be a friend and define a * size_type type. * * @note TransposeTable uses this template to implement its iterators. */ template class LinearIndexIterator { public: /** * Iterator category. */ #ifdef DEAL_II_HAVE_CXX20 using iterator_category = std::contiguous_iterator_tag; #else using iterator_category = std::random_access_iterator_tag; #endif /** * An alias for the type you get when you dereference an iterator of the * current kind. */ using value_type = AccessorType; /** * Difference type. */ using difference_type = std::ptrdiff_t; /** * Reference type. */ using reference = const value_type &; /** * Pointer type. */ using pointer = const value_type *; /** * Size type used by the underlying container. */ using size_type = typename value_type::size_type; /** * Copy operator. */ DerivedIterator & operator=(const DerivedIterator &it); /** * Prefix increment. */ DerivedIterator & operator++(); /** * Postfix increment. */ DerivedIterator operator++(int); /** * Prefix decrement. */ DerivedIterator & operator--(); /** * Postfix decrement. */ DerivedIterator operator--(int); /** * Return an iterator that is @p n entries ahead of the current one. */ DerivedIterator operator+(const difference_type n) const; /** * Return an iterator that is @p n entries behind the current one. */ DerivedIterator operator-(const difference_type n) const; /** * Increment the iterator position by @p n. */ DerivedIterator & operator+=(const difference_type n); /** * Decrement the iterator position by @p n. */ DerivedIterator & operator-=(const difference_type n); /** * Return the distance between the current iterator and the argument. The * distance is given by how many times one has to apply operator++() to the * current iterator to get the argument (for a positive return value), or * operator--() (for a negative return value). */ difference_type operator-(const DerivedIterator &p) const; /** * Dereferencing operator. */ reference operator*() const; /** * Dereferencing operator. */ pointer operator->() const; /** * Comparison operator. Returns true if both iterators point to * the same entry in the same container. */ template std::enable_if_t, bool> operator==(const OtherIterator &right) const { const auto &right_2 = static_cast(right); return this->accessor == right_2.accessor; } /** * Opposite of operator==(). */ template std::enable_if_t, bool> operator!=(const OtherIterator &right) const { return !(*this == right); } /** * Comparison operator: uses the same ordering as operator<(), but also * checks for equality. * * This function is only valid if both iterators point into the same * container. */ bool operator<=(const DerivedIterator &) const; /** * Comparison operator: uses the same ordering as operator>(), but also * checks for equality. * * This function is only valid if both iterators point into the same * container. */ bool operator>=(const DerivedIterator &) const; /** * Comparison operator. Result is true if either the first row number is * smaller or if the row numbers are equal and the first index is smaller. * * This function is only valid if both iterators point into the same * container. */ bool operator<(const DerivedIterator &) const; /** * Comparison operator. Works in the same way as operator<(), just the other * way round. */ bool operator>(const DerivedIterator &) const; protected: /* * The inheriting class should have a default constructor. */ LinearIndexIterator() = default; // NOLINT /** * Constructor that copies an accessor. */ LinearIndexIterator(const AccessorType accessor); protected: /** * Store an object of the accessor class. */ AccessorType accessor; }; template inline DerivedIterator & LinearIndexIterator::operator=( const DerivedIterator &it) { accessor.container = it.container; accessor.linear_index = it.linear_index; return static_cast(*this); } template inline DerivedIterator & LinearIndexIterator::operator++() { return operator+=(1); } template inline DerivedIterator LinearIndexIterator::operator++(int) { const DerivedIterator copy(this->accessor); operator+=(1); return copy; } template inline DerivedIterator & LinearIndexIterator::operator--() { return operator+=(-1); } template inline DerivedIterator LinearIndexIterator::operator--(int) { const DerivedIterator copy(this->accessor); operator+=(-1); return copy; } template inline DerivedIterator LinearIndexIterator::operator+( const difference_type n) const { DerivedIterator copy(this->accessor); copy += n; return copy; } template inline DerivedIterator LinearIndexIterator::operator-( const difference_type n) const { DerivedIterator copy(this->accessor); copy += -n; return copy; } template inline DerivedIterator & LinearIndexIterator::operator+=( const difference_type n) { accessor.linear_index += n; return static_cast(*this); } template inline DerivedIterator & LinearIndexIterator::operator-=( const difference_type n) { return operator+=(-n); } template inline typename LinearIndexIterator::difference_type LinearIndexIterator::operator-( const DerivedIterator &other) const { Assert(this->accessor.container == other.accessor.container, ExcMessage( "Only iterators pointing to the same container can be compared.")); return this->accessor.linear_index - other.accessor.linear_index; } template inline typename LinearIndexIterator::reference LinearIndexIterator::operator*() const { return accessor; } template inline typename LinearIndexIterator::pointer LinearIndexIterator::operator->() const { return &accessor; } template inline bool LinearIndexIterator::operator<=( const DerivedIterator &other) const { return (*this == other) || (*this < other); } template inline bool LinearIndexIterator::operator>=( const DerivedIterator &other) const { return !(*this < other); } template inline bool LinearIndexIterator::operator<( const DerivedIterator &other) const { Assert(this->accessor.container == other.accessor.container, ExcMessage( "Only iterators pointing to the same container can be compared.")); return this->accessor.linear_index < other.accessor.linear_index; } template inline bool LinearIndexIterator::operator>( const DerivedIterator &other) const { return other < static_cast(*this); } template inline LinearIndexIterator::LinearIndexIterator( const AccessorType accessor) : accessor(accessor) {} DEAL_II_NAMESPACE_CLOSE #endif