|
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 */ |
|
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 |
|
30 namespace 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<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. |
|
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 |