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