001package hw4;
002
003import java.util.ArrayList;
004import java.util.List;
005import java.util.StringTokenizer;
006
007/**
008 * <b>RatPoly</b> represents an immutable single-variate polynomial expression.
009 * RatPolys are sums of RatTerms with non-negative exponents.
010 * <p>
011 *
012 * Examples of RatPolys include "0", "x-10", and "x^3-2*x^2+5/3*x+3", and "NaN".
013 */
014// See RatNum's documentation for a definition of "immutable".
015public final class RatPoly {
016
017  /** Holds all the RatTerms in this RatPoly */
018  private final List<RatTerm> terms;
019
020  // Definitions:
021  // For a RatPoly p, let C(p,i) be "p.terms.get(i).getCoeff()" and
022  // E(p,i) be "p.terms.get(i).getExpt()"
023  // length(p) be "p.terms.size()"
024  // (These are helper functions that will make it easier for us
025  // to write the remainder of the specifications. They are not
026  // executable code; they just represent complex expressions in a
027  // concise manner, so that we can stress the important parts of
028  // other expressions in the spec rather than get bogged down in
029  // the details of how we extract the coefficient for the 2nd term
030  // or the exponent for the 5th term. So when you see C(p,i),
031  // think "coefficient for the ith term in p".)
032  //
033  // Abstraction Function:
034  // RatPoly, p, represents the polynomial equal to the sum of the
035  // RatTerms contained in 'terms':
036  // sum (0 <= i < length(p)): p.terms.get(i)
037  // If there are no terms, then the RatPoly represents the zero
038  // polynomial.
039  //
040  // Representation Invariant for every RatPoly p:
041  // terms != null &&
042  // forall i such that (0 <= i < length(p)), C(p,i) != 0 &&
043  // forall i such that (0 <= i < length(p)), E(p,i) >= 0 &&
044  // forall i such that (0 <= i < length(p) - 1), E(p,i) > E(p, i+1)
045  // In other words:
046  // * The terms field always points to some usable object.
047  // * No term in a RatPoly has a zero coefficient.
048  // * No term in a RatPoly has a negative exponent.
049  // * The terms in a RatPoly are sorted in descending exponent order.
050  // (It is implied that 'terms' does not contain any null elements by the
051  // above
052  // invariant.)
053
054  /** A constant holding a Not-a-Number (NaN) value of type RatPoly */
055  public static final RatPoly NaN = new RatPoly(RatTerm.NaN);
056
057  /** A constant holding a zero value of type RatPoly */
058  public static final RatPoly ZERO = new RatPoly();
059
060  /**
061   * @effects Constructs a new Poly, "0".
062   */
063  public RatPoly() {
064    terms = new ArrayList<RatTerm>();
065    checkRep();
066  }
067
068  /**
069   * @param rt The single term which the new RatPoly equals.
070   * @requires rt.getExpt() >= 0
071   * @effects Constructs a new Poly equal to "rt". If rt.getCoeff() is zero,
072   *          constructs a "0" polynomial.
073   */
074  public RatPoly(RatTerm rt) {
075    // TODO: Fill in this method, then remove the RuntimeException
076    throw new RuntimeException("RatPoly constructor is not yet implemented");
077  }
078
079  /**
080   * @param c The constant in the term which the new RatPoly equals.
081   * @param e The exponent in the term which the new RatPoly equals.
082   * @requires e >= 0
083   * @effects Constructs a new Poly equal to "c*x^e". If c is zero, constructs
084   *          a "0" polynomial.
085   */
086  public RatPoly(int c, int e) {
087    // TODO: Fill in this method, then remove the RuntimeException
088    throw new RuntimeException("RatPoly constructor is not yet implemented");
089  }
090
091  /**
092   * @param rt A list of terms to be contained in the new RatPoly.
093   * @requires 'rt' satisfies clauses given in rep. invariant
094   * @effects Constructs a new Poly using 'rt' as part of the representation.
095   *          The method does not make a copy of 'rt'.
096   */
097  private RatPoly(List<RatTerm> rt) {
098    terms = rt;
099    // The spec tells us that we don't need to make a copy of 'rt'
100    checkRep();
101  }
102
103  /**
104   * Returns the degree of this RatPoly.
105   *
106   * @requires !this.isNaN()
107   * @return the largest exponent with a non-zero coefficient, or 0 if this is
108   *         "0".
109   */
110  public int degree() {
111    // TODO: Fill in this method, then remove the RuntimeException
112    throw new RuntimeException("RatPoly->degree() is not yet implemented");
113  }
114
115  /**
116   * Gets the RatTerm associated with degree 'deg'
117   *
118   * @param deg The degree for which to find the corresponding RatTerm.
119   * @requires !this.isNaN()
120   * @return the RatTerm of degree 'deg'. If there is no term of degree 'deg'
121   *         in this poly, then returns the zero RatTerm.
122   */
123  public RatTerm getTerm(int deg) {
124    // TODO: Fill in this method, then remove the RuntimeException
125    throw new RuntimeException("RatPoly->getTerm() is not yet implemented");
126  }
127
128  /**
129   * Returns true if this RatPoly is not-a-number.
130   *
131   * @return true if and only if this has some coefficient = "NaN".
132   */
133  public boolean isNaN() {
134    // TODO: Fill in this method, then remove the RuntimeException
135    throw new RuntimeException("RatPoly->isNaN() is not yet implemented");
136  }
137
138  /**
139   * Scales coefficients within 'lst' by 'scalar' (helper procedure).
140   *
141   * @param lst The RatTerms to be scaled.
142   * @param scalar the value by which to scale coefficients in lst.
143   * @requires lst, scalar != null
144   * @modifies lst
145   * @effects Forall i s.t. 0 <= i < lst.size(), if lst.get(i) = (C . E) then
146   *          lst_post.get(i) = (C*scalar . E)
147   * @see hw4.RatTerm regarding (C . E) notation
148   */
149  private static void scaleCoeff(List<RatTerm> lst, RatNum scalar) {
150    // TODO: Fill in this method, then remove the RuntimeException
151    throw new RuntimeException("RatPoly->scaleCoeff() is not yet implemented");
152  }
153
154  /**
155   * Increments exponents within 'lst' by 'degree' (helper procedure).
156   *
157   * @param lst The RatTerms whose exponents are to be incremented.
158   * @param degree the value by which to increment exponents in lst.
159   * @requires lst != null
160   * @modifies lst
161   * @effects Forall i s.t. 0 <= i < lst.size(), if (C . E) = lst.get(i) then
162   *          lst_post.get(i) = (C . E+degree)
163   * @see hw4.RatTerm regarding (C . E) notation
164   */
165  private static void incremExpt(List<RatTerm> lst, int degree) {
166    // TODO: Fill in this method, then remove the RuntimeException
167    throw new RuntimeException("RatPoly->incremExpt() is not yet implemented");
168  }
169
170  /**
171   * Helper procedure: Inserts a term into a sorted sequence of terms,
172   * preserving the sorted nature of the sequence. If a term with the given
173   * degree already exists, adds their coefficients.
174   *
175   * Definitions: Let a "Sorted List<RatTerm>" be a List<RatTerm> V such
176   * that [1] V is sorted in descending exponent order && [2] there are no two
177   * RatTerms with the same exponent in V && [3] there is no RatTerm in V with
178   * a coefficient equal to zero
179   *
180   * For a Sorted List<RatTerm> V and integer e, let cofind(V, e) be either
181   * the coefficient for a RatTerm rt in V whose exponent is e, or zero if
182   * there does not exist any such RatTerm in V. (This is like the coeff
183   * function of RatPoly.) We will write sorted(lst) to denote that lst is a
184   * Sorted List<RatTerm>, as defined above.
185   *
186   * @param lst The list into which newTerm should be inserted.
187   * @param newTerm The term to be inserted into the list.
188   * @requires lst != null && sorted(lst)
189   * @modifies lst
190   * @effects sorted(lst_post) && (cofind(lst_post,newTerm.getExpt()) =
191   *          cofind(lst,newTerm.getExpt()) + newTerm.getCoeff())
192   */
193  private static void sortedInsert(List<RatTerm> lst, RatTerm newTerm) {
194    // TODO: Fill in this method, then remove the RuntimeException
195    throw new RuntimeException("RatPoly->sortedInsert() is not yet implemented");
196  }
197
198  /**
199   * Return the additive inverse of this RatPoly.
200   *
201   * @return a RatPoly equal to "0 - this"; if this.isNaN(), returns some r
202   *         such that r.isNaN()
203   */
204  public RatPoly negate() {
205    // TODO: Fill in this method, then remove the RuntimeException
206    throw new RuntimeException("RatPoly->negate() is not yet implemented");
207  }
208
209  /**
210   * Addition operation.
211   *
212   * @param p The other value to be added.
213   * @requires p != null
214   * @return a RatPoly, r, such that r = "this + p"; if this.isNaN() or
215   *         p.isNaN(), returns some r such that r.isNaN()
216   */
217  public RatPoly add(RatPoly p) {
218    // TODO: Fill in this method, then remove the RuntimeException
219    throw new RuntimeException("RatPoly->add() is not yet implemented");
220  }
221
222  /**
223   * Subtraction operation.
224   *
225   * @param p The value to be subtracted.
226   * @requires p != null
227   * @return a RatPoly, r, such that r = "this - p"; if this.isNaN() or
228   *         p.isNaN(), returns some r such that r.isNaN()
229   */
230  public RatPoly sub(RatPoly p) {
231    // TODO: Fill in this method, then remove the RuntimeException
232    throw new RuntimeException("RatPoly->sub() is not yet implemented");
233  }
234
235  /**
236   * Multiplication operation.
237   *
238   * @param p The other value to be multiplied.
239   * @requires p != null
240   * @return a RatPoly, r, such that r = "this * p"; if this.isNaN() or
241   *         p.isNaN(), returns some r such that r.isNaN()
242   */
243  public RatPoly mul(RatPoly p) {
244    // TODO: Fill in this method, then remove the RuntimeException
245    throw new RuntimeException("RatPoly->mul() is not yet implemented");
246  }
247
248  /**
249   * Division operation (truncating).
250   *
251   * @param p The divisor.
252   * @requires p != null
253   * @return a RatPoly, q, such that q = "this / p"; if p = 0 or this.isNaN()
254   *         or p.isNaN(), returns some q such that q.isNaN()
255   *         <p>
256   *
257   * Division of polynomials is defined as follows: Given two polynomials u
258   * and v, with v != "0", we can divide u by v to obtain a quotient
259   * polynomial q and a remainder polynomial r satisfying the condition u = "q *
260   * v + r", where the degree of r is strictly less than the degree of v, the
261   * degree of q is no greater than the degree of u, and r and q have no
262   * negative exponents.
263   * <p>
264   *
265   * For the purposes of this class, the operation "u / v" returns q as
266   * defined above.
267   * <p>
268   *
269   * The following are examples of div's behavior: "x^3-2*x+3" / "3*x^2" =
270   * "1/3*x" (with r = "-2*x+3"). "x^2+2*x+15 / 2*x^3" = "0" (with r =
271   * "x^2+2*x+15"). "x^3+x-1 / x+1 = x^2-x+2 (with r = "-3").
272   * <p>
273   *
274   * Note that this truncating behavior is similar to the behavior of integer
275   * division on computers.
276   */
277  public RatPoly div(RatPoly p) {
278    // TODO: Fill in this method, then remove the RuntimeException
279    throw new RuntimeException("RatPoly->div() is not yet implemented");
280  }
281
282  /**
283   * Return the derivative of this RatPoly.
284   *
285   * @return a RatPoly, q, such that q = dy/dx, where this == y. In other
286   *         words, q is the derivative of this. If this.isNaN(), then return
287   *         some q such that q.isNaN()
288   *
289   * <p>
290   * The derivative of a polynomial is the sum of the derivative of each term.
291   */
292  public RatPoly differentiate() {
293    // TODO: Fill in this method, then remove the RuntimeException
294    throw new RuntimeException("RatPoly->differentiate() is not yet implemented");
295  }
296
297  /**
298   * Returns the antiderivative of this RatPoly.
299   *
300   * @param integrationConstant The constant of integration to use when
301   *  computating the antiderivative.
302   * @requires integrationConstant != null
303   * @return a RatPoly, q, such that dq/dx = this and the constant of
304   *         integration is "integrationConstant" In other words, q is the
305   *         antiderivative of this. If this.isNaN() or
306   *         integrationConstant.isNaN(), then return some q such that
307   *         q.isNaN()
308   *
309   * <p>
310   * The antiderivative of a polynomial is the sum of the antiderivative of
311   * each term plus some constant.
312   */
313  public RatPoly antiDifferentiate(RatNum integrationConstant) {
314    // TODO: Fill in this method, then remove the RuntimeException
315    throw new RuntimeException(
316        "RatPoly->antiDifferentiate() unimplemented!");
317  }
318
319  /**
320   * Returns the integral of this RatPoly, integrated from lowerBound to
321   * upperBound.
322   *
323   * <p>
324   * The Fundamental Theorem of Calculus states that the definite integral of
325   * f(x) with bounds a to b is F(b) - F(a) where dF/dx = f(x) NOTE: Remember
326   * that the lowerBound can be higher than the upperBound.
327   *
328   * @param lowerBound The lower bound of integration.
329   * @param upperBound The upper bound of integration.
330   * @return a double that is the definite integral of this with bounds of
331   *         integration between lowerBound and upperBound. If this.isNaN(),
332   *         or either lowerBound or upperBound is Double.NaN, return
333   *         Double.NaN.
334   */
335  public double integrate(double lowerBound, double upperBound) {
336    // TODO: Fill in this method, then remove the RuntimeException
337    throw new RuntimeException("RatPoly->integrate() is not yet implemented");
338  }
339
340  /**
341   * Returns the value of this RatPoly, evaluated at d.
342   *
343   * @param d The value at which to evaluate this polynomial.
344   * @return the value of this polynomial when evaluated at 'd'. For example,
345   *         "x+2" evaluated at 3 is 5, and "x^2-x" evaluated at 3 is 6. if
346   *         (this.isNaN() == true), return Double.NaN
347   */
348  public double eval(double d) {
349    // TODO: Fill in this method, then remove the RuntimeException
350    throw new RuntimeException("RatPoly->eval() is not yet implemented");
351  }
352
353  /**
354   * Returns a string representation of this RatPoly.
355   *
356   * @return A String representation of the expression represented by this,
357   *         with the terms sorted in order of degree from highest to lowest.
358   *         <p>
359   *         There is no whitespace in the returned string.
360   *         <p>
361   *         If the polynomial is itself zero, the returned string will just
362   *         be "0".
363   *         <p>
364   *         If this.isNaN(), then the returned string will be just "NaN"
365   *         <p>
366   *         The string for a non-zero, non-NaN poly is in the form
367   *         "(-)T(+|-)T(+|-)...", where "(-)" refers to a possible minus
368   *         sign, if needed, and "(+|-)" refer to either a plus or minus
369   *         sign, as needed. For each term, T takes the form "C*x^E" or "C*x"
370   *         where C > 0, UNLESS: (1) the exponent E is zero, in which case T
371   *         takes the form "C", or (2) the coefficient C is one, in which
372   *         case T takes the form "x^E" or "x". In cases were both (1) and
373   *         (2) apply, (1) is used.
374   *         <p>
375   *         Valid example outputs include "x^17-3/2*x^2+1", "-x+1", "-1/2",
376   *         and "0".
377   *         <p>
378   */
379  @Override
380  public String toString() {
381    if (terms.size() == 0) {
382      return "0";
383    }
384    if (isNaN()) {
385      return "NaN";
386    }
387    StringBuilder output = new StringBuilder();
388    boolean isFirst = true;
389    for (RatTerm rt : terms) {
390      if (isFirst) {
391        isFirst = false;
392        output.append(rt.toString());
393      } else {
394        if (rt.getCoeff().isNegative()) {
395          output.append(rt.toString());
396        } else {
397          output.append("+" + rt.toString());
398        }
399      }
400    }
401    return output.toString();
402  }
403
404  /**
405   * Builds a new RatPoly, given a descriptive String.
406   *
407   * @param ratStr A string of the format described in the @requires clause.
408   * @requires 'polyStr' is an instance of a string with no spaces that
409   *           expresses a poly in the form defined in the toString() method.
410   *           <p>
411   *
412   * Valid inputs include "0", "x-10", and "x^3-2*x^2+5/3*x+3", and "NaN".
413   *
414   * @return a RatPoly p such that p.toString() = polyStr
415   */
416  public static RatPoly valueOf(String polyStr) {
417
418    List<RatTerm> parsedTerms = new ArrayList<RatTerm>();
419
420    // First we decompose the polyStr into its component terms;
421    // third arg orders "+" and "-" to be returned as tokens.
422    StringTokenizer termStrings = new StringTokenizer(polyStr, "+-", true);
423
424    boolean nextTermIsNegative = false;
425    while (termStrings.hasMoreTokens()) {
426      String termToken = termStrings.nextToken();
427
428      if (termToken.equals("-")) {
429        nextTermIsNegative = true;
430      } else if (termToken.equals("+")) {
431        nextTermIsNegative = false;
432      } else {
433        // Not "+" or "-"; must be a term
434        RatTerm term = RatTerm.valueOf(termToken);
435
436        // at this point, coeff and expt are initialized.
437        // Need to fix coeff if it was preceeded by a '-'
438        if (nextTermIsNegative) {
439          term = term.negate();
440        }
441
442        // accumulate terms of polynomial in 'parsedTerms'
443        sortedInsert(parsedTerms, term);
444      }
445    }
446    return new RatPoly(parsedTerms);
447  }
448
449  /**
450   * Standard hashCode function.
451   *
452   * @return an int that all objects equal to this will also return.
453   */
454  @Override
455  public int hashCode() {
456    // all instances that are NaN must return the same hashcode;
457    if (this.isNaN()) {
458      return 0;
459    }
460    return terms.hashCode();
461  }
462
463  /**
464   * Standard equality operation.
465   *
466   * @param obj The object to be compared for equality.
467   * @return true if and only if 'obj' is an instance of a RatPoly and 'this'
468   *         and 'obj' represent the same rational polynomial. Note that all
469   *         NaN RatPolys are equal.
470   */
471  @Override
472  public boolean equals(/*@Nullable*/ Object obj) {
473    if (obj instanceof RatPoly) {
474      RatPoly rp = (RatPoly) obj;
475
476      // special case: check if both are NaN
477      if (this.isNaN() && rp.isNaN()) {
478        return true;
479      } else {
480        return terms.equals(rp.terms);
481      }
482    } else {
483      return false;
484    }
485  }
486
487  /**
488   * Checks that the representation invariant holds (if any).
489   */
490  private void checkRep() {
491    assert (terms != null);
492    
493    for (int i = 0; i < terms.size(); i++) {
494        assert (!terms.get(i).getCoeff().equals(new RatNum(0))) : "zero coefficient";
495        assert (terms.get(i).getExpt() >= 0) : "negative exponent";
496        
497        if (i < terms.size() - 1)
498            assert (terms.get(i + 1).getExpt() < terms.get(i).getExpt()) : "terms out of order";
499    }
500  }
501}