I've created a type trait to create a type pack of rotating index sequences:
#include <cstddef>
#include <utility>
template <class...>
struct type_pack {};
template <size_t N>
using make_pack_of_rotating_index_sequences = ...;
make_pack_of_rotating_index_sequences<3> is then an alias for
type_pack<std::index_sequence<0,1,2>,
std::index_sequence<1,2,0>,
std::index_sequence<2,0,1>>
However, with large Ns, compilers start having problems (running out of heap space, timing out in Compler Explorer etc). clang and icx manages 700+ and gcc and MSVC fail long before that (playground @ Compiler Explorer).
My current approach naively adds one index_sequence at a time by recursive inheritance:
template <class...>
struct type_pack {}; // seems to compile slightly faster than using a tuple
namespace rot_detail {
template <class...> // primary, not implemented
struct rot_help;
template <> // empty sequence entry point and terminator
struct rot_help<std::index_sequence<>> {
using type = type_pack<>;
};
// extra entry point and terminator needed for MSVC with N=1.
// I tried to report this bug but was "not authorized".
template <std::size_t I0>
struct rot_help<std::index_sequence<I0>> {
using type = type_pack<std::index_sequence<I0>>;
};
template <size_t I0, size_t... Is, class... Seqs> // normal terminator
struct rot_help<std::index_sequence<I0, Is...>, std::index_sequence<I0, Is...>,
Seqs...> {
using type = type_pack<Seqs...>;
};
template <size_t I0, size_t... Is> // entry point for non-empty sequence
struct rot_help<std::index_sequence<I0, Is...>>
: rot_help<std::index_sequence<Is..., I0>, std::index_sequence<I0, Is...>,
std::index_sequence<I0, Is...>> {};
template <size_t I0, size_t... Is, class End, class... Seqs> // builder
struct rot_help<std::index_sequence<I0, Is...>, End, Seqs...>
: rot_help<std::index_sequence<Is..., I0>, End, Seqs...,
std::index_sequence<I0, Is...>> {};
} // namespace rot_detail
template <size_t N>
using make_pack_of_rotating_index_sequences =
rot_detail::rot_help<std::make_index_sequence<N>>::type;
I've also tried a similar approach using function overloads. It's very similar so I don't include it. It also made matters worse so I dropped that idea.
When creating traits using recursive inheritance it's often possible to apply some sort of divide and conquer approach and then to assemble the result at the end to reduce the recursive depth and complexity, and in that spirit I tried to see if I could cut the inheritance depth in half by doing two rotations per pass (Compler Explorer) as long as the next depth doesn't reach the terminator:
template <class...> struct two;
template <size_t I0, size_t I1, size_t... Is, class End, class... Seqs>
struct two<std::index_sequence<I0, I1, Is...>, End, Seqs...> {
using type = rot_help<std::index_sequence<Is..., I0, I1>, End, Seqs...,
std::index_sequence<I0, I1, Is...>,
std::index_sequence<I1, Is..., I0>>;
};
template <size_t I0, size_t... Is, class End, class... Seqs> // builder
struct rot_help<std::index_sequence<I0, Is...>, End, Seqs...>
: std::conditional_t<
std::same_as<std::index_sequence<Is..., I0>, End>,
rot_help<End, End, Seqs..., std::index_sequence<I0, Is...>>,
typename two<std::index_sequence<I0, Is...>, End, Seqs...>::type> {};
But the compilation time and max N seems largely unaffected by this attempt. I need fresh eyes on this.
This type trait is used as an implementation detail in code which available for review in a series of questions. See Freestanding try_lock_for / try_lock_until.
This would do it:
template <std::size_t N>
using make_pack_of_rotating_index_sequences = decltype([]<std::size_t... I>(std::index_sequence<I...>){
return type_pack<decltype([]<std::size_t II, std::size_t... J>() {
return std::index_sequence<((J + II) % N)...>{};
}.template operator()<I, I...>())...>{};
}(std::make_index_sequence<N>{}));
It does appear to reveal a clang bug with make_index_sequence, so you can do a version with class templates instead:
namespace rot_detail {
template<std::size_t I, typename IndexSeq>
struct rotate;
template<std::size_t I, std::size_t... J>
struct rotate<I, std::index_sequence<J...>> {
using type = std::index_sequence<((J + I) % sizeof...(J))...>;
};
template<typename IndexSeq>
struct make_pack_impl;
template<std::size_t... I>
struct make_pack_impl<std::index_sequence<I...>> {
using type = type_pack<typename rotate<I, std::index_sequence<I...>>::type...>;
};
} // namespace rot_detail
template <std::size_t N>
using make_pack_of_rotating_index_sequences = typename rot_detail::make_pack_impl<std::make_index_sequence<N>>::type;
The crux is rotating std::make_index_sequence<N> by some value I is the same as adding I to every value and then taking it modulo N.