|
BWAPI
|
00001 // Copyright (c) 2008 Max-Planck-Institute Saarbruecken (Germany). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00005 // modify it under the terms of the GNU Lesser General Public License as 00006 // published by the Free Software Foundation; version 2.1 of the License. 00007 // See the file LICENSE.LGPL distributed with CGAL. 00008 // 00009 // Licensees holding a valid commercial license may use this file in 00010 // accordance with the commercial license agreement provided with the software. 00011 // 00012 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00013 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00014 // 00015 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Polynomial/include/CGAL/Polynomial_traits_d.h $ 00016 // $Id: Polynomial_traits_d.h 48562 2009-03-27 17:30:16Z mkerber $ 00017 // 00018 // 00019 // Author(s) : Michael Hemmer <hemmer@informatik.uni-mainz.de> 00020 // Sebastian Limbach <slimbach@mpi-inf.mpg.de> 00021 // 00022 // ============================================================================ 00023 #ifndef CGAL_POLYNOMIAL_TRAITS_D_H 00024 #define CGAL_POLYNOMIAL_TRAITS_D_H 00025 00026 #include <CGAL/basic.h> 00027 #include <functional> 00028 #include <list> 00029 #include <vector> 00030 #include <utility> 00031 00032 #include <CGAL/Polynomial/fwd.h> 00033 #include <CGAL/Polynomial/misc.h> 00034 #include <CGAL/Polynomial/Polynomial_type.h> 00035 #include <CGAL/polynomial_utils.h> 00036 #include <CGAL/Polynomial/square_free_factorize.h> 00037 #include <CGAL/Polynomial/modular_filter.h> 00038 #include <CGAL/extended_euclidean_algorithm.h> 00039 #include <CGAL/Polynomial/resultant.h> 00040 #include <CGAL/Polynomial/subresultants.h> // not in release 3.4 00041 #include <CGAL/Polynomial/sturm_habicht_sequence.h> // not in release 3.4 00042 00043 00044 #define CGAL_POLYNOMIAL_TRAITS_D_BASE_TYPEDEFS \ 00045 private: \ 00046 typedef Polynomial_traits_d< Polynomial< Coefficient_type_ > > PT; \ 00047 typedef Polynomial_traits_d< Coefficient_type_ > PTC; \ 00048 \ 00049 typedef Polynomial<Coefficient_type_> Polynomial_d; \ 00050 typedef Coefficient_type_ Coefficient_type; \ 00051 \ 00052 typedef typename Innermost_coefficient_type<Polynomial_d>::Type \ 00053 Innermost_coefficient_type; \ 00054 static const int d = Dimension<Polynomial_d>::value; \ 00055 \ 00056 \ 00057 typedef std::pair< Exponent_vector, Innermost_coefficient_type > \ 00058 Exponents_coeff_pair; \ 00059 typedef std::vector< Exponents_coeff_pair > Monom_rep; \ 00060 \ 00061 typedef CGAL::Recursive_const_flattening< d-1, \ 00062 typename CGAL::Polynomial<Coefficient_type>::const_iterator > \ 00063 Coefficient_const_flattening; \ 00064 \ 00065 typedef typename \ 00066 Coefficient_const_flattening::Recursive_flattening_iterator \ 00067 Innermost_coefficient_const_iterator; \ 00068 \ 00069 typedef typename Polynomial_d::const_iterator \ 00070 Coefficient_const_iterator; \ 00071 \ 00072 typedef std::pair<Innermost_coefficient_const_iterator, \ 00073 Innermost_coefficient_const_iterator> \ 00074 Innermost_coefficient_const_iterator_range; \ 00075 \ 00076 typedef std::pair<Coefficient_const_iterator, \ 00077 Coefficient_const_iterator> \ 00078 Coefficient_const_iterator_range; \ 00079 00080 00081 00082 CGAL_BEGIN_NAMESPACE; 00083 00084 namespace CGALi { 00085 00086 // Base class for functors depending on the algebraic category of the 00087 // innermost coefficient 00088 template< class Coefficient_type_, class ICoeffAlgebraicCategory > 00089 class Polynomial_traits_d_base_icoeff_algebraic_category { 00090 public: 00091 typedef Null_functor Multivariate_content; 00092 }; 00093 00094 // Specializations 00095 template< class Coefficient_type_ > 00096 class Polynomial_traits_d_base_icoeff_algebraic_category< 00097 Polynomial< Coefficient_type_ >, Integral_domain_without_division_tag > 00098 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00099 Polynomial< Coefficient_type_ >, Null_tag > {}; 00100 00101 template< class Coefficient_type_ > 00102 class Polynomial_traits_d_base_icoeff_algebraic_category< 00103 Polynomial< Coefficient_type_ >, Integral_domain_tag > 00104 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00105 Polynomial< Coefficient_type_ >, Integral_domain_without_division_tag > {}; 00106 00107 template< class Coefficient_type_ > 00108 class Polynomial_traits_d_base_icoeff_algebraic_category< 00109 Polynomial< Coefficient_type_ >, Unique_factorization_domain_tag > 00110 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00111 Polynomial< Coefficient_type_ >, Integral_domain_tag > { 00112 CGAL_POLYNOMIAL_TRAITS_D_BASE_TYPEDEFS 00113 00114 public: 00115 00116 00117 struct Multivariate_content 00118 : public std::unary_function< Polynomial_d , Innermost_coefficient_type >{ 00119 Innermost_coefficient_type 00120 operator()(const Polynomial_d& p) const { 00121 typedef Innermost_coefficient_const_iterator IT; 00122 Innermost_coefficient_type content(0); 00123 typename PT::Construct_innermost_coefficient_const_iterator_range range; 00124 for (IT it = range(p).first; it != range(p).second; it++){ 00125 content = CGAL::gcd(content, *it); 00126 if(CGAL::is_one(content)) break; 00127 } 00128 return content; 00129 } 00130 }; 00131 }; 00132 00133 template< class Coefficient_type_ > 00134 class Polynomial_traits_d_base_icoeff_algebraic_category< 00135 Polynomial< Coefficient_type_ >, Euclidean_ring_tag > 00136 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00137 Polynomial< Coefficient_type_ >, Unique_factorization_domain_tag > 00138 {}; 00139 00140 template< class Coefficient_type_ > 00141 class Polynomial_traits_d_base_icoeff_algebraic_category< 00142 Polynomial< Coefficient_type_ >, Field_tag > 00143 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00144 Polynomial< Coefficient_type_ >, Integral_domain_tag > { 00145 CGAL_POLYNOMIAL_TRAITS_D_BASE_TYPEDEFS 00146 00147 public: 00148 00149 // Multivariate_content; 00150 struct Multivariate_content 00151 : public std::unary_function< Polynomial_d , Innermost_coefficient_type >{ 00152 Innermost_coefficient_type operator()(const Polynomial_d& p) const { 00153 if( CGAL::is_zero(p) ) 00154 return Innermost_coefficient_type(0); 00155 else 00156 return Innermost_coefficient_type(1); 00157 } 00158 }; 00159 }; 00160 00161 template< class Coefficient_type_ > 00162 class Polynomial_traits_d_base_icoeff_algebraic_category< 00163 Polynomial< Coefficient_type_ >, Field_with_sqrt_tag > 00164 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00165 Polynomial< Coefficient_type_ >, Field_tag > {}; 00166 00167 template< class Coefficient_type_ > 00168 class Polynomial_traits_d_base_icoeff_algebraic_category< 00169 Polynomial< Coefficient_type_ >, Field_with_kth_root_tag > 00170 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00171 Polynomial< Coefficient_type_ >, Field_with_sqrt_tag > {}; 00172 00173 template< class Coefficient_type_ > 00174 class Polynomial_traits_d_base_icoeff_algebraic_category< 00175 Polynomial< Coefficient_type_ >, Field_with_root_of_tag > 00176 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00177 Polynomial< Coefficient_type_ >, Field_with_kth_root_tag > {}; 00178 00179 // Base class for functors depending on the algebraic category of the 00180 // Polynomial type 00181 template< class Coefficient_type_, class PolynomialAlgebraicCategory > 00182 class Polynomial_traits_d_base_polynomial_algebraic_category { 00183 public: 00184 typedef Null_functor Univariate_content; 00185 typedef Null_functor Square_free_factorize; 00186 }; 00187 00188 // Specializations 00189 template< class Coefficient_type_ > 00190 class Polynomial_traits_d_base_polynomial_algebraic_category< 00191 Polynomial< Coefficient_type_ >, Integral_domain_without_division_tag > 00192 : public Polynomial_traits_d_base_polynomial_algebraic_category< 00193 Polynomial< Coefficient_type_ >, Null_tag > {}; 00194 00195 template< class Coefficient_type_ > 00196 class Polynomial_traits_d_base_polynomial_algebraic_category< 00197 Polynomial< Coefficient_type_ >, Integral_domain_tag > 00198 : public Polynomial_traits_d_base_polynomial_algebraic_category< 00199 Polynomial< Coefficient_type_ >, Integral_domain_without_division_tag > {}; 00200 00201 template< class Coefficient_type_ > 00202 class Polynomial_traits_d_base_polynomial_algebraic_category< 00203 Polynomial< Coefficient_type_ >, Unique_factorization_domain_tag > 00204 : public Polynomial_traits_d_base_polynomial_algebraic_category< 00205 Polynomial< Coefficient_type_ >, Integral_domain_tag > { 00206 CGAL_POLYNOMIAL_TRAITS_D_BASE_TYPEDEFS 00207 00208 public: 00209 00210 // Univariate_content 00211 struct Univariate_content 00212 : public std::unary_function< Polynomial_d , Coefficient_type>{ 00213 Coefficient_type operator()(const Polynomial_d& p) const { 00214 return p.content(); 00215 } 00216 }; 00217 00218 // Square_free_factorize; 00219 struct Square_free_factorize{ 00220 00221 template < class OutputIterator > 00222 OutputIterator operator()( const Polynomial_d& p, OutputIterator oi) const { 00223 std::vector<Polynomial_d> factors; 00224 std::vector<int> mults; 00225 00226 square_free_factorize 00227 ( p, std::back_inserter(factors), std::back_inserter(mults) ); 00228 00229 CGAL_postcondition( factors.size() == mults.size() ); 00230 for(unsigned int i = 0; i < factors.size(); i++){ 00231 *oi++=std::make_pair(factors[i],mults[i]); 00232 } 00233 00234 return oi; 00235 } 00236 00237 template< class OutputIterator > 00238 OutputIterator operator()( 00239 const Polynomial_d& p , 00240 OutputIterator oi, 00241 Innermost_coefficient_type& a ) const { 00242 00243 if( CGAL::is_zero(p) ) { 00244 a = Innermost_coefficient_type(0); 00245 return oi; 00246 } 00247 00248 typedef Polynomial_traits_d< Polynomial_d > PT; 00249 typename PT::Innermost_leading_coefficient ilcoeff; 00250 typename PT::Multivariate_content mcontent; 00251 a = CGAL::unit_part( ilcoeff( p ) ) * mcontent( p ); 00252 00253 return (*this)( p/Polynomial_d(a), oi); 00254 } 00255 }; 00256 }; 00257 00258 template< class Coefficient_type_ > 00259 class Polynomial_traits_d_base_polynomial_algebraic_category< 00260 Polynomial< Coefficient_type_ >, Euclidean_ring_tag > 00261 : public Polynomial_traits_d_base_polynomial_algebraic_category< 00262 Polynomial< Coefficient_type_ >, Unique_factorization_domain_tag > {}; 00263 00264 00265 // Polynomial_traits_d_base class connecting the two base classes which depend 00266 // on the algebraic category of the innermost coefficient type and the poly- 00267 // nomial type. 00268 00269 // First the general base class for the innermost coefficient 00270 template< class InnermostCoefficient_type, 00271 class ICoeffAlgebraicCategory, class PolynomialAlgebraicCategory > 00272 class Polynomial_traits_d_base { 00273 typedef InnermostCoefficient_type ICoeff; 00274 public: 00275 static const int d = 0; 00276 00277 typedef ICoeff Polynomial_d; 00278 typedef ICoeff Coefficient_type; 00279 typedef ICoeff Innermost_coefficient_type; 00280 00281 struct Degree 00282 : public std::unary_function< ICoeff , int > { 00283 int operator()(const ICoeff&) const { return 0; } 00284 }; 00285 struct Total_degree 00286 : public std::unary_function< ICoeff , int > { 00287 int operator()(const ICoeff&) const { return 0; } 00288 }; 00289 00290 typedef Null_functor Construct_polynomial; 00291 typedef Null_functor Get_coefficient; 00292 typedef Null_functor Leading_coefficient; 00293 typedef Null_functor Univariate_content; 00294 typedef Null_functor Multivariate_content; 00295 typedef Null_functor Shift; 00296 typedef Null_functor Negate; 00297 typedef Null_functor Invert; 00298 typedef Null_functor Translate; 00299 typedef Null_functor Translate_homogeneous; 00300 typedef Null_functor Scale_homogeneous; 00301 typedef Null_functor Differentiate; 00302 00303 struct Is_square_free 00304 : public std::unary_function< ICoeff, bool > { 00305 bool operator()( const ICoeff& ) const { 00306 return true; 00307 } 00308 }; 00309 00310 struct Make_square_free 00311 : public std::unary_function< ICoeff, ICoeff>{ 00312 ICoeff operator()( const ICoeff& x ) const { 00313 if (CGAL::is_zero(x)) return x ; 00314 else return ICoeff(1); 00315 } 00316 }; 00317 00318 typedef Null_functor Square_free_factorize; 00319 typedef Null_functor Pseudo_division; 00320 typedef Null_functor Pseudo_division_remainder; 00321 typedef Null_functor Pseudo_division_quotient; 00322 00323 struct Gcd_up_to_constant_factor 00324 : public std::binary_function< ICoeff, ICoeff, ICoeff >{ 00325 ICoeff operator()(const ICoeff& x, const ICoeff& y) const { 00326 if (CGAL::is_zero(x) && CGAL::is_zero(y)) 00327 return ICoeff(0); 00328 else 00329 return ICoeff(1); 00330 } 00331 }; 00332 00333 typedef Null_functor Integral_division_up_to_constant_factor; 00334 00335 struct Univariate_content_up_to_constant_factor 00336 : public std::unary_function< ICoeff, ICoeff >{ 00337 ICoeff operator()(const ICoeff& ) const { 00338 // TODO: Why not return 0 if argument is 0 ? 00339 return ICoeff(1); 00340 } 00341 }; 00342 00343 typedef Null_functor Square_free_factorize_up_to_constant_factor; 00344 typedef Null_functor Resultant; 00345 typedef Null_functor Canonicalize; 00346 typedef Null_functor Evaluate_homogeneous; 00347 00348 struct Innermost_leading_coefficient 00349 :public std::unary_function <ICoeff, ICoeff>{ 00350 ICoeff operator()(const ICoeff& x){return x;} 00351 }; 00352 00353 struct Degree_vector{ 00354 typedef Exponent_vector result_type; 00355 typedef Coefficient_type argument_type; 00356 // returns the exponent vector of inner_most_lcoeff. 00357 result_type operator()(const Coefficient_type&) const{ 00358 return Exponent_vector(); 00359 } 00360 }; 00361 00362 struct Get_innermost_coefficient 00363 : public std::binary_function< ICoeff, Polynomial_d, Exponent_vector > { 00364 00365 ICoeff operator()( const Polynomial_d& p, Exponent_vector ev ) { 00366 CGAL_precondition( ev.empty() ); 00367 return p; 00368 } 00369 }; 00370 00371 typedef Null_functor Evaluate ; 00372 00373 struct Substitute{ 00374 public: 00375 template <class Input_iterator> 00376 typename 00377 CGAL::Coercion_traits< 00378 typename std::iterator_traits<Input_iterator>::value_type, 00379 Innermost_coefficient_type>::Type 00380 operator()( 00381 const Innermost_coefficient_type& p, 00382 Input_iterator begin, 00383 Input_iterator end) const { 00384 CGAL_precondition(end == begin); 00385 typedef typename std::iterator_traits<Input_iterator>::value_type 00386 value_type; 00387 typedef CGAL::Coercion_traits<Innermost_coefficient_type,value_type> CT; 00388 return typename CT::Cast()(p); 00389 } 00390 }; 00391 00392 struct Substitute_homogeneous{ 00393 public: 00394 // this is the end of the recursion 00395 // begin contains the homogeneous variabel 00396 // hdegree is the remaining degree 00397 template <class Input_iterator> 00398 typename 00399 CGAL::Coercion_traits< 00400 typename std::iterator_traits<Input_iterator>::value_type, 00401 Innermost_coefficient_type>::Type 00402 operator()( 00403 const Innermost_coefficient_type& p, 00404 Input_iterator begin, 00405 Input_iterator end, 00406 int hdegree) const { 00407 00408 typedef typename std::iterator_traits<Input_iterator>::value_type 00409 value_type; 00410 typedef CGAL::Coercion_traits<Innermost_coefficient_type,value_type> CT; 00411 typename CT::Type result = 00412 typename CT::Cast()(CGAL::ipower(*begin++,hdegree)) 00413 * typename CT::Cast()(p); 00414 00415 CGAL_precondition(end == begin); 00416 CGAL_precondition(hdegree >= 0); 00417 return result; 00418 } 00419 }; 00420 }; 00421 00422 // Now the version for the polynomials with all functors provided by all 00423 // polynomials 00424 template< class Coefficient_type_, 00425 class ICoeffAlgebraicCategory, class PolynomialAlgebraicCategory > 00426 class Polynomial_traits_d_base< Polynomial< Coefficient_type_ >, 00427 ICoeffAlgebraicCategory, PolynomialAlgebraicCategory > 00428 : public Polynomial_traits_d_base_icoeff_algebraic_category< 00429 Polynomial< Coefficient_type_ >, ICoeffAlgebraicCategory >, 00430 public Polynomial_traits_d_base_polynomial_algebraic_category< 00431 Polynomial< Coefficient_type_ >, PolynomialAlgebraicCategory > { 00432 00433 typedef Polynomial_traits_d< Polynomial< Coefficient_type_ > > PT; 00434 typedef Polynomial_traits_d< Coefficient_type_ > PTC; 00435 00436 public: 00437 typedef Polynomial<Coefficient_type_> Polynomial_d; 00438 typedef Coefficient_type_ Coefficient_type; 00439 00440 typedef typename CGALi::Innermost_coefficient_type<Polynomial_d>::Type 00441 Innermost_coefficient_type; 00442 static const int d = Dimension<Polynomial_d>::value; 00443 00444 private: 00445 typedef std::pair< Exponent_vector, Innermost_coefficient_type > 00446 Exponents_coeff_pair; 00447 typedef std::vector< Exponents_coeff_pair > Monom_rep; 00448 00449 typedef CGAL::Recursive_const_flattening< d-1, 00450 typename CGAL::Polynomial<Coefficient_type>::const_iterator > 00451 Coefficient_const_flattening; 00452 00453 public: 00454 typedef typename Coefficient_const_flattening::Recursive_flattening_iterator 00455 Innermost_coefficient_const_iterator; 00456 typedef typename Polynomial_d::const_iterator Coefficient_const_iterator; 00457 00458 typedef std::pair<Innermost_coefficient_const_iterator, 00459 Innermost_coefficient_const_iterator> 00460 Innermost_coefficient_const_iterator_range; 00461 00462 typedef std::pair<Coefficient_const_iterator, 00463 Coefficient_const_iterator> 00464 Coefficient_const_iterator_range; 00465 00466 00467 // We use our own Strict Weak Ordering predicate in order to avoid 00468 // problems when calling sort for a Exponents_coeff_pair where the 00469 // coeff type has no comparison operators available. 00470 private: 00471 struct Compare_exponents_coeff_pair 00472 : public std::binary_function< 00473 std::pair< Exponent_vector, Innermost_coefficient_type >, 00474 std::pair< Exponent_vector, Innermost_coefficient_type >, 00475 bool > 00476 { 00477 bool operator()( 00478 const std::pair< Exponent_vector, Innermost_coefficient_type >& p1, 00479 const std::pair< Exponent_vector, Innermost_coefficient_type >& p2 ) const { 00480 // TODO: Precondition leads to an error within test_translate in 00481 // Polynomial_traits_d test 00482 // CGAL_precondition( p1.first != p2.first ); 00483 return p1.first < p2.first; 00484 } 00485 }; 00486 00487 public: 00488 00489 // 00490 // Functors as defined in the reference manual 00491 // (with sometimes slightly extended functionality) 00492 00493 // Construct_polynomial; 00494 struct Construct_polynomial { 00495 00496 typedef Polynomial_d result_type; 00497 00498 Polynomial_d operator()() const { 00499 return Polynomial_d(0); 00500 } 00501 00502 template <class T> 00503 Polynomial_d operator()( T a ) const { 00504 return Polynomial_d(a); 00505 } 00506 00508 Polynomial_d operator() (const Coefficient_type& a0) const 00509 {return Polynomial_d(a0);} 00510 00512 Polynomial_d operator() ( 00513 const Coefficient_type& a0, const Coefficient_type& a1) const 00514 {return Polynomial_d(a0,a1);} 00515 00517 Polynomial_d operator() ( 00518 const Coefficient_type& a0, const Coefficient_type& a1, 00519 const Coefficient_type& a2) const 00520 {return Polynomial_d(a0,a1,a2);} 00521 00523 Polynomial_d operator() ( 00524 const Coefficient_type& a0, const Coefficient_type& a1, 00525 const Coefficient_type& a2, const Coefficient_type& a3) const 00526 {return Polynomial_d(a0,a1,a2,a3);} 00527 00529 Polynomial_d operator() ( 00530 const Coefficient_type& a0, const Coefficient_type& a1, 00531 const Coefficient_type& a2, const Coefficient_type& a3, 00532 const Coefficient_type& a4) const 00533 {return Polynomial_d(a0,a1,a2,a3,a4);} 00534 00536 Polynomial_d operator() ( 00537 const Coefficient_type& a0, const Coefficient_type& a1, 00538 const Coefficient_type& a2, const Coefficient_type& a3, 00539 const Coefficient_type& a4, const Coefficient_type& a5) const 00540 {return Polynomial_d(a0,a1,a2,a3,a4,a5);} 00541 00543 Polynomial_d operator() ( 00544 const Coefficient_type& a0, const Coefficient_type& a1, 00545 const Coefficient_type& a2, const Coefficient_type& a3, 00546 const Coefficient_type& a4, const Coefficient_type& a5, 00547 const Coefficient_type& a6) const 00548 {return Polynomial_d(a0,a1,a2,a3,a4,a5,a6);} 00549 00551 Polynomial_d operator() ( 00552 const Coefficient_type& a0, const Coefficient_type& a1, 00553 const Coefficient_type& a2, const Coefficient_type& a3, 00554 const Coefficient_type& a4, const Coefficient_type& a5, 00555 const Coefficient_type& a6, const Coefficient_type& a7) const 00556 {return Polynomial_d(a0,a1,a2,a3,a4,a5,a6,a7);} 00557 00559 Polynomial_d operator() ( 00560 const Coefficient_type& a0, const Coefficient_type& a1, 00561 const Coefficient_type& a2, const Coefficient_type& a3, 00562 const Coefficient_type& a4, const Coefficient_type& a5, 00563 const Coefficient_type& a6, const Coefficient_type& a7, 00564 const Coefficient_type& a8) const 00565 {return Polynomial_d(a0,a1,a2,a3,a4,a5,a6,a7,a8);} 00566 00567 // Construct from Coefficient type 00568 template< class Input_iterator > 00569 inline Polynomial_d 00570 construct( Input_iterator begin, Input_iterator end, Tag_true) const { 00571 if(begin == end ) return Polynomial_d(0); 00572 return Polynomial_d(begin,end); 00573 } 00574 // Construct from momom rep 00575 template< class Input_iterator > 00576 inline Polynomial_d 00577 construct( Input_iterator begin, Input_iterator end, Tag_false) const { 00578 // construct from non sorted monom rep 00579 return (*this)(begin,end,false); 00580 } 00581 00582 template< class Input_iterator > 00583 Polynomial_d 00584 operator()( Input_iterator begin, Input_iterator end ) const { 00585 if(begin == end ) return Polynomial_d(0); 00586 typedef typename std::iterator_traits<Input_iterator>::value_type value_type; 00587 typedef Boolean_tag<boost::is_same<value_type,Coefficient_type>::value> 00588 Is_coeff; 00589 std::vector<value_type> vec(begin,end); 00590 return construct(vec.begin(),vec.end(),Is_coeff()); 00591 } 00592 00593 00594 template< class Input_iterator > 00595 Polynomial_d 00596 operator()(Input_iterator begin, Input_iterator end , bool is_sorted) const{ 00597 if(!is_sorted) 00598 std::sort(begin,end,Compare_exponents_coeff_pair()); 00599 return Create_polynomial_from_monom_rep< Coefficient_type >()(begin,end); 00600 } 00601 00602 public: 00603 00604 template< class T > 00605 class Create_polynomial_from_monom_rep { 00606 public: 00607 template <class Monom_rep_iterator> 00608 Polynomial_d operator()( 00609 Monom_rep_iterator begin, 00610 Monom_rep_iterator end) const { 00611 00612 std::vector< Innermost_coefficient_type > coefficients; 00613 for(Monom_rep_iterator it = begin; it != end; it++){ 00614 while( it->first[0] > (int) coefficients.size() ){ 00615 coefficients.push_back(Innermost_coefficient_type(0)); 00616 } 00617 coefficients.push_back(it->second); 00618 } 00619 return Polynomial_d(coefficients.begin(),coefficients.end()); 00620 } 00621 }; 00622 template< class T > 00623 class Create_polynomial_from_monom_rep< Polynomial < T > > { 00624 public: 00625 template <class Monom_rep_iterator> 00626 Polynomial_d operator()( 00627 Monom_rep_iterator begin, 00628 Monom_rep_iterator end) const { 00629 00630 typedef Polynomial_traits_d<Coefficient_type> PT; 00631 typename PT::Construct_polynomial construct; 00632 00633 BOOST_STATIC_ASSERT(PT::d != 0); // Coefficient_type is a Polynomial 00634 std::vector<Coefficient_type> coefficients; 00635 00636 Monom_rep_iterator it = begin; 00637 while(it != end){ 00638 int current_exp = it->first[PT::d]; 00639 // fill up with zeros until current exp is reached 00640 while( (int) coefficients.size() < current_exp){ 00641 coefficients.push_back(Coefficient_type(0)); 00642 } 00643 // collect all coeffs for this exp 00644 Monom_rep monoms; 00645 while( it != end && it->first[PT::d] == current_exp ){ 00646 Exponent_vector ev = it->first; 00647 ev.pop_back(); 00648 monoms.push_back( Exponents_coeff_pair(ev,it->second)); 00649 it++; 00650 } 00651 coefficients.push_back( 00652 construct(monoms.begin(), monoms.end())); 00653 } 00654 return Polynomial_d(coefficients.begin(),coefficients.end()); 00655 } 00656 }; 00657 }; 00658 00659 // Get_coefficient; 00660 struct Get_coefficient 00661 : public std::binary_function<Polynomial_d, int, Coefficient_type > { 00662 00663 Coefficient_type operator()( const Polynomial_d& p, int i) const { 00664 CGAL_precondition( i >= 0 ); 00665 typename PT::Degree degree; 00666 if( i > degree(p) ) 00667 return Coefficient_type(0); 00668 return p[i]; 00669 } 00670 }; 00671 00672 // Get_innermost_coefficient; 00673 struct Get_innermost_coefficient 00674 : public 00675 std::binary_function< Polynomial_d, Exponent_vector, Innermost_coefficient_type > 00676 { 00677 00678 Innermost_coefficient_type 00679 operator()( const Polynomial_d& p, Exponent_vector ev ) const { 00680 CGAL_precondition( !ev.empty() ); 00681 typename PTC::Get_innermost_coefficient gic; 00682 typename PT::Get_coefficient gc; 00683 int exponent = ev.back(); 00684 ev.pop_back(); 00685 return gic( gc( p, exponent ), ev ); 00686 }; 00687 }; 00688 00689 // Swap variable x_i with x_j 00690 struct Swap { 00691 typedef Polynomial_d result_type; 00692 typedef Polynomial_d first_argument_type; 00693 typedef int second_argument_type; 00694 typedef int third_argument_type; 00695 00696 public: 00697 00698 Polynomial_d operator()(const Polynomial_d& p, int i, int j ) const { 00699 CGAL_precondition(0 <= i && i < d); 00700 CGAL_precondition(0 <= j && j < d); 00701 typedef std::pair< Exponent_vector, Innermost_coefficient_type > 00702 Exponents_coeff_pair; 00703 typedef std::vector< Exponents_coeff_pair > Monom_rep; 00704 Monomial_representation gmr; 00705 Construct_polynomial construct; 00706 Monom_rep mon_rep; 00707 gmr( p, std::back_inserter( mon_rep ) ); 00708 for( typename Monom_rep::iterator it = mon_rep.begin(); 00709 it != mon_rep.end(); 00710 ++it ) { 00711 std::swap(it->first[i],it->first[j]); 00712 // it->first.swap( i, j ); 00713 } 00714 return construct( mon_rep.begin(), mon_rep.end() ); 00715 } 00716 }; 00717 00718 00719 // Move; 00720 // move variable x_i to position of x_j 00721 // order of other variables remains 00722 // default j = d makes x_i the othermost variable 00723 struct Move { 00724 typedef Polynomial_d result_type; 00725 typedef Polynomial_d first_argument_type; 00726 typedef int second_argument_type; 00727 typedef int third_argument_type; 00728 00729 Polynomial_d 00730 operator()(const Polynomial_d& p, int i, int j = (d-1) ) const { 00731 CGAL_precondition(0 <= i && i < d); 00732 CGAL_precondition(0 <= j && j < d); 00733 typedef std::pair< Exponent_vector, Innermost_coefficient_type > 00734 Exponents_coeff_pair; 00735 typedef std::vector< Exponents_coeff_pair > Monom_rep; 00736 Monomial_representation gmr; 00737 Construct_polynomial construct; 00738 Monom_rep mon_rep; 00739 gmr( p, std::back_inserter( mon_rep ) ); 00740 for( typename Monom_rep::iterator it = mon_rep.begin(); 00741 it != mon_rep.end(); 00742 ++it ) { 00743 // this is as good as std::rotate since it uses swap also 00744 if (i < j) 00745 for( int k = i; k < j; k++ ) 00746 std::swap(it->first[k],it->first[k+1]); 00747 else 00748 for( int k = i; k > j; k-- ) 00749 std::swap(it->first[k],it->first[k-1]); 00750 00751 } 00752 return construct( mon_rep.begin(), mon_rep.end() ); 00753 } 00754 }; 00755 00756 00757 struct Permute { 00758 typedef Polynomial_d result_type; 00759 template <typename Input_iterator> Polynomial_d operator() 00760 (const Polynomial_d& p, Input_iterator first, Input_iterator last) const { 00761 Construct_polynomial construct; 00762 Monomial_representation gmr; 00763 Monom_rep mon_rep; 00764 gmr( p, std::back_inserter( mon_rep )); 00765 std::vector<int> on_place, number_is; 00766 int i= 0; 00767 for (Input_iterator iter = first ; iter != last ; ++iter) 00768 number_is.push_back (i++); 00769 on_place = number_is; 00770 int rem_place = 0, rem_number = i= 0; 00771 for(Input_iterator iter = first ; iter != last ; ++iter){ 00772 for( typename Monom_rep::iterator it = mon_rep.begin(); it != 00773 mon_rep.end(); ++it ) 00774 std::swap(it->first[number_is[i]],it->first[(*iter)]); 00775 00776 00777 rem_place= number_is[i]; 00778 rem_number= on_place[(*iter)]; 00779 00780 on_place[(*iter)] = i; 00781 on_place[rem_place]=rem_number; 00782 number_is[rem_number]=rem_place; 00783 number_is[i++]= (*iter); 00784 } 00785 return construct( mon_rep.begin(), mon_rep.end() ); 00786 } 00787 }; 00788 00789 // Degree; 00790 struct Degree : public std::unary_function< Polynomial_d , int >{ 00791 int operator()(const Polynomial_d& p, int i = (d-1)) const { 00792 if (i == (d-1)) return p.degree(); 00793 else return Swap()(p,i,d-1).degree(); 00794 } 00795 }; 00796 00797 // Total_degree; 00798 struct Total_degree : public std::unary_function< Polynomial_d , int >{ 00799 int operator()(const Polynomial_d& p) const { 00800 typedef Polynomial_traits_d<Coefficient_type> COEFF_POLY_TRAITS; 00801 typename COEFF_POLY_TRAITS::Total_degree total_degree; 00802 Degree degree; 00803 CGAL_precondition( degree(p) >= 0); 00804 00805 int result = 0; 00806 for(int i = 0; i <= degree(p) ; i++){ 00807 if( ! CGAL::is_zero( p[i]) ) 00808 result = std::max(result , total_degree(p[i]) + i ); 00809 } 00810 return result; 00811 } 00812 }; 00813 00814 // Leading_coefficient; 00815 struct Leading_coefficient 00816 : public std::unary_function< Polynomial_d , Coefficient_type>{ 00817 Coefficient_type operator()(const Polynomial_d& p) const { 00818 return p.lcoeff(); 00819 } 00820 }; 00821 00822 // Innermost_leading_coefficient; 00823 struct Innermost_leading_coefficient 00824 : public std::unary_function< Polynomial_d , Innermost_coefficient_type>{ 00825 Innermost_coefficient_type 00826 operator()(const Polynomial_d& p) const { 00827 typename PTC::Innermost_leading_coefficient ilcoeff; 00828 typename PT::Leading_coefficient lcoeff; 00829 return ilcoeff(lcoeff(p)); 00830 } 00831 }; 00832 00833 00834 //return a canonical representative of all constant multiples. 00835 struct Canonicalize 00836 : public std::unary_function<Polynomial_d, Polynomial_d>{ 00837 00838 private: 00839 inline Polynomial_d canonicalize_(Polynomial_d p, CGAL::Tag_true) const 00840 { 00841 typedef typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type IC; 00842 typename Polynomial_traits_d<Polynomial_d>::Innermost_leading_coefficient ilcoeff; 00843 typename Algebraic_extension_traits<IC>::Normalization_factor nfac; 00844 00845 IC tmp = nfac(ilcoeff(p)); 00846 if(tmp != IC(1)){ 00847 p *= Polynomial_d(tmp); 00848 } 00849 remove_scalar_factor(p); 00850 p /= p.unit_part(); 00851 p.simplify_coefficients(); 00852 00853 CGAL_postcondition(nfac(ilcoeff(p)) == IC(1)); 00854 return p; 00855 }; 00856 00857 inline Polynomial_d canonicalize_(Polynomial_d p, CGAL::Tag_false) const 00858 { 00859 remove_scalar_factor(p); 00860 p /= p.unit_part(); 00861 p.simplify_coefficients(); 00862 return p; 00863 }; 00864 00865 public: 00866 Polynomial_d 00867 operator()( const Polynomial_d& p ) const { 00868 if (CGAL::is_zero(p)) return p; 00869 00870 typedef Innermost_coefficient_type IC; 00871 typedef typename Algebraic_extension_traits<IC>::Is_extended Is_extended; 00872 return canonicalize_(p, Is_extended()); 00873 } 00874 }; 00875 00876 // Differentiate; 00877 struct Differentiate 00878 : public std::unary_function<Polynomial_d, Polynomial_d>{ 00879 Polynomial_d 00880 operator()(Polynomial_d p, int i = (d-1)) const { 00881 if (i == (d-1) ){ 00882 p.diff(); 00883 }else{ 00884 Swap swap; 00885 p = swap(p,i,d-1); 00886 p.diff(); 00887 p = swap(p,i,d-1); 00888 } 00889 return p; 00890 } 00891 }; 00892 00893 // Evaluate; 00894 struct Evaluate 00895 :public std::binary_function<Polynomial_d,Coefficient_type,Coefficient_type>{ 00896 // Evaluate with respect to one variable 00897 Coefficient_type 00898 operator()(const Polynomial_d& p, Coefficient_type x) const { 00899 return p.evaluate(x); 00900 } 00901 #define ICOEFF typename First_if_different<Innermost_coefficient_type, Coefficient_type>::Type 00902 Coefficient_type operator() 00903 ( const Polynomial_d& p, const ICOEFF& x) const 00904 { 00905 return p.evaluate(x); 00906 } 00907 #undef ICOEFF 00908 }; 00909 00910 // Evaluate_homogeneous; 00911 struct Evaluate_homogeneous{ 00912 typedef Coefficient_type result_type; 00913 typedef Polynomial_d first_argument_type; 00914 typedef Coefficient_type second_argument_type; 00915 typedef Coefficient_type third_argument_type; 00916 00917 Coefficient_type operator()( 00918 const Polynomial_d& p, Coefficient_type a, Coefficient_type b) const 00919 { 00920 return p.evaluate_homogeneous(a,b); 00921 } 00922 #define ICOEFF typename First_if_different<Innermost_coefficient_type, Coefficient_type>::Type 00923 Coefficient_type operator() 00924 ( const Polynomial_d& p, const ICOEFF& a, const ICOEFF& b) const 00925 { 00926 return p.evaluate_homogeneous(a,b); 00927 } 00928 #undef ICOEFF 00929 00930 }; 00931 00932 // Is_zero_at; 00933 struct Is_zero_at { 00934 private: 00935 typedef Algebraic_structure_traits<Innermost_coefficient_type> AST; 00936 typedef typename AST::Is_zero::result_type BOOL; 00937 public: 00938 typedef BOOL result_type; 00939 00940 template< class Input_iterator > 00941 BOOL operator()( 00942 const Polynomial_d& p, 00943 Input_iterator begin, 00944 Input_iterator end ) const { 00945 typename PT::Substitute substitute; 00946 return( CGAL::is_zero( substitute( p, begin, end ) ) ); 00947 } 00948 }; 00949 00950 // Is_zero_at_homogeneous; 00951 struct Is_zero_at_homogeneous { 00952 private: 00953 typedef Algebraic_structure_traits<Innermost_coefficient_type> AST; 00954 typedef typename AST::Is_zero::result_type BOOL; 00955 public: 00956 typedef BOOL result_type; 00957 00958 template< class Input_iterator > 00959 BOOL operator() 00960 ( const Polynomial_d& p, Input_iterator begin, Input_iterator end ) const 00961 { 00962 typename PT::Substitute_homogeneous substitute_homogeneous; 00963 return( CGAL::is_zero( substitute_homogeneous( p, begin, end ) ) ); 00964 } 00965 }; 00966 00967 // Sign_at, Sign_at_homogeneous, Compare 00968 // define XXX_ even though ICoeff may not be Real_embeddable 00969 // select propoer XXX among XXX_ or Null_functor using ::boost::mpl::if_ 00970 private: 00971 struct Sign_at_ { 00972 private: 00973 typedef Real_embeddable_traits<Innermost_coefficient_type> RT; 00974 public: 00975 typedef typename RT::Sign result_type; 00976 00977 template< class Input_iterator > 00978 result_type operator()( 00979 const Polynomial_d& p, 00980 Input_iterator begin, 00981 Input_iterator end ) const 00982 { 00983 typename PT::Substitute substitute; 00984 return CGAL::sign( substitute( p, begin, end ) ); 00985 } 00986 }; 00987 00988 struct Sign_at_homogeneous_ { 00989 typedef Real_embeddable_traits<Innermost_coefficient_type> RT; 00990 public: 00991 typedef typename RT::Sign result_type; 00992 00993 template< class Input_iterator > 00994 result_type operator()( 00995 const Polynomial_d& p, 00996 Input_iterator begin, 00997 Input_iterator end) const { 00998 typename PT::Substitute_homogeneous substitute_homogeneous; 00999 return CGAL::sign( substitute_homogeneous( p, begin, end ) ); 01000 } 01001 }; 01002 01003 typedef Real_embeddable_traits<Innermost_coefficient_type> RET_IC; 01004 typedef typename RET_IC::Is_real_embeddable IC_is_real_embeddable; 01005 public: 01006 typedef typename ::boost::mpl::if_<IC_is_real_embeddable,Sign_at_,Null_functor>::type Sign_at; 01007 typedef typename ::boost::mpl::if_<IC_is_real_embeddable,Sign_at_homogeneous_,Null_functor>::type Sign_at_homogeneous; 01008 typedef typename Real_embeddable_traits<Polynomial_d>::Compare Compare; 01009 01010 01011 struct Construct_coefficient_const_iterator_range 01012 : public std::unary_function< Polynomial_d, 01013 Coefficient_const_iterator_range> { 01014 Coefficient_const_iterator_range 01015 operator () (const Polynomial_d& p) const { 01016 return std::make_pair( p.begin(), p.end() ); 01017 } 01018 }; 01019 01020 struct Construct_innermost_coefficient_const_iterator_range 01021 : public std::unary_function< Polynomial_d, 01022 Innermost_coefficient_const_iterator_range> { 01023 Innermost_coefficient_const_iterator_range 01024 operator () (const Polynomial_d& p) const { 01025 return std::make_pair( 01026 typename Coefficient_const_flattening::Flatten()(p.end(),p.begin()), 01027 typename Coefficient_const_flattening::Flatten()(p.end(),p.end())); 01028 } 01029 }; 01030 01031 struct Is_square_free 01032 : public std::unary_function< Polynomial_d, bool >{ 01033 bool operator()( const Polynomial_d& p ) const { 01034 if( !CGALi::may_have_multiple_factor( p ) ) 01035 return true; 01036 01037 Univariate_content_up_to_constant_factor ucontent_utcf; 01038 Integral_division_up_to_constant_factor idiv_utcf; 01039 Differentiate diff; 01040 01041 Coefficient_type content = ucontent_utcf( p ); 01042 typename PTC::Is_square_free isf; 01043 01044 if( !isf( content ) ) 01045 return false; 01046 01047 Polynomial_d regular_part = idiv_utcf( p, Polynomial_d( content ) ); 01048 01049 Polynomial_d g = gcd_utcf(regular_part,diff(regular_part)); 01050 return ( g.degree() == 0 ); 01051 } 01052 }; 01053 01054 01055 struct Make_square_free 01056 : public std::unary_function< Polynomial_d, Polynomial_d >{ 01057 Polynomial_d 01058 operator()(const Polynomial_d& p) const { 01059 if (CGAL::is_zero(p)) return p; 01060 Univariate_content_up_to_constant_factor ucontent_utcf; 01061 Integral_division_up_to_constant_factor idiv_utcf; 01062 Differentiate diff; 01063 typename PTC::Make_square_free msf; 01064 01065 Coefficient_type content = ucontent_utcf(p); 01066 Polynomial_d result = Polynomial_d(msf(content)); 01067 01068 Polynomial_d regular_part = idiv_utcf(p,Polynomial_d(content)); 01069 Polynomial_d g = gcd_utcf(regular_part,diff(regular_part)); 01070 01071 01072 result *= idiv_utcf(regular_part,g); 01073 return Canonicalize()(result); 01074 01075 } 01076 }; 01077 01078 // Pseudo_division; 01079 struct Pseudo_division { 01080 typedef Polynomial_d result_type; 01081 void 01082 operator()( 01083 const Polynomial_d& f, const Polynomial_d& g, 01084 Polynomial_d& q, Polynomial_d& r, Coefficient_type& D) const { 01085 Polynomial_d::pseudo_division(f,g,q,r,D); 01086 } 01087 }; 01088 01089 struct Pseudo_division_quotient 01090 :public std::binary_function<Polynomial_d, Polynomial_d, Polynomial_d> { 01091 01092 Polynomial_d 01093 operator()(const Polynomial_d& f, const Polynomial_d& g) const { 01094 Polynomial_d q,r; 01095 Coefficient_type D; 01096 Polynomial_d::pseudo_division(f,g,q,r,D); 01097 return q; 01098 } 01099 }; 01100 01101 struct Pseudo_division_remainder 01102 :public std::binary_function<Polynomial_d, Polynomial_d, Polynomial_d> { 01103 01104 Polynomial_d 01105 operator()(const Polynomial_d& f, const Polynomial_d& g) const { 01106 Polynomial_d q,r; 01107 Coefficient_type D; 01108 Polynomial_d::pseudo_division(f,g,q,r,D); 01109 return r; 01110 } 01111 }; 01112 01113 struct Gcd_up_to_constant_factor 01114 :public std::binary_function<Polynomial_d, Polynomial_d, Polynomial_d> { 01115 Polynomial_d 01116 operator()(const Polynomial_d& p, const Polynomial_d& q) const { 01117 if (CGAL::is_zero(p) && CGAL::is_zero(q)){ 01118 return Polynomial_d(0); 01119 } 01120 // apply modular filter first 01121 if (CGALi::may_have_common_factor(p,q)){ 01122 return CGALi::gcd_utcf(p,q); 01123 }else{ 01124 return Polynomial_d(1); 01125 } 01126 } 01127 }; 01128 01129 struct Integral_division_up_to_constant_factor 01130 :public std::binary_function<Polynomial_d, Polynomial_d, Polynomial_d> { 01131 Polynomial_d 01132 operator()(const Polynomial_d& p, const Polynomial_d& q) const { 01133 typedef Innermost_coefficient_type IC; 01134 01135 typename PT::Construct_polynomial construct; 01136 typename PT::Innermost_leading_coefficient ilcoeff; 01137 typename PT::Construct_innermost_coefficient_const_iterator_range range; 01138 typedef Algebraic_extension_traits<Innermost_coefficient_type> AET; 01139 typename AET::Denominator_for_algebraic_integers dfai; 01140 typename AET::Normalization_factor nfac; 01141 01142 01143 IC ilcoeff_q = ilcoeff(q); 01144 // this factor is needed in case IC is an Algebraic extension 01145 IC dfai_q = dfai(range(q).first, range(q).second); 01146 // make dfai_q a 'scalar' 01147 ilcoeff_q *= dfai_q * nfac(dfai_q); 01148 01149 Polynomial_d result = (p * construct(ilcoeff_q)) / q; 01150 01151 return Canonicalize()(result); 01152 } 01153 }; 01154 01155 struct Univariate_content_up_to_constant_factor 01156 :public std::unary_function<Polynomial_d, Coefficient_type> { 01157 Coefficient_type 01158 operator()(const Polynomial_d& p) const { 01159 typename PTC::Gcd_up_to_constant_factor gcd_utcf; 01160 01161 if(CGAL::is_zero(p)) return Coefficient_type(0); 01162 if(PT::d == 1) return Coefficient_type(1); 01163 01164 Coefficient_type result(0); 01165 for(typename Polynomial_d::const_iterator it = p.begin(); 01166 it != p.end(); 01167 it++){ 01168 result = gcd_utcf(*it,result); 01169 } 01170 return result; 01171 01172 } 01173 }; 01174 01175 struct Square_free_factorize_up_to_constant_factor { 01176 private: 01177 typedef Coefficient_type Coeff; 01178 typedef Innermost_coefficient_type ICoeff; 01179 01180 // rsqff_utcf computes the sqff recursively for Coeff 01181 // end of recursion: ICoeff 01182 01183 template < class OutputIterator > 01184 OutputIterator rsqff_utcf ( ICoeff , OutputIterator oi) const{ 01185 return oi; 01186 } 01187 01188 template < class OutputIterator > 01189 OutputIterator rsqff_utcf ( 01190 typename First_if_different<Coeff,ICoeff>::Type c, 01191 OutputIterator oi) const { 01192 01193 typename PTC::Square_free_factorize_up_to_constant_factor sqff; 01194 std::vector<std::pair<Coefficient_type,int> > fac_mul_pairs; 01195 sqff(c,std::back_inserter(fac_mul_pairs)); 01196 01197 for(unsigned int i = 0; i < fac_mul_pairs.size(); i++){ 01198 Polynomial_d factor(fac_mul_pairs[i].first); 01199 int mult = fac_mul_pairs[i].second; 01200 *oi++=std::make_pair(factor,mult); 01201 } 01202 return oi; 01203 } 01204 01205 public: 01206 template < class OutputIterator> 01207 OutputIterator 01208 operator()(Polynomial_d p, OutputIterator oi) const { 01209 if (CGAL::is_zero(p)) return oi; 01210 01211 Univariate_content_up_to_constant_factor ucontent_utcf; 01212 Integral_division_up_to_constant_factor idiv_utcf; 01213 Coefficient_type c = ucontent_utcf(p); 01214 01215 p = idiv_utcf( p , Polynomial_d(c)); 01216 std::vector<Polynomial_d> factors; 01217 std::vector<int> mults; 01218 square_free_factorize_utcf( 01219 p, std::back_inserter(factors), std::back_inserter(mults)); 01220 for(unsigned int i = 0; i < factors.size() ; i++){ 01221 *oi++=std::make_pair(factors[i],mults[i]); 01222 } 01223 if (CGAL::total_degree(c) == 0) 01224 return oi; 01225 else 01226 return rsqff_utcf(c,oi); 01227 } 01228 }; 01229 01230 struct Shift 01231 : public std::binary_function< Polynomial_d,int,Polynomial_d >{ 01232 01233 Polynomial_d 01234 operator()(const Polynomial_d& p, int e, int i = (d-1)) const { 01235 Construct_polynomial construct; 01236 Monomial_representation gmr; 01237 Monom_rep monom_rep; 01238 gmr(p,std::back_inserter(monom_rep)); 01239 for(typename Monom_rep::iterator it = monom_rep.begin(); 01240 it != monom_rep.end(); 01241 it++){ 01242 it->first[i]+=e; 01243 } 01244 return construct(monom_rep.begin(), monom_rep.end()); 01245 } 01246 }; 01247 01248 struct Negate 01249 : public std::unary_function< Polynomial_d, Polynomial_d >{ 01250 01251 Polynomial_d operator()(const Polynomial_d& p, int i = (d-1)) const { 01252 Construct_polynomial construct; 01253 Monomial_representation gmr; 01254 Monom_rep monom_rep; 01255 gmr(p,std::back_inserter(monom_rep)); 01256 for(typename Monom_rep::iterator it = monom_rep.begin(); 01257 it != monom_rep.end(); 01258 it++){ 01259 if (it->first[i] % 2 != 0) 01260 it->second = - it->second; 01261 } 01262 return construct(monom_rep.begin(), monom_rep.end()); 01263 } 01264 }; 01265 01266 struct Invert 01267 : public std::unary_function< Polynomial_d , Polynomial_d >{ 01268 Polynomial_d operator()(Polynomial_d p, int i = (PT::d-1)) const { 01269 if (i == (d-1)){ 01270 p.reversal(); 01271 }else{ 01272 p = Swap()(p,i,PT::d-1); 01273 p.reversal(); 01274 p = Swap()(p,i,PT::d-1); 01275 } 01276 return p ; 01277 } 01278 }; 01279 01280 struct Translate 01281 : public std::binary_function< Polynomial_d , Innermost_coefficient_type, 01282 Polynomial_d >{ 01283 Polynomial_d 01284 operator()( 01285 Polynomial_d p, 01286 const Innermost_coefficient_type& c, 01287 int i = (d-1)) 01288 const { 01289 if (i == (d-1) ){ 01290 p.translate(Coefficient_type(c)); 01291 }else{ 01292 Swap swap; 01293 p = swap(p,i,d-1); 01294 p.translate(Coefficient_type(c)); 01295 p = swap(p,i,d-1); 01296 } 01297 return p; 01298 } 01299 }; 01300 01301 struct Translate_homogeneous{ 01302 typedef Polynomial_d result_type; 01303 typedef Polynomial_d first_argument_type; 01304 typedef Innermost_coefficient_type second_argument_type; 01305 typedef Innermost_coefficient_type third_argument_type; 01306 01307 Polynomial_d 01308 operator()(Polynomial_d p, 01309 const Innermost_coefficient_type& a, 01310 const Innermost_coefficient_type& b, 01311 int i = (d-1) ) const { 01312 if (i == (d-1) ){ 01313 p.translate(Coefficient_type(a),Coefficient_type(b)); 01314 }else{ 01315 Swap swap; 01316 p = swap(p,i,d-1); 01317 p.translate(Coefficient_type(a),Coefficient_type(b)); 01318 p = swap(p,i,d-1); 01319 } 01320 return p; 01321 } 01322 }; 01323 01324 struct Scale 01325 : public 01326 std::binary_function< Polynomial_d, Innermost_coefficient_type, Polynomial_d > { 01327 01328 Polynomial_d operator()( Polynomial_d p, const Innermost_coefficient_type& c, 01329 int i = (PT::d-1) ) const { 01330 CGAL_precondition( i <= d-1 ); 01331 CGAL_precondition( i >= 0 ); 01332 typename PT::Scale_homogeneous scale_homogeneous; 01333 return scale_homogeneous( p, c, Innermost_coefficient_type(1), i ); 01334 } 01335 01336 }; 01337 01338 struct Scale_homogeneous{ 01339 typedef Polynomial_d result_type; 01340 typedef Polynomial_d first_argument_type; 01341 typedef Innermost_coefficient_type second_argument_type; 01342 typedef Innermost_coefficient_type third_argument_type; 01343 01344 Polynomial_d 01345 operator()( 01346 Polynomial_d p, 01347 const Innermost_coefficient_type& a, 01348 const Innermost_coefficient_type& b, 01349 int i = (d-1) ) const { 01350 01351 CGAL_precondition( ! CGAL::is_zero(b) ); 01352 CGAL_precondition( i <= d-1 ); 01353 CGAL_precondition( i >= 0 ); 01354 01355 if (i != (d-1) ) p = Swap()(p,i,d-1); 01356 01357 if(CGAL::is_one(b)) 01358 p.scale_up(Coefficient_type(a)); 01359 else 01360 if(CGAL::is_one(a)) 01361 p.scale_down(Coefficient_type(b)); 01362 else 01363 p.scale(Coefficient_type(a),Coefficient_type(b)); 01364 01365 if (i != (d-1) ) p = Swap()(p,i,d-1); 01366 01367 return p; 01368 } 01369 }; 01370 01371 struct Resultant 01372 : public std::binary_function<Polynomial_d, Polynomial_d, Coefficient_type>{ 01373 01374 Coefficient_type 01375 operator()( 01376 const Polynomial_d& p, 01377 const Polynomial_d& q) const { 01378 return CGALi::resultant(p,q); 01379 } 01380 }; 01381 01382 // Polynomial subresultants (aka subresultant polynomials) 01383 struct Polynomial_subresultants { 01384 01385 template<typename OutputIterator> 01386 OutputIterator operator()( 01387 const Polynomial_d& p, 01388 const Polynomial_d& q, 01389 OutputIterator out, 01390 int i = (d-1) ) const { 01391 if(i == (d-1) ) 01392 return CGAL::CGALi::polynomial_subresultants<PT>(p,q,out); 01393 else 01394 return CGAL::CGALi::polynomial_subresultants<PT>(Move()(p,i), 01395 Move()(q,i), 01396 out); 01397 } 01398 }; 01399 01400 // principal subresultants (aka scalar subresultants) 01401 struct Principal_subresultants { 01402 01403 template<typename OutputIterator> 01404 OutputIterator operator()( 01405 const Polynomial_d& p, 01406 const Polynomial_d& q, 01407 OutputIterator out, 01408 int i = (d-1) ) const { 01409 if(i == (d-1) ) 01410 return CGAL::CGALi::principal_subresultants<PT>(p,q,out); 01411 else 01412 return CGAL::CGALi::principal_subresultants<PT>(Move()(p,i), 01413 Move()(q,i), 01414 out); 01415 } 01416 }; 01417 01418 // Subresultants with cofactors 01419 struct Polynomial_subresultants_with_cofactors { 01420 01421 template<typename OutputIterator1, 01422 typename OutputIterator2, 01423 typename OutputIterator3> 01424 OutputIterator1 operator()( 01425 const Polynomial_d& p, 01426 const Polynomial_d& q, 01427 OutputIterator1 out_sres, 01428 OutputIterator2 out_co_p, 01429 OutputIterator3 out_co_q, 01430 int i = (d-1) ) const { 01431 if(i == (d-1) ) 01432 return CGAL::CGALi::polynomial_subresultants_with_cofactors<PT> 01433 (p,q,out_sres,out_co_p,out_co_q); 01434 else 01435 return CGAL::CGALi::polynomial_subresultants_with_cofactors<PT> 01436 (Move()(p,i),Move()(q,i),out_sres,out_co_p,out_co_q); 01437 } 01438 }; 01439 01440 // Sturm-Habicht sequence (aka signed subresultant sequence) 01441 struct Sturm_habicht_sequence { 01442 01443 template<typename OutputIterator> 01444 OutputIterator operator()( 01445 const Polynomial_d& p, 01446 OutputIterator out, 01447 int i = (d-1) ) const { 01448 if(i == (d-1) ) 01449 return CGAL::CGALi::sturm_habicht_sequence<PT>(p,out); 01450 else 01451 return CGAL::CGALi::sturm_habicht_sequence<PT>(Move()(p,i), 01452 out); 01453 } 01454 }; 01455 01456 // Sturm-Habicht sequence with cofactors 01457 struct Sturm_habicht_sequence_with_cofactors { 01458 01459 template<typename OutputIterator1, 01460 typename OutputIterator2, 01461 typename OutputIterator3> 01462 OutputIterator1 operator()( 01463 const Polynomial_d& p, 01464 OutputIterator1 out_stha, 01465 OutputIterator2 out_f, 01466 OutputIterator3 out_fx, 01467 int i = (d-1) ) const { 01468 if(i == (d-1) ) 01469 return CGAL::CGALi::sturm_habicht_sequence_with_cofactors<PT> 01470 (p,out_stha,out_f,out_fx); 01471 else 01472 return CGAL::CGALi::sturm_habicht_sequence_with_cofactors<PT> 01473 (Move()(p,i),out_stha,out_f,out_fx); 01474 } 01475 }; 01476 01477 // Principal Sturm-Habicht sequence (formal leading coefficients 01478 // of Sturm-Habicht sequence) 01479 struct Principal_sturm_habicht_sequence { 01480 01481 template<typename OutputIterator> 01482 OutputIterator operator()( 01483 const Polynomial_d& p, 01484 OutputIterator out, 01485 int i = (d-1) ) const { 01486 if(i == (d-1) ) 01487 return CGAL::CGALi::principal_sturm_habicht_sequence<PT>(p,out); 01488 else 01489 return CGAL::CGALi::principal_sturm_habicht_sequence<PT> 01490 (Move()(p,i),out); 01491 } 01492 }; 01493 01494 struct Monomial_representation { 01495 typedef std::pair< Exponent_vector, Innermost_coefficient_type > 01496 Exponents_coeff_pair; 01497 01498 template <class OutputIterator> 01499 void operator()( const Polynomial_d& p, OutputIterator oit ) const { 01500 if(CGAL::is_zero(p)){ 01501 *oit= std::make_pair(Exponent_vector(std::vector<int>(d,0)), 01502 Innermost_coefficient_type(0)); 01503 oit++; 01504 return; 01505 } 01506 01507 typedef Boolean_tag< d == 1 > Is_univariat; 01508 create_monom_representation( p, oit , Is_univariat()); 01509 } 01510 01511 private: 01512 01513 template <class OutputIterator> 01514 void 01515 create_monom_representation 01516 ( const Polynomial_d& p, OutputIterator oit, Tag_true ) const{ 01517 for( int exponent = 0; exponent <= p.degree(); ++exponent ) { 01518 if ( !CGAL::is_zero(p[exponent])){ 01519 Exponent_vector exp_vec; 01520 exp_vec.push_back( exponent ); 01521 *oit = Exponents_coeff_pair( exp_vec, p[exponent] ); 01522 } 01523 } 01524 } 01525 template <class OutputIterator> 01526 void 01527 create_monom_representation 01528 ( const Polynomial_d& p, OutputIterator oit, Tag_false ) const { 01529 typedef Polynomial_traits_d< Coefficient_type > PT; 01530 typename PT::Monomial_representation gmr; 01531 for( int exponent = 0; exponent <= p.degree(); ++exponent ) { 01532 Monom_rep monom_rep; 01533 if ( !CGAL::is_zero(p[exponent])){ 01534 gmr( p[exponent], std::back_inserter( monom_rep ) ); 01535 for( typename Monom_rep::iterator it = monom_rep.begin(); 01536 it != monom_rep.end(); ++it ) { 01537 it->first.push_back( exponent ); 01538 } 01539 } 01540 copy( monom_rep.begin(), monom_rep.end(), oit ); 01541 } 01542 } 01543 }; 01544 01545 01546 // returns the Exponten_vector of the innermost leading coefficient 01547 struct Degree_vector{ 01548 typedef Exponent_vector result_type; 01549 typedef Polynomial_d argument_type; 01550 01551 // returns the exponent vector of inner_most_lcoeff. 01552 result_type operator()(const Polynomial_d& polynomial) const{ 01553 typename PTC::Degree_vector degree_vector; 01554 Exponent_vector result = degree_vector(polynomial.lcoeff()); 01555 result.push_back(polynomial.degree()); 01556 return result; 01557 } 01558 }; 01559 01560 // substitute every variable by its new value in the iterator range 01561 // begin refers to the innermost/first variable 01562 struct Substitute{ 01563 public: 01564 template <class Input_iterator> 01565 typename CGAL::Coercion_traits< 01566 typename std::iterator_traits<Input_iterator>::value_type, 01567 Innermost_coefficient_type 01568 >::Type 01569 operator()( 01570 const Polynomial_d& p, 01571 Input_iterator begin, 01572 Input_iterator end) const { 01573 typedef typename std::iterator_traits<Input_iterator> ITT; 01574 typedef typename ITT::iterator_category Category; 01575 return (*this)(p,begin,end,Category()); 01576 } 01577 01578 template <class Input_iterator> 01579 typename CGAL::Coercion_traits< 01580 typename std::iterator_traits<Input_iterator>::value_type, 01581 Innermost_coefficient_type 01582 >::Type 01583 operator()( 01584 const Polynomial_d& p, 01585 Input_iterator begin, 01586 Input_iterator end, 01587 std::forward_iterator_tag) const { 01588 typedef typename std::iterator_traits<Input_iterator> ITT; 01589 std::list<typename ITT::value_type> list(begin,end); 01590 return (*this)(p,list.begin(),list.end()); 01591 } 01592 01593 template <class Input_iterator> 01594 typename 01595 CGAL::Coercion_traits 01596 <typename std::iterator_traits<Input_iterator>::value_type, 01597 Innermost_coefficient_type>::Type 01598 operator()( 01599 const Polynomial_d& p, 01600 Input_iterator begin, 01601 Input_iterator end, 01602 std::bidirectional_iterator_tag) const { 01603 01604 typedef typename std::iterator_traits<Input_iterator>::value_type 01605 value_type; 01606 typedef CGAL::Coercion_traits<Innermost_coefficient_type,value_type> CT; 01607 typename PTC::Substitute subs; 01608 01609 typename CT::Type x = typename CT::Cast()(*(--end)); 01610 01611 int i = Degree()(p); 01612 typename CT::Type y = 01613 subs(Get_coefficient()(p,i),begin,end); 01614 01615 while (--i >= 0){ 01616 y *= x; 01617 y += subs(Get_coefficient()(p,i),begin,end); 01618 } 01619 return y; 01620 } 01621 }; // substitute every variable by its new value in the iterator range 01622 01623 01624 01625 // begin refers to the innermost/first variable 01626 struct Substitute_homogeneous{ 01627 01628 template<typename Input_iterator> 01629 struct Result_type{ 01630 typedef std::iterator_traits<Input_iterator> ITT; 01631 typedef typename ITT::value_type value_type; 01632 typedef Coercion_traits<value_type, Innermost_coefficient_type> CT; 01633 typedef typename CT::Type Type; 01634 }; 01635 01636 public: 01637 01638 template <class Input_iterator> 01639 typename Result_type<Input_iterator>::Type 01640 operator()( const Polynomial_d& p, Input_iterator begin, Input_iterator end) const{ 01641 int hdegree = Total_degree()(p); 01642 01643 typedef std::iterator_traits<Input_iterator> ITT; 01644 std::list<typename ITT::value_type> list(begin,end); 01645 01646 // make the homogeneous variable the first in the list 01647 list.push_front(list.back()); 01648 list.pop_back(); 01649 01650 // reverse and begin with the outermost variable 01651 return (*this)(p, list.rbegin(), list.rend(), hdegree); 01652 } 01653 01654 // this operator is undcoumented and for internal use: 01655 // the iterator range starts with the outermost variable 01656 // and ends with the homogeneous variable 01657 template <class Input_iterator> 01658 typename Result_type<Input_iterator>::Type 01659 operator()( 01660 const Polynomial_d& p, 01661 Input_iterator begin, 01662 Input_iterator end, 01663 int hdegree) const{ 01664 01665 01666 typedef std::iterator_traits<Input_iterator> ITT; 01667 typedef typename ITT::value_type value_type; 01668 typedef Coercion_traits<value_type, Innermost_coefficient_type> CT; 01669 typedef typename CT::Type Type; 01670 01671 typename PTC::Substitute_homogeneous subsh; 01672 01673 typename CT::Type x = typename CT::Cast()(*begin++); 01674 01675 01676 int i = Degree()(p); 01677 typename CT::Type y = subsh(Get_coefficient()(p,i),begin,end, hdegree-i); 01678 01679 while (--i >= 0){ 01680 y *= x; 01681 y += subsh(Get_coefficient()(p,i),begin,end,hdegree-i); 01682 } 01683 return y; 01684 } 01685 }; 01686 01687 }; 01688 01689 } // namespace CGALi 01690 01691 // Definition of Polynomial_traits_d 01692 // 01693 // In order to determine the algebraic category of the innermost coefficient, 01694 // the Polynomial_traits_d_base class with "Null_tag" is used. 01695 01696 template< class Polynomial > 01697 class Polynomial_traits_d 01698 : public CGALi::Polynomial_traits_d_base< Polynomial, 01699 typename Algebraic_structure_traits< 01700 typename CGALi::Innermost_coefficient_type<Polynomial>::Type >::Algebraic_category, 01701 typename Algebraic_structure_traits< Polynomial >::Algebraic_category > , 01702 public Algebraic_structure_traits<Polynomial>{ 01703 01704 //------------ Rebind ----------- 01705 private: 01706 template <class T, int d> 01707 struct Gen_polynomial_type{ 01708 typedef CGAL::Polynomial<typename Gen_polynomial_type<T,d-1>::Type> Type; 01709 }; 01710 template <class T> 01711 struct Gen_polynomial_type<T,0>{ typedef T Type; }; 01712 01713 public: 01714 template <class T, int d> 01715 struct Rebind{ 01716 typedef Polynomial_traits_d<typename Gen_polynomial_type<T,d>::Type> Other; 01717 }; 01718 //------------ Rebind ----------- 01719 }; 01720 01721 CGAL_END_NAMESPACE 01722 01723 #endif // CGAL_POLYNOMIAL_TRAITS_D_H
1.7.6.1
