/******************************************************************************
 *  Compilation:  javac Rational.java
 *  Execution:    java Rational
 *  Dependencies: StdOut.java
 *
 *  Immutable ADT for Rational numbers.
 *
 *  Invariants
 *  -----------
 *   - gcd(num, den) = 1, i.e, the rational number is in reduced form
 *   - den >= 1, the denominator is always a positive integer
 *   - 0/1 is the unique representation of 0
 *
 *  We employ some tricks to stave off overflow, but if you
 *  need arbitrary precision rationals, use BigRational.java.
 *
 *  % java Rational
 *  5/6
 *  1
 *  1/120000000
 *  1073741789/12
 *  1
 *  841/961
 *  -1/3
 *
 *  Todo
 *  =====================
 *   - better style to make instance variables final since
 *     data type is immutable
 *
 ******************************************************************************/

public class Rational implements Comparable<Rational> {
    private static Rational zero = new Rational(0, 1);

    private long num;   // the numerator
    private long den;   // the denominator

    // create and initialize a new Rational object
    public Rational(long numerator, long denominator) {

        // deal with x/0
        if (denominator == 0) {
            throw new ArithmeticException("denominator is zero");
        }

        // reduce fraction
        long g = gcd(numerator, denominator);
        num = numerator   / g;
        den = denominator / g;

        // only needed for negative numbers
        if (den < 0) {
            den = -den;
            num = -num;
        }
    }

    // return the numerator and denominator of this rational number
    public long numerator()   { return num; }
    public long denominator() { return den; }

    // return double precision representation of this rational number
    public double toDouble() {
        return (double) num / den;
    }

    // return string representation of this rational number
    public String toString() {
        if (den == 1) return num + "";
        else          return num + "/" + den;
    }

    // return { -1, 0, +1 } if this < that, this = that, or this > that
    public int compareTo(Rational that) {
        long lhs = this.num * that.den;
        long rhs = this.den * that.num;
        if (lhs < rhs) return -1;
        if (lhs > rhs) return +1;
        return 0;
    }

    // is this Rational object equal to other?
    public boolean equals(Object other) {
        if (other == null) return false;
        if (other.getClass() != this.getClass()) return false;
        Rational that = (Rational) other;
        return this.compareTo(that) == 0;
    }

    // hashCode consistent with equals() and compareTo()
    public int hashCode() {
        return this.toString().hashCode();
    }


    // create and return a new rational (r.num + s.num) / (r.den + s.den)
    public static Rational mediant(Rational r, Rational s) {
        return new Rational(r.num + s.num, r.den + s.den);
    }

    // return gcd(|m|, |n|)
    private static long gcd(long m, long n) {
        if (m < 0) m = -m;
        if (n < 0) n = -n;
        if (0 == n) return m;
        else return gcd(n, m % n);
    }

    // return lcm(|m|, |n|)
    private static long lcm(long m, long n) {
        if (m < 0) m = -m;
        if (n < 0) n = -n;
        return m * (n / gcd(m, n));    // parentheses important to avoid overflow
    }

    // return this * that, staving off overflow as much as possible by cross-cancellation
    public Rational times(Rational that) {

        // reduce p1/q2 and p2/q1, then multiply, where a = p1/q1 and b = p2/q2
        Rational c = new Rational(this.num, that.den);
        Rational d = new Rational(that.num, this.den);
        return new Rational(c.num * d.num, c.den * d.den);
    }


    // return this + that, staving off overflow
    public Rational plus(Rational that) {

        // special cases
        if (this.compareTo(zero) == 0) return that;
        if (that.compareTo(zero) == 0) return this;

        // Find gcd of numerators and denominators
        long f = gcd(this.num, that.num);
        long g = gcd(this.den, that.den);

        // add cross-product terms for numerator
        Rational s = new Rational((this.num / f) * (that.den / g)
                                + (that.num / f) * (this.den / g),
                                  this.den * (that.den / g));

        // multiply back in
        s.num *= f;
        return s;
    }

    // return -this
    public Rational negate() {
        return new Rational(-num, den);
    }

    // return |this|
    public Rational abs() {
        if (num >= 0) return this;
        else return negate();
    }

    // return this - that
    public Rational minus(Rational that) {
        return this.plus(that.negate());
    }


    public Rational reciprocal() { return new Rational(den, num);  }

    // return this / that
    public Rational dividedBy(Rational that) {
        return this.times(that.reciprocal());
    }


    // test client
    public static void main(String[] args) {
        Rational x, y, z;

        // 1/2 + 1/3 = 5/6
        x = new Rational(1, 2);
        y = new Rational(1, 3);
        z = x.plus(y);
        StdOut.println(z);

        // 8/9 + 1/9 = 1
        x = new Rational(8, 9);
        y = new Rational(1, 9);
        z = x.plus(y);
        StdOut.println(z);

        // 1/200000000 + 1/300000000 = 1/120000000
        x = new Rational(1, 200000000);
        y = new Rational(1, 300000000);
        z = x.plus(y);
        StdOut.println(z);

        // 1073741789/20 + 1073741789/30 = 1073741789/12
        x = new Rational(1073741789, 20);
        y = new Rational(1073741789, 30);
        z = x.plus(y);
        StdOut.println(z);

        //  4/17 * 17/4 = 1
        x = new Rational(4, 17);
        y = new Rational(17, 4);
        z = x.times(y);
        StdOut.println(z);

        // 3037141/3247033 * 3037547/3246599 = 841/961
        x = new Rational(3037141, 3247033);
        y = new Rational(3037547, 3246599);
        z = x.times(y);
        StdOut.println(z);

        // 1/6 - -4/-8 = -1/3
        x = new Rational(1, 6);
        y = new Rational(-4, -8);
        z = x.minus(y);
        StdOut.println(z);
    }

}