# source:lemon-0.x/lemon/polynomial.h

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 12 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 8.2 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 */
18
19#ifndef LEMON_BEZIER_H
20#define LEMON_BEZIER_H
21
22///\ingroup misc
23///\file
24///\brief A simple class implementing polynomials.
25///
26///\author Alpar Juttner
27
28#include<vector>
29
30namespace lemon {
31
32  /// \addtogroup misc
33  /// @{
34
35  ///Simple polinomial class
36
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.
56
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.
62
63    ///Set the degree of the polynomial. In fact it resizes the
64    ///coefficient vector.
65    void deg(int d) { _coeff.resize(d+1);}
66
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];}
72
73    ///Substitute the value u into the polinomial.
74
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<dim2::Point<double> > line(1);
80    ///  line[0]=dim2::Point<double>(12,25);
81    ///  line[1]=dim2::Point<double>(2,7);
82    ///  ...
83    ///  dim2::Point<double> d = line.subst<dim2::Point<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.
101
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    }
110
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    }
118
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    }
126
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    }
135
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    }
144
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    }
192
193  };
194
195  ///Equality comparison
196
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  }
207
208  ///Non-equality comparison
209
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  }
218
219  ///\e
220
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  }
230
231  ///\e
232
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  }
242
243  ///\e
244
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
257
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
268
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
279
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
290
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
301
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
312
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
323
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
334
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  }
344
345  /// @}
346
347} //END OF NAMESPACE LEMON
348
349#endif // LEMON_POLYNOMIAL_H
Note: See TracBrowser for help on using the repository browser.