#ifndef bqw_fraction_h
#define bqt_fraction_h

/* Fraction number handling.
 * Copyright (C) 1992,2001 Bisqwit (http://iki.fi/bisqwit/)
 */

template<typename inttype=int>
class fraction
{
    inttype num1, num2;
    typedef fraction<inttype> self;
    void Optim();
    inline void Debug(char/* op*/, const self& /*b*/)
    {/*
        cerr << nom() << '/' << denom() << ' ' << op
             << ' ' << b.nom() << '/' << denom()
             << ":\n";*/
    }
public:
    fraction() : num1(0), num2(1) { }
    fraction(inttype valhi) : num1(valhi), num2(1) { }
    fraction(inttype valhi, inttype vallo) : num1(valhi), num2(vallo) { Optim(); }
    inline double value() const {return nom() / (double)denom(); }
    self &operator= (const inttype valhi) { num2=1; num1=valhi; return *this; }
    self &operator+= (const inttype& valhi) { num1+=valhi*denom(); Optim(); return *this; }
    self &operator-= (const inttype& valhi) { num1-=valhi*denom(); Optim(); return *this; }
    self &operator*= (const inttype& valhi) { num1*=valhi; Optim(); return *this; }
    self &operator/= (const inttype& valhi) { num2*=valhi; Optim(); return *this; }
    self &operator+= (const self& b);
    self &operator-= (const self& b);
    self &operator*= (const self& b) { Debug('*',b);num1*=b.nom(); num2*=b.denom(); Optim(); return *this; }
    self &operator/= (const self& b) { Debug('/',b);num1*=b.denom(); num2*=b.nom(); Optim(); return *this; }
    
#define generate_binary_fraction_func_forwarder(op1, op2) \
      self operator op1 (const self& b) const { self tmp(*this); tmp op2 b; return tmp; }
    
    generate_binary_fraction_func_forwarder( +, += )
    generate_binary_fraction_func_forwarder( -, -= )
    generate_binary_fraction_func_forwarder( /, /= ) 
    generate_binary_fraction_func_forwarder( *, *= )
    
#undef generate_binary_fraction_func_forwarder

#define generate_fraction_comparison_func(op) \
      bool operator op(const self& b) const { return value() op b.value(); } \
      bool operator op(inttype b) const { return value() op b; }
    
    generate_fraction_comparison_func( < )
    generate_fraction_comparison_func( > )
    generate_fraction_comparison_func( <= )
    generate_fraction_comparison_func( >= )

#undef generate_fraction_comparison_func
    
    inline const inttype &nom() const   { return num1; }
    inline const inttype &denom() const { return num2; }
    inline bool operator == (inttype b) const { return denom() == 1 && nom() == b; }
    inline bool operator != (inttype b) const { return denom() != 1 || nom() != b; }
    inline bool operator == (const self& b) const { return denom()==b.denom() && nom()==b.nom(); }
    inline bool operator != (const self& b) const { return denom()!=b.denom() || nom()!=b.nom(); }
    operator bool () const { return nom() != 0; }
    inline bool negative() const { return (nom() < 0) ^ (denom() < 0); }
    
    void extract_integer_into(inttype& intpart)
    {
        intpart += num1 / num2;
        num1 %= num2;
    }
};
template<typename inttype>
void fraction<inttype>::Optim()
{
    /* Euclidean algorithm */
    inttype n1, n2;
    if(abs(num1) < abs(num2))
        n1 = num1, n2 = num2;
    else
        n1 = num2, n2 = num1;
    if(!num1) { num2 = 1; return; }
    for(;;)
    {
        //fprintf(stderr, "%d/%d: n1=%d,n2=%d\n", nom(),denom(),n1,n2);
        inttype tmp = n2 % n1;
        if(!tmp)break;
        n2 = n1;
        n1 = tmp;
    }
    num1 /= n1;
    num2 /= n1;
    //fprintf(stderr, "result: %d/%d\n\n", nom(), denom());
}

#define generate_inttype_fraction_forwarder_func(op) \
  template<typename inttype> \
  fraction<inttype> operator op \
    (const inttype bla, const fraction<inttype>& b) \
      { return fraction<inttype> (bla) op b; }
generate_inttype_fraction_forwarder_func( + )
generate_inttype_fraction_forwarder_func( - )
generate_inttype_fraction_forwarder_func( * )
generate_inttype_fraction_forwarder_func( / )
#undef generate_inttype_fraction_forwarder_func

#define generate_summative_fraction_func(op1, op2) \
  template<typename inttype> \
  fraction<inttype> &fraction<inttype>::operator op2 (const fraction<inttype>& b) \
    { \
        if(denom() == b.denom()) \
            num1 op2 b.num1; \
        else \
        { \
            inttype newnom = nom()*b.denom() op1 denom()*b.nom(); \
            num2 *= b.denom(); \
            num1 = newnom; \
            Optim(); \
        } \
        return *this; \
    }
generate_summative_fraction_func( +, += )
generate_summative_fraction_func( -, -= )
#undef generate_summative_fraction_func

/*
template<typename inttype>
ostream &operator << (ostream &dest, const fraction<inttype> &m)
{
    if(m.denom() == 1) return dest << m.nom();
    return dest << m.nom() << '/' << m.denom();
}
*/

#endif