#ifndef FRACTIONH
#define FRACTIONH

/* ***************************************************************** *
 *                                                                   *
 *             Fraction.h  (C) 1999   Michael R. Toth                *
 *                                                                   *
 *    This class implements the field of fractions of a Euclidean    *
 *  domain. The class parameter "PID" should implement  +, -, *, /,  *
 *  %, ==, !=, =, +=, -=, *=, /=, %=, and << and >> to and from      *
 *  streams. It should be constructable from an "int".               *
 *                                                                   *
 * ***************************************************************** */

#include <iostream.h>
#include "Euclid.h"

template<class PID>  class Fraction
{
  friend PID& Numerator( Fraction& );
  friend PID& Denominator( Fraction& );
  friend bool Invert( Fraction& );
  friend ostream& operator<< ( ostream&, const Fraction& );
  friend istream& operator>> ( istream&, Fraction& );
protected:
  PID  Num, Den;
public:
  void Reduce( )  { PID Gcd=GCD(Num,Den);  Num/=Gcd, Den/=Gcd; }
  void Inflate( PID& Cd )  { Num*=Cd, Den*=Cd; } 
  Fraction( const Fraction& that ): Num(that.Num),Den(that.Den)   { }  
  Fraction( const PID& n,const PID& d =PID(1) ): Num(n),Den(d)
          { Reduce( ); }
  Fraction( const int n =0 ): Num(PID(n)),Den(PID(1))  { }
  Fraction& operator= ( const Fraction& that )
                      {
                        if ( this!=&that )  Num=that.Num, Den=that.Den;
                        return *this;
                      }
  Fraction& operator= ( const PID& n )  { Num=n, Den=1;  return *this; }
  bool operator== ( const Fraction& that ) const
                  { return  Num*that.Den==Den*that.Num; }
  bool operator!= ( const Fraction& that ) const
                  { return  Num*that.Den!=Den*that.Num; }
  Fraction operator- ( ) const  { return  Fraction(-Num,Den); }
  Fraction& operator+= ( const Fraction& );
  Fraction& operator+= ( const PID& n )  { Num+=n*Den;  return *this; }
  Fraction& operator-= ( const Fraction& that )
                       { operator+= (-that);  return *this; } 
  Fraction& operator-= ( const PID& n )  { Num-=n*Den;  return *this; }
  Fraction& operator*= ( const Fraction& );
  Fraction& operator*= ( const PID& n )
            { PID Gcd=GCD(n,Den);  Num*=n/Gcd, Den/=Gcd;  return *this; }
  Fraction& operator/= ( const Fraction& );
  Fraction& operator/= ( const PID& d )
            { PID Gcd=GCD(d,Den);  Num/=Gcd, Den*=d/Gcd;  return *this; }
  Fraction operator[] ( int ) const;   // Integer power.
};

template<class PID> inline
PID& Numerator( Fraction<PID>& x )  { return x.Num; }

template<class PID> inline
PID& Denominator( Fraction<PID>& x )  { return x.Den; }

template<class PID> inline
bool Invert( Fraction<PID>& x )
           { PID n=x.Num;  x.Num=x.Den, x.Den=n;  return  n!=0; }

template<class PID>
ostream& operator<< ( ostream& out, const Fraction<PID>& x )
                    { 
                      if ( Unit(x.Den) )  out<<x.Num/x.Den;
                           else  out<<"("<<x.Num<<" / "<<x.Den<<")";
                      return out;
                     }

template<class PID>
istream& operator>> ( istream& in, Fraction<PID>& x )
                    { in>>x.Num>>x.Den;  x.Reduce( );  return in; }

template<class PID>
Fraction<PID>& Fraction<PID>::operator+= ( const Fraction& that )
               { 
                 PID Gcd=GCD(Den,that.Den);
                 PID Q=that.Den/Gcd;
                 Num*=Q;
                 Num+=Den/Gcd*that.Num;
                 Den*=Q;
                 Reduce( );
                 return *this;
               }

template<class PID>
Fraction<PID>& Fraction<PID>::operator*= ( const Fraction& that )
               {
                 Fraction L(Num,that.Den);
                 Fraction R(that.Num,Den);
                 Num=L.Num*R.Num, Den=L.Den*R.Den;
                 return *this;
               }

template<class PID>
Fraction<PID>& Fraction<PID>::operator/= ( const Fraction& that )
               {
                 Fraction L(Num,that.Num);
                 Fraction R(that.Den,Den);
                 Num=L.Num*R.Num, Den=L.Den*R.Den;
                 return *this;
               }

template<class PID> inline
Fraction<PID> operator+ ( Fraction<PID> x, const Fraction<PID>& y )
                        { return  x+=y; }

template<class PID> inline
Fraction<PID> operator+ ( Fraction<PID> x, const PID& y )
                        { return  x+=y; }

template<class PID> inline
Fraction<PID> operator+ ( const PID& x, Fraction<PID> y )
                        { return  y+=x; }

template<class PID> inline
Fraction<PID> operator- ( Fraction<PID> x, const Fraction<PID>& y )
                        { return  x-=y; }

template<class PID> inline
Fraction<PID> operator- ( Fraction<PID> x, const PID& y )
                        { return  x-=y; }

template<class PID> inline
Fraction<PID> operator- ( const PID& x, const Fraction<PID>& y )
                        { return  -y+=x; }

template<class PID> inline
Fraction<PID> operator* ( Fraction<PID> x, const Fraction<PID>& y )
                        { return  x*=y; }

template<class PID> inline
Fraction<PID> operator* ( Fraction<PID> x, const PID& y )
                        { return  x*=y; }

template<class PID> inline
Fraction<PID> operator* ( const PID& x, Fraction<PID> y )
                        { return  y*=x; }

template<class PID> inline
Fraction<PID> operator/ ( Fraction<PID> x, const Fraction<PID>& y )
                        { return  x/=y; }

template<class PID> inline
Fraction<PID> operator/ ( Fraction<PID> x, const PID& y )
                        { return  x/=y; }

template<class PID> inline
Fraction<PID> operator/ ( const PID& x, Fraction<PID> y )
                        { Invert(y);  return  y*=x; }

template<class PID>
Fraction<PID> Fraction<PID>::operator[] ( int p ) const
              {                
                Fraction x=*this;
                if ( p<0 )  Invert(x), p=-p;
                Fraction y= p&1? x: Fraction(1);
                while ( p>>=1 )  { x*=x;  if ( p&1 )  y*=x; }
                return y;
              }

#endif FRACTIONH