traccc/sanity/contiguous_on.hpp

0001 /**
0002  * traccc library, part of the ACTS project (R&D line)
0003  *
0004  * (c) 2024 CERN for the benefit of the ACTS project
0005  *
0006  * Mozilla Public License Version 2.0
0007  */
0008
0009 #pragma once
0010
0011 // System include
0012 #include <concepts>
0013 #include <memory>
0014 #include <unordered_set>
0015 #include <utility>
0016
0017 namespace traccc::host {
0018
0019 /**
0020  * @brief Sanity check that a given container is contiguous on a given
0021  *        projection.
0022  *
0023  * For a container $c$ to be contiguous on a projection $\pi$, it must be the
0024  * case that for all indices $i$ and $j$, if $v_i = v_j$, then all indices $k$
0025  * between $i$ and $j$, $v_i = v_j = v_k$.
0026  *
0027  * @note This function runs in O(n^2) time.
0028  *
0029  * @tparam P The type of projection $\pi$, a callable which returns some
0030  * comparable type.
0031  * @tparam CONTAINER The (SoA) container type
0032  * @param projection A projection object of type `P`.
0033  * @param mr A memory resource used for allocating intermediate memory.
0034  * @param vector The vector which to check for contiguity.
0035  * @return true If the vector is contiguous on `P`.
0036  * @return false Otherwise.
0037  */
0038 template <typename P, typename CONTAINER>
0039   requires std::regular_invocable<P,
0040                                   decltype(std::declval<CONTAINER>().at(0))> &&
0041            std::semiregular<P>
0042 bool is_contiguous_on(P&& projection, const CONTAINER& in) {
0043   // Grab the number of elements in our container.
0044   typename CONTAINER::size_type n = in.size();
0045
0046   // Get the output type of the projection.
0047   using projection_t =
0048       std::invoke_result_t<P, decltype(std::declval<CONTAINER>().at(0))>;
0049
0050   // Allocate memory for intermediate values and outputs, then set them up.
0051   std::unique_ptr<projection_t[]> iout = std::make_unique<projection_t[]>(n);
0052   std::size_t iout_size = 0;
0053
0054   // Compress adjacent elements
0055   for (std::size_t i = 0; i < n; ++i) {
0056     if (i == 0) {
0057       iout[iout_size++] =
0058           projection(in.at(static_cast<typename CONTAINER::size_type>(i)));
0059     } else {
0060       projection_t v =
0061           projection(in.at(static_cast<typename CONTAINER::size_type>(i)));
0062
0063       if (v != iout[iout_size - 1]) {
0064         iout[iout_size++] = v;
0065       }
0066     }
0067   }
0068
0069   // Check whether all elements are unique
0070   std::unordered_set<projection_t> seen;
0071
0072   for (std::size_t i = 0; i < iout_size; ++i) {
0073     projection_t& v = iout[i];
0074
0075     if (seen.count(v) == 1) {
0076       return false;
0077     } else {
0078       seen.insert(v);
0079     }
0080   }
0081
0082   return true;
0083 }
0084
0085 }  // namespace traccc::host