Swiftdiff options
Diffstat (limited to '3rdParty/Boost/src/boost/random')
14 files changed, 2442 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/random/detail/config.hpp b/3rdParty/Boost/src/boost/random/detail/config.hpp new file mode 100644 index 0000000..d6bc0cc --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/config.hpp @@ -0,0 +1,18 @@ +/* boost random/detail/config.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: config.hpp 52492 2009-04-19 14:55:57Z steven_watanabe $ + */ + +#include <boost/config.hpp> + +#if (defined(BOOST_NO_OPERATORS_IN_NAMESPACE) || defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)) \ + && !defined(BOOST_MSVC) + #define BOOST_RANDOM_NO_STREAM_OPERATORS +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/const_mod.hpp b/3rdParty/Boost/src/boost/random/detail/const_mod.hpp new file mode 100644 index 0000000..e0a8839 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/const_mod.hpp @@ -0,0 +1,363 @@ +/* boost random/detail/const_mod.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: const_mod.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_CONST_MOD_HPP +#define BOOST_RANDOM_CONST_MOD_HPP + +#include <cassert> +#include <boost/static_assert.hpp> +#include <boost/cstdint.hpp> +#include <boost/integer_traits.hpp> +#include <boost/detail/workaround.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { + +/* + * Some random number generators require modular arithmetic. Put + * everything we need here. + * IntType must be an integral type. + */ + +namespace detail { + + template<bool is_signed> + struct do_add + { }; + + template<> + struct do_add<true> + { + template<class IntType> + static IntType add(IntType m, IntType x, IntType c) + { + if (x < m - c) + return x + c; + else + return x - (m-c); + } + }; + + template<> + struct do_add<false> + { + template<class IntType> + static IntType add(IntType, IntType, IntType) + { + // difficult + assert(!"const_mod::add with c too large"); + return 0; + } + }; +} // namespace detail + +#if !(defined(__BORLANDC__) && (__BORLANDC__ == 0x560)) + +template<class IntType, IntType m> +class const_mod +{ +public: + static IntType add(IntType x, IntType c) + { + if(c == 0) + return x; + else if(c <= traits::const_max - m) // i.e. m+c < max + return add_small(x, c); + else + return detail::do_add<traits::is_signed>::add(m, x, c); + } + + static IntType mult(IntType a, IntType x) + { + if(a == 1) + return x; + else if(m <= traits::const_max/a) // i.e. a*m <= max + return mult_small(a, x); + else if(traits::is_signed && (m%a < m/a)) + return mult_schrage(a, x); + else { + // difficult + assert(!"const_mod::mult with a too large"); + return 0; + } + } + + static IntType mult_add(IntType a, IntType x, IntType c) + { + if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max + return (a*x+c) % m; + else + return add(mult(a, x), c); + } + + static IntType invert(IntType x) + { return x == 0 ? 0 : invert_euclidian(x); } + +private: + typedef integer_traits<IntType> traits; + + const_mod(); // don't instantiate + + static IntType add_small(IntType x, IntType c) + { + x += c; + if(x >= m) + x -= m; + return x; + } + + static IntType mult_small(IntType a, IntType x) + { + return a*x % m; + } + + static IntType mult_schrage(IntType a, IntType value) + { + const IntType q = m / a; + const IntType r = m % a; + + assert(r < q); // check that overflow cannot happen + + value = a*(value%q) - r*(value/q); + // An optimizer bug in the SGI MIPSpro 7.3.1.x compiler requires this + // convoluted formulation of the loop (Synge Todo) + for(;;) { + if (value > 0) + break; + value += m; + } + return value; + } + + // invert c in the finite field (mod m) (m must be prime) + static IntType invert_euclidian(IntType c) + { + // we are interested in the gcd factor for c, because this is our inverse + BOOST_STATIC_ASSERT(m > 0); +#if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003)) + assert(boost::integer_traits<IntType>::is_signed); +#elif !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) + BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed); +#endif + assert(c > 0); + IntType l1 = 0; + IntType l2 = 1; + IntType n = c; + IntType p = m; + for(;;) { + IntType q = p / n; + l1 -= q * l2; // this requires a signed IntType! + p -= q * n; + if(p == 0) + return (l2 < 1 ? l2 + m : l2); + IntType q2 = n / p; + l2 -= q2 * l1; + n -= q2 * p; + if(n == 0) + return (l1 < 1 ? l1 + m : l1); + } + } +}; + +// The modulus is exactly the word size: rely on machine overflow handling. +// Due to a GCC bug, we cannot partially specialize in the presence of +// template value parameters. +template<> +class const_mod<unsigned int, 0> +{ + typedef unsigned int IntType; +public: + static IntType add(IntType x, IntType c) { return x+c; } + static IntType mult(IntType a, IntType x) { return a*x; } + static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; + +template<> +class const_mod<unsigned long, 0> +{ + typedef unsigned long IntType; +public: + static IntType add(IntType x, IntType c) { return x+c; } + static IntType mult(IntType a, IntType x) { return a*x; } + static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; + +// the modulus is some power of 2: rely partly on machine overflow handling +// we only specialize for rand48 at the moment +#ifndef BOOST_NO_INT64_T +template<> +class const_mod<uint64_t, uint64_t(1) << 48> +{ + typedef uint64_t IntType; +public: + static IntType add(IntType x, IntType c) { return c == 0 ? x : mod(x+c); } + static IntType mult(IntType a, IntType x) { return mod(a*x); } + static IntType mult_add(IntType a, IntType x, IntType c) + { return mod(a*x+c); } + static IntType mod(IntType x) { return x &= ((uint64_t(1) << 48)-1); } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; +#endif /* !BOOST_NO_INT64_T */ + +#else + +// +// for some reason Borland C++ Builder 6 has problems with +// the full specialisations of const_mod, define a generic version +// instead, the compiler will optimise away the const-if statements: +// + +template<class IntType, IntType m> +class const_mod +{ +public: + static IntType add(IntType x, IntType c) + { + if(0 == m) + { + return x+c; + } + else + { + if(c == 0) + return x; + else if(c <= traits::const_max - m) // i.e. m+c < max + return add_small(x, c); + else + return detail::do_add<traits::is_signed>::add(m, x, c); + } + } + + static IntType mult(IntType a, IntType x) + { + if(x == 0) + { + return a*x; + } + else + { + if(a == 1) + return x; + else if(m <= traits::const_max/a) // i.e. a*m <= max + return mult_small(a, x); + else if(traits::is_signed && (m%a < m/a)) + return mult_schrage(a, x); + else { + // difficult + assert(!"const_mod::mult with a too large"); + return 0; + } + } + } + + static IntType mult_add(IntType a, IntType x, IntType c) + { + if(m == 0) + { + return a*x+c; + } + else + { + if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max + return (a*x+c) % m; + else + return add(mult(a, x), c); + } + } + + static IntType invert(IntType x) + { return x == 0 ? 0 : invert_euclidian(x); } + +private: + typedef integer_traits<IntType> traits; + + const_mod(); // don't instantiate + + static IntType add_small(IntType x, IntType c) + { + x += c; + if(x >= m) + x -= m; + return x; + } + + static IntType mult_small(IntType a, IntType x) + { + return a*x % m; + } + + static IntType mult_schrage(IntType a, IntType value) + { + const IntType q = m / a; + const IntType r = m % a; + + assert(r < q); // check that overflow cannot happen + + value = a*(value%q) - r*(value/q); + while(value <= 0) + value += m; + return value; + } + + // invert c in the finite field (mod m) (m must be prime) + static IntType invert_euclidian(IntType c) + { + // we are interested in the gcd factor for c, because this is our inverse + BOOST_STATIC_ASSERT(m > 0); +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed); +#endif + assert(c > 0); + IntType l1 = 0; + IntType l2 = 1; + IntType n = c; + IntType p = m; + for(;;) { + IntType q = p / n; + l1 -= q * l2; // this requires a signed IntType! + p -= q * n; + if(p == 0) + return (l2 < 1 ? l2 + m : l2); + IntType q2 = n / p; + l2 -= q2 * l1; + n -= q2 * p; + if(n == 0) + return (l1 < 1 ? l1 + m : l1); + } + } +}; + + +#endif + +} // namespace random +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_CONST_MOD_HPP diff --git a/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp b/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp new file mode 100644 index 0000000..f3ade5e --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp @@ -0,0 +1,23 @@ +/* boost random/detail/disable_warnings.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: disable_warnings.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + */ + +// No #include guard. This header is intended to be included multiple times. + +#include <boost/config.hpp> + +#ifdef BOOST_MSVC +#pragma warning(push) +#pragma warning(disable:4512) +#pragma warning(disable:4127) +#pragma warning(disable:4724) +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp b/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp new file mode 100644 index 0000000..26184ea --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp @@ -0,0 +1,18 @@ +/* boost random/detail/enable_warnings.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: enable_warnings.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + */ + +// No #include guard. This header is intended to be included multiple times. + +#ifdef BOOST_MSVC +#pragma warning(pop) +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp b/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp new file mode 100644 index 0000000..468427c --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp @@ -0,0 +1,100 @@ +/* boost random/detail/uniform_int_float.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: pass_through_engine.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP +#define BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP + +#include <boost/config.hpp> +#include <boost/random/detail/ptr_helper.hpp> +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { +namespace detail { + +template<class UniformRandomNumberGenerator> +class pass_through_engine +{ +private: + typedef ptr_helper<UniformRandomNumberGenerator> helper_type; + +public: + typedef typename helper_type::value_type base_type; + typedef typename base_type::result_type result_type; + + explicit pass_through_engine(UniformRandomNumberGenerator rng) + // make argument an rvalue to avoid matching Generator& constructor + : _rng(static_cast<typename helper_type::rvalue_type>(rng)) + { } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (base().min)(); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (base().max)(); } + base_type& base() { return helper_type::ref(_rng); } + const base_type& base() const { return helper_type::ref(_rng); } + + result_type operator()() { return base()(); } + +private: + UniformRandomNumberGenerator _rng; +}; + +#ifndef BOOST_NO_STD_LOCALE + +template<class UniformRandomNumberGenerator, class CharT, class Traits> +std::basic_ostream<CharT,Traits>& +operator<<( + std::basic_ostream<CharT,Traits>& os + , const pass_through_engine<UniformRandomNumberGenerator>& ud + ) +{ + return os << ud.base(); +} + +template<class UniformRandomNumberGenerator, class CharT, class Traits> +std::basic_istream<CharT,Traits>& +operator>>( + std::basic_istream<CharT,Traits>& is + , const pass_through_engine<UniformRandomNumberGenerator>& ud + ) +{ + return is >> ud.base(); +} + +#else // no new streams + +template<class UniformRandomNumberGenerator> +inline std::ostream& +operator<<(std::ostream& os, + const pass_through_engine<UniformRandomNumberGenerator>& ud) +{ + return os << ud.base(); +} + +template<class UniformRandomNumberGenerator> +inline std::istream& +operator>>(std::istream& is, + const pass_through_engine<UniformRandomNumberGenerator>& ud) +{ + return is >> ud.base(); +} + +#endif + +} // namespace detail +} // namespace random +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP + diff --git a/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp b/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp new file mode 100644 index 0000000..3f3fbdd --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp @@ -0,0 +1,94 @@ +/* boost random/detail/ptr_helper.hpp header file + * + * Copyright Jens Maurer 2002 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: ptr_helper.hpp 24096 2004-07-27 03:43:34Z dgregor $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_PTR_HELPER_HPP +#define BOOST_RANDOM_DETAIL_PTR_HELPER_HPP + +#include <boost/config.hpp> + + +namespace boost { +namespace random { +namespace detail { + +// type_traits could help here, but I don't want to depend on type_traits. +template<class T> +struct ptr_helper +{ + typedef T value_type; + typedef T& reference_type; + typedef const T& rvalue_type; + static reference_type ref(T& r) { return r; } + static const T& ref(const T& r) { return r; } +}; + +#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION +template<class T> +struct ptr_helper<T&> +{ + typedef T value_type; + typedef T& reference_type; + typedef T& rvalue_type; + static reference_type ref(T& r) { return r; } + static const T& ref(const T& r) { return r; } +}; + +template<class T> +struct ptr_helper<T*> +{ + typedef T value_type; + typedef T& reference_type; + typedef T* rvalue_type; + static reference_type ref(T * p) { return *p; } + static const T& ref(const T * p) { return *p; } +}; +#endif + +} // namespace detail +} // namespace random +} // namespace boost + +// +// BOOST_RANDOM_PTR_HELPER_SPEC -- +// +// Helper macro for broken compilers defines specializations of +// ptr_helper. +// +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION +# define BOOST_RANDOM_PTR_HELPER_SPEC(T) \ +namespace boost { namespace random { namespace detail { \ +template<> \ +struct ptr_helper<T&> \ +{ \ + typedef T value_type; \ + typedef T& reference_type; \ + typedef T& rvalue_type; \ + static reference_type ref(T& r) { return r; } \ + static const T& ref(const T& r) { return r; } \ +}; \ + \ +template<> \ +struct ptr_helper<T*> \ +{ \ + typedef T value_type; \ + typedef T& reference_type; \ + typedef T* rvalue_type; \ + static reference_type ref(T * p) { return *p; } \ + static const T& ref(const T * p) { return *p; } \ +}; \ +}}} +#else +# define BOOST_RANDOM_PTR_HELPER_SPEC(T) +#endif + +#endif // BOOST_RANDOM_DETAIL_PTR_HELPER_HPP diff --git a/3rdParty/Boost/src/boost/random/detail/seed.hpp b/3rdParty/Boost/src/boost/random/detail/seed.hpp new file mode 100644 index 0000000..48cc17e --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/seed.hpp @@ -0,0 +1,89 @@ +/* boost random/detail/seed.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: seed.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + */ + +#ifndef BOOST_RANDOM_DETAIL_SEED_HPP +#define BOOST_RANDOM_DETAIL_SEED_HPP + +#include <boost/config.hpp> + +// Sun seems to have trouble with the use of SFINAE for the +// templated constructor. So does Borland. +#if !defined(BOOST_NO_SFINAE) && !defined(__SUNPRO_CC) && !defined(__BORLANDC__) + +#include <boost/utility/enable_if.hpp> +#include <boost/type_traits/is_arithmetic.hpp> + +namespace boost { +namespace random { +namespace detail { + +template<class T> +struct disable_seed : boost::disable_if<boost::is_arithmetic<T> > {}; + +template<class Engine, class T> +struct disable_constructor : disable_seed<T> {}; + +template<class Engine> +struct disable_constructor<Engine, Engine> {}; + +#define BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self, Generator, gen) \ + template<class Generator> \ + explicit Self(Generator& gen, typename ::boost::random::detail::disable_constructor<Self, Generator>::type* = 0) + +#define BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self, Generator, gen) \ + template<class Generator> \ + void seed(Generator& gen, typename ::boost::random::detail::disable_seed<Generator>::type* = 0) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self, T, x) \ + explicit Self(const T& x) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self, T, x) \ + void seed(const T& x) + +} +} +} + +#else + +#include <boost/type_traits/is_arithmetic.hpp> +#include <boost/mpl/bool.hpp> + +#define BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self, Generator, gen) \ + Self(Self& other) { *this = other; } \ + Self(const Self& other) { *this = other; } \ + template<class Generator> \ + explicit Self(Generator& gen) { \ + boost_random_constructor_impl(gen, ::boost::is_arithmetic<Generator>());\ + } \ + template<class Generator> \ + void boost_random_constructor_impl(Generator& gen, ::boost::mpl::false_) + +#define BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self, Generator, gen) \ + template<class Generator> \ + void seed(Generator& gen) { \ + boost_random_seed_impl(gen, ::boost::is_arithmetic<Generator>());\ + }\ + template<class Generator>\ + void boost_random_seed_impl(Generator& gen, ::boost::mpl::false_) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self, T, x) \ + explicit Self(const T& x) { boost_random_constructor_impl(x, ::boost::mpl::true_()); }\ + void boost_random_constructor_impl(const T& x, ::boost::mpl::true_) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self, T, x) \ + void seed(const T& x) { boost_random_seed_impl(x, ::boost::mpl::true_()); }\ + void boost_random_seed_impl(const T& x, ::boost::mpl::true_) + +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp b/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp new file mode 100644 index 0000000..3c81cf4 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp @@ -0,0 +1,89 @@ +/* boost random/detail/signed_unsigned_tools.hpp header file + * + * Copyright Jens Maurer 2006 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + */ + +#ifndef BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS +#define BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS + +#include <boost/limits.hpp> +#include <boost/config.hpp> +#include <boost/type_traits/make_unsigned.hpp> + +namespace boost { +namespace random { +namespace detail { + + +/* + * Compute x - y, we know that x >= y, return an unsigned value. + */ + +template<class T, bool sgn = std::numeric_limits<T>::is_signed> +struct subtract { }; + +template<class T> +struct subtract<T, /* signed */ false> +{ + typedef T result_type; + result_type operator()(T x, T y) { return x - y; } +}; + +template<class T> +struct subtract<T, /* signed */ true> +{ + typedef typename make_unsigned<T>::type result_type; + result_type operator()(T x, T y) + { + if (y >= 0) // because x >= y, it follows that x >= 0, too + return result_type(x) - result_type(y); + if (x >= 0) // y < 0 + // avoid the nasty two's complement case for y == min() + return result_type(x) + result_type(-(y+1)) + 1; + // both x and y are negative: no signed overflow + return result_type(x - y); + } +}; + +/* + * Compute x + y, x is unsigned, result fits in type of "y". + */ + +template<class T1, class T2, bool sgn = std::numeric_limits<T2>::is_signed> +struct add { }; + +template<class T1, class T2> +struct add<T1, T2, /* signed */ false> +{ + typedef T2 result_type; + result_type operator()(T1 x, T2 y) { return T2(x) + y; } +}; + +template<class T1, class T2> +struct add<T1, T2, /* signed */ true> +{ + typedef T2 result_type; + result_type operator()(T1 x, T2 y) + { + if (y >= 0) + return T2(x) + y; + // y < 0 + if (x >= T1(-(y+1))) // result >= 0 after subtraction + // avoid the nasty two's complement edge case for y == min() + return T2(x - T1(-(y+1)) - 1); + // abs(x) < abs(y), thus T2 able to represent x + return T2(x) + y; + } +}; + +} // namespace detail +} // namespace random +} // namespace boost + +#endif // BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS + diff --git a/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp b/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp new file mode 100644 index 0000000..4607021 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp @@ -0,0 +1,85 @@ +/* boost random/detail/uniform_int_float.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_int_float.hpp 52492 2009-04-19 14:55:57Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP +#define BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP + +#include <boost/config.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/uniform_01.hpp> + + +namespace boost { +namespace random { +namespace detail { + +template<class UniformRandomNumberGenerator, class IntType = unsigned long> +class uniform_int_float +{ +public: + typedef UniformRandomNumberGenerator base_type; + typedef IntType result_type; + + uniform_int_float(base_type rng, IntType min_arg = 0, IntType max_arg = 0xffffffff) + : _rng(rng), _min(min_arg), _max(max_arg) + { + init(); + } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } + base_type& base() { return _rng.base(); } + const base_type& base() const { return _rng.base(); } + + result_type operator()() + { + return static_cast<IntType>(_rng() * _range) + _min; + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int_float& ud) + { + os << ud._min << " " << ud._max; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_int_float& ud) + { + is >> std::ws >> ud._min >> std::ws >> ud._max; + ud.init(); + return is; + } +#endif + +private: + void init() + { + _range = static_cast<base_result>(_max-_min)+1; + } + + typedef typename base_type::result_type base_result; + uniform_01<base_type> _rng; + result_type _min, _max; + base_result _range; +}; + + +} // namespace detail +} // namespace random +} // namespace boost + +#endif // BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP diff --git a/3rdParty/Boost/src/boost/random/linear_congruential.hpp b/3rdParty/Boost/src/boost/random/linear_congruential.hpp new file mode 100644 index 0000000..351b9c1 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/linear_congruential.hpp @@ -0,0 +1,403 @@ +/* boost random/linear_congruential.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: linear_congruential.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP +#define BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP + +#include <iostream> +#include <cassert> +#include <stdexcept> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/const_mod.hpp> +#include <boost/detail/workaround.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { + +/** + * Instantiations of class template linear_congruential model a + * \pseudo_random_number_generator. Linear congruential pseudo-random + * number generators are described in: + * + * "Mathematical methods in large-scale computing units", D. H. Lehmer, + * Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, + * Harvard University Press, 1951, pp. 141-146 + * + * Let x(n) denote the sequence of numbers returned by some pseudo-random + * number generator. Then for the linear congruential generator, + * x(n+1) := (a * x(n) + c) mod m. Parameters for the generator are + * x(0), a, c, m. The template parameter IntType shall denote an integral + * type. It must be large enough to hold values a, c, and m. The template + * parameters a and c must be smaller than m. + * + * Note: The quality of the generator crucially depends on the choice of + * the parameters. User code should use one of the sensibly parameterized + * generators such as minstd_rand instead. + */ +template<class IntType, IntType a, IntType c, IntType m, IntType val> +class linear_congruential +{ +public: + typedef IntType result_type; +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION + static const bool has_fixed_range = true; + static const result_type min_value = ( c == 0 ? 1 : 0 ); + static const result_type max_value = m-1; +#else + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); +#endif + BOOST_STATIC_CONSTANT(IntType, multiplier = a); + BOOST_STATIC_CONSTANT(IntType, increment = c); + BOOST_STATIC_CONSTANT(IntType, modulus = m); + + // MSVC 6 and possibly others crash when encountering complicated integral + // constant expressions. Avoid the check for now. + // BOOST_STATIC_ASSERT(m == 0 || a < m); + // BOOST_STATIC_ASSERT(m == 0 || c < m); + + /** + * Constructs a linear_congruential generator, seeding it with @c x0. + */ + explicit linear_congruential(IntType x0 = 1) + { + seed(x0); + + // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer); +#endif + } + + /** + * Constructs a @c linear_congruential generator and seeds it + * with values taken from the itrator range [first, last) + * and adjusts first to point to the element after the last one + * used. If there are not enough elements, throws @c std::invalid_argument. + * + * first and last must be input iterators. + */ + template<class It> + linear_congruential(It& first, It last) + { + seed(first, last); + } + + // compiler-generated copy constructor and assignment operator are fine + + /** + * If c mod m is zero and x0 mod m is zero, changes the current value of + * the generator to 1. Otherwise, changes it to x0 mod m. If c is zero, + * distinct seeds in the range [1,m) will leave the generator in distinct + * states. If c is not zero, the range is [0,m). + */ + void seed(IntType x0 = 1) + { + // wrap _x if it doesn't fit in the destination + if(modulus == 0) { + _x = x0; + } else { + _x = x0 % modulus; + } + // handle negative seeds + if(_x <= 0 && _x != 0) { + _x += modulus; + } + // adjust to the correct range + if(increment == 0 && _x == 0) { + _x = 1; + } + assert(_x >= (min)()); + assert(_x <= (max)()); + } + + /** + * seeds a @c linear_congruential generator with values taken + * from the itrator range [first, last) and adjusts @c first to + * point to the element after the last one used. If there are + * not enough elements, throws @c std::invalid_argument. + * + * @c first and @c last must be input iterators. + */ + template<class It> + void seed(It& first, It last) + { + if(first == last) + throw std::invalid_argument("linear_congruential::seed"); + seed(*first++); + } + + /** + * Returns the smallest value that the @c linear_congruential generator + * can produce. + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return c == 0 ? 1 : 0; } + /** + * Returns the largest value that the @c linear_congruential generator + * can produce. + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return modulus-1; } + + /** Returns the next value of the @c linear_congruential generator. */ + IntType operator()() + { + _x = const_mod<IntType, m>::mult_add(a, _x, c); + return _x; + } + + static bool validation(IntType x) { return val == x; } + +#ifdef BOOST_NO_OPERATORS_IN_NAMESPACE + + // Use a member function; Streamable concept not supported. + bool operator==(const linear_congruential& rhs) const + { return _x == rhs._x; } + bool operator!=(const linear_congruential& rhs) const + { return !(*this == rhs); } + +#else + friend bool operator==(const linear_congruential& x, + const linear_congruential& y) + { return x._x == y._x; } + friend bool operator!=(const linear_congruential& x, + const linear_congruential& y) + { return !(x == y); } + +#if !defined(BOOST_RANDOM_NO_STREAM_OPERATORS) && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, + const linear_congruential& lcg) + { + return os << lcg._x; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, + linear_congruential& lcg) + { + return is >> lcg._x; + } + +private: +#endif +#endif + + IntType _x; +}; + +// probably needs the "no native streams" caveat for STLPort +#if !defined(__SGI_STL_PORT) && BOOST_WORKAROUND(__GNUC__, == 2) +template<class IntType, IntType a, IntType c, IntType m, IntType val> +std::ostream& +operator<<(std::ostream& os, + const linear_congruential<IntType,a,c,m,val>& lcg) +{ + return os << lcg._x; +} + +template<class IntType, IntType a, IntType c, IntType m, IntType val> +std::istream& +operator>>(std::istream& is, + linear_congruential<IntType,a,c,m,val>& lcg) +{ + return is >> lcg._x; +} +#elif defined(BOOST_RANDOM_NO_STREAM_OPERATORS) || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) +template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> +std::basic_ostream<CharT,Traits>& +operator<<(std::basic_ostream<CharT,Traits>& os, + const linear_congruential<IntType,a,c,m,val>& lcg) +{ + return os << lcg._x; +} + +template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> +std::basic_istream<CharT,Traits>& +operator>>(std::basic_istream<CharT,Traits>& is, + linear_congruential<IntType,a,c,m,val>& lcg) +{ + return is >> lcg._x; +} +#endif + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const bool linear_congruential<IntType, a, c, m, val>::has_fixed_range; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::min_value; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::max_value; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const IntType linear_congruential<IntType,a,c,m,val>::modulus; +#endif + +} // namespace random + +// validation values from the publications +/** + * The specialization \minstd_rand0 was originally suggested in + * + * @blockquote + * A pseudo-random number generator for the System/360, P.A. Lewis, + * A.S. Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, + * 1969, pp. 136-146 + * @endblockquote + * + * It is examined more closely together with \minstd_rand in + * + * @blockquote + * "Random Number Generators: Good ones are hard to find", + * Stephen K. Park and Keith W. Miller, Communications of + * the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201 + * @endblockquote + */ +typedef random::linear_congruential<int32_t, 16807, 0, 2147483647, + 1043618065> minstd_rand0; + +/** The specialization \minstd_rand was suggested in + * + * @blockquote + * "Random Number Generators: Good ones are hard to find", + * Stephen K. Park and Keith W. Miller, Communications of + * the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201 + * @endblockquote + */ +typedef random::linear_congruential<int32_t, 48271, 0, 2147483647, + 399268537> minstd_rand; + + +#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T) +/** Class @c rand48 models a \pseudo_random_number_generator. It uses + * the linear congruential algorithm with the parameters a = 0x5DEECE66D, + * c = 0xB, m = 2**48. It delivers identical results to the @c lrand48() + * function available on some systems (assuming lcong48 has not been called). + * + * It is only available on systems where @c uint64_t is provided as an + * integral type, so that for example static in-class constants and/or + * enum definitions with large @c uint64_t numbers work. + */ +class rand48 +{ +public: + typedef int32_t result_type; +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION + static const bool has_fixed_range = true; + static const int32_t min_value = 0; + static const int32_t max_value = integer_traits<int32_t>::const_max; +#else + enum { has_fixed_range = false }; +#endif + /** + * Returns the smallest value that the generator can produce + */ + int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; } + /** + * Returns the largest value that the generator can produce + */ + int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); } + +#ifdef BOOST_RANDOM_DOXYGEN + /** + * If T is an integral type smaller than int46_t, constructs + * a \rand48 generator with x(0) := (x0 << 16) | 0x330e. Otherwise + * constructs a \rand48 generator with x(0) = x0. + */ + template<class T> explicit rand48(T x0 = 1); +#else + rand48() : lcf(cnv(static_cast<int32_t>(1))) {} + template<class T> explicit rand48(T x0) : lcf(cnv(x0)) { } +#endif + template<class It> rand48(It& first, It last) : lcf(first, last) { } + + // compiler-generated copy ctor and assignment operator are fine + +#ifdef BOOST_RANDOM_DOXYGEN + /** + * If T is an integral type smaller than int46_t, changes + * the current value x(n) of the generator to (x0 << 16) | 0x330e. + * Otherwise changes the current value x(n) to x0. + */ + template<class T> void seed(T x0 = 1); +#else + void seed() { seed(static_cast<int32_t>(1)); } + template<class T> void seed(T x0) { lcf.seed(cnv(x0)); } +#endif + template<class It> void seed(It& first, It last) { lcf.seed(first,last); } + + /** + * Returns the next value of the generator. + */ + int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); } + // by experiment from lrand48() + static bool validation(int32_t x) { return x == 1993516219; } + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT,class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const rand48& r) + { os << r.lcf; return os; } + + template<class CharT,class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, rand48& r) + { is >> r.lcf; return is; } +#endif + + friend bool operator==(const rand48& x, const rand48& y) + { return x.lcf == y.lcf; } + friend bool operator!=(const rand48& x, const rand48& y) + { return !(x == y); } +#else + // Use a member function; Streamable concept not supported. + bool operator==(const rand48& rhs) const + { return lcf == rhs.lcf; } + bool operator!=(const rand48& rhs) const + { return !(*this == rhs); } +#endif +private: + /// \cond hide_private_members + random::linear_congruential<uint64_t, + uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable + 0xB, uint64_t(1)<<48, /* unknown */ 0> lcf; + template<class T> + static uint64_t cnv(T x) + { + if(sizeof(T) < sizeof(uint64_t)) { + return (static_cast<uint64_t>(x) << 16) | 0x330e; + } else { + return(static_cast<uint64_t>(x)); + } + } + static uint64_t cnv(float x) { return(static_cast<uint64_t>(x)); } + static uint64_t cnv(double x) { return(static_cast<uint64_t>(x)); } + static uint64_t cnv(long double x) { return(static_cast<uint64_t>(x)); } + /// \endcond +}; +#endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */ + +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP diff --git a/3rdParty/Boost/src/boost/random/mersenne_twister.hpp b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp new file mode 100644 index 0000000..fa80aa6 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp @@ -0,0 +1,367 @@ +/* boost random/mersenne_twister.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: mersenne_twister.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP +#define BOOST_RANDOM_MERSENNE_TWISTER_HPP + +#include <iostream> +#include <algorithm> // std::copy +#include <stdexcept> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/integer_traits.hpp> +#include <boost/cstdint.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/ptr_helper.hpp> +#include <boost/random/detail/seed.hpp> + +namespace boost { +namespace random { + +/** + * Instantiations of class template mersenne_twister model a + * \pseudo_random_number_generator. It uses the algorithm described in + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed uniform + * pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura, + * ACM Transactions on Modeling and Computer Simulation: Special Issue on + * Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + * + * @xmlnote + * The boost variant has been implemented from scratch and does not + * derive from or use mt19937.c provided on the above WWW site. However, it + * was verified that both produce identical output. + * @endxmlnote + * + * The seeding from an integer was changed in April 2005 to address a + * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>. + * + * The quality of the generator crucially depends on the choice of the + * parameters. User code should employ one of the sensibly parameterized + * generators such as \mt19937 instead. + * + * The generator requires considerable amounts of memory for the storage of + * its state array. For example, \mt11213b requires about 1408 bytes and + * \mt19937 requires about 2496 bytes. + */ +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +class mersenne_twister +{ +public: + typedef UIntType result_type; + BOOST_STATIC_CONSTANT(int, word_size = w); + BOOST_STATIC_CONSTANT(int, state_size = n); + BOOST_STATIC_CONSTANT(int, shift_size = m); + BOOST_STATIC_CONSTANT(int, mask_bits = r); + BOOST_STATIC_CONSTANT(UIntType, parameter_a = a); + BOOST_STATIC_CONSTANT(int, output_u = u); + BOOST_STATIC_CONSTANT(int, output_s = s); + BOOST_STATIC_CONSTANT(UIntType, output_b = b); + BOOST_STATIC_CONSTANT(int, output_t = t); + BOOST_STATIC_CONSTANT(UIntType, output_c = c); + BOOST_STATIC_CONSTANT(int, output_l = l); + + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); + + /** + * Constructs a @c mersenne_twister and calls @c seed(). + */ + mersenne_twister() { seed(); } + + /** + * Constructs a @c mersenne_twister and calls @c seed(value). + */ + BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value) + { seed(value); } + template<class It> mersenne_twister(It& first, It last) { seed(first,last); } + + /** + * Constructs a mersenne_twister and calls @c seed(gen). + * + * @xmlnote + * The copy constructor will always be preferred over + * the templated constructor. + * @endxmlnote + */ + BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen) + { seed(gen); } + + // compiler-generated copy ctor and assignment operator are fine + + /** Calls @c seed(result_type(5489)). */ + void seed() { seed(UIntType(5489)); } + + /** + * Sets the state x(0) to v mod 2w. Then, iteratively, + * sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2<sup>w</sup> + * for i = 1 .. n-1. x(n) is the first value to be returned by operator(). + */ + BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value) + { + // New seeding algorithm from + // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html + // In the previous versions, MSBs of the seed affected only MSBs of the + // state x[]. + const UIntType mask = ~0u; + x[0] = value & mask; + for (i = 1; i < n; i++) { + // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106 + x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask; + } + } + + /** + * Sets the state of this mersenne_twister to the values + * returned by n invocations of gen. + * + * Complexity: Exactly n invocations of gen. + */ + BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen) + { +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed); +#endif + // I could have used std::generate_n, but it takes "gen" by value + for(int j = 0; j < n; j++) + x[j] = gen(); + i = n; + } + + template<class It> + void seed(It& first, It last) + { + int j; + for(j = 0; j < n && first != last; ++j, ++first) + x[j] = *first; + i = n; + if(first == last && j < n) + throw std::invalid_argument("mersenne_twister::seed"); + } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const + { + // avoid "left shift count >= with of type" warning + result_type res = 0; + for(int j = 0; j < w; ++j) + res |= (1u << j); + return res; + } + + result_type operator()(); + static bool validation(result_type v) { return val == v; } + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const mersenne_twister& mt) + { + for(int j = 0; j < mt.state_size; ++j) + os << mt.compute(j) << " "; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt) + { + for(int j = 0; j < mt.state_size; ++j) + is >> mt.x[j] >> std::ws; + // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template + // value parameter "n" available from the class template scope, so use + // the static constant with the same value + mt.i = mt.state_size; + return is; + } +#endif + + friend bool operator==(const mersenne_twister& x, const mersenne_twister& y) + { + for(int j = 0; j < state_size; ++j) + if(x.compute(j) != y.compute(j)) + return false; + return true; + } + + friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y) + { return !(x == y); } +#else + // Use a member function; Streamable concept not supported. + bool operator==(const mersenne_twister& rhs) const + { + for(int j = 0; j < state_size; ++j) + if(compute(j) != rhs.compute(j)) + return false; + return true; + } + + bool operator!=(const mersenne_twister& rhs) const + { return !(*this == rhs); } +#endif + +private: + /// \cond hide_private_members + // returns x(i-n+index), where index is in 0..n-1 + UIntType compute(unsigned int index) const + { + // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers + return x[ (i + n + index) % (2*n) ]; + } + void twist(int block); + /// \endcond + + // state representation: next output is o(x(i)) + // x[0] ... x[k] x[k+1] ... x[n-1] x[n] ... x[2*n-1] represents + // x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)] + // The goal is to always have x(i-n) ... x(i-1) available for + // operator== and save/restore. + + UIntType x[2*n]; + int i; +}; + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l; +#endif + +/// \cond hide_private_members +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block) +{ + const UIntType upper_mask = (~0u) << r; + const UIntType lower_mask = ~upper_mask; + + if(block == 0) { + for(int j = n; j < 2*n; j++) { + UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask); + x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0); + } + } else if (block == 1) { + // split loop to avoid costly modulo operations + { // extra scope for MSVC brokenness w.r.t. for scope + for(int j = 0; j < n-m; j++) { + UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask); + x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0); + } + } + + for(int j = n-m; j < n-1; j++) { + UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask); + x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0); + } + // last iteration + UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask); + x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0); + i = 0; + } +} +/// \endcond + +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type +mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()() +{ + if(i == n) + twist(0); + else if(i >= 2*n) + twist(1); + // Step 4 + UIntType z = x[i]; + ++i; + z ^= (z >> u); + z ^= ((z << s) & b); + z ^= ((z << t) & c); + z ^= (z >> l); + return z; +} + +} // namespace random + +/** + * The specializations \mt11213b and \mt19937 are from + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed + * uniform pseudo-random number generator", Makoto Matsumoto + * and Takuji Nishimura, ACM Transactions on Modeling and + * Computer Simulation: Special Issue on Uniform Random Number + * Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + */ +typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11, + 7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b; + +/** + * The specializations \mt11213b and \mt19937 are from + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed + * uniform pseudo-random number generator", Makoto Matsumoto + * and Takuji Nishimura, ACM Transactions on Modeling and + * Computer Simulation: Special Issue on Uniform Random Number + * Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + */ +typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11, + 7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937; + +} // namespace boost + +BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937) + +#endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP diff --git a/3rdParty/Boost/src/boost/random/uniform_01.hpp b/3rdParty/Boost/src/boost/random/uniform_01.hpp new file mode 100644 index 0000000..2cdd05f --- /dev/null +++ b/3rdParty/Boost/src/boost/random/uniform_01.hpp @@ -0,0 +1,273 @@ +/* boost random/uniform_01.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_01.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_UNIFORM_01_HPP +#define BOOST_RANDOM_UNIFORM_01_HPP + +#include <iostream> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/pass_through_engine.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { + +#ifdef BOOST_RANDOM_DOXYGEN + +/** + * The distribution function uniform_01 models a \random_distribution. + * On each invocation, it returns a random floating-point value + * uniformly distributed in the range [0..1). + * + * The template parameter RealType shall denote a float-like value type + * with support for binary operators +, -, and /. + * + * Note: The current implementation is buggy, because it may not fill + * all of the mantissa with random bits. I'm unsure how to fill a + * (to-be-invented) @c boost::bigfloat class with random bits efficiently. + * It's probably time for a traits class. + */ +template<class RealType = double> +class uniform_01 +{ +public: + typedef RealType input_type; + typedef RealType result_type; + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const; + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const; + void reset(); + + template<class Engine> + result_type operator()(Engine& eng); + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const new_uniform_01&) + { + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, new_uniform_01&) + { + return is; + } +#endif +}; + +#else + +namespace detail { + +template<class RealType> +class new_uniform_01 +{ +public: + typedef RealType input_type; + typedef RealType result_type; + // compiler-generated copy ctor and copy assignment are fine + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(0); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(1); } + void reset() { } + + template<class Engine> + result_type operator()(Engine& eng) { + for (;;) { + typedef typename Engine::result_type base_result; + result_type factor = result_type(1) / + (result_type((eng.max)()-(eng.min)()) + + result_type(std::numeric_limits<base_result>::is_integer ? 1 : 0)); + result_type result = result_type(eng() - (eng.min)()) * factor; + if (result < result_type(1)) + return result; + } + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const new_uniform_01&) + { + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, new_uniform_01&) + { + return is; + } +#endif +}; + +template<class UniformRandomNumberGenerator, class RealType> +class backward_compatible_uniform_01 +{ + typedef boost::random::detail::ptr_helper<UniformRandomNumberGenerator> traits; + typedef boost::random::detail::pass_through_engine<UniformRandomNumberGenerator> internal_engine_type; +public: + typedef UniformRandomNumberGenerator base_type; + typedef RealType result_type; + + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); + +#if !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300) + BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer); +#endif + + explicit backward_compatible_uniform_01(typename traits::rvalue_type rng) + : _rng(rng), + _factor(result_type(1) / + (result_type((_rng.max)()-(_rng.min)()) + + result_type(std::numeric_limits<base_result>::is_integer ? 1 : 0))) + { + } + // compiler-generated copy ctor and copy assignment are fine + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(0); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(1); } + typename traits::value_type& base() { return _rng.base(); } + const typename traits::value_type& base() const { return _rng.base(); } + void reset() { } + + result_type operator()() { + for (;;) { + result_type result = result_type(_rng() - (_rng.min)()) * _factor; + if (result < result_type(1)) + return result; + } + } + +#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const backward_compatible_uniform_01& u) + { + os << u._rng; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, backward_compatible_uniform_01& u) + { + is >> u._rng; + return is; + } +#endif + +private: + typedef typename internal_engine_type::result_type base_result; + internal_engine_type _rng; + result_type _factor; +}; + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class UniformRandomNumberGenerator, class RealType> +const bool backward_compatible_uniform_01<UniformRandomNumberGenerator, RealType>::has_fixed_range; +#endif + +template<class UniformRandomNumberGenerator> +struct select_uniform_01 +{ + template<class RealType> + struct apply + { + typedef backward_compatible_uniform_01<UniformRandomNumberGenerator, RealType> type; + }; +}; + +template<> +struct select_uniform_01<float> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<float> type; + }; +}; + +template<> +struct select_uniform_01<double> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<double> type; + }; +}; + +template<> +struct select_uniform_01<long double> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<long double> type; + }; +}; + +} + +// Because it is so commonly used: uniform distribution on the real [0..1) +// range. This allows for specializations to avoid a costly int -> float +// conversion plus float multiplication +template<class UniformRandomNumberGenerator = double, class RealType = double> +class uniform_01 + : public detail::select_uniform_01<UniformRandomNumberGenerator>::BOOST_NESTED_TEMPLATE apply<RealType>::type +{ + typedef typename detail::select_uniform_01<UniformRandomNumberGenerator>::BOOST_NESTED_TEMPLATE apply<RealType>::type impl_type; + typedef boost::random::detail::ptr_helper<UniformRandomNumberGenerator> traits; +public: + + uniform_01() {} + + explicit uniform_01(typename traits::rvalue_type rng) + : impl_type(rng) + { + } + +#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_01& u) + { + os << static_cast<const impl_type&>(u); + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_01& u) + { + is >> static_cast<impl_type&>(u); + return is; + } +#endif +}; + +#endif + +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_UNIFORM_01_HPP diff --git a/3rdParty/Boost/src/boost/random/uniform_int.hpp b/3rdParty/Boost/src/boost/random/uniform_int.hpp new file mode 100644 index 0000000..426a9e1 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/uniform_int.hpp @@ -0,0 +1,300 @@ +/* boost random/uniform_int.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_int.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-04-08 added min<max assertion (N. Becker) + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_UNIFORM_INT_HPP +#define BOOST_RANDOM_UNIFORM_INT_HPP + +#include <cassert> +#include <iostream> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/signed_unsigned_tools.hpp> +#include <boost/type_traits/make_unsigned.hpp> + +namespace boost { + +/** + * The distribution function uniform_int models a \random_distribution. + * On each invocation, it returns a random integer value uniformly + * distributed in the set of integer numbers {min, min+1, min+2, ..., max}. + * + * The template parameter IntType shall denote an integer-like value type. + */ +template<class IntType = int> +class uniform_int +{ +public: + typedef IntType input_type; + typedef IntType result_type; + + /// \cond hide_private_members + typedef typename make_unsigned<result_type>::type range_type; + /// \endcond + + /** + * Constructs a uniform_int object. @c min and @c max are + * the parameters of the distribution. + * + * Requires: min <= max + */ + explicit uniform_int(IntType min_arg = 0, IntType max_arg = 9) + : _min(min_arg), _max(max_arg) + { +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope + BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer); +#endif + assert(min_arg <= max_arg); + init(); + } + + /** + * Returns: The "min" parameter of the distribution + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } + /** + * Returns: The "max" parameter of the distribution + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } + void reset() { } + + // can't have member function templates out-of-line due to MSVC bugs + template<class Engine> + result_type operator()(Engine& eng) + { + return generate(eng, _min, _max, _range); + } + + template<class Engine> + result_type operator()(Engine& eng, result_type n) + { + assert(n > 0); + + if (n == 1) + { + return 0; + } + + return generate(eng, 0, n - 1, n - 1); + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud) + { + os << ud._min << " " << ud._max; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud) + { + is >> std::ws >> ud._min >> std::ws >> ud._max; + ud.init(); + return is; + } +#endif + +private: + +#ifdef BOOST_MSVC +#pragma warning(push) +// disable division by zero warning, since we can't +// actually divide by zero. +#pragma warning(disable:4723) +#endif + + /// \cond hide_private_members + template<class Engine> + static result_type generate(Engine& eng, result_type min_value, result_type /*max_value*/, range_type range) + { + typedef typename Engine::result_type base_result; + // ranges are always unsigned + typedef typename make_unsigned<base_result>::type base_unsigned; + const base_result bmin = (eng.min)(); + const base_unsigned brange = + random::detail::subtract<base_result>()((eng.max)(), (eng.min)()); + + if(range == 0) { + return min_value; + } else if(brange == range) { + // this will probably never happen in real life + // basically nothing to do; just take care we don't overflow / underflow + base_unsigned v = random::detail::subtract<base_result>()(eng(), bmin); + return random::detail::add<base_unsigned, result_type>()(v, min_value); + } else if(brange < range) { + // use rejection method to handle things like 0..3 --> 0..4 + for(;;) { + // concatenate several invocations of the base RNG + // take extra care to avoid overflows + + // limit == floor((range+1)/(brange+1)) + // Therefore limit*(brange+1) <= range+1 + range_type limit; + if(range == (std::numeric_limits<range_type>::max)()) { + limit = range/(range_type(brange)+1); + if(range % (range_type(brange)+1) == range_type(brange)) + ++limit; + } else { + limit = (range+1)/(range_type(brange)+1); + } + + // We consider "result" as expressed to base (brange+1): + // For every power of (brange+1), we determine a random factor + range_type result = range_type(0); + range_type mult = range_type(1); + + // loop invariants: + // result < mult + // mult <= range + while(mult <= limit) { + // Postcondition: result <= range, thus no overflow + // + // limit*(brange+1)<=range+1 def. of limit (1) + // eng()-bmin<=brange eng() post. (2) + // and mult<=limit. loop condition (3) + // Therefore mult*(eng()-bmin+1)<=range+1 by (1),(2),(3) (4) + // Therefore mult*(eng()-bmin)+mult<=range+1 rearranging (4) (5) + // result<mult loop invariant (6) + // Therefore result+mult*(eng()-bmin)<range+1 by (5), (6) (7) + // + // Postcondition: result < mult*(brange+1) + // + // result<mult loop invariant (1) + // eng()-bmin<=brange eng() post. (2) + // Therefore result+mult*(eng()-bmin) < + // mult+mult*(eng()-bmin) by (1) (3) + // Therefore result+(eng()-bmin)*mult < + // mult+mult*brange by (2), (3) (4) + // Therefore result+(eng()-bmin)*mult < + // mult*(brange+1) by (4) + result += static_cast<range_type>(random::detail::subtract<base_result>()(eng(), bmin) * mult); + + // equivalent to (mult * (brange+1)) == range+1, but avoids overflow. + if(mult * range_type(brange) == range - mult + 1) { + // The destination range is an integer power of + // the generator's range. + return(result); + } + + // Postcondition: mult <= range + // + // limit*(brange+1)<=range+1 def. of limit (1) + // mult<=limit loop condition (2) + // Therefore mult*(brange+1)<=range+1 by (1), (2) (3) + // mult*(brange+1)!=range+1 preceding if (4) + // Therefore mult*(brange+1)<range+1 by (3), (4) (5) + // + // Postcondition: result < mult + // + // See the second postcondition on the change to result. + mult *= range_type(brange)+range_type(1); + } + // loop postcondition: range/mult < brange+1 + // + // mult > limit loop condition (1) + // Suppose range/mult >= brange+1 Assumption (2) + // range >= mult*(brange+1) by (2) (3) + // range+1 > mult*(brange+1) by (3) (4) + // range+1 > (limit+1)*(brange+1) by (1), (4) (5) + // (range+1)/(brange+1) > limit+1 by (5) (6) + // limit < floor((range+1)/(brange+1)) by (6) (7) + // limit==floor((range+1)/(brange+1)) def. of limit (8) + // not (2) reductio (9) + // + // loop postcondition: (range/mult)*mult+(mult-1) >= range + // + // (range/mult)*mult + range%mult == range identity (1) + // range%mult < mult def. of % (2) + // (range/mult)*mult+mult > range by (1), (2) (3) + // (range/mult)*mult+(mult-1) >= range by (3) (4) + // + // Note that the maximum value of result at this point is (mult-1), + // so after this final step, we generate numbers that can be + // at least as large as range. We have to really careful to avoid + // overflow in this final addition and in the rejection. Anything + // that overflows is larger than range and can thus be rejected. + + // range/mult < brange+1 -> no endless loop + range_type result_increment = uniform_int<range_type>(0, range/mult)(eng); + if((std::numeric_limits<range_type>::max)() / mult < result_increment) { + // The multiplcation would overflow. Reject immediately. + continue; + } + result_increment *= mult; + // unsigned integers are guaranteed to wrap on overflow. + result += result_increment; + if(result < result_increment) { + // The addition overflowed. Reject. + continue; + } + if(result > range) { + // Too big. Reject. + continue; + } + return random::detail::add<range_type, result_type>()(result, min_value); + } + } else { // brange > range + base_unsigned bucket_size; + // it's safe to add 1 to range, as long as we cast it first, + // because we know that it is less than brange. However, + // we do need to be careful not to cause overflow by adding 1 + // to brange. + if(brange == (std::numeric_limits<base_unsigned>::max)()) { + bucket_size = brange / (static_cast<base_unsigned>(range)+1); + if(brange % (static_cast<base_unsigned>(range)+1) == static_cast<base_unsigned>(range)) { + ++bucket_size; + } + } else { + bucket_size = (brange+1) / (static_cast<base_unsigned>(range)+1); + } + for(;;) { + base_unsigned result = + random::detail::subtract<base_result>()(eng(), bmin); + result /= bucket_size; + // result and range are non-negative, and result is possibly larger + // than range, so the cast is safe + if(result <= static_cast<base_unsigned>(range)) + return random::detail::add<base_unsigned, result_type>()(result, min_value); + } + } + } + +#ifdef BOOST_MSVC +#pragma warning(pop) +#endif + + void init() + { + _range = random::detail::subtract<result_type>()(_max, _min); + } + + /// \endcond + + // The result_type may be signed or unsigned, but the _range is always + // unsigned. + result_type _min, _max; + range_type _range; +}; + +} // namespace boost + +#endif // BOOST_RANDOM_UNIFORM_INT_HPP diff --git a/3rdParty/Boost/src/boost/random/variate_generator.hpp b/3rdParty/Boost/src/boost/random/variate_generator.hpp new file mode 100644 index 0000000..930d961 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/variate_generator.hpp @@ -0,0 +1,220 @@ +/* boost random/variate_generator.hpp header file + * + * Copyright Jens Maurer 2002 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: variate_generator.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_RANDOM_GENERATOR_HPP +#define BOOST_RANDOM_RANDOM_GENERATOR_HPP + +#include <boost/config.hpp> + +// implementation details +#include <boost/detail/workaround.hpp> +#include <boost/random/uniform_01.hpp> +#include <boost/random/detail/pass_through_engine.hpp> +#include <boost/random/detail/uniform_int_float.hpp> +#include <boost/random/detail/ptr_helper.hpp> + +// Borland C++ 5.6.0 has problems using its numeric_limits traits as +// template parameters +#if BOOST_WORKAROUND(__BORLANDC__, <= 0x564) +#include <boost/type_traits/is_integral.hpp> +#endif + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { + +/// \cond hide_private_members + +namespace random { +namespace detail { + +template<bool have_int, bool want_int> +struct engine_helper; + +// for consistency, always have two levels of decorations +template<> +struct engine_helper<true, true> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef pass_through_engine<Engine> type; + }; +}; + +template<> +struct engine_helper<false, false> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_01<Engine, DistInputType> type; + }; +}; + +template<> +struct engine_helper<true, false> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_01<Engine, DistInputType> type; + }; +}; + +template<> +struct engine_helper<false, true> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_int_float<Engine, unsigned long> type; + }; +}; + +} // namespace detail +} // namespace random + +///\endcond + +/** + * A random variate generator is used to join a random number + * generator together with a random number distribution. + * Boost.Random provides a vast choice of \generators as well + * as \distributions. + * + * Instantations of class template @c variate_generator model + * a \number_generator. + * + * The argument for the template parameter Engine shall be of + * the form U, U&, or U*, where U models a + * \uniform_random_number_generator. Then, the member + * engine_value_type names U (not the pointer or reference to U). + * + * Specializations of @c variate_generator satisfy the + * requirements of CopyConstructible. They also satisfy the + * requirements of Assignable unless the template parameter + * Engine is of the form U&. + * + * The complexity of all functions specified in this section + * is constant. No function described in this section except + * the constructor throws an exception. + */ +template<class Engine, class Distribution> +class variate_generator +{ +private: + typedef random::detail::pass_through_engine<Engine> decorated_engine; + +public: + typedef typename decorated_engine::base_type engine_value_type; + typedef Engine engine_type; + typedef Distribution distribution_type; + typedef typename Distribution::result_type result_type; + + /** + * Constructs a @c variate_generator object with the associated + * \uniform_random_number_generator eng and the associated + * \random_distribution d. + * + * Throws: If and what the copy constructor of Engine or + * Distribution throws. + */ + variate_generator(Engine e, Distribution d) + : _eng(decorated_engine(e)), _dist(d) { } + + /** + * Returns: distribution()(e) + * + * Notes: The sequence of numbers produced by the + * \uniform_random_number_generator e, s<sub>e</sub>, is + * obtained from the sequence of numbers produced by the + * associated \uniform_random_number_generator eng, s<sub>eng</sub>, + * as follows: Consider the values of @c numeric_limits<T>::is_integer + * for @c T both @c Distribution::input_type and + * @c engine_value_type::result_type. If the values for both types are + * true, then se is identical to s<sub>eng</sub>. Otherwise, if the + * values for both types are false, then the numbers in s<sub>eng</sub> + * are divided by engine().max()-engine().min() to obtain the numbers + * in s<sub>e</sub>. Otherwise, if the value for + * @c engine_value_type::result_type is true and the value for + * @c Distribution::input_type is false, then the numbers in s<sub>eng</sub> + * are divided by engine().max()-engine().min()+1 to obtain the numbers in + * s<sub>e</sub>. Otherwise, the mapping from s<sub>eng</sub> to + * s<sub>e</sub> is implementation-defined. In all cases, an + * implicit conversion from @c engine_value_type::result_type to + * @c Distribution::input_type is performed. If such a conversion does + * not exist, the program is ill-formed. + */ + result_type operator()() { return _dist(_eng); } + /** + * Returns: distribution()(e, value). + * For the semantics of e, see the description of operator()(). + */ + template<class T> + result_type operator()(T value) { return _dist(_eng, value); } + + /** + * Returns: A reference to the associated uniform random number generator. + */ + engine_value_type& engine() { return _eng.base().base(); } + /** + * Returns: A reference to the associated uniform random number generator. + */ + const engine_value_type& engine() const { return _eng.base().base(); } + + /** + * Returns: A reference to the associated random distribution. + */ + distribution_type& distribution() { return _dist; } + /** + * Returns: A reference to the associated random distribution. + */ + const distribution_type& distribution() const { return _dist; } + + /** + * Precondition: distribution().min() is well-formed + * + * Returns: distribution().min() + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().min)(); } + /** + * Precondition: distribution().max() is well-formed + * + * Returns: distribution().max() + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().max)(); } + +private: +#if BOOST_WORKAROUND(__BORLANDC__, <= 0x564) + typedef typename random::detail::engine_helper< + ::boost::is_integral<typename decorated_engine::result_type>::value, + ::boost::is_integral<typename Distribution::input_type>::value + >::BOOST_NESTED_TEMPLATE impl<decorated_engine, typename Distribution::input_type>::type internal_engine_type; +#else + enum { + have_int = std::numeric_limits<typename decorated_engine::result_type>::is_integer, + want_int = std::numeric_limits<typename Distribution::input_type>::is_integer + }; + typedef typename random::detail::engine_helper<have_int, want_int>::BOOST_NESTED_TEMPLATE impl<decorated_engine, typename Distribution::input_type>::type internal_engine_type; +#endif + + internal_engine_type _eng; + distribution_type _dist; +}; + +} // namespace boost + +#include <boost/random/detail/disable_warnings.hpp> + +#endif // BOOST_RANDOM_RANDOM_GENERATOR_HPP |