Acts/Utilities/NeighborHoodIndices.hpp

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 #pragma once
0010
0011 #include <vector>
0012
0013 namespace Acts {
0014
0015 /// This object can be iterated to produce up to two sequences of integer
0016 /// indices, corresponding to the half-open integer ranges [begin1, end1[ and
0017 /// [begin2, end2[.
0018 ///
0019 /// The goal is to emulate the effect of enumerating a range of neighbor
0020 /// indices on an axis (which may go out of bounds and wrap around since we
0021 /// have AxisBoundaryType::Closed), inserting them into an std::vector, and
0022 /// discarding duplicates, without paying the price of duplicate removal
0023 /// and dynamic memory allocation in hot magnetic field interpolation code.
0024 ///
0025 /// Iterable indices for neighborhood lookups with optional wrap-around.
0026 class NeighborHoodIndices {
0027  public:
0028   NeighborHoodIndices() = default;
0029
0030   /// Constructor for continuous range
0031   /// @param begin Start index
0032   /// @param end End index (exclusive)
0033   NeighborHoodIndices(std::size_t begin, std::size_t end)
0034       : m_begin1(begin), m_end1(end), m_begin2(end), m_end2(end) {}
0035
0036   /// Constructor for wrapped range (two segments)
0037   /// @param begin1 Start of first segment
0038   /// @param end1 End of first segment (exclusive)
0039   /// @param begin2 Start of second segment
0040   /// @param end2 End of second segment (exclusive)
0041   NeighborHoodIndices(std::size_t begin1, std::size_t end1, std::size_t begin2,
0042                       std::size_t end2)
0043       : m_begin1(begin1), m_end1(end1), m_begin2(begin2), m_end2(end2) {}
0044
0045   /// Iterator over the neighborhood index sequence.
0046   class iterator {
0047    public:
0048     iterator() = default;
0049
0050     /// Constructor for end iterator
0051     /// @param current End position
0052     explicit iterator(std::size_t current)
0053         : m_current(current), m_wrapped(true) {}
0054
0055     /// Constructor for begin iterator
0056     /// @param begin1 Start of first segment
0057     /// @param end1 End of first segment
0058     /// @param begin2 Start of second segment
0059     iterator(std::size_t begin1, std::size_t end1, std::size_t begin2)
0060         : m_current(begin1),
0061           m_end1(end1),
0062           m_begin2(begin2),
0063           m_wrapped(begin1 == begin2) {}
0064
0065     /// Dereference operator
0066     /// @return Current index
0067     std::size_t operator*() const { return m_current; }
0068
0069     /// Pre-increment operator
0070     /// @return Reference to this iterator
0071     iterator& operator++() {
0072       ++m_current;
0073       if (m_current == m_end1) {
0074         m_current = m_begin2;
0075         m_wrapped = true;
0076       }
0077       return *this;
0078     }
0079
0080     /// Equality comparison operator
0081     /// @param it Other iterator
0082     /// @return True if iterators are equal
0083     bool operator==(const iterator& it) const {
0084       return (m_current == it.m_current) && (m_wrapped == it.m_wrapped);
0085     }
0086
0087    private:
0088     std::size_t m_current = 0, m_end1 = 0, m_begin2 = 0;
0089     bool m_wrapped = false;
0090   };
0091
0092   /// Get begin iterator
0093   /// @return Iterator to first index
0094   iterator begin() const { return iterator(m_begin1, m_end1, m_begin2); }
0095
0096   /// Get end iterator
0097   /// @return Iterator past last index
0098   iterator end() const { return iterator(m_end2); }
0099
0100   /// Get total number of indices in the sequence
0101   /// @return Number of indices
0102   std::size_t size() const { return (m_end1 - m_begin1) + (m_end2 - m_begin2); }
0103
0104   /// Collect all indices into a vector
0105   /// @return Vector containing all indices
0106   std::vector<std::size_t> collect() const {
0107     std::vector<std::size_t> result;
0108     result.reserve(this->size());
0109     for (std::size_t idx : *this) {
0110       result.push_back(idx);
0111     }
0112     return result;
0113   }
0114
0115  private:
0116   std::size_t m_begin1 = 0;
0117   std::size_t m_end1 = 0;
0118   std::size_t m_begin2 = 0;
0119   std::size_t m_end2 = 0;
0120 };
0121
0122 }  // namespace Acts