Polynomial


1   /*
2    * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
3    * Copyright (C) 2006 - JScience (http://jscience.org/)
4    * All rights reserved.
5    * 
6    * Permission to use, copy, modify, and distribute this software is
7    * freely granted, provided that this notice is preserved.
8    */
9   package org.jscience.mathematics.functions;
10  
11  import java.util.List  ;
12  import java.util.Map  ;
13  import java.util.Set  ;
14  
15  import org.jscience.mathematics.structures.GroupAdditive;
16  import org.jscience.mathematics.structures.GroupMultiplicative;
17  import org.jscience.mathematics.structures.Ring;
18  
19  import javolution.util.FastMap;
20  import javolution.util.FastTable;
21  import javolution.text.Text;
22  import javolution.text.TextBuilder;
23  
24  /**
25   * <p> This class represents a mathematical expression involving a sum of powers
26   *     in one or more {@link Variable variables} multiplied by 
27   *     coefficients (such as <code>x² + x·y + 3y²</code>).</p>
28   *     
29   * <p> Polynomials are characterized by the type of variable they operate 
30   *     upon. For example:[code]
31   *           Variable<Measure<?>> varX = new Variable.Local<Measure<?>>("x");
32   *           Polynomial<Measure<?>> x = Polynomial.valueOf(Measure.valueOf(1, SI.METER), varX);
33   *     and
34   *           Variable<Complex> varX = new Variable.Local<Complex>("x");
35   *           Polynomial<Complex> x = Polynomial.valueOf(Complex.ONE, varX);[/code]
36   *     are two different polynomials, the first one operates on physical 
37   *     {@link org.jscience.physics.measures.Measure measures},
38   *     whereas the second operates on 
39   *     {@link org.jscience.mathematics.numbers.Complex complex} numbers.</p>
40   *     
41   * <p> Terms (others than {@link Term#ONE ONE}) having zero (additive identity) 
42   *     for coefficient are automatically removed.</p>    
43   * 
44   * @author  <a HREF="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
45   * @version 3.1, April 1, 2006
46   */
47  public class Polynomial<R extends Ring<R>> extends Function<R, R> implements 
48           Ring<Polynomial<R>> {
49  
50      /**
51       * Holds the terms to coefficients mapping 
52       * (never empty, holds Term.ONE when constant)
53       */
54      FastMap<Term, R> _termToCoef = new FastMap<Term, R>();
55  
56      /**
57       * Default constructor.
58       */
59      Polynomial() {
60      }
61  
62      /**
63       * Returns an univariate polynomial of degree one with the specified 
64       * coefficient multiplier.
65       * 
66       * @param coefficient the coefficient for the variable of degree 1.  
67       * @param variable the variable for this polynomial.
68       * @return <code>valueOf(coefficient, Term.valueOf(variable, 1))</code>
69       */
70      public static <R extends Ring<R>> Polynomial<R> valueOf(R coefficient,
71              Variable<R> variable) {
72          return valueOf(coefficient, Term.valueOf(variable, 1));
73      }
74  
75      /**
76       * Returns a polynomial corresponding to the specified {@link Term term}
77       * with the specified coefficient multiplier.
78       * 
79       * @param coefficient the coefficient multiplier.  
80       * @param term the term multiplicand.
81       * @return <code>coefficient * term</code>
82       */
83      public static <R extends Ring<R>> Polynomial<R> valueOf(R coefficient,
84              Term term) {
85          if (term.equals(Term.ONE)) return Constant.valueOf(coefficient);
86          if (isZero(coefficient)) return Constant.valueOf(coefficient);
87          Polynomial<R> p = Polynomial.newInstance();
88          p._termToCoef.put(term, coefficient);
89          return p;
90      }
91  
92      private static boolean isZero(GroupAdditive coefficient) {
93          return coefficient.equals(coefficient.opposite());
94      }
95      
96      /**
97       * Returns the terms of this polynomial.
98       * 
99       * @return this polynomial's terms.
100      */
101     public Set  <Term> getTerms() {
102         return _termToCoef.unmodifiable().keySet();
103     }
104 
105     /**
106      * Returns the coefficient for the specified term.
107      * 
108      * @param term the term for which the coefficient is returned.
109      * @return the coefficient for the specified term or <code>null</code>
110      *         if this polynomial does not contain the specified term.
111      */
112     public final R getCoefficient(Term term) {
113         return _termToCoef.get(term);
114     }
115 
116     /**
117      * Returns the order of this polynomial for the specified variable.
118      * 
119      * @return the polynomial order relative to the specified variable.
120      */
121     public int getOrder(Variable<R> v) {
122         int order = 0;
123         for (Term term : _termToCoef.keySet()) {
124             int power = term.getPower(v);
125             if (power > order) {
126                 order = power;
127             }
128         }
129         return order;
130     }
131 
132     /**
133      * Returns the sum of this polynomial with a constant polynomial 
134      * having the specified value (convenience method).
135      * 
136      * @param constantValue the value of the constant polynomial to add.
137      * @return <code>this + Constant.valueOf(constantValue)</code>
138      */
139     public Polynomial<R> plus(R constantValue) {
140         return this.plus(Constant.valueOf(constantValue));
141     }
142 
143     /**
144      * Returns the product of this polynomial with a constant polynomial 
145      * having the specified value (convenience method).
146      * 
147      * @param constantValue the value of the constant polynomial to multiply.
148      * @return <code>this · Constant.valueOf(constantValue)</code>
149      */
150     public Polynomial<R> times(R constantValue) {
151         return this.times(Constant.valueOf(constantValue));
152     }
153 
154     /**
155      * Returns the sum of two polynomials.
156      * 
157      * @param that the polynomial being added.
158      * @return <code>this + that</code>
159      */
160     public Polynomial<R> plus(Polynomial<R> that) {
161         Polynomial<R> result = Polynomial.newInstance();
162         R zero = null;
163         result._termToCoef.putAll(this._termToCoef);
164         result._termToCoef.putAll(that._termToCoef);
165         for (FastMap.Entry<Term, R> e = result._termToCoef.head(), 
166                 end = result._termToCoef.tail(); (e = e.getNext()) != end;) {
167             Term term = e.getKey();
168             R thisCoef = this._termToCoef.get(term);
169             R thatCoef = that._termToCoef.get(term);
170             if ((thisCoef != null) && (thatCoef != null)) {
171                 R sum = thisCoef.plus(thatCoef);
172                 if (isZero(sum)) { // Remove entry (be careful iterating)
173                     FastMap.Entry<Term, R> prev = e.getPrevious();
174                     result._termToCoef.remove(term);
175                     e = prev; // Move back to previous entry.
176                     zero = sum; // To be used if constant polynomial.
177                 } else {
178                     result._termToCoef.put(term, sum);
179                 }
180             } // Else the current coefficient is correct.
181         }
182         if (result._termToCoef.size() == 0) return Constant.valueOf(zero);
183         return result;
184     }
185 
186     /**
187      * Returns the opposite of this polynomial.
188      * 
189      * @return <code> - this</code>
190      */
191     public Polynomial<R> opposite() {
192         Polynomial<R> result = Polynomial.newInstance();
193         for (FastMap.Entry<Term, R> e = _termToCoef.head(), 
194                 end = _termToCoef.tail(); (e = e.getNext()) != end;) {
195             result._termToCoef.put(e.getKey(), e.getValue().opposite());
196         }
197         return result;
198     }
199     
200     /**
201      * Returns the difference of two polynomials.
202      * 
203      * @param that the polynomial being subtracted.
204      * @return <code>this - that</code>
205      */
206     public Polynomial<R> minus(Polynomial<R> that) {
207         return this.plus(that.opposite());
208     }
209 
210     /**
211      * Returns the product of two polynomials.
212      * 
213      * @param that the polynomial multiplier.
214      * @return <code>this · that</code>
215      */
216     public Polynomial<R> times(Polynomial<R> that) {
217         Polynomial<R> result = Polynomial.newInstance();
218         R zero = null;
219         for (Map.Entry  <Term, R> entry1 : this._termToCoef.entrySet()) {
220             Term t1 = entry1.getKey();
221             R c1 = entry1.getValue();
222             for (Map.Entry  <Term, R> entry2 : that._termToCoef.entrySet()) {
223                 Term t2 = entry2.getKey();
224                 R c2 = entry2.getValue();
225                 Term t = t1.times(t2);
226                 R c = c1.times(c2);
227                 R prev = result.getCoefficient(t);
228                 R coef = (prev != null) ? prev.plus(c) : c;
229                 if (isZero(coef)) {
230                     zero = coef;
231                 } else {
232                     result._termToCoef.put(t, coef);
233                 }
234             }
235         }
236         if (result._termToCoef.size() == 0) return Constant.valueOf(zero);
237         return result;
238     }
239 
240     /**
241      * Returns the composition of this polynomial with the one specified.
242      *
243      * @param  that the polynomial for which the return value is passed as
244      *         argument to this function.
245      * @return the polynomial <code>(this o that)</code>
246      * @throws FunctionException if this function is not univariate.
247      */
248     public Polynomial<R> compose(Polynomial<R> that) {
249         List  <Variable<R>> variables = getVariables();
250         if (getVariables().size() != 1)
251             throw new FunctionException("This polynomial is not monovariate");
252         Variable<R> v = variables.get(0);
253         Polynomial<R> result = null;
254         for (Map.Entry  <Term, R> entry : this._termToCoef.entrySet()) {
255             Term term = entry.getKey();
256             Constant<R> cst = Constant.valueOf(entry.getValue());
257             int power = term.getPower(v);
258             if (power > 0) {
259                 Polynomial<R> fn = that.pow(power);
260                 result = (result != null) ? result.plus(cst.times(fn)) : cst
261                         .times(fn);
262             } else { // power = 0
263                 result = (result != null) ? result.plus(cst) : cst;
264             }
265         }
266         return result;
267     }
268 
269     ////////////////////////////////////////////////////////////////
270     // Overrides parent method potentially returning polynomials  //
271     ////////////////////////////////////////////////////////////////
272     
273     @SuppressWarnings  ("unchecked")
274     @Override  
275     public <Z> Function<Z, R> compose(Function<Z, R> that) {
276       return (Function<Z, R>) ((that instanceof Polynomial) ?
277       compose((Polynomial)that) : super.compose(that)); 
278     }
279 
280     @Override  
281     public Polynomial<R> differentiate(Variable<R> v) {
282         if (this.getOrder(v) > 0) {
283             Polynomial<R> result = null;
284             for (Map.Entry  <Term, R> entry : this._termToCoef.entrySet()) {
285                 Term term = entry.getKey();
286                 R coef = entry.getValue();
287                 int power = term.getPower(v);
288                 if (power > 0) {
289                     R newCoef = multiply(coef, power);
290                     Term newTerm = term.divide(Term.valueOf(v, 1));
291                     Polynomial<R> p = valueOf(newCoef, newTerm);
292                     result = (result != null) ? result.plus(p) : p;
293                 }
294             }
295             return result;
296         } else { // Returns zero.
297             R coef = _termToCoef.values().iterator().next();
298             return Constant.valueOf(coef.plus(coef.opposite()));
299         }
300     }
301 
302     private static <R extends Ring<R>> R multiply(R o, int n) {
303         if (n <= 0)
304             throw new IllegalArgumentException  ("n: " + n
305                     + " zero or negative values not allowed");
306         R shift2 = o;
307         R result = null;
308         while (n >= 1) { // Iteration.
309             if ((n & 1) == 1) {
310                 result = (result == null) ? shift2 : result.plus(shift2);
311             }
312             shift2 = shift2.plus(shift2);
313             n >>>= 1;
314         }
315         return result;
316     }
317 
318     @SuppressWarnings  ("unchecked")
319     @Override  
320     public Polynomial<R> integrate(Variable<R> v) {
321         Polynomial<R> result = null;
322         for (Map.Entry  <Term, R> entry : this._termToCoef.entrySet()) {
323             Term term = entry.getKey();
324             R coef = entry.getValue();
325             int power = term.getPower(v);
326             R newCoef = (R)((GroupMultiplicative)multiply((R)((GroupMultiplicative)coef).inverse(), power + 1)).inverse();
327             Term newTerm = term.times(Term.valueOf(v, 1));
328             Polynomial<R> p = valueOf(newCoef, newTerm);
329             result = (result != null) ? result.plus(p) : p;
330         }
331         return result;
332     }
333 
334     @Override  
335     public Function<R, R> plus(Function<R, R> that) {
336         return (that instanceof Polynomial) ?
337                 this.plus((Polynomial<R>)that) : super.plus(that);       
338     }
339 
340     @Override  
341     public Function<R, R> minus(Function<R, R> that) {
342         return (that instanceof Polynomial) ?
343                 this.minus((Polynomial<R>)that) : super.minus(that);       
344     }
345 
346     @Override  
347     public Function<R, R> times(Function<R, R> that) {
348         return (that instanceof Polynomial) ?
349                 this.times((Polynomial<R>)that) : super.times(that);       
350     }
351     
352     @Override  
353     public Polynomial<R> pow(int n) {
354         return (Polynomial<R>) super.pow(n);
355     }
356 
357     @SuppressWarnings  ("unchecked")
358     @Override  
359     public List  <Variable<R>> getVariables() {
360         List   vars = _termToCoef.head().getNext().getKey().getVariables();
361         for (FastMap.Entry<Term, R> e = _termToCoef.head().getNext(), 
362                 end = _termToCoef.tail(); (e = e.getNext()) != end;) {
363             vars = merge(vars, e.getKey().getVariables());
364         }
365         return (List  <Variable<R>>) vars;
366     }
367 
368     @Override  
369     @SuppressWarnings  ("unchecked")
370     public R evaluate() {
371         R sum = null;
372         for (Map.Entry  <Term, R> entry : _termToCoef.entrySet()) {
373             Term term = entry.getKey();
374             R coef = entry.getValue();
375             R termValue = (R) term.evaluate();
376             R value = (termValue != null) ? coef.times(termValue) : coef;
377             sum = (sum == null) ? value : sum.plus(value);
378         }
379         return sum;
380     }
381 
382     @Override  
383     public boolean equals(Object   obj) {
384         if (!(obj instanceof Polynomial))
385             return false;
386         Polynomial that = (Polynomial) obj;
387         return this._termToCoef.equals(that._termToCoef);
388     }
389 
390     @Override  
391     public int hashCode() {
392         return _termToCoef.hashCode();
393     }
394 
395     @Override  
396     public Text toText() {
397         FastTable<Term> terms = FastTable.newInstance();
398         terms.addAll(_termToCoef.keySet());
399         terms.sort();
400         TextBuilder tb = TextBuilder.newInstance();
401         for (int i=0, n = terms.size(); i < n; i++) {
402             if (i != 0) {
403                 tb.append(" + ");
404             }
405             tb.append('[').append(_termToCoef.get(terms.get(i)));
406             tb.append(']').append(terms.get(i));
407         }
408         return tb.toText();
409     }
410 
411     @Override  
412     public boolean move(ObjectSpace os) {
413         if (super.move(os)) {
414             _termToCoef.move(os);
415             return true;
416         }
417         return false;
418     }
419     
420     @SuppressWarnings  ("unchecked")
421     private static <R extends Ring<R>> Polynomial<R> newInstance() {
422         return FACTORY.object();
423     }
424     private static final Factory<Polynomial> FACTORY = new Factory<Polynomial>() {
425 
426         protected Polynomial create() {
427             return new Polynomial();
428         }
429         
430         protected void cleanup(Polynomial p) {
431             p._termToCoef.reset();
432         }
433     };
434 
435     private static final long serialVersionUID = 1L;
436 
437 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags