traccc/sanity/ordered_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 // VecMem include(s).
0012 #include <vecmem/containers/data/vector_view.hpp>
0013 #include <vecmem/containers/device_vector.hpp>
0014 #include <vecmem/memory/memory_resource.hpp>
0015 #include <vecmem/utils/copy.hpp>
0016
0017 // System include
0018 #include <concepts>
0019 #include <utility>
0020
0021 namespace traccc::host {
0022 /**
0023  * @brief Sanity check that a given vector is ordered on a given relation.
0024  *
0025  * For a vector $v$ to be ordered on a relation $R$, it must be the case that
0026  * for all indices $i$ and $j$, if $i < j$, then $R(i, j)$.
0027  *
0028  * @note This function runs in O(n) time.
0029  *
0030  * @note Although functions like `std::sort` requires the relation to be strict
0031  * weak order, this function is more lax in its requirements. Rather, the
0032  * relation should be a total preorder, i.e. a non-strict weak order.
0033  *
0034  * @note For any strict weak order $R$, `is_ordered_on(sort(R, v))` is true.
0035  *
0036  * @tparam R The type of relation $R$, a callable which returns a bool if the
0037  * first argument can be immediately before the second type.
0038  * @tparam T The type of the vector.
0039  * @param relation A relation object of type `R`.
0040  * @param mr A memory resource used for allocating intermediate memory.
0041  * @param vector The vector which to check for ordering.
0042  * @return true If the vector is ordered on `R`.
0043  * @return false Otherwise.
0044  */
0045 template <typename R, typename CONTAINER>
0046   requires std::regular_invocable<R, decltype(std::declval<CONTAINER>().at(0)),
0047                                   decltype(std::declval<CONTAINER>().at(0))> &&
0048            std::semiregular<R>
0049
0050 bool is_ordered_on(R&& relation, const CONTAINER& in) {
0051   // Grab the number of elements in our vector.
0052   typename CONTAINER::size_type n = in.size();
0053
0054   // Check for orderedness.
0055   for (typename CONTAINER::size_type i = 1; i < n; ++i) {
0056     if (!relation(in.at(i - 1), in.at(i))) {
0057       return false;
0058     }
0059   }
0060
0061   return true;
0062 }
0063 }  // namespace traccc::host