001    package hw3;
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 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         * @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 hw3.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 hw3.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(/*@Nullable*/ 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          /*  assert terms != null: "terms == null!";
471            for (int i = 0; i < terms.size(); i++) {
472                    assert !(terms.get(i).getCoeff().equals(new RatNum(0))): "zero coefficient!";
473                    assert !(terms.get(i).getExpt() < 0): "negative exponent!";
474                    if (i < terms.size() - 1) {
475                            assert !(terms.get(i + 1).getExpt() >= terms.get(i).getExpt()): "terms out of order!";
476                    }
477            }*/
478            
479            
480            if (terms == null) {
481                assert (false) : "CheckRep assert";
482                throw new RuntimeException("terms == null!");
483            }
484            for (int i = 0; i < terms.size(); i++) {
485                if (terms.get(i).getCoeff().equals(new RatNum(0))) {
486                    throw new RuntimeException("zero coefficient!");
487                }
488                if (terms.get(i).getExpt() < 0) {
489                    throw new RuntimeException("negative exponent!");
490                }
491                if (i < terms.size() - 1) {
492                    if (terms.get(i + 1).getExpt() >= terms.get(i).getExpt()) {
493                        throw new RuntimeException("terms out of order!");
494                    }
495                }
496            }
497        }
498    }