001 package hw3;
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://docs.oracle.com/javase/specs/jls/se7/html/jls-4.html#jls-4.2.3">
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 // we expect the implementation to use "round half away from zero".
160 // for more info, see http://en.wikipedia.org/wiki/Rounding#Round_half_away_from_zero
161
162 // note that even though the result is guaranteed to fit in an
163 // int, we need to use longs for the computation.
164 if (numer >= 0) {
165 return (int) (((long)numer + (denom/2)) / denom);
166 } else {
167 return (int) (((long)numer - (denom/2)) / denom);
168 }
169 }
170
171 /** Returns a float approximation for this. This method is
172 specified by our superclass, Number.
173 */
174 public float floatValue() {
175 return (float) doubleValue();
176 }
177
178
179 /** Returns a long approximation for this. This method is
180 specified by our superclass, Number. The value returned
181 is rounded to the nearest long.
182 */
183 public long longValue() {
184 return intValue();
185 }
186
187
188 // in the implementation comments for the following methods, <this>
189 // is notated as "a/b" and <arg> likewise as "x/y"
190
191 /** Returns the additive inverse of this RatNum.
192 @return a Rational equal to (0 - this).
193 */
194 public RatNum negate() {
195 return new RatNum(- this.numer, this.denom);
196 }
197
198 /** Addition operation.
199 @requires arg != null
200 @return a RatNum equal to (this + arg).
201 If either argument is NaN, then returns NaN.
202 */
203 public RatNum add(RatNum arg) {
204 // a/b + x/y = ay/by + bx/by = (ay + bx)/by
205 return new RatNum(this.numer*arg.denom + arg.numer*this.denom,
206 this.denom*arg.denom);
207 }
208
209 /** Subtraction operation.
210 @requires arg != null
211 @return a RatNum equal to (this - arg).
212 If either argument is NaN, then returns NaN.
213 */
214 public RatNum sub(RatNum arg) {
215 // a/b - x/y = a/b + -x/y
216 return this.add(arg.negate());
217 }
218
219 /** Multiplication operation.
220 @requires arg != null
221 @return a RatNum equal to (this * arg).
222 If either argument is NaN, then returns NaN.
223 */
224 public RatNum mul(RatNum arg) {
225 // (a/b) * (x/y) = ax/by
226 return new RatNum(this.numer*arg.numer,
227 this.denom*arg.denom );
228 }
229
230 /** Division operation.
231 @requires arg != null
232 @return a RatNum equal to (this / arg).
233 If arg is zero, or if either argument is NaN, then returns NaN.
234 */
235 public RatNum div(RatNum arg) {
236 // (a/b) / (x/y) = ay/bx
237 if (arg.isNaN()) {
238 return arg;
239 } else {
240 return new RatNum(this.numer*arg.denom,
241 this.denom*arg.numer);
242 }
243 }
244
245 /** Returns the greatest common divisor of 'a' and 'b'.
246 @requires b != 0
247 @return d such that a % d = 0 and b % d = 0
248 */
249 private static int gcd(int a, int b) {
250 // Euclid's method
251 if (b == 0)
252 return 0;
253 while (b != 0) {
254 int tmp = b;
255 b = a % b;
256 a = tmp;
257 }
258 return a;
259 }
260
261 /** Standard hashCode function.
262 @return an int that all objects equal to this will also
263 return.
264 */
265 @Override
266 public int hashCode() {
267 // all instances that are NaN must return the same hashcode;
268 if (this.isNaN()) {
269 return 0;
270 }
271 return this.numer*2 + this.denom*3;
272 }
273
274 /** Standard equality operation.
275 @return true if and only if 'obj' is an instance of a RatNum
276 and 'this' and 'obj' represent the same rational number. Note
277 that NaN = NaN for RatNums.
278 */
279 @Override
280 public boolean equals(/*@Nullable*/ Object obj) {
281 if (obj instanceof RatNum) {
282 RatNum rn = (RatNum) obj;
283
284 // special case: check if both are NaN
285 if (this.isNaN() && rn.isNaN()) {
286 return true;
287 } else {
288 return this.numer == rn.numer && this.denom == rn.denom;
289 }
290 } else {
291 return false;
292 }
293 }
294
295 /** @return a String representing this, in reduced terms.
296 The returned string will either be "NaN", or it will take on
297 either of the forms "N" or "N/M", where N and M are both
298 integers in decimal notation and M != 0.
299 */
300 @Override
301 public String toString() {
302 // using '+' as String concatenation operator in this method
303 if (isNaN()) {
304 return "NaN";
305 } else if (denom != 1) {
306 return numer + "/" + denom;
307 } else {
308 return Integer.toString(numer);
309 }
310 }
311
312 /** Makes a RatNum from a string describing it.
313 @requires 'ratStr' is an instance of a string, with no spaces,
314 of the form: <UL>
315 <LI> "NaN"
316 <LI> "N/M", where N and M are both integers in
317 decimal notation, and M != 0, or
318 <LI> "N", where N is an integer in decimal
319 notation.
320 </UL>
321 @returns NaN if ratStr = "NaN". Else returns a
322 RatNum r = ( N / M ), letting M be 1 in the case
323 where only "N" is passed in.
324 */
325 public static RatNum valueOf(String ratStr) {
326 int slashLoc = ratStr.indexOf('/');
327 if (ratStr.equals("NaN")) {
328 return new RatNum(1,0);
329 } else if (slashLoc == -1) {
330 // not NaN, and no slash, must be an Integer
331 return new RatNum( Integer.parseInt( ratStr ) );
332 } else {
333 // slash, need to parse the two parts seperately
334 int n = Integer.parseInt(ratStr.substring(0, slashLoc));
335 int d = Integer.parseInt(ratStr.substring(slashLoc+1,
336 ratStr.length()));
337 return new RatNum(n, d);
338 }
339 }
340
341 /**
342 * Declare a serialization version number. This field is necessary because
343 * our parent class (Number) implements Serializable; see the api docs for
344 * java.lang.Serializable for more details.
345 */
346 private static final long serialVersionUID = -8593953691277016262L;
347 }