public class Rational {

	public Rational() {
		this(0, 1);
	}

	public Rational(long num, long den) {
		assert den != 0; // denominator cannot be 0
		if (num == 0) {
			den = 1;
		}
		long factor = gcd(num, den);
		num /= factor;
		den /= factor;
		if (den < 0) {
			num = -num;
			den = -den;
		}
		this.numerator = num;
		this.denominator = den;
	}

	public Rational(Rational r) {
		this(r.numerator, r.denominator);
	}

	public Rational(long n) {
		this(n, 1);
	}

	public Rational add(Rational r) {
		long numer = this.numerator * r.denominator + r.numerator
				* this.denominator;
		long denom = this.denominator * r.denominator;
		return new Rational(numer, denom);
	}

	public Rational subtract(Rational r) {
		long numer = this.numerator * r.denominator - r.numerator
				* this.denominator;
		long denom = this.denominator * r.denominator;
		return new Rational(numer, denom);
	}

	public Rational multiply(Rational r) {
		// caution! overflow if huge numbers
		Rational r1 = new Rational(this.numerator, r.denominator);
		Rational r2 = new Rational(r.numerator, this.denominator);
		return new Rational(r1.numerator*r2.numerator, r1.denominator*r2.denominator);
	}

	public Rational divide(Rational r) {
		// a/b divide c/d = a/b * d/c
		Rational r1 = new Rational(r.denominator, r.numerator);
		return this.multiply(r1);
	}

	public String toString() {
		return "(" + this.numerator + "/" + this.denominator + ")";
	}

	public long compareTo(Rational r) {
		// a/b > c/d if ad > bc
//		long factorTop = gcd(this.numerator, r.numerator);
//		long factorBottom = gcd(this.denominator, r.denominator);
		
		return this.numerator*r.denominator - this.denominator*r.numerator;
	}

	private static long gcd(long a, long b) {
		if (b == 0)
			return a;
		else
			return gcd(b, a % b);
	}
	
	private void invert() {
		assert numerator != 0;
		long temp = this.numerator;
		this.numerator = this.denominator;
		this.denominator = temp;
	}

	public long numerator() {
		return this.numerator;
	}

	public long denominator() {
		return this.denominator;
	}

	private long numerator;
	private long denominator;
}