// Pattern Matching of Variadic Templates for Type Collections in C++
// - see peano.cpp for an introduction to type arithmetic
// - check a functional programming language like Haskell for
//   the declaration and usage of recursive lists

// compile and test: "c++ typecollections.cpp -o typecollections && ./typecollections"

//
// typelist declaration
//

template<class ...elems>
struct typelist {
};

//
// typelist_index: get the (first) index of a type
//

// empty declaration: compilation error if the type is not found
template<class type, class list>
struct typelist_index {
};

// end of the recursion, the type match the head
template<class type, class ...tail>
struct typelist_index<type, typelist<type, tail...>> {
    enum : unsigned { value = 0 };
};

// recursive declaration
template<class type, class head, class ...tail>
struct typelist_index<type, typelist<head, tail...>> {
    enum : unsigned { value = typelist_index<type, typelist<tail...>>::value + 1u };
};

//
// typelist_get: get the type at the given index
//

// empty declaration: compilation error if the index is out of bound
template<unsigned index, class list>
struct typelist_get {
};

// end of the recursion, the type match
template<class _type, class ...tail>
struct typelist_get<0u, typelist<_type, tail...>> {
    using type = _type;
};

// recursive declaration
template<unsigned index, class head, class ...tail>
struct typelist_get<index, typelist<head, tail...>> {
    using type = typename typelist_get<index - 1, typelist<tail...>>::type;
};

//
// typelist_insert: insert an element at the beginning of a list
//

// declaration
template<class elem, class list>
struct typelist_insert {
};

// insert the new head, actually not recursive
template<class head, class ...tail>
struct typelist_insert<head, typelist<tail...>> {
    using type = typelist<head, tail...>;
};

//
// typedict_entry declaration
//

// typedict_entry declaration
template<auto key, class type>
struct typedict_entry {
};

//
// typedict_contains: check if the typelist contains the key
//

// declaration and fallback if the key is missing
template<auto key, class list>
struct typedict_contains {
	enum : bool { value = false };
};

// end of the recursion when the key is found
template<auto key, class type, class ...tail>
struct typedict_contains<key, typelist<typedict_entry<key, type>, tail...>> {
	enum : bool { value = true };
};

// recursive declaration
template<auto key, class head, class ...tail>
struct typedict_contains<key, typelist<head, tail...>> {
    enum : bool { value = typedict_contains<key, typelist<tail...>>::value };
};

//
// typedict_index: get the (first) index of a key
//

// empty declaration: compilation error if the key is missing
template<auto key, class list>
struct typedict_index {
};

// end of the recursion, the key match
template<auto key, class type, class ...tail>
struct typedict_index<key, typelist<typedict_entry<key, type>, tail...>> {
	enum : unsigned { value = 0 };
};

// recursive declaration
template<auto key, class head, class ...tail>
struct typedict_index<key, typelist<head, tail...>> {
    enum : unsigned { value = typedict_index<key, typelist<tail...>>::value + 1u };
};

//
// typedict_get: get the type associated with a key
//

// empty declaration: compilation error if the key is missing
template<auto key, class list>
struct typedict_get {
};

// end of the recursion: the key match a typedict_entry in the list
template<auto key, class _type, class ...tail>
struct typedict_get<key, typelist<typedict_entry<key, _type>, tail...>> {
    using type = _type;
};

// recursive declaration
template<auto key, class head, class ...tail>
struct typedict_get<key, typelist<head, tail...>> {
    using type = typename typedict_get<key, typelist<tail...>>::type;
};

//
// typetree_flatten: flatten a tree
//

// empty declaration: end of the recursion if the typelist is empty
template<class list>
struct typetree_flatten {
	using type = typelist<>;
};

// recursive declaration when the first element is a list
template<class ...elems, class ...tail>
struct typetree_flatten<typelist<typelist<elems...>, tail...>> {
    using type = typename typetree_flatten<typelist<elems..., tail...>>::type;
};

// recursive declaration
template<class head, class ...tail>
struct typetree_flatten<typelist<head, tail...>> {
    using type = typename typelist_insert<head, typename typetree_flatten<typelist<tail...>>::type>::type;
};

//
// now let's test!
//

#include <cstdio>

void test_typelist() {
    using testlist = typelist<bool, int, float>;

    // output: index of bool = 0
    printf("index of bool = %u\n",
        typelist_index<bool, testlist>::value);

    // output: index of int = 1
    printf("index of int = %u\n",
        typelist_index<int, testlist>::value);

    // output: index of float = 2
    printf("index of float = %u\n",
        typelist_index<float, testlist>::value);

    // compilation error: type not found
    // printf("index of double = %u\n",
    //     typelist_index<double, testlist>::value);

    auto const bool_value = typelist_get<0u, testlist>::type(true);
    auto const int_value = typelist_get<1u, testlist>::type(42);
    auto const float_value = typelist_get<2u, testlist>::type(3.14159f);

    // compilation error: cast not allowed
    // auto const badtype_value = typelist_get<2u, testlist>::type("string");

    // compilation error: index out of range
    // auto const outofrange_value = typelist_get<3u, testlist>::type();

    // output: bool = true, int = 42, float = 3.141590
    printf("bool = %s, int = %d, float = %f\n",
        bool_value ? "true" : "false", int_value, float_value);
}

void test_typedict() {
    enum {
        key1,
        key2,
        key3,
        key4
    };

    using testdict = typelist<
        typedict_entry<key1, bool>,
        typedict_entry<key2, int>,
        typedict_entry<key3, float>
    >;

    // output: contains key1 = true
    printf("contains key1 = %s\n",
        typedict_contains<key1, testdict>::value ? "true" : "false");

    // output: contains key4 = false
    printf("contains key4 = %s\n",
        typedict_contains<key4, testdict>::value ? "true" : "false");

    // output: index of key1 = 0
    printf("index of key1 = %u\n",
        typedict_index<key1, testdict>::value);

    // output: index of key2 = 1
    printf("index of key2 = %u\n",
        typedict_index<key2, testdict>::value);

    // output: index of key3 = 2
    printf("index of key3 = %u\n",
        typedict_index<key3, testdict>::value);

    // compilation error: entry not found
    // printf("index of key4 = %u\n",
    //     typedict_index<key4, testdict>::value);

    auto const bool_value = typedict_get<key1, testdict>::type(true);
    auto const int_value = typedict_get<key2, testdict>::type(42);
    auto const float_value = typedict_get<key3, testdict>::type(3.14159f);

    // compilation error: cast not allowed
    // auto const badtype_value = typedict_get<key3, testdict>::type("string");

    // compilation error: entry not found
    // auto const outofrange_value = typedict_get<key4, testdict>::type();

    // output: bool = true, int = 42, float = 3.141590
    printf("bool = %s, int = %d, float = %f\n",
        bool_value ? "true" : "false", int_value, float_value);
}

void test_typetree() {
    enum {
        key1,
        key2,
        key3,
        key4
    };

    using testtree = typelist<
        typelist<
            typedict_entry<key1, bool>
        >,
        typelist<
            typelist<
                typedict_entry<key2, int>
            >
        >,
        typelist<
            typelist<
                typelist<
                    typedict_entry<key3, float>
                >,
                typedict_entry<key4, double>
            >
        >
    >;

    using flattened = typetree_flatten<testtree>::type;

    // output: index of key1 = 0
    printf("index of key1 = %u\n",
        typedict_index<key1, flattened>::value);

    // output: index of key2 = 1
    printf("index of key2 = %u\n",
        typedict_index<key2, flattened>::value);

    // output: index of key3 = 2
    printf("index of key3 = %u\n",
        typedict_index<key3, flattened>::value);

    // output: index of key4 = 3
    printf("index of key4 = %u\n",
        typedict_index<key4, flattened>::value);
}

int main () {
    printf("\n> typelist test:\n");
    test_typelist();

    printf("\n> typedict test:\n");
    test_typedict();

    printf("\n> typetree test:\n");
    test_typetree();

    return 0;
}