lemon-0.x: lemon/polynomial.h@eaf16c8f6fef

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #ifndef LEMON_BEZIER_H

    20 #define LEMON_BEZIER_H

    22 ///\ingroup misc

    23 ///\file

    24 ///\brief A simple class implementing polynomials.

    25 ///

    26 ///\author Alpar Juttner

    28 #include<vector>

    30 namespace lemon {

    32   /// \addtogroup misc

    33   /// @{

    35   ///Simple polinomial class

    37   ///This class implements a polynomial where the coefficients are of

    38   ///type \c T.

    39   ///

    40   ///The coefficients are stored in an std::vector.

    41   template<class T>

    42   class Polynomial

    43   {

    44     std::vector<T> _coeff;

    45   public:

    46     ///Construct a polynomial of degree \c d.

    47     explicit Polynomial(int d=0) : _coeff(d+1) {}

    48     ///\e

    49     template<class U> Polynomial(const U &u) : _coeff(1,u) {}

    50     ///\e

    51     template<class U> Polynomial(const Polynomial<U> &u) : _coeff(u.deg()+1)

    52     {

    53       for(int i=0;i<(int)_coeff.size();i++) _coeff[i]=u[i];

    54     }

    55     ///Query the degree of the polynomial.

    57     ///Query the degree of the polynomial.

    58     ///\warning This number differs from real degree of the polinomial if

    59     ///the coefficient of highest degree is 0.

    60     int deg() const { return _coeff.size()-1; }

    61     ///Set the degree of the polynomial.

    63     ///Set the degree of the polynomial. In fact it resizes the

    64     ///coefficient vector.

    65     void deg(int d) { _coeff.resize(d+1);}

    67     ///Returns (as a reference) the coefficient of degree \c d.

    68     typename std::vector<T>::reference operator[](int d) { return _coeff[d]; }

    69     ///Returns (as a const reference) the coefficient of degree \c d.

    70     typename std::vector<T>::const_reference

    71     operator[](int d) const {return _coeff[d];}

    73     ///Substitute the value u into the polinomial.

    75     ///Substitute the value u into the polinomial.

    76     ///The calculation will be done using type \c R.

    77     ///The following examples shows the usage of the template parameter \c R.

    78     ///\code

    79     ///  Polynomial<xy<double> > line(1);

    80     ///  line[0]=xy<double>(12,25);

    81     ///  line[1]=xy<double>(2,7);

    82     ///  ...

    83     ///  xy<double> d = line.subst<xy<double> >(23.2);

    84     ///\endcode

    85     ///

    86     ///\code

    87     ///  Polynomial<double> p;

    88     ///  Polynomial<double> q;

    89     ///  ...

    90     ///  Polynomial<double> s = p.subst<Polynomial<double> >(q);

    91     ///\endcode

    92     template<class R,class U>

    93     R subst(const U &u) const

    94     {

    95       typename std::vector<T>::const_reverse_iterator i=_coeff.rbegin();

    96       R v=*i;

    97       for(++i;i!=_coeff.rend();++i) v=v*u+*i;

    98       return v;

    99     }

   100     ///Substitute the value u into the polinomial.

   102     ///Substitute the value u into the polinomial.

   103     ///The calculation will be done using type \c T

   104     ///(i.e. using the type of the coefficients.)

   105     template<class U>

   106     T operator()(const U &u) const

   107     {

   108       return subst<T>(u);

   109     }

   111     ///Derivate the polynomial (in place)

   112     Polynomial &derivateMyself()

   113     {

   114       for(int i=1;i<(int)_coeff.size();i++) _coeff[i-1]=i*_coeff[i];

   115       _coeff.pop_back();

   116       return *this;

   117     }

   119     ///Return the derivate of the polynomial

   120     Polynomial derivate() const

   121     {

   122       Polynomial tmp(deg()-1);

   123       for(int i=1;i<(int)_coeff.size();i++) tmp[i-1]=i*_coeff[i];

   124       return tmp;

   125     }

   127     ///Integrate the polynomial (in place)

   128     Polynomial &integrateMyself()

   129     {

   130       _coeff.push_back(T());

   131       for(int i=_coeff.size()-1;i>=0;i--) _coeff[i]=_coeff[i-1]/i;

   132       _coeff[0]=0;

   133       return *this;

   134     }

   136     ///Return the integrate of the polynomial

   137     Polynomial integrate() const

   138     {

   139       Polynomial tmp(deg()+1);

   140       tmp[0]=0;

   141       for(int i=0;i<(int)_coeff.size();i++) tmp[i+1]=_coeff[i]/(i+1);

   142       return tmp;

   143     }

   145     ///\e

   146     template<class U>

   147     Polynomial &operator+=(const Polynomial<U> &p)

   148     {

   149       if(p.deg()>deg()) _coeff.resize(p.deg()+1);

   150       for(int i=0;i<=(int)std::min(deg(),p.deg());i++)

   151 	_coeff[i]+=p[i];

   152       return *this;

   153     }

   154     ///\e

   155     template<class U>

   156     Polynomial &operator-=(const Polynomial<U> &p)

   157     {

   158       if(p.deg()>deg()) _coeff.resize(p.deg()+1);

   159       for(int i=0;i<=std::min(deg(),p.deg());i++) _coeff[i]-=p[i];

   160       return *this;

   161     }

   162     ///\e

   163     template<class U>

   164     Polynomial &operator+=(const U &u)

   165     {

   166       _coeff[0]+=u;

   167       return *this;

   168     }

   169     ///\e

   170     template<class U>

   171     Polynomial &operator-=(const U &u)

   172     {

   173       _coeff[0]+=u;

   174       return *this;

   175     }

   176     ///\e

   177     template<class U>

   178     Polynomial &operator*=(const U &u)

   179     {

   180       for(typename std::vector<T>::iterator i=_coeff.begin();i!=_coeff.end();++i)

   181 	*i*=u;

   182       return *this;

   183     }

   184     ///\e

   185     template<class U>

   186     Polynomial &operator/=(const U &u)

   187     {

   188       for(typename std::vector<T>::iterator i=_coeff.begin();i!=_coeff.end();++i)

   189 	*i/=u;

   190       return *this;

   191     }

   193   };

   195   ///Equality comparison

   197   ///\relates Polynomial

   198   ///\warning Two polynomials are defined to be unequal if their degrees differ,

   199   ///even if the non-zero coefficients are the same.

   200   template<class U,class V>

   201   bool operator==(const Polynomial<U> &u,const Polynomial<V> &v)

   202   {

   203     if(u.deg()!=v.deg()) return false;

   204     for(int i=0;i<=u.deg();i++) if(u[i]!=v[i]) return false;

   205     return true;

   206   }

   208   ///Non-equality comparison

   210   ///\relates Polynomial

   211   ///\warning Two polynomials are defined to be unequal if their degrees differ,

   212   ///even if the non-zero coefficients are the same.

   213   template<class U,class V>

   214   bool operator!=(const Polynomial<U> &u,const Polynomial<V> &v)

   215   {

   216     return !(u==v);

   217   }

   219   ///\e

   221   ///\relates Polynomial

   222   ///

   223   template<class U,class V>

   224   Polynomial<U> operator+(const Polynomial<U> &u,const Polynomial<V> &v)

   225   {

   226     Polynomial<U> tmp=u;

   227     tmp+=v;

   228     return tmp;

   229   }

   231   ///\e

   233   ///\relates Polynomial

   234   ///

   235   template<class U,class V>

   236   Polynomial<U> operator-(const Polynomial<U> &u,const Polynomial<V> &v)

   237   {

   238     Polynomial<U> tmp=u;

   239     tmp-=v;

   240     return tmp;

   241   }

   243   ///\e

   245   ///\relates Polynomial

   246   ///

   247   template<class U,class V>

   248   Polynomial<U> operator*(const Polynomial<U> &u,const Polynomial<V> &v)

   249   {

   250     Polynomial<U> tmp(u.deg()+v.deg());

   251     for(int i=0;i<=v.deg();i++)

   252       for(int j=0;j<=u.deg();j++)

   253 	tmp[i+j]+=v[i]*u[j];

   254     return tmp;

   255   }

   256   ///\e

   258   ///\relates Polynomial

   259   ///

   260   template<class U,class V>

   261   Polynomial<U> operator+(const Polynomial<U> &u,const V &v)

   262   {

   263     Polynomial<U> tmp=u;

   264     tmp+=v;

   265     return tmp;

   266   }

   267   ///\e

   269   ///\relates Polynomial

   270   ///

   271   template<class U,class V>

   272   Polynomial<U> operator+(const V &v,const Polynomial<U> &u)

   273   {

   274     Polynomial<U> tmp=u;

   275     tmp+=v;

   276     return tmp;

   277   }

   278   ///\e

   280   ///\relates Polynomial

   281   ///

   282   template<class U,class V>

   283   Polynomial<U> operator-(const Polynomial<U> &u,const V &v)

   284   {

   285     Polynomial<U> tmp=u;

   286     tmp-=v;

   287     return tmp;

   288   }

   289   ///\e

   291   ///\relates Polynomial

   292   ///

   293   template<class U>

   294   Polynomial<U> operator-(const Polynomial<U> &u)

   295   {

   296     Polynomial<U> tmp(u.deg());

   297     for(int i=0;i<=u.deg();i++) tmp[i]=-u[i];

   298     return tmp;

   299   }

   300   ///\e

   302   ///\relates Polynomial

   303   ///

   304   template<class U,class V>

   305   Polynomial<U> operator-(const V &v,const Polynomial<U> &u)

   306   {

   307     Polynomial<U> tmp=-u;

   308     tmp+=v;

   309     return tmp;

   310   }

   311   ///\e

   313   ///\relates Polynomial

   314   ///

   315   template<class U,class V>

   316   Polynomial<U> operator*(const Polynomial<U> &u,const V &v)

   317   {

   318     Polynomial<U> tmp=u;

   319     tmp*=v;

   320     return tmp;

   321   }

   322   ///\e

   324   ///\relates Polynomial

   325   ///

   326   template<class U,class V>

   327   Polynomial<U> operator*(const V &v,const Polynomial<U> &u)

   328   {

   329     Polynomial<U> tmp=u;

   330     tmp*=v;

   331     return tmp;

   332   }

   333   ///\e

   335   ///\relates Polynomial

   336   ///

   337   template<class U,class V>

   338   Polynomial<U> operator/(const Polynomial<U> &u,const V &v)

   339   {

   340     Polynomial<U> tmp=u;

   341     tmp/=v;

   342     return tmp;

   343   }

   345   /// @}

   347 } //END OF NAMESPACE LEMON

   349 #endif // LEMON_POLYNOMIAL_H

author	alpar
	Mon, 04 Sep 2006 19:12:44 +0000
changeset 2194	eaf16c8f6fef
child 2199	1229af45cc69
permissions	-rw-r--r--