Moved the gui to glemon/trunk.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_BEZIER_H
20 #define LEMON_BEZIER_H
24 ///\brief A simple class implementing polynomials.
26 ///\author Alpar Juttner
35 ///Simple polinomial class
37 ///This class implements a polynomial where the coefficients are of
40 ///The coefficients are stored in an std::vector.
44 std::vector<T> _coeff;
46 ///Construct a polynomial of degree \c d.
47 explicit Polynomial(int d=0) : _coeff(d+1) {}
49 template<class U> Polynomial(const U &u) : _coeff(1,u) {}
51 template<class U> Polynomial(const Polynomial<U> &u) : _coeff(u.deg()+1)
53 for(int i=0;i<(int)_coeff.size();i++) _coeff[i]=u[i];
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.
79 /// Polynomial<xy<double> > line(1);
80 /// line[0]=xy<double>(12,25);
81 /// line[1]=xy<double>(2,7);
83 /// xy<double> d = line.subst<xy<double> >(23.2);
87 /// Polynomial<double> p;
88 /// Polynomial<double> q;
90 /// Polynomial<double> s = p.subst<Polynomial<double> >(q);
92 template<class R,class U>
93 R subst(const U &u) const
95 typename std::vector<T>::const_reverse_iterator i=_coeff.rbegin();
97 for(++i;i!=_coeff.rend();++i) v=v*u+*i;
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.)
106 T operator()(const U &u) const
111 ///Derivate the polynomial (in place)
112 Polynomial &derivateMyself()
114 for(int i=1;i<(int)_coeff.size();i++) _coeff[i-1]=i*_coeff[i];
119 ///Return the derivate of the polynomial
120 Polynomial derivate() const
122 Polynomial tmp(deg()-1);
123 for(int i=1;i<(int)_coeff.size();i++) tmp[i-1]=i*_coeff[i];
127 ///Integrate the polynomial (in place)
128 Polynomial &integrateMyself()
130 _coeff.push_back(T());
131 for(int i=_coeff.size()-1;i>=0;i--) _coeff[i]=_coeff[i-1]/i;
136 ///Return the integrate of the polynomial
137 Polynomial integrate() const
139 Polynomial tmp(deg()+1);
141 for(int i=0;i<(int)_coeff.size();i++) tmp[i+1]=_coeff[i]/(i+1);
147 Polynomial &operator+=(const Polynomial<U> &p)
149 if(p.deg()>deg()) _coeff.resize(p.deg()+1);
150 for(int i=0;i<=(int)std::min(deg(),p.deg());i++)
156 Polynomial &operator-=(const Polynomial<U> &p)
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];
164 Polynomial &operator+=(const U &u)
171 Polynomial &operator-=(const U &u)
178 Polynomial &operator*=(const U &u)
180 for(typename std::vector<T>::iterator i=_coeff.begin();i!=_coeff.end();++i)
186 Polynomial &operator/=(const U &u)
188 for(typename std::vector<T>::iterator i=_coeff.begin();i!=_coeff.end();++i)
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)
203 if(u.deg()!=v.deg()) return false;
204 for(int i=0;i<=u.deg();i++) if(u[i]!=v[i]) return false;
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)
221 ///\relates Polynomial
223 template<class U,class V>
224 Polynomial<U> operator+(const Polynomial<U> &u,const Polynomial<V> &v)
233 ///\relates Polynomial
235 template<class U,class V>
236 Polynomial<U> operator-(const Polynomial<U> &u,const Polynomial<V> &v)
245 ///\relates Polynomial
247 template<class U,class V>
248 Polynomial<U> operator*(const Polynomial<U> &u,const Polynomial<V> &v)
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++)
258 ///\relates Polynomial
260 template<class U,class V>
261 Polynomial<U> operator+(const Polynomial<U> &u,const V &v)
269 ///\relates Polynomial
271 template<class U,class V>
272 Polynomial<U> operator+(const V &v,const Polynomial<U> &u)
280 ///\relates Polynomial
282 template<class U,class V>
283 Polynomial<U> operator-(const Polynomial<U> &u,const V &v)
291 ///\relates Polynomial
294 Polynomial<U> operator-(const Polynomial<U> &u)
296 Polynomial<U> tmp(u.deg());
297 for(int i=0;i<=u.deg();i++) tmp[i]=-u[i];
302 ///\relates Polynomial
304 template<class U,class V>
305 Polynomial<U> operator-(const V &v,const Polynomial<U> &u)
307 Polynomial<U> tmp=-u;
313 ///\relates Polynomial
315 template<class U,class V>
316 Polynomial<U> operator*(const Polynomial<U> &u,const V &v)
324 ///\relates Polynomial
326 template<class U,class V>
327 Polynomial<U> operator*(const V &v,const Polynomial<U> &u)
335 ///\relates Polynomial
337 template<class U,class V>
338 Polynomial<U> operator/(const Polynomial<U> &u,const V &v)
347 } //END OF NAMESPACE LEMON
349 #endif // LEMON_POLYNOMIAL_H