// Rational Number Template

#include <stdlib.h>
#include <sstream>
using namespace std;
#include <math.h>
#include "my_limits.h"
#include "Rational.h"

// template<class T> struct Is_integer_like {
//   static bool constraints(T a) { T b(0), c(1); b=a%c; return a<b;}
//   Is_integer_like() { bool(*p)(T) = constraints; }
// };

// default constructor
template<class T>
Rational<T>::Rational(T n, T d) {
  // Is_integer_like<T>();
  if (d == 0) {
    cerr << "Division by Zero" << endl;
    exit(1);
  }
  if (d < 0) { n = -n; d = -d; }
  if (n == 0) {
    num = 0;   den = 1;
  } else {
    T g = gcd(n, d);
    num = n/g; den = d/g;
  }
}

// binary shortcut operators
template<class T>
const Rational<T>& Rational<T>::operator+=(const Rational<T>& rhs) {
  T g1 = gcd(den, rhs.den);
  if (g1 == 1) {  // 61% probability!
    num = num*rhs.den + den*rhs.num;
    den = den*rhs.den;
  } else {
    T t = num * (rhs.den/g1) + (den/g1)*rhs.num;
    T g2 = gcd(t, g1);
    num = t/g2;
    den = (den/g1) * (rhs.den/g2);
  }
  return *this;
}
 
template<class T>
const Rational<T>& Rational<T>::operator+=(T rhs) {
  num = num + den*rhs;
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator-=(const Rational<T>& rhs) {
  T g1 = gcd(den, rhs.den);
  if (g1 == 1) {  // 61% probability!
    num = num*rhs.den - den*rhs.num;
    den = den*rhs.den;
  } else {
    T t = num * (rhs.den/g1) - (den/g1)*rhs.num;
    T g2 = gcd(t, g1);
    num = t/g2;
    den = (den/g1) * (rhs.den/g2);
  }
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator-=(T rhs) {
  num = num - den*rhs;
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator*=(const Rational<T>& rhs) {
  T g1 = gcd(num, rhs.den);
  T g2 = gcd(den, rhs.num);
  num = (num/g1) * (rhs.num/g2);
  den = (den/g2) * (rhs.den/g1);
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator*=(T rhs) {
  T g = gcd(den, rhs);
  num *= rhs/g;
  den /= g;
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator/=(const Rational<T>& rhs) {
  if (rhs == Rational<T>(0)) {
    cerr << "Division by Zero" << endl;
    exit(1);
  }
  T g1 = gcd(num, rhs.num);
  T g2 = gcd(den, rhs.den);
  num = (num/g1) * (rhs.den/g2);
  den = (den/g2) * (rhs.num/g1);
  if (den < 0) { num = -num; den = -den; }
  return *this;
}

template<class T>
const Rational<T>& Rational<T>::operator/=(T rhs) {
  if (rhs == 0) {
    cerr << "Division by Zero" << endl;
    exit(1);
  }
  T g = gcd(num, rhs);
  num /= g;
  den *= rhs/g;
  if (den < 0) { num = -num; den = -den; }
  return *this;
}

// increment/decrement iterators
template<class T>
const Rational<T>& Rational<T>::operator++() {
  return (*this += 1);
}

template<class T>
const Rational<T> Rational<T>::operator++(int) {
  Rational<T> oldVal = *this;
  ++(*this);
  return oldVal;
}

template<class T>
const Rational<T>& Rational<T>::operator--() {
  return (*this -= 1);
}

template<class T>
const Rational<T> Rational<T>::operator--(int) {
  Rational<T> oldVal = *this;
  --(*this);
  return oldVal;
}

// greatest common divisor: // euclid's algorithm
template<class T>
T Rational<T>::gcd(T u, T v) {
  T a = u < 0 ? -u : u;
  T b = v < 0 ? -v : v;
  T tmp;
  
  if (b > a) {
    tmp = a; a = b; b = tmp;
  }
  for(;;) {
    if (b == 0)
      return a;
    else if (b == 1)
      return b;
    else {
      tmp = b; b = a % b; a = tmp;
    }
  }
}

// binary operators
template<class T>
const Rational<T> operator+(const Rational<T>& lhs, const Rational<T>& rhs) {
  return Rational<T>(lhs) += rhs;
}

template<class T>
const Rational<T> operator-(const Rational<T>& lhs, const Rational<T>& rhs) {
  return Rational<T>(lhs) -= rhs;
}

template<class T>
const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs) {
  return Rational<T>(lhs) *= rhs;
}

template<class T>
const Rational<T> operator/(const Rational<T>& lhs, const Rational<T>& rhs) {
  return Rational<T>(lhs) /= rhs;
}

template<class T>
Rational<T> rabs(const Rational<T>& r) {
  if (r.numerator() < 0) return -r; else return r;
}

// boolean operators
template<class T>
bool operator==(const Rational<T>& lhs, const Rational<T>& rhs) {
  return (lhs.numerator() == rhs.numerator() &&
          lhs.denominator() == rhs.denominator());
}

template<class T>
bool operator!=(const Rational<T>& lhs, const Rational<T>& rhs) {
  return (lhs.numerator() != rhs.numerator() ||
          lhs.denominator() != rhs.denominator());
}

template<class T>
bool operator<(const Rational<T>& lhs, const Rational<T>& rhs) {
  return (toDouble(lhs) < toDouble(rhs));
}

template<class T>
bool operator>(const Rational<T>& lhs, const Rational<T>& rhs) {
  return (toDouble(lhs) > toDouble(rhs));
}

template<class T>
bool operator<=(const Rational<T>& lhs, const Rational<T>& rhs) {
  return ((lhs < rhs) || (lhs == rhs));
}

template<class T>
bool operator>=(const Rational<T>& lhs, const Rational<T>& rhs) {
  return ((lhs > rhs) || (lhs == rhs));
}

template<class T>
ostream& operator<< (ostream& ostr, const Rational<T>& r) {
  if (r.denominator() == 1)
    ostr << r.numerator();
  else {
    ostringstream buf;
    buf.flags(ostr.flags());         // copy stream flags
    buf.fill(ostr.fill());           // copy fill character

    buf << r.numerator() << "/" << r.denominator();

    ostr << buf.str();
  }
  return ostr;
}

template<class T>
istream& operator>> (istream& istr, Rational<T>& r) {
  // accepted format # and #/#
  // where # is integer number
  T n = 0, d = 1;

  istr >> n;
  if ( istr.peek() == '/' ) {
    istr.ignore(1);
    istr >> d;
  }
  if ( istr ) r = Rational<T>(n,d);
  return istr;
}

// double -> Rational conversion
template<class T>
Rational<T> toRational(double x, double limit, int iterations) {
  double intpart;
  double fractpart = modf(x, &intpart);
  double d = 1.0 / fractpart;
  T left = T(intpart);
  if ( d > limit || iterations == 0 ) {
    return Rational<T>(left);
  } else {
    return Rational<T>(left) +
           toRational<T>(d, limit * 0.1, --iterations).invert();
  }
}

template<class T>
Rational<T> toRational(double x, int iterations) {
  if ( x == 0.0 ||
       x < numeric_limits<T>::min() ||
       x > numeric_limits<T>::max() ) {
    return Rational<T>(0,1);
  } else {
    int sign = x < 0.0 ? -1 : 1;
    return Rational<T>(sign) * toRational<T>(sign * x, 1.0e12, iterations);
  }
}