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