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