Eigen/src/Core/util/Meta.h

// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2008-2015 Gael Guennebaud <gael.guennebaud@inria.fr>
// Copyright (C) 2006-2008 Benoit Jacob <jacob.benoit.1@gmail.com>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

#ifndef EIGEN_META_H
#define EIGEN_META_H

#include "../InternalHeaderCheck.h"

#if defined(EIGEN_GPU_COMPILE_PHASE)

 #include <cfloat>

 #if defined(EIGEN_CUDA_ARCH)
  #include <math_constants.h>
 #endif

 #if defined(EIGEN_HIP_DEVICE_COMPILE)
  #include "Eigen/src/Core/arch/HIP/hcc/math_constants.h"
  #endif

#endif

#include "EmulateArray.h"

// Define portable (u)int{32,64} types
#include <cstdint>

namespace Eigen {
namespace numext {
typedef std::uint8_t  uint8_t;
typedef std::int8_t   int8_t;
typedef std::uint16_t uint16_t;
typedef std::int16_t  int16_t;
typedef std::uint32_t uint32_t;
typedef std::int32_t  int32_t;
typedef std::uint64_t uint64_t;
typedef std::int64_t  int64_t;

template <size_t Size>
struct get_integer_by_size {
    typedef void signed_type;
    typedef void unsigned_type;
};
template <>
struct get_integer_by_size<1> {
    typedef int8_t signed_type;
    typedef uint8_t unsigned_type;
};
template <>
struct get_integer_by_size<2> {
    typedef int16_t signed_type;
    typedef uint16_t unsigned_type;
};
template <>
struct get_integer_by_size<4> {
    typedef int32_t signed_type;
    typedef uint32_t unsigned_type;
};
template <>
struct get_integer_by_size<8> {
    typedef int64_t signed_type;
    typedef uint64_t unsigned_type;
};
}
}

namespace Eigen {

typedef EIGEN_DEFAULT_DENSE_INDEX_TYPE DenseIndex;

/**
 * \brief The Index type as used for the API.
 * \details To change this, \c \#define the preprocessor symbol \c EIGEN_DEFAULT_DENSE_INDEX_TYPE.
 * \sa \blank \ref TopicPreprocessorDirectives, StorageIndex.
 */

typedef EIGEN_DEFAULT_DENSE_INDEX_TYPE Index;

namespace internal {

/** \internal
  * \file Meta.h
  * This file contains generic metaprogramming classes which are not specifically related to Eigen.
  * \note In case you wonder, yes we're aware that Boost already provides all these features,
  * we however don't want to add a dependency to Boost.
  */

struct true_type {  enum { value = 1 }; };
struct false_type { enum { value = 0 }; };

template<bool Condition>
struct bool_constant;

template<>
struct bool_constant<true> : true_type {};

template<>
struct bool_constant<false> : false_type {};

// Third-party libraries rely on these.
using std::conditional;
using std::remove_reference;
using std::remove_pointer;
using std::remove_const;

template<typename T> struct remove_all { typedef T type; };
template<typename T> struct remove_all<const T>   { typedef typename remove_all<T>::type type; };
template<typename T> struct remove_all<T const&>  { typedef typename remove_all<T>::type type; };
template<typename T> struct remove_all<T&>        { typedef typename remove_all<T>::type type; };
template<typename T> struct remove_all<T const*>  { typedef typename remove_all<T>::type type; };
template<typename T> struct remove_all<T*>        { typedef typename remove_all<T>::type type; };

template<typename T>
using remove_all_t = typename remove_all<T>::type;

template<typename T> struct is_arithmetic      { enum { value = false }; };
template<> struct is_arithmetic<float>         { enum { value = true }; };
template<> struct is_arithmetic<double>        { enum { value = true }; };
// GPU devices treat `long double` as `double`.
#ifndef EIGEN_GPU_COMPILE_PHASE
template<> struct is_arithmetic<long double>   { enum { value = true }; };
#endif
template<> struct is_arithmetic<bool>          { enum { value = true }; };
template<> struct is_arithmetic<char>          { enum { value = true }; };
template<> struct is_arithmetic<signed char>   { enum { value = true }; };
template<> struct is_arithmetic<unsigned char> { enum { value = true }; };
template<> struct is_arithmetic<signed short>  { enum { value = true }; };
template<> struct is_arithmetic<unsigned short>{ enum { value = true }; };
template<> struct is_arithmetic<signed int>    { enum { value = true }; };
template<> struct is_arithmetic<unsigned int>  { enum { value = true }; };
template<> struct is_arithmetic<signed long>   { enum { value = true }; };
template<> struct is_arithmetic<unsigned long> { enum { value = true }; };

template<typename T, typename U> struct is_same { enum { value = 0 }; };
template<typename T> struct is_same<T,T> { enum { value = 1 }; };

template< class T >
struct is_void : is_same<void, std::remove_const_t<T>> {};

/** \internal
  * Implementation of std::void_t for SFINAE.
  *
  * Pre C++17:
  * Custom implementation.
  *
  * Post C++17: Uses std::void_t
  */
#if EIGEN_COMP_CXXVER >= 17
using std::void_t;
#else
template<typename...>
using void_t = void;
#endif

template<> struct is_arithmetic<signed long long>   { enum { value = true }; };
template<> struct is_arithmetic<unsigned long long> { enum { value = true }; };
using std::is_integral;

using std::make_unsigned;

template <typename T> struct is_const { enum { value = 0 }; };
template <typename T> struct is_const<T const> { enum { value = 1 }; };

template<typename T> struct add_const_on_value_type            { typedef const T type;  };
template<typename T> struct add_const_on_value_type<T&>        { typedef T const& type; };
template<typename T> struct add_const_on_value_type<T*>        { typedef T const* type; };
template<typename T> struct add_const_on_value_type<T* const>  { typedef T const* const type; };
template<typename T> struct add_const_on_value_type<T const* const>  { typedef T const* const type; };

template<typename T>
using add_const_on_value_type_t = typename add_const_on_value_type<T>::type;

using std::is_convertible;

/** \internal
  * A base class do disable default copy ctor and copy assignment operator.
  */
class noncopyable
{
  EIGEN_DEVICE_FUNC noncopyable(const noncopyable&);
  EIGEN_DEVICE_FUNC const noncopyable& operator=(const noncopyable&);
protected:
  EIGEN_DEVICE_FUNC noncopyable() {}
  EIGEN_DEVICE_FUNC ~noncopyable() {}
};

/** \internal
  * Provides access to the number of elements in the object of as a compile-time constant expression.
  * It "returns" Eigen::Dynamic if the size cannot be resolved at compile-time (default).
  *
  * Similar to std::tuple_size, but more general.
  *
  * It currently supports:
  *  - any types T defining T::SizeAtCompileTime
  *  - plain C arrays as T[N]
  *  - std::array (c++11)
  *  - some internal types such as SingleRange and AllRange
  *
  * The second template parameter eases SFINAE-based specializations.
  */
template<typename T, typename EnableIf = void> struct array_size {
  enum { value = Dynamic };
};

template<typename T> struct array_size<T, std::enable_if_t<((T::SizeAtCompileTime&0)==0)>> {
  enum { value = T::SizeAtCompileTime };
};

template<typename T, int N> struct array_size<const T (&)[N]> {
  enum { value = N };
};
template<typename T, int N> struct array_size<T (&)[N]> {
  enum { value = N };
};

template<typename T, std::size_t N> struct array_size<const std::array<T,N> > {
  enum { value = N };
};
template<typename T, std::size_t N> struct array_size<std::array<T,N> > {
  enum { value = N };
};


/** \internal
  * Analogue of the std::ssize free function.
  * It returns the signed size of the container or view \a x of type \c T
  *
  * It currently supports:
  *  - any types T defining a member T::size() const
  *  - plain C arrays as T[N]
  *
  * For C++20, this function just forwards to `std::ssize`, or any ADL discoverable `ssize` function.
  */
#if EIGEN_COMP_CXXVER < 20 || EIGEN_GNUC_STRICT_LESS_THAN(10,0,0)
template <typename T>
EIGEN_CONSTEXPR auto index_list_size(const T& x) {
  using R = std::common_type_t<std::ptrdiff_t, std::make_signed_t<decltype(x.size())>>;
  return static_cast<R>(x.size());
}

template<typename T, std::ptrdiff_t N>
EIGEN_CONSTEXPR std::ptrdiff_t index_list_size(const T (&)[N]) { return N; }
#else
template <typename T>
EIGEN_CONSTEXPR auto index_list_size(T&& x) {
  using std::ssize;
  return ssize(std::forward<T>(x));
}
#endif // EIGEN_COMP_CXXVER

/** \internal
  * Convenient struct to get the result type of a nullary, unary, binary, or
  * ternary functor.
  *
  * Pre C++17:
  * This uses std::result_of. However, note the `type` member removes
  * const and converts references/pointers to their corresponding value type.
  *
  * Post C++17: Uses std::invoke_result
  */
#if EIGEN_HAS_STD_INVOKE_RESULT
template<typename T> struct result_of;

template<typename F, typename... ArgTypes>
struct result_of<F(ArgTypes...)> {
  typedef typename std::invoke_result<F, ArgTypes...>::type type1;
  typedef remove_all_t<type1> type;
};

template<typename F, typename... ArgTypes>
struct invoke_result {
  typedef typename std::invoke_result<F, ArgTypes...>::type type1;
  typedef remove_all_t<type1> type;
};
#else
template<typename T> struct result_of {
  typedef typename std::result_of<T>::type type1;
  typedef remove_all_t<type1> type;
};

template<typename F, typename... ArgTypes>
struct invoke_result {
    typedef typename result_of<F(ArgTypes...)>::type type1;
    typedef remove_all_t<type1> type;
};
#endif

// Reduces a sequence of bools to true if all are true, false otherwise.
template<bool... values>
using reduce_all = std::is_same<std::integer_sequence<bool, values..., true>,
    std::integer_sequence<bool, true, values...> >;

// Reduces a sequence of bools to true if any are true, false if all false.
template<bool... values>
using reduce_any = std::integral_constant<bool,
    !std::is_same<std::integer_sequence<bool, values..., false>, std::integer_sequence<bool, false, values...> >::value>;

struct meta_yes { char a[1]; };
struct meta_no  { char a[2]; };

// Check whether T::ReturnType does exist
template <typename T>
struct has_ReturnType
{
  template <typename C> static meta_yes testFunctor(C const *, typename C::ReturnType const * = 0);
  template <typename C> static meta_no  testFunctor(...);

  enum { value = sizeof(testFunctor<T>(static_cast<T*>(0))) == sizeof(meta_yes) };
};

template<typename T> const T* return_ptr();

template <typename T, typename IndexType=Index>
struct has_nullary_operator
{
  template <typename C> static meta_yes testFunctor(C const *,std::enable_if_t<(sizeof(return_ptr<C>()->operator()())>0)> * = 0);
  static meta_no testFunctor(...);

  enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
};

template <typename T, typename IndexType=Index>
struct has_unary_operator
{
  template <typename C> static meta_yes testFunctor(C const *,std::enable_if_t<(sizeof(return_ptr<C>()->operator()(IndexType(0)))>0)> * = 0);
  static meta_no testFunctor(...);

  enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
};

template <typename T, typename IndexType=Index>
struct has_binary_operator
{
  template <typename C> static meta_yes testFunctor(C const *,std::enable_if_t<(sizeof(return_ptr<C>()->operator()(IndexType(0),IndexType(0)))>0)> * = 0);
  static meta_no testFunctor(...);

  enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
};

/** \internal In short, it computes int(sqrt(\a Y)) with \a Y an integer.
  * Usage example: \code meta_sqrt<1023>::ret \endcode
  */
template<int Y,
         int InfX = 0,
         int SupX = ((Y==1) ? 1 : Y/2),
         bool Done = ((SupX - InfX) <= 1 || ((SupX * SupX <= Y) && ((SupX + 1) * (SupX + 1) > Y)))>
class meta_sqrt
{
    enum {
      MidX = (InfX+SupX)/2,
      TakeInf = MidX*MidX > Y ? 1 : 0,
      NewInf = int(TakeInf) ? InfX : int(MidX),
      NewSup = int(TakeInf) ? int(MidX) : SupX
    };
  public:
    enum { ret = meta_sqrt<Y,NewInf,NewSup>::ret };
};

template<int Y, int InfX, int SupX>
class meta_sqrt<Y, InfX, SupX, true> { public:  enum { ret = (SupX*SupX <= Y) ? SupX : InfX }; };


/** \internal Computes the least common multiple of two positive integer A and B
  * at compile-time. 
  */
template<int A, int B, int K=1, bool Done = ((A*K)%B)==0, bool Big=(A>=B)>
struct meta_least_common_multiple
{
  enum { ret = meta_least_common_multiple<A,B,K+1>::ret };
};
template<int A, int B, int K, bool Done>
struct meta_least_common_multiple<A,B,K,Done,false>
{
  enum { ret = meta_least_common_multiple<B,A,K>::ret };
};
template<int A, int B, int K>
struct meta_least_common_multiple<A,B,K,true,true>
{
  enum { ret = A*K };
};


/** \internal determines whether the product of two numeric types is allowed and what the return type is */
template<typename T, typename U> struct scalar_product_traits
{
  enum { Defined = 0 };
};

// FIXME quick workaround around current limitation of result_of
// template<typename Scalar, typename ArgType0, typename ArgType1>
// struct result_of<scalar_product_op<Scalar>(ArgType0,ArgType1)> {
// typedef typename scalar_product_traits<remove_all_t<ArgType0>, remove_all_t<ArgType1>>::ReturnType type;
// };

/** \internal Obtains a POD type suitable to use as storage for an object of a size
  * of at most Len bytes, aligned as specified by \c Align.
  */
template<unsigned Len, unsigned Align>
struct aligned_storage {
  struct type {
    EIGEN_ALIGN_TO_BOUNDARY(Align) unsigned char data[Len];
  };
};

} // end namespace internal

template<typename T> struct NumTraits;

namespace numext {

#if defined(EIGEN_GPU_COMPILE_PHASE)
template<typename T> EIGEN_DEVICE_FUNC   void swap(T &a, T &b) { T tmp = b; b = a; a = tmp; }
#else
template<typename T> EIGEN_STRONG_INLINE void swap(T &a, T &b) { std::swap(a,b); }
#endif

using std::numeric_limits;

// Integer division with rounding up.
// T is assumed to be an integer type with a>=0, and b>0
template<typename T>
EIGEN_DEVICE_FUNC
T div_ceil(const T &a, const T &b)
{
  return (a+b-1) / b;
}

// The aim of the following functions is to bypass -Wfloat-equal warnings
// when we really want a strict equality comparison on floating points.
template<typename X, typename Y> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool equal_strict(const X& x,const Y& y) { return x == y; }

#if !defined(EIGEN_GPU_COMPILE_PHASE) || (!defined(EIGEN_CUDA_ARCH) && defined(EIGEN_CONSTEXPR_ARE_DEVICE_FUNC))
template<> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool equal_strict(const float& x,const float& y) { return std::equal_to<float>()(x,y); }

template<> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool equal_strict(const double& x,const double& y) { return std::equal_to<double>()(x,y); }
#endif

/**
 * \internal Performs an exact comparison of x to zero, e.g. to decide whether a term can be ignored.
 * Use this to to bypass -Wfloat-equal warnings when exact zero is what needs to be tested.
*/
template<typename X> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool is_exactly_zero(const X& x) { return equal_strict(x, typename NumTraits<X>::Literal{0}); }

/**
 * \internal Performs an exact comparison of x to one, e.g. to decide whether a factor needs to be multiplied.
 * Use this to to bypass -Wfloat-equal warnings when exact one is what needs to be tested.
*/
template<typename X> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool is_exactly_one(const X& x) { return equal_strict(x, typename NumTraits<X>::Literal{1}); }

template<typename X, typename Y> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool not_equal_strict(const X& x,const Y& y) { return x != y; }

#if !defined(EIGEN_GPU_COMPILE_PHASE) || (!defined(EIGEN_CUDA_ARCH) && defined(EIGEN_CONSTEXPR_ARE_DEVICE_FUNC))
template<> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool not_equal_strict(const float& x,const float& y) { return std::not_equal_to<float>()(x,y); }

template<> EIGEN_STRONG_INLINE EIGEN_DEVICE_FUNC
bool not_equal_strict(const double& x,const double& y) { return std::not_equal_to<double>()(x,y); }
#endif

} // end namespace numext

namespace internal {

template<typename Scalar>
struct is_identically_zero_impl {
  static inline bool run(const Scalar& s) {
    return numext::is_exactly_zero(s);
  }
};

template<typename Scalar> EIGEN_STRONG_INLINE
bool is_identically_zero(const Scalar& s) { return is_identically_zero_impl<Scalar>::run(s); }

/// \internal Returns true if its argument is of integer or enum type.
/// FIXME this has the same purpose as `is_valid_index_type` in XprHelper.h
template<typename A>
constexpr bool is_int_or_enum_v = std::is_enum<A>::value || std::is_integral<A>::value;

/// \internal Gets the minimum of two values which may be integers or enums
template<typename A, typename B>
inline constexpr int plain_enum_min(A a, B b) {
  static_assert(is_int_or_enum_v<A>, "Argument a must be an integer or enum");
  static_assert(is_int_or_enum_v<B>, "Argument b must be an integer or enum");
  return ((int) a <= (int) b) ? (int) a : (int) b;
}

/// \internal Gets the maximum of two values which may be integers or enums
template<typename A, typename B>
inline constexpr int plain_enum_max(A a, B b) {
  static_assert(is_int_or_enum_v<A>, "Argument a must be an integer or enum");
  static_assert(is_int_or_enum_v<B>, "Argument b must be an integer or enum");
  return ((int) a >= (int) b) ? (int) a : (int) b;
}

/**
 * \internal
 *  `min_size_prefer_dynamic` gives the min between compile-time sizes. 0 has absolute priority, followed by 1,
 *  followed by Dynamic, followed by other finite values. The reason for giving Dynamic the priority over
 *  finite values is that min(3, Dynamic) should be Dynamic, since that could be anything between 0 and 3.
 */
template<typename A, typename B>
inline constexpr int min_size_prefer_dynamic(A a, B b) {
  static_assert(is_int_or_enum_v<A>, "Argument a must be an integer or enum");
  static_assert(is_int_or_enum_v<B>, "Argument b must be an integer or enum");
  if ((int) a == 0 || (int) b == 0) return 0;
  if ((int) a == 1 || (int) b == 1) return 1;
  if ((int) a == Dynamic || (int) b == Dynamic) return Dynamic;
  return plain_enum_min(a, b);
}

/**
 * \internal
 *  min_size_prefer_fixed is a variant of `min_size_prefer_dynamic` comparing MaxSizes. The difference is that finite values
 *  now have priority over Dynamic, so that min(3, Dynamic) gives 3. Indeed, whatever the actual value is
 *  (between 0 and 3), it is not more than 3.
 */
template<typename A, typename B>
inline constexpr int min_size_prefer_fixed(A a, B b) {
  static_assert(is_int_or_enum_v<A>, "Argument a must be an integer or enum");
  static_assert(is_int_or_enum_v<B>, "Argument b must be an integer or enum");
  if ((int) a == 0 || (int) b == 0) return 0;
  if ((int) a == 1 || (int) b == 1) return 1;
  if ((int) a == Dynamic && (int) b == Dynamic) return Dynamic;
  if ((int) a == Dynamic) return (int) b;
  if ((int) b == Dynamic) return (int) a;
  return plain_enum_min(a, b);
}

/// \internal see `min_size_prefer_fixed`. No need for a separate variant for MaxSizes here.
template<typename A, typename B>
inline constexpr int max_size_prefer_dynamic(A a, B b) {
  static_assert(is_int_or_enum_v<A>, "Argument a must be an integer or enum");
  static_assert(is_int_or_enum_v<B>, "Argument b must be an integer or enum");
  if ((int) a == Dynamic || (int) b == Dynamic) return Dynamic;
  return plain_enum_max(a, b);
}

/// \internal Calculate logical XOR at compile time
inline constexpr bool logical_xor(bool a, bool b) {
  return a != b;
}

/// \internal Calculate logical IMPLIES at compile time
inline constexpr bool check_implication(bool a, bool b) {
  return !a || b;
}

/// \internal Provide fallback for std::is_constant_evaluated for pre-C++20.
#if EIGEN_COMP_CXXVER >= 20
using std::is_constant_evaluated;
#else
constexpr bool is_constant_evaluated() { return false; }
#endif

template<typename... tt>
struct type_list { constexpr static int count = sizeof...(tt); };

template<typename t, typename... tt>
struct type_list<t, tt...> { constexpr static int count = sizeof...(tt) + 1; typedef t first_type; };

template<typename T, T... nn>
struct numeric_list { constexpr static std::size_t count = sizeof...(nn); };

template<typename T, T n, T... nn>
struct numeric_list<T, n, nn...> { static constexpr std::size_t count = sizeof...(nn) + 1;
                                   static constexpr T first_value = n; };

#ifndef EIGEN_PARSED_BY_DOXYGEN
/* numeric list constructors
 *
 * equivalencies:
 *     constructor                                              result
 *     typename gen_numeric_list<int, 5>::type                  numeric_list<int, 0,1,2,3,4>
 *     typename gen_numeric_list_reversed<int, 5>::type         numeric_list<int, 4,3,2,1,0>
 *     typename gen_numeric_list_swapped_pair<int, 5,1,2>::type numeric_list<int, 0,2,1,3,4>
 *     typename gen_numeric_list_repeated<int, 0, 5>::type      numeric_list<int, 0,0,0,0,0>
 */

template<typename T, std::size_t n, T start = 0, T... ii> struct gen_numeric_list                     : gen_numeric_list<T, n-1, start, start + n-1, ii...> {};
template<typename T, T start, T... ii>                    struct gen_numeric_list<T, 0, start, ii...> { typedef numeric_list<T, ii...> type; };

template<typename T, std::size_t n, T start = 0, T... ii> struct gen_numeric_list_reversed                     : gen_numeric_list_reversed<T, n-1, start, ii..., start + n-1> {};
template<typename T, T start, T... ii>                    struct gen_numeric_list_reversed<T, 0, start, ii...> { typedef numeric_list<T, ii...> type; };

template<typename T, std::size_t n, T a, T b, T start = 0, T... ii> struct gen_numeric_list_swapped_pair                           : gen_numeric_list_swapped_pair<T, n-1, a, b, start, (start + n-1) == a ? b : ((start + n-1) == b ? a : (start + n-1)), ii...> {};
template<typename T, T a, T b, T start, T... ii>                    struct gen_numeric_list_swapped_pair<T, 0, a, b, start, ii...> { typedef numeric_list<T, ii...> type; };

template<typename T, std::size_t n, T V, T... nn> struct gen_numeric_list_repeated                 : gen_numeric_list_repeated<T, n-1, V, V, nn...> {};
template<typename T, T V, T... nn>                struct gen_numeric_list_repeated<T, 0, V, nn...> { typedef numeric_list<T, nn...> type; };

/* list manipulation: concatenate */

template<class a, class b> struct concat;

template<typename... as, typename... bs> struct concat<type_list<as...>,       type_list<bs...>>        { typedef type_list<as..., bs...> type; };
template<typename T, T... as, T... bs>   struct concat<numeric_list<T, as...>, numeric_list<T, bs...> > { typedef numeric_list<T, as..., bs...> type; };

template<typename... p> struct mconcat;
template<typename a>                             struct mconcat<a>           { typedef a type; };
template<typename a, typename b>                 struct mconcat<a, b>        : concat<a, b> {};
template<typename a, typename b, typename... cs> struct mconcat<a, b, cs...> : concat<a, typename mconcat<b, cs...>::type> {};

/* list manipulation: extract slices */

template<int n, typename x> struct take;
template<int n, typename a, typename... as> struct take<n, type_list<a, as...>> : concat<type_list<a>, typename take<n-1, type_list<as...>>::type> {};
template<int n>                             struct take<n, type_list<>>         { typedef type_list<> type; };
template<typename a, typename... as>        struct take<0, type_list<a, as...>> { typedef type_list<> type; };
template<>                                  struct take<0, type_list<>>         { typedef type_list<> type; };

template<typename T, int n, T a, T... as> struct take<n, numeric_list<T, a, as...>> : concat<numeric_list<T, a>, typename take<n-1, numeric_list<T, as...>>::type> {};
// XXX The following breaks in gcc-11, and is invalid anyways.
// template<typename T, int n>               struct take<n, numeric_list<T>>           { typedef numeric_list<T> type; };
template<typename T, T a, T... as>        struct take<0, numeric_list<T, a, as...>> { typedef numeric_list<T> type; };
template<typename T>                      struct take<0, numeric_list<T>>           { typedef numeric_list<T> type; };

template<typename T, int n, T... ii>      struct h_skip_helper_numeric;
template<typename T, int n, T i, T... ii> struct h_skip_helper_numeric<T, n, i, ii...> : h_skip_helper_numeric<T, n-1, ii...> {};
template<typename T, T i, T... ii>        struct h_skip_helper_numeric<T, 0, i, ii...> { typedef numeric_list<T, i, ii...> type; };
template<typename T, int n>               struct h_skip_helper_numeric<T, n>           { typedef numeric_list<T> type; };
template<typename T>                      struct h_skip_helper_numeric<T, 0>           { typedef numeric_list<T> type; };

template<int n, typename... tt>             struct h_skip_helper_type;
template<int n, typename t, typename... tt> struct h_skip_helper_type<n, t, tt...> : h_skip_helper_type<n-1, tt...> {};
template<typename t, typename... tt>        struct h_skip_helper_type<0, t, tt...> { typedef type_list<t, tt...> type; };
template<int n>                             struct h_skip_helper_type<n>           { typedef type_list<> type; };
template<>                                  struct h_skip_helper_type<0>           { typedef type_list<> type; };
#endif //not EIGEN_PARSED_BY_DOXYGEN

template<int n>
struct h_skip {
  template<typename T, T... ii>
  constexpr static EIGEN_STRONG_INLINE typename h_skip_helper_numeric<T, n, ii...>::type helper(numeric_list<T, ii...>) { return typename h_skip_helper_numeric<T, n, ii...>::type(); }
  template<typename... tt>
  constexpr static EIGEN_STRONG_INLINE typename h_skip_helper_type<n, tt...>::type helper(type_list<tt...>) { return typename h_skip_helper_type<n, tt...>::type(); }
};

template<int n, typename a> struct skip { typedef decltype(h_skip<n>::helper(a())) type; };

template<int start, int count, typename a> struct slice : take<count, typename skip<start, a>::type> {};

/* list manipulation: retrieve single element from list */

template<int n, typename x> struct get;

template<int n, typename a, typename... as>               struct get<n, type_list<a, as...>>   : get<n-1, type_list<as...>> {};
template<typename a, typename... as>                      struct get<0, type_list<a, as...>>   { typedef a type; };

template<typename T, int n, T a, T... as>                        struct get<n, numeric_list<T, a, as...>>   : get<n-1, numeric_list<T, as...>> {};
template<typename T, T a, T... as>                               struct get<0, numeric_list<T, a, as...>>   { constexpr static T value = a; };

template<std::size_t n, typename T, T a, T... as> constexpr T       array_get(const numeric_list<T, a, as...>&) {
   return get<(int)n, numeric_list<T, a, as...>>::value;
}

/* always get type, regardless of dummy; good for parameter pack expansion */

template<typename T, T dummy, typename t> struct id_numeric  { typedef t type; };
template<typename dummy, typename t>      struct id_type     { typedef t type; };

/* equality checking, flagged version */

template<typename a, typename b> struct is_same_gf : is_same<a, b> { constexpr static int global_flags = 0; };

/* apply_op to list */

template<
  bool from_left, // false
  template<typename, typename> class op,
  typename additional_param,
  typename... values
>
struct h_apply_op_helper                                        { typedef type_list<typename op<values, additional_param>::type...> type; };
template<
  template<typename, typename> class op,
  typename additional_param,
  typename... values
>
struct h_apply_op_helper<true, op, additional_param, values...> { typedef type_list<typename op<additional_param, values>::type...> type; };

template<
  bool from_left,
  template<typename, typename> class op,
  typename additional_param
>
struct h_apply_op
{
  template<typename... values>
  constexpr static typename h_apply_op_helper<from_left, op, additional_param, values...>::type helper(type_list<values...>)
  { return typename h_apply_op_helper<from_left, op, additional_param, values...>::type(); }
};

template<
  template<typename, typename> class op,
  typename additional_param,
  typename a
>
struct apply_op_from_left { typedef decltype(h_apply_op<true, op, additional_param>::helper(a())) type; };

template<
  template<typename, typename> class op,
  typename additional_param,
  typename a
>
struct apply_op_from_right { typedef decltype(h_apply_op<false, op, additional_param>::helper(a())) type; };

/* see if an element is in a list */

template<
  template<typename, typename> class test,
  typename check_against,
  typename h_list,
  bool last_check_positive = false
>
struct contained_in_list;

template<
  template<typename, typename> class test,
  typename check_against,
  typename h_list
>
struct contained_in_list<test, check_against, h_list, true>
{
  constexpr static bool value = true;
};

template<
  template<typename, typename> class test,
  typename check_against,
  typename a,
  typename... as
>
struct contained_in_list<test, check_against, type_list<a, as...>, false> : contained_in_list<test, check_against, type_list<as...>, test<check_against, a>::value> {};

template<
  template<typename, typename> class test,
  typename check_against,
  typename... empty
>
struct contained_in_list<test, check_against, type_list<empty...>, false> { constexpr static bool value = false; };

/* see if an element is in a list and check for global flags */

template<
  template<typename, typename> class test,
  typename check_against,
  typename h_list,
  int default_flags = 0,
  bool last_check_positive = false,
  int last_check_flags = default_flags
>
struct contained_in_list_gf;

template<
  template<typename, typename> class test,
  typename check_against,
  typename h_list,
  int default_flags,
  int last_check_flags
>
struct contained_in_list_gf<test, check_against, h_list, default_flags, true, last_check_flags>
{
  constexpr static bool value = true;
  constexpr static int global_flags = last_check_flags;
};

template<
  template<typename, typename> class test,
  typename check_against,
  typename a,
  typename... as,
  int default_flags,
  int last_check_flags
>
struct contained_in_list_gf<test, check_against, type_list<a, as...>, default_flags, false, last_check_flags> : contained_in_list_gf<test, check_against, type_list<as...>, default_flags, test<check_against, a>::value, test<check_against, a>::global_flags> {};

template<
  template<typename, typename> class test,
  typename check_against,
  typename... empty,
  int default_flags,
  int last_check_flags
>
struct contained_in_list_gf<test, check_against, type_list<empty...>, default_flags, false, last_check_flags> { constexpr static bool value = false; constexpr static int global_flags = default_flags; };

/* generic reductions */

template<
  typename Reducer,
  typename... Ts
> struct reduce;

template<
  typename Reducer
> struct reduce<Reducer>
{
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE int run() { return Reducer::Identity; }
};

template<
  typename Reducer,
  typename A
> struct reduce<Reducer, A>
{
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE A run(A a) { return a; }
};

template<
  typename Reducer,
  typename A,
  typename... Ts
> struct reduce<Reducer, A, Ts...>
{
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE auto run(A a, Ts... ts) -> decltype(Reducer::run(a, reduce<Reducer, Ts...>::run(ts...))) {
    return Reducer::run(a, reduce<Reducer, Ts...>::run(ts...));
  }
};

/* generic binary operations */

struct sum_op           {
  template<typename A, typename B> EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a + b)   { return a + b;   }
  static constexpr int Identity = 0;
};
struct product_op       {
  template<typename A, typename B> EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a * b)   { return a * b;   }
  static constexpr int Identity = 1;
};

struct logical_and_op   { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a && b)  { return a && b;  } };
struct logical_or_op    { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a || b)  { return a || b;  } };

struct equal_op         { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a == b)  { return a == b;  } };
struct not_equal_op     { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a != b)  { return a != b;  } };
struct lesser_op        { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a < b)   { return a < b;   } };
struct lesser_equal_op  { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a <= b)  { return a <= b;  } };
struct greater_op       { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a > b)   { return a > b;   } };
struct greater_equal_op { template<typename A, typename B> constexpr static EIGEN_STRONG_INLINE auto run(A a, B b) -> decltype(a >= b)  { return a >= b;  } };

/* generic unary operations */

struct not_op                { template<typename A> constexpr static EIGEN_STRONG_INLINE auto run(A a) -> decltype(!a)      { return !a;      } };
struct negation_op           { template<typename A> constexpr static EIGEN_STRONG_INLINE auto run(A a) -> decltype(-a)      { return -a;      } };
struct greater_equal_zero_op { template<typename A> constexpr static EIGEN_STRONG_INLINE auto run(A a) -> decltype(a >= 0)  { return a >= 0;  } };


/* reductions for lists */

// using auto -> return value spec makes ICC 13.0 and 13.1 crash here, so we have to hack it
// together in front... (13.0 doesn't work with array_prod/array_reduce/... anyway, but 13.1
// does...
template<typename... Ts>
EIGEN_DEVICE_FUNC constexpr EIGEN_STRONG_INLINE decltype(reduce<product_op, Ts...>::run((*((Ts*)0))...)) arg_prod(Ts... ts)
{
  return reduce<product_op, Ts...>::run(ts...);
}

template<typename... Ts>
constexpr EIGEN_STRONG_INLINE decltype(reduce<sum_op, Ts...>::run((*((Ts*)0))...)) arg_sum(Ts... ts)
{
  return reduce<sum_op, Ts...>::run(ts...);
}

/* reverse arrays */

template<typename Array, int... n>
constexpr EIGEN_STRONG_INLINE Array h_array_reverse(Array arr, numeric_list<int, n...>)
{
  return {{array_get<sizeof...(n) - n - 1>(arr)...}};
}

template<typename T, std::size_t N>
constexpr EIGEN_STRONG_INLINE array<T, N> array_reverse(array<T, N> arr)
{
  return h_array_reverse(arr, typename gen_numeric_list<int, N>::type());
}


/* generic array reductions */

// can't reuse standard reduce() interface above because Intel's Compiler
// *really* doesn't like it, so we just reimplement the stuff
// (start from N - 1 and work down to 0 because specialization for
// n == N - 1 also doesn't work in Intel's compiler, so it goes into
// an infinite loop)
template<typename Reducer, typename T, std::size_t N, std::size_t n = N - 1>
struct h_array_reduce {
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE auto run(array<T, N> arr, T identity) -> decltype(Reducer::run(h_array_reduce<Reducer, T, N, n - 1>::run(arr, identity), array_get<n>(arr)))
  {
    return Reducer::run(h_array_reduce<Reducer, T, N, n - 1>::run(arr, identity), array_get<n>(arr));
  }
};

template<typename Reducer, typename T, std::size_t N>
struct h_array_reduce<Reducer, T, N, 0>
{
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE T run(const array<T, N>& arr, T)
  {
    return array_get<0>(arr);
  }
};

template<typename Reducer, typename T>
struct h_array_reduce<Reducer, T, 0>
{
  EIGEN_DEVICE_FUNC constexpr static EIGEN_STRONG_INLINE T run(const array<T, 0>&, T identity)
  {
    return identity;
  }
};

template<typename Reducer, typename T, std::size_t N>
EIGEN_DEVICE_FUNC constexpr EIGEN_STRONG_INLINE auto array_reduce(const array<T, N>& arr, T identity) -> decltype(h_array_reduce<Reducer, T, N>::run(arr, identity))
{
  return h_array_reduce<Reducer, T, N>::run(arr, identity);
}

/* standard array reductions */

template<typename T, std::size_t N>
EIGEN_DEVICE_FUNC constexpr EIGEN_STRONG_INLINE auto array_sum(const array<T, N>& arr) -> decltype(array_reduce<sum_op, T, N>(arr, static_cast<T>(0)))
{
  return array_reduce<sum_op, T, N>(arr, static_cast<T>(0));
}

template<typename T, std::size_t N>
EIGEN_DEVICE_FUNC constexpr EIGEN_STRONG_INLINE auto array_prod(const array<T, N>& arr) -> decltype(array_reduce<product_op, T, N>(arr, static_cast<T>(1)))
{
  return array_reduce<product_op, T, N>(arr, static_cast<T>(1));
}

template<typename t>
EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE t array_prod(const std::vector<t>& a) {
  eigen_assert(a.size() > 0);
  t prod = 1;
  for (size_t i = 0; i < a.size(); ++i) { prod *= a[i]; }
  return prod;
}

/* zip an array */

template<typename Op, typename A, typename B, std::size_t N, int... n>
constexpr EIGEN_STRONG_INLINE array<decltype(Op::run(A(), B())),N> h_array_zip(array<A, N> a, array<B, N> b, numeric_list<int, n...>)
{
  return array<decltype(Op::run(A(), B())),N>{{ Op::run(array_get<n>(a), array_get<n>(b))... }};
}

template<typename Op, typename A, typename B, std::size_t N>
constexpr EIGEN_STRONG_INLINE array<decltype(Op::run(A(), B())),N> array_zip(array<A, N> a, array<B, N> b)
{
  return h_array_zip<Op>(a, b, typename gen_numeric_list<int, N>::type());
}

/* zip an array and reduce the result */

template<typename Reducer, typename Op, typename A, typename B, std::size_t N, int... n>
constexpr EIGEN_STRONG_INLINE auto h_array_zip_and_reduce(array<A, N> a, array<B, N> b, numeric_list<int, n...>) -> decltype(reduce<Reducer, typename id_numeric<int,n,decltype(Op::run(A(), B()))>::type...>::run(Op::run(array_get<n>(a), array_get<n>(b))...))
{
  return reduce<Reducer, typename id_numeric<int,n,decltype(Op::run(A(), B()))>::type...>::run(Op::run(array_get<n>(a), array_get<n>(b))...);
}

template<typename Reducer, typename Op, typename A, typename B, std::size_t N>
constexpr EIGEN_STRONG_INLINE auto array_zip_and_reduce(array<A, N> a, array<B, N> b) -> decltype(h_array_zip_and_reduce<Reducer, Op, A, B, N>(a, b, typename gen_numeric_list<int, N>::type()))
{
  return h_array_zip_and_reduce<Reducer, Op, A, B, N>(a, b, typename gen_numeric_list<int, N>::type());
}

/* apply stuff to an array */

template<typename Op, typename A, std::size_t N, int... n>
constexpr EIGEN_STRONG_INLINE array<decltype(Op::run(A())),N> h_array_apply(array<A, N> a, numeric_list<int, n...>)
{
  return array<decltype(Op::run(A())),N>{{ Op::run(array_get<n>(a))... }};
}

template<typename Op, typename A, std::size_t N>
constexpr EIGEN_STRONG_INLINE array<decltype(Op::run(A())),N> array_apply(array<A, N> a)
{
  return h_array_apply<Op>(a, typename gen_numeric_list<int, N>::type());
}

/* apply stuff to an array and reduce */

template<typename Reducer, typename Op, typename A, std::size_t N, int... n>
constexpr EIGEN_STRONG_INLINE auto h_array_apply_and_reduce(array<A, N> arr, numeric_list<int, n...>) -> decltype(reduce<Reducer, typename id_numeric<int,n,decltype(Op::run(A()))>::type...>::run(Op::run(array_get<n>(arr))...))
{
  return reduce<Reducer, typename id_numeric<int,n,decltype(Op::run(A()))>::type...>::run(Op::run(array_get<n>(arr))...);
}

template<typename Reducer, typename Op, typename A, std::size_t N>
constexpr EIGEN_STRONG_INLINE auto array_apply_and_reduce(array<A, N> a) -> decltype(h_array_apply_and_reduce<Reducer, Op, A, N>(a, typename gen_numeric_list<int, N>::type()))
{
  return h_array_apply_and_reduce<Reducer, Op, A, N>(a, typename gen_numeric_list<int, N>::type());
}

/* repeat a value n times (and make an array out of it
 * usage:
 *   array<int, 16> = repeat<16>(42);
 */

template<int n>
struct h_repeat
{
  template<typename t, int... ii>
  constexpr static EIGEN_STRONG_INLINE array<t, n> run(t v, numeric_list<int, ii...>)
  {
    return {{ typename id_numeric<int, ii, t>::type(v)... }};
  }
};

template<int n, typename t>
constexpr array<t, n> repeat(t v) { return h_repeat<n>::run(v, typename gen_numeric_list<int, n>::type()); }

/* instantiate a class by a C-style array */
template<class InstType, typename ArrType, std::size_t N, bool Reverse, typename... Ps>
struct h_instantiate_by_c_array;

template<class InstType, typename ArrType, std::size_t N, typename... Ps>
struct h_instantiate_by_c_array<InstType, ArrType, N, false, Ps...>
{
  static InstType run(ArrType* arr, Ps... args)
  {
    return h_instantiate_by_c_array<InstType, ArrType, N - 1, false, Ps..., ArrType>::run(arr + 1, args..., arr[0]);
  }
};

template<class InstType, typename ArrType, std::size_t N, typename... Ps>
struct h_instantiate_by_c_array<InstType, ArrType, N, true, Ps...>
{
  static InstType run(ArrType* arr, Ps... args)
  {
    return h_instantiate_by_c_array<InstType, ArrType, N - 1, false, ArrType, Ps...>::run(arr + 1, arr[0], args...);
  }
};

template<class InstType, typename ArrType, typename... Ps>
struct h_instantiate_by_c_array<InstType, ArrType, 0, false, Ps...>
{
  static InstType run(ArrType* arr, Ps... args)
  {
    (void)arr;
    return InstType(args...);
  }
};

template<class InstType, typename ArrType, typename... Ps>
struct h_instantiate_by_c_array<InstType, ArrType, 0, true, Ps...>
{
  static InstType run(ArrType* arr, Ps... args)
  {
    (void)arr;
    return InstType(args...);
  }
};

template<class InstType, typename ArrType, std::size_t N, bool Reverse = false>
InstType instantiate_by_c_array(ArrType* arr)
{
  return h_instantiate_by_c_array<InstType, ArrType, N, Reverse>::run(arr);
}

} // end namespace internal

} // end namespace Eigen

#endif // EIGEN_META_H