src/math/Polynomial.hpp

/*
 * Copyright (C) 2000-2004  Object Oriented Parallel Simulation Engine (OOPSE) project
 * 
 * Contact: oopse@oopse.org
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation; either version 2.1
 * of the License, or (at your option) any later version.
 * All we ask is that proper credit is given for our work, which includes
 * - but is not limited to - adding the above copyright notice to the beginning
 * of your source code files, and to any copyright notice that you may distribute
 * with programs based on this work.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 */

/**
 * @file Polynomial.hpp
 * @author    teng lin
 * @date  11/16/2004
 * @version 1.0
 */ 

#ifndef MATH_POLYNOMIAL_HPP
#define MATH_POLYNOMIAL_HPP

#include <list>
#include <utility>
#include <map>

namespace oopse {

template<typename ElemType> pow(ElemType x, int N) {
    ElemType result(1);

    for (int i = 0; i < N; ++i) {
        result *= x;
    }

    return result;
}

/**
 * @class Polynomial Polynomial.hpp "math/Polynomial.hpp"
 * A generic Polynomial class
 */
template<typename ElemType>
class Polynomial {

    public:
        
        typedef int ExponentType;
        typedef ElemType CoefficientType;
        typedef std::map<ExponentType, CoefficientType> PolynomialPairMap;
        typedef PolynomialPairMap::iterator PolynomialIterator;

        /** 
         * Calculates the value of this Polynomial evaluated at the given x value.
         * @return The value of this Polynomial evaluates at the given x value
         * @param x the value of the independent variable for this Polynomial function
         */
        ElemType evaluate(const ElemType& x) {
            ElemType result;
            double exponent;
            double coefficient;
            
            for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) {
                exponent = i->first;
                coefficient = i->second;
                result  += pow(x, exponent) * coefficient;
            }

            return result;
        }

        /**
         * Returns the first derivative of this polynomial.
         * @return the first derivative of this polynomial
         * @param x
         */
        ElemType evaluateDerivative(const ElemType& x) {
            ElemType result;
            double exponent;
            double coefficient;
            
            for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) {
                exponent = i->first;
                coefficient = i->second;
                result  += pow(x, exponent - 1) * coefficient * exponent;
            }

            return result;
        }

        /**
         * Set the coefficent of the specified exponent, if the coefficient is already there, it
         * will be overwritten.
         * @param exponent exponent of a term in this Polynomial 
         * @param coefficient multiplier of a term in this Polynomial 
         */
        
        void setCoefficient(int exponent, const ElemType& coefficient) {
            polyPairMap_.insert(PolynomialPairMap::value_type(exponent, coefficient));
        }

        /**
         * Set the coefficent of the specified exponent. If the coefficient is already there,  just add the
         * new coefficient to the old one, otherwise,  just call setCoefficent
         * @param exponent exponent of a term in this Polynomial 
         * @param coefficient multiplier of a term in this Polynomial 
         */
        
        void addCoefficient(int exponent, const ElemType& coefficient) {
            PolynomialIterator i = find(exponent);

            if (i != end()) {
                i->second += coefficient;
            } else {
                setCoefficient(exponent, coefficient);
            }
        }


        /**
         * Returns the coefficient associated with the given power for this Polynomial.
         * @return the coefficient associated with the given power for this Polynomial
         * @exponent exponent of any term in this Polynomial
         */
        ElemType getCoefficient(ExponentType exponent) {
            PolynomialIterator i = find(exponent);

            if (i != end()) {
                return i->second;
            } else {
                return ElemType(0);
            }
        }

        PolynomialIterator begin() {
            return polyPairMap_.begin();
        }
        
        PolynomialIterator end() {
            return polyPairMap_.end();
        }

        PolynomialIterator find(ExponentType exponent) {
            return polyPairMap_.find();
        }

        size_t size() {
            return polyPairMap_.size();
        }
        
    private:
        
        PolynomialPairMap polyPairMap_;
};


/**
 * Generates and returns the product of two given Polynomials.
 * @return A Polynomial containing the product of the two given Polynomial parameters
 */
template<typename ElemType>
Polynomial<ElemType> operator *(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
    typename Polynomial<ElemType>::PolynomialIterator i;
    typename Polynomial<ElemType>::PolynomialIterator j;
    typename Polynomial<ElemType>::PolynomialIterator k;
    Polynomial<ElemType> p;
    int exponent;
    int coefficient;
    
    for (i = p1.begin(); i !=p1.end(); ++i) {
        for (j = p1.begin(); j !=p1.end(); ++j) {
            exponent = i->first + j->first;            
            coefficient = i->second * j->second;
            k = p->find(exponent);

            if (k != p.end()) {
                p[exponent] = coefficient;
            } else {
                k->second += coefficient;
            }
        }
    }
}

/**
 * Generates and returns the sum of two given Polynomials.
 * @param p1 the first polynomial
 * @param p2 the second polynomial
 */
template<typename ElemType>
Polynomial<ElemType> operator +(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
    Polynomial<ElemType> p(p1);

    typename Polynomial<ElemType>::PolynomialIterator i;
    typename Polynomial<ElemType>::PolynomialIterator j;

    for (i =  p2.begin(); i  != p2.end(); ++i) {
        j = p.find(i->first);
        if (j == p.end()) {
            p[j] = i->second;
        } else {
            j->second += i->second;
        }
    }

    return p;

}

/**
 * Generates and returns the difference of two given Polynomials. 
 * @return
 * @param p1 the first polynomial
 * @param p2 the second polynomial
 */
template<typename ElemType>
Polynomial<ElemType> operator -(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
    Polynomial<ElemType> p(p1);

    typename Polynomial<ElemType>::PolynomialIterator i;
    typename Polynomial<ElemType>::PolynomialIterator j;

    for (i =  p2.begin(); i  != p2.end(); ++i) {
        j = p.find(i->first);
        if (j == p.end()) {
            p[j] = -i->second;
        } else {
            j->second -= i->second;
        }
    }

    return p;

}

/**
 * Tests if two polynomial have the same exponents
 * @return true if these all of the exponents in these Polynomial are identical
 * @param p1 the first polynomial
 * @param p2 the second polynomial
 * @note this function does not compare the coefficient
 */
template<typename ElemType>
bool equal(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {

    typename Polynomial<ElemType>::PolynomialIterator i;
    typename Polynomial<ElemType>::PolynomialIterator j;

    if (p1.size() !== p2.size() ) {
        return false;
    }
    
    for (i =  p1.begin(), j = p2.begin(); i  != p1.end() && j != p2.end(); ++i, ++j) {
        if (i->first != j->first) {
            return false;
        }
    }

    return true;
}

typedef Polynomial<double> DoublePolynomial;

} //end namespace oopse
#endif //MATH_POLYNOMIAL_HPP
Revision:	1786
Committed:	Fri Nov 26 02:13:56 2004 UTC (19 years, 8 months ago) by tim
File size:	8385 byte(s)
Log Message:	rename some files
#	Content
1	/*
2	* Copyright (C) 2000-2004 Object Oriented Parallel Simulation Engine (OOPSE) project
3	*
4	* Contact: oopse@oopse.org
5	*
6	* This program is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU Lesser General Public License
8	* as published by the Free Software Foundation; either version 2.1
9	* of the License, or (at your option) any later version.
10	* All we ask is that proper credit is given for our work, which includes
11	* - but is not limited to - adding the above copyright notice to the beginning
12	* of your source code files, and to any copyright notice that you may distribute
13	* with programs based on this work.
14	*
15	* This program is distributed in the hope that it will be useful,
16	* but WITHOUT ANY WARRANTY; without even the implied warranty of
17	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18	* GNU Lesser General Public License for more details.
19	*
20	* You should have received a copy of the GNU Lesser General Public License
21	* along with this program; if not, write to the Free Software
22	* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
23	*
24	*/
25
26	/**
27	* @file Polynomial.hpp
28	* @author teng lin
29	* @date 11/16/2004
30	* @version 1.0
31	*/
32
33	#ifndef MATH_POLYNOMIAL_HPP
34	#define MATH_POLYNOMIAL_HPP
35
36	#include <list>
37	#include <utility>
38	#include <map>
39
40	namespace oopse {
41
42	template<typename ElemType> pow(ElemType x, int N) {
43	ElemType result(1);
44
45	for (int i = 0; i < N; ++i) {
46	result *= x;
47	}
48
49	return result;
50	}
51
52	/**
53	* @class Polynomial Polynomial.hpp "math/Polynomial.hpp"
54	* A generic Polynomial class
55	*/
56	template<typename ElemType>
57	class Polynomial {
58
59	public:
60
61	typedef int ExponentType;
62	typedef ElemType CoefficientType;
63	typedef std::map<ExponentType, CoefficientType> PolynomialPairMap;
64	typedef PolynomialPairMap::iterator PolynomialIterator;
65
66	/**
67	* Calculates the value of this Polynomial evaluated at the given x value.
68	* @return The value of this Polynomial evaluates at the given x value
69	* @param x the value of the independent variable for this Polynomial function
70	*/
71	ElemType evaluate(const ElemType& x) {
72	ElemType result;
73	double exponent;
74	double coefficient;
75
76	for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) {
77	exponent = i->first;
78	coefficient = i->second;
79	result += pow(x, exponent) * coefficient;
80	}
81
82	return result;
83	}
84
85	/**
86	* Returns the first derivative of this polynomial.
87	* @return the first derivative of this polynomial
88	* @param x
89	*/
90	ElemType evaluateDerivative(const ElemType& x) {
91	ElemType result;
92	double exponent;
93	double coefficient;
94
95	for (PolynomialIterator i = polyPairMap_.begin(); i != polyPairMap_.end(); ++i) {
96	exponent = i->first;
97	coefficient = i->second;
98	result += pow(x, exponent - 1) * coefficient * exponent;
99	}
100
101	return result;
102	}
103
104	/**
105	* Set the coefficent of the specified exponent, if the coefficient is already there, it
106	* will be overwritten.
107	* @param exponent exponent of a term in this Polynomial
108	* @param coefficient multiplier of a term in this Polynomial
109	*/
110
111	void setCoefficient(int exponent, const ElemType& coefficient) {
112	polyPairMap_.insert(PolynomialPairMap::value_type(exponent, coefficient));
113	}
114
115	/**
116	* Set the coefficent of the specified exponent. If the coefficient is already there, just add the
117	* new coefficient to the old one, otherwise, just call setCoefficent
118	* @param exponent exponent of a term in this Polynomial
119	* @param coefficient multiplier of a term in this Polynomial
120	*/
121
122	void addCoefficient(int exponent, const ElemType& coefficient) {
123	PolynomialIterator i = find(exponent);
124
125	if (i != end()) {
126	i->second += coefficient;
127	} else {
128	setCoefficient(exponent, coefficient);
129	}
130	}
131
132
133	/**
134	* Returns the coefficient associated with the given power for this Polynomial.
135	* @return the coefficient associated with the given power for this Polynomial
136	* @exponent exponent of any term in this Polynomial
137	*/
138	ElemType getCoefficient(ExponentType exponent) {
139	PolynomialIterator i = find(exponent);
140
141	if (i != end()) {
142	return i->second;
143	} else {
144	return ElemType(0);
145	}
146	}
147
148	PolynomialIterator begin() {
149	return polyPairMap_.begin();
150	}
151
152	PolynomialIterator end() {
153	return polyPairMap_.end();
154	}
155
156	PolynomialIterator find(ExponentType exponent) {
157	return polyPairMap_.find();
158	}
159
160	size_t size() {
161	return polyPairMap_.size();
162	}
163
164	private:
165
166	PolynomialPairMap polyPairMap_;
167	};
168
169
170	/**
171	* Generates and returns the product of two given Polynomials.
172	* @return A Polynomial containing the product of the two given Polynomial parameters
173	*/
174	template<typename ElemType>
175	Polynomial<ElemType> operator *(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
176	typename Polynomial<ElemType>::PolynomialIterator i;
177	typename Polynomial<ElemType>::PolynomialIterator j;
178	typename Polynomial<ElemType>::PolynomialIterator k;
179	Polynomial<ElemType> p;
180	int exponent;
181	int coefficient;
182
183	for (i = p1.begin(); i !=p1.end(); ++i) {
184	for (j = p1.begin(); j !=p1.end(); ++j) {
185	exponent = i->first + j->first;
186	coefficient = i->second * j->second;
187	k = p->find(exponent);
188
189	if (k != p.end()) {
190	p[exponent] = coefficient;
191	} else {
192	k->second += coefficient;
193	}
194	}
195	}
196	}
197
198	/**
199	* Generates and returns the sum of two given Polynomials.
200	* @param p1 the first polynomial
201	* @param p2 the second polynomial
202	*/
203	template<typename ElemType>
204	Polynomial<ElemType> operator +(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
205	Polynomial<ElemType> p(p1);
206
207	typename Polynomial<ElemType>::PolynomialIterator i;
208	typename Polynomial<ElemType>::PolynomialIterator j;
209
210	for (i = p2.begin(); i != p2.end(); ++i) {
211	j = p.find(i->first);
212	if (j == p.end()) {
213	p[j] = i->second;
214	} else {
215	j->second += i->second;
216	}
217	}
218
219	return p;
220
221	}
222
223	/**
224	* Generates and returns the difference of two given Polynomials.
225	* @return
226	* @param p1 the first polynomial
227	* @param p2 the second polynomial
228	*/
229	template<typename ElemType>
230	Polynomial<ElemType> operator -(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
231	Polynomial<ElemType> p(p1);
232
233	typename Polynomial<ElemType>::PolynomialIterator i;
234	typename Polynomial<ElemType>::PolynomialIterator j;
235
236	for (i = p2.begin(); i != p2.end(); ++i) {
237	j = p.find(i->first);
238	if (j == p.end()) {
239	p[j] = -i->second;
240	} else {
241	j->second -= i->second;
242	}
243	}
244
245	return p;
246
247	}
248
249	/**
250	* Tests if two polynomial have the same exponents
251	* @return true if these all of the exponents in these Polynomial are identical
252	* @param p1 the first polynomial
253	* @param p2 the second polynomial
254	* @note this function does not compare the coefficient
255	*/
256	template<typename ElemType>
257	bool equal(const Polynomial<ElemType>& p1, const Polynomial<ElemType>& p2) {
258
259	typename Polynomial<ElemType>::PolynomialIterator i;
260	typename Polynomial<ElemType>::PolynomialIterator j;
261
262	if (p1.size() !== p2.size() ) {
263	return false;
264	}
265
266	for (i = p1.begin(), j = p2.begin(); i != p1.end() && j != p2.end(); ++i, ++j) {
267	if (i->first != j->first) {
268	return false;
269	}
270	}
271
272	return true;
273	}
274
275	typedef Polynomial<double> DoublePolynomial;
276
277	} //end namespace oopse
278	#endif //MATH_POLYNOMIAL_HPP