001 package ps1; 002 003 /** <b>RatNum</b> represents an <b>immutable</b> rational number. 004 It includes all of the elements in the set of rationals, as well 005 as the special "NaN" (not-a-number) element that results from 006 division by zero. 007 <p> 008 The "NaN" element is special in many ways. Any arithmetic 009 operation (such as addition) involving "NaN" will return "NaN". 010 With respect to comparison operations, such as less-than, "NaN" is 011 considered equal to itself, and larger than all other rationals. 012 <p> 013 Examples of RatNums include "-1/13", "53/7", "4", "NaN", and "0". 014 */ 015 016 // ("immutable" is a common term for which "Effective Java" (p. 63) 017 // provides the following definition: "An immutatable class is simply 018 // a class whose instances cannot be modified. All of the information 019 // contained in each instance is provided when it is created and is 020 // fixed for the lifetime of the object.") 021 public final class RatNum extends Number implements Comparable<RatNum> { 022 023 private final int numer; 024 private final int denom; 025 026 // Abstraction Function: 027 // A RatNum r is NaN if r.denom = 0, (r.numer / r.denom) otherwise. 028 // (An abstraction function explains what the state of the fields in a 029 // RatNum represents. In this case, a rational number can be 030 // understood as the result of dividing two integers, or not-a-number 031 // if we would be dividing by zero.) 032 033 // Representation invariant for every RatNum r: 034 // (r.denom >= 0) && 035 // (r.denom > 0 ==> there does not exist integer i > 1 such that 036 // r.numer mod i = 0 and r.denom mod i = 0;) 037 // In other words, 038 // * r.denom is always non-negative. 039 // * r.numer/r.denom is in reduced form (assuming r.denom is not zero). 040 // (A representation invariant tells us something that is true for all 041 // instances of a RatNum) 042 043 /** A constant holding a Not-a-Number (NaN) value of type RatNum */ 044 public static final RatNum NaN = new RatNum(1, 0); 045 046 /** A constant holding a zero value of type RatNum */ 047 public static final RatNum ZERO = new RatNum(0); 048 049 /** @effects Constructs a new RatNum = n. */ 050 public RatNum(int n) { 051 numer = n; 052 denom = 1; 053 checkRep(); 054 } 055 056 /** @effects If d = 0, constructs a new RatNum = NaN. Else 057 constructs a new RatNum = (n / d). 058 */ 059 public RatNum(int n, int d) { 060 // special case for zero denominator; gcd(n,d) requires d != 0 061 if (d == 0) { 062 numer = n; 063 denom = 0; 064 065 } else { 066 067 // reduce ratio to lowest terms 068 int g = gcd(n,d); 069 n = n / g; 070 d = d / g; 071 072 if (d < 0) { 073 numer = -n; 074 denom = -d; 075 } else { 076 numer = n; 077 denom = d; 078 } 079 } 080 checkRep(); 081 } 082 083 /** 084 * Checks that the representation invariant holds (if any). 085 **/ 086 // Throws a RuntimeException if the rep invariant is violated. 087 private void checkRep() throws RuntimeException { 088 if(denom < 0) 089 throw new RuntimeException("Denominator of a RatNum cannot be less than zero"); 090 091 if(denom > 0) { 092 int thisGcd = gcd (numer, denom); 093 if (thisGcd != 1 && thisGcd != -1) { 094 throw new RuntimeException("RatNum not in lowest form"); 095 } 096 } 097 } 098 099 /** Returns true if this is NaN 100 @return true iff this is NaN (not-a-number) 101 */ 102 public boolean isNaN() { 103 return (denom == 0); 104 } 105 106 /** Returns true if this is negative. 107 @return true iff this < 0. */ 108 public boolean isNegative() { 109 return (compareTo(ZERO) < 0); 110 } 111 112 /** Returns true if this is positive. 113 @return true iff this > 0. */ 114 public boolean isPositive() { 115 return (compareTo(ZERO) > 0); 116 } 117 118 /** Compares two RatNums. 119 @requires rn != null 120 @return a negative number if this < rn, 121 0 if this = rn, 122 a positive number if this > rn. 123 */ 124 public int compareTo(RatNum rn) { 125 if (this.isNaN() && rn.isNaN()) { 126 return 0; 127 } else if (this.isNaN()) { 128 return 1; 129 } else if (rn.isNaN()) { 130 return -1; 131 } else { 132 RatNum diff = this.sub(rn); 133 return diff.numer; 134 } 135 } 136 137 /** Approximates the value of this rational. 138 @return a double approximation for this. Note that "NaN" is 139 mapped to {@link Double#NaN}, and the {@link Double#NaN} value 140 is treated in a special manner by several arithmetic operations, 141 such as the comparison and equality operators. See the 142 <a href="http://java.sun.com/docs/books/jls/second_edition/html/typesValues.doc.html#9208"> 143 Java Language Specification, section 4.2.3</a>, for more details. 144 */ 145 public double doubleValue() { 146 if (isNaN()) { 147 return Double.NaN; 148 } else { 149 // convert int values to doubles before dividing. 150 return ((double)numer) / ((double)denom); 151 } 152 } 153 154 /** Returns an integer approximation for this. The rational number 155 is rounded to the nearest integer. 156 */ 157 public int intValue() { 158 // round to nearest by adding +/- .5 before truncating division 159 // note that even though the result is guaranteed to fit in an 160 // int, we need to use longs for the computation. 161 if (numer >= 0) { 162 return (int) (((long)numer + (denom/2)) / denom); 163 } else { 164 return (int) (((long)numer - (denom/2)) / denom); 165 } 166 } 167 168 /** Returns a float approximation for this. This method is 169 specified by our superclass, Number. 170 */ 171 public float floatValue() { 172 return (float) doubleValue(); 173 } 174 175 176 /** Returns a long approximation for this. This method is 177 specified by our superclass, Number. The value returned 178 is rounded to the nearest long. 179 */ 180 public long longValue() { 181 return intValue(); 182 } 183 184 185 // in the implementation comments for the following methods, <this> 186 // is notated as "a/b" and <arg> likewise as "x/y" 187 188 /** Returns the additive inverse of this RatNum. 189 @return a Rational equal to (0 - this). 190 */ 191 public RatNum negate() { 192 return new RatNum(- this.numer, this.denom); 193 } 194 195 /** Addition operation. 196 @requires arg != null 197 @return a RatNum equal to (this + arg). 198 If either argument is NaN, then returns NaN. 199 */ 200 public RatNum add(RatNum arg) { 201 // a/b + x/y = ay/by + bx/by = (ay + bx)/by 202 return new RatNum(this.numer*arg.denom + arg.numer*this.denom, 203 this.denom*arg.denom); 204 } 205 206 /** Subtraction operation. 207 @requires arg != null 208 @return a RatNum equal to (this - arg). 209 If either argument is NaN, then returns NaN. 210 */ 211 public RatNum sub(RatNum arg) { 212 // a/b - x/y = a/b + -x/y 213 return this.add(arg.negate()); 214 } 215 216 /** Multiplication operation. 217 @requires arg != null 218 @return a RatNum equal to (this * arg). 219 If either argument is NaN, then returns NaN. 220 */ 221 public RatNum mul(RatNum arg) { 222 // (a/b) * (x/y) = ax/by 223 return new RatNum(this.numer*arg.numer, 224 this.denom*arg.denom ); 225 } 226 227 /** Division operation. 228 @requires arg != null 229 @return a RatNum equal to (this / arg). 230 If arg is zero, or if either argument is NaN, then returns NaN. 231 */ 232 public RatNum div(RatNum arg) { 233 // (a/b) / (x/y) = ay/bx 234 if (arg.isNaN()) { 235 return arg; 236 } else { 237 return new RatNum(this.numer*arg.denom, 238 this.denom*arg.numer); 239 } 240 } 241 242 /** Returns the greatest common divisor of 'a' and 'b'. 243 @requires b != 0 244 @return d such that a % d = 0 and b % d = 0 245 */ 246 private static int gcd(int a, int b) { 247 // Euclid's method 248 if (b == 0) 249 return 0; 250 while (b != 0) { 251 int tmp = b; 252 b = a % b; 253 a = tmp; 254 } 255 return a; 256 } 257 258 /** Standard hashCode function. 259 @return an int that all objects equal to this will also 260 return. 261 */ 262 @Override 263 public int hashCode() { 264 // all instances that are NaN must return the same hashcode; 265 if (this.isNaN()) { 266 return 0; 267 } 268 return this.numer*2 + this.denom*3; 269 } 270 271 /** Standard equality operation. 272 @return true if and only if 'obj' is an instance of a RatNum 273 and 'this' and 'obj' represent the same rational number. Note 274 that NaN = NaN for RatNums. 275 */ 276 @Override 277 public boolean equals(Object obj) { 278 if (obj instanceof RatNum) { 279 RatNum rn = (RatNum) obj; 280 281 // special case: check if both are NaN 282 if (this.isNaN() && rn.isNaN()) { 283 return true; 284 } else { 285 return this.numer == rn.numer && this.denom == rn.denom; 286 } 287 } else { 288 return false; 289 } 290 } 291 292 /** @return a String representing this, in reduced terms. 293 The returned string will either be "NaN", or it will take on 294 either of the forms "N" or "N/M", where N and M are both 295 integers in decimal notation and M != 0. 296 */ 297 @Override 298 public String toString() { 299 // using '+' as String concatenation operator in this method 300 if (isNaN()) { 301 return "NaN"; 302 } else if (denom != 1) { 303 return numer + "/" + denom; 304 } else { 305 return Integer.toString(numer); 306 } 307 } 308 309 /** Makes a RatNum from a string describing it. 310 @requires 'ratStr' is an instance of a string, with no spaces, 311 of the form: <UL> 312 <LI> "NaN" 313 <LI> "N/M", where N and M are both integers in 314 decimal notation, and M != 0, or 315 <LI> "N", where N is an integer in decimal 316 notation. 317 </UL> 318 @returns NaN if ratStr = "NaN". Else returns a 319 RatNum r = ( N / M ), letting M be 1 in the case 320 where only "N" is passed in. 321 */ 322 public static RatNum valueOf(String ratStr) { 323 int slashLoc = ratStr.indexOf('/'); 324 if (ratStr.equals("NaN")) { 325 return new RatNum(1,0); 326 } else if (slashLoc == -1) { 327 // not NaN, and no slash, must be an Integer 328 return new RatNum( Integer.parseInt( ratStr ) ); 329 } else { 330 // slash, need to parse the two parts seperately 331 int n = Integer.parseInt(ratStr.substring(0, slashLoc)); 332 int d = Integer.parseInt(ratStr.substring(slashLoc+1, 333 ratStr.length())); 334 return new RatNum(n, d); 335 } 336 } 337 338 /** 339 * Declare a serialization version number. This field is necessary because 340 * our parent class (Number) implements Serializable; see the api docs for 341 * java.lang.Serializable for more details. 342 */ 343 private static final long serialVersionUID = -8593953691277016262L; 344 }