I have the data structure:
template <int...I> struct index {};
template <typename...T> struct data {};
template <int I, int J> struct X
{
static constexpr int i = I;
static constexpr int j = J;
};
typedef data< X<0,4>, X<1,2>, X<2,1>, X<1,6>, X<1,3> > data_t;
Where data does not contain duplicates and the indices J are small, in the range 0-31.
I want to create a static index which contains the position in data of all X with index I equal to some given value (e.g. I=1), sorted by index J. It is the "sorting" bit which I find difficult.
For example, I would like to implement a class build_index such that:
typedef build_index<1,data>::type_t index_t;
generates the same as:
typedef index<1, 4, 3> index_t;
which reflects the positions in data of the elements X(1,J) ordered by J: X(1,2) at data(1), X(1,3) at data(4), X(1,6) at data(3)
I would prefer not to use the STL, as it is not available for gcc-avr, although I could port selected snippets.
When you are facing something complex in C++ template programming, it mostly helps to try to break it into several smaller steps (like with most programming problems). Here is a possible path:
And here is the corresponding code. I am using std::conditional
, but that is easy to replace of course. I am using std::is_same
in the tests, you do not really need that of course (and it would be trivial to implement otherwise).
Your stuff + utility header for std::conditional and std::is_same
#include <utility>
template <int... I>
struct index
{
};
template <typename... T>
struct data
{
};
template <int I, int J>
struct X
{
static constexpr int i = I;
static constexpr int j = J;
};
typedef data<X<0, 4>, X<1, 2>, X<2, 1>, X<1, 6>, X<1, 3>> data_t;
Extract the X
s that match the I
we are looking for and replace the i
s with the position.
template <int Pos, int I, typename Extracted, typename Rest>
struct ExtractImpl;
template <int Pos, int I, typename... ExtractedX>
struct ExtractImpl<Pos, I, data<ExtractedX...>, data<>>
{
using type = data<ExtractedX...>;
};
template <int Pos, int I, typename... ExtractedX, typename T, typename... Rest>
struct ExtractImpl<Pos, I, data<ExtractedX...>, data<T, Rest...>>
{
using type = typename std::conditional<
(T::i == I),
typename ExtractImpl<Pos + 1,
I,
data<ExtractedX..., X<Pos, T::j>>,
data<Rest...>>::type,
typename ExtractImpl<Pos + 1, I, data<ExtractedX...>, data<Rest...>>::
type>::type;
};
template <int I, typename Data>
struct Extract
{
using type = typename ExtractImpl<0, I, data<>, Data>::type;
};
using extracted = typename Extract<1, data_t>::type;
static_assert(std::is_same<extracted, data<X<1, 2>, X<3, 6>, X<4, 3>>>::value, "");
Sort by J. This is done by incrementally inserting elements into a sorted list. There might be more elegant ways to do it.
template <typename T, typename LessList, typename RestList>
struct insert_impl;
template <typename T, typename... Lesser>
struct insert_impl<T, data<Lesser...>, data<>>
{
using type = data<Lesser..., T>;
};
template <typename T, typename... Lesser, typename Next, typename... Rest>
struct insert_impl<T, data<Lesser...>, data<Next, Rest...>>
{
using type = typename std::conditional<
(T::j < Next::j),
data<Lesser..., T, Next, Rest...>,
typename insert_impl<T, data<Lesser..., Next>, data<Rest...>>::type>::
type;
};
template <typename T, typename SortedList>
struct insert
{
using type = typename insert_impl<T, data<>, SortedList>::type;
};
template <typename SortedList, typename UnsortedList>
struct SortImpl;
template <typename SortedList>
struct SortImpl<SortedList, data<>>
{
using type = SortedList;
};
template <typename SortedList, typename T, typename... UnsortedX>
struct SortImpl<SortedList, data<T, UnsortedX...>>
{
using type = typename SortImpl<typename insert<T, SortedList>::type,
data<UnsortedX...>>::type;
};
template <typename UnsortedList>
struct Sort
{
using type = typename SortImpl<data<>, UnsortedList>::type;
};
using sorted = typename Sort<extracted>::type;
static_assert(std::is_same<sorted, data<X<1, 2>, X<4, 3>, X<3, 6>>>::value, "");
Finally, extract the indexes you are looking for:
template <typename List>
struct Indexes;
template <typename... Data>
struct Indexes<data<Data...>>
{
using type = index<Data::i...>;
};
using result = typename Indexes<sorted>::type;
static_assert(std::is_same<result, index<1, 4, 3>>::value, "");
Word of warning: While I don't see any problems in the code, I have not tested it beyond your example...
I'll share my approach to this problem which I think is kind of neat. I used C++11 std::conditional
, and C++14 std::integer_sequence
and std::make_integer_sequence
, all of which you can find implementations of online.
Let's start with the data structures you had.
template <int... Is> struct index {};
template <typename... Ts> struct list {};
template <int L, int R> struct pair {};
We'll use a metafunction concat
, which concatenates N
list of types. We use it to filter a list by returning list<T>
when the predicate returns true
, and list<>
otherwise.
For example, to filter the even numbers from list<1, 3, 2, 4, 2>
, we can perform std::conditional_t<I % 2 == 0, list<I>, list<>>
for each I
to get concat_t<list<>, list<>, list<2>, list<4>, list<2>>
= list<2, 4, 2>
.
template <typename... Ts> struct concat;
template <> struct concat<> { using type = list<>; }
template <typename... Ts>
struct concat<list<Ts...>> { using type = list<Ts...>; };
template <typename... Ts, typename... Us>
struct concat<list<Ts...>, list<Us...>> { using type = list<Ts..., Us...>; };
template <typename... Ts, typename... Us, typename... Tail>
struct concat<list<Ts...>, list<Us...>, Tail...>
: concat<list<Ts..., Us...>, Tail...> {};
template <typename... Ts>
using concat_t = typename concat<Ts...>::type;
Now we get to build_index
. We perform bucket sort within the known range of [0, 32)
. We could have used a generic sorting algorithm, but it was more fun to cheat.
template <int N, typename T> struct build_index;
// e.g., `build_index<
// 1, list<pair<0, 4>, pair<1, 2>, pair<2, 1>, pair<1, 6>, pair<1, 3>>`
template <int N, int... Ls, int... Rs>
struct build_index<N, list<pair<Ls, Rs>...>> {
// Filter for pairs where `N == lhs`, and replace the `lhs` with the index.
template <int... Is>
static auto filter(std::integer_sequence<int, Is...>)
-> concat_t<std::conditional_t<N == Ls, list<pair<Is, Rs>>, list<>>...>;
// e.g., `list<pair<1, 2>, pair<3, 6>, pair<4, 3>>`
using filtered =
decltype(filter(std::make_integer_sequence<int, sizeof...(Ls)>{}));
// `get<I>(set)` returns the `lhs` if `set` can implicitly convert to
// `pair<lhs, I>` for some `lhs`, and nothing otherwise.
template <typename... Ts> struct set : Ts... {};
template <int I, int L> static list<index<L>> get(pair<L, I>);
template <int I> static list<> get(...);
// We invoke `get<I>` for `I` in `[0, 32)` to sort `filtered`.
template <int... Is, typename... Ts>
static auto sort(std::integer_sequence<int, Is...>, list<Ts...>)
-> concat_t<decltype(get<Is>(set<Ts...>{}))...>;
// e.g., `list<index<1>, index<4>, index<3>>`
using sorted =
decltype(sort(std::make_integer_sequence<int, 32>{}, filtered{}));
// e.g., `list<1, 4, 3>`
template <int... Is> static index<Is...> indices(list<index<Is>...>);
using type = decltype(indices(sorted{}));
};
template <int N, typename... Ts>
using build_index_t = typename build_index<N, Ts...>::type;
With which we get:
using index_t = build_index_t<
1, list<pair<0, 4>, pair<1, 2>, pair<2, 1>, pair<1, 6>, pair<1, 3>>>;
static_assert(std::is_same<index<1, 4, 3>, index_t>::value, "");
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With