vnl_rational.h

InsightToolkit-1.4.0(有大量的优化算法程序)

// This is vxl/vnl/vnl_rational.h
#ifndef vnl_rational_h_
#define vnl_rational_h_
//:
// \file
// \brief Infinite precision rational numbers
//
// The  vnl_rational  class  provides  infinite  precision rational numbers and
// arithmetic, using the built-in type long, for the numerator and denominator.
// Implicit conversion to the system defined types short, int, long, float, and
// double is supported by  overloaded  operator member functions.  Although the
// rational class makes judicous use  of inline  functions and  deals only with
// integral values, the user  is warned that  the rational  integer  arithmetic
// class is still considerably slower than the built-in  integer data types. If
// the range  of values  anticipated will  fit into a  built-in  type, use that
// instead.
//
// In  addition  to  the  original  COOL Rational class, vnl_rational is able to
// represent plus and minus infinity.  An  other  interesting  addition  is  the
// possibility  to construct a rational from a double.  This allows for lossless
// conversion from e.g. double 1.0/3.0 to the rational number 1/3, hence no more
// rounding errors.  This is implemented with continued fraction approximations.
//
// \author
// Copyright (C) 1991 Texas Instruments Incorporated.
//
// Permission is granted to any individual or institution to use, copy, modify,
// and distribute this software, provided that this complete copyright and
// permission notice is maintained, intact, in all copies and supporting
// documentation.
//
// Texas Instruments Incorporated provides this software "as is" without
// express or implied warranty.
//
// \verbatim
// Modifications
//  Peter Vanroose, 13 July 2001: Added continued fraction cnstrctr from double
//  Peter Vanroose, 10 July 2001: corrected operator%=()
//  Peter Vanroose, 10 July 2001: corrected ceil() and floor() for negative args
//  Peter Vanroose, 10 July 2001: extended operability range of += by using gcd
//  Peter Vanroose, 10 July 2001: added abs().
//  Peter Vanroose, 10 July 2001: removed state data member and added Inf repres
//  Peter Vanroose,  9 July 2001: ported to vnl from COOL
// \endverbatim

#include <vcl_iostream.h>
#include <vcl_cassert.h>
#include <vcl_cmath.h>
//: Infinite precision rational numbers
//
// The  vnl_rational  class  provides  infinite  precision rational numbers and
// arithmetic, using the built-in type long, for the numerator and denominator.
// Implicit conversion to the system defined types short, int, long, float, and
// double is supported by  overloaded  operator member functions.  Although the
// rational class makes judicous use  of inline  functions and  deals only with
// integral values, the user  is warned that  the rational  integer  arithmetic
// class is still considerably slower than the built-in  integer data types. If
// the range  of values  anticipated will  fit into a  built-in  type, use that
// instead.
//
// In  addition  to  the  original  COOL Rational class, vnl_rational is able to
// represent plus and minus infinity.  An  other  interesting  addition  is  the
// possibility  to construct a rational from a double.  This allows for lossless
// conversion from e.g. double 1.0/3.0 to the rational number 1/3, hence no more
// rounding errors.  This is implemented with continued fraction approximations.
//
class vnl_rational
{
  long num_; //!< Numerator portion
  long den_; //!< Denominator portion

public:
  //: Creates a rational with given numerator and denominator.
  //  Default constructor gives 0.
  //  Also serves as automatic cast from long to vnl_rational.
  //  The only input which is not allowed is (0,0);
  //  the denominator is allowed to be 0, to represent +Inf or -Inf.
#ifdef VCL_BORLAND
  explicit 
#endif
  inline vnl_rational (long num = 0L, long den = 1L)
    : num_(num), den_(den) { assert(num!=0||den!=0); normalize(); }
#ifdef VCL_BORLAND
  inline vnl_rational (int num, int den)
    : num_(num), den_(den) { assert(num!=0||den!=0); normalize(); }
  explicit inline vnl_rational (int num)
    : num_(num), den_(1) { assert(num!=0); normalize(); }
#else
  inline vnl_rational (int num, int den=1)
    : num_(num), den_(den) { assert(num!=0||den!=0); normalize(); }
#endif
  explicit inline vnl_rational (unsigned int num, unsigned int den = 1)
    : num_((long)num), den_((long)den) { assert(num!=0||den!=0); normalize(); }
  //: Creates a rational from a double.
  //  This is done by computing the continued fraction approximation for d.
  //  Note that this is explicitly *not* an automatic type conversion.
  explicit vnl_rational (double d);
  //  Copy constructor
  inline vnl_rational (vnl_rational const& from)
    : num_(from.numerator()), den_(from.denominator()) {}
  //  Destructor
  inline ~vnl_rational() {}
  //  Assignment: overwrite an existing vnl_rational
  inline void set(long num, long den) { assert(num!=0||den!=0); num_=num; den_=den; normalize(); }

  //: Return the numerator of the (simplified) rational number representation
  inline long numerator () const { return num_; }
  //: Return the denominator of the (simplified) rational number representation
  inline long denominator () const { return den_; }

  //: Copies the contents and state of rhs rational over to the lhs
  inline vnl_rational& operator= (vnl_rational const& rhs) {
    num_ = rhs.numerator(); den_ = rhs.denominator(); return *this; }

  //: Returns true if the two rationals have the same representation
  inline bool operator== (vnl_rational const& rhs) const {
    return num_ == rhs.numerator() && den_ == rhs.denominator(); }
  inline bool operator!= (vnl_rational const& rhs) const { return !operator==(rhs); }
  inline bool operator== (long rhs) const { return num_ == rhs && den_ == 1; }
  inline bool operator!= (long rhs) const { return !operator==(rhs); }
  inline bool operator== (int rhs) const { return num_ == rhs && den_ == 1; }
  inline bool operator!= (int rhs) const { return !operator==(rhs); }

  //: Unary minus - returns the negation of the current rational.
  inline vnl_rational operator-() const { return vnl_rational(-num_, den_); }
  //: Unary plus - returns the current rational.
  inline vnl_rational operator+() const { return *this; }
  //: Unary not - returns true if rational is equal to zero.
  inline bool operator!() const { return num_ == 0L; }
  //: Returns the absolute value of the current rational.
  inline vnl_rational abs() const { return vnl_rational(num_<0?-num_:num_, den_); }
  //: Replaces rational with 1/rational and returns it.
  //  Inverting 0 gives +Inf, inverting +-Inf gives 0.
  vnl_rational& invert () {
    long t = num_; num_ = den_; den_ = t; normalize(); return *this; }

  //: Plus/assign: replace lhs by lhs + rhs
  //  Note that +Inf + -Inf and -Inf + +Inf are undefined.
  inline vnl_rational& operator+= (vnl_rational const& r) {
    if (den_ == r.denominator()) num_ += r.numerator();
    else { long c = vnl_rational::gcd(den_,r.denominator()); if (c==0) c=1;
           num_ = num_*(r.denominator()/c) + (den_/c)*r.numerator();
           den_ *= r.denominator()/c; }
    assert(num_!=0 || den_ != 0); // +Inf + -Inf is undefined
    normalize (); return *this;
  }
  inline vnl_rational& operator+= (long r) { num_ += den_*r; return *this; }
  //: Minus/assign: replace lhs by lhs - rhs
  //  Note that +Inf - +Inf and -Inf - -Inf are undefined.
  inline vnl_rational& operator-= (vnl_rational const& r) {
    if (den_ == r.denominator()) num_ -= r.num_;
    else { long c = vnl_rational::gcd(den_,r.denominator()); if (c==0) c=1;
           num_ = num_*(r.denominator()/c) - (den_/c)*r.numerator();
           den_ *= r.denominator()/c; }
    assert(num_!=0 || den_ != 0); // +Inf - +Inf is undefined
    normalize (); return *this;
  }
  inline vnl_rational& operator-= (long r) { num_ -= den_*r; return *this; }
  //: Multiply/assign: replace lhs by lhs * rhs
  //  Note that 0 * Inf and Inf * 0 are undefined.
  inline vnl_rational& operator*= (vnl_rational const& r) {
    num_ *= r.numerator(); den_ *= r.denominator();
    assert(num_!=0 || den_ != 0); // 0 * Inf is undefined
    normalize (); return *this;
  }
  inline vnl_rational& operator*= (long r) {num_*=r;normalize();return *this;}
  //: Divide/assign: replace lhs by lhs / rhs
  //  Note that 0 / 0 and Inf / Inf are undefined.
  inline vnl_rational& operator/= (vnl_rational const& r) {
    num_ *= r.denominator(); den_ *= r.numerator();
    assert(num_!=0 || den_ != 0); // 0/0, Inf/Inf undefined
    normalize (); return *this;
  }
  inline vnl_rational& operator/= (long r) {
    den_ *= r; assert(num_!=0 || den_ != 0); // 0/0 undefined
    normalize (); return *this;
  }
  //: Modulus/assign: replace lhs by lhs % rhs
  //  Note that r % Inf is r, and that r % 0 and Inf % r are undefined.
  inline vnl_rational& operator%= (vnl_rational const& r) {
    assert(r.numerator() != 0);
    if (den_ == r.denominator()) num_ %= r.numerator();
    else { long c = vnl_rational::gcd(den_,r.denominator()); if (c==0) c=1;
           num_ *= r.denominator()/c;
           num_ %= (den_/c)*r.numerator();
           den_ *= r.denominator()/c; }
    normalize (); return *this;
  }
  inline vnl_rational& operator%=(long r){assert(r);num_%=den_*r;normalize();return *this;}

  //: Pre-increment (++r).  No-op when +-Inf.
  inline vnl_rational& operator++ () { num_ += den_; return *this; }
  //: Pre-decrement (--r).  No-op when +-Inf.
  inline vnl_rational& operator-- () { num_ -= den_; return *this; }
  //: Post-increment (r++).  No-op when +-Inf.
  inline vnl_rational operator++(int){vnl_rational b=*this;num_+=den_;return b;}
  //: Post-decrement (r--).  No-op when +-Inf.
  inline vnl_rational operator--(int){vnl_rational b=*this;num_-=den_;return b;}

  inline bool operator< (vnl_rational const& rhs) const {
    if (den_ == rhs.denominator())   // If same denominator
      return num_ < rhs.numerator(); // includes the case -Inf < +Inf
    // note that denominator is always >= 0: