From 0b73fa857f3600dc12dda6354905613254d91d0b Mon Sep 17 00:00:00 2001 From: David Wells Date: Thu, 1 Mar 2018 10:03:54 -0500 Subject: [PATCH] Add a new header for implementing random-access iterators. --- doc/news/changes/minor/20180301DavidWells | 3 + include/deal.II/base/linear_index_iterator.h | 515 +++++++++++++++++++ 2 files changed, 518 insertions(+) create mode 100644 doc/news/changes/minor/20180301DavidWells create mode 100644 include/deal.II/base/linear_index_iterator.h diff --git a/doc/news/changes/minor/20180301DavidWells b/doc/news/changes/minor/20180301DavidWells new file mode 100644 index 0000000000..b0dce3d37b --- /dev/null +++ b/doc/news/changes/minor/20180301DavidWells @@ -0,0 +1,3 @@ +New: A template class LinearIndexIterator has been added with the intent of +using it to generalize iterators over contiguously stored data. +
(David Wells, 2018/03/01) diff --git a/include/deal.II/base/linear_index_iterator.h b/include/deal.II/base/linear_index_iterator.h new file mode 100644 index 0000000000..6613ab03d4 --- /dev/null +++ b/include/deal.II/base/linear_index_iterator.h @@ -0,0 +1,515 @@ +// --------------------------------------------------------------------- +// +// Copyright (C) 2018 by the deal.II authors +// +// This file is part of the deal.II library. +// +// The deal.II library is free software; you can use it, redistribute +// it, and/or modify it under the terms of the GNU Lesser General +// Public License as published by the Free Software Foundation; either +// version 2.1 of the License, or (at your option) any later version. +// The full text of the license can be found in the file LICENSE at +// the top level of the deal.II distribution. +// +// --------------------------------------------------------------------- + +#ifndef dealii_linear_index_iterator_h +#define dealii_linear_index_iterator_h + +#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 + * typedef typename std::conditional*, Container*>::type + * container_pointer_type; + * + * // This typedef is assumed to exist. + * typedef std::size_t size_type; + * + * // 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: + * typedef std::size_t size_type; + * typedef Iterator const_iterator; + * typedef 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. + *
  2. 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.
    3. + *
+ * 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. + * + * @author David Wells, 2018 + */ +template +class LinearIndexIterator +{ +public: + /** + * Iterator category. + */ + typedef std::random_access_iterator_tag iterator_category; + + /** + * A typedef for the type you get when you dereference an iterator of the + * current kind. + */ + typedef + AccessorType value_type; + + /** + * Difference type. + */ + typedef std::ptrdiff_t difference_type; + + /** + * Reference type. + */ + typedef const value_type &reference; + + /** + * Pointer type. + */ + typedef const value_type *pointer; + + /** + * Size type used by the underlying container. + */ + typedef typename value_type::size_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. + */ + bool operator == (const DerivedIterator &) const; + + /** + * Inverse of operator==(). + */ + 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: 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; + + /** + * 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 +{ + const auto &other_2 = static_cast(other); + return accessor.container == other_2.accessor.container && + accessor.linear_index == other_2.accessor.linear_index; +} + + + +template +inline +bool +LinearIndexIterator:: +operator != (const DerivedIterator &other) const +{ + return !(*this == other); +} + + + +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 < *this; +} + + + +template +inline +LinearIndexIterator::LinearIndexIterator +(const AccessorType accessor) + : + accessor(accessor) +{} + + +DEAL_II_NAMESPACE_CLOSE + +#endif -- 2.39.5