33 |
|
#ifndef MATH_POLYNOMIAL_HPP |
34 |
|
#define MATH_POLYNOMIAL_HPP |
35 |
|
|
36 |
+ |
#include <iostream> |
37 |
|
#include <list> |
38 |
+ |
#include <map> |
39 |
|
#include <utility> |
40 |
|
|
41 |
|
namespace oopse { |
42 |
|
|
43 |
< |
template<typename ElemType> pow(ElemType x, int N) { |
43 |
> |
template<typename ElemType> ElemType pow(ElemType x, int N) { |
44 |
|
ElemType result(1); |
45 |
|
|
46 |
|
for (int i = 0; i < N; ++i) { |
62 |
|
typedef int ExponentType; |
63 |
|
typedef ElemType CoefficientType; |
64 |
|
typedef std::map<ExponentType, CoefficientType> PolynomialPairMap; |
65 |
< |
typedef PolynomialPairMap::iterator PolynomialIterator; |
66 |
< |
|
65 |
> |
typedef PolynomialPairMap::iterator iterator; |
66 |
> |
typedef PolynomialPairMap::const_iterator const_iterator; |
67 |
|
/** |
68 |
|
* Calculates the value of this Polynomial evaluated at the given x value. |
69 |
|
* @return The value of this Polynomial evaluates at the given x value |
70 |
|
* @param x the value of the independent variable for this Polynomial function |
71 |
|
*/ |
72 |
|
ElemType evaluate(const ElemType& x) { |
73 |
< |
ElemType result; |
73 |
> |
ElemType result = ElemType(); |
74 |
|
double exponent; |
75 |
|
double coefficient; |
76 |
|
|
77 |
< |
for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
77 |
> |
for (iterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
78 |
|
exponent = i->first; |
79 |
|
coefficient = i->second; |
80 |
|
result += pow(x, exponent) * coefficient; |
89 |
|
* @param x |
90 |
|
*/ |
91 |
|
ElemType evaluateDerivative(const ElemType& x) { |
92 |
< |
ElemType result; |
92 |
> |
ElemType result = ElemType(); |
93 |
|
double exponent; |
94 |
|
double coefficient; |
95 |
|
|
96 |
< |
for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
96 |
> |
for (iterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) { |
97 |
|
exponent = i->first; |
98 |
|
coefficient = i->second; |
99 |
|
result += pow(x, exponent - 1) * coefficient * exponent; |
103 |
|
} |
104 |
|
|
105 |
|
/** |
106 |
+ |
* Set the coefficent of the specified exponent, if the coefficient is already there, it |
107 |
+ |
* will be overwritten. |
108 |
|
* @param exponent exponent of a term in this Polynomial |
109 |
|
* @param coefficient multiplier of a term in this Polynomial |
110 |
|
*/ |
114 |
|
} |
115 |
|
|
116 |
|
/** |
117 |
+ |
* Set the coefficent of the specified exponent. If the coefficient is already there, just add the |
118 |
+ |
* new coefficient to the old one, otherwise, just call setCoefficent |
119 |
+ |
* @param exponent exponent of a term in this Polynomial |
120 |
+ |
* @param coefficient multiplier of a term in this Polynomial |
121 |
+ |
*/ |
122 |
+ |
|
123 |
+ |
void addCoefficient(int exponent, const ElemType& coefficient) { |
124 |
+ |
iterator i = polyPairMap_.find(exponent); |
125 |
+ |
|
126 |
+ |
if (i != end()) { |
127 |
+ |
i->second += coefficient; |
128 |
+ |
} else { |
129 |
+ |
setCoefficient(exponent, coefficient); |
130 |
+ |
} |
131 |
+ |
} |
132 |
+ |
|
133 |
+ |
|
134 |
+ |
/** |
135 |
|
* Returns the coefficient associated with the given power for this Polynomial. |
136 |
|
* @return the coefficient associated with the given power for this Polynomial |
137 |
|
* @exponent exponent of any term in this Polynomial |
138 |
|
*/ |
139 |
|
ElemType getCoefficient(ExponentType exponent) { |
140 |
< |
PolynomialIterator i = find(exponent); |
140 |
> |
iterator i = polyPairMap_.find(exponent); |
141 |
|
|
142 |
|
if (i != end()) { |
143 |
|
return i->second; |
146 |
|
} |
147 |
|
} |
148 |
|
|
149 |
< |
PolynomialIterator begin() { |
149 |
> |
iterator begin() { |
150 |
|
return polyPairMap_.begin(); |
151 |
|
} |
152 |
+ |
|
153 |
+ |
const_iterator begin() const{ |
154 |
+ |
return polyPairMap_.begin(); |
155 |
+ |
} |
156 |
|
|
157 |
< |
PolynomialIterator end() { |
157 |
> |
iterator end() { |
158 |
|
return polyPairMap_.end(); |
159 |
|
} |
160 |
|
|
161 |
< |
PolynomialIterator find(ExponentType exponent) { |
162 |
< |
return polyPairMap_.find(); |
161 |
> |
const_iterator end() const{ |
162 |
> |
return polyPairMap_.end(); |
163 |
|
} |
164 |
|
|
165 |
+ |
iterator find(ExponentType exponent) { |
166 |
+ |
return polyPairMap_.find(exponent); |
167 |
+ |
} |
168 |
+ |
|
169 |
|
size_t size() { |
170 |
|
return polyPairMap_.size(); |
171 |
|
} |
182 |
|
*/ |
183 |
|
template<typename ElemType> |
184 |
|
Polynomial<ElemType> operator *(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
185 |
< |
typename Polynomial<ElemType>::PolynomialIterator i; |
186 |
< |
typename Polynomial<ElemType>::PolynomialIterator j; |
157 |
< |
typename Polynomial<ElemType>::PolynomialIterator k; |
185 |
> |
typename Polynomial<ElemType>::const_iterator i; |
186 |
> |
typename Polynomial<ElemType>::const_iterator j; |
187 |
|
Polynomial<ElemType> p; |
159 |
– |
int exponent; |
160 |
– |
int coefficient; |
188 |
|
|
189 |
|
for (i = p1.begin(); i !=p1.end(); ++i) { |
190 |
< |
for (j = p1.begjn(); j !=p1.end(); ++j) { |
191 |
< |
exponent = i->first + j->first; |
165 |
< |
coefficient = i->second * j->second; |
166 |
< |
k = p->find(exponent); |
167 |
< |
|
168 |
< |
if (k != p.end()) { |
169 |
< |
p[exponent] = coefficient; |
170 |
< |
} else { |
171 |
< |
k->second += coefficient; |
172 |
< |
} |
190 |
> |
for (j = p2.begin(); j !=p2.end(); ++j) { |
191 |
> |
p.addCoefficient( i->first + j->first, i->second * j->second); |
192 |
|
} |
193 |
|
} |
194 |
+ |
|
195 |
+ |
return p; |
196 |
|
} |
197 |
|
|
198 |
|
/** |
204 |
|
Polynomial<ElemType> operator +(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
205 |
|
Polynomial<ElemType> p(p1); |
206 |
|
|
207 |
< |
typename Polynomial<ElemType>::PolynomialIterator i; |
187 |
< |
typename Polynomial<ElemType>::PolynomialIterator j; |
207 |
> |
typename Polynomial<ElemType>::const_iterator i; |
208 |
|
|
209 |
|
for (i = p2.begin(); i != p2.end(); ++i) { |
210 |
< |
j = p.find(i->first); |
191 |
< |
if (j == p.end()) { |
192 |
< |
p[j] = i->second; |
193 |
< |
} else { |
194 |
< |
j->second += i->second; |
195 |
< |
} |
210 |
> |
p.addCoefficient(i->first, i->second); |
211 |
|
} |
212 |
|
|
213 |
|
return p; |
224 |
|
Polynomial<ElemType> operator -(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
225 |
|
Polynomial<ElemType> p(p1); |
226 |
|
|
227 |
< |
typename Polynomial<ElemType>::PolynomialIterator i; |
213 |
< |
typename Polynomial<ElemType>::PolynomialIterator j; |
227 |
> |
typename Polynomial<ElemType>::const_iterator i; |
228 |
|
|
229 |
|
for (i = p2.begin(); i != p2.end(); ++i) { |
230 |
< |
j = p.find(i->first); |
217 |
< |
if (j == p.end()) { |
218 |
< |
p[j] = -i->second; |
219 |
< |
} else { |
220 |
< |
j->second -= i->second; |
221 |
< |
} |
230 |
> |
p.addCoefficient(i->first, -i->second); |
231 |
|
} |
232 |
|
|
233 |
|
return p; |
244 |
|
template<typename ElemType> |
245 |
|
bool equal(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) { |
246 |
|
|
247 |
< |
typename Polynomial<ElemType>::PolynomialIterator i; |
248 |
< |
typename Polynomial<ElemType>::PolynomialIterator j; |
247 |
> |
typename Polynomial<ElemType>::const_iterator i; |
248 |
> |
typename Polynomial<ElemType>::const_iterator j; |
249 |
|
|
250 |
|
if (p1.size() !== p2.size() ) { |
251 |
|
return false; |