Java API By Example, From Geeks To Geeks.

# Java > Open Source Codes > org > jscience > mathematics > functions > 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 is7  * 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  *

This class represents a mathematical expression involving a sum of powers26  * in one or more {@link Variable variables} multiplied by 27  * coefficients (such as x² + x·y + 3y²).

28  * 29  *

Polynomials are characterized by the type of variable they operate 30  * upon. For example:[code]31  * Variable> varX = new Variable.Local>("x");32  * Polynomial> x = Polynomial.valueOf(Measure.valueOf(1, SI.METER), varX);33  * and34  * Variable varX = new Variable.Local("x");35  * Polynomial 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.

40  * 41  *

Terms (others than {@link Term#ONE ONE}) having zero (additive identity) 42  * for coefficient are automatically removed.

43  * 44  * @author Jean-Marie Dautelle45  * @version 3.1, April 1, 200646  */47 public class Polynomial> extends Function implements 48          Ring> {49 50     /**51      * Holds the terms to coefficients mapping 52      * (never empty, holds Term.ONE when constant)53      */54     FastMap _termToCoef = new FastMap();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 valueOf(coefficient, Term.valueOf(variable, 1))69      */70     public static > Polynomial valueOf(R coefficient,71             Variable 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 coefficient * term82      */83     public static > Polynomial 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 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 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 null110      * 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 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 this + Constant.valueOf(constantValue)138      */139     public Polynomial 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 this · Constant.valueOf(constantValue)149      */150     public Polynomial 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 this + that159      */160     public Polynomial plus(Polynomial that) {161         Polynomial result = Polynomial.newInstance();162         R zero = null;163         result._termToCoef.putAll(this._termToCoef);164         result._termToCoef.putAll(that._termToCoef);165         for (FastMap.Entry 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 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 - this190      */191     public Polynomial opposite() {192         Polynomial result = Polynomial.newInstance();193         for (FastMap.Entry 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 this - that205      */206     public Polynomial minus(Polynomial 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 this · that215      */216     public Polynomial times(Polynomial that) {217         Polynomial result = Polynomial.newInstance();218         R zero = null;219         for (Map.Entry entry1 : this._termToCoef.entrySet()) {220             Term t1 = entry1.getKey();221             R c1 = entry1.getValue();222             for (Map.Entry 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 as244      * argument to this function.245      * @return the polynomial (this o that)246      * @throws FunctionException if this function is not univariate.247      */248     public Polynomial compose(Polynomial that) {249         List > variables = getVariables();250         if (getVariables().size() != 1)251             throw new FunctionException("This polynomial is not monovariate");252         Variable v = variables.get(0);253         Polynomial result = null;254         for (Map.Entry entry : this._termToCoef.entrySet()) {255             Term term = entry.getKey();256             Constant cst = Constant.valueOf(entry.getValue());257             int power = term.getPower(v);258             if (power > 0) {259                 Polynomial fn = that.pow(power);260                 result = (result != null) ? result.plus(cst.times(fn)) : cst261                         .times(fn);262             } else { // power = 0263 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 Function compose(Function that) {276       return (Function) ((that instanceof Polynomial) ?277       compose((Polynomial)that) : super.compose(that)); 278     }279 280     @Override 281     public Polynomial differentiate(Variable v) {282         if (this.getOrder(v) > 0) {283             Polynomial result = null;284             for (Map.Entry 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 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 multiply(R o, int n) {303         if (n <= 0)304             throw new IllegalArgumentException ("n: " + n305                     + " 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 integrate(Variable v) {321         Polynomial result = null;322         for (Map.Entry 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 p = valueOf(newCoef, newTerm);329             result = (result != null) ? result.plus(p) : p;330         }331         return result;332     }333 334     @Override 335     public Function plus(Function that) {336         return (that instanceof Polynomial) ?337                 this.plus((Polynomial)that) : super.plus(that); 338     }339 340     @Override 341     public Function minus(Function that) {342         return (that instanceof Polynomial) ?343                 this.minus((Polynomial)that) : super.minus(that); 344     }345 346     @Override 347     public Function times(Function that) {348         return (that instanceof Polynomial) ?349                 this.times((Polynomial)that) : super.times(that); 350     }351     352     @Override 353     public Polynomial pow(int n) {354         return (Polynomial) super.pow(n);355     }356 357     @SuppressWarnings ("unchecked")358     @Override 359     public List > getVariables() {360         List vars = _termToCoef.head().getNext().getKey().getVariables();361         for (FastMap.Entry e = _termToCoef.head().getNext(), 362                 end = _termToCoef.tail(); (e = e.getNext()) != end;) {363             vars = merge(vars, e.getKey().getVariables());364         }365         return (List >) vars;366     }367 368     @Override 369     @SuppressWarnings ("unchecked")370     public R evaluate() {371         R sum = null;372         for (Map.Entry 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 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 > Polynomial newInstance() {422         return FACTORY.object();423     }424     private static final Factory FACTORY = new Factory() {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 }` Popular Tags