Rational.hh

/*************************************************************************
 * File: Rational.hh
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * Implementation of a rational number class.  This object tracks a
 * numerator and denominator of arbitrary integral type, and allows for
 * operations that manipulate the rational quantity.  Each addition,
 * subtraction, multiplication, or division runs in time O(op + lg n),
 * where op is the time it takes to perform the operation.  The lg n term
 * comes in from the application of Euclid's algorithm to normalize the
 * numerator and denominator by their gcd.
 */
#ifndef Rational_Included
#define Rational_Included

#include <ostream>   // For std::ostream
#include <stdexcept> // For std::domain_error
#include <algorithm> // For std::swap
#include <sstream>   // For std::basic_stringstream

/**
 * Class: Rational<T>
 * -----------------------------------------------------------------------
 * A generalized rational number class.  The template parameter must be
 * an integral type supporting +, -, *, /, and the compound assignment
 * versions of these operators.  The template parameter should be signed.
 */
template <typename SignedInteger>
class Rational {
public:
  /**
   * Rational(const SignedInteger& num = 0, 
   *          const SignedInteger& denom = 1);
   * Usage: Rational<int> piApprox(355, 113);
   * ---------------------------------------------------------------------
   * Constructs a new Rational with the specified numerator and
   * denominator.  If the denominator is zero, a domain_error is thrown.
   */
  Rational(const SignedInteger& numerator = SignedInteger(0),
           const SignedInteger& denominator = SignedInteger(1));

  /**
   * SignedInteger numerator() const;
   * SignedInteger denominator() const;
   * ---------------------------------------------------------------------
   * Retrieves the numerator or denominator of the rational number.
   */
  SignedInteger numerator() const;
  SignedInteger denominator() const;

  /**
   * Rational& operator+= (const Rational<SignedInteger>& rhs);
   * Rational& operator-= (const Rational<SignedInteger>& rhs);
   * Rational& operator*= (const Rational<SignedInteger>& rhs);
   * Rational& operator/= (const Rational<SignedInteger>& rhs);
   * ---------------------------------------------------------------------
   * Adds, subtracts, multiplies, or divides this rational number by some
   * other rational number.
   */
  Rational& operator+= (const Rational<SignedInteger>& rhs);
  Rational& operator-= (const Rational<SignedInteger>& rhs);
  Rational& operator*= (const Rational<SignedInteger>& rhs);
  Rational& operator/= (const Rational<SignedInteger>& rhs);

  /**
   * Rational& operator*= (const SignedInteger& scaleFactor);
   * Rational& operator/= (const SignedInteger& scaleFactor);
   * ---------------------------------------------------------------------
   * Scales the rational number by the specified value.  Dividing by zero
   * will produce a domain_error.
   */
  Rational& operator*= (const SignedInteger& scaleFactor);
  Rational& operator/= (const SignedInteger& scaleFactor);

private:
  /* The numerator and denominator. */
  SignedInteger mNumerator, mDenominator;

  /* Yields the GCD of two numbers. */
  static SignedInteger gcd(const SignedInteger& one, 
                           const SignedInteger& two);

  /* Simplifies the fraction by dividing by the GCD of the numerator
   * and denominator.
   */
  void simplify();
};

/*** Utility functions ***/

/**
 * double AsReal(const Rational<T>&) const;
 * Usage: cout << AsReal(piApprox) << endl;
 * ----------------------------------------------------------------------
 * Returns an approximation of the rational number as a real number.
 * This operation is only supported if SignedInteger can be converted to
 * a double.
 */
template <typename SignedInteger>
double AsReal(const Rational<SignedInteger>& ratio);

/**
 * const Rational<T> Reciprocal(const Rational<T>&);
 * Usage: Rational<int> oneOverPi = Reciprocal(piApprox);
 * ---------------------------------------------------------------------
 * Returns the reciprocal of the specified fraction, throwing a
 * domain_error if the argument is zero.
 */
template <typename SignedInteger>
const Rational<SignedInteger> Reciprocal(const Rational<SignedInteger>& ratio);

/* Binary arithmetic operators */
template <typename SignedInteger>
const Rational<SignedInteger> operator+ (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
const Rational<SignedInteger> operator- (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
const Rational<SignedInteger> operator* (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
const Rational<SignedInteger> operator/ (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs);

/* Comparison operators. */
template <typename SignedInteger>
bool operator<  (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
bool operator<= (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
bool operator== (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
bool operator!= (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
bool operator>= (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
template <typename SignedInteger>
bool operator>  (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs);
  
/* Unary arithmetic operators */
template <typename SignedInteger>
const Rational<SignedInteger> operator- (const Rational<SignedInteger>& r);
template <typename SignedInteger>
const Rational<SignedInteger> operator+ (const Rational<SignedInteger>& r);

/* Stream insertion operator. */
template <typename SignedInteger, typename charT, typename traits>
std::basic_ostream<charT, traits>&
operator<< (std::basic_ostream<charT, traits>&,
            const Rational<SignedInteger>& r);

/* * * * * Implementation Below This Point * * * * */

/* Constructor sets the numerator and denominator, then normalizes them. */
template <typename SignedInteger>
Rational<SignedInteger>::Rational(const SignedInteger& numerator,
                                  const SignedInteger& denominator) 
  : mNumerator(numerator), mDenominator(denominator) {
  /* Report an error if the denominator is zero. */
  if (denominator == SignedInteger(0))
    throw std::domain_error("Denominator cannot be zero.");

  /* Simplify the fraction. */
  simplify();
}

/* Getting the numerator or denominator is straightforward. */
template <typename SignedInteger>
SignedInteger Rational<SignedInteger>::numerator() const {
  return mNumerator;
}
template <typename SignedInteger>
SignedInteger Rational<SignedInteger>::denominator() const {
  return mDenominator;
}

/* Scaling by a constant works by multiplying the numerator by the
 * specified value, then simplifying the fraction.
 */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator*= (const SignedInteger& scale) {
  mNumerator *= scale;
  simplify();

  return *this;
}

/* Dividing by a constant checks whether that constant is zero, then
 * scales the denominator appropriately.
 */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator/= (const SignedInteger& scale) {
  /* Check for division-by-zero. */
  if (scale == SignedInteger(0))
    throw std::domain_error("Attempted to divide by zero.");

  mDenominator *= scale;
  simplify();

  return *this;
}

/* Addition works by scaling each side by the denominator of the other,
 * adding the two sides, then simplifying.
 */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator+= (const Rational<SignedInteger>& rhs) {
  /* a/b + c/d = ad + bc / bd */
  mNumerator = numerator() * rhs.denominator() +
               rhs.numerator() * denominator();
  mDenominator *= rhs.denominator();

  /* Simplify everything. */
  simplify();

  return *this;
}

/* Subtraction is similar to addition, but we add the inverse of the other
 * side instead of directly adding the other side.
 */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator-= (const Rational<SignedInteger>& rhs) {
  return *this += -rhs;
}

/* Multiplication works by scaling the numerator and denominator by the
 * numerator and denominator of the other fraction, then normalizing.
 */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator*= (const Rational<SignedInteger>& rhs) {
  mNumerator *= rhs.numerator();
  mDenominator *= rhs.denominator();
  simplify();

  return *this;
}

/* Division is just multiplication by the reciprocal. */
template <typename SignedInteger>
Rational<SignedInteger>& Rational<SignedInteger>::operator/= (const Rational<SignedInteger>& rhs) {
  return *this *= Reciprocal(rhs);
}

/* Simplification works by getting the GCD of the numerator and denominator,
 * then dividing each by it.
 */
template <typename SignedInteger>
void Rational<SignedInteger>::simplify() {
  /* Compute the GCD. */
  const SignedInteger GCD = gcd(numerator(), denominator());

  /* Normalize by it. */
  mNumerator /= GCD;
  mDenominator /= GCD;

  /* If the denominator is negative, then flip its sign and make the
   * numerator negative.
   */
  if (mDenominator < SignedInteger(0)) {
    mDenominator = -mDenominator;
    mNumerator = -mNumerator;
  }
}

/* Getting the GCD uses Euclid's algorithm.  In particular:
 *               GCD(b, a)     if a < b
 * GCD(a, b) = { a             if b == 0
 *               GCD(b, a % b) otherwise
 * However, we have to account for the possibility that one or more
 * of the numbers is negative.  In that case, we'll use the GCD
 * algorithm on the positive version of the numbers, then will
 * correct the sign of the GCD appropriately upon return.  In
 * particular, we'll only say that the GCD is negative if both
 * values are negative.
 *
 * Note that this will behave weirdly if either a or b are the
 * minimum possible integer in a two's-complement, fixed-size
 * representation because -INT_MIN == INT_MIN.  We won't handle
 * this case here.
 */
template <typename SignedInteger>
SignedInteger Rational<SignedInteger>::gcd(const SignedInteger& one,
                                           const SignedInteger& two) {
  /* Copy the values here so that we can mangle them in the process.*/
  SignedInteger a = one, b = two;
  
  /* Correct for sign errors. */
  const bool bothNegative = a < SignedInteger(0) && b < SignedInteger(0);

  /* Make both values positive. */
  if (a < SignedInteger(0))
    a = -a;
  if (b < SignedInteger(0))
    b = -b;

  /* Loop until convergence. */
  while (true) {
    /* Make sure a >= b. */
    if (a < b)
      std::swap(a, b);

    /* Base case: If b == 0, the answer is a. */
    if (b == 0) break;

    /* Otherwise, set a = b, b = a % b. */
    const SignedInteger tmp = b;
    b = a % b;
    a = tmp;
  }

  /* Return a, after possibly multiplying by -1. */
  return bothNegative? -a : a;
}

/* AsReal works by casting the numerator and denominator to doubles and
 * performing the division.
 */
template <typename SignedInteger>
double AsReal(const Rational<SignedInteger>& rational) {
  return double(rational.numerator()) / double(rational.denominator());
}

/* Reciprocal just creates a new Rational with the numerator and
 * denominator swapped.  The Rational constructor handles the error-checking.
 */
template <typename SignedInteger>
const Rational<SignedInteger> Reciprocal(const Rational<SignedInteger>& rational) {
  return Rational<SignedInteger>(rational.denominator(), rational.numerator());
}

/* Binary arithmetic operators implemented in terms of compound assignment
 * operators.
 */
template <typename SignedInteger>
const Rational<SignedInteger> operator+ (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs) {
  return Rational<SignedInteger>(lhs) += rhs;
}
template <typename SignedInteger>
const Rational<SignedInteger> operator- (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs) {
  return Rational<SignedInteger>(lhs) -= rhs;
}
template <typename SignedInteger>
const Rational<SignedInteger> operator* (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs) {
  return Rational<SignedInteger>(lhs) *= rhs;
}
template <typename SignedInteger>
const Rational<SignedInteger> operator/ (const Rational<SignedInteger>& lhs,
                                         const Rational<SignedInteger>& rhs) {
  return Rational<SignedInteger>(lhs) /= rhs;
}

/* Binary equality works by testing if the two objects have identical
 * representations.  This works because we always simplify the
 * representation to a canonical form.
 */
template <typename SignedInteger>
bool operator== (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs) {
  return lhs.numerator() == rhs.numerator() && lhs.denominator() == rhs.denominator();
}

/* Less-than works by scaling both rationals up to have the same denominator,
 * then checking the numerators.
 */
template <typename SignedInteger>
bool operator<  (const Rational<SignedInteger>& lhs,
                 const Rational<SignedInteger>& rhs) {
  /* a/b < c/d   iff   ad/bd < bc/bd */
  return lhs.numerator() * rhs.denominator() < rhs.numerator() * lhs.denominator();
}

/* Remaining relational operators implemented in terms of the existing
 * operators.
 */
template <typename SignedInteger>
bool operator <= (const Rational<SignedInteger>& lhs,
                  const Rational<SignedInteger>& rhs) {
  return !(rhs < lhs);
}
template <typename SignedInteger>
bool operator != (const Rational<SignedInteger>& lhs,
                  const Rational<SignedInteger>& rhs) {
  return !(rhs == lhs);
}
template <typename SignedInteger>
bool operator >= (const Rational<SignedInteger>& lhs,
                  const Rational<SignedInteger>& rhs) {
  return !(lhs < rhs);
}
template <typename SignedInteger>
bool operator >  (const Rational<SignedInteger>& lhs,
                  const Rational<SignedInteger>& rhs) {
  return rhs < lhs;
}

/* Unary arithmetic operators implemented in terms of constructor and
 * identity.
 */
template <typename SignedInteger>
const Rational<SignedInteger> operator+ (const Rational<SignedInteger>& op) {
  return op;
}
template <typename SignedInteger>
const Rational<SignedInteger> operator- (const Rational<SignedInteger>& op) {
  return Rational<SignedInteger>(-op.numerator(), op.denominator());
}

/* Stream insertion operator works by printing out the numerator and
 * denominator separated by a / sign.
 */
template <typename SignedInteger, typename charT, typename traits>
std::basic_ostream<charT, traits>& 
operator<< (std::basic_ostream<charT, traits>& out,
            const Rational<SignedInteger>& rational) {
  /* Buffer all operations into a stringstream. */
  std::basic_stringstream<charT, traits> buffer;
 
  /* Copy formatting info, but not width. */
  buffer.imbue(out.getloc());
  buffer.flags(out.flags());
  buffer.precision(out.precision());

  /* Get a copy of the code conversion facet so we can print out appropriate
   * representations of spaces and slashes.
   */
  const std::ctype<charT>& ccvt = std::use_facet< std::ctype<charT> >(buffer.getloc());

  /* Print out the rational number. */
  buffer << rational.numerator() << ccvt.widen('/') << rational.denominator();

  /* Flush buffer into the stream. */
  return out << buffer.str();
}

#endif