diff options
Diffstat (limited to 'src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector')
12 files changed, 1791 insertions, 0 deletions
diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/array.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/array.h new file mode 100644 index 00000000..0ad9bb36 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/array.h @@ -0,0 +1,165 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_ARRAY_H +#define CGAL_VECTOR_ARRAY_H +#include <boost/type_traits/is_arithmetic.hpp> +#include <boost/utility/enable_if.hpp> +#include <CGAL/Dimension.h> +#include <CGAL/NewKernel_d/utils.h> +#include <CGAL/array.h> +#include <boost/preprocessor/repetition.hpp> +#include <boost/preprocessor/repetition/enum.hpp> + +#include <CGAL/NewKernel_d/Vector/determinant_of_points_from_vectors.h> +#include <CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim.h> +#include <CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_iterator_to_vectors.h> +#include <CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_points.h> +#include <CGAL/NewKernel_d/Vector/determinant_of_iterator_to_vectors_from_vectors.h> + + + +namespace CGAL { + +// May not be safe to use with dim!=max_dim. +// In that case, we should store the real dim next to the array. +template<class NT_,class Dim_,class Max_dim_=Dim_> struct Array_vector { + typedef NT_ NT; + typedef Dim_ Dimension; + typedef Max_dim_ Max_dimension; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef Array_vector< NT, D2, D3 > Other; + }; + template<class> struct Property : boost::false_type {}; + + static const unsigned d_=Max_dim_::value; + CGAL_static_assertion(d_ != (unsigned)UNKNOWN_DIMENSION); + + typedef cpp0x::array<NT,d_> Vector; + struct Construct_vector { + struct Dimension { + // Initialize with NaN if possible? + Vector operator()(unsigned CGAL_assertion_code(d)) const { + CGAL_assertion(d<=d_); + return Vector(); + } + }; + + struct Iterator { + template<typename Iter> + Vector operator()(unsigned CGAL_assertion_code(d),Iter const& f,Iter const& e) const { + CGAL_assertion(d==(unsigned) std::distance(f,e)); + CGAL_assertion(d<=d_); + //TODO: optimize for forward iterators + Vector a; + std::copy(f,e,a.begin()); + return a; + } + }; + +#if 0 + struct Iterator_add_one { + template<typename Iter> + Vector operator()(unsigned d,Iter const& f,Iter const& e) const { + CGAL_assertion(d==std::distance(f,e)+1); + CGAL_assertion(d<=d_); + //TODO: optimize + Vector a; + std::copy(f,e,a.begin()); + a.back()=1; + return a; + } + }; +#endif + + struct Iterator_and_last { + template<typename Iter,typename T> + Vector operator()(unsigned CGAL_assertion_code(d),Iter const& f,Iter const& e,CGAL_FORWARDABLE(T) t) const { + CGAL_assertion(d==std::distance(f,e)+1); + CGAL_assertion(d<=d_); + //TODO: optimize for forward iterators + Vector a; + std::copy(f,e,a.begin()); + a.back()=CGAL_FORWARD(T,t); + return a; + } + }; + + struct Values { +#ifdef CGAL_CXX11 + template<class...U> + Vector operator()(U&&...u) const { + static_assert(sizeof...(U)<=d_,"too many arguments"); + Vector a={{forward_safe<NT,U>(u)...}}; + return a; + } +#else + +#define CGAL_CODE(Z,N,_) Vector operator()(BOOST_PP_ENUM_PARAMS(N,NT const& t)) const { \ + CGAL_assertion(N<=d_); \ + Vector a={{BOOST_PP_ENUM_PARAMS(N,t)}}; \ + return a; \ +} +BOOST_PP_REPEAT_FROM_TO(1, 11, CGAL_CODE, _ ) +#undef CGAL_CODE + +#endif + }; + + struct Values_divide { +#ifdef CGAL_CXX11 + template<class H,class...U> + Vector operator()(H const& h,U&&...u) const { + static_assert(sizeof...(U)<=d_,"too many arguments"); + Vector a={{Rational_traits<NT>().make_rational(std::forward<U>(u),h)...}}; + return a; + } +#else + +#define CGAL_VAR(Z,N,_) Rational_traits<NT>().make_rational( t##N , h) +#define CGAL_CODE(Z,N,_) template <class H> Vector \ + operator()(H const&h, BOOST_PP_ENUM_PARAMS(N,NT const& t)) const { \ + CGAL_assertion(N<=d_); \ + Vector a={{BOOST_PP_ENUM(N,CGAL_VAR,_)}}; \ + return a; \ + } + BOOST_PP_REPEAT_FROM_TO(1, 11, CGAL_CODE, _ ) +#undef CGAL_CODE +#undef CGAL_VAR + +#endif + }; + }; + + typedef NT const* Vector_const_iterator; + static Vector_const_iterator vector_begin(Vector const&a){ + return &a[0]; + } + static Vector_const_iterator vector_end(Vector const&a){ + return &a[0]+d_; // Don't know the real size + } + static unsigned size_of_vector(Vector const&){ + return d_; // Don't know the real size + } + +}; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/avx4.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/avx4.h new file mode 100644 index 00000000..954a3c1b --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/avx4.h @@ -0,0 +1,213 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_AVX4_H +#define CGAL_VECTOR_AVX4_H + +#if !defined __AVX__ || (__GNUC__ * 100 + __GNUC_MINOR__ < 408) +#error Requires AVX and gcc 4.8+ +#endif +#include <x86intrin.h> + +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> +#include <CGAL/enum.h> // CGAL::Sign +#include <CGAL/number_utils.h> // CGAL::sign + + + +namespace CGAL { + + struct Avx_vector_4 { + typedef double NT; + typedef Dimension_tag<4> Dimension; + typedef Dimension_tag<4> Max_dimension; + // No Rebind_dimension, this is a building block + template<class,bool=true> struct Property : boost::false_type {}; + template<bool b> struct Property<Has_vector_plus_minus_tag,b> + : boost::true_type {}; + /* MAYBE? + template<bool b> struct Property<Has_vector_scalar_ops_tag,b> + : boost::true_type {}; + */ + template<bool b> struct Property<Has_determinant_of_vectors_tag,b> + : boost::true_type {}; + template<bool b> struct Property<Has_dot_product_tag,b> + : boost::true_type {}; + template<bool b> struct Property<Has_determinant_of_vectors_omit_last_tag,b> + : boost::true_type {}; + + typedef __m256d Vector; + struct Construct_vector { + struct Dimension { + // Initialize with NaN? + Vector operator()(unsigned d) const { + CGAL_assertion(d==4); + return Vector(); + } + }; + + struct Iterator { + template<typename Iter> + Vector operator()(unsigned d,Iter const& f,Iter const& e) const { + CGAL_assertion(d==4); + double x0 = *f; + double x1 = *++f; + double x2 = *++f; + double x3 = *++f; + CGAL_assertion(++f==e); + Vector a = { x0, x1, x2, x3 }; + return a; + } + }; + + struct Iterator_and_last { + template<typename Iter,typename T> + Vector operator()(unsigned d,Iter const& f,Iter const& e,double t) const { + CGAL_assertion(d==4); + double x0 = *f; + double x1 = *++f; + double x2 = *++f; + CGAL_assertion(++f==e); + Vector a = { x0, x1, x2, t }; + return a; + } + }; + + struct Values { + Vector operator()(double a,double b,double c,double d) const { + Vector r = { a, b, c, d }; + return r; + } + }; + + struct Values_divide { + Vector operator()(double h,double a,double b,double c,double d) const { + // {a,b,c,d}/{h,h,h,h} should be roughly the same + Vector r = { a/h, b/h, c/h, d/h }; + return r; + } + }; + }; + + public: + typedef double const* Vector_const_iterator; + static inline Vector_const_iterator vector_begin(Vector const&a){ + return (Vector_const_iterator)(&a); + } + static inline Vector_const_iterator vector_end(Vector const&a){ + return (Vector_const_iterator)(&a)+4; + } + static inline unsigned size_of_vector(Vector){ + return 4; + } + static inline double dot_product(__m256d x, __m256d y){ + __m256d p=x*y; + __m256d z=_mm256_hadd_pd(p,p); + return z[0]+z[2]; + } + private: + static inline __m256d avx_sym(__m256d x){ +#if 0 + return __builtin_shuffle(x,(__m256i){2,3,0,1}); +#else + return _mm256_permute2f128_pd(x,x,1); +#endif + } + static inline __m256d avx_left(__m256d x){ +#if 0 + return __builtin_shuffle(x,(__m256i){1,2,3,0}); +#else +#ifdef __AVX2__ + return _mm256_permute4x64_pd(x,1+2*4+3*16+0*64); +#else + __m256d s = _mm256_permute2f128_pd(x,x,1); + return _mm256_shuffle_pd(x,s,5); +#endif +#endif + } + static inline __m256d avx_right(__m256d x){ +#if 0 + return __builtin_shuffle(x,(__m256i){3,0,1,2}); +#else +#ifdef __AVX2__ + return _mm256_permute4x64_pd(x,3+0*4+1*16+2*64); +#else + __m256d s = _mm256_permute2f128_pd(x,x,1); + return _mm256_shuffle_pd(s,x,5); +#endif +#endif + } + static inline double avx_altprod(__m256d x, __m256d y){ + __m256d p=x*y; + __m256d z=_mm256_hsub_pd(p,p); + return z[0]+z[2]; + } + public: + static double + determinant_of_vectors(Vector a, Vector b, Vector c, Vector d) { + __m256d x=a*avx_left(b)-avx_left(a)*b; + __m256d yy=a*avx_sym(b); + __m256d y=yy-avx_sym(yy); + __m256d z0=x*avx_sym(c); + __m256d z1=avx_left(x)*c; + __m256d z2=y*avx_left(c); + __m256d z=z0+z1-z2; + return avx_altprod(z,avx_right(d)); + } + static CGAL::Sign + sign_of_determinant_of_vectors(Vector a, Vector b, Vector c, Vector d) { + return CGAL::sign(determinant_of_vectors(a,b,c,d)); + } + + private: + static inline __m256d avx3_right(__m256d x){ +#if 0 + return __builtin_shuffle(x,(__m256i){2,0,1,3}); // can replace 3 with anything +#else +#ifdef __AVX2__ + return _mm256_permute4x64_pd(x,2+0*4+1*16+3*64); +#else + __m256d s = _mm256_permute2f128_pd(x,x,1); + return _mm256_shuffle_pd(s,x,12); +#endif +#endif + } + public: + static inline double dot_product_omit_last(__m256d x, __m256d y){ + __m256d p=x*y; + __m128d q=_mm256_extractf128_pd(p,0); + double z=_mm_hadd_pd(q,q)[0]; + return z+p[2]; + } + // Note: without AVX2, is it faster than the scalar computation? + static double + determinant_of_vectors_omit_last(Vector a, Vector b, Vector c) { + __m256d x=a*avx3_right(b)-avx3_right(a)*b; + return dot_product_omit_last(c,avx3_right(x)); + } + static CGAL::Sign + sign_of_determinant_of_vectors_omit_last(Vector a, Vector b, Vector c) { + return CGAL::sign(determinant_of_vectors_omit_last(a,b,c)); + } + + }; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_iterator_to_vectors.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_iterator_to_vectors.h new file mode 100644 index 00000000..b8efbe28 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_iterator_to_vectors.h @@ -0,0 +1,76 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_DET_ITER_PTS_ITER_VEC_H +#define CGAL_VECTOR_DET_ITER_PTS_ITER_VEC_H +#include <functional> +#include <CGAL/transforming_iterator.h> +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> + +namespace CGAL { + +template <class LA, class Dim_=typename LA::Dimension, + class Max_dim_=typename LA::Max_dimension, + bool = LA::template Property<Has_determinant_of_iterator_to_points_tag>::value, + bool = LA::template Property<Has_determinant_of_iterator_to_vectors_tag>::value> +struct Add_determinant_of_iterator_to_points_from_iterator_to_vectors : LA { + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_iterator_to_vectors<LA2> Other; + }; +}; + +template <class LA, class Dim_,class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_iterator_to_vectors +<LA, Dim_, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_iterator_to_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + // TODO: use std::minus, boost::bind, etc + template<class T> struct Minus_fixed { + T const& a; + Minus_fixed(T const&a_):a(a_){} + T operator()(T const&b)const{return b-a;} + }; + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Minus_fixed<Vector> f(a); + return LA::determinant_of_iterator_to_vectors(make_transforming_iterator(first,f),make_transforming_iterator(end,f)); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Minus_fixed<Vector> f(a); + return LA::sign_of_determinant_of_iterator_to_vectors(make_transforming_iterator(first,f),make_transforming_iterator(end,f)); + } +}; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_points.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_points.h new file mode 100644 index 00000000..71a31d81 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_points_from_points.h @@ -0,0 +1,211 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_DET_ITER_PTS_PTS_H +#define CGAL_VECTOR_DET_ITER_PTS_PTS_H +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> + +namespace CGAL { + +template <class LA, class Dim_=typename LA::Dimension, + class Max_dim_=typename LA::Max_dimension, + bool = LA::template Property<Has_determinant_of_iterator_to_points_tag>::value, + bool = LA::template Property<Has_determinant_of_points_tag>::value> +struct Add_determinant_of_iterator_to_points_from_points : LA { + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; +}; + +//FIXME: Use variadics and boost so it works in any dimension. +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_points +<LA, Dimension_tag<2>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; CGAL_assertion(++first==end); + return LA::determinant_of_points(a,b,c); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_points(a,b,c); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_points +<LA, Dimension_tag<3>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; CGAL_assertion(++first==end); + return LA::determinant_of_points(a,b,c,d); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_points(a,b,c,d); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_points +<LA, Dimension_tag<4>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; CGAL_assertion(++first==end); + return LA::determinant_of_points(a,b,c,d,e); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_points(a,b,c,d,e); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_points +<LA, Dimension_tag<5>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; CGAL_assertion(++first==end); + return LA::determinant_of_points(a,b,c,d,e,f); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_points(a,b,c,d,e,f); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_points_from_points +<LA, Dimension_tag<6>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_points_from_points<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_points_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; ++first; + Vector const&g=*first; CGAL_assertion(++first==end); + return LA::determinant_of_points(a,b,c,d,e,f,g); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_points(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; ++first; + Vector const&g=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_points(a,b,c,d,e,f,g); + } +}; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_vectors_from_vectors.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_vectors_from_vectors.h new file mode 100644 index 00000000..f096d6c7 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_iterator_to_vectors_from_vectors.h @@ -0,0 +1,201 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_DET_ITER_VEC_VEC_H +#define CGAL_VECTOR_DET_ITER_VEC_VEC_H +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> + +namespace CGAL { + +template <class LA, class Dim_=typename LA::Dimension, + class Max_dim_=typename LA::Max_dimension, + bool = LA::template Property<Has_determinant_of_iterator_to_vectors_tag>::value, + bool = LA::template Property<Has_determinant_of_vectors_tag>::value> +struct Add_determinant_of_iterator_to_vectors_from_vectors : LA { + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; +}; + +//FIXME: Use variadics and boost so it works in any dimension. +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_vectors_from_vectors +<LA, Dimension_tag<2>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_vectors_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; CGAL_assertion(++first==end); + return LA::determinant_of_vectors(a,b); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_vectors(a,b); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_vectors_from_vectors +<LA, Dimension_tag<3>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_vectors_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; CGAL_assertion(++first==end); + return LA::determinant_of_vectors(a,b,c); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_vectors(a,b,c); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_vectors_from_vectors +<LA, Dimension_tag<4>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_vectors_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; CGAL_assertion(++first==end); + return LA::determinant_of_vectors(a,b,c,d); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_vectors(a,b,c,d); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_vectors_from_vectors +<LA, Dimension_tag<5>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_vectors_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; CGAL_assertion(++first==end); + return LA::determinant_of_vectors(a,b,c,d,e); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_vectors(a,b,c,d,e); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_iterator_to_vectors_from_vectors +<LA, Dimension_tag<6>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_iterator_to_vectors_from_vectors<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_iterator_to_vectors_tag, D> : + boost::true_type {}; + + template<class Iter> + static NT determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; CGAL_assertion(++first==end); + return LA::determinant_of_vectors(a,b,c,d,e,f); + } + template<class Iter> + static Sign sign_of_determinant_of_iterator_to_vectors(Iter const&first, Iter const&end){ + Vector const&a=*first; ++first; + Vector const&b=*first; ++first; + Vector const&c=*first; ++first; + Vector const&d=*first; ++first; + Vector const&e=*first; ++first; + Vector const&f=*first; CGAL_assertion(++first==end); + return LA::sign_of_determinant_of_vectors(a,b,c,d,e,f); + } +}; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_points_from_vectors.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_points_from_vectors.h new file mode 100644 index 00000000..7ddb73c3 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_points_from_vectors.h @@ -0,0 +1,164 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_DETPTS_H +#define CGAL_VECTOR_DETPTS_H +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> + +namespace CGAL { + +template <class LA, class Dim_=typename LA::Dimension, + class Max_dim_=typename LA::Max_dimension, + bool = LA::template Property<Has_determinant_of_points_tag>::value, + bool = LA::template Property<Has_determinant_of_vectors_tag>::value + && LA::template Property<Has_vector_plus_minus_tag>::value> +struct Add_determinant_of_points_from_vectors_and_minus : LA { + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; +}; + +//FIXME: Use variadics and boost so it works in any dimension. +template <class LA, class Max_dim_> +struct Add_determinant_of_points_from_vectors_and_minus +<LA, Dimension_tag<2>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_points_tag, D> : + boost::true_type {}; + + static NT determinant_of_points(Vector const&a, Vector const&b, + Vector const&c){ + return LA::determinant_of_vectors(b-a,c-a); + } + static Sign sign_of_determinant_of_points(Vector const&a, Vector const&b, + Vector const&c){ + return LA::sign_of_determinant_of_vectors(b-a,c-a); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_points_from_vectors_and_minus +<LA, Dimension_tag<3>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_points_tag, D> : + boost::true_type {}; + + static NT determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d){ + return LA::determinant_of_vectors(b-a,c-a,d-a); + } + static Sign sign_of_determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d){ + return LA::sign_of_determinant_of_vectors(b-a,c-a,d-a); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_points_from_vectors_and_minus +<LA, Dimension_tag<4>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_points_tag, D> : + boost::true_type {}; + + static NT determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e){ + return LA::determinant_of_vectors(b-a,c-a,d-a,e-a); + } + static Sign sign_of_determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e){ + return LA::sign_of_determinant_of_vectors(b-a,c-a,d-a,e-a); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_points_from_vectors_and_minus +<LA, Dimension_tag<5>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_points_tag, D> : + boost::true_type {}; + + static NT determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f){ + return LA::determinant_of_vectors(b-a,c-a,d-a,e-a,f-a); + } + static Sign sign_of_determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f){ + return LA::sign_of_determinant_of_vectors(b-a,c-a,d-a,e-a,f-a); + } +}; + +template <class LA, class Max_dim_> +struct Add_determinant_of_points_from_vectors_and_minus +<LA, Dimension_tag<6>, Max_dim_, false, true> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef Add_determinant_of_points_from_vectors_and_minus<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<Has_determinant_of_points_tag, D> : + boost::true_type {}; + + static NT determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f, + Vector const&g){ + return LA::determinant_of_vectors(b-a,c-a,d-a,e-a,f-a,g-a); + } + static Sign sign_of_determinant_of_points(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f, + Vector const&g){ + return LA::sign_of_determinant_of_vectors(b-a,c-a,d-a,e-a,f-a,g-a); + } +}; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim.h new file mode 100644 index 00000000..64eafe69 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim.h @@ -0,0 +1,58 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_DETVEC_SMALL_H +#define CGAL_VECTOR_DETVEC_SMALL_H +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> +#include <CGAL/determinant_of_vectors.h> + +#define CGAL_ALLOWED_INCLUSION 1 + +#define CGAL_CLASS Add_determinant_of_vectors_small_dim +#define CGAL_TAG Has_determinant_of_vectors_tag +#define CGAL_FUNC determinant_of_vectors +#define CGAL_SIGN_FUNC sign_of_determinant_of_vectors +#define CGAL_SHIFT 0 + +#include <CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim_internal.h> + +#undef CGAL_CLASS +#undef CGAL_TAG +#undef CGAL_FUNC +#undef CGAL_SIGN_FUNC +#undef CGAL_SHIFT + +#define CGAL_CLASS Add_determinant_of_vectors_omit_last_small_dim +#define CGAL_TAG Has_determinant_of_vectors_omit_last_tag +#define CGAL_FUNC determinant_of_vectors_omit_last +#define CGAL_SIGN_FUNC sign_of_determinant_of_vectors_omit_last +#define CGAL_SHIFT 1 + +#include <CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim_internal.h> + +#undef CGAL_CLASS +#undef CGAL_TAG +#undef CGAL_FUNC +#undef CGAL_SIGN_FUNC +#undef CGAL_SHIFT + +#undef CGAL_ALLOWED_INCLUSION + +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim_internal.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim_internal.h new file mode 100644 index 00000000..b4856742 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/determinant_of_vectors_small_dim_internal.h @@ -0,0 +1,164 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_ALLOWED_INCLUSION +#error Must not include this header directly +#endif +#if !defined(CGAL_TAG) \ + || ! defined(CGAL_CLASS) \ + || ! defined(CGAL_FUNC) \ + || ! defined(CGAL_SIGN_FUNC) \ + || ! defined(CGAL_SHIFT) + +#error Forgot one macro +#endif + +namespace CGAL { + +template <class LA, class Dim_=typename LA::Dimension, + class Max_dim_=typename LA::Max_dimension, + bool=LA::template Property<CGAL_TAG>::value> +struct CGAL_CLASS : LA { + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; +}; + +template <class LA, class Max_dim_> +struct CGAL_CLASS +<LA, Dimension_tag<2+CGAL_SHIFT>, Max_dim_, false> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<CGAL_TAG, D> : + boost::true_type {}; + + static NT CGAL_FUNC(Vector const&a, Vector const&b){ + return CGAL::determinant_of_vectors<NT>(a,b); + } + template <class V1, class V2> + static Sign CGAL_SIGN_FUNC(V1 const&a, V2 const&b){ + return CGAL::sign_of_determinant_of_vectors<NT>(a,b); + } +}; + +template <class LA, class Max_dim_> +struct CGAL_CLASS +<LA, Dimension_tag<3+CGAL_SHIFT>, Max_dim_, false> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<CGAL_TAG, D> : + boost::true_type {}; + + static NT CGAL_FUNC(Vector const&a, Vector const&b, + Vector const&c){ + return CGAL::determinant_of_vectors<NT>(a,b,c); + } + static Sign CGAL_SIGN_FUNC(Vector const&a, Vector const&b, + Vector const&c){ + return CGAL::sign_of_determinant_of_vectors<NT>(a,b,c); + } +}; + +template <class LA, class Max_dim_> +struct CGAL_CLASS +<LA, Dimension_tag<4+CGAL_SHIFT>, Max_dim_, false> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<CGAL_TAG, D> : + boost::true_type {}; + + static NT CGAL_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d){ + return CGAL::determinant_of_vectors<NT>(a,b,c,d); + } + static Sign CGAL_SIGN_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d){ + return CGAL::sign_of_determinant_of_vectors<NT>(a,b,c,d); + } +}; + +template <class LA, class Max_dim_> +struct CGAL_CLASS +<LA, Dimension_tag<5+CGAL_SHIFT>, Max_dim_, false> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<CGAL_TAG, D> : + boost::true_type {}; + + static NT CGAL_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e){ + return CGAL::determinant_of_vectors<NT>(a,b,c,d,e); + } + static Sign CGAL_SIGN_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e){ + return CGAL::sign_of_determinant_of_vectors<NT>(a,b,c,d,e); + } +}; + +template <class LA, class Max_dim_> +struct CGAL_CLASS +<LA, Dimension_tag<6+CGAL_SHIFT>, Max_dim_, false> : LA { + typedef typename LA::NT NT; + typedef typename LA::Vector Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef typename LA::template Rebind_dimension<D2,D3> LA2; + typedef CGAL_CLASS<LA2> Other; + }; + template<class P,class=void> struct Property : LA::template Property<P> {}; + template<class D> struct Property<CGAL_TAG, D> : + boost::true_type {}; + + static NT CGAL_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f){ + return CGAL::determinant_of_vectors<NT>(a,b,c,d,e,f); + } + static Sign CGAL_SIGN_FUNC(Vector const&a, Vector const&b, + Vector const&c, Vector const&d, Vector const&e, Vector const&f){ + return CGAL::sign_of_determinant_of_vectors<NT>(a,b,c,d,e,f); + } +}; + +} diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/mix.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/mix.h new file mode 100644 index 00000000..d4cfeeb1 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/mix.h @@ -0,0 +1,46 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_KD_MIX_VECTOR_H +#define CGAL_KD_MIX_VECTOR_H +#include <CGAL/Dimension.h> +namespace CGAL { + +template <class Static_, class Dynamic_, class NT_ ,class Dim_, class Max_dim_ = Dim_> +struct Mix_vector +: Dynamic_::template Rebind_dimension<Dim_, Max_dim_>::Other +{ + template <class D2, class D3 = D2> + struct Rebind_dimension { + typedef Mix_vector<Static_, Dynamic_, NT_, D2, D3> Other; + }; +}; + +template <class Static_, class Dynamic_, class NT_, int d, class Max_dim_> +struct Mix_vector<Static_, Dynamic_, NT_, Dimension_tag<d>, Max_dim_> +: Static_::template Rebind_dimension<Dimension_tag<d>, Max_dim_>::Other +{ + template <class D2, class D3 = D2> + struct Rebind_dimension { + typedef Mix_vector<Static_, Dynamic_, NT_, D2, D3> Other; + }; +}; +} +#endif + diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/sse2.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/sse2.h new file mode 100644 index 00000000..2a75385c --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/sse2.h @@ -0,0 +1,145 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_SSE2_H +#define CGAL_VECTOR_SSE2_H + +// Check what needs adapting for clang, intel and microsoft +#if !defined __SSE2__ || (__GNUC__ * 100 + __GNUC_MINOR__ < 408) +#error Requires SSE2 and gcc 4.8+ +#endif +#include <x86intrin.h> // FIXME: other platforms call it differently + +#include <CGAL/NewKernel_d/functor_tags.h> +#include <CGAL/Dimension.h> +#include <CGAL/enum.h> // CGAL::Sign +#include <CGAL/number_utils.h> // CGAL::sign + + + +namespace CGAL { + + struct Sse_vector_2 { + typedef double NT; + typedef Dimension_tag<2> Dimension; + typedef Dimension_tag<2> Max_dimension; + // No Rebind_dimension, this is a building block + template<class,bool=true> struct Property : boost::false_type {}; + template<bool b> struct Property<Has_vector_plus_minus_tag,b> + : boost::true_type {}; + /* MAYBE? + template<bool b> struct Property<Has_vector_scalar_ops_tag,b> + : boost::true_type {}; + */ + template<bool b> struct Property<Has_determinant_of_vectors_tag,b> + : boost::true_type {}; + template<bool b> struct Property<Has_dot_product_tag,b> + : boost::true_type {}; + + typedef __m128d Vector; + struct Construct_vector { + struct Dimension { + // Initialize with NaN? + Vector operator()(unsigned d) const { + CGAL_assertion(d==2); + return Vector(); + } + }; + + struct Iterator { + template<typename Iter> + Vector operator()(unsigned d,Iter const& f,Iter const& e) const { + CGAL_assertion(d==2); + double x0 = *f; + double x1 = *++f; + CGAL_assertion(++f==e); + Vector a = { x0, x1 }; + return a; + } + }; + + struct Iterator_and_last { + template<typename Iter,typename T> + Vector operator()(unsigned d,Iter const& f,Iter const& e,double t) const { + CGAL_assertion(d==2); + Vector a = { *f, t }; + CGAL_assertion(++f==e); + return a; + } + }; + + struct Values { + Vector operator()(double a,double b) const { + Vector r = { a, b }; + return r; + } + }; + + struct Values_divide { + Vector operator()(double h,double a,double b) const { + // {a,b}/{h,h} is probably slower + Vector r = { a/h, b/h }; + return r; + } + }; + }; + + typedef double const* Vector_const_iterator; + static inline Vector_const_iterator vector_begin(Vector const&a){ + return (Vector_const_iterator)(&a); + } + static inline Vector_const_iterator vector_end(Vector const&a){ + return (Vector_const_iterator)(&a)+2; + } + static inline unsigned size_of_vector(Vector){ + return 2; + } + public: + + static double determinant_of_vectors(Vector a, Vector b) { + __m128d c = _mm_shuffle_pd (b, b, 1); // b1, b0 + __m128d d = a * c; // a0*b1, a1*b0 +#ifdef __SSE3__ + __m128d e = _mm_hsub_pd (d, d); + return e[0]; +#else + return d[0]-d[1]; +#endif + } + static CGAL::Sign sign_of_determinant_of_vectors(Vector a, Vector b) { + return CGAL::sign(determinant_of_vectors(a,b)); + } + + static double dot_product(Vector a,Vector b){ +#ifdef __SSE4_1__ + return _mm_dp_pd (a, b, 1+16+32)[0]; +#else + __m128d p = a * b; +#if defined __SSE3__ + __m128d s = _mm_hadd_pd (p, p); + return s[0]; +#else + return p[0]+p[1]; +#endif +#endif + }; + }; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/v2int.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/v2int.h new file mode 100644 index 00000000..b85a3734 --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/v2int.h @@ -0,0 +1,181 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_2INT_H +#define CGAL_VECTOR_2INT_H + +#include <stdint.h> +#include <cmath> +#include <CGAL/array.h> +#include <CGAL/Dimension.h> +#include <CGAL/enum.h> +#include <CGAL/number_utils.h> +#include <CGAL/NT_converter.h> +#include <CGAL/transforming_iterator.h> +#include <CGAL/determinant_of_vectors.h> +#include <CGAL/NewKernel_d/functor_tags.h> + + +// What are the pros and cons of having NT be int vs double? + +namespace CGAL { + struct Vector_2_int_prop1 { + typedef double NT; // try lying a bit + typedef int32_t NT1; // what is really stored + typedef int32_t NT1b; // slightly longer + typedef int_fast64_t NT2; // longer type for computations + typedef int_fast64_t NT2b; // slightly longer + bool check_limits(int32_t x){return std::abs(x)<(1<<30);} + // TODO: find nice bounds + }; +#ifdef __SIZEOF_INT128__ + struct Vector_2_int_prop2 { + typedef double NT; + typedef int32_t NT1; + typedef int_fast64_t NT1b; + typedef int_fast64_t NT2; + typedef __int128 NT2b; + bool check_limits(int32_t){return true;} + // take a template/int64_t input and still check the limits? + }; + struct Vector_2_int_prop3 { + typedef long double NT; + typedef int64_t NT1; + typedef int64_t NT1b; + typedef __int128 NT2; + typedef __int128 NT2b; + enum { has_limit=true }; + bool check_limits(int32_t x){return std::abs(x)<(1L<<62);} + // TODO: find nice bounds + }; +#endif + + template<class Prop=Vector_2_int_prop1> + struct Vector_2_int : Prop { + using typename Prop::NT; + using typename Prop::NT1; + using typename Prop::NT1b; + using typename Prop::NT2; + using typename Prop::NT2b; + using Prop::check_limits; + + typedef Dimension_tag<2> Dimension; + typedef Dimension_tag<2> Max_dimension; + // No Rebind_dimension, this is a building block + template<class,bool=true> struct Property : boost::false_type {}; + //template<bool b> struct Property<Has_vector_plus_minus_tag,b> + // : boost::true_type {}; + template<bool b> struct Property<Has_determinant_of_vectors_tag,b> + : boost::true_type {}; + //template<bool b> struct Property<Has_determinant_of_points_tag,b> + // : boost::true_type {}; + // Advertise somehow that the sign_of_determinant* are exact? + + typedef cpp0x::array<NT1,2> Vector; + struct Construct_vector { + struct Dimension { + Vector operator()(unsigned d) const { + CGAL_assertion(d==2); + return Vector(); + } + }; + + // TODO (for all constructors): check that input fits in NT1... + struct Iterator { + template<typename Iter> + Vector operator()(unsigned d,Iter const& f,Iter const& e) const { + CGAL_assertion(d==2); + NT1 x0 = *f; + NT1 x1 = *++f; + CGAL_assertion (++f == e); + CGAL_assertion (check_limits(x0) && check_limits(x1)); + Vector a = { x0, x1 }; + return a; + } + }; + + struct Iterator_and_last { + template<typename Iter,typename T> + Vector operator()(unsigned d,Iter const& f,Iter const& e,double t) const { + CGAL_assertion(d==2); + NT1 x = *f; + CGAL_assertion (++f == e); + CGAL_assertion (check_limits(x) && check_limits(t)); + Vector a = { x, t }; + return a; + } + }; + + struct Values { + Vector operator()(NT1 a,NT1 b) const { + CGAL_assertion (check_limits(a) && check_limits(b)); + Vector r = { a, b }; + return r; + } + }; + + /* + // Maybe safer not to provide it + struct Values_divide { + Vector operator()(double h,double a,double b) const { + Vector r = { a/h, b/h }; + return r; + } + }; + */ + }; + + // Since we lie about NT, be consistent about it + typedef transforming_iterator<NT_converter<NT1,NT>,NT1 const*> Vector_const_iterator; + static inline Vector_const_iterator vector_begin(Vector const&a){ + return Vector_const_iterator(a.begin()); + } + static inline Vector_const_iterator vector_end(Vector const&a){ + return Vector_const_iterator(a.end()); + } + static inline unsigned size_of_vector(Vector){ + return 2; + } + + // for unsigned NT1, check what changes to do. + // return NT or NT2? + static NT determinant_of_vectors(Vector a, Vector b) { + return CGAL::determinant_of_vectors<NT2>(a,b); + } + static CGAL::Sign sign_of_determinant_of_vectors(Vector a, Vector b) { + return CGAL::sign_of_determinant_of_vectors<NT2>(a,b); + } + + static NT determinant_of_points(Vector a, Vector b, Vector c) { + // could be faster to convert to NT directly + NT1b a0=a[0]; NT1b a1=a[1]; + NT1b x0=b[0]-a0; NT1b x1=b[1]-a1; + NT1b y0=c[0]-a0; NT1b y1=c[1]-a1; + return CGAL::determinant<NT>(x0,x1,y0,y1); + } + static CGAL::Sign sign_of_determinant_of_points(Vector a, Vector b, Vector c) { + NT1b a0=a[0]; NT1b a1=a[1]; + NT1b x0=b[0]-a0; NT1b x1=b[1]-a1; + NT2b y0=c[0]-a0; NT2b y1=c[1]-a1; + return CGAL::compare(x0*y1,x1*y0); + } + }; + +} +#endif diff --git a/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/vector.h b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/vector.h new file mode 100644 index 00000000..f9cc4e3c --- /dev/null +++ b/src/common/include/gudhi_patches/CGAL/NewKernel_d/Vector/vector.h @@ -0,0 +1,167 @@ +// Copyright (c) 2014 +// INRIA Saclay-Ile de France (France) +// +// This file is part of CGAL (www.cgal.org); you can redistribute it and/or +// modify it under the terms of the GNU Lesser General Public License as +// published by the Free Software Foundation; either version 3 of the License, +// or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Marc Glisse + +#ifndef CGAL_VECTOR_VECTOR_H +#define CGAL_VECTOR_VECTOR_H +#include <boost/type_traits/is_arithmetic.hpp> +#include <boost/utility/enable_if.hpp> +#include <CGAL/Dimension.h> +#include <CGAL/NewKernel_d/utils.h> +#include <vector> +#include <boost/preprocessor/repetition.hpp> +#include <boost/preprocessor/repetition/enum.hpp> +namespace CGAL { + +//Derive from a class that doesn't depend on Dim, or still use Dim for checking? +template<class NT_,class Dim_,class Max_dim_=Dim_> struct Vector_vector { + typedef NT_ NT; + typedef Dim_ Dimension; + typedef Max_dim_ Max_dimension; + typedef std::vector<NT> Vector; + template< class D2, class D3=D2 > + struct Rebind_dimension { + typedef Vector_vector< NT, D2, D3 > Other; + }; + template<class> struct Property : boost::false_type {}; + + struct Construct_vector { + struct Dimension { + Vector operator()(int d) const { + return Vector(d); + } + }; + + struct Iterator { + template<typename Iter> + Vector operator()(int CGAL_assertion_code(d),Iter const& f,Iter const& e) const { + CGAL_assertion(d==std::distance(f,e)); + return Vector(f,e); + } + }; + + // unneeded thanks to Iterator_and_last? +#if 0 + struct Iterator_add_one { + template<typename Iter> + Vector operator()(int CGAL_assertion_code(d),Iter const& f,Iter const& e) const { + CGAL_assertion(d==std::distance(f,e)+1); + Vector a; + a.reserve(d+1); + a.insert(a.end(),f,e); + a.push_back(1); + return a; + } + }; +#endif + + struct Iterator_and_last { + template<typename Iter,typename T> + Vector operator()(int d,Iter const& f,Iter const& e,CGAL_FORWARDABLE(T) t) const { + CGAL_assertion(d==std::distance(f,e)+1); + Vector a; + a.reserve(d+1); + a.insert(a.end(),f,e); + a.push_back(CGAL_FORWARD(T,t)); + return a; + } + }; + + // useless, use a transform_iterator? +#if 0 + struct Iterator_and_last_divide { + template<typename Iter,typename T> + Vector operator()(int d,Iter f,Iter const& e,T const&t) const { + CGAL_assertion(d==std::distance(f,e)+1); + Vector a; + a.reserve(d+1); + for(;f!=e;++f){ + a.push_back(*f/t); + } + return a; + } + }; +#endif + + struct Values { +#ifdef CGAL_CXX11 + template<class...U> + Vector operator()(U&&...u) const { + //TODO: check the right number of {}, g++ accepts one and two + Vector a={forward_safe<NT,U>(u)...}; + return a; + } +#else + +#define CGAL_VAR(Z,N,_) a.push_back(t##N); +#define CGAL_CODE(Z,N,_) Vector operator()(BOOST_PP_ENUM_PARAMS(N,NT const& t)) const { \ + Vector a; \ + a.reserve(N); \ + BOOST_PP_REPEAT(N,CGAL_VAR,) \ + return a; \ +} +BOOST_PP_REPEAT_FROM_TO(1, 11, CGAL_CODE, _ ) +#undef CGAL_CODE +#undef CGAL_VAR + +#endif + }; + + struct Values_divide { +#ifdef CGAL_CXX11 + template<class H,class...U> + Vector operator()(H const&h,U&&...u) const { + //TODO: do we want to cast at some point? + //e.g. to avoid 1/2 in integers + // ==> use Rational_traits<NT>().make_rational(x,y) ? + Vector a={Rational_traits<NT>().make_rational(std::forward<U>(u),h)...}; + return a; + } +#else + +#define CGAL_VAR(Z,N,_) a.push_back(Rational_traits<NT>().make_rational( t##N ,h)); +#define CGAL_CODE(Z,N,_) template<class H> Vector \ + operator()(H const&h, BOOST_PP_ENUM_PARAMS(N,NT const& t)) const { \ + Vector a; \ + a.reserve(N); \ + BOOST_PP_REPEAT(N,CGAL_VAR,) \ + return a; \ + } + BOOST_PP_REPEAT_FROM_TO(1, 11, CGAL_CODE, _ ) +#undef CGAL_CODE +#undef CGAL_VAR + +#endif + }; + }; + typedef typename Vector::const_iterator Vector_const_iterator; + static Vector_const_iterator vector_begin(Vector const&a){ + return a.begin(); + } + static Vector_const_iterator vector_end(Vector const&a){ + return a.end(); + } + static int size_of_vector(Vector const&a){ + return (int)a.size(); + } +}; + + +} +#endif + |