1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008-2015 Gael Guennebaud <gael.guennebaud@inria.fr>
5 // Copyright (C) 2006-2008 Benoit Jacob <jacob.benoit.1@gmail.com>
6 //
7 // This Source Code Form is subject to the terms of the Mozilla
8 // Public License v. 2.0. If a copy of the MPL was not distributed
9 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10 
11 #ifndef EIGEN_META_H
12 #define EIGEN_META_H
13 
14 #if defined(__CUDA_ARCH__)
15 #include <cfloat>
16 #include <math_constants.h>
17 #endif
18 
19 #if EIGEN_COMP_ICC>=1600 &&  __cplusplus >= 201103L
20 #include <cstdint>
21 #endif
22 
23 namespace Eigen {
24 
25 typedef EIGEN_DEFAULT_DENSE_INDEX_TYPE DenseIndex;
26 
27 /**
28  * \brief The Index type as used for the API.
29  * \details To change this, \c \#define the preprocessor symbol \c EIGEN_DEFAULT_DENSE_INDEX_TYPE.
30  * \sa \blank \ref TopicPreprocessorDirectives, StorageIndex.
31  */
32 
33 typedef EIGEN_DEFAULT_DENSE_INDEX_TYPE Index;
34 
35 namespace internal {
36 
37 /** \internal
38   * \file Meta.h
39   * This file contains generic metaprogramming classes which are not specifically related to Eigen.
40   * \note In case you wonder, yes we're aware that Boost already provides all these features,
41   * we however don't want to add a dependency to Boost.
42   */
43 
44 // Only recent versions of ICC complain about using ptrdiff_t to hold pointers,
45 // and older versions do not provide *intptr_t types.
46 #if EIGEN_COMP_ICC>=1600 &&  __cplusplus >= 201103L
47 typedef std::intptr_t  IntPtr;
48 typedef std::uintptr_t UIntPtr;
49 #else
50 typedef std::ptrdiff_t IntPtr;
51 typedef std::size_t UIntPtr;
52 #endif
53 
54 struct true_type {  enum { value = 1 }; };
55 struct false_type { enum { value = 0 }; };
56 
57 template<bool Condition, typename Then, typename Else>
58 struct conditional { typedef Then type; };
59 
60 template<typename Then, typename Else>
61 struct conditional <false, Then, Else> { typedef Else type; };
62 
63 template<typename T, typename U> struct is_same { enum { value = 0 }; };
64 template<typename T> struct is_same<T,T> { enum { value = 1 }; };
65 
66 template<typename T> struct remove_reference { typedef T type; };
67 template<typename T> struct remove_reference<T&> { typedef T type; };
68 
69 template<typename T> struct remove_pointer { typedef T type; };
70 template<typename T> struct remove_pointer<T*> { typedef T type; };
71 template<typename T> struct remove_pointer<T*const> { typedef T type; };
72 
73 template <class T> struct remove_const { typedef T type; };
74 template <class T> struct remove_const<const T> { typedef T type; };
75 template <class T> struct remove_const<const T[]> { typedef T type[]; };
76 template <class T, unsigned int Size> struct remove_const<const T[Size]> { typedef T type[Size]; };
77 
78 template<typename T> struct remove_all { typedef T type; };
79 template<typename T> struct remove_all<const T>   { typedef typename remove_all<T>::type type; };
80 template<typename T> struct remove_all<T const&>  { typedef typename remove_all<T>::type type; };
81 template<typename T> struct remove_all<T&>        { typedef typename remove_all<T>::type type; };
82 template<typename T> struct remove_all<T const*>  { typedef typename remove_all<T>::type type; };
83 template<typename T> struct remove_all<T*>        { typedef typename remove_all<T>::type type; };
84 
85 template<typename T> struct is_arithmetic      { enum { value = false }; };
86 template<> struct is_arithmetic<float>         { enum { value = true }; };
87 template<> struct is_arithmetic<double>        { enum { value = true }; };
88 template<> struct is_arithmetic<long double>   { enum { value = true }; };
89 template<> struct is_arithmetic<bool>          { enum { value = true }; };
90 template<> struct is_arithmetic<char>          { enum { value = true }; };
91 template<> struct is_arithmetic<signed char>   { enum { value = true }; };
92 template<> struct is_arithmetic<unsigned char> { enum { value = true }; };
93 template<> struct is_arithmetic<signed short>  { enum { value = true }; };
94 template<> struct is_arithmetic<unsigned short>{ enum { value = true }; };
95 template<> struct is_arithmetic<signed int>    { enum { value = true }; };
96 template<> struct is_arithmetic<unsigned int>  { enum { value = true }; };
97 template<> struct is_arithmetic<signed long>   { enum { value = true }; };
98 template<> struct is_arithmetic<unsigned long> { enum { value = true }; };
99 
100 template<typename T> struct is_integral        { enum { value = false }; };
101 template<> struct is_integral<bool>            { enum { value = true }; };
102 template<> struct is_integral<char>            { enum { value = true }; };
103 template<> struct is_integral<signed char>     { enum { value = true }; };
104 template<> struct is_integral<unsigned char>   { enum { value = true }; };
105 template<> struct is_integral<signed short>    { enum { value = true }; };
106 template<> struct is_integral<unsigned short>  { enum { value = true }; };
107 template<> struct is_integral<signed int>      { enum { value = true }; };
108 template<> struct is_integral<unsigned int>    { enum { value = true }; };
109 template<> struct is_integral<signed long>     { enum { value = true }; };
110 template<> struct is_integral<unsigned long>   { enum { value = true }; };
111 
112 template <typename T> struct add_const { typedef const T type; };
113 template <typename T> struct add_const<T&> { typedef T& type; };
114 
115 template <typename T> struct is_const { enum { value = 0 }; };
116 template <typename T> struct is_const<T const> { enum { value = 1 }; };
117 
118 template<typename T> struct add_const_on_value_type            { typedef const T type;  };
119 template<typename T> struct add_const_on_value_type<T&>        { typedef T const& type; };
120 template<typename T> struct add_const_on_value_type<T*>        { typedef T const* type; };
121 template<typename T> struct add_const_on_value_type<T* const>  { typedef T const* const type; };
122 template<typename T> struct add_const_on_value_type<T const* const>  { typedef T const* const type; };
123 
124 
125 template<typename From, typename To>
126 struct is_convertible_impl
127 {
128 private:
129   struct any_conversion
130   {
131     template <typename T> any_conversion(const volatile T&);
132     template <typename T> any_conversion(T&);
133   };
134   struct yes {int a[1];};
135   struct no  {int a[2];};
136 
137   static yes test(const To&, int);
138   static no  test(any_conversion, ...);
139 
140 public:
141   static From ms_from;
142 #ifdef __INTEL_COMPILER
143   #pragma warning push
144   #pragma warning ( disable : 2259 )
145 #endif
146   enum { value = sizeof(test(ms_from, 0))==sizeof(yes) };
147 #ifdef __INTEL_COMPILER
148   #pragma warning pop
149 #endif
150 };
151 
152 template<typename From, typename To>
153 struct is_convertible
154 {
155   enum { value = is_convertible_impl<typename remove_all<From>::type,
156                                      typename remove_all<To  >::type>::value };
157 };
158 
159 /** \internal Allows to enable/disable an overload
160   * according to a compile time condition.
161   */
162 template<bool Condition, typename T=void> struct enable_if;
163 
164 template<typename T> struct enable_if<true,T>
165 { typedef T type; };
166 
167 #if defined(__CUDA_ARCH__)
168 #if !defined(__FLT_EPSILON__)
169 #define __FLT_EPSILON__ FLT_EPSILON
170 #define __DBL_EPSILON__ DBL_EPSILON
171 #endif
172 
173 namespace device {
174 
175 template<typename T> struct numeric_limits
176 {
177   EIGEN_DEVICE_FUNC
178   static T epsilon() { return 0; }
179   static T (max)() { assert(false && "Highest not supported for this type"); }
180   static T (min)() { assert(false && "Lowest not supported for this type"); }
181   static T infinity() { assert(false && "Infinity not supported for this type"); }
182   static T quiet_NaN() { assert(false && "quiet_NaN not supported for this type"); }
183 };
184 template<> struct numeric_limits<float>
185 {
186   EIGEN_DEVICE_FUNC
187   static float epsilon() { return __FLT_EPSILON__; }
188   EIGEN_DEVICE_FUNC
189   static float (max)() { return CUDART_MAX_NORMAL_F; }
190   EIGEN_DEVICE_FUNC
191   static float (min)() { return FLT_MIN; }
192   EIGEN_DEVICE_FUNC
193   static float infinity() { return CUDART_INF_F; }
194   EIGEN_DEVICE_FUNC
195   static float quiet_NaN() { return CUDART_NAN_F; }
196 };
197 template<> struct numeric_limits<double>
198 {
199   EIGEN_DEVICE_FUNC
200   static double epsilon() { return __DBL_EPSILON__; }
201   EIGEN_DEVICE_FUNC
202   static double (max)() { return DBL_MAX; }
203   EIGEN_DEVICE_FUNC
204   static double (min)() { return DBL_MIN; }
205   EIGEN_DEVICE_FUNC
206   static double infinity() { return CUDART_INF; }
207   EIGEN_DEVICE_FUNC
208   static double quiet_NaN() { return CUDART_NAN; }
209 };
210 template<> struct numeric_limits<int>
211 {
212   EIGEN_DEVICE_FUNC
213   static int epsilon() { return 0; }
214   EIGEN_DEVICE_FUNC
215   static int (max)() { return INT_MAX; }
216   EIGEN_DEVICE_FUNC
217   static int (min)() { return INT_MIN; }
218 };
219 template<> struct numeric_limits<unsigned int>
220 {
221   EIGEN_DEVICE_FUNC
222   static unsigned int epsilon() { return 0; }
223   EIGEN_DEVICE_FUNC
224   static unsigned int (max)() { return UINT_MAX; }
225   EIGEN_DEVICE_FUNC
226   static unsigned int (min)() { return 0; }
227 };
228 template<> struct numeric_limits<long>
229 {
230   EIGEN_DEVICE_FUNC
231   static long epsilon() { return 0; }
232   EIGEN_DEVICE_FUNC
233   static long (max)() { return LONG_MAX; }
234   EIGEN_DEVICE_FUNC
235   static long (min)() { return LONG_MIN; }
236 };
237 template<> struct numeric_limits<unsigned long>
238 {
239   EIGEN_DEVICE_FUNC
240   static unsigned long epsilon() { return 0; }
241   EIGEN_DEVICE_FUNC
242   static unsigned long (max)() { return ULONG_MAX; }
243   EIGEN_DEVICE_FUNC
244   static unsigned long (min)() { return 0; }
245 };
246 template<> struct numeric_limits<long long>
247 {
248   EIGEN_DEVICE_FUNC
249   static long long epsilon() { return 0; }
250   EIGEN_DEVICE_FUNC
251   static long long (max)() { return LLONG_MAX; }
252   EIGEN_DEVICE_FUNC
253   static long long (min)() { return LLONG_MIN; }
254 };
255 template<> struct numeric_limits<unsigned long long>
256 {
257   EIGEN_DEVICE_FUNC
258   static unsigned long long epsilon() { return 0; }
259   EIGEN_DEVICE_FUNC
260   static unsigned long long (max)() { return ULLONG_MAX; }
261   EIGEN_DEVICE_FUNC
262   static unsigned long long (min)() { return 0; }
263 };
264 
265 }
266 
267 #endif
268 
269 /** \internal
270   * A base class do disable default copy ctor and copy assignement operator.
271   */
272 class noncopyable
273 {
274   EIGEN_DEVICE_FUNC noncopyable(const noncopyable&);
275   EIGEN_DEVICE_FUNC const noncopyable& operator=(const noncopyable&);
276 protected:
277   EIGEN_DEVICE_FUNC noncopyable() {}
278   EIGEN_DEVICE_FUNC ~noncopyable() {}
279 };
280 
281 /** \internal
282   * Convenient struct to get the result type of a unary or binary functor.
283   *
284   * It supports both the current STL mechanism (using the result_type member) as well as
285   * upcoming next STL generation (using a templated result member).
286   * If none of these members is provided, then the type of the first argument is returned. FIXME, that behavior is a pretty bad hack.
287   */
288 #if EIGEN_HAS_STD_RESULT_OF
289 template<typename T> struct result_of {
290   typedef typename std::result_of<T>::type type1;
291   typedef typename remove_all<type1>::type type;
292 };
293 #else
294 template<typename T> struct result_of { };
295 
296 struct has_none {int a[1];};
297 struct has_std_result_type {int a[2];};
298 struct has_tr1_result {int a[3];};
299 
300 template<typename Func, typename ArgType, int SizeOf=sizeof(has_none)>
301 struct unary_result_of_select {typedef typename internal::remove_all<ArgType>::type type;};
302 
303 template<typename Func, typename ArgType>
304 struct unary_result_of_select<Func, ArgType, sizeof(has_std_result_type)> {typedef typename Func::result_type type;};
305 
306 template<typename Func, typename ArgType>
307 struct unary_result_of_select<Func, ArgType, sizeof(has_tr1_result)> {typedef typename Func::template result<Func(ArgType)>::type type;};
308 
309 template<typename Func, typename ArgType>
310 struct result_of<Func(ArgType)> {
311     template<typename T>
312     static has_std_result_type    testFunctor(T const *, typename T::result_type const * = 0);
313     template<typename T>
314     static has_tr1_result         testFunctor(T const *, typename T::template result<T(ArgType)>::type const * = 0);
315     static has_none               testFunctor(...);
316 
317     // note that the following indirection is needed for gcc-3.3
318     enum {FunctorType = sizeof(testFunctor(static_cast<Func*>(0)))};
319     typedef typename unary_result_of_select<Func, ArgType, FunctorType>::type type;
320 };
321 
322 template<typename Func, typename ArgType0, typename ArgType1, int SizeOf=sizeof(has_none)>
323 struct binary_result_of_select {typedef typename internal::remove_all<ArgType0>::type type;};
324 
325 template<typename Func, typename ArgType0, typename ArgType1>
326 struct binary_result_of_select<Func, ArgType0, ArgType1, sizeof(has_std_result_type)>
327 {typedef typename Func::result_type type;};
328 
329 template<typename Func, typename ArgType0, typename ArgType1>
330 struct binary_result_of_select<Func, ArgType0, ArgType1, sizeof(has_tr1_result)>
331 {typedef typename Func::template result<Func(ArgType0,ArgType1)>::type type;};
332 
333 template<typename Func, typename ArgType0, typename ArgType1>
334 struct result_of<Func(ArgType0,ArgType1)> {
335     template<typename T>
336     static has_std_result_type    testFunctor(T const *, typename T::result_type const * = 0);
337     template<typename T>
338     static has_tr1_result         testFunctor(T const *, typename T::template result<T(ArgType0,ArgType1)>::type const * = 0);
339     static has_none               testFunctor(...);
340 
341     // note that the following indirection is needed for gcc-3.3
342     enum {FunctorType = sizeof(testFunctor(static_cast<Func*>(0)))};
343     typedef typename binary_result_of_select<Func, ArgType0, ArgType1, FunctorType>::type type;
344 };
345 
346 template<typename Func, typename ArgType0, typename ArgType1, typename ArgType2, int SizeOf=sizeof(has_none)>
347 struct ternary_result_of_select {typedef typename internal::remove_all<ArgType0>::type type;};
348 
349 template<typename Func, typename ArgType0, typename ArgType1, typename ArgType2>
350 struct ternary_result_of_select<Func, ArgType0, ArgType1, ArgType2, sizeof(has_std_result_type)>
351 {typedef typename Func::result_type type;};
352 
353 template<typename Func, typename ArgType0, typename ArgType1, typename ArgType2>
354 struct ternary_result_of_select<Func, ArgType0, ArgType1, ArgType2, sizeof(has_tr1_result)>
355 {typedef typename Func::template result<Func(ArgType0,ArgType1,ArgType2)>::type type;};
356 
357 template<typename Func, typename ArgType0, typename ArgType1, typename ArgType2>
358 struct result_of<Func(ArgType0,ArgType1,ArgType2)> {
359     template<typename T>
360     static has_std_result_type    testFunctor(T const *, typename T::result_type const * = 0);
361     template<typename T>
362     static has_tr1_result         testFunctor(T const *, typename T::template result<T(ArgType0,ArgType1,ArgType2)>::type const * = 0);
363     static has_none               testFunctor(...);
364 
365     // note that the following indirection is needed for gcc-3.3
366     enum {FunctorType = sizeof(testFunctor(static_cast<Func*>(0)))};
367     typedef typename ternary_result_of_select<Func, ArgType0, ArgType1, ArgType2, FunctorType>::type type;
368 };
369 #endif
370 
371 struct meta_yes { char a[1]; };
372 struct meta_no  { char a[2]; };
373 
374 // Check whether T::ReturnType does exist
375 template <typename T>
376 struct has_ReturnType
377 {
378   template <typename C> static meta_yes testFunctor(typename C::ReturnType const *);
379   template <typename C> static meta_no testFunctor(...);
380 
381   enum { value = sizeof(testFunctor<T>(0)) == sizeof(meta_yes) };
382 };
383 
384 template<typename T> const T* return_ptr();
385 
386 template <typename T, typename IndexType=Index>
387 struct has_nullary_operator
388 {
389   template <typename C> static meta_yes testFunctor(C const *,typename enable_if<(sizeof(return_ptr<C>()->operator()())>0)>::type * = 0);
390   static meta_no testFunctor(...);
391 
392   enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
393 };
394 
395 template <typename T, typename IndexType=Index>
396 struct has_unary_operator
397 {
398   template <typename C> static meta_yes testFunctor(C const *,typename enable_if<(sizeof(return_ptr<C>()->operator()(IndexType(0)))>0)>::type * = 0);
399   static meta_no testFunctor(...);
400 
401   enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
402 };
403 
404 template <typename T, typename IndexType=Index>
405 struct has_binary_operator
406 {
407   template <typename C> static meta_yes testFunctor(C const *,typename enable_if<(sizeof(return_ptr<C>()->operator()(IndexType(0),IndexType(0)))>0)>::type * = 0);
408   static meta_no testFunctor(...);
409 
410   enum { value = sizeof(testFunctor(static_cast<T*>(0))) == sizeof(meta_yes) };
411 };
412 
413 /** \internal In short, it computes int(sqrt(\a Y)) with \a Y an integer.
414   * Usage example: \code meta_sqrt<1023>::ret \endcode
415   */
416 template<int Y,
417          int InfX = 0,
418          int SupX = ((Y==1) ? 1 : Y/2),
419          bool Done = ((SupX-InfX)<=1 ? true : ((SupX*SupX <= Y) && ((SupX+1)*(SupX+1) > Y))) >
420                                 // use ?: instead of || just to shut up a stupid gcc 4.3 warning
421 class meta_sqrt
422 {
423     enum {
424       MidX = (InfX+SupX)/2,
425       TakeInf = MidX*MidX > Y ? 1 : 0,
426       NewInf = int(TakeInf) ? InfX : int(MidX),
427       NewSup = int(TakeInf) ? int(MidX) : SupX
428     };
429   public:
430     enum { ret = meta_sqrt<Y,NewInf,NewSup>::ret };
431 };
432 
433 template<int Y, int InfX, int SupX>
434 class meta_sqrt<Y, InfX, SupX, true> { public:  enum { ret = (SupX*SupX <= Y) ? SupX : InfX }; };
435 
436 
437 /** \internal Computes the least common multiple of two positive integer A and B
438   * at compile-time. It implements a naive algorithm testing all multiples of A.
439   * It thus works better if A>=B.
440   */
441 template<int A, int B, int K=1, bool Done = ((A*K)%B)==0>
442 struct meta_least_common_multiple
443 {
444   enum { ret = meta_least_common_multiple<A,B,K+1>::ret };
445 };
446 template<int A, int B, int K>
447 struct meta_least_common_multiple<A,B,K,true>
448 {
449   enum { ret = A*K };
450 };
451 
452 /** \internal determines whether the product of two numeric types is allowed and what the return type is */
453 template<typename T, typename U> struct scalar_product_traits
454 {
455   enum { Defined = 0 };
456 };
457 
458 // FIXME quick workaround around current limitation of result_of
459 // template<typename Scalar, typename ArgType0, typename ArgType1>
460 // struct result_of<scalar_product_op<Scalar>(ArgType0,ArgType1)> {
461 // typedef typename scalar_product_traits<typename remove_all<ArgType0>::type, typename remove_all<ArgType1>::type>::ReturnType type;
462 // };
463 
464 } // end namespace internal
465 
466 namespace numext {
467 
468 #if defined(__CUDA_ARCH__)
469 template<typename T> EIGEN_DEVICE_FUNC   void swap(T &a, T &b) { T tmp = b; b = a; a = tmp; }
470 #else
471 template<typename T> EIGEN_STRONG_INLINE void swap(T &a, T &b) { std::swap(a,b); }
472 #endif
473 
474 #if defined(__CUDA_ARCH__)
475 using internal::device::numeric_limits;
476 #else
477 using std::numeric_limits;
478 #endif
479 
480 // Integer division with rounding up.
481 // T is assumed to be an integer type with a>=0, and b>0
482 template<typename T>
483 T div_ceil(const T &a, const T &b)
484 {
485   return (a+b-1) / b;
486 }
487 
488 } // end namespace numext
489 
490 } // end namespace Eigen
491 
492 #endif // EIGEN_META_H
493