3
\$\begingroup\$

Often we need to find out if two tuples, or two packs in general, are the same as each other up to permutation. If there are no repeat types, then implementing is_permutation_no_repeats is quite straightforward. For example, simply remove each type in the first pack from the second pack and check if the second pack becomes empty or not. If the two packs have repeated types, then simply group those repeated types into num_types<T, Count>, where Count is the number of times T occurs in the pack. Then we've reduced the two packs into packs of num_types<T, Count>s types, and thus have no repeat types any more, and then is_permutation_no_repeats can be invoked. Here is my implementation and test:

#include <type_traits>
#include <utility>

namespace utilities {
    template <typename T, typename Pack, typename... Ts> struct remove_first_found;

    template <typename T, template <typename...> class P,  typename... Ts>
    struct remove_first_found<T, P<>, Ts...> {
        using type = P<Ts...>;  // T was never found.   
    };

    template <typename T, template <typename...> class P, typename... Rest, typename... Ts>
    struct remove_first_found<T, P<T, Rest...>, Ts...> {
        using type = P<Ts..., Rest...>;  // First T found and removed.
    };

    template <typename T, template <typename...> class P, typename First, typename... Rest, typename... Ts>
    struct remove_first_found<T, P<First, Rest...>, Ts...> : remove_first_found<T, P<Rest...>, Ts..., First> { };
}

template <typename T, std::size_t Count> struct num_types;

template <typename T, typename Pack, std::size_t Count, typename... Ts> struct get_num_types;

template <typename T, template <typename...> class P, std::size_t Count, typename... Ts>
struct get_num_types<T, P<>, Count, Ts...> {
    using type = num_types<T, Count>;
    using remaining = P<Ts...>;
};

template <typename T, template <typename...> class P, typename First, typename... Rest, std::size_t Count, typename... Ts>
struct get_num_types<T, P<First, Rest...>, Count, Ts...> : get_num_types<T, P<Rest...>, Count, Ts..., First> { };

template <typename T, template <typename...> class P, typename... Rest, std::size_t Count, typename... Ts>
struct get_num_types<T, P<T, Rest...>, Count, Ts...> : get_num_types<T, P<Rest...>, Count + 1, Ts...> { };

template <typename Pack, typename... NumTypes> struct count_types;

template <template <typename...> class P, typename... NumTypes>
struct count_types<P<>, NumTypes...> {
    using type = P<NumTypes...>;
};

template <template <typename...> class P, typename First, typename... Rest, typename... NumTypes>
struct count_types<P<First, Rest...>, NumTypes...> {
    using meta = get_num_types<First, P<Rest...>, 1>;
    using type = typename count_types<typename meta::remaining, NumTypes..., typename meta::type>::type;
};

template <typename Pack1, typename Pack2>
struct is_permutation_no_repeats : std::false_type { };

template <template <typename...> class P, template <typename...> class Q>
struct is_permutation_no_repeats<P<>, Q<>> : std::true_type { };

template <template <typename...> class P, typename First, typename... Rest, typename Pack2>
struct is_permutation_no_repeats<P<First, Rest...>, Pack2> {
    using meta = typename utilities::remove_first_found<First, Pack2>::type;
    static constexpr bool value = std::is_same_v<meta, Pack2> ? false : is_permutation_no_repeats<P<Rest...>, meta>::value;
};

template <typename Pack1, typename Pack2>
struct is_permutation : is_permutation_no_repeats<typename count_types<Pack1>::type, typename count_types<Pack2>::type> { };

template <typename Pack1, typename Pack2>
constexpr bool is_permutation_v = is_permutation<Pack1, Pack2>::value;

// Testing
template <typename...> struct P;
template <typename...> struct Q;

int main() {
    static_assert(std::is_same_v<
        count_types<P<int, char, long, int, bool, char, bool, int, double, int, bool>>::type,
        P<num_types<int, 4>, num_types<char, 2>, num_types<long, 1>, num_types<bool, 3>, num_types<double, 1>>
    >);

    static_assert(is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
        Q<int, char, long, int, bool, char, bool, int, double, int, bool>>);  // Identical contents in the two packs.
    static_assert(is_permutation_v<P<int, char, long, bool, double>,
        Q<double, bool, int, long, char>>);  // Permutation with no repeats types.
    static_assert(is_permutation_no_repeats<P<int, char, long, bool, double>,
        Q<double, bool, int, long, char>>::value);
    static_assert(is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
        Q<bool, int, bool, int, char, int, int, bool, char, long, double>>);  // Permutations with repeat types.
    static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
        Q<bool, int, float, int, char, int, int, bool, char, long, double>>);  // Second pack has float when the first pack does not.
    static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
        Q<bool, int, bool, int, char, int, int, bool, char, long>>);  // Second pack is one type less than the first pack.
    static_assert(!is_permutation_v<P<int, char, long, int, bool, char, bool, int, double, int, bool>,
        Q<bool, int, bool, int, char, int, int, bool, double, long, double>>);  // Second pack 2 doubles instead of 1 and 1 char instead of 2.
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Ok, nice example of building Prolog with templates. Just tell me the example when you need that in real project and what you will do after having the knoledge about "permutations". Cause "slightly" better would be define the order of types in template, so other people, and you after some time would not have headacke about what parameter is on what position. With the thing above, you can heal the wrong order only of different types. \$\endgroup\$ – user8426627 Jan 25 '18 at 0:12
  • \$\begingroup\$ @user8426627 I believe Scott Meyers did something similar when he was adding concepts to the language. This kind of stuff is useful when building library features that provide extension like features to the language (like boost::MPL or feature like that). It may not be needed by an external user of the library but to provide internal consistency within the library it is very useful. \$\endgroup\$ – Martin York Jan 25 '18 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.