public class Fraction
{
  private int top;    //top and bottom are in lowest terms (i.e. gcd(top, bottom) = 1)
  private int bottom; //must be strictly positive
 
  public Fraction(int t, int b) 
  {
    this.top = t;
    this.bottom = b;
    if (this.bottom == 0)
    {
      throw new FractionException("Invalid denominator");
    }
    if(this.bottom < 0)
    {
      this.top = -this.top;
      this.bottom = -this.bottom;
    }
  }

  public Fraction(int val) 
  {
    this(val, 1);
  }

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

  private void normalize()
  {
    int g = gcd(Math.abs(this.top), Math.abs(this.bottom));
    if(g > 1)  
    {
      this.top = this.top / g;
      this.bottom = this.bottom / g;
    }
  }

  private static int gcd(int lg, int s)
  {
    int r;
    while(s > 0)
    {
      r = lg % s;
      lg = s; 
      s = r;
    }
    return lg;
  }

  public Fraction add(Fraction rhs) 
  {
    Fraction retval = new Fraction();
    retval.bottom = this.bottom * rhs.bottom;
    retval.top = this.top * rhs.bottom + rhs.top * this.bottom;
    retval.normalize();
    return retval;
  }
    
  public Fraction negate() 
  {
    Fraction retval = new Fraction(-this.top, this.bottom);
    return retval;
  }

  public Fraction subtract(Fraction rhs) 
  {
    Fraction retval = rhs.negate();
    retval =  this.add(retval);
    retval.normalize();
    return retval;
  }

  public Fraction times(Fraction rhs)
  {
    Fraction retval = new Fraction(this.top*rhs.top, this.bottom*rhs.bottom);
    retval.normalize();
    return retval;
  }

  public Fraction invert()
  {
    if(this.top == 0)
      throw new FractionException("Fraction divide by zero");
    else 
      return new Fraction(this.bottom, this.top);
  }

  public Fraction divideBy(Fraction rhs)
  {
    Fraction retval = rhs.invert();
    retval = this.times(retval);
    retval.normalize();
    return retval;
  }

  public int compareTo(Fraction rhs)
  {
    Fraction temp = this.subtract(rhs);
    return temp.top;
  }

  public String toString()
  {
    return this.top + "/"  + this.bottom;
  }
  
  public static void main(String args[]) 
  {
    Fraction f1 = new Fraction(1,2);
    Fraction f2 = new Fraction(1,4);
    Fraction f3 = f1.add(f2);
    System.out.println(f1 + " + " + f2 + " = " + f3);
    Fraction f4 = f2.negate();
    System.out.println(f4); 
    Fraction f5 = f1.subtract(f2);
    System.out.println(f5);
    Fraction f6 = f1.times(f2);
    System.out.println(f6);
    Fraction f7 = f1.divideBy(f2);
    System.out.println(f7);

    System.out.println(f1.compareTo(f2));
    System.out.println(f2.compareTo(f1));
    System.out.println(f1.compareTo(f1));

  }
}