utils/ranges/pick.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
0017 // System include(s)
0018 #include <cassert>
0019 #include <memory>
0020 #include <type_traits>
0021 #include <utility>
0022
0023 namespace detray::ranges {
0024
0025 /// @brief Range adaptor that indexes the elements of a range using another
0026 ///        index range.
0027 ///
0028 /// @tparam range_itr_t the iterator type of the enumerated range
0029 /// @tparam sequence_itr_t range of indices.
0030 ///
0031 /// @note Does not take ownership of the range it operates on. Its lifetime
0032 /// needs to be guaranteed throughout iteration or between iterations with the
0033 /// same enumerate instance.
0034 /// @note Is not fit for lazy evaluation.
0035 template <std::input_iterator range_itr_t, std::input_iterator sequence_itr_t>
0036 class pick_view : public detray::ranges::view_interface<
0037                       pick_view<range_itr_t, sequence_itr_t>> {
0038  private:
0039   using index_t = std::iter_value_t<sequence_itr_t>;
0040   using value_t = std::iter_value_t<range_itr_t>;
0041   using difference_t = std::iter_difference_t<range_itr_t>;
0042
0043   /// @brief Nested iterator to randomly index the elements of a range.
0044   ///
0045   /// The indices by which to reference the range are obtained by a dedicated
0046   /// index range
0047   ///
0048   /// @todo Add Comparability to fulfill random access iterator traits once
0049   ///       needed.
0050   struct iterator {
0051     using itr_value_t = std::iter_value_t<range_itr_t>;
0052     using itr_ref_t = std::iter_reference_t<range_itr_t>;
0053     using itr_ptr_t = typename std::iterator_traits<range_itr_t>::pointer;
0054
0055     using difference_type = std::iter_difference_t<range_itr_t>;
0056     using value_type = std::pair<std::iter_value_t<sequence_itr_t>, itr_ref_t>;
0057     using pointer = value_type *;
0058     using reference = value_type;
0059     using iterator_category =
0060         typename std::iterator_traits<sequence_itr_t>::iterator_category;
0061
0062     static_assert(std::is_convertible_v<index_t, difference_type>,
0063                   "Given sequence cannot be "
0064                   "used to index elements of range.");
0065
0066     /// Default constructor required by LegacyIterator trait
0067     constexpr iterator() = default;
0068
0069     /// Construct from range and sequence range
0070     DETRAY_HOST_DEVICE
0071     constexpr iterator(range_itr_t rng_itr, range_itr_t rng_begin,
0072                        sequence_itr_t sq_itr, sequence_itr_t sq_end)
0073         : m_range_iter{rng_itr},
0074           m_range_begin{rng_begin},
0075           m_seq_iter{sq_itr},
0076           m_seq_end{sq_end} {}
0077
0078     /// Increment iterator and index in lockstep
0079     /// @{
0080     DETRAY_HOST_DEVICE constexpr auto operator++() -> iterator & {
0081       ++m_seq_iter;
0082       if (m_seq_iter != m_seq_end) {
0083         m_range_iter =
0084             m_range_begin + static_cast<difference_type>(*m_seq_iter);
0085       }
0086       return *this;
0087     }
0088
0089     DETRAY_HOST_DEVICE constexpr auto operator++(int) -> iterator {
0090       auto tmp(*this);
0091       ++(*this);
0092       return tmp;
0093     }
0094     /// @}
0095
0096     /// Decrement iterator and index in lockstep
0097     /// @{
0098     DETRAY_HOST_DEVICE constexpr auto operator--() -> iterator &
0099       requires std::bidirectional_iterator<range_itr_t>
0100     {
0101       m_range_iter =
0102           m_range_begin + static_cast<difference_type>(*(--m_seq_iter));
0103       return *this;
0104     }
0105
0106     DETRAY_HOST_DEVICE constexpr auto operator--(int) -> iterator
0107       requires std::bidirectional_iterator<range_itr_t>
0108     {
0109       auto tmp(*this);
0110       --(*this);
0111       return tmp;
0112     }
0113
0114     /// @returns iterator and index together
0115     DETRAY_HOST_DEVICE auto operator*() const {
0116       return value_type(*m_seq_iter, *m_range_iter);
0117     }
0118
0119     /// @returns advance this iterator state by @param j.
0120     DETRAY_HOST_DEVICE constexpr auto operator+=(const difference_type j)
0121         -> iterator &
0122       requires std::random_access_iterator<range_itr_t>
0123     {
0124       detray::ranges::advance(m_seq_iter, j);
0125       m_range_begin += static_cast<difference_type>(*m_seq_iter);
0126       return *this;
0127     }
0128
0129     /// @returns advance this iterator state by @param j.
0130     DETRAY_HOST_DEVICE constexpr auto operator-=(const difference_type j)
0131         -> iterator &
0132       requires std::random_access_iterator<range_itr_t> &&
0133                std::random_access_iterator<sequence_itr_t>
0134     {
0135       return *this += -j;
0136     }
0137
0138     /// @returns the value and index at a given position - const
0139     DETRAY_HOST_DEVICE constexpr auto operator[](const difference_type i) const
0140       requires std::random_access_iterator<range_itr_t> &&
0141                std::random_access_iterator<sequence_itr_t>
0142     {
0143       const auto index{m_seq_iter[i]};
0144       return value_type(index, m_range_begin[index]);
0145     }
0146
0147    private:
0148     /// @returns true if we reach end of sequence
0149     DETRAY_HOST_DEVICE
0150     friend constexpr auto operator==(const iterator &lhs, const iterator &rhs)
0151         -> bool {
0152       return (lhs.m_seq_iter == rhs.m_seq_iter);
0153     }
0154
0155     /// @returns true if we reach end of sequence
0156     DETRAY_HOST_DEVICE
0157     friend constexpr auto operator<=>(const iterator &lhs, const iterator &rhs)
0158       requires detray::ranges::random_access_iterator<sequence_itr_t>
0159     {
0160 #if defined(__apple_build_version__)
0161       const auto l{lhs.m_seq_iter};
0162       const auto r{rhs.m_seq_iter};
0163       if (l < r || (l == r && l < r)) {
0164         return std::strong_ordering::less;
0165       }
0166       if (l > r || (l == r && l > r)) {
0167         return std::strong_ordering::greater;
0168       }
0169       return std::strong_ordering::equivalent;
0170 #else
0171       return (lhs.m_seq_iter <=> rhs.m_seq_iter);
0172 #endif
0173     }
0174
0175     /// @returns an iterator and index position advanced by @param j.
0176     DETRAY_HOST_DEVICE friend constexpr auto operator+(const iterator &itr,
0177                                                        const difference_type j)
0178         -> iterator
0179       requires std::random_access_iterator<range_itr_t>
0180     {
0181       auto seq_iter = detray::ranges::next(itr.m_seq_iter, j);
0182       return {itr.m_range_begin + static_cast<difference_type>(*seq_iter),
0183               itr.m_range_begin, seq_iter, itr.m_seq_end};
0184     }
0185
0186     /// @returns an iterator and index position advanced by @param j.
0187     DETRAY_HOST_DEVICE friend constexpr auto operator+(const difference_type j,
0188                                                        const iterator &itr)
0189         -> iterator
0190       requires std::random_access_iterator<range_itr_t>
0191     {
0192       return itr + j;
0193     }
0194
0195     /// @returns an iterator and index position advanced by @param j.
0196     DETRAY_HOST_DEVICE friend constexpr auto operator-(const iterator &itr,
0197                                                        const difference_type j)
0198         -> iterator
0199       requires std::random_access_iterator<range_itr_t>
0200     {
0201       return itr + (-j);
0202     }
0203
0204     /// @returns the positional difference between two iterations
0205     DETRAY_HOST_DEVICE friend constexpr auto operator-(const iterator &lhs,
0206                                                        const iterator &rhs)
0207         -> difference_type
0208       requires std::random_access_iterator<range_itr_t> &&
0209                std::random_access_iterator<sequence_itr_t>
0210     {
0211       return lhs.m_seq_iter - rhs.m_seq_iter;
0212     }
0213
0214     range_itr_t m_range_iter{};
0215     range_itr_t m_range_begin{};
0216     sequence_itr_t m_seq_iter{};
0217     sequence_itr_t m_seq_end{};
0218   };
0219
0220   range_itr_t m_range_begin{};
0221   range_itr_t m_range_end{};
0222   sequence_itr_t m_seq_begin{};
0223   sequence_itr_t m_seq_end{};
0224
0225  public:
0226   using iterator_t = iterator;
0227
0228   /// Default constructor
0229   constexpr pick_view() = default;
0230
0231   /// Construct from a @param range that will be enumerated beginning at 0
0232   template <detray::ranges::range range_t, detray::ranges::range sequence_t>
0233   DETRAY_HOST_DEVICE constexpr pick_view(range_t &&range, sequence_t &&seq)
0234       : m_range_begin{detray::ranges::begin(std::forward<range_t>(range))},
0235         m_range_end{detray::ranges::end(std::forward<range_t>(range))},
0236         m_seq_begin{detray::ranges::cbegin(std::forward<sequence_t>(seq))},
0237         m_seq_end{detray::ranges::cend(std::forward<sequence_t>(seq))} {}
0238
0239   /// @return start position of range on container.
0240   DETRAY_HOST_DEVICE
0241   constexpr auto begin() -> iterator {
0242     return {m_range_begin + static_cast<difference_t>(*m_seq_begin),
0243             m_range_begin, m_seq_begin, m_seq_end};
0244   }
0245
0246   /// @return start position of range on container.
0247   DETRAY_HOST_DEVICE
0248   constexpr auto begin() const -> iterator {
0249     return {m_range_begin + static_cast<difference_t>(*m_seq_begin),
0250             m_range_begin, m_seq_begin, m_seq_end};
0251   }
0252
0253   /// @return sentinel of a sequence.
0254   DETRAY_HOST_DEVICE
0255   constexpr auto end() -> iterator {
0256     return {m_range_begin, m_range_begin, m_seq_end, m_seq_end};
0257   }
0258
0259   /// @returns a pointer to the beginning of the data of the first underlying
0260   /// range - const
0261   DETRAY_HOST_DEVICE
0262   constexpr auto data() const -> const typename iterator_t::value_type * {
0263     return std::addressof(
0264         *(m_range_begin + static_cast<difference_t>(*m_seq_begin)));
0265   }
0266
0267   /// @returns a pointer to the beginning of the data of the first underlying
0268   /// range - non-const
0269   DETRAY_HOST_DEVICE
0270   constexpr auto data() -> typename iterator_t::value_type * {
0271     return std::addressof(
0272         *(m_range_begin + static_cast<difference_t>(*m_seq_begin)));
0273   }
0274
0275   /// @returns the number of elements in the underlying range. Simplified
0276   /// implementation compared to @c view_interface.
0277   DETRAY_HOST_DEVICE
0278   constexpr auto size() const noexcept {
0279     return detray::ranges::distance(m_seq_begin, m_seq_end);
0280   }
0281
0282   /// @returns access to the first element value in the range, including the
0283   /// corresponding index.
0284   DETRAY_HOST_DEVICE
0285   constexpr auto front() noexcept {
0286     return std::pair<index_t, value_t &>(
0287         *m_seq_begin,
0288         *detray::ranges::next(m_range_begin,
0289                               static_cast<difference_t>(*m_seq_begin)));
0290   }
0291
0292   /// @returns access to the last element value in the range, including the
0293   /// corresponding index.
0294   DETRAY_HOST_DEVICE
0295   constexpr auto back() noexcept {
0296     index_t last_idx{*detray::ranges::next(
0297         m_seq_begin, static_cast<difference_t>((size() - 1u)))};
0298     return std::pair<index_t, value_t &>(
0299         last_idx, *detray::ranges::next(m_range_begin,
0300                                         static_cast<difference_t>(last_idx)));
0301   }
0302
0303   DETRAY_HOST_DEVICE
0304   constexpr auto operator[](const dindex i) const {
0305     index_t last_idx{
0306         *detray::ranges::next(m_seq_begin, static_cast<difference_t>(i))};
0307     return std::pair<index_t, value_t &>(
0308         last_idx, *detray::ranges::next(m_range_begin,
0309                                         static_cast<difference_t>(last_idx)));
0310   }
0311 };
0312
0313 namespace views {
0314
0315 template <std::input_iterator range_itr_t,
0316           detray::ranges::input_range sequence_t>
0317 struct pick : public pick_view<range_itr_t, detray::ranges::const_iterator_t<
0318                                                 std::decay_t<sequence_t>>> {
0319   using sequence_itr_t =
0320       detray::ranges::const_iterator_t<std::decay_t<sequence_t>>;
0321   using base_type = pick_view<range_itr_t, sequence_itr_t>;
0322
0323   constexpr pick() = default;
0324
0325   template <detray::ranges::input_range deduced_sequence_t>
0326   DETRAY_HOST_DEVICE constexpr explicit pick(deduced_sequence_t &&seq)
0327       : m_seq(std::forward<deduced_sequence_t>(seq)) {}
0328
0329   template <detray::ranges::range range_t,
0330             detray::ranges::input_range deduced_sequence_t>
0331   DETRAY_HOST_DEVICE constexpr pick(range_t &&range, deduced_sequence_t &&seq)
0332       : base_type(std::forward<range_t>(range), seq),
0333         m_seq{std::forward<deduced_sequence_t>(seq)} {}
0334
0335   /// Call operator for range composition - move semantics
0336   template <detray::ranges::range range_t>
0337     requires(std::same_as<sequence_t, std::remove_cvref_t<sequence_t>> &&
0338              !std::is_pointer_v<sequence_t>)
0339   DETRAY_HOST_DEVICE constexpr auto operator()(range_t &&rng) && {
0340     using itr_t = detray::ranges::iterator_t<std::remove_reference_t<range_t>>;
0341     return detray::ranges::pick_view<itr_t, sequence_itr_t>(
0342         std::forward<range_t>(rng), std::move(m_seq));
0343   }
0344
0345   /// Call operator for range composition
0346   template <detray::ranges::range range_t>
0347     requires(!std::same_as<sequence_t, std::remove_cvref_t<sequence_t>> ||
0348              std::is_pointer_v<sequence_t>)
0349   DETRAY_HOST_DEVICE constexpr auto operator()(range_t &&rng) {
0350     using itr_t = detray::ranges::iterator_t<std::remove_reference_t<range_t>>;
0351     return detray::ranges::pick_view<itr_t, sequence_itr_t>(
0352         std::forward<range_t>(rng), m_seq);
0353   }
0354
0355   /// Copy assignment operator
0356   DETRAY_HOST_DEVICE
0357   pick &operator=(const pick &other) {
0358     base_type::operator=(other);
0359     m_seq = other.m_seq;
0360     return *this;
0361   }
0362
0363  private:
0364   sequence_t m_seq{};
0365 };
0366
0367 // deduction guides>
0368 DETRAY_HOST_DEVICE pick()
0369     -> pick<detray::ranges::iterator_t<detray::ranges::views::empty<int>>,
0370             dvector<int>>;
0371
0372 template <detray::ranges::range sequence_t>
0373 DETRAY_HOST_DEVICE pick(sequence_t &&seq)
0374     -> pick<detray::ranges::iterator_t<detray::ranges::views::empty<int>>,
0375             sequence_t>;
0376
0377 template <detray::ranges::range range_t, detray::ranges::range sequence_t>
0378 DETRAY_HOST_DEVICE pick(range_t &&range, sequence_t &&seq)
0379     -> pick<detray::ranges::iterator_t<std::remove_reference_t<range_t>>,
0380             sequence_t>;
0381
0382 }  // namespace views
0383
0384 }  // namespace detray::ranges