1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// Copyright (C) 2013 Christian Seiler <christian@iwakd.de>
5//
6// This Source Code Form is subject to the terms of the Mozilla
7// Public License v. 2.0. If a copy of the MPL was not distributed
8// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9
10#ifndef EIGEN_CXX11META_H
11#define EIGEN_CXX11META_H
12
13#include <vector>
14#include "EmulateArray.h"
15
16// Emulate the cxx11 functionality that we need if the compiler doesn't support it.
17// Visual studio 2015 doesn't advertise itself as cxx11 compliant, although it
18// supports enough of the standard for our needs
19#if __cplusplus > 199711L || EIGEN_COMP_MSVC >= 1900
20
21#include "CXX11Workarounds.h"
22
23namespace Eigen {
24
25namespace internal {
26
27/** \internal
28  * \file CXX11/util/CXX11Meta.h
29  * This file contains generic metaprogramming classes which are not specifically related to Eigen.
30  * This file expands upon Core/util/Meta.h and adds support for C++11 specific features.
31  */
32
33template<typename... tt>
34struct type_list { constexpr static int count = sizeof...(tt); };
35
36template<typename t, typename... tt>
37struct type_list<t, tt...> { constexpr static int count = sizeof...(tt) + 1; typedef t first_type; };
38
39template<typename T, T... nn>
40struct numeric_list { constexpr static std::size_t count = sizeof...(nn); };
41
42template<typename T, T n, T... nn>
43struct numeric_list<T, n, nn...> { constexpr static std::size_t count = sizeof...(nn) + 1; constexpr static T first_value = n; };
44
45/* numeric list constructors
46 *
47 * equivalencies:
48 *     constructor                                              result
49 *     typename gen_numeric_list<int, 5>::type                  numeric_list<int, 0,1,2,3,4>
50 *     typename gen_numeric_list_reversed<int, 5>::type         numeric_list<int, 4,3,2,1,0>
51 *     typename gen_numeric_list_swapped_pair<int, 5,1,2>::type numeric_list<int, 0,2,1,3,4>
52 *     typename gen_numeric_list_repeated<int, 0, 5>::type      numeric_list<int, 0,0,0,0,0>
53 */
54
55template<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...> {};
56template<typename T, T start, T... ii>                    struct gen_numeric_list<T, 0, start, ii...> { typedef numeric_list<T, ii...> type; };
57
58template<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> {};
59template<typename T, T start, T... ii>                    struct gen_numeric_list_reversed<T, 0, start, ii...> { typedef numeric_list<T, ii...> type; };
60
61template<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...> {};
62template<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; };
63
64template<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...> {};
65template<typename T, T V, T... nn>                struct gen_numeric_list_repeated<T, 0, V, nn...> { typedef numeric_list<T, nn...> type; };
66
67/* list manipulation: concatenate */
68
69template<class a, class b> struct concat;
70
71template<typename... as, typename... bs> struct concat<type_list<as...>,       type_list<bs...>>        { typedef type_list<as..., bs...> type; };
72template<typename T, T... as, T... bs>   struct concat<numeric_list<T, as...>, numeric_list<T, bs...> > { typedef numeric_list<T, as..., bs...> type; };
73
74template<typename... p> struct mconcat;
75template<typename a>                             struct mconcat<a>           { typedef a type; };
76template<typename a, typename b>                 struct mconcat<a, b>        : concat<a, b> {};
77template<typename a, typename b, typename... cs> struct mconcat<a, b, cs...> : concat<a, typename mconcat<b, cs...>::type> {};
78
79/* list manipulation: extract slices */
80
81template<int n, typename x> struct take;
82template<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> {};
83template<int n>                             struct take<n, type_list<>>         { typedef type_list<> type; };
84template<typename a, typename... as>        struct take<0, type_list<a, as...>> { typedef type_list<> type; };
85template<>                                  struct take<0, type_list<>>         { typedef type_list<> type; };
86
87template<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> {};
88template<typename T, int n>               struct take<n, numeric_list<T>>           { typedef numeric_list<T> type; };
89template<typename T, T a, T... as>        struct take<0, numeric_list<T, a, as...>> { typedef numeric_list<T> type; };
90template<typename T>                      struct take<0, numeric_list<T>>           { typedef numeric_list<T> type; };
91
92template<typename T, int n, T... ii>      struct h_skip_helper_numeric;
93template<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...> {};
94template<typename T, T i, T... ii>        struct h_skip_helper_numeric<T, 0, i, ii...> { typedef numeric_list<T, i, ii...> type; };
95template<typename T, int n>               struct h_skip_helper_numeric<T, n>           { typedef numeric_list<T> type; };
96template<typename T>                      struct h_skip_helper_numeric<T, 0>           { typedef numeric_list<T> type; };
97
98template<int n, typename... tt>             struct h_skip_helper_type;
99template<int n, typename t, typename... tt> struct h_skip_helper_type<n, t, tt...> : h_skip_helper_type<n-1, tt...> {};
100template<typename t, typename... tt>        struct h_skip_helper_type<0, t, tt...> { typedef type_list<t, tt...> type; };
101template<int n>                             struct h_skip_helper_type<n>           { typedef type_list<> type; };
102template<>                                  struct h_skip_helper_type<0>           { typedef type_list<> type; };
103
104template<int n>
105struct h_skip {
106  template<typename T, T... ii>
107  constexpr static 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(); }
108  template<typename... tt>
109  constexpr static inline typename h_skip_helper_type<n, tt...>::type helper(type_list<tt...>) { return typename h_skip_helper_type<n, tt...>::type(); }
110};
111
112template<int n, typename a> struct skip { typedef decltype(h_skip<n>::helper(a())) type; };
113
114template<int start, int count, typename a> struct slice : take<count, typename skip<start, a>::type> {};
115
116/* list manipulation: retrieve single element from list */
117
118template<int n, typename x> struct get;
119
120template<int n, typename a, typename... as>               struct get<n, type_list<a, as...>>   : get<n-1, type_list<as...>> {};
121template<typename a, typename... as>                      struct get<0, type_list<a, as...>>   { typedef a type; };
122
123template<typename T, int n, T a, T... as>                        struct get<n, numeric_list<T, a, as...>>   : get<n-1, numeric_list<T, as...>> {};
124template<typename T, T a, T... as>                               struct get<0, numeric_list<T, a, as...>>   { constexpr static T value = a; };
125
126/* always get type, regardless of dummy; good for parameter pack expansion */
127
128template<typename T, T dummy, typename t> struct id_numeric  { typedef t type; };
129template<typename dummy, typename t>      struct id_type     { typedef t type; };
130
131/* equality checking, flagged version */
132
133template<typename a, typename b> struct is_same_gf : is_same<a, b> { constexpr static int global_flags = 0; };
134
135/* apply_op to list */
136
137template<
138  bool from_left, // false
139  template<typename, typename> class op,
140  typename additional_param,
141  typename... values
142>
143struct h_apply_op_helper                                        { typedef type_list<typename op<values, additional_param>::type...> type; };
144template<
145  template<typename, typename> class op,
146  typename additional_param,
147  typename... values
148>
149struct h_apply_op_helper<true, op, additional_param, values...> { typedef type_list<typename op<additional_param, values>::type...> type; };
150
151template<
152  bool from_left,
153  template<typename, typename> class op,
154  typename additional_param
155>
156struct h_apply_op
157{
158  template<typename... values>
159  constexpr static typename h_apply_op_helper<from_left, op, additional_param, values...>::type helper(type_list<values...>)
160  { return typename h_apply_op_helper<from_left, op, additional_param, values...>::type(); }
161};
162
163template<
164  template<typename, typename> class op,
165  typename additional_param,
166  typename a
167>
168struct apply_op_from_left { typedef decltype(h_apply_op<true, op, additional_param>::helper(a())) type; };
169
170template<
171  template<typename, typename> class op,
172  typename additional_param,
173  typename a
174>
175struct apply_op_from_right { typedef decltype(h_apply_op<false, op, additional_param>::helper(a())) type; };
176
177/* see if an element is in a list */
178
179template<
180  template<typename, typename> class test,
181  typename check_against,
182  typename h_list,
183  bool last_check_positive = false
184>
185struct contained_in_list;
186
187template<
188  template<typename, typename> class test,
189  typename check_against,
190  typename h_list
191>
192struct contained_in_list<test, check_against, h_list, true>
193{
194  constexpr static bool value = true;
195};
196
197template<
198  template<typename, typename> class test,
199  typename check_against,
200  typename a,
201  typename... as
202>
203struct 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> {};
204
205template<
206  template<typename, typename> class test,
207  typename check_against
208  EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty)
209>
210struct contained_in_list<test, check_against, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(empty)>, false> { constexpr static bool value = false; };
211
212/* see if an element is in a list and check for global flags */
213
214template<
215  template<typename, typename> class test,
216  typename check_against,
217  typename h_list,
218  int default_flags = 0,
219  bool last_check_positive = false,
220  int last_check_flags = default_flags
221>
222struct contained_in_list_gf;
223
224template<
225  template<typename, typename> class test,
226  typename check_against,
227  typename h_list,
228  int default_flags,
229  int last_check_flags
230>
231struct contained_in_list_gf<test, check_against, h_list, default_flags, true, last_check_flags>
232{
233  constexpr static bool value = true;
234  constexpr static int global_flags = last_check_flags;
235};
236
237template<
238  template<typename, typename> class test,
239  typename check_against,
240  typename a,
241  typename... as,
242  int default_flags,
243  int last_check_flags
244>
245struct 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> {};
246
247template<
248  template<typename, typename> class test,
249  typename check_against
250  EIGEN_TPL_PP_SPEC_HACK_DEFC(typename, empty),
251  int default_flags,
252  int last_check_flags
253>
254struct contained_in_list_gf<test, check_against, type_list<EIGEN_TPL_PP_SPEC_HACK_USE(empty)>, default_flags, false, last_check_flags> { constexpr static bool value = false; constexpr static int global_flags = default_flags; };
255
256/* generic reductions */
257
258template<
259  typename Reducer,
260  typename... Ts
261> struct reduce;
262
263template<
264  typename Reducer
265> struct reduce<Reducer>
266{
267  constexpr static inline int run() { return Reducer::Identity; }
268};
269
270template<
271  typename Reducer,
272  typename A
273> struct reduce<Reducer, A>
274{
275  constexpr static inline A run(A a) { return a; }
276};
277
278template<
279  typename Reducer,
280  typename A,
281  typename... Ts
282> struct reduce<Reducer, A, Ts...>
283{
284  constexpr static inline auto run(A a, Ts... ts) -> decltype(Reducer::run(a, reduce<Reducer, Ts...>::run(ts...))) {
285    return Reducer::run(a, reduce<Reducer, Ts...>::run(ts...));
286  }
287};
288
289/* generic binary operations */
290
291struct sum_op           {
292  template<typename A, typename B> EIGEN_DEVICE_FUNC constexpr static inline auto run(A a, B b) -> decltype(a + b)   { return a + b;   }
293  static constexpr int Identity = 0;
294};
295struct product_op       {
296  template<typename A, typename B> EIGEN_DEVICE_FUNC constexpr static inline auto run(A a, B b) -> decltype(a * b)   { return a * b;   }
297  static constexpr int Identity = 1;
298};
299
300struct logical_and_op   { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a && b)  { return a && b;  } };
301struct logical_or_op    { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a || b)  { return a || b;  } };
302
303struct equal_op         { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a == b)  { return a == b;  } };
304struct not_equal_op     { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a != b)  { return a != b;  } };
305struct lesser_op        { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a < b)   { return a < b;   } };
306struct lesser_equal_op  { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a <= b)  { return a <= b;  } };
307struct greater_op       { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a > b)   { return a > b;   } };
308struct greater_equal_op { template<typename A, typename B> constexpr static inline auto run(A a, B b) -> decltype(a >= b)  { return a >= b;  } };
309
310/* generic unary operations */
311
312struct not_op                { template<typename A> constexpr static inline auto run(A a) -> decltype(!a)      { return !a;      } };
313struct negation_op           { template<typename A> constexpr static inline auto run(A a) -> decltype(-a)      { return -a;      } };
314struct greater_equal_zero_op { template<typename A> constexpr static inline auto run(A a) -> decltype(a >= 0)  { return a >= 0;  } };
315
316
317/* reductions for lists */
318
319// using auto -> return value spec makes ICC 13.0 and 13.1 crash here, so we have to hack it
320// together in front... (13.0 doesn't work with array_prod/array_reduce/... anyway, but 13.1
321// does...
322template<typename... Ts>
323constexpr inline decltype(reduce<product_op, Ts...>::run((*((Ts*)0))...)) arg_prod(Ts... ts)
324{
325  return reduce<product_op, Ts...>::run(ts...);
326}
327
328template<typename... Ts>
329constexpr inline decltype(reduce<sum_op, Ts...>::run((*((Ts*)0))...)) arg_sum(Ts... ts)
330{
331  return reduce<sum_op, Ts...>::run(ts...);
332}
333
334/* reverse arrays */
335
336template<typename Array, int... n>
337constexpr inline Array h_array_reverse(Array arr, numeric_list<int, n...>)
338{
339  return {{array_get<sizeof...(n) - n - 1>(arr)...}};
340}
341
342template<typename T, std::size_t N>
343constexpr inline array<T, N> array_reverse(array<T, N> arr)
344{
345  return h_array_reverse(arr, typename gen_numeric_list<int, N>::type());
346}
347
348
349/* generic array reductions */
350
351// can't reuse standard reduce() interface above because Intel's Compiler
352// *really* doesn't like it, so we just reimplement the stuff
353// (start from N - 1 and work down to 0 because specialization for
354// n == N - 1 also doesn't work in Intel's compiler, so it goes into
355// an infinite loop)
356template<typename Reducer, typename T, std::size_t N, std::size_t n = N - 1>
357struct h_array_reduce {
358  EIGEN_DEVICE_FUNC constexpr static 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)))
359  {
360    return Reducer::run(h_array_reduce<Reducer, T, N, n - 1>::run(arr, identity), array_get<n>(arr));
361  }
362};
363
364template<typename Reducer, typename T, std::size_t N>
365struct h_array_reduce<Reducer, T, N, 0>
366{
367  EIGEN_DEVICE_FUNC constexpr static inline T run(const array<T, N>& arr, T)
368  {
369    return array_get<0>(arr);
370  }
371};
372
373template<typename Reducer, typename T>
374struct h_array_reduce<Reducer, T, 0>
375{
376  EIGEN_DEVICE_FUNC constexpr static inline T run(const array<T, 0>&, T identity)
377  {
378    return identity;
379  }
380};
381
382template<typename Reducer, typename T, std::size_t N>
383EIGEN_DEVICE_FUNC constexpr inline auto array_reduce(const array<T, N>& arr, T identity) -> decltype(h_array_reduce<Reducer, T, N>::run(arr, identity))
384{
385  return h_array_reduce<Reducer, T, N>::run(arr, identity);
386}
387
388/* standard array reductions */
389
390template<typename T, std::size_t N>
391EIGEN_DEVICE_FUNC constexpr inline auto array_sum(const array<T, N>& arr) -> decltype(array_reduce<sum_op, T, N>(arr, static_cast<T>(0)))
392{
393  return array_reduce<sum_op, T, N>(arr, static_cast<T>(0));
394}
395
396template<typename T, std::size_t N>
397EIGEN_DEVICE_FUNC constexpr inline auto array_prod(const array<T, N>& arr) -> decltype(array_reduce<product_op, T, N>(arr, static_cast<T>(1)))
398{
399  return array_reduce<product_op, T, N>(arr, static_cast<T>(1));
400}
401
402template<typename t>
403EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE t array_prod(const std::vector<t>& a) {
404  eigen_assert(a.size() > 0);
405  t prod = 1;
406  for (size_t i = 0; i < a.size(); ++i) { prod *= a[i]; }
407  return prod;
408}
409
410/* zip an array */
411
412template<typename Op, typename A, typename B, std::size_t N, int... n>
413constexpr inline array<decltype(Op::run(A(), B())),N> h_array_zip(array<A, N> a, array<B, N> b, numeric_list<int, n...>)
414{
415  return array<decltype(Op::run(A(), B())),N>{{ Op::run(array_get<n>(a), array_get<n>(b))... }};
416}
417
418template<typename Op, typename A, typename B, std::size_t N>
419constexpr inline array<decltype(Op::run(A(), B())),N> array_zip(array<A, N> a, array<B, N> b)
420{
421  return h_array_zip<Op>(a, b, typename gen_numeric_list<int, N>::type());
422}
423
424/* zip an array and reduce the result */
425
426template<typename Reducer, typename Op, typename A, typename B, std::size_t N, int... n>
427constexpr 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))...))
428{
429  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))...);
430}
431
432template<typename Reducer, typename Op, typename A, typename B, std::size_t N>
433constexpr 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()))
434{
435  return h_array_zip_and_reduce<Reducer, Op, A, B, N>(a, b, typename gen_numeric_list<int, N>::type());
436}
437
438/* apply stuff to an array */
439
440template<typename Op, typename A, std::size_t N, int... n>
441constexpr inline array<decltype(Op::run(A())),N> h_array_apply(array<A, N> a, numeric_list<int, n...>)
442{
443  return array<decltype(Op::run(A())),N>{{ Op::run(array_get<n>(a))... }};
444}
445
446template<typename Op, typename A, std::size_t N>
447constexpr inline array<decltype(Op::run(A())),N> array_apply(array<A, N> a)
448{
449  return h_array_apply<Op>(a, typename gen_numeric_list<int, N>::type());
450}
451
452/* apply stuff to an array and reduce */
453
454template<typename Reducer, typename Op, typename A, std::size_t N, int... n>
455constexpr 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))...))
456{
457  return reduce<Reducer, typename id_numeric<int,n,decltype(Op::run(A()))>::type...>::run(Op::run(array_get<n>(arr))...);
458}
459
460template<typename Reducer, typename Op, typename A, std::size_t N>
461constexpr 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()))
462{
463  return h_array_apply_and_reduce<Reducer, Op, A, N>(a, typename gen_numeric_list<int, N>::type());
464}
465
466/* repeat a value n times (and make an array out of it
467 * usage:
468 *   array<int, 16> = repeat<16>(42);
469 */
470
471template<int n>
472struct h_repeat
473{
474  template<typename t, int... ii>
475  constexpr static inline array<t, n> run(t v, numeric_list<int, ii...>)
476  {
477    return {{ typename id_numeric<int, ii, t>::type(v)... }};
478  }
479};
480
481template<int n, typename t>
482constexpr array<t, n> repeat(t v) { return h_repeat<n>::run(v, typename gen_numeric_list<int, n>::type()); }
483
484/* instantiate a class by a C-style array */
485template<class InstType, typename ArrType, std::size_t N, bool Reverse, typename... Ps>
486struct h_instantiate_by_c_array;
487
488template<class InstType, typename ArrType, std::size_t N, typename... Ps>
489struct h_instantiate_by_c_array<InstType, ArrType, N, false, Ps...>
490{
491  static InstType run(ArrType* arr, Ps... args)
492  {
493    return h_instantiate_by_c_array<InstType, ArrType, N - 1, false, Ps..., ArrType>::run(arr + 1, args..., arr[0]);
494  }
495};
496
497template<class InstType, typename ArrType, std::size_t N, typename... Ps>
498struct h_instantiate_by_c_array<InstType, ArrType, N, true, Ps...>
499{
500  static InstType run(ArrType* arr, Ps... args)
501  {
502    return h_instantiate_by_c_array<InstType, ArrType, N - 1, false, ArrType, Ps...>::run(arr + 1, arr[0], args...);
503  }
504};
505
506template<class InstType, typename ArrType, typename... Ps>
507struct h_instantiate_by_c_array<InstType, ArrType, 0, false, Ps...>
508{
509  static InstType run(ArrType* arr, Ps... args)
510  {
511    (void)arr;
512    return InstType(args...);
513  }
514};
515
516template<class InstType, typename ArrType, typename... Ps>
517struct h_instantiate_by_c_array<InstType, ArrType, 0, true, Ps...>
518{
519  static InstType run(ArrType* arr, Ps... args)
520  {
521    (void)arr;
522    return InstType(args...);
523  }
524};
525
526template<class InstType, typename ArrType, std::size_t N, bool Reverse = false>
527InstType instantiate_by_c_array(ArrType* arr)
528{
529  return h_instantiate_by_c_array<InstType, ArrType, N, Reverse>::run(arr);
530}
531
532} // end namespace internal
533
534} // end namespace Eigen
535
536#else // Non C++11, fallback to emulation mode
537
538#include "EmulateCXX11Meta.h"
539
540#endif
541
542#endif // EIGEN_CXX11META_H
543