utils/ranges/enumerate.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 // Project include(s)
0012 #include "detray/definitions/detail/qualifiers.hpp"
0013 #include "detray/definitions/indexing.hpp"
0014 #include "detray/utils/ranges/empty.hpp"
0015 #include "detray/utils/ranges/ranges.hpp"
0016 #include "detray/utils/ranges/subrange.hpp"
0017
0018 // System include(s)
0019 #include <type_traits>
0020 #include <utility>
0021
0022 namespace detray::ranges {
0023
0024 /// @brief Enumerates the elements of a range on the fly.
0025 ///
0026 /// @tparam range_itr_t the iterator type of the enumerated range
0027 /// @tparam incr_t a type that can be incremented in lockstep with the
0028 ///         iterator 'range_itr_t'.
0029 ///
0030 /// @note Does not take ownership of the range it operates on. Its lifetime
0031 /// needs to be guaranteed throughout iteration or between iterations with the
0032 /// same enumerate instance.
0033 /// @note Is not fit for lazy evaluation.
0034 template <std::input_iterator range_itr_t, std::incrementable incr_t>
0035 class enumerate_view : public detray::ranges::view_interface<
0036                            enumerate_view<range_itr_t, incr_t>> {
0037  private:
0038   /// @brief Nested iterator to enumerate the elements of a range.
0039   ///
0040   /// The enumeration is done by incrementing an index in lockstep with a
0041   /// wrapped iterator of a range. Index and current iterator value are
0042   /// returned using structured binding.
0043   struct iterator {
0044     using itr_value_t = std::iter_value_t<range_itr_t>;
0045     using itr_ref_t = std::iter_reference_t<range_itr_t>;
0046     using itr_ptr_t = typename std::iterator_traits<range_itr_t>::pointer;
0047
0048     using difference_type = std::iter_difference_t<range_itr_t>;
0049     using value_type = std::pair<incr_t, itr_ref_t>;
0050     using pointer = value_type *;
0051     using reference = value_type;
0052     using iterator_category =
0053         typename std::iterator_traits<range_itr_t>::iterator_category;
0054
0055     constexpr iterator()
0056       requires std::default_initializable<range_itr_t>
0057     = default;
0058
0059     DETRAY_HOST_DEVICE
0060     explicit iterator(range_itr_t iter, incr_t offset = 0)
0061         : m_iter(iter), m_i{offset}, m_offset{offset} {};
0062
0063     /// Increment iterator and index in lockstep
0064     /// @{
0065     DETRAY_HOST_DEVICE constexpr auto operator++() -> iterator & {
0066       ++m_i;
0067       ++m_iter;
0068       return *this;
0069     }
0070
0071     DETRAY_HOST_DEVICE constexpr auto operator++(int) -> iterator {
0072       auto tmp(*this);
0073       ++(*this);
0074       return tmp;
0075     }
0076     /// @}
0077
0078     /// Decrement iterator and index in lockstep
0079     /// @{
0080     DETRAY_HOST_DEVICE constexpr auto operator--() -> iterator &
0081       requires std::bidirectional_iterator<range_itr_t>
0082     {
0083       --m_i;
0084       --m_iter;
0085       return *this;
0086     }
0087
0088     DETRAY_HOST_DEVICE constexpr auto operator--(int) -> iterator
0089       requires std::bidirectional_iterator<range_itr_t>
0090     {
0091       auto tmp(*this);
0092       ++(*this);
0093       return tmp;
0094     }
0095     /// @}
0096
0097     /// @returns iterator and index together
0098     DETRAY_HOST_DEVICE constexpr auto operator*() const {
0099       return std::pair<incr_t, itr_ref_t>(m_i, *m_iter);
0100     }
0101
0102     /// @returns advance this iterator state by @param j.
0103     DETRAY_HOST_DEVICE constexpr auto operator+=(const difference_type j)
0104         -> iterator &
0105       requires std::random_access_iterator<range_itr_t>
0106     {
0107       m_iter += j;
0108       m_i += static_cast<incr_t>(j);
0109       return *this;
0110     }
0111
0112     /// @returns advance this iterator state by @param j.
0113     DETRAY_HOST_DEVICE constexpr auto operator-=(const difference_type j)
0114         -> iterator &
0115       requires std::random_access_iterator<range_itr_t>
0116     {
0117       m_iter -= j;
0118       m_i -= static_cast<incr_t>(j);
0119       return *this;
0120     }
0121
0122     /// @returns the value and index at a given position - const
0123     DETRAY_HOST_DEVICE constexpr auto operator[](const difference_type i) const
0124       requires std::random_access_iterator<range_itr_t>
0125     {
0126       // check narrowing
0127       const incr_t index{m_offset + static_cast<incr_t>(i)};
0128       return std::pair<incr_t, itr_ref_t>(index, m_iter[i]);
0129     }
0130
0131    private:
0132     /// @returns true if we reach end of sequence
0133     DETRAY_HOST_DEVICE
0134     friend constexpr auto operator==(const iterator &lhs, const iterator &rhs)
0135         -> bool {
0136       return (lhs.m_iter == rhs.m_iter);
0137     }
0138
0139     /// @returns true if the wrapped iterators are not the same.
0140     DETRAY_HOST_DEVICE friend constexpr auto operator!=(const iterator &lhs,
0141                                                         const iterator &rhs)
0142         -> bool {
0143       return (lhs.m_iter != rhs.m_iter);
0144     }
0145
0146     /// @returns true if we reach end of sequence
0147     DETRAY_HOST_DEVICE
0148     friend constexpr auto operator<=>(const iterator &lhs, const iterator &rhs)
0149       requires detray::ranges::random_access_iterator<range_itr_t>
0150     {
0151 #if defined(__apple_build_version__)
0152       const auto l{lhs.m_iter};
0153       const auto r{rhs.m_iter};
0154       if (l < r || (l == r && l < r)) {
0155         return std::strong_ordering::less;
0156       }
0157       if (l > r || (l == r && l > r)) {
0158         return std::strong_ordering::greater;
0159       }
0160       return std::strong_ordering::equivalent;
0161 #else
0162       return (lhs.m_iter <=> rhs.m_iter);
0163 #endif
0164     }
0165
0166     /// @returns an iterator and index, position advanced by @param j.
0167     DETRAY_HOST_DEVICE friend constexpr auto operator+(const iterator &itr,
0168                                                        const difference_type j)
0169         -> iterator
0170       requires std::random_access_iterator<range_itr_t>
0171     {
0172       return {itr.m_iter + j, itr.m_i + static_cast<incr_t>(j)};
0173     }
0174
0175     /// @returns an iterator and index, position advanced by @param j.
0176     DETRAY_HOST_DEVICE friend constexpr auto operator+(const difference_type j,
0177                                                        const iterator &itr)
0178         -> iterator
0179       requires std::random_access_iterator<range_itr_t>
0180     {
0181       return itr + j;
0182     }
0183
0184     /// @returns an iterator and index, position advanced by @param j.
0185     DETRAY_HOST_DEVICE friend constexpr auto operator-(const iterator &itr,
0186                                                        const difference_type j)
0187         -> iterator
0188       requires std::random_access_iterator<range_itr_t>
0189     {
0190       return itr + (-j);
0191     }
0192
0193     /// @returns the positional difference between two iterators
0194     /// (independent from their enumeration of the range values)
0195     DETRAY_HOST_DEVICE friend constexpr auto operator-(const iterator &lhs,
0196                                                        const iterator &rhs)
0197         -> difference_type
0198       requires std::random_access_iterator<range_itr_t>
0199     {
0200       return lhs.m_iter - rhs.m_iter;
0201     }
0202
0203     range_itr_t m_iter{};
0204     incr_t m_i{0};
0205     incr_t m_offset{0};
0206   };
0207
0208   iterator m_begin{};
0209   iterator m_end{};
0210
0211  public:
0212   using iterator_t = iterator;
0213
0214   /// Default constructor (only works if @c imrementable_t is default
0215   /// constructible)
0216   constexpr enumerate_view() = default;
0217
0218   /// Construct from a @param range that will be enumerated beginning at 0
0219   template <detray::ranges::range range_t>
0220     requires(!std::same_as<range_t, enumerate_view>)
0221   DETRAY_HOST_DEVICE constexpr explicit enumerate_view(range_t &&rng)
0222       : m_begin{detray::ranges::begin(rng)},
0223         m_end{detray::ranges::end(rng), static_cast<incr_t>(rng.size())} {}
0224
0225   /// Construct from a @param range that will be enumerated beginning at
0226   /// @param start.
0227   template <detray::ranges::range range_t>
0228   DETRAY_HOST_DEVICE constexpr enumerate_view(range_t &&rng, incr_t start)
0229       : m_begin{detray::ranges::begin(rng), start},
0230         m_end{detray::ranges::end(rng),
0231               start + static_cast<incr_t>(rng.size())} {}
0232
0233   /// @return start position of range on container.
0234   DETRAY_HOST_DEVICE
0235   constexpr auto begin() -> iterator { return m_begin; }
0236
0237   /// @return start position of range on container - const
0238   DETRAY_HOST_DEVICE
0239   constexpr auto begin() const -> iterator { return m_begin; }
0240
0241   /// @return sentinel of a sequence.
0242   DETRAY_HOST_DEVICE
0243   constexpr auto end() const -> iterator { return m_end; }
0244 };
0245
0246 namespace views {
0247
0248 template <std::input_iterator range_itr_t, std::incrementable incr_t = dindex>
0249   requires std::convertible_to<std::iter_difference_t<range_itr_t>, incr_t>
0250 struct enumerate : public enumerate_view<range_itr_t, incr_t> {
0251   using base_type = enumerate_view<range_itr_t, incr_t>;
0252
0253   /// Partial construction for range composition
0254   /// @{
0255   constexpr enumerate() = default;
0256
0257   DETRAY_HOST_DEVICE constexpr explicit enumerate(incr_t start)
0258       : m_incr{start} {}
0259   /// @}
0260
0261   /// Direct view construction
0262   /// @{
0263   template <detray::ranges::range range_t>
0264     requires(!std::same_as<range_t, enumerate>)
0265   DETRAY_HOST_DEVICE constexpr explicit enumerate(range_t &&rng)
0266       : base_type(std::forward<range_t>(rng)) {}
0267
0268   template <detray::ranges::range range_t>
0269   DETRAY_HOST_DEVICE constexpr enumerate(range_t &&rng, incr_t start)
0270       : base_type(std::forward<range_t>(rng), start) {}
0271
0272   template <detray::ranges::range deduced_range_t, typename volume_t,
0273             typename = typename std::remove_reference_t<volume_t>::volume_def>
0274   DETRAY_HOST_DEVICE enumerate(deduced_range_t &&range, const volume_t &vol)
0275       : enumerate(
0276             detray::ranges::subrange(std::forward<deduced_range_t>(range), vol),
0277             detray::detail::get<0>(vol.full_range())) {}
0278   /// @}
0279
0280   /// Call operator for range composition
0281   template <detray::ranges::range range_t>
0282   DETRAY_HOST_DEVICE constexpr auto operator()(range_t &&rng) {
0283     using itr_t = detray::ranges::const_iterator_t<std::decay_t<range_t>>;
0284     return detray::ranges::enumerate_view<itr_t, incr_t>(
0285         std::forward<range_t>(rng), m_incr);
0286   }
0287
0288  private:
0289   incr_t m_incr{0};
0290 };
0291
0292 // deduction guides
0293 DETRAY_HOST_DEVICE enumerate() -> enumerate<
0294     detray::ranges::const_iterator_t<detray::ranges::views::empty<int>>,
0295     dindex>;
0296
0297 DETRAY_HOST_DEVICE enumerate(dindex start) -> enumerate<
0298     detray::ranges::const_iterator_t<detray::ranges::views::empty<int>>,
0299     dindex>;
0300
0301 template <detray::ranges::range range_t>
0302 DETRAY_HOST_DEVICE enumerate(range_t &&rng)
0303     -> enumerate<detray::ranges::const_iterator_t<std::decay_t<range_t>>,
0304                  dindex>;
0305
0306 template <detray::ranges::range range_t, typename volume_t,
0307           typename = typename std::remove_reference_t<volume_t>::volume_def>
0308 DETRAY_HOST_DEVICE enumerate(range_t &&range, const volume_t &vol)
0309     -> enumerate<detray::ranges::const_iterator_t<std::decay_t<range_t>>,
0310                  dindex>;
0311
0312 template <detray::ranges::range range_t>
0313 DETRAY_HOST_DEVICE enumerate(range_t &&rng, dindex start)
0314     -> enumerate<detray::ranges::const_iterator_t<std::decay_t<range_t>>,
0315                  dindex>;
0316
0317 }  // namespace views
0318
0319 }  // namespace detray::ranges