itkIndexRange.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright NumFOCUS
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
 
#ifndef itkIndexRange_h
#define itkIndexRange_h
 
#include <cassert>
#include <cstddef>     // For ptrdiff_t.
#include <iterator>    // For bidirectional_iterator_tag and reverse_iterator.
#include <type_traits> // For conditional and enable_if.
 
#include "itkImageRegion.h"
#include "itkIndex.h"
#include "itkSize.h"
 
namespace itk
{

template <unsigned int VDimension, bool VBeginAtZero>
class IndexRange final
{
public:
  static constexpr unsigned int Dimension = VDimension;
  using SizeType = Size<VDimension>;
  using IndexType = Index<VDimension>;
 
  class const_iterator final
  {
  public:
    // Types conforming the iterator requirements of the C++ standard library:
    using difference_type = ptrdiff_t;
    using value_type = IndexType;
    using reference = const IndexType &;
    using pointer = const IndexType *;
    using iterator_category = std::bidirectional_iterator_tag;

    const_iterator() = default;
 

    constexpr reference
    operator*() const noexcept
    {
      return m_Index;
    }
 

    constexpr pointer
    operator->() const noexcept
    {
      return &(**this);
    }
 

    constexpr const_iterator &
    operator++() noexcept
    {
      ++m_Position;
 
      for (unsigned int i = 0; i < (VDimension - 1); ++i)
      {
        auto & indexValue = m_Index[i];
 
        ++indexValue;
 
        if (indexValue <= m_MaxIndex[i])
        {
          return *this;
        }
        indexValue = m_MinIndex[i];
      }
      ++m_Index.back();
 
      return *this;
    }
 

    constexpr const_iterator
    operator++(int) noexcept
    {
      auto result = *this;
      ++(*this);
      return result;
    }
 

    constexpr const_iterator &
    operator--() noexcept
    {
      --m_Position;
 
      for (unsigned int i = 0; i < (VDimension - 1); ++i)
      {
        auto & indexValue = m_Index[i];
 
        --indexValue;
 
        if (indexValue >= m_MinIndex[i])
        {
          return *this;
        }
        indexValue = m_MaxIndex[i];
      }
      --m_Index.back();
      return *this;
    }
 

    constexpr const_iterator
    operator--(int) noexcept
    {
      auto result = *this;
      --(*this);
      return result;
    }
 

    friend bool
    operator==(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      assert(lhs.m_MaxIndex == rhs.m_MaxIndex);
 
      // Note that comparing m_Position is typically much faster than comparing m_Index, because m_Position is just an
      // integer, whereas m_Index is of a user-defined type, which usually has more bytes than m_Position.
      return lhs.m_Position == rhs.m_Position;
    }
 

    friend bool
    operator!=(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      // Implemented just like the corresponding std::rel_ops operator.
      return !(lhs == rhs);
    }
 

    friend constexpr bool
    operator<(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      return lhs.m_Position < rhs.m_Position;
    }
 

    friend constexpr bool
    operator>(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      // Implemented just like the corresponding std::rel_ops operator.
      return rhs < lhs;
    }
 

    friend constexpr bool
    operator<=(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      // Implemented just like the corresponding std::rel_ops operator.
      return !(rhs < lhs);
    }
 

    friend constexpr bool
    operator>=(const const_iterator & lhs, const const_iterator & rhs) noexcept
    {
      // Implemented just like the corresponding std::rel_ops operator.
      return !(lhs < rhs);
    }
 
 
  private:
    friend class IndexRange;
 
    // Represents an N-dimensional index that is always zero
    // Aims towards zero runtime overhead.
    struct ZeroIndex
    {
      // The "index" operator.
      constexpr IndexValueType
      operator[](unsigned int) const
      {
        return 0;
      }
 
      // Implicitly converts to a default-initialized itk::Index<N>.
      constexpr
      operator IndexType() const
      {
        return IndexType();
      }
    };
 
 
    // When BeginAtZero is true, use zero as minimum index, otherwise use itk::Index<N>.
    using MinIndexType = std::conditional_t<VBeginAtZero, ZeroIndex, IndexType>;
 
    // Private constructor, only used by friend class IndexRange.
    constexpr const_iterator(const IndexType &    index,
                             const MinIndexType & minIndex,
                             const IndexType &    maxIndex,
                             const size_t         position) noexcept
      : // Note: Use parentheses instead of curly braces to initialize data members,
        // to avoid AppleClang 6.0.0.6000056 compilation error, "no viable conversion..."
      m_Index(index)
      , m_MinIndex(minIndex)
      , m_MaxIndex(maxIndex)
      , m_Position(position)
    {}
 
 
    // IndexRange::const_iterator data members:
 
    // Current (N-dimensional) index.
    IndexType m_Index;
 
    // Minimum (N-dimensional) index.
    MinIndexType m_MinIndex;
 
    // Maximum (N-dimensional) index.
    IndexType m_MaxIndex;
 
    // The position within the range, relative to the begin. So it is zero at the begin, and it is equal to
    // `range.size()` at the end of the range.
    size_t m_Position{};
  };
 
  using iterator = const_iterator;
  using reverse_iterator = std::reverse_iterator<iterator>;
  using const_reverse_iterator = std::reverse_iterator<const_iterator>;

  IndexRange() = default;
 

  constexpr explicit IndexRange(const SizeType & gridSize)
    : // Note: Use parentheses instead of curly braces to initialize data members,
      // to avoid AppleClang 6.0.0.6000056 compile errors, "no viable conversion..."
    m_MinIndex()
    , m_MaxIndex(CalculateMaxIndex(typename iterator::MinIndexType(), gridSize))
  {}
 

  template <bool VIsSubstitutionFailure = VBeginAtZero,
            typename TVoid = std::enable_if_t<!VIsSubstitutionFailure>>
  explicit IndexRange(const ImageRegion<VDimension> & imageRegion)
    : // Note: Use parentheses instead of curly braces to initialize data members,
      // to avoid AppleClang 6.0.0.6000056 compile errors, "no viable conversion..."
    m_MinIndex(imageRegion.GetIndex())
    , m_MaxIndex(CalculateMaxIndex(imageRegion.GetIndex(), imageRegion.GetSize()))
  {
    // Three compile-time asserts, just to check if SFINAE worked properly:
    static_assert(!VIsSubstitutionFailure,
                  "This template should (of course) be instantiated without substitution failure.");
    static_assert(std::is_same_v<TVoid, void>,
                  "std::enable_if<!VIsSubstitutionFailure> should yield void, by definition.");
    static_assert(!VBeginAtZero, "This constructor should only be is available when VBeginAtZero is false.");
  }
 

  [[nodiscard]] constexpr iterator
  begin() const noexcept
  {
    return iterator(m_MinIndex, m_MinIndex, m_MaxIndex, 0);
  }

  [[nodiscard]] constexpr iterator
  end() const noexcept
  {
    IndexType index = m_MinIndex;
    index.back() = m_MaxIndex.back() + 1;
    return iterator(index, m_MinIndex, m_MaxIndex, size());
  }

  [[nodiscard]] constexpr const_iterator
  cbegin() const noexcept
  {
    return this->begin();
  }

  [[nodiscard]] constexpr const_iterator
  cend() const noexcept
  {
    return this->end();
  }

  [[nodiscard]] reverse_iterator
  rbegin() const noexcept
  {
    return reverse_iterator(this->end());
  }

  [[nodiscard]] reverse_iterator
  rend() const noexcept
  {
    return reverse_iterator(this->begin());
  }

  [[nodiscard]] const_reverse_iterator
  crbegin() const noexcept
  {
    return this->rbegin();
  }

  [[nodiscard]] const_reverse_iterator
  crend() const noexcept
  {
    return this->rend();
  }
 

  [[nodiscard]] constexpr size_t
  size() const noexcept
  {
    size_t result = 1;
 
    for (unsigned int i = 0; i < VDimension; ++i)
    {
      result *= ((m_MaxIndex[i] + 1) - m_MinIndex[i]);
    }
    return result;
  }
 

  [[nodiscard]] constexpr bool
  empty() const noexcept
  {
    // When an IndexRange is empty, each index value of m_MaxIndex is less than the corresponding
    // index value of m_MinIndex. And vice versa: when an IndexRange is non-empty, each index value
    // of m_MaxIndex is greater than or equal to the corresponding index value of m_MinIndex.
    // Note that the range contains one element when m_MaxIndex == m_MinIndex.
    return m_MaxIndex[0] < m_MinIndex[0];
  }
 
 
private:
  using MinIndexType = typename iterator::MinIndexType;
 
  static constexpr IndexType
  CalculateMaxIndex(const MinIndexType & minIndex, const SizeType & size)
  {
    const bool sizeHasZeroValue = [&size] {
      for (const auto sizeValue : size)
      {
        if (sizeValue == 0)
        {
          return true;
        }
      }
      return false;
    }();
 
    // Treat any size that has a zero value equally.
    const SizeType normalizedSize = sizeHasZeroValue ? SizeType{ { 0 } } : size;
 
    // The `index` is initialized (`{}`), just to support C++17 constexpr.
    IndexType index{};
 
    for (unsigned int i = 0; i < VDimension; ++i)
    {
      index[i] = minIndex[i] + static_cast<IndexValueType>(normalizedSize[i]) - 1;
    }
 
    return index;
  }
 
  // IndexRange data members:
 
  // Minimum (N-dimensional) index.
  MinIndexType m_MinIndex{};
 
  // Maximum (N-dimensional) index.
  IndexType m_MaxIndex = IndexType::Filled(-1);
};
 
template <unsigned int VDimension>
using ImageRegionIndexRange = IndexRange<VDimension, false>;
 
template <unsigned int VDimension>
using ZeroBasedIndexRange = IndexRange<VDimension, true>;
 
/* Creates a range of indices for the specified grid size. */
template <unsigned int VDimension>
[[nodiscard]] constexpr auto
MakeIndexRange(const Size<VDimension> & gridSize)
{
  return ZeroBasedIndexRange<VDimension>(gridSize);
}
 
/* Creates a range of indices for the specified image region. */
template <unsigned int VDimension>
[[nodiscard]] auto
MakeIndexRange(const ImageRegion<VDimension> & imageRegion)
{
  return ImageRegionIndexRange<VDimension>(imageRegion);
}
 
/* Creates a range of indices for the image region specified by its index and size. */
template <unsigned int VDimension>
[[nodiscard]] auto
MakeIndexRange(const Index<VDimension> & imageRegionIndex, const Size<VDimension> & imageRegionSize)
{
  return ImageRegionIndexRange<VDimension>(ImageRegion<VDimension>{ imageRegionIndex, imageRegionSize });
}
 
} // namespace itk
 
#endif