//Rewrite from https://github.com/dave-hagedorn/cpp-typelist
//Test successfully on GCC 10.1.0, but fail on VS 2009 16.11.3

#include <array>
#include <concepts>
#include <iostream>
#include <memory>
#include <string>
#include <type_traits>
#include <utility>
#include <variant>

namespace dhagedorn::types
{
  template<auto Predicate>
  concept is_complex_iter_predicate = requires { //两个模板参数：类型、序号。int, 0 都是占位符
    { Predicate.template operator()<int, std::size_t{ 0 }>() } -> std::convertible_to<bool>;
  };

  template<auto Predicate>
  concept is_simple_iter_predicate = requires { //只有一个模板参数：类型
    { Predicate.template operator()<int>() } -> std::convertible_to<bool>;
  };

  template<auto Predicate> //遍历类型，返回布尔值
  concept is_iter_predicate = is_simple_iter_predicate<Predicate> || is_complex_iter_predicate<Predicate>;

  template<typename ...Types>
  struct typelist;

  template<auto Predicate>
  concept is_complex_filter_predicate = requires { //最后一个参数是结果列表, accum 操作可能会用到
    { Predicate.template operator()<int, std::size_t{ 0 }, typelist<>>() } -> std::convertible_to<bool>;
  };

  template<auto Predicate>
  concept is_simple_filter_predicate = requires {
    { Predicate.template operator()<int>() } -> std::convertible_to<bool>;
  };

  template<auto Predicate>
  concept is_filter_predicate = is_simple_filter_predicate<Predicate> || is_complex_filter_predicate<Predicate>;

  template<auto Predicate>
  concept is_comp_predicate = requires {
    { Predicate.template operator() < int, int > () } -> std::convertible_to<bool>;
  };

  template<typename T>
  struct is_typelist_t : std::false_type {};

  template<typename ...Types>
  struct is_typelist_t<typelist<Types...>> : std::true_type {};

  template<typename T>
  concept is_typelist = is_typelist_t<T>::value;

  struct no_type {}; //empty/non-existent type. Ex: find no matching type

  template<template <typename T> class Trait>
  constexpr auto trait_predicate = []<typename Other, auto...>()
  {
    return Trait<Other>::value; //只使用首个类型。用例：trait_predicate<std::is_integral>
  };

  template<typename ...Types>
  struct typelist
  {
  private:
    template<typename ...Other>
    struct holder {};

    template<auto Predicate, typename T, auto I> //调用的地方有 requires，这里可以不用
    constexpr static auto invoke_iter_predicate()
    {
      if constexpr (is_simple_iter_predicate<Predicate>)
        return Predicate.template operator()<T>();
      else
        return Predicate.template operator()<T, I>();
    }

    template<auto Predicate, typename T, auto I, is_typelist List>
    constexpr static auto invoke_filter_predicate()
    {
      if constexpr (is_simple_filter_predicate<Predicate>)
        return Predicate.template operator()<T>();
      else
        return Predicate.template operator()<T, I, List>();
    }

    template<auto Predicate, auto I, is_typelist List>
    constexpr static List* filter_impl() { return nullptr; } //没有类型了，返回空指针

    template<auto Predicate, auto I, is_typelist List, typename First, typename ...Rest>
    static auto* filter_impl() //这里无法加 constexpr，因为有递归调用无法完成类型推导
    {
      constexpr auto pass = invoke_filter_predicate<Predicate, First, I, List>();
      if constexpr (pass) { //首类型符合
        using NewList = typename List::template push_back<First>; //首类型加入结果 List
        return filter_impl<Predicate, I + 1, NewList, Rest...>();
      } else
        return filter_impl<Predicate, I + 1, List, Rest...>(); //否则直接遍历下一个
    };

    template<auto Predicate, auto I>
    constexpr static no_type* find_if_impl() { return nullptr; }

    template<auto Predicate, auto I, typename First, typename ...Rest>
    static auto* find_if_impl()
    {
      constexpr auto pass = invoke_iter_predicate<Predicate, First, I>;
      if constexpr (pass)
        return static_cast<First*>(nullptr); //返回类型指针，实际值是空的就可以
      else
        return find_if_impl<Predicate, I + 1, Rest...>(); //首类型不符合，继续往向找
    }

    template<auto Predicate, auto ...Indices>
    static constexpr auto transform_v_impl(std::index_sequence<Indices...>)
    {
      std::array result { invoke_iter_predicate<Predicate, Types, Indices>()... };
      return result;
    }

    template<auto Predicate, auto ...Indices>
    static constexpr auto* transform_impl(std::index_sequence<Indices...>)
    {
      return static_cast<typelist<decltype(invoke_iter_predicate<Predicate, Types, Indices>())...>*>(nullptr);
    }

    template<auto Predicate, bool NoSwap, typename First, typename Second, typename ...Rest, typename ...List>
    static constexpr auto* sortImpl2(holder<List...>)
    {
      constexpr bool lessThan = Predicate.template operator()<First, Second>();
      constexpr bool Equal = !Predicate.template operator()<First, Second>() && !Predicate.template operator()<Second, First>();
      constexpr bool lessThanOrEqual = lessThan || Equal;
      constexpr bool donePass = sizeof...(Rest) == 0;
      if constexpr (donePass) {
        if constexpr (lessThanOrEqual) {
          if constexpr (NoSwap)
            return static_cast<typelist<List..., First, Second>*>(nullptr);
          else
            return sortImpl2<Predicate, true, List..., First, Second>(holder<>{});
        } else {
          if constexpr (NoSwap)
            return static_cast<typelist<List..., Second, First>*>(nullptr);
          else
            return sortImpl2<Predicate, true, List..., Second, First>(holder<>{});
        }
      } else if constexpr (lessThanOrEqual)
        return sortImpl2<Predicate, NoSwap && true, Second, Rest...>(holder<List..., First>{});
      else
        return sortImpl2<Predicate, NoSwap && false, First, Rest...>(holder<List..., Second>{});
    }

    template<template <typename ...> class From, typename ...Other>
    constexpr static auto* fromImpl(From<Other...>*)
    {
      return static_cast<typelist<Other...>*>(nullptr);
    }

  public:

    constexpr static std::size_t size = sizeof...(Types);

    constexpr static auto indices = std::make_index_sequence<size>();

    template<auto Predicate> requires is_iter_predicate<Predicate>
    constexpr static bool any_of = []<auto ...I>(std::index_sequence<I...>)
    {
      return (invoke_iter_predicate<Predicate, Types, I>() || ...); //遍历类型求一真
    }(indices);

    template<auto Predicate> requires is_iter_predicate<Predicate>
    constexpr static bool all_of = []<auto ...I>(std::index_sequence<I...>)
    {
      return (invoke_iter_predicate<Predicate, Types, I>() && ...); //遍历求全真
    }(indices);

    template<auto Predicate> requires is_iter_predicate<Predicate>
    constexpr static bool none_of = !any_of<Predicate>;

    template<typename Other>
    constexpr static auto contains_one = ((std::is_same_v<Other, Types>) || ...);

    template<typename ...Other>
    constexpr static auto contains = ((contains_one<Other>)&& ...);

    template<typename ...Other>
    using push_back = typelist<Types..., Other...>;

    template<typename ...Other>
    using push_front = typelist<Other..., Types...>;

    template<auto Predicate> requires is_filter_predicate<Predicate> //remove_ref 确保类型不是引用
    using filter = std::remove_reference_t<decltype(*filter_impl<Predicate, 0, typelist<>, Types...>())>;

    using set = filter<[]<typename IT, auto I, is_typelist List>(){ return !List::template contains<IT>; }>;

    template<std::size_t From, std::size_t To> requires (From < To && To <= size)
    using slice = std::remove_reference_t<decltype(*filter_impl<
      []<typename TYPE, auto I, typename List>(){ return From <= I && I < To; }, 0, typelist<>, Types...>())>;

    template<auto Predicate> requires is_iter_predicate<Predicate>
    using find_if = std::remove_pointer_t<decltype(find_if_impl<Predicate, 0, Types...>())>;

    template<std::size_t Index> requires (Index < size)
    using at = std::remove_reference_t<decltype(*find_if_impl<[]<typename T, auto I>(){ return I == Index; }, 0, Types...>())>;

    template<auto Predicate> requires is_iter_predicate<Predicate>
    static constexpr auto transform_v = transform_v_impl<Predicate>(indices);

    template<auto Predicate> requires is_iter_predicate<Predicate>
    using transform_with = std::remove_reference_t<decltype(*transform_impl<Predicate>(indices))>;

    template<template <typename> class From>
    using transform = typelist<From<Types>...>;

    template<auto Predicate = []<typename A, typename B>(){ return sizeof(A) < sizeof(B); }>
    requires is_comp_predicate<Predicate>
    using sort = std::remove_reference_t<decltype(*sortImpl2<Predicate, false, Types...>(holder<>{}))>;

    template<template <typename ...> class As>
    using as = As<Types...>;

    template<typename Type>
    using from = std::remove_reference_t<decltype(*fromImpl(static_cast<Type*>(nullptr)))>;
  }; //class typelist
} //namespace

namespace types = dhagedorn::types;

int main()
{
  using list = types::typelist<double, float, int, char, int, char, float, double>;
  std::cout << "size: " << list::size << std::endl;
  constexpr auto has_double = list::any_of<[]<typename T>(){ return std::is_same_v<T, double>; }>;
  std::cout << "has_double: " << std::boolalpha << has_double << std::endl;
  constexpr auto is_mathy = list::any_of<[]<typename T>(){ return std::is_integral_v<T> || std::is_floating_point_v<T>; }>;
  std::cout << "is_mathy: " << is_mathy << std::endl;
  constexpr auto is_not_stringy = list::none_of<[]<typename T>(){ return std::is_same_v<T, std::string>; }>;
  std::cout << "is_not_stringy: " << is_not_stringy << std::endl;
  constexpr auto has_int = list::contains<int>;
  constexpr auto has_int2 = list::any_of<types::trait_predicate<std::is_integral>>;
  std::cout << "has_int: " << has_int << "， has_int2: " << has_int2 << std::endl;
  using with_string = list::push_back<std::string>; //..., std::string
  using with_void = list::push_front<void>; //void, ...
  using set = list::set; //double, float, int, char
  using no_floats = list::filter<[]<typename T>(){ return !std::is_floating_point_v<T>; }>;
  using no_floats2 = list::filter<types::trait_predicate<std::is_integral>>;
  std::cout << "no_float size: " << no_floats::size << ", " << no_floats2::size << std::endl; //4
  constexpr auto all_integeral = no_floats::all_of<types::trait_predicate<std::is_integral>>;
  std::cout << "all_integeral: " << all_integeral << std::endl;

  //using list = types::typelist<double, float, int, char, int, char, float, double>;
  using odds = list::filter<[]<typename T, auto I, types::is_typelist list>(){ return I % 2 == 1; }>;
  using sliced = list::slice<0, 3>;
  std::cout << "sliced size: " << sliced::size << std::endl; //3
  using first_integral = list::find_if<[]<typename T>(){ return std::is_integral_v<T>; }>;
  std::cout << "first_integral: " << typeid(first_integral).name() << std::endl; //TODO：这里一直不正确
  using first_type = list::at<0>;
  std::cout << "first_type: " << typeid(first_type).name() << std::endl; //TODO：这里一直不正确

  constexpr auto sizes = list::transform_v<[]<typename T>(){ return sizeof(T); }>;
  std::cout << "sizes: " << typeid(sizes).name() << std::endl; //TODO：这里一直不正确
  constexpr auto indices = list::transform_v<[]<typename T, auto I>(){ return I; }>; //array: 0 ~ 7
  std::cout << "indices: " << typeid(indices).name() << std::endl; //TODO：这里一直不正确

  using pointy = list::transform_with<[]<typename T>() -> T* { return nullptr; }>;
  std::cout << "pointy: " << typeid(pointy).name() << std::endl; //TODO：这里一直不正确
  using safe_pointy = list::transform<std::shared_ptr>; //所有类型用 shared_ptr 包装起来
  std::cout << "safe_pointy: " << typeid(safe_pointy).name() << std::endl; //TODO：这里一直不正确
  using sorted = list::sort<>;
  std::cout << "sorted: " << typeid(sorted).name() << std::endl; //TODO：这里一直不正确
  using sorted_backwards = list::sort<[]<typename A, typename B>(){ return sizeof(B) < sizeof(A); }>;
  std::cout << "sorted_backwards: " << typeid(sorted_backwards).name() << std::endl; //TODO：这里一直不正确

  using variant = list::as<std::variant>;
  std::cout << "variant: " << typeid(variant).name() << std::endl; //TODO：这里一直不正确
  using from_variant = list::from<variant>;
  std::cout << "from_variant: " << typeid(from_variant).name() << std::endl; //TODO：这里一直不正确

  return 0;
}