core/utility/static_permutation.hpp

0001 /*
0002  * SPDX-PackageName: "covfie, a part of the ACTS project"
0003  * SPDX-FileCopyrightText: 2022 CERN
0004  * SPDX-License-Identifier: MPL-2.0
0005  */
0006
0007 #pragma once
0008
0009 #include <cstddef>
0010 #include <type_traits>
0011 #include <utility>
0012
0013 namespace covfie::utility {
0014 /**
0015  * @brief Utility to concatenate two type-level index sequences.
0016  *
0017  * This is the unspecialised version of the utility, which basically does
0018  * nothing. It needs to be matched to two actual index sequences to work.
0019  */
0020 template <typename, typename>
0021 struct concat_index_sequence {
0022 };
0023
0024 /*
0025  * This is a specialization of `concat_index_sequence` specialized to work on
0026  * two index sequences, this simply takes two sequences and puts one after the
0027  * other in a new type.
0028  */
0029 template <std::size_t... L, std::size_t... H>
0030 struct concat_index_sequence<
0031     std::index_sequence<L...>,
0032     std::index_sequence<H...>> {
0033     using type = std::index_sequence<L..., H...>;
0034 };
0035
0036 /**
0037  * @brief Utility to filter index sequences, keeping only values smaller than
0038  * a given pivot.
0039  *
0040  * This is the unspecialised version of the utility, which basically does
0041  * nothing. It needs to be matched to a pivot and an index sequence to work.
0042  */
0043 template <typename, typename>
0044 struct filter_index_sequence_lt {
0045 };
0046
0047 /*
0048  * This is a specialization of `filter_index_sequence_lt` that works on empty
0049  * sequences. Obviously, this just returns an empty sequence.
0050  */
0051 template <std::size_t N>
0052 struct filter_index_sequence_lt<
0053     std::integral_constant<std::size_t, N>,
0054     std::index_sequence<>> {
0055     using type = std::index_sequence<>;
0056 };
0057
0058 /*
0059  * This is a specialization of `filter_index_sequence_lt` that works on
0060  * non-empty sequences, which consist of a head V and a tail Vs. This works
0061  * recursively.
0062  */
0063 template <std::size_t N, std::size_t V, std::size_t... Vs>
0064 struct filter_index_sequence_lt<
0065     std::integral_constant<std::size_t, N>,
0066     std::index_sequence<V, Vs...>> {
0067     using type = typename concat_index_sequence <
0068                  std::conditional_t<
0069                      V<N, std::index_sequence<V>, std::index_sequence<>>,
0070                      typename filter_index_sequence_lt<
0071                          std::integral_constant<std::size_t, N>,
0072                          std::index_sequence<Vs...>>::type>::type;
0073 };
0074
0075 /**
0076  * @brief Utility to filter index sequences, keeping only values greater than
0077  * or equal to a given pivot.
0078  *
0079  * This is the unspecialised version of the utility, which basically does
0080  * nothing. It needs to be matched to a pivot and an index sequence to work.
0081  */
0082 template <typename, typename>
0083 struct filter_index_sequence_geq {
0084 };
0085
0086 /*
0087  * This is a specialization of `filter_index_sequence_geq` that works on empty
0088  * sequences. Obviously, this just returns an empty sequence.
0089  */
0090 template <std::size_t N>
0091 struct filter_index_sequence_geq<
0092     std::integral_constant<std::size_t, N>,
0093     std::index_sequence<>> {
0094     using type = std::index_sequence<>;
0095 };
0096
0097 /*
0098  * This is a specialization of `filter_index_sequence_geq` that works on
0099  * non-empty sequences, which consist of a head V and a tail Vs. This works
0100  * recursively.
0101  */
0102 template <std::size_t N, std::size_t V, std::size_t... Vs>
0103 struct filter_index_sequence_geq<
0104     std::integral_constant<std::size_t, N>,
0105     std::index_sequence<V, Vs...>> {
0106     using type = typename concat_index_sequence<
0107         std::conditional_t<
0108             V >= N,
0109             std::index_sequence<V>,
0110             std::index_sequence<>>,
0111         typename filter_index_sequence_geq<
0112             std::integral_constant<std::size_t, N>,
0113             std::index_sequence<Vs...>>::type>::type;
0114 };
0115
0116 /**
0117  * @brief Utility to sort a compile-time index sequence using a merge sort
0118  * algorithm.
0119  *
0120  * This is the unspecialised version of the utility, which basically does
0121  * nothing. It needs to be matched to a pivot and an index sequence to work.
0122  */
0123 template <typename>
0124 struct sort_index_sequence {
0125 };
0126
0127 /*
0128  * This is a specialization of `sort_index_sequence` that works on empty
0129  * sequences, which obviously returns an empty sequence.
0130  */
0131 template <>
0132 struct sort_index_sequence<std::index_sequence<>> {
0133     using type = std::index_sequence<>;
0134 };
0135
0136 /*
0137  * This is a specialization of `sort_index_sequence` that works on non-empty
0138  * sequences consisting of a head N and a tail Ns. The head N is used as a
0139  * pivot, and the tail is split in two parts: the lower half (with values
0140  * smaller than N) and the upper part (with values greater than or equal to N).
0141  * These are then concatenated, with the pivot N in between them.
0142  */
0143 template <std::size_t N, std::size_t... Ns>
0144 struct sort_index_sequence<std::index_sequence<N, Ns...>> {
0145     using type = typename concat_index_sequence<
0146         typename sort_index_sequence<typename filter_index_sequence_lt<
0147             std::integral_constant<std::size_t, N>,
0148             std::index_sequence<Ns...>>::type>::type,
0149         typename concat_index_sequence<
0150             std::index_sequence<N>,
0151             typename sort_index_sequence<typename filter_index_sequence_geq<
0152                 std::integral_constant<std::size_t, N>,
0153                 std::index_sequence<Ns...>>::type>::type>::type>::type;
0154 };
0155
0156 /**
0157  * @brief Utility to check if two index sequences are permutations of each
0158  * other.
0159  *
0160  * This is the unspecialised version of the utility, which basically does
0161  * nothing. It needs to be matched to a pivot and an index sequence to work.
0162  */
0163 template <typename, typename>
0164 struct is_permutation : std::false_type {
0165 };
0166
0167 /*
0168  * This is a specialization of `is_permutation`, which simply sorts both
0169  * sequences and then checks if they are equal! Simplest algorithm to check for
0170  * permutations in the book.
0171  */
0172 template <std::size_t... Us, std::size_t... Vs>
0173 struct is_permutation<std::index_sequence<Us...>, std::index_sequence<Vs...>>
0174     : std::is_same<
0175           typename sort_index_sequence<std::index_sequence<Us...>>::type,
0176           typename sort_index_sequence<std::index_sequence<Vs...>>::type> {
0177 };
0178 }