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