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