|
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_utils.h $ 00016 // $Id: polynomial_utils.h 50332 2009-07-02 13:49:48Z hemmer $ 00017 // 00018 // 00019 // Author(s) : Michael Hemmer <hemmer@mpi-inf.mpg.de> 00020 // 00021 // ============================================================================ 00022 00023 #include <CGAL/basic.h> 00024 #include <CGAL/Polynomial_traits_d.h> 00025 00026 #ifndef CGAL_POLYNOMIAL_UTILS_H 00027 #define CGAL_POLYNOMIAL_UTILS_H 00028 00029 #define CGAL_UNARY_POLY_FUNCTION(functor,function) \ 00030 template <typename Polynomial_d> inline \ 00031 typename Polynomial_traits_d<Polynomial_d>::functor::result_type \ 00032 function(const Polynomial_d& p){ \ 00033 typedef Polynomial_traits_d<Polynomial_d> PT; \ 00034 return typename PT::functor()(p); \ 00035 } 00036 00037 #define CGAL_UNARY_POLY_FUNCTION_INDEX(functor,function) \ 00038 CGAL_UNARY_POLY_FUNCTION(functor,function); \ 00039 template <typename Polynomial_d> inline \ 00040 typename Polynomial_traits_d<Polynomial_d>::functor::result_type \ 00041 function(const Polynomial_d& p, int index ){ \ 00042 typedef Polynomial_traits_d<Polynomial_d> PT; \ 00043 typename PT::functor fo; \ 00044 return fo(p,index); \ 00045 } 00046 00047 #define CGAL_BINARY_POLY_FUNCTION(functor,function) \ 00048 template <typename Polynomial_d> inline \ 00049 typename Polynomial_traits_d<Polynomial_d>::functor::result_type \ 00050 function(const Polynomial_d& p, \ 00051 const typename Polynomial_traits_d<Polynomial_d>:: \ 00052 functor::second_argument_type& second \ 00053 ){ \ 00054 typedef Polynomial_traits_d<Polynomial_d> PT; \ 00055 return typename PT::functor()(p,second); \ 00056 } 00057 00058 #define CGAL_BINARY_POLY_FUNCTION_INDEX(functor,function) \ 00059 CGAL_BINARY_POLY_FUNCTION(functor,function) \ 00060 template <typename Polynomial_d> inline \ 00061 typename Polynomial_traits_d<Polynomial_d>::functor::result_type \ 00062 function(const Polynomial_d& p, \ 00063 const typename Polynomial_traits_d<Polynomial_d>:: \ 00064 functor::second_argument_type& second, \ 00065 int index \ 00066 ){ \ 00067 typedef Polynomial_traits_d<Polynomial_d> PT; \ 00068 return typename PT::functor()(p,second,index); \ 00069 } 00070 00071 CGAL_BEGIN_NAMESPACE 00072 00073 // GetCoefficient 00074 template <typename Polynomial_d> inline 00075 typename Polynomial_traits_d<Polynomial_d>::Get_coefficient::result_type 00076 get_coefficient(const Polynomial_d& p, int i){ 00077 typename Polynomial_traits_d<Polynomial_d>::Get_coefficient get_coefficient; 00078 return get_coefficient(p,i); 00079 } 00080 // GetInnermostCoefficient 00081 template <typename Polynomial_d> inline 00082 typename Polynomial_traits_d<Polynomial_d> 00083 ::Get_innermost_coefficient::result_type 00084 get_innermost_coefficient(const Polynomial_d& p, Exponent_vector ev){ 00085 typename Polynomial_traits_d<Polynomial_d>::Get_innermost_coefficient gic; 00086 return gic(p,ev); 00087 } 00088 // ConstructCoefficientConstIteratorRange 00089 // ConstructInnermostCoefficientConstIteratorRange 00090 // Swap 00091 template <typename Polynomial_d> inline 00092 typename Polynomial_traits_d<Polynomial_d>::Swap::result_type 00093 swap(const Polynomial_d& p, int i, int j){ 00094 typename Polynomial_traits_d<Polynomial_d>::Swap swap; 00095 return swap(p,i,j); 00096 } 00097 // Move 00098 template <typename Polynomial_d> inline 00099 typename Polynomial_traits_d<Polynomial_d>::Move::result_type 00100 move(const Polynomial_d& p, int i, int j){ 00101 typename Polynomial_traits_d<Polynomial_d>::Move move; 00102 return move(p,i,j); 00103 } 00104 // Permute 00105 template <typename Polynomial_d, typename Input_iterator> inline 00106 typename Polynomial_traits_d<Polynomial_d>::Permute::result_type 00107 permute(const Polynomial_d& p, Input_iterator begin, Input_iterator end){ 00108 typename Polynomial_traits_d<Polynomial_d>::Permute permute; 00109 return permute(p,begin,end); 00110 } 00111 00112 // Degree 00113 CGAL_UNARY_POLY_FUNCTION_INDEX(Degree,degree); 00114 // TotalDegree 00115 CGAL_UNARY_POLY_FUNCTION(Total_degree,total_degree); 00116 // DegreeVector 00117 CGAL_UNARY_POLY_FUNCTION(Degree_vector,degree_vector); 00118 // LeadingCoefficient 00119 CGAL_UNARY_POLY_FUNCTION(Leading_coefficient,leading_coefficient); 00120 // InnermostLeadingCoefficient 00121 CGAL_UNARY_POLY_FUNCTION( 00122 Innermost_leading_coefficient, 00123 innermost_leading_coefficient); 00124 00125 // Canonicalize 00126 CGAL_UNARY_POLY_FUNCTION(Canonicalize, canonicalize); 00127 // Differentiate 00128 CGAL_UNARY_POLY_FUNCTION_INDEX(Differentiate, differentiate); 00129 00130 // Evaluate 00131 CGAL_BINARY_POLY_FUNCTION(Evaluate,evaluate); 00132 // EvaluateHomogeneous 00133 template <typename Polynomial_d> inline 00134 typename Polynomial_traits_d<Polynomial_d>::Evaluate_homogeneous::result_type 00135 evaluate_homogeneous(const Polynomial_d& p, 00136 const typename Polynomial_traits_d<Polynomial_d>::Coefficient_type& num, 00137 const typename Polynomial_traits_d<Polynomial_d>::Coefficient_type& den){ 00138 typedef Polynomial_traits_d<Polynomial_d> PT; 00139 return typename PT::Evaluate_homogeneous()(p,num,den); 00140 } 00141 00142 // Substitute 00143 template <typename Polynomial_d, typename Input_iterator> inline 00144 typename CGAL::Coercion_traits< 00145 typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type, 00146 typename std::iterator_traits<Input_iterator>::value_type> 00147 ::Type 00148 substitute(const Polynomial_d& p,Input_iterator begin, Input_iterator end){ 00149 typedef Polynomial_traits_d<Polynomial_d> PT; 00150 return typename PT::Substitute()(p,begin, end); 00151 } 00152 // IsZeroAt 00153 template <typename Polynomial_d, typename Input_iterator> inline 00154 typename Polynomial_traits_d<Polynomial_d>::Is_zero_at::result_type 00155 is_zero_at(const Polynomial_d& p, Input_iterator begin, Input_iterator end){ 00156 typedef Polynomial_traits_d<Polynomial_d> PT; 00157 return typename PT::Is_zero_at()(p,begin, end); 00158 } 00159 // SignAt 00160 template <typename Polynomial_d, typename Input_iterator> inline 00161 typename Polynomial_traits_d<Polynomial_d>::Sign_at::result_type 00162 sign_at(const Polynomial_d& p, Input_iterator begin, Input_iterator end){ 00163 typedef Polynomial_traits_d<Polynomial_d> PT; 00164 return typename PT::Sign_at()(p,begin, end); 00165 } 00166 00167 // SubstituteHomogeneous 00168 template <typename Polynomial_d, typename Input_iterator> inline 00169 typename CGAL::Coercion_traits< 00170 typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type, 00171 typename std::iterator_traits<Input_iterator>::value_type> 00172 ::Type 00173 substitute_homogeneous( 00174 const Polynomial_d& p,Input_iterator begin, Input_iterator end){ 00175 typedef Polynomial_traits_d<Polynomial_d> PT; 00176 return typename PT::Substitute_homogeneous()(p,begin, end); 00177 } 00178 // IsZeroAtHomogeneous 00179 template <typename Polynomial_d, typename Input_iterator> inline 00180 typename Polynomial_traits_d<Polynomial_d>::Is_zero_at_homogeneous::result_type 00181 is_zero_at_homogeneous( 00182 const Polynomial_d& p, Input_iterator begin, Input_iterator end){ 00183 typedef Polynomial_traits_d<Polynomial_d> PT; 00184 return typename PT::Is_zero_at_homogeneous()(p,begin, end); 00185 } 00186 // SignAtHomogeneous 00187 template <typename Polynomial_d, typename Input_iterator> inline 00188 typename Polynomial_traits_d<Polynomial_d>::Sign_at_homogeneous::result_type 00189 sign_at_homogeneous( 00190 const Polynomial_d& p, Input_iterator begin, Input_iterator end){ 00191 typedef Polynomial_traits_d<Polynomial_d> PT; 00192 return typename PT::Sign_at_homogeneous()(p,begin, end); 00193 } 00194 00195 // Compare // provided by number_type utils 00196 // CGAL_BINARY_POLY_FUNCTION(Compare,compare); 00197 00198 // UnivariateContent 00199 CGAL_UNARY_POLY_FUNCTION(Univariate_content, univariate_content); 00200 // MultivariateContent 00201 CGAL_UNARY_POLY_FUNCTION(Multivariate_content, multivariate_content); 00202 00203 // SquareFreeFactorize 00204 template <typename Polynomial_d, typename OutputIterator> inline 00205 OutputIterator 00206 square_free_factorize(const Polynomial_d& p, OutputIterator oi){ 00207 typedef Polynomial_traits_d<Polynomial_d> PT; 00208 return typename PT::Square_free_factorize()(p,oi); 00209 } 00210 // MakeSquareFree 00211 CGAL_UNARY_POLY_FUNCTION(Make_square_free, make_square_free); 00212 00213 // PseudoDivision 00214 // PseudoDivisionQuotient 00215 // PseudoDivisionRemainder 00216 template <typename Polynomial_d> inline 00217 void 00218 pseudo_division( 00219 const Polynomial_d& f, const Polynomial_d& g, 00220 Polynomial_d& q, Polynomial_d& r, 00221 typename Polynomial_traits_d<Polynomial_d>::Coefficient_type& D){ 00222 typedef Polynomial_traits_d<Polynomial_d> PT; 00223 typename PT::Pseudo_division()(f,g,q,r,D); 00224 return; 00225 } 00226 template <typename Polynomial_d> inline 00227 typename Polynomial_traits_d<Polynomial_d>::Pseudo_division_quotient::result_type 00228 pseudo_division_quotient(const Polynomial_d& f, const Polynomial_d& g){ 00229 typedef Polynomial_traits_d<Polynomial_d> PT; 00230 return typename PT::Pseudo_division_quotient()(f,g); 00231 } 00232 template <typename Polynomial_d> inline 00233 typename Polynomial_traits_d<Polynomial_d>::Pseudo_division_remainder::result_type 00234 pseudo_division_remainder(const Polynomial_d& f, const Polynomial_d& g){ 00235 typedef Polynomial_traits_d<Polynomial_d> PT; 00236 return typename PT::Pseudo_division_remainder()(f,g); 00237 } 00238 00239 // GcdUpToConstantFactor 00240 CGAL_BINARY_POLY_FUNCTION( 00241 Gcd_up_to_constant_factor, 00242 gcd_up_to_constant_factor); 00243 // IntegralDivisionUpToConstantFactor 00244 CGAL_BINARY_POLY_FUNCTION( 00245 Integral_division_up_to_constant_factor, 00246 integral_division_up_to_constant_factor); 00247 // UnivariateContentUpToConstantFactor 00248 CGAL_UNARY_POLY_FUNCTION( 00249 Univariate_content_up_to_constant_factor, 00250 univariate_content_up_to_constant_factor); 00251 // SquareFreeFactorizeUpToConstantFactor 00252 template <typename Polynomial_d, typename OutputIterator> inline 00253 OutputIterator 00254 square_free_factorize_up_to_constant_factor( 00255 const Polynomial_d& p, OutputIterator oi){ 00256 typedef Polynomial_traits_d<Polynomial_d> PT; 00257 return typename PT::Square_free_factorize_up_to_constant_factor()(p,oi); 00258 } 00259 00260 // Shift 00261 CGAL_BINARY_POLY_FUNCTION_INDEX(Shift,shift); 00262 // Negate 00263 CGAL_UNARY_POLY_FUNCTION_INDEX(Negate,negate); 00264 // Invert 00265 CGAL_UNARY_POLY_FUNCTION_INDEX(Invert,invert); 00266 // Translate 00267 CGAL_BINARY_POLY_FUNCTION_INDEX(Translate,translate); 00268 // TranslateHomogeneous 00269 template <typename Polynomial_d> inline 00270 typename Polynomial_traits_d<Polynomial_d>::Translate_homogeneous::result_type 00271 translate_homogeneous(const Polynomial_d& f, 00272 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& num, 00273 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& den){ 00274 00275 typedef Polynomial_traits_d<Polynomial_d> PT; 00276 return typename PT::Translate_homogeneous()(f,num,den); 00277 } 00278 template <typename Polynomial_d> inline 00279 typename Polynomial_traits_d<Polynomial_d>::Translate_homogeneous::result_type 00280 translate_homogeneous(const Polynomial_d& f, 00281 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& num, 00282 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& den, 00283 int index ){ 00284 typedef Polynomial_traits_d<Polynomial_d> PT; 00285 return typename PT::Translate_homogeneous()(f,num,den,index); 00286 } 00287 // Scale 00288 CGAL_BINARY_POLY_FUNCTION_INDEX(Scale,scale); 00289 // ScaleHomogeneous 00290 template <typename Polynomial_d> inline 00291 typename Polynomial_traits_d<Polynomial_d>::Scale_homogeneous::result_type 00292 scale_homogeneous(const Polynomial_d& f, 00293 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& num, 00294 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& den){ 00295 00296 typedef Polynomial_traits_d<Polynomial_d> PT; 00297 return typename PT::Scale_homogeneous()(f,num,den); 00298 } 00299 template <typename Polynomial_d> inline 00300 typename Polynomial_traits_d<Polynomial_d>::Scale_homogeneous::result_type 00301 scale_homogeneous(const Polynomial_d& f, 00302 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& num, 00303 const typename Polynomial_traits_d<Polynomial_d>::Innermost_coefficient_type& den, 00304 int index ){ 00305 typedef Polynomial_traits_d<Polynomial_d> PT; 00306 return typename PT::Scale_homogeneous()(f,num,den,index); 00307 } 00308 // Resultant 00309 CGAL_BINARY_POLY_FUNCTION(Resultant,resultant); 00310 00311 template <typename Polynomial_d,typename OutputIterator> inline 00312 OutputIterator polynomial_subresultants 00313 (Polynomial_d p, Polynomial_d q, OutputIterator out) { 00314 typedef Polynomial_traits_d<Polynomial_d> PT; 00315 return typename PT::Polynomial_subresultants() (p, q, out); 00316 } 00317 00318 template <typename Polynomial_d,typename OutputIterator> inline 00319 OutputIterator principal_subresultants 00320 (Polynomial_d p, Polynomial_d q, OutputIterator out) { 00321 typedef Polynomial_traits_d<Polynomial_d> PT; 00322 return typename PT::Principal_subresultants() (p, q, out); 00323 } 00324 00325 template<typename Polynomial_d, 00326 typename OutputIterator1, 00327 typename OutputIterator2, 00328 typename OutputIterator3> inline 00329 OutputIterator1 polynomial_subresultants_with_cofactors 00330 (Polynomial_d p, 00331 Polynomial_d q, 00332 OutputIterator1 sres_out, 00333 OutputIterator2 coP_out, 00334 OutputIterator3 coQ_out) { 00335 typedef Polynomial_traits_d<Polynomial_d> PT; 00336 return typename PT::Polynomial_subresultants_with_cofactors() 00337 (p, q, sres_out, coP_out, coQ_out); 00338 } 00339 00340 00341 template <typename Polynomial_d,typename OutputIterator> inline 00342 OutputIterator 00343 principal_sturm_habicht_sequence 00344 (Polynomial_d f, OutputIterator out){ 00345 typedef Polynomial_traits_d<Polynomial_d> PT; 00346 return typename PT::Principal_sturm_habicht_sequence() (f, out); 00347 } 00348 00349 template<typename Polynomial_d,typename OutputIterator> OutputIterator 00350 sturm_habicht_sequence(Polynomial_d f,OutputIterator out) { 00351 typedef Polynomial_traits_d<Polynomial_d> PT; 00352 return typename PT::Sturm_habicht_sequence() (f, out); 00353 } 00354 00355 template<typename Polynomial_d, 00356 typename OutputIterator1, 00357 typename OutputIterator2, 00358 typename OutputIterator3> 00359 OutputIterator1 00360 sturm_habicht_sequence_with_cofactors 00361 (Polynomial_d f, 00362 OutputIterator1 stha_out, 00363 OutputIterator2 cof_out, 00364 OutputIterator3 cofx_out) { 00365 typedef Polynomial_traits_d<Polynomial_d> PT; 00366 return typename PT::Sturm_habicht_sequence_with_cofactors() 00367 (f, stha_out, cof_out, cofx_out); 00368 } 00369 00370 00371 // TODO: REMOVE function below 00372 00373 // sign() forwarded to the sign() member function 00374 //template <typename NT> inline 00375 //CGAL::Sign sign(const Polynomial<NT>& p) { return p.sign(); } 00376 00377 // the non-member variants of diff() etc. 00378 template <typename NT> inline 00379 Polynomial<NT> diff(const Polynomial<NT>& p) 00380 { Polynomial<NT> q(p); q.diff(); return q; } 00381 00382 template<typename NT> inline 00383 Polynomial<NT> scale_up(const Polynomial<NT>& p, const NT& a) 00384 { Polynomial<NT> q(p); q.scale_up(a); return q; } 00385 00386 template<typename NT> inline 00387 Polynomial<NT> scale_down(const Polynomial<NT>& p, const NT& b) 00388 { Polynomial<NT> q(p); q.scale_down(b); return q; } 00389 00390 template<typename NT> inline 00391 Polynomial<NT> scale(const Polynomial<NT>& p, const NT& a, const NT& b) 00392 { Polynomial<NT> q(p); q.scale(a, b); return q; } 00393 00394 template<typename NT> inline 00395 Polynomial<NT> translate_by_one(const Polynomial<NT>& p) 00396 { Polynomial<NT> q(p); q.translate_by_one(); return q; } 00397 00398 template<typename NT> inline 00399 Polynomial<NT> translate(const Polynomial<NT>& p, const NT& c) 00400 { Polynomial<NT> q(p); q.translate(c); return q; } 00401 00402 template<typename NT> inline 00403 Polynomial<NT> translate(const Polynomial<NT>& p, const NT& a, const NT& b) 00404 { Polynomial<NT> q(p); q.translate(a, b); return q; } 00405 00406 template<typename NT> inline 00407 Polynomial<NT> reversal(const Polynomial<NT>& p) 00408 { Polynomial<NT> q(p); q.reversal(); return q; } 00409 00410 template< class Polynomial > 00411 bool is_square_free( const Polynomial& p ) { 00412 return typename CGAL::Polynomial_traits_d< Polynomial>:: 00413 Is_square_free()( p ); 00414 } 00415 00416 CGAL_END_NAMESPACE 00417 00418 #undef CGAL_UNARY_POLY_FUNCTION 00419 #undef CGAL_UNARY_POLY_FUNCTION_INDEX 00420 #undef CGAL_BINARY_POLY_FUNCTION 00421 #undef CGAL_BINARY_POLY_FUNCTION_INDEX 00422 00423 #endif // CGAL_POLYNOMIAL_UTILS_H
1.7.6.1
