1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/ossrv/ossrv_pub/boost_apis/boost/rational.hpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,548 @@
1.4 +// Boost rational.hpp header file ------------------------------------------//
1.5 +
1.6 +// (C) Copyright Paul Moore 1999. Permission to copy, use, modify, sell and
1.7 +// distribute this software is granted provided this copyright notice appears
1.8 +// in all copies. This software is provided "as is" without express or
1.9 +// implied warranty, and with no claim as to its suitability for any purpose.
1.10 +
1.11 +// See http://www.boost.org/libs/rational for documentation.
1.12 +
1.13 +// Credits:
1.14 +// Thanks to the boost mailing list in general for useful comments.
1.15 +// Particular contributions included:
1.16 +// Andrew D Jewell, for reminding me to take care to avoid overflow
1.17 +// Ed Brey, for many comments, including picking up on some dreadful typos
1.18 +// Stephen Silver contributed the test suite and comments on user-defined
1.19 +// IntType
1.20 +// Nickolay Mladenov, for the implementation of operator+=
1.21 +
1.22 +// Revision History
1.23 +// 20 Oct 06 Fix operator bool_type for CW 8.3 (Joaquín M López Muñoz)
1.24 +// 18 Oct 06 Use EXPLICIT_TEMPLATE_TYPE helper macros from Boost.Config
1.25 +// (Joaquín M López Muñoz)
1.26 +// 27 Dec 05 Add Boolean conversion operator (Daryle Walker)
1.27 +// 28 Sep 02 Use _left versions of operators from operators.hpp
1.28 +// 05 Jul 01 Recode gcd(), avoiding std::swap (Helmut Zeisel)
1.29 +// 03 Mar 01 Workarounds for Intel C++ 5.0 (David Abrahams)
1.30 +// 05 Feb 01 Update operator>> to tighten up input syntax
1.31 +// 05 Feb 01 Final tidy up of gcd code prior to the new release
1.32 +// 27 Jan 01 Recode abs() without relying on abs(IntType)
1.33 +// 21 Jan 01 Include Nickolay Mladenov's operator+= algorithm,
1.34 +// tidy up a number of areas, use newer features of operators.hpp
1.35 +// (reduces space overhead to zero), add operator!,
1.36 +// introduce explicit mixed-mode arithmetic operations
1.37 +// 12 Jan 01 Include fixes to handle a user-defined IntType better
1.38 +// 19 Nov 00 Throw on divide by zero in operator /= (John (EBo) David)
1.39 +// 23 Jun 00 Incorporate changes from Mark Rodgers for Borland C++
1.40 +// 22 Jun 00 Change _MSC_VER to BOOST_MSVC so other compilers are not
1.41 +// affected (Beman Dawes)
1.42 +// 6 Mar 00 Fix operator-= normalization, #include <string> (Jens Maurer)
1.43 +// 14 Dec 99 Modifications based on comments from the boost list
1.44 +// 09 Dec 99 Initial Version (Paul Moore)
1.45 +
1.46 +#ifndef BOOST_RATIONAL_HPP
1.47 +#define BOOST_RATIONAL_HPP
1.48 +
1.49 +#include <iostream> // for std::istream and std::ostream
1.50 +#include <iomanip> // for std::noskipws
1.51 +#include <stdexcept> // for std::domain_error
1.52 +#include <string> // for std::string implicit constructor
1.53 +#include <boost/operators.hpp> // for boost::addable etc
1.54 +#include <cstdlib> // for std::abs
1.55 +#include <boost/call_traits.hpp> // for boost::call_traits
1.56 +#include <boost/config.hpp> // for BOOST_NO_STDC_NAMESPACE, BOOST_MSVC
1.57 +#include <boost/detail/workaround.hpp> // for BOOST_WORKAROUND
1.58 +
1.59 +namespace boost {
1.60 +
1.61 +// Note: We use n and m as temporaries in this function, so there is no value
1.62 +// in using const IntType& as we would only need to make a copy anyway...
1.63 +template <typename IntType>
1.64 +IntType gcd(IntType n, IntType m)
1.65 +{
1.66 + // Avoid repeated construction
1.67 + IntType zero(0);
1.68 +
1.69 + // This is abs() - given the existence of broken compilers with Koenig
1.70 + // lookup issues and other problems, I code this explicitly. (Remember,
1.71 + // IntType may be a user-defined type).
1.72 + if (n < zero)
1.73 + n = -n;
1.74 + if (m < zero)
1.75 + m = -m;
1.76 +
1.77 + // As n and m are now positive, we can be sure that %= returns a
1.78 + // positive value (the standard guarantees this for built-in types,
1.79 + // and we require it of user-defined types).
1.80 + for(;;) {
1.81 + if(m == zero)
1.82 + return n;
1.83 + n %= m;
1.84 + if(n == zero)
1.85 + return m;
1.86 + m %= n;
1.87 + }
1.88 +}
1.89 +
1.90 +template <typename IntType>
1.91 +IntType lcm(IntType n, IntType m)
1.92 +{
1.93 + // Avoid repeated construction
1.94 + IntType zero(0);
1.95 +
1.96 + if (n == zero || m == zero)
1.97 + return zero;
1.98 +
1.99 + n /= gcd(n, m);
1.100 + n *= m;
1.101 +
1.102 + if (n < zero)
1.103 + n = -n;
1.104 + return n;
1.105 +}
1.106 +
1.107 +class bad_rational : public std::domain_error
1.108 +{
1.109 +public:
1.110 + explicit bad_rational() : std::domain_error("bad rational: zero denominator") {}
1.111 +};
1.112 +
1.113 +template <typename IntType>
1.114 +class rational;
1.115 +
1.116 +template <typename IntType>
1.117 +rational<IntType> abs(const rational<IntType>& r);
1.118 +
1.119 +template <typename IntType>
1.120 +class rational :
1.121 + less_than_comparable < rational<IntType>,
1.122 + equality_comparable < rational<IntType>,
1.123 + less_than_comparable2 < rational<IntType>, IntType,
1.124 + equality_comparable2 < rational<IntType>, IntType,
1.125 + addable < rational<IntType>,
1.126 + subtractable < rational<IntType>,
1.127 + multipliable < rational<IntType>,
1.128 + dividable < rational<IntType>,
1.129 + addable2 < rational<IntType>, IntType,
1.130 + subtractable2 < rational<IntType>, IntType,
1.131 + subtractable2_left < rational<IntType>, IntType,
1.132 + multipliable2 < rational<IntType>, IntType,
1.133 + dividable2 < rational<IntType>, IntType,
1.134 + dividable2_left < rational<IntType>, IntType,
1.135 + incrementable < rational<IntType>,
1.136 + decrementable < rational<IntType>
1.137 + > > > > > > > > > > > > > > > >
1.138 +{
1.139 + typedef typename boost::call_traits<IntType>::param_type param_type;
1.140 +
1.141 + struct helper { IntType parts[2]; };
1.142 + typedef IntType (helper::* bool_type)[2];
1.143 +
1.144 +public:
1.145 + typedef IntType int_type;
1.146 + rational() : num(0), den(1) {}
1.147 + rational(param_type n) : num(n), den(1) {}
1.148 + rational(param_type n, param_type d) : num(n), den(d) { normalize(); }
1.149 +
1.150 + // Default copy constructor and assignment are fine
1.151 +
1.152 + // Add assignment from IntType
1.153 + rational& operator=(param_type n) { return assign(n, 1); }
1.154 +
1.155 + // Assign in place
1.156 + rational& assign(param_type n, param_type d);
1.157 +
1.158 + // Access to representation
1.159 + IntType numerator() const { return num; }
1.160 + IntType denominator() const { return den; }
1.161 +
1.162 + // Arithmetic assignment operators
1.163 + rational& operator+= (const rational& r);
1.164 + rational& operator-= (const rational& r);
1.165 + rational& operator*= (const rational& r);
1.166 + rational& operator/= (const rational& r);
1.167 +
1.168 + rational& operator+= (param_type i);
1.169 + rational& operator-= (param_type i);
1.170 + rational& operator*= (param_type i);
1.171 + rational& operator/= (param_type i);
1.172 +
1.173 + // Increment and decrement
1.174 + const rational& operator++();
1.175 + const rational& operator--();
1.176 +
1.177 + // Operator not
1.178 + bool operator!() const { return !num; }
1.179 +
1.180 + // Boolean conversion
1.181 +
1.182 +#if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.183 + // The "ISO C++ Template Parser" option in CW 8.3 chokes on the
1.184 + // following, hence we selectively disable that option for the
1.185 + // offending memfun.
1.186 +#pragma parse_mfunc_templ off
1.187 +#endif
1.188 +
1.189 + operator bool_type() const { return operator !() ? 0 : &helper::parts; }
1.190 +
1.191 +#if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.192 +#pragma parse_mfunc_templ reset
1.193 +#endif
1.194 +
1.195 + // Comparison operators
1.196 + bool operator< (const rational& r) const;
1.197 + bool operator== (const rational& r) const;
1.198 +
1.199 + bool operator< (param_type i) const;
1.200 + bool operator> (param_type i) const;
1.201 + bool operator== (param_type i) const;
1.202 +
1.203 +private:
1.204 + // Implementation - numerator and denominator (normalized).
1.205 + // Other possibilities - separate whole-part, or sign, fields?
1.206 + IntType num;
1.207 + IntType den;
1.208 +
1.209 + // Representation note: Fractions are kept in normalized form at all
1.210 + // times. normalized form is defined as gcd(num,den) == 1 and den > 0.
1.211 + // In particular, note that the implementation of abs() below relies
1.212 + // on den always being positive.
1.213 + void normalize();
1.214 +};
1.215 +
1.216 +// Assign in place
1.217 +template <typename IntType>
1.218 +inline rational<IntType>& rational<IntType>::assign(param_type n, param_type d)
1.219 +{
1.220 + num = n;
1.221 + den = d;
1.222 + normalize();
1.223 + return *this;
1.224 +}
1.225 +
1.226 +// Unary plus and minus
1.227 +template <typename IntType>
1.228 +inline rational<IntType> operator+ (const rational<IntType>& r)
1.229 +{
1.230 + return r;
1.231 +}
1.232 +
1.233 +template <typename IntType>
1.234 +inline rational<IntType> operator- (const rational<IntType>& r)
1.235 +{
1.236 + return rational<IntType>(-r.numerator(), r.denominator());
1.237 +}
1.238 +
1.239 +// Arithmetic assignment operators
1.240 +template <typename IntType>
1.241 +rational<IntType>& rational<IntType>::operator+= (const rational<IntType>& r)
1.242 +{
1.243 + // This calculation avoids overflow, and minimises the number of expensive
1.244 + // calculations. Thanks to Nickolay Mladenov for this algorithm.
1.245 + //
1.246 + // Proof:
1.247 + // We have to compute a/b + c/d, where gcd(a,b)=1 and gcd(b,c)=1.
1.248 + // Let g = gcd(b,d), and b = b1*g, d=d1*g. Then gcd(b1,d1)=1
1.249 + //
1.250 + // The result is (a*d1 + c*b1) / (b1*d1*g).
1.251 + // Now we have to normalize this ratio.
1.252 + // Let's assume h | gcd((a*d1 + c*b1), (b1*d1*g)), and h > 1
1.253 + // If h | b1 then gcd(h,d1)=1 and hence h|(a*d1+c*b1) => h|a.
1.254 + // But since gcd(a,b1)=1 we have h=1.
1.255 + // Similarly h|d1 leads to h=1.
1.256 + // So we have that h | gcd((a*d1 + c*b1) , (b1*d1*g)) => h|g
1.257 + // Finally we have gcd((a*d1 + c*b1), (b1*d1*g)) = gcd((a*d1 + c*b1), g)
1.258 + // Which proves that instead of normalizing the result, it is better to
1.259 + // divide num and den by gcd((a*d1 + c*b1), g)
1.260 +
1.261 + // Protect against self-modification
1.262 + IntType r_num = r.num;
1.263 + IntType r_den = r.den;
1.264 +
1.265 + IntType g = gcd(den, r_den);
1.266 + den /= g; // = b1 from the calculations above
1.267 + num = num * (r_den / g) + r_num * den;
1.268 + g = gcd(num, g);
1.269 + num /= g;
1.270 + den *= r_den/g;
1.271 +
1.272 + return *this;
1.273 +}
1.274 +
1.275 +template <typename IntType>
1.276 +rational<IntType>& rational<IntType>::operator-= (const rational<IntType>& r)
1.277 +{
1.278 + // Protect against self-modification
1.279 + IntType r_num = r.num;
1.280 + IntType r_den = r.den;
1.281 +
1.282 + // This calculation avoids overflow, and minimises the number of expensive
1.283 + // calculations. It corresponds exactly to the += case above
1.284 + IntType g = gcd(den, r_den);
1.285 + den /= g;
1.286 + num = num * (r_den / g) - r_num * den;
1.287 + g = gcd(num, g);
1.288 + num /= g;
1.289 + den *= r_den/g;
1.290 +
1.291 + return *this;
1.292 +}
1.293 +
1.294 +template <typename IntType>
1.295 +rational<IntType>& rational<IntType>::operator*= (const rational<IntType>& r)
1.296 +{
1.297 + // Protect against self-modification
1.298 + IntType r_num = r.num;
1.299 + IntType r_den = r.den;
1.300 +
1.301 + // Avoid overflow and preserve normalization
1.302 + IntType gcd1 = gcd<IntType>(num, r_den);
1.303 + IntType gcd2 = gcd<IntType>(r_num, den);
1.304 + num = (num/gcd1) * (r_num/gcd2);
1.305 + den = (den/gcd2) * (r_den/gcd1);
1.306 + return *this;
1.307 +}
1.308 +
1.309 +template <typename IntType>
1.310 +rational<IntType>& rational<IntType>::operator/= (const rational<IntType>& r)
1.311 +{
1.312 + // Protect against self-modification
1.313 + IntType r_num = r.num;
1.314 + IntType r_den = r.den;
1.315 +
1.316 + // Avoid repeated construction
1.317 + IntType zero(0);
1.318 +
1.319 + // Trap division by zero
1.320 + if (r_num == zero)
1.321 + throw bad_rational();
1.322 + if (num == zero)
1.323 + return *this;
1.324 +
1.325 + // Avoid overflow and preserve normalization
1.326 + IntType gcd1 = gcd<IntType>(num, r_num);
1.327 + IntType gcd2 = gcd<IntType>(r_den, den);
1.328 + num = (num/gcd1) * (r_den/gcd2);
1.329 + den = (den/gcd2) * (r_num/gcd1);
1.330 +
1.331 + if (den < zero) {
1.332 + num = -num;
1.333 + den = -den;
1.334 + }
1.335 + return *this;
1.336 +}
1.337 +
1.338 +// Mixed-mode operators
1.339 +template <typename IntType>
1.340 +inline rational<IntType>&
1.341 +rational<IntType>::operator+= (param_type i)
1.342 +{
1.343 + return operator+= (rational<IntType>(i));
1.344 +}
1.345 +
1.346 +template <typename IntType>
1.347 +inline rational<IntType>&
1.348 +rational<IntType>::operator-= (param_type i)
1.349 +{
1.350 + return operator-= (rational<IntType>(i));
1.351 +}
1.352 +
1.353 +template <typename IntType>
1.354 +inline rational<IntType>&
1.355 +rational<IntType>::operator*= (param_type i)
1.356 +{
1.357 + return operator*= (rational<IntType>(i));
1.358 +}
1.359 +
1.360 +template <typename IntType>
1.361 +inline rational<IntType>&
1.362 +rational<IntType>::operator/= (param_type i)
1.363 +{
1.364 + return operator/= (rational<IntType>(i));
1.365 +}
1.366 +
1.367 +// Increment and decrement
1.368 +template <typename IntType>
1.369 +inline const rational<IntType>& rational<IntType>::operator++()
1.370 +{
1.371 + // This can never denormalise the fraction
1.372 + num += den;
1.373 + return *this;
1.374 +}
1.375 +
1.376 +template <typename IntType>
1.377 +inline const rational<IntType>& rational<IntType>::operator--()
1.378 +{
1.379 + // This can never denormalise the fraction
1.380 + num -= den;
1.381 + return *this;
1.382 +}
1.383 +
1.384 +// Comparison operators
1.385 +template <typename IntType>
1.386 +bool rational<IntType>::operator< (const rational<IntType>& r) const
1.387 +{
1.388 + // Avoid repeated construction
1.389 + IntType zero(0);
1.390 +
1.391 + // If the two values have different signs, we don't need to do the
1.392 + // expensive calculations below. We take advantage here of the fact
1.393 + // that the denominator is always positive.
1.394 + if (num < zero && r.num >= zero) // -ve < +ve
1.395 + return true;
1.396 + if (num >= zero && r.num <= zero) // +ve or zero is not < -ve or zero
1.397 + return false;
1.398 +
1.399 + // Avoid overflow
1.400 + IntType gcd1 = gcd<IntType>(num, r.num);
1.401 + IntType gcd2 = gcd<IntType>(r.den, den);
1.402 + return (num/gcd1) * (r.den/gcd2) < (den/gcd2) * (r.num/gcd1);
1.403 +}
1.404 +
1.405 +template <typename IntType>
1.406 +bool rational<IntType>::operator< (param_type i) const
1.407 +{
1.408 + // Avoid repeated construction
1.409 + IntType zero(0);
1.410 +
1.411 + // If the two values have different signs, we don't need to do the
1.412 + // expensive calculations below. We take advantage here of the fact
1.413 + // that the denominator is always positive.
1.414 + if (num < zero && i >= zero) // -ve < +ve
1.415 + return true;
1.416 + if (num >= zero && i <= zero) // +ve or zero is not < -ve or zero
1.417 + return false;
1.418 +
1.419 + // Now, use the fact that n/d truncates towards zero as long as n and d
1.420 + // are both positive.
1.421 + // Divide instead of multiplying to avoid overflow issues. Of course,
1.422 + // division may be slower, but accuracy is more important than speed...
1.423 + if (num > zero)
1.424 + return (num/den) < i;
1.425 + else
1.426 + return -i < (-num/den);
1.427 +}
1.428 +
1.429 +template <typename IntType>
1.430 +bool rational<IntType>::operator> (param_type i) const
1.431 +{
1.432 + // Trap equality first
1.433 + if (num == i && den == IntType(1))
1.434 + return false;
1.435 +
1.436 + // Otherwise, we can use operator<
1.437 + return !operator<(i);
1.438 +}
1.439 +
1.440 +template <typename IntType>
1.441 +inline bool rational<IntType>::operator== (const rational<IntType>& r) const
1.442 +{
1.443 + return ((num == r.num) && (den == r.den));
1.444 +}
1.445 +
1.446 +template <typename IntType>
1.447 +inline bool rational<IntType>::operator== (param_type i) const
1.448 +{
1.449 + return ((den == IntType(1)) && (num == i));
1.450 +}
1.451 +
1.452 +// Normalisation
1.453 +template <typename IntType>
1.454 +void rational<IntType>::normalize()
1.455 +{
1.456 + // Avoid repeated construction
1.457 + IntType zero(0);
1.458 +
1.459 + if (den == zero)
1.460 + throw bad_rational();
1.461 +
1.462 + // Handle the case of zero separately, to avoid division by zero
1.463 + if (num == zero) {
1.464 + den = IntType(1);
1.465 + return;
1.466 + }
1.467 +
1.468 + IntType g = gcd<IntType>(num, den);
1.469 +
1.470 + num /= g;
1.471 + den /= g;
1.472 +
1.473 + // Ensure that the denominator is positive
1.474 + if (den < zero) {
1.475 + num = -num;
1.476 + den = -den;
1.477 + }
1.478 +}
1.479 +
1.480 +namespace detail {
1.481 +
1.482 + // A utility class to reset the format flags for an istream at end
1.483 + // of scope, even in case of exceptions
1.484 + struct resetter {
1.485 + resetter(std::istream& is) : is_(is), f_(is.flags()) {}
1.486 + ~resetter() { is_.flags(f_); }
1.487 + std::istream& is_;
1.488 + std::istream::fmtflags f_; // old GNU c++ lib has no ios_base
1.489 + };
1.490 +
1.491 +}
1.492 +
1.493 +// Input and output
1.494 +template <typename IntType>
1.495 +std::istream& operator>> (std::istream& is, rational<IntType>& r)
1.496 +{
1.497 + IntType n = IntType(0), d = IntType(1);
1.498 + char c = 0;
1.499 + detail::resetter sentry(is);
1.500 +
1.501 + is >> n;
1.502 + c = is.get();
1.503 +
1.504 + if (c != '/')
1.505 + is.clear(std::istream::badbit); // old GNU c++ lib has no ios_base
1.506 +
1.507 +#if !defined(__GNUC__) || (defined(__GNUC__) && (__GNUC__ >= 3)) || defined __SGI_STL_PORT
1.508 + is >> std::noskipws;
1.509 +#else
1.510 + is.unsetf(ios::skipws); // compiles, but seems to have no effect.
1.511 +#endif
1.512 + is >> d;
1.513 +
1.514 + if (is)
1.515 + r.assign(n, d);
1.516 +
1.517 + return is;
1.518 +}
1.519 +
1.520 +// Add manipulators for output format?
1.521 +template <typename IntType>
1.522 +std::ostream& operator<< (std::ostream& os, const rational<IntType>& r)
1.523 +{
1.524 + os << r.numerator() << '/' << r.denominator();
1.525 + return os;
1.526 +}
1.527 +
1.528 +// Type conversion
1.529 +template <typename T, typename IntType>
1.530 +inline T rational_cast(
1.531 + const rational<IntType>& src BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(T))
1.532 +{
1.533 + return static_cast<T>(src.numerator())/src.denominator();
1.534 +}
1.535 +
1.536 +// Do not use any abs() defined on IntType - it isn't worth it, given the
1.537 +// difficulties involved (Koenig lookup required, there may not *be* an abs()
1.538 +// defined, etc etc).
1.539 +template <typename IntType>
1.540 +inline rational<IntType> abs(const rational<IntType>& r)
1.541 +{
1.542 + if (r.numerator() >= IntType(0))
1.543 + return r;
1.544 +
1.545 + return rational<IntType>(-r.numerator(), r.denominator());
1.546 +}
1.547 +
1.548 +} // namespace boost
1.549 +
1.550 +#endif // BOOST_RATIONAL_HPP
1.551 +