001 package edu.nrao.sss.math;
002
003 import java.io.Serializable;
004 import java.util.NoSuchElementException;
005 import java.util.SortedMap;
006 import java.util.TreeMap;
007
008 import javax.xml.bind.annotation.adapters.XmlAdapter;
009 import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;
010
011 /**
012 * A polynomial equation of the form
013 * <tt>f(x)=c<sub>0</sub> + c<sub>1</sub>x + c<sub>2</sub>x<sup>2</sup>
014 * + ... + c<sub>n</sub>x<sup>n</sup></tt>.
015 * <p>
016 * <b>Version Info:</b>
017 * <table style="margin-left:2em">
018 * <tr><td>$Revision: 2151 $</td>
019 * <tr><td>$Date: 2009-04-03 10:26:17 -0600 (Fri, 03 Apr 2009) $</td>
020 * <tr><td>$Author: dharland $ (last person to modify)</td>
021 * </table></p>
022 *
023 * @author David M. Harland
024 * @since 2006-03-24
025 */
026 @XmlJavaTypeAdapter(Polynomial.JaxbAdapter.class)
027 public class Polynomial
028 implements Cloneable, Serializable, Comparable<Polynomial>
029 {
030 private static final long serialVersionUID = 1L;
031
032 //The terms are stored in a map with the exponent as the key.
033 //Note that the setters and getters deal with clones, so that
034 //this class can be the sole owner of the terms. If it were
035 //not, then another object could change the exponent and
036 //spoil the mapping.
037 private SortedMap<Integer, PolynomialTerm> terms;
038
039 /** Creates a new polynomial that has no terms. */
040 public Polynomial()
041 {
042 terms = new TreeMap<Integer, PolynomialTerm>();
043 }
044
045 /**
046 * Returns a new polynomial based on {@code polynomialString}.
047 * See {@link #parse(String)} for the expected format of
048 * {@code polynomialString}.
049 *
050 * @param polynomialString a string that will be used to configure
051 * this polynomial.
052 *
053 * @throws IllegalArgumentException if {@code polynomialString} is not in
054 * the expected form.
055 */
056 public void set(String polynomialString)
057 {
058 clear();
059
060 Polynomial.parse(polynomialString, this);
061 }
062
063 /**
064 * Adds a term to this polynomial.
065 * <p>
066 * After this method is called, the coefficient of the term of this
067 * polynomial with exponent equal to that of {@code term} is equal
068 * to what it had been plus {@code term.getCoefficient()}. In
069 * otherwords, this method truly adds term (in an arithmetical
070 * sense, as opposed to a collection of objects sense) to this
071 * polynomial. Contrast this with the behavior of
072 * {@link #replace(PolynomialTerm)}.</p>
073 * <p>
074 * Note that this polynomial will not hold a reference to
075 * {@code term} as a result of a call to this method. This
076 * means that any operations performed on term after this
077 * method is called will <i>not</i> have an effect on this
078 * polynomial.</p>
079 *
080 * @param term the term to be added to this polynomial. If this
081 * value is <i>null</i> this polynomial is not altered.
082 */
083 public void add(PolynomialTerm term)
084 {
085 //Quick exit if term is null
086 if (term == null)
087 return;
088
089 //See if we already have a term of this order
090 PolynomialTerm mappedTerm = terms.get(term.getExponent());
091
092 if (mappedTerm != null)
093 mappedTerm.add(term);
094 else
095 replace(term);
096 }
097
098 /**
099 * Adds the given polynomial to this one.
100 *
101 * @param other the polynomial to be added to this one.
102 */
103 public void add(Polynomial other)
104 {
105 for (int key : other.terms.keySet())
106 add(other.getNonNullTerm(key));
107 }
108
109 /**
110 * Replaces a term in this polynomial with a copy of {@code newTerm}.
111 * <p>
112 * If this polynomial already contained a term with the same exponent
113 * as {@code newTerm}, it will be replaced. Note that it is a
114 * <i>copy</i> of {@code newTerm} that will become part of this
115 * polynomial. This polynomial will not maintain a reference to
116 * {@code newTerm}.</p>
117 *
118 * @param newTerm a replacement for the term of this polynomial that
119 * has an exponent of {@code newTerm.getExponent()}.
120 */
121 public void replace(PolynomialTerm newTerm)
122 {
123 PolynomialTerm clone = (PolynomialTerm)newTerm.clone();
124
125 terms.put(clone.getExponent(), clone);
126 }
127
128 //If you activate the line below, you can get jaxb/bin/schemagen.sh to
129 //create an XML schema for this class.
130 //public void setTerms(SortedMap<Integer, PolynomialTerm> replacementSet) { }
131
132 /**
133 * Returns <i>true</i> if this polynomial has a term with the
134 * given exponent.
135 * <p>
136 * If this method returns <i>true</i>, {@link #getTerm(int)}
137 * will not return <i>null</i>. It is possible, though, that
138 * the returned term will have a coefficient of zero.</p>
139 *
140 * @param exponent the exponent of a term whose existence is sought.
141 *
142 * @return <i>true</i> if this polynomial has a term with the
143 * given exponent.
144 */
145 public boolean hasTerm(int exponent)
146 {
147 return terms.containsKey(exponent);
148 }
149
150 /**
151 * Returns a set of copies of the terms of this polynomial.
152 *
153 * @return a set of copies of the terms of this polynomial.
154 */
155 public SortedMap<Integer, PolynomialTerm> getTerms()
156 {
157 //The returned set contains clones of our terms
158 SortedMap<Integer, PolynomialTerm> termClones =
159 new TreeMap<Integer, PolynomialTerm>();
160
161 for (int key : terms.keySet())
162 termClones.put(key, getNonNullTerm(key));
163
164 return termClones;
165 }
166
167 /**
168 * Returns a copy of this polynomial's term with the given exponent.
169 * <p>
170 * If this polynomial has no such term, <i>null</i> is returned.
171 * Contrast this with the behavior of {@link #getNonNullTerm(int)}.</p>
172 * <p>
173 * Note that this method never returns a reference to one of its terms,
174 * but always returns a copy (or <i>null</i>).</p>
175 *
176 * @param exponent the exponent for which a term is sought.
177 *
178 * @return a copy of this polynomial's term with the given exponent,
179 * or <i>null</i> if this polynomial has no such term.
180 */
181 public PolynomialTerm getTerm(int exponent)
182 {
183 return hasTerm(exponent) ? getNonNullTerm(exponent) : null;
184 }
185
186 /**
187 * Returns a copy of this polynomial's term with the given exponent.
188 * <p>
189 * If this polynomial has no such term, a new term with a coefficient of
190 * zero is created and returned. This means that this method will never
191 * return a value of <i>null</i>, even when it has no term for the given
192 * exponent.
193 * Contrast this with the behavior of {@link #getTerm(int)}.</p>
194 * <p>
195 * Note that this method never returns a reference to one of its terms,
196 * but always returns a copy (or a new null-like term).</p>
197 *
198 * @param exponent the exponent for which a term is sought.
199 *
200 * @return a copy of this polynomial's term with the given exponent,
201 * or a new term with coefficient of zero, if this polynomial
202 * has no such term. The value returned will never be <i>null</i>.
203 */
204 public PolynomialTerm getNonNullTerm(int exponent)
205 {
206 PolynomialTerm term = terms.get(exponent);
207
208 if (term == null)
209 term = new PolynomialTerm(0.0, exponent);
210 else
211 term = (PolynomialTerm)term.clone();
212
213 return term;
214 }
215
216 /**
217 * Returns the order of this polynomial. The order is the largest
218 * exponent of this polynomial's terms.
219 *
220 * @return the order of this polynomial.
221 */
222 public int order()
223 {
224 try
225 {
226 return terms.lastKey();
227 }
228 catch (NoSuchElementException ex)
229 {
230 return 0; //consider the empty polynomial to be of order zero.
231 }
232 }
233
234 public int smallestExponent()
235 {
236 try
237 {
238 return terms.firstKey();
239 }
240 catch (NoSuchElementException ex)
241 {
242 return 0; //consider the empty polynomial to have implied 0x^0 term.
243 }
244 }
245
246 /**
247 * Returns the number of terms in this polynomial.
248 *
249 * @return the number of terms in this polynomial.
250 */
251 public int getNumberOfTerms()
252 {
253 return terms.size();
254 }
255
256 /**
257 * Returns the value of this polynomial by using {@code number} as the
258 * value of the independent variable.
259 *
260 * @return the value of this polynomial evaluated for {@code number}.
261 */
262 public double calculateFor(double number)
263 {
264 double answer = 0.0;
265
266 for (int key : terms.keySet())
267 answer += getNonNullTerm(key).calculateFor(number);
268
269 return answer;
270 }
271
272 /**
273 * Returns a polynomial that is the mathematical derivative of this one.
274 * That is, for each term <tt>c<sub>i</sub>x<sup>i</sup></tt> of this
275 * polynomial, the derivative polynomial has a
276 * term with a coefficient of <tt>i * c<sub>i</sub></tt> and an
277 * exponent of of <tt>x<sup>i-1</sup></tt>. Note: the exception to the
278 * above rule is that if this polynomial has a term with an exponent
279 * of zero, the derivative will not contain a term derived from it.
280 *
281 * @return a polynomial that is the mathematical derivative of this one.
282 */
283 public Polynomial createDerivative()
284 {
285 Polynomial derivative = new Polynomial();
286
287 for (PolynomialTerm term : terms.values())
288 if (term.getExponent() != 0)
289 derivative.add(term.createDerivativeTerm());
290
291 return derivative;
292 }
293
294 /** Removes all terms from this polynomial. */
295 public void clear()
296 {
297 terms.clear();
298 }
299
300 /**
301 * Returns a new polynomial based on {@code polynomialString}.
302 * <p>
303 * Each term of the parsed string must comply with the form
304 * documented in {@link PolynomialTerm#parse(String)}. Each
305 * term may be separated by either a '+' or '-' character.
306 * White space between the terms and their separators is legal
307 * but not necessary.</p>
308 * <p>
309 * <b><u>Examples:</u></b></br>
310 * <ul><tt>
311 * <li>1.2 + 3.4x - 5.6x^2 + 7.8x^3 - 9x^4</li>
312 * <li>1.2+3.4x-5.6x^2+7.8x^3-9x^4</li>
313 * <li>1.2 + 3.4x + -5.6x^2 + 7.8x^3 + -9x^4</li>
314 * </tt></ul></p>
315 * <p>
316 * The terms are <i>not</i> required to be in any particular order,
317 * and the number of terms with a given exponent is not restricted.</p>
318 * <p>
319 * <b><u>Special Cases</u></b><br/>
320 * A {@code polynomialString} of <i>null</i> or <tt>""</tt> (the empty
321 * string) will <i>not</i> result in an {@code IllegalArgumentException},
322 * but will instead return a polynomial that contains no terms.</p>
323 *
324 *
325 * @param polynomialString a string that will be converted into
326 * a polynomial.
327 *
328 * @throws IllegalArgumentException if {@code polynomialString} is not in
329 * the expected form.
330 */
331 public static Polynomial parse(String polynomialString)
332 {
333 Polynomial newPolynomial = new Polynomial();
334
335 if ((polynomialString != null) && !polynomialString.equals(""))
336 Polynomial.parse(polynomialString, newPolynomial);
337
338 return newPolynomial;
339 }
340
341 private static void parse(String polynomialString, Polynomial polynomial)
342 {
343 //Here we isolate the '+' and '-' characters that separate terms, as
344 //opposed to those that might be present in the exponents. After this
345 //operation all terms should be separated by a comma (',').
346 String terms = polynomialString.replaceAll("\\s", ""); //Strip spaces
347 terms = terms.replaceAll("\\+\\-", "-"); //Change "+-" to "-"
348 terms = terms.replaceAll("\\-\\+", "-"); //Change "-+" to "-"
349 terms = terms.replaceAll("\\^\\+", "^#"); //Change "^+" to "^#"
350 terms = terms.replaceAll("\\^\\-", "^~"); //Change "^-" to "^~"
351 terms = terms.replaceAll("\\+", ";"); //Change "+" to ";"
352 terms = terms.replaceAll("\\-", ";-"); //Change "-" to ";-"
353 terms = terms.replaceAll("\\^\\#", "^+"); //Restore "^#" to "^+"
354 terms = terms.replaceAll("\\^\\~", "^-"); //Restore "^~" to "^-"
355
356 StringBuilder termErrors = null;
357
358 //Send the individual terms to PolynomialTerm for parsing.
359 //Try to process all terms, even after receiving parsing error.
360 //The idea is to show the client all errors at once.
361 for (String term : terms.split(";"))
362 {
363 if (term.equals(""))
364 continue;
365
366 try
367 {
368 polynomial.add(PolynomialTerm.parse(term));
369 }
370 catch (IllegalArgumentException ex)
371 {
372 if (termErrors == null)
373 termErrors = new StringBuilder("Problem parsing " + polynomialString + ":");
374
375 termErrors.append("\n ").append(ex.getMessage());
376 }
377 }
378
379 if (termErrors != null)
380 throw new IllegalArgumentException(termErrors.toString());
381 }
382
383 /** Returns an polynomial that is equal to this one. */
384 public Polynomial clone()
385 {
386 Polynomial clone = null;
387
388 try
389 {
390 clone = (Polynomial)super.clone();
391 clone.terms = new TreeMap<Integer, PolynomialTerm>();
392 clone.add(this);
393 }
394 catch (CloneNotSupportedException ex)
395 {
396 throw new RuntimeException(ex);
397 }
398
399 return clone;
400 }
401
402 /** Returns <i>true</i> if {@code o} is equal to this polynomial. */
403 public boolean equals(Object o)
404 {
405 //Quick exit if o is this
406 if (o == this)
407 return true;
408
409 //Quick exit if o is null
410 if (o == null)
411 return false;
412
413 //Quick exit if classes are different
414 if (!o.getClass().equals(this.getClass()))
415 return false;
416
417 //If both polynomials have the same string representation, they are equal
418 return o.toString().equals(this.toString());
419 }
420
421 /** Returns a hash code value for this polynomial. */
422 public int hashCode()
423 {
424 return this.toString().hashCode();
425 }
426
427 /**
428 * Compares this polynomial to {@code other} for order.
429 * <p>
430 * The polynomials are ordered by comparing the coefficients of their
431 * terms of equal exponents. Of two terms with equal exponents, the
432 * one with the smaller coefficient is considered to be the lesser.
433 * When two polynomials do not have a complete set of matching terms,
434 * those that are missing are considered to have coefficients of zero.</p>
435 * <p>
436 * <b><u>Example</u></b><br/>
437 * Consider these two polynomials:<pre>
438 * A. <tt>1 + 2x + 4x^3 + 6x^5</tt>
439 * B. <tt>1 + 2x + 3x^2 + 6x^5</tt></pre>
440 * For purposes of comparison, these are expanded to:<pre>
441 * A. <tt>1 + 2x + 0x^2 + 4x^3 + 0x^4 + 6x^5</tt>
442 * B. <tt>1 + 2x + 3x^2 + 0x^3 + 0x^4 + 6x^5</tt></pre>
443 * The comparison then looks at the <tt>x^0</tt> terms, then
444 * the <tt>x^1</tt> terms, and so on, until it comes to a pair
445 * that does not have equal coefficients. In this example, A
446 * precedes B because of the coefficients of the <tt>x^2</tt>
447 * term.</p>
448 *
449 * @param other the polynomial to which this one is compared.
450 *
451 * @return a negative integer, zero, or a positive integer as this interval
452 * is less than, equal to, or greater than the other interval.
453 */
454 public int compareTo(Polynomial other)
455 {
456 //Quick exit if polynomials are equal. Also allows NullPointerException to
457 //be thrown if other is null.
458 if (other.equals(this))
459 return 0;
460
461 int smallestExponent = Math.min(this.smallestExponent(),
462 other.smallestExponent());
463
464 int largestExponent = Math.max(this.order(), other.order());
465
466 int answer = 0;
467
468 for (int exp=smallestExponent; exp <= largestExponent; exp++)
469 {
470 PolynomialTerm thisTerm = this.getTerm(exp);
471 PolynomialTerm otherTerm = other.getTerm(exp);
472
473 double thisCoeff = (thisTerm == null) ? 0.0 : thisTerm.getCoefficient();
474 double otherCoeff = (otherTerm == null) ? 0.0 : otherTerm.getCoefficient();
475
476 answer = (int)Math.signum(thisCoeff - otherCoeff);
477
478 if (answer != 0.0)
479 break;
480 }
481
482 return answer;
483 }
484
485 /**
486 * Returns a text representation of this polynomial.
487 * <p>
488 * The individual terms are represented as documented in
489 * {@link PolynomialTerm#toString()}. Each term is separated
490 * by " + " (a single space, a '+' character, and another
491 * single space).</p>
492 *
493 * @return
494 * a text representation of this polynomial.
495 */
496 @Override
497 public String toString()
498 {
499 return toString('t');
500 }
501
502 /**
503 * Returns a text representation of this polynomial.
504 * <p>
505 * The individual terms are represented as documented in
506 * {@link PolynomialTerm#toString(char)}. Each term is separated
507 * by " + " (a single space, a '+' character, and another
508 * single space).</p>
509 *
510 * @param variableName
511 * the character to use as the independent variable.
512 *
513 * @return
514 * a text representation of this polynomial.
515 */
516 public String toString(char variableName)
517 {
518 StringBuilder buff = new StringBuilder();
519
520 int termCount = getNumberOfTerms();
521
522 if (termCount > 0)
523 {
524 int firstExponent = terms.firstKey();
525
526 buff.append(terms.get(firstExponent));
527
528 SortedMap<Integer, PolynomialTerm> remainingTerms =
529 terms.tailMap(firstExponent + 1);
530
531 for (int key : remainingTerms.keySet())
532 {
533 String termString = terms.get(key).toString(variableName);
534 if (termString.startsWith("-"))
535 {
536 termString = termString.substring(1);
537 buff.append(" - ").append(termString);
538 }
539 else
540 {
541 buff.append(" + ").append(terms.get(key));
542 }
543 }
544 }
545
546 return buff.toString();
547 }
548
549 /*
550 public static void main(String[] args)
551 {
552 Polynomial poly;
553
554 for (String arg : args)
555 {
556 System.out.println("Input: " + arg);
557 poly = Polynomial.parse(arg);
558 System.out.println("Output: " + poly);
559
560 Polynomial newPoly = Polynomial.parse(poly.toString());
561 System.out.println("New Poly: " + newPoly);
562
563 System.out.println();
564 }
565
566 poly = Polynomial.parse("1 + 2x + 3x^2");
567 System.out.println(poly);
568
569 poly = Polynomial.parse("");
570 System.out.println(poly);
571
572 poly = Polynomial.parse(null);
573 System.out.println(poly);
574
575 System.out.println();
576
577 Polynomial p1 = Polynomial.parse("1 + 2x + 3x^2");
578 Polynomial p2 = Polynomial.parse("1 + 2x + 3x^2");
579 System.out.println("p1.equals(p2)? -> " + p1.equals(p2) +
580 ", p1.compareTo(p2) -> " +p1.compareTo(p2));
581
582 p2 = Polynomial.parse("1 + 2x + 4x^2");
583 System.out.println("p1.equals(p2)? -> " + p1.equals(p2) +
584 ", p1.compareTo(p2) -> " +p1.compareTo(p2));
585
586 p2 = Polynomial.parse("1 + 3x^2");
587 System.out.println("p1.equals(p2)? -> " + p1.equals(p2) +
588 ", p1.compareTo(p2) -> " +p1.compareTo(p2));
589
590 p2 = Polynomial.parse("x^5");
591 System.out.println("p1.equals(p2)? -> " + p1.equals(p2) +
592 ", p1.compareTo(p2) -> " +p1.compareTo(p2));
593
594 p1 = Polynomial.parse("3x^2 + 1x + 9");
595 System.out.println(p1);
596 }
597 */
598
599 static class JaxbAdapter extends XmlAdapter<String, Polynomial>
600 {
601 public String marshal(Polynomial polynomial)
602 {
603 return polynomial.toString();
604 }
605
606 public Polynomial unmarshal(String polynomialString)
607 {
608 return Polynomial.parse(polynomialString);
609 }
610 }
611 }