001: /*
002: * JScience - Java(TM) Tools and Libraries for the Advancement of Sciences.
003: * Copyright (C) 2006 - JScience (http://jscience.org/)
004: * All rights reserved.
005: *
006: * Permission to use, copy, modify, and distribute this software is
007: * freely granted, provided that this notice is preserved.
008: */
009: package org.jscience.mathematics.function;
010:
011: import java.util.List;
012: import java.util.Map;
013: import java.util.Set;
014:
015: import org.jscience.mathematics.structure.GroupAdditive;
016: import org.jscience.mathematics.structure.GroupMultiplicative;
017: import org.jscience.mathematics.structure.Ring;
018:
019: import javolution.util.FastMap;
020: import javolution.util.FastTable;
021: import javolution.context.ObjectFactory;
022: import javolution.text.Text;
023: import javolution.text.TextBuilder;
024:
025: /**
026: * <p> This class represents a mathematical expression involving a sum of powers
027: * in one or more {@link Variable variables} multiplied by
028: * coefficients (such as <code>x² + x·y + 3y²</code>).</p>
029: *
030: * <p> Polynomials are characterized by the type of variable they operate
031: * upon. For example:[code]
032: * Variable<Amount<?>> varX = new Variable.Local<Amount<?>>("x");
033: * Polynomial<Amount<?>> x = Polynomial.valueOf(Amount.valueOf(1, SI.METER), varX);
034: * and
035: * Variable<Complex> varX = new Variable.Local<Complex>("x");
036: * Polynomial<Complex> x = Polynomial.valueOf(Complex.ONE, varX);[/code]
037: * are two different polynomials, the first one operates on physical
038: * {@link org.jscience.physics.amount.Amount measures},
039: * whereas the second operates on
040: * {@link org.jscience.mathematics.number.Complex complex} numbers.</p>
041: *
042: * <p> Terms (others than {@link Term#ONE ONE}) having zero (additive identity)
043: * for coefficient are automatically removed.</p>
044: *
045: * @author <a href="mailto:jean-marie@dautelle.com">Jean-Marie Dautelle</a>
046: * @version 3.1, April 1, 2006
047: */
048: public class Polynomial<R extends Ring<R>> extends Function<R, R>
049: implements Ring<Polynomial<R>> {
050:
051: /**
052: * Holds the terms to coefficients mapping
053: * (never empty, holds Term.ONE when constant)
054: */
055: final FastMap<Term, R> _termToCoef = new FastMap<Term, R>();
056:
057: /**
058: * Default constructor.
059: */
060: Polynomial() {
061: }
062:
063: /**
064: * Returns an univariate polynomial of degree one with the specified
065: * coefficient multiplier.
066: *
067: * @param coefficient the coefficient for the variable of degree 1.
068: * @param variable the variable for this polynomial.
069: * @return <code>valueOf(coefficient, Term.valueOf(variable, 1))</code>
070: */
071: public static <R extends Ring<R>> Polynomial<R> valueOf(
072: R coefficient, Variable<R> variable) {
073: return valueOf(coefficient, Term.valueOf(variable, 1));
074: }
075:
076: /**
077: * Returns a polynomial corresponding to the specified {@link Term term}
078: * with the specified coefficient multiplier.
079: *
080: * @param coefficient the coefficient multiplier.
081: * @param term the term multiplicand.
082: * @return <code>coefficient * term</code>
083: */
084: public static <R extends Ring<R>> Polynomial<R> valueOf(
085: R coefficient, Term term) {
086: if (term.equals(Term.ONE))
087: return Constant.valueOf(coefficient);
088: if (isZero(coefficient))
089: return Constant.valueOf(coefficient);
090: Polynomial<R> p = Polynomial.newInstance();
091: p._termToCoef.put(term, coefficient);
092: return p;
093: }
094:
095: private static boolean isZero(GroupAdditive<?> coefficient) {
096: return coefficient.equals(coefficient.opposite());
097: }
098:
099: /**
100: * Returns the terms of this polynomial.
101: *
102: * @return this polynomial's terms.
103: */
104: public Set<Term> getTerms() {
105: return _termToCoef.unmodifiable().keySet();
106: }
107:
108: /**
109: * Returns the coefficient for the specified term.
110: *
111: * @param term the term for which the coefficient is returned.
112: * @return the coefficient for the specified term or <code>null</code>
113: * if this polynomial does not contain the specified term.
114: */
115: public final R getCoefficient(Term term) {
116: return _termToCoef.get(term);
117: }
118:
119: /**
120: * Returns the order of this polynomial for the specified variable.
121: *
122: * @return the polynomial order relative to the specified variable.
123: */
124: public int getOrder(Variable<R> v) {
125: int order = 0;
126: for (Term term : _termToCoef.keySet()) {
127: int power = term.getPower(v);
128: if (power > order) {
129: order = power;
130: }
131: }
132: return order;
133: }
134:
135: /**
136: * Returns the sum of this polynomial with a constant polynomial
137: * having the specified value (convenience method).
138: *
139: * @param constantValue the value of the constant polynomial to add.
140: * @return <code>this + Constant.valueOf(constantValue)</code>
141: */
142: public Polynomial<R> plus(R constantValue) {
143: return this .plus(Constant.valueOf(constantValue));
144: }
145:
146: /**
147: * Returns the product of this polynomial with a constant polynomial
148: * having the specified value (convenience method).
149: *
150: * @param constantValue the value of the constant polynomial to multiply.
151: * @return <code>this · Constant.valueOf(constantValue)</code>
152: */
153: public Polynomial<R> times(R constantValue) {
154: return this .times(Constant.valueOf(constantValue));
155: }
156:
157: /**
158: * Returns the sum of two polynomials.
159: *
160: * @param that the polynomial being added.
161: * @return <code>this + that</code>
162: */
163: public Polynomial<R> plus(Polynomial<R> that) {
164: Polynomial<R> result = Polynomial.newInstance();
165: R zero = null;
166: result._termToCoef.putAll(this ._termToCoef);
167: result._termToCoef.putAll(that._termToCoef);
168: for (FastMap.Entry<Term, R> e = result._termToCoef.head(), end = result._termToCoef
169: .tail(); (e = e.getNext()) != end;) {
170: Term term = e.getKey();
171: R this Coef = this ._termToCoef.get(term);
172: R thatCoef = that._termToCoef.get(term);
173: if ((this Coef != null) && (thatCoef != null)) {
174: R sum = this Coef.plus(thatCoef);
175: if (isZero(sum)) { // Remove entry (be careful iterating)
176: FastMap.Entry<Term, R> prev = e.getPrevious();
177: result._termToCoef.remove(term);
178: e = prev; // Move back to previous entry.
179: zero = sum; // To be used if constant polynomial.
180: } else {
181: result._termToCoef.put(term, sum);
182: }
183: } // Else the current coefficient is correct.
184: }
185: if (result._termToCoef.size() == 0)
186: return Constant.valueOf(zero);
187: return result;
188: }
189:
190: /**
191: * Returns the opposite of this polynomial.
192: *
193: * @return <code> - this</code>
194: */
195: public Polynomial<R> opposite() {
196: Polynomial<R> result = Polynomial.newInstance();
197: for (FastMap.Entry<Term, R> e = _termToCoef.head(), end = _termToCoef
198: .tail(); (e = e.getNext()) != end;) {
199: result._termToCoef.put(e.getKey(), e.getValue().opposite());
200: }
201: return result;
202: }
203:
204: /**
205: * Returns the difference of two polynomials.
206: *
207: * @param that the polynomial being subtracted.
208: * @return <code>this - that</code>
209: */
210: public Polynomial<R> minus(Polynomial<R> that) {
211: return this .plus(that.opposite());
212: }
213:
214: /**
215: * Returns the product of two polynomials.
216: *
217: * @param that the polynomial multiplier.
218: * @return <code>this · that</code>
219: */
220: public Polynomial<R> times(Polynomial<R> that) {
221: Polynomial<R> result = Polynomial.newInstance();
222: R zero = null;
223: for (Map.Entry<Term, R> entry1 : this ._termToCoef.entrySet()) {
224: Term t1 = entry1.getKey();
225: R c1 = entry1.getValue();
226: for (Map.Entry<Term, R> entry2 : that._termToCoef
227: .entrySet()) {
228: Term t2 = entry2.getKey();
229: R c2 = entry2.getValue();
230: Term t = t1.times(t2);
231: R c = c1.times(c2);
232: R prev = result.getCoefficient(t);
233: R coef = (prev != null) ? prev.plus(c) : c;
234: if (isZero(coef)) {
235: zero = coef;
236: } else {
237: result._termToCoef.put(t, coef);
238: }
239: }
240: }
241: if (result._termToCoef.size() == 0)
242: return Constant.valueOf(zero);
243: return result;
244: }
245:
246: /**
247: * Returns the composition of this polynomial with the one specified.
248: *
249: * @param that the polynomial for which the return value is passed as
250: * argument to this function.
251: * @return the polynomial <code>(this o that)</code>
252: * @throws FunctionException if this function is not univariate.
253: */
254: public Polynomial<R> compose(Polynomial<R> that) {
255: List<Variable<R>> variables = getVariables();
256: if (getVariables().size() != 1)
257: throw new FunctionException(
258: "This polynomial is not monovariate");
259: Variable<R> v = variables.get(0);
260: Polynomial<R> result = null;
261: for (Map.Entry<Term, R> entry : this ._termToCoef.entrySet()) {
262: Term term = entry.getKey();
263: Constant<R> cst = Constant.valueOf(entry.getValue());
264: int power = term.getPower(v);
265: if (power > 0) {
266: Polynomial<R> fn = that.pow(power);
267: result = (result != null) ? result.plus(cst.times(fn))
268: : cst.times(fn);
269: } else { // power = 0
270: result = (result != null) ? result.plus(cst) : cst;
271: }
272: }
273: return result;
274: }
275:
276: ////////////////////////////////////////////////////////////////
277: // Overrides parent method potentially returning polynomials //
278: ////////////////////////////////////////////////////////////////
279:
280: @SuppressWarnings("unchecked")
281: @Override
282: public <Z> Function<Z, R> compose(Function<Z, R> that) {
283: return (Function<Z, R>) ((that instanceof Polynomial) ? compose((Polynomial) that)
284: : super .compose(that));
285: }
286:
287: @Override
288: public Polynomial<R> differentiate(Variable<R> v) {
289: if (this .getOrder(v) > 0) {
290: Polynomial<R> result = null;
291: for (Map.Entry<Term, R> entry : this ._termToCoef.entrySet()) {
292: Term term = entry.getKey();
293: R coef = entry.getValue();
294: int power = term.getPower(v);
295: if (power > 0) {
296: R newCoef = multiply(coef, power);
297: Term newTerm = term.divide(Term.valueOf(v, 1));
298: Polynomial<R> p = valueOf(newCoef, newTerm);
299: result = (result != null) ? result.plus(p) : p;
300: }
301: }
302: return result;
303: } else { // Returns zero.
304: R coef = _termToCoef.values().iterator().next();
305: return Constant.valueOf(coef.plus(coef.opposite()));
306: }
307: }
308:
309: private static <R extends Ring<R>> R multiply(R o, int n) {
310: if (n <= 0)
311: throw new IllegalArgumentException("n: " + n
312: + " zero or negative values not allowed");
313: R shift2 = o;
314: R result = null;
315: while (n >= 1) { // Iteration.
316: if ((n & 1) == 1) {
317: result = (result == null) ? shift2 : result
318: .plus(shift2);
319: }
320: shift2 = shift2.plus(shift2);
321: n >>>= 1;
322: }
323: return result;
324: }
325:
326: @SuppressWarnings("unchecked")
327: @Override
328: public Polynomial<R> integrate(Variable<R> v) {
329: Polynomial<R> result = null;
330: for (Map.Entry<Term, R> entry : this ._termToCoef.entrySet()) {
331: Term term = entry.getKey();
332: R coef = entry.getValue();
333: int power = term.getPower(v);
334: R newCoef = (R) ((GroupMultiplicative) multiply(
335: (R) ((GroupMultiplicative) coef).inverse(),
336: power + 1)).inverse();
337: Term newTerm = term.times(Term.valueOf(v, 1));
338: Polynomial<R> p = valueOf(newCoef, newTerm);
339: result = (result != null) ? result.plus(p) : p;
340: }
341: return result;
342: }
343:
344: @SuppressWarnings("unchecked")
345: @Override
346: public Function<R, R> plus(Function<R, R> that) {
347: return (that instanceof Polynomial) ? this
348: .plus((Polynomial<R>) that) : super .plus(that);
349: }
350:
351: @SuppressWarnings("unchecked")
352: @Override
353: public Function<R, R> minus(Function<R, R> that) {
354: return (that instanceof Polynomial) ? this
355: .minus((Polynomial<R>) that) : super .minus(that);
356: }
357:
358: @SuppressWarnings("unchecked")
359: @Override
360: public Function<R, R> times(Function<R, R> that) {
361: return (that instanceof Polynomial) ? this
362: .times((Polynomial<R>) that) : super .times(that);
363: }
364:
365: @SuppressWarnings("unchecked")
366: @Override
367: public Polynomial<R> pow(int n) {
368: return (Polynomial<R>) super .pow(n);
369: }
370:
371: @SuppressWarnings("unchecked")
372: @Override
373: public List<Variable<R>> getVariables() {
374: // We multiply all terms togethers, the resulting product
375: // will hold all variabgles (powers are always positive).
376: Term product = _termToCoef.head().getNext().getKey();
377: for (FastMap.Entry<Term, R> e = _termToCoef.head().getNext(), end = _termToCoef
378: .tail(); (e = e.getNext()) != end;) {
379: product = product.times(e.getKey());
380: }
381: FastTable vars = FastTable.newInstance();
382: for (int i = 0, n = product.size(); i < n; i++) {
383: vars.add(product.getVariable(i));
384: }
385: return vars;
386: }
387:
388: @Override
389: @SuppressWarnings("unchecked")
390: public R evaluate() {
391: R sum = null;
392: for (Map.Entry<Term, R> entry : _termToCoef.entrySet()) {
393: Term term = entry.getKey();
394: R coef = entry.getValue();
395: R termValue = (R) term.evaluate();
396: R value = (termValue != null) ? coef.times(termValue)
397: : coef;
398: sum = (sum == null) ? value : sum.plus(value);
399: }
400: return sum;
401: }
402:
403: @Override
404: public boolean equals(Object obj) {
405: if (!(obj instanceof Polynomial))
406: return false;
407: Polynomial<?> that = (Polynomial<?>) obj;
408: return this ._termToCoef.equals(that._termToCoef);
409: }
410:
411: @Override
412: public int hashCode() {
413: return _termToCoef.hashCode();
414: }
415:
416: @Override
417: public Text toText() {
418: FastTable<Term> terms = FastTable.newInstance();
419: terms.addAll(_termToCoef.keySet());
420: terms.sort();
421: TextBuilder tb = TextBuilder.newInstance();
422: for (int i = 0, n = terms.size(); i < n; i++) {
423: if (i != 0) {
424: tb.append(" + ");
425: }
426: tb.append('[').append(_termToCoef.get(terms.get(i)));
427: tb.append(']').append(terms.get(i));
428: }
429: return tb.toText();
430: }
431:
432: /**
433: * Returns a copy of this polynomial
434: * {@link javolution.context.AllocatorContext allocated}
435: * by the calling thread (possibly on the stack).
436: *
437: * @return an identical and independant copy of this polynomial.
438: */
439: public Polynomial<R> copy() {
440: Polynomial<R> p = Polynomial.newInstance();
441: for (Map.Entry<Term, R> entry : _termToCoef.entrySet()) {
442: p._termToCoef.put(entry.getKey().copy(), entry.getValue());
443: }
444: return p;
445: }
446:
447: @SuppressWarnings("unchecked")
448: private static <R extends Ring<R>> Polynomial<R> newInstance() {
449: Polynomial p = FACTORY.object();
450: p._termToCoef.clear();
451: return p;
452: }
453:
454: @SuppressWarnings("unchecked")
455: private static final ObjectFactory<Polynomial> FACTORY = new ObjectFactory<Polynomial>() {
456: protected Polynomial create() {
457: return new Polynomial();
458: }
459: };
460:
461: private static final long serialVersionUID = 1L;
462:
463: }
|