Acts/Utilities/GridIterator.ipp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 namespace Acts {
0010 // Global Iterator
0011 template <typename T, class... Axes>
0012 GridGlobalIterator<T, Axes...>::GridGlobalIterator(
0013     const Acts::Grid<T, Axes...>& grid, std::size_t idx)
0014     : m_grid(&grid), m_idx(idx) {}
0015
0016 template <typename T, class... Axes>
0017 GridGlobalIterator<T, Axes...>::GridGlobalIterator(
0018     GridGlobalIterator<T, Axes...>&& other) noexcept
0019     : m_grid(std::exchange(other.m_grid.ptr, nullptr)), m_idx(other.m_idx) {}
0020
0021 template <typename T, class... Axes>
0022 GridGlobalIterator<T, Axes...>& GridGlobalIterator<T, Axes...>::operator=(
0023     GridGlobalIterator<T, Axes...>&& other) noexcept {
0024   m_grid.ptr = std::exchange(other.m_grid.ptr, nullptr);
0025   m_idx = other.m_idx;
0026   return *this;
0027 }
0028
0029 template <typename T, class... Axes>
0030 bool GridGlobalIterator<T, Axes...>::operator==(
0031     const GridGlobalIterator<T, Axes...>& other) const {
0032   // This will always return false if we are comparing two iterators from
0033   // different grids.
0034   // As such a loop from itrStart (from grid A) to itrStop (from grid B) will
0035   // never complete since itrStop will not be reachable from itrStart
0036   return (m_grid.ptr == other.m_grid.ptr) && m_idx == other.m_idx;
0037 }
0038
0039 template <typename T, class... Axes>
0040 auto GridGlobalIterator<T, Axes...>::operator<=>(
0041     const GridGlobalIterator<T, Axes...>& other) const {
0042   // This operator only makes sense if the two iterators we are comparing
0043   // are using the same grid
0044   assert(m_grid.ptr == other.m_grid.ptr);
0045   return m_idx <=> other.m_idx;
0046 }
0047
0048 template <typename T, class... Axes>
0049 GridGlobalIterator<T, Axes...>& GridGlobalIterator<T, Axes...>::operator+=(
0050     const std::size_t offset) {
0051   m_idx += offset;
0052   return *this;
0053 }
0054
0055 template <typename T, class... Axes>
0056 GridGlobalIterator<T, Axes...>& GridGlobalIterator<T, Axes...>::operator-=(
0057     const std::size_t offset) {
0058   m_idx -= offset;
0059   return *this;
0060 }
0061
0062 template <typename T, class... Axes>
0063 GridGlobalIterator<T, Axes...> GridGlobalIterator<T, Axes...>::operator+(
0064     const std::size_t offset) const {
0065   return {*m_grid, m_idx + offset};
0066 }
0067
0068 template <typename T, class... Axes>
0069 GridGlobalIterator<T, Axes...> GridGlobalIterator<T, Axes...>::operator-(
0070     const std::size_t offset) const {
0071   return {*m_grid, m_idx - offset};
0072 }
0073
0074 template <typename T, class... Axes>
0075 typename GridGlobalIterator<T, Axes...>::difference_type
0076 GridGlobalIterator<T, Axes...>::operator-(
0077     const GridGlobalIterator<T, Axes...>& other) const {
0078   assert(m_grid.ptr == other.m_grid.ptr);
0079   assert(other <= *this);
0080   return m_idx - other.m_idx;
0081 }
0082
0083 template <typename T, class... Axes>
0084 const typename GridGlobalIterator<T, Axes...>::value_type&
0085 GridGlobalIterator<T, Axes...>::operator*() const {
0086   return m_grid->at(m_idx);
0087 }
0088
0089 template <typename T, class... Axes>
0090 GridGlobalIterator<T, Axes...>& GridGlobalIterator<T, Axes...>::operator++() {
0091   ++m_idx;
0092   return *this;
0093 }
0094
0095 template <typename T, class... Axes>
0096 GridGlobalIterator<T, Axes...> GridGlobalIterator<T, Axes...>::operator++(int) {
0097   GridGlobalIterator<T, Axes...> output(*m_grid, m_idx++);
0098   return output;
0099 }
0100
0101 template <typename T, class... Axes>
0102 std::size_t GridGlobalIterator<T, Axes...>::globalBinIndex() const {
0103   return m_idx;
0104 }
0105
0106 template <typename T, class... Axes>
0107 std::array<std::size_t, GridGlobalIterator<T, Axes...>::DIM>
0108 GridGlobalIterator<T, Axes...>::localBinsIndices() const {
0109   return m_grid->localBinsFromGlobalBin(m_idx);
0110 }
0111
0112 // Local Iterator
0113 template <typename T, class... Axes>
0114 Acts::GridLocalIterator<T, Axes...>::GridLocalIterator(
0115     const Acts::Grid<T, Axes...>& grid,
0116     const std::array<std::size_t, DIM>& indices)
0117     : m_grid(&grid),
0118       m_numLocalBins(grid.numLocalBins()),
0119       m_currentIndex(indices) {
0120   // Since the user has not defined a custom navigation pattern, we tell the
0121   // iterator we want to iterate on all the local bins in ascending order from
0122   // 1ul to numLocalBin for that specific axis.
0123   for (std::size_t i(0); i < DIM; ++i) {
0124     m_navigationIndex[i].resize(m_numLocalBins[i]);
0125     std::iota(m_navigationIndex[i].begin(), m_navigationIndex[i].end(), 1ul);
0126   }
0127 }
0128
0129 template <typename T, class... Axes>
0130 Acts::GridLocalIterator<T, Axes...>::GridLocalIterator(
0131     const Acts::Grid<T, Axes...>& grid,
0132     const std::array<std::size_t, DIM>& indices,
0133     std::array<std::vector<std::size_t>, DIM> navigation)
0134     : m_grid(&grid),
0135       m_numLocalBins(grid.numLocalBins()),
0136       m_currentIndex(indices),
0137       m_navigationIndex(std::move(navigation)) {
0138   /// We can allow navigation on only a subset of bins.
0139   /// If the number of specified bins in the navigation for one axis is not
0140   /// zero then override the maximum number of navigation bins instead of using
0141   /// the total number of available bins in the axis
0142   for (std::size_t i(0ul); i < DIM; ++i) {
0143     /// We do not allow empty bin sequences
0144     if (m_navigationIndex[i].size() == 0) {
0145       throw std::invalid_argument(
0146           "Invalid navigation sequence in local grid iterator. No bins "
0147           "specified.");
0148     }
0149     /// Too many bins
0150     if (m_navigationIndex[i].size() > m_numLocalBins[i]) {
0151       throw std::invalid_argument(
0152           "Invalid navigation sequence in local grid iterator. Too many bins "
0153           "specified.");
0154     }
0155     m_numLocalBins[i] = m_navigationIndex[i].size();
0156   }
0157 }
0158
0159 template <typename T, class... Axes>
0160 Acts::GridLocalIterator<T, Axes...>::GridLocalIterator(
0161     Acts::GridLocalIterator<T, Axes...>&& other) noexcept
0162     : m_grid(std::exchange(other.m_grid.ptr, nullptr)),
0163       m_numLocalBins(other.m_numLocalBins),
0164       m_currentIndex(other.m_currentIndex),
0165       m_navigationIndex(std::move(other.m_navigationIndex)) {}
0166
0167 template <typename T, class... Axes>
0168 Acts::GridLocalIterator<T, Axes...>&
0169 Acts::GridLocalIterator<T, Axes...>::operator=(
0170     Acts::GridLocalIterator<T, Axes...>&& other) noexcept {
0171   m_grid.ptr = std::exchange(other.m_grid.ptr, nullptr);
0172   m_numLocalBins = other.m_numLocalBins;
0173   m_currentIndex = other.m_currentIndex;
0174   m_navigationIndex = std::move(other.m_navigationIndex);
0175   return *this;
0176 }
0177
0178 template <typename T, class... Axes>
0179 bool Acts::GridLocalIterator<T, Axes...>::operator==(
0180     const Acts::GridLocalIterator<T, Axes...>& other) const {
0181   // This will always return false if we are comparing two iterators from
0182   // different grids.
0183   // As such a loop from itrStart (from grid A) to itrStop (from grid B) will
0184   // never complete since itrStop will not be reachable from itrStart
0185   if (m_grid.ptr != other.m_grid.ptr) {
0186     return false;
0187   }
0188
0189   for (std::size_t i(0); i < DIM; ++i) {
0190     if (m_currentIndex[i] != other.m_currentIndex[i]) {
0191       return false;
0192     }
0193   }
0194
0195   return true;
0196 }
0197
0198 template <typename T, class... Axes>
0199 const typename Acts::GridLocalIterator<T, Axes...>::value_type&
0200 Acts::GridLocalIterator<T, Axes...>::operator*() const {
0201   std::array<std::size_t, DIM> localPositionBin{};
0202   for (std::size_t i(0); i < DIM; ++i) {
0203     localPositionBin[i] = m_navigationIndex[i][m_currentIndex[i]];
0204   }
0205   return m_grid->atLocalBins(localPositionBin);
0206 }
0207
0208 template <typename T, class... Axes>
0209 GridLocalIterator<T, Axes...>& GridLocalIterator<T, Axes...>::operator++() {
0210   increment<DIM - 1>();
0211   return *this;
0212 }
0213
0214 template <typename T, class... Axes>
0215 GridLocalIterator<T, Axes...> GridLocalIterator<T, Axes...>::operator++(int) {
0216   GridLocalIterator<T, Axes...> output(*this);
0217   this->operator++();
0218   return output;
0219 }
0220
0221 template <typename T, class... Axes>
0222 template <std::size_t N>
0223 void GridLocalIterator<T, Axes...>::increment() {
0224   // Check if the current local bin can be incremented, or we reached the end
0225   // of bins in the axis
0226   if (++m_currentIndex[N] < m_numLocalBins[N]) {
0227     return;
0228   }
0229   // We have reached the last bin in the axis, we set the position to 0ul and
0230   // try to increment another axis
0231   if constexpr (N != 0) {
0232     m_currentIndex[N] = 0;
0233     increment<N - 1>();
0234   } else {
0235     m_currentIndex = m_numLocalBins;
0236   }
0237 }
0238
0239 template <typename T, class... Axes>
0240 std::size_t GridLocalIterator<T, Axes...>::globalBinIndex() const {
0241   return m_grid->globalBinFromLocalBins(localBinsIndices());
0242 }
0243
0244 template <typename T, class... Axes>
0245 std::array<std::size_t, GridLocalIterator<T, Axes...>::DIM>
0246 GridLocalIterator<T, Axes...>::localBinsIndices() const {
0247   std::array<std::size_t, DIM> output{};
0248   for (std::size_t i(0); i < DIM; ++i) {
0249     output[i] = m_navigationIndex[i][m_currentIndex[i]];
0250   }
0251   return output;
0252 }
0253
0254 }  // namespace Acts