// Rational number class template
#ifndef RATIONAL_H
#define RATIONAL_H

#include <cmath>
#include <cstdlib>
#include <ios>
#include <iostream>
#include <ostream>
#include <sstream>
#include <string>

template<typename T>
class rational
{
public:
  typedef T value_type;

  rational()                               : num_(0),   den_(1) {}
  rational(value_type num)                 : num_(num), den_(1) {}
  rational(value_type num, value_type den) : num_(num), den_(den) { reduce(); }
  rational(const rational& r)              : num_(r.num_), den_(r.den_) {}
  template<typename U>
  rational(const rational<U>& r)           : num_(r.num_), den_(r.den_) { reduce(); }

  rational& operator=(const rational& r)    { num_ = r.num_; den_ = r.den_; return *this; }
  template<typename U>
  rational& operator=(const rational<U>& r) { assign(r.numerator(), r.denominator()); return *this; }

  void assign(value_type n, value_type d) { num_ = n; den_ = d; reduce(); }

  value_type numerator()   const { return num_; }
  value_type denominator() const { return den_; }

private:
  void reduce();
  value_type num_;
  value_type den_;
};

template<typename T>
rational<T> abs(const rational<T> a)
{
  return rational<T>(std::abs(a.numerator()), a.denominator());
}

// Return the greatest common divisor of the numerator & denominator,
// using Euclid's algorithm.
template<typename T>
T gcd(T n, T d)
{
  n = std::abs(n);
  while (d != 0) {
    T t = n % d;
    n = d;
    d = t;
  }
  return n;
}

// Reduce the numerator and denominator by the gcd.
template<typename T>
void rational<T>::reduce()
{
  if (den_ < 0) {
    den_ = -den_;
    num_ = -num_;
  }
  T d = gcd(num_, den_);
  num_ /= d;
  den_ /= d;
}

template<typename T, typename U>
rational<T>& operator+=(rational<T>& dst, const rational<U>& src)
{
  dst.assign(dst.numerator() * src.denominator() + dst.denominator() * src.numerator(),
             dst.denominator() * src.denominator());
  return dst;
}
template<typename T, typename U>
rational<T>& operator*=(rational<T>& dst, const rational<U>& src)
{
  dst.assign(dst.numerator() * src.numerator(), dst.denominator() * src.denominator());
  return dst;
}

/* Multiply two rationals. */
template<typename T>
rational<T> operator*(const rational<T>& a, const rational<T>& b)
{
  rational<T> result(a);
  result *= b;
  return result;
}

template<typename T>
rational<T> operator*(const T& a, const rational<T>& b)
{
  return rational<T>(a * b.numerator(), b.denominator());
}

template<typename T>
rational<T> operator*(const rational<T>& a, const T& b)
{
  return rational<T>(b * a.numerator(), a.denominator());
}

/* Add two rationals. */
template<typename T>
rational<T> operator+(const rational<T>& a, const rational<T>& b)
{
  rational<T> result(a);
  result += b;
  return result;
}

template<typename T>
rational<T> operator+(const T& a, const rational<T>& b)
{
  return rational<T>(a * b.denominator() + b.numerator(), b.denominator());
}

template<typename T>
rational<T> operator+(const rational<T>& a, const T& b)
{
  return rational<T>(b * a.denominator() + a.numerator(), a.denominator());
}


template<typename T>
bool operator==(const rational<T>& a, const rational<T>& b)
{
  return a.numerator() == b.numerator() && a.denominator() == b.denominator();
}

template<typename T>
bool operator<(const rational<T>& a, const rational<T>& b)
{
  return a.numerator() * b.denominator() < b.numerator() * a.denominator();
}

template<typename T>
rational<T> operator-(const rational<T>& r)
{
  return rational<T>(-r.numerator(), r.denominator());
}

template<typename T>
rational<T> operator-(const rational<T>& a, const rational<T>& b)
{
  return a + -b;
}

template<typename T>
rational<T> operator-(const rational<T>& a, const T& b)
{
  return a + rational<T>(-b, 1);
}

template<typename T>
rational<T> operator-(const T& a, const rational<T>& b)
{
  return rational<T>(a, 1) - b;
}

/* Read a rational number. The numerator and denominator must be written
 * as two numbers (the first can be signed) separated by a slash (/),
 * e.g., "2/3", "-14/19".
 */
template<typename T, typename charT, typename traits>
::std::basic_istream<charT, traits>& operator>>(::std::basic_istream<charT, traits>& in, rational<T>& r)
{
  typename rational<T>::value_type n;
  typename rational<T>::value_type d;
  char c;

  if (! (in >> n)) return in;
  if (! (in >> c)) return in;
  if (c != '/') {
     // Malformed input.
     in.setstate(::std::ios_base::badbit);
     return in;
  }
  if (! (in >> d)) return in;
  r.assign(n, d);
  return in;
}

/* Print a rational number as two integers separated by a slash. */
template<typename T, typename charT, typename traits>
::std::basic_ostream<charT, traits>& operator<<(::std::basic_ostream<charT, traits>& out, const rational<T>& r) {
  ::std::basic_ostringstream<charT, traits> s;
  s.flags(out.flags());
  s.imbue(out.getloc());
  s.precision(out.precision());
  s << r.numerator() << '/' << r.denominator();
  out << s.str();
  return out;
}

#endif // RATIONAL_H