// Copyright (c) 1999-2004 Utrecht University (The Netherlands), // ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany), // INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg // (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria), // and Tel-Aviv University (Israel). All rights reserved. // // This file is part of CGAL (www.cgal.org); you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public License as // published by the Free Software Foundation; version 2.1 of the License. // See the file LICENSE.LGPL distributed with CGAL. // // Licensees holding a valid commercial license may use this file in // accordance with the commercial license agreement provided with the software. // // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. // // $Source: /CVSROOT/CGAL/Packages/Number_types/include/CGAL/Quotient.h,v $ // $Revision: 1.36 $ $Date: 2004/09/22 16:54:17 $ // $Name: $ // // Author(s) : Stefan Schirra, Sylvain Pion // The template class Quotient is based on the LEDA class // leda_rational written by Stefan Naeher and Christian Uhrig. // It is basically a templated version with restricted functionality // of the version of rational in LEDA release 3.3. // The modification was done by Stefan.Schirra@mpi-sb.mpg.de // The include is done before the protect macro on purpose, because // of a cyclic dependency. #include #ifndef CGAL_QUOTIENT_H #define CGAL_QUOTIENT_H #include #ifndef CGAL_CFG_NO_LOCALE # include #else # include #endif #include #include CGAL_BEGIN_NAMESPACE namespace CGALi { // Mini helper to prevent clashes when NT == int. template < typename T > struct Int_if_not_int { typedef int type; }; template <> struct Int_if_not_int { struct type{}; }; } // namespace CGALi #define CGAL_int(T) typename CGALi::Int_if_not_int::type // Simplify the quotient numerator/denominator. // Currently the default template doesn't do anything. // This function is not documented as a number type requirement for now. template < typename NT > inline void simplify_quotient(NT &, NT &) {} template class Quotient { public: typedef NT_ NT; typedef Tag_false Has_gcd; typedef Tag_true Has_division; typedef typename Number_type_traits::Has_sqrt Has_sqrt; typedef Tag_true Has_exact_division; typedef typename Number_type_traits::Has_exact_sqrt Has_exact_sqrt; typedef typename Number_type_traits::Has_exact_ring_operations Has_exact_ring_operations; Quotient() : num(0), den(1) {} template Quotient(const T& n) : num(n), den(1) {} template Quotient(const T1& n, const T2& d) : num(n), den(d) { CGAL_precondition( d != 0 ); } Quotient& operator+= (const Quotient& r); Quotient& operator-= (const Quotient& r); Quotient& operator*= (const Quotient& r); Quotient& operator/= (const Quotient& r); Quotient& operator+= (const NT& r); Quotient& operator-= (const NT& r); Quotient& operator*= (const NT& r); Quotient& operator/= (const NT& r); Quotient& operator+= (const CGAL_int(NT)& r); Quotient& operator-= (const CGAL_int(NT)& r); Quotient& operator*= (const CGAL_int(NT)& r); Quotient& operator/= (const CGAL_int(NT)& r); Quotient& normalize(); const NT& numerator() const { return num; } const NT& denominator() const { return den; } void swap(Quotient &q) { using std::swap; swap(num, q.num); swap(den, q.den); } public: NT num; NT den; }; template inline void swap(Quotient &p, Quotient &q) { p.swap(q); } template Quotient sqrt(const Quotient &q) { CGAL_precondition(q > 0); return Quotient(CGAL_NTS sqrt(q.numerator()*q.denominator()), q.denominator()); } template CGAL_MEDIUM_INLINE Quotient& Quotient::normalize() { if (num == den) { num = den = 1; return *this; } if (-num == den) { num = -1; den = 1; return *this; } NT ggt = gcd(num, den); if (ggt != 1 ) { num /= ggt; den /= ggt; } return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator+= (const Quotient& r) { num = num * r.den + r.num * den; den *= r.den; simplify_quotient(num, den); return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator-= (const Quotient& r) { num = num * r.den - r.num * den; den *= r.den; simplify_quotient(num, den); return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator*= (const Quotient& r) { num *= r.num; den *= r.den; simplify_quotient(num, den); return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator/= (const Quotient& r) { CGAL_precondition( r.num != 0 ); num *= r.den; den *= r.num; simplify_quotient(num, den); return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator+= (const NT& r) { num += r * den; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator-= (const NT& r) { num -= r * den; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator*= (const NT& r) { num *= r; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator/= (const NT& r) { CGAL_precondition( r != 0 ); den *= r; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator+= (const CGAL_int(NT)& r) { num += r * den; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator-= (const CGAL_int(NT)& r) { num -= r * den; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator*= (const CGAL_int(NT)& r) { num *= r; return *this; } template CGAL_MEDIUM_INLINE Quotient& Quotient::operator/= (const CGAL_int(NT)& r) { CGAL_precondition( r != 0 ); den *= r; return *this; } template CGAL_MEDIUM_INLINE Comparison_result quotient_cmp(const Quotient& x, const Quotient& y) { // No assumptions on the sign of den are made // code assumes that SMALLER == - 1; CGAL_precondition( SMALLER == static_cast(-1) ); int xsign = CGAL_NTS sign(x.num) * CGAL_NTS sign(x.den) ; int ysign = CGAL_NTS sign(y.num) * CGAL_NTS sign(y.den) ; if (xsign == 0) return static_cast(-ysign); if (ysign == 0) return static_cast(xsign); // now (x != 0) && (y != 0) int diff = xsign - ysign; if (diff == 0) { int msign = CGAL_NTS sign(x.den) * CGAL_NTS sign(y.den); NT leftop = x.num * y.den * msign; NT rightop = y.num * x.den * msign; return CGAL_NTS compare(leftop, rightop); } else { return (xsign < ysign) ? SMALLER : LARGER; } } template inline Comparison_result compare(const Quotient& x, const Quotient& y) { return quotient_cmp(x, y); } template std::ostream& operator<<(std::ostream& s, const Quotient& r) { return s << r.numerator() << "/" << r.denominator(); } template std::istream& operator>>(std::istream& in, Quotient& r) { /* format num/den or simply num */ char c = 0; #ifndef CGAL_CFG_NO_LOCALE while (in.get(c) && std::isspace(c, std::locale::classic() )); #else while (in.get(c) && CGAL_CLIB_STD::isspace(c)); #endif // CGAL_CFG_NO_LOCALE if ( !in ) return in; in.putback(c); NT num; NT den(1); in >> num; #ifndef CGAL_CFG_NO_LOCALE while (in.get(c) && std::isspace(c, std::locale::classic() )); #else while (in.get(c) && CGAL_CLIB_STD::isspace(c)); #endif // CGAL_CFG_NO_LOCALE if (( in ) && ( c == '/')) { #ifndef CGAL_CFG_NO_LOCALE while (in.get(c) && std::isspace(c, std::locale::classic() )); #else while (in.get(c) && CGAL_CLIB_STD::isspace(c)); #endif // CGAL_CFG_NO_LOCALE CGAL_assertion( in ); in.putback(c); in >> den; } else { in.putback(c); if ( in.eof() ) in.clear(); } r = Quotient( num, den); return in; } template inline io_Operator io_tag(const Quotient&) { return io_Operator(); } template CGAL_MEDIUM_INLINE Quotient operator+(const Quotient& x, const Quotient& y) { Quotient z = x; return z += y; } template CGAL_MEDIUM_INLINE Quotient operator-(const Quotient& x, const Quotient& y) { return (Quotient(x) -= y); } template CGAL_MEDIUM_INLINE Quotient operator*(const Quotient& x, const Quotient& y) { Quotient z = x; return z *= y; } template CGAL_MEDIUM_INLINE Quotient operator/(const Quotient& x, const Quotient& y) { Quotient z = x; return z /= y; } template inline Quotient operator-(const Quotient& x) { return Quotient(-x.num,x.den); } template CGAL_MEDIUM_INLINE Quotient operator+(const NT& x, const Quotient& y) { Quotient z(x); return z += y; } template CGAL_MEDIUM_INLINE Quotient operator+(const Quotient& x, const NT& y) { Quotient z = x; return z += y; } template CGAL_MEDIUM_INLINE Quotient operator+(const Quotient& x, const CGAL_int(NT)& y) { Quotient z = x; return z += NT(y); } template CGAL_MEDIUM_INLINE Quotient operator+(const CGAL_int(NT)& x, const Quotient& y) { return y + x; } template CGAL_MEDIUM_INLINE Quotient operator-(const NT& x, const Quotient& y) { Quotient z(x); return z -= y; } template CGAL_MEDIUM_INLINE Quotient operator-(const Quotient& x, const NT& y) { Quotient z = x; return z -= y; } template CGAL_MEDIUM_INLINE Quotient operator-(const Quotient& x, const CGAL_int(NT)& y) { Quotient z = x; return z -= NT(y); } template CGAL_MEDIUM_INLINE Quotient operator-(const CGAL_int(NT)& x, const Quotient& y) { Quotient z = x; return z -= y; } template CGAL_MEDIUM_INLINE Quotient operator*(const NT& x, const Quotient& y) { Quotient z(x); return z *= y; } template CGAL_MEDIUM_INLINE Quotient operator*(const Quotient& x, const NT& y) { Quotient z = x; return z *= y; } template CGAL_MEDIUM_INLINE Quotient operator*(const Quotient& x, const CGAL_int(NT)& y) { Quotient z = x; return z *= NT(y); } template inline Quotient operator*(const CGAL_int(NT)& x, const Quotient& y) { return y*x; } template CGAL_MEDIUM_INLINE Quotient operator/(const NT& x, const Quotient& y) { Quotient z(x) ; return z /= y; } template CGAL_MEDIUM_INLINE Quotient operator/(const Quotient& x, const NT& y) { Quotient z = x; return z /= y; } template CGAL_MEDIUM_INLINE Quotient operator/(const Quotient& x, const CGAL_int(NT)& y) { Quotient z = x; return z /= NT(y); } template CGAL_MEDIUM_INLINE Quotient operator/(const CGAL_int(NT)& x, const Quotient& y) { Quotient z = x; return z /= y; } template CGAL_MEDIUM_INLINE NT quotient_truncation(const Quotient& r) { return (r.num / r.den); } template CGAL_MEDIUM_INLINE bool operator==(const Quotient& x, const Quotient& y) { return x.num * y.den == x.den * y.num; } template CGAL_MEDIUM_INLINE bool operator==(const Quotient& x, const NT& y) { return x.den * y == x.num; } template inline bool operator==(const NT& x, const Quotient& y) { return y == x; } template CGAL_MEDIUM_INLINE bool operator==(const CGAL_int(NT) & x, const Quotient& y) { return y.den * x == y.num; } template inline bool operator==(const Quotient& x, const CGAL_int(NT) & y) { return y == x; } template inline bool operator!=(const Quotient& x, const Quotient& y) { return ! (x == y); } template inline bool operator!=(const Quotient& x, const NT& y) { return ! (x == y); } template inline bool operator!=(const NT& x, const Quotient& y) { return ! (x == y); } template inline bool operator!=(const CGAL_int(NT) & x, const Quotient& y) { return ! (x == y); } template inline bool operator!=(const Quotient& x, const CGAL_int(NT) & y) { return ! (x == y); } template CGAL_MEDIUM_INLINE bool operator<(const Quotient& x, const Quotient& y) { return quotient_cmp(x,y) == SMALLER; } template CGAL_MEDIUM_INLINE bool operator<(const Quotient& x, const NT& y) { return quotient_cmp(x,Quotient(y)) == SMALLER; } template CGAL_MEDIUM_INLINE bool operator<(const NT& x, const Quotient& y) { return quotient_cmp(Quotient(x),y) == SMALLER; } template CGAL_MEDIUM_INLINE bool operator<(const CGAL_int(NT)& x, const Quotient& y) { return quotient_cmp(Quotient(x),y) == SMALLER; } template CGAL_MEDIUM_INLINE bool operator<(const Quotient& x, const CGAL_int(NT)& y) { return quotient_cmp(x,Quotient(y)) == SMALLER; } template inline bool operator>(const Quotient& x, const Quotient& y) { return y < x; } template inline bool operator>(const Quotient& x, const NT& y) { return y < x; } template inline bool operator>(const NT& x, const Quotient& y) { return y < x; } template inline bool operator>(const Quotient& x, const CGAL_int(NT)& y) { return y < x; } template inline bool operator>(const CGAL_int(NT)& x, const Quotient& y) { return y < x; } template inline bool operator<=(const Quotient& x, const Quotient& y) { return ! (y < x); } template inline bool operator<=(const Quotient& x, const NT& y) { return ! (y < x); } template inline bool operator<=(const NT& x, const Quotient& y) { return ! (y < x); } template inline bool operator<=(const Quotient& x, const CGAL_int(NT)& y) { return ! (y < x); } template inline bool operator<=(const CGAL_int(NT)& x, const Quotient& y) { return ! (y < x); } template inline bool operator>=(const Quotient& x, const Quotient& y) { return ! (x < y); } template inline bool operator>=(const Quotient& x, const NT& y) { return ! (x < y); } template inline bool operator>=(const NT& x, const Quotient& y) { return ! (x < y); } template inline bool operator>=(const Quotient& x, const CGAL_int(NT)& y) { return ! (x < y); } template inline bool operator>=(const CGAL_int(NT)& x, const Quotient& y) { return ! (x < y); } template double to_double(const Quotient& q) /* TODO */ { if (q.num == 0 ) return 0; double nd = CGAL_NTS to_double( q.num ); if (q.den == 1 ) return nd; double dd = CGAL_NTS to_double( q.den ); if ( is_finite( q.den ) && is_finite( q.num ) ) return nd/dd; if ( CGAL_NTS abs(q.num) > CGAL_NTS abs(q.den) ) { NT nt_div = q.num / q.den; double divd = CGAL_NTS to_double(nt_div); if ( divd >= CGAL_CLIB_STD::ldexp(1.0,53) ) { return divd; } } if ( CGAL_NTS abs(q.num) < CGAL_NTS abs(q.den) ) { return 1.0 / CGAL_NTS to_double( NT(1) / q ); } return nd/dd; } template std::pair to_interval (const Quotient& z) { Interval_nt<> quot = Interval_nt<>(CGAL_NTS to_interval(z.numerator())) / Interval_nt<>(CGAL_NTS to_interval(z.denominator())); return std::make_pair(quot.inf(), quot.sup()); } template bool is_valid(const Quotient& q) { return is_valid(q.num) && is_valid(q.den); } template bool is_finite(const Quotient& q) { return is_finite(q.num) && is_finite(q.den); } template inline const NT& denominator(const Quotient& q) { return q.den ; } template inline const NT& numerator(const Quotient& q) { return q.num ; } // The min/max are functions are needed since LEDA defines template // min/max functions which clash with std::min/max with ADL. template inline const Quotient& min(const Quotient& p, const Quotient& q) { return std::min(p, q); } template inline const Quotient& max(const Quotient& p, const Quotient& q) { return std::max(p, q); } /* template NT gcd(const NT&, const NT&) { return NT(1); } */ #undef CGAL_int // Rational traits template < class NT > struct Rational_traits< Quotient > { typedef NT RT; RT numerator (const Quotient& r) const { return r.numerator(); } RT denominator (const Quotient& r) const { return r.denominator(); } Quotient make_rational(const RT & n, const RT & d) const { return Quotient(n, d); } }; CGAL_END_NAMESPACE #endif // CGAL_QUOTIENT_H