| // -*- C++ -*- |
| //===--------------------------- random -----------------------------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef _LIBCPP_RANDOM |
| #define _LIBCPP_RANDOM |
| |
| /* |
| random synopsis |
| |
| #include <initializer_list> |
| |
| namespace std |
| { |
| |
| // Engines |
| |
| template <class UIntType, UIntType a, UIntType c, UIntType m> |
| class linear_congruential_engine |
| { |
| public: |
| // types |
| typedef UIntType result_type; |
| |
| // engine characteristics |
| static constexpr result_type multiplier = a; |
| static constexpr result_type increment = c; |
| static constexpr result_type modulus = m; |
| static constexpr result_type min() { return c == 0u ? 1u: 0u;} |
| static constexpr result_type max() { return m - 1u;} |
| static constexpr result_type default_seed = 1u; |
| |
| // constructors and seeding functions |
| explicit linear_congruential_engine(result_type s = default_seed); |
| template<class Sseq> explicit linear_congruential_engine(Sseq& q); |
| void seed(result_type s = default_seed); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long z); |
| }; |
| |
| template <class UIntType, UIntType a, UIntType c, UIntType m> |
| bool |
| operator==(const linear_congruential_engine<UIntType, a, c, m>& x, |
| const linear_congruential_engine<UIntType, a, c, m>& y); |
| |
| template <class UIntType, UIntType a, UIntType c, UIntType m> |
| bool |
| operator!=(const linear_congruential_engine<UIntType, a, c, m>& x, |
| const linear_congruential_engine<UIntType, a, c, m>& y); |
| |
| template <class charT, class traits, |
| class UIntType, UIntType a, UIntType c, UIntType m> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const linear_congruential_engine<UIntType, a, c, m>& x); |
| |
| template <class charT, class traits, |
| class UIntType, UIntType a, UIntType c, UIntType m> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| linear_congruential_engine<UIntType, a, c, m>& x); |
| |
| template <class UIntType, size_t w, size_t n, size_t m, size_t r, |
| UIntType a, size_t u, UIntType d, size_t s, |
| UIntType b, size_t t, UIntType c, size_t l, UIntType f> |
| class mersenne_twister_engine |
| { |
| public: |
| // types |
| typedef UIntType result_type; |
| |
| // engine characteristics |
| static constexpr size_t word_size = w; |
| static constexpr size_t state_size = n; |
| static constexpr size_t shift_size = m; |
| static constexpr size_t mask_bits = r; |
| static constexpr result_type xor_mask = a; |
| static constexpr size_t tempering_u = u; |
| static constexpr result_type tempering_d = d; |
| static constexpr size_t tempering_s = s; |
| static constexpr result_type tempering_b = b; |
| static constexpr size_t tempering_t = t; |
| static constexpr result_type tempering_c = c; |
| static constexpr size_t tempering_l = l; |
| static constexpr result_type initialization_multiplier = f; |
| static constexpr result_type min () { return 0; } |
| static constexpr result_type max() { return 2^w - 1; } |
| static constexpr result_type default_seed = 5489u; |
| |
| // constructors and seeding functions |
| explicit mersenne_twister_engine(result_type value = default_seed); |
| template<class Sseq> explicit mersenne_twister_engine(Sseq& q); |
| void seed(result_type value = default_seed); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long z); |
| }; |
| |
| template <class UIntType, size_t w, size_t n, size_t m, size_t r, |
| UIntType a, size_t u, UIntType d, size_t s, |
| UIntType b, size_t t, UIntType c, size_t l, UIntType f> |
| bool |
| operator==( |
| const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x, |
| const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y); |
| |
| template <class UIntType, size_t w, size_t n, size_t m, size_t r, |
| UIntType a, size_t u, UIntType d, size_t s, |
| UIntType b, size_t t, UIntType c, size_t l, UIntType f> |
| bool |
| operator!=( |
| const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x, |
| const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y); |
| |
| template <class charT, class traits, |
| class UIntType, size_t w, size_t n, size_t m, size_t r, |
| UIntType a, size_t u, UIntType d, size_t s, |
| UIntType b, size_t t, UIntType c, size_t l, UIntType f> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x); |
| |
| template <class charT, class traits, |
| class UIntType, size_t w, size_t n, size_t m, size_t r, |
| UIntType a, size_t u, UIntType d, size_t s, |
| UIntType b, size_t t, UIntType c, size_t l, UIntType f> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x); |
| |
| template<class UIntType, size_t w, size_t s, size_t r> |
| class subtract_with_carry_engine |
| { |
| public: |
| // types |
| typedef UIntType result_type; |
| |
| // engine characteristics |
| static constexpr size_t word_size = w; |
| static constexpr size_t short_lag = s; |
| static constexpr size_t long_lag = r; |
| static constexpr result_type min() { return 0; } |
| static constexpr result_type max() { return m-1; } |
| static constexpr result_type default_seed = 19780503u; |
| |
| // constructors and seeding functions |
| explicit subtract_with_carry_engine(result_type value = default_seed); |
| template<class Sseq> explicit subtract_with_carry_engine(Sseq& q); |
| void seed(result_type value = default_seed); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long z); |
| }; |
| |
| template<class UIntType, size_t w, size_t s, size_t r> |
| bool |
| operator==( |
| const subtract_with_carry_engine<UIntType, w, s, r>& x, |
| const subtract_with_carry_engine<UIntType, w, s, r>& y); |
| |
| template<class UIntType, size_t w, size_t s, size_t r> |
| bool |
| operator!=( |
| const subtract_with_carry_engine<UIntType, w, s, r>& x, |
| const subtract_with_carry_engine<UIntType, w, s, r>& y); |
| |
| template <class charT, class traits, |
| class UIntType, size_t w, size_t s, size_t r> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const subtract_with_carry_engine<UIntType, w, s, r>& x); |
| |
| template <class charT, class traits, |
| class UIntType, size_t w, size_t s, size_t r> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| subtract_with_carry_engine<UIntType, w, s, r>& x); |
| |
| template<class Engine, size_t p, size_t r> |
| class discard_block_engine |
| { |
| public: |
| // types |
| typedef typename Engine::result_type result_type; |
| |
| // engine characteristics |
| static constexpr size_t block_size = p; |
| static constexpr size_t used_block = r; |
| static constexpr result_type min() { return Engine::min(); } |
| static constexpr result_type max() { return Engine::max(); } |
| |
| // constructors and seeding functions |
| discard_block_engine(); |
| explicit discard_block_engine(const Engine& e); |
| explicit discard_block_engine(Engine&& e); |
| explicit discard_block_engine(result_type s); |
| template<class Sseq> explicit discard_block_engine(Sseq& q); |
| void seed(); |
| void seed(result_type s); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long z); |
| |
| // property functions |
| const Engine& base() const; |
| }; |
| |
| template<class Engine, size_t p, size_t r> |
| bool |
| operator==( |
| const discard_block_engine<Engine, p, r>& x, |
| const discard_block_engine<Engine, p, r>& y); |
| |
| template<class Engine, size_t p, size_t r> |
| bool |
| operator!=( |
| const discard_block_engine<Engine, p, r>& x, |
| const discard_block_engine<Engine, p, r>& y); |
| |
| template <class charT, class traits, |
| class Engine, size_t p, size_t r> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const discard_block_engine<Engine, p, r>& x); |
| |
| template <class charT, class traits, |
| class Engine, size_t p, size_t r> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| discard_block_engine<Engine, p, r>& x); |
| |
| template<class Engine, size_t w, class UIntType> |
| class independent_bits_engine |
| { |
| public: |
| // types |
| typedef UIntType result_type; |
| |
| // engine characteristics |
| static constexpr result_type min() { return 0; } |
| static constexpr result_type max() { return 2^w - 1; } |
| |
| // constructors and seeding functions |
| independent_bits_engine(); |
| explicit independent_bits_engine(const Engine& e); |
| explicit independent_bits_engine(Engine&& e); |
| explicit independent_bits_engine(result_type s); |
| template<class Sseq> explicit independent_bits_engine(Sseq& q); |
| void seed(); |
| void seed(result_type s); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); void discard(unsigned long long z); |
| |
| // property functions |
| const Engine& base() const; |
| }; |
| |
| template<class Engine, size_t w, class UIntType> |
| bool |
| operator==( |
| const independent_bits_engine<Engine, w, UIntType>& x, |
| const independent_bits_engine<Engine, w, UIntType>& y); |
| |
| template<class Engine, size_t w, class UIntType> |
| bool |
| operator!=( |
| const independent_bits_engine<Engine, w, UIntType>& x, |
| const independent_bits_engine<Engine, w, UIntType>& y); |
| |
| template <class charT, class traits, |
| class Engine, size_t w, class UIntType> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const independent_bits_engine<Engine, w, UIntType>& x); |
| |
| template <class charT, class traits, |
| class Engine, size_t w, class UIntType> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| independent_bits_engine<Engine, w, UIntType>& x); |
| |
| template<class Engine, size_t k> |
| class shuffle_order_engine |
| { |
| public: |
| // types |
| typedef typename Engine::result_type result_type; |
| |
| // engine characteristics |
| static constexpr size_t table_size = k; |
| static constexpr result_type min() { return Engine::min; } |
| static constexpr result_type max() { return Engine::max; } |
| |
| // constructors and seeding functions |
| shuffle_order_engine(); |
| explicit shuffle_order_engine(const Engine& e); |
| explicit shuffle_order_engine(Engine&& e); |
| explicit shuffle_order_engine(result_type s); |
| template<class Sseq> explicit shuffle_order_engine(Sseq& q); |
| void seed(); |
| void seed(result_type s); |
| template<class Sseq> void seed(Sseq& q); |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long z); |
| |
| // property functions |
| const Engine& base() const; |
| }; |
| |
| template<class Engine, size_t k> |
| bool |
| operator==( |
| const shuffle_order_engine<Engine, k>& x, |
| const shuffle_order_engine<Engine, k>& y); |
| |
| template<class Engine, size_t k> |
| bool |
| operator!=( |
| const shuffle_order_engine<Engine, k>& x, |
| const shuffle_order_engine<Engine, k>& y); |
| |
| template <class charT, class traits, |
| class Engine, size_t k> |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const shuffle_order_engine<Engine, k>& x); |
| |
| template <class charT, class traits, |
| class Engine, size_t k> |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| shuffle_order_engine<Engine, k>& x); |
| |
| typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> |
| minstd_rand0; |
| typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> |
| minstd_rand; |
| typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31, |
| 0x9908b0df, |
| 11, 0xffffffff, |
| 7, 0x9d2c5680, |
| 15, 0xefc60000, |
| 18, 1812433253> mt19937; |
| typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31, |
| 0xb5026f5aa96619e9, |
| 29, 0x5555555555555555, |
| 17, 0x71d67fffeda60000, |
| 37, 0xfff7eee000000000, |
| 43, 6364136223846793005> mt19937_64; |
| typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base; |
| typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base; |
| typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24; |
| typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48; |
| typedef shuffle_order_engine<minstd_rand0, 256> knuth_b; |
| typedef minstd_rand0 default_random_engine; |
| |
| // Generators |
| |
| class random_device |
| { |
| public: |
| // types |
| typedef unsigned int result_type; |
| |
| // generator characteristics |
| static constexpr result_type min() { return numeric_limits<result_type>::min(); } |
| static constexpr result_type max() { return numeric_limits<result_type>::max(); } |
| |
| // constructors |
| explicit random_device(const string& token = "/dev/urandom"); |
| |
| // generating functions |
| result_type operator()(); |
| |
| // property functions |
| double entropy() const; |
| |
| // no copy functions |
| random_device(const random_device& ) = delete; |
| void operator=(const random_device& ) = delete; |
| }; |
| |
| // Utilities |
| |
| class seed_seq |
| { |
| public: |
| // types |
| typedef uint_least32_t result_type; |
| |
| // constructors |
| seed_seq(); |
| template<class T> |
| seed_seq(initializer_list<T> il); |
| template<class InputIterator> |
| seed_seq(InputIterator begin, InputIterator end); |
| |
| // generating functions |
| template<class RandomAccessIterator> |
| void generate(RandomAccessIterator begin, RandomAccessIterator end); |
| |
| // property functions |
| size_t size() const; |
| template<class OutputIterator> |
| void param(OutputIterator dest) const; |
| |
| // no copy functions |
| seed_seq(const seed_seq&) = delete; |
| void operator=(const seed_seq& ) = delete; |
| }; |
| |
| template<class RealType, size_t bits, class URNG> |
| RealType generate_canonical(URNG& g); |
| |
| // Distributions |
| |
| template<class IntType = int> |
| class uniform_int_distribution |
| { |
| public: |
| // types |
| typedef IntType result_type; |
| |
| class param_type |
| { |
| public: |
| typedef uniform_int_distribution distribution_type; |
| |
| explicit param_type(IntType a = 0, |
| IntType b = numeric_limits<IntType>::max()); |
| |
| result_type a() const; |
| result_type b() const; |
| |
| friend bool operator==(const param_type& x, const param_type& y); |
| friend bool operator!=(const param_type& x, const param_type& y); |
| }; |
| |
| // constructors and reset functions |
| explicit uniform_int_distribution(IntType a = 0, |
| IntType b = numeric_limits<IntType>::max()); |
| explicit uniform_int_distribution(const param_type& parm); |
| void reset(); |
| |
| // generating functions |
| template<class URNG> result_type operator()(URNG& g); |
| template<class URNG> result_type operator()(URNG& g, const param_type& parm); |
| |
| // property functions |
| result_type a() const; |
| result_type b() const; |
| |
| param_type param() const; |
| void param(const param_type& parm); |
| |
| result_type min() const; |
| result_type max() const; |
| |
| friend bool operator==(const uniform_int_distribution& x, |
| const uniform_int_distribution& y); |
| friend bool operator!=(const uniform_int_distribution& x, |
| const uniform_int_distribution& y); |
| |
| template <class charT, class traits> |
| friend |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const uniform_int_distribution& x); |
| |
| template <class charT, class traits> |
| friend |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| uniform_int_distribution& x); |
| }; |
| |
| template<class RealType = double> |
| class uniform_real_distribution |
| { |
| public: |
| // types |
| typedef RealType result_type; |
| |
| class param_type |
| { |
| public: |
| typedef uniform_real_distribution distribution_type; |
| |
| explicit param_type(RealType a = 0, |
| RealType b = 1); |
| |
| result_type a() const; |
| result_type b() const; |
| |
| friend bool operator==(const param_type& x, const param_type& y); |
| friend bool operator!=(const param_type& x, const param_type& y); |
| }; |
| |
| // constructors and reset functions |
| explicit uniform_real_distribution(RealType a = 0.0, RealType b = 1.0); |
| explicit uniform_real_distribution(const param_type& parm); |
| void reset(); |
| |
| // generating functions |
| template<class URNG> result_type operator()(URNG& g); |
| template<class URNG> result_type operator()(URNG& g, const param_type& parm); |
| |
| // property functions |
| result_type a() const; |
| result_type b() const; |
| |
| param_type param() const; |
| void param(const param_type& parm); |
| |
| result_type min() const; |
| result_type max() const; |
| |
| friend bool operator==(const uniform_real_distribution& x, |
| const uniform_real_distribution& y); |
| friend bool operator!=(const uniform_real_distribution& x, |
| const uniform_real_distribution& y); |
| |
| template <class charT, class traits> |
| friend |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const uniform_real_distribution& x); |
| |
| template <class charT, class traits> |
| friend |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| uniform_real_distribution& x); |
| }; |
| |
| class bernoulli_distribution |
| { |
| public: |
| // types |
| typedef bool result_type; |
| |
| class param_type |
| { |
| public: |
| typedef bernoulli_distribution distribution_type; |
| |
| explicit param_type(double p = 0.5); |
| |
| double p() const; |
| |
| friend bool operator==(const param_type& x, const param_type& y); |
| friend bool operator!=(const param_type& x, const param_type& y); |
| }; |
| |
| // constructors and reset functions |
| explicit bernoulli_distribution(double p = 0.5); |
| explicit bernoulli_distribution(const param_type& parm); |
| void reset(); |
| |
| // generating functions |
| template<class URNG> result_type operator()(URNG& g); |
| template<class URNG> result_type operator()(URNG& g, const param_type& parm); |
| |
| // property functions |
| double p() const; |
| |
| param_type param() const; |
| void param(const param_type& parm); |
| |
| result_type min() const; |
| result_type max() const; |
| |
| friend bool operator==(const bernoulli_distribution& x, |
| const bernoulli_distribution& y); |
| friend bool operator!=(const bernoulli_distribution& x, |
| const bernoulli_distribution& y); |
| |
| template <class charT, class traits> |
| friend |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const bernoulli_distribution& x); |
| |
| template <class charT, class traits> |
| friend |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| bernoulli_distribution& x); |
| }; |
| |
| template<class IntType = int> |
| class binomial_distribution |
| { |
| public: |
| // types |
| typedef IntType result_type; |
| |
| class param_type |
| { |
| public: |
| typedef binomial_distribution distribution_type; |
| |
| explicit param_type(IntType t = 1, double p = 0.5); |
| |
| IntType t() const; |
| double p() const; |
| |
| friend bool operator==(const param_type& x, const param_type& y); |
| friend bool operator!=(const param_type& x, const param_type& y); |
| }; |
| |
| // constructors and reset functions |
| explicit binomial_distribution(IntType t = 1, double p = 0.5); |
| explicit binomial_distribution(const param_type& parm); |
| void reset(); |
| |
| // generating functions |
| template<class URNG> result_type operator()(URNG& g); |
| template<class URNG> result_type operator()(URNG& g, const param_type& parm); |
| |
| // property functions |
| IntType t() const; |
| double p() const; |
| |
| param_type param() const; |
| void param(const param_type& parm); |
| |
| result_type min() const; |
| result_type max() const; |
| |
| friend bool operator==(const binomial_distribution& x, |
| const binomial_distribution& y); |
| friend bool operator!=(const binomial_distribution& x, |
| const binomial_distribution& y); |
| |
| template <class charT, class traits> |
| friend |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const binomial_distribution& x); |
| |
| template <class charT, class traits> |
| friend |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| binomial_distribution& x); |
| }; |
| |
| template<class IntType = int> |
| class geometric_distribution; |
| |
| template<class IntType = int> |
| class negative_binomial_distribution; |
| |
| template<class IntType = int> |
| class poisson_distribution; |
| |
| template<class RealType = double> |
| class exponential_distribution |
| { |
| public: |
| // types |
| typedef RealType result_type; |
| |
| class param_type |
| { |
| public: |
| typedef exponential_distribution distribution_type; |
| |
| explicit param_type(RealType lambda = 1.0); |
| |
| RealType lambda() const; |
| |
| friend bool operator==(const param_type& x, const param_type& y); |
| friend bool operator!=(const param_type& x, const param_type& y); |
| }; |
| |
| // constructors and reset functions |
| explicit exponential_distribution(RealType lambda = 1.0); |
| explicit exponential_distribution(const param_type& parm); |
| void reset(); |
| |
| // generating functions |
| template<class URNG> result_type operator()(URNG& g); |
| template<class URNG> result_type operator()(URNG& g, const param_type& parm); |
| |
| // property functions |
| RealType lambda() const; |
| |
| param_type param() const; |
| void param(const param_type& parm); |
| |
| result_type min() const; |
| result_type max() const; |
| |
| friend bool operator==(const exponential_distribution& x, |
| const exponential_distribution& y); |
| friend bool operator!=(const exponential_distribution& x, |
| const exponential_distribution& y); |
| |
| template <class charT, class traits> |
| friend |
| basic_ostream<charT, traits>& |
| operator<<(basic_ostream<charT, traits>& os, |
| const exponential_distribution& x); |
| |
| template <class charT, class traits> |
| friend |
| basic_istream<charT, traits>& |
| operator>>(basic_istream<charT, traits>& is, |
| exponential_distribution& x); |
| }; |
| |
| template<class RealType = double> |
| class gamma_distribution; |
| |
| template<class RealType = double> |
| class weibull_distribution; |
| |
| template<class RealType = double> |
| class extreme_value_distribution; |
| |
| template<class RealType = double> |
| class normal_distribution; |
| |
| template<class RealType = double> |
| class lognormal_distribution; |
| |
| template<class RealType = double> |
| class chi_squared_distribution; |
| |
| template<class RealType = double> |
| class cauchy_distribution; |
| |
| template<class RealType = double> |
| class fisher_f_distribution; |
| |
| template<class RealType = double> |
| class student_t_distribution; |
| |
| template<class IntType = int> |
| class discrete_distribution; |
| |
| template<class RealType = double> |
| class piecewise_constant_distribution; |
| |
| template<class RealType = double> |
| class piecewise_linear_distribution; |
| |
| } // std |
| */ |
| |
| #include <__config> |
| #include <cstddef> |
| #include <type_traits> |
| #include <initializer_list> |
| #include <cstdint> |
| #include <limits> |
| #include <algorithm> |
| #include <vector> |
| #include <string> |
| #include <istream> |
| #include <ostream> |
| #include <cmath> |
| |
| #pragma GCC system_header |
| |
| _LIBCPP_BEGIN_NAMESPACE_STD |
| |
| // linear_congruential_engine |
| |
| template <unsigned long long __a, unsigned long long __c, |
| unsigned long long __m, unsigned long long _M, |
| bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_M-__c)/__a)> |
| struct __lce_ta; |
| |
| // 64 |
| |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> |
| struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true> |
| { |
| typedef unsigned long long result_type; |
| static result_type next(result_type __x) |
| { |
| // Schrage's algorithm |
| const result_type __q = __m / __a; |
| const result_type __r = __m % __a; |
| const result_type __t0 = __a * (__x % __q); |
| const result_type __t1 = __r * (__x / __q); |
| __x = __t0 + (__t0 < __t1) * __m - __t1; |
| __x += __c - (__x >= __m - __c) * __m; |
| return __x; |
| } |
| }; |
| |
| template <unsigned long long __a, unsigned long long __m> |
| struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true> |
| { |
| typedef unsigned long long result_type; |
| static result_type next(result_type __x) |
| { |
| // Schrage's algorithm |
| const result_type __q = __m / __a; |
| const result_type __r = __m % __a; |
| const result_type __t0 = __a * (__x % __q); |
| const result_type __t1 = __r * (__x / __q); |
| __x = __t0 + (__t0 < __t1) * __m - __t1; |
| return __x; |
| } |
| }; |
| |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m> |
| struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false> |
| { |
| typedef unsigned long long result_type; |
| static result_type next(result_type __x) |
| { |
| return (__a * __x + __c) % __m; |
| } |
| }; |
| |
| template <unsigned long long __a, unsigned long long __c> |
| struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false> |
| { |
| typedef unsigned long long result_type; |
| static result_type next(result_type __x) |
| { |
| return __a * __x + __c; |
| } |
| }; |
| |
| // 32 |
| |
| template <unsigned long long _A, unsigned long long _C, unsigned long long _M> |
| struct __lce_ta<_A, _C, _M, unsigned(~0), true> |
| { |
| typedef unsigned result_type; |
| static result_type next(result_type __x) |
| { |
| const result_type __a = static_cast<result_type>(_A); |
| const result_type __c = static_cast<result_type>(_C); |
| const result_type __m = static_cast<result_type>(_M); |
| // Schrage's algorithm |
| const result_type __q = __m / __a; |
| const result_type __r = __m % __a; |
| const result_type __t0 = __a * (__x % __q); |
| const result_type __t1 = __r * (__x / __q); |
| __x = __t0 + (__t0 < __t1) * __m - __t1; |
| __x += __c - (__x >= __m - __c) * __m; |
| return __x; |
| } |
| }; |
| |
| template <unsigned long long _A, unsigned long long _M> |
| struct __lce_ta<_A, 0, _M, unsigned(~0), true> |
| { |
| typedef unsigned result_type; |
| static result_type next(result_type __x) |
| { |
| const result_type __a = static_cast<result_type>(_A); |
| const result_type __m = static_cast<result_type>(_M); |
| // Schrage's algorithm |
| const result_type __q = __m / __a; |
| const result_type __r = __m % __a; |
| const result_type __t0 = __a * (__x % __q); |
| const result_type __t1 = __r * (__x / __q); |
| __x = __t0 + (__t0 < __t1) * __m - __t1; |
| return __x; |
| } |
| }; |
| |
| template <unsigned long long _A, unsigned long long _C, unsigned long long _M> |
| struct __lce_ta<_A, _C, _M, unsigned(~0), false> |
| { |
| typedef unsigned result_type; |
| static result_type next(result_type __x) |
| { |
| const result_type __a = static_cast<result_type>(_A); |
| const result_type __c = static_cast<result_type>(_C); |
| const result_type __m = static_cast<result_type>(_M); |
| return (__a * __x + __c) % __m; |
| } |
| }; |
| |
| template <unsigned long long _A, unsigned long long _C> |
| struct __lce_ta<_A, _C, 0, unsigned(~0), false> |
| { |
| typedef unsigned result_type; |
| static result_type next(result_type __x) |
| { |
| const result_type __a = static_cast<result_type>(_A); |
| const result_type __c = static_cast<result_type>(_C); |
| return __a * __x + __c; |
| } |
| }; |
| |
| // 16 |
| |
| template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b> |
| struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b> |
| { |
| typedef unsigned short result_type; |
| static result_type next(result_type __x) |
| { |
| return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x)); |
| } |
| }; |
| |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| class linear_congruential_engine; |
| |
| template <class _CharT, class _Traits, |
| class _U, _U _A, _U _C, _U _N> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const linear_congruential_engine<_U, _A, _C, _N>&); |
| |
| template <class _CharT, class _Traits, |
| class _U, _U _A, _U _C, _U _N> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| linear_congruential_engine<_U, _A, _C, _N>& __x); |
| |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| class linear_congruential_engine |
| { |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| result_type __x_; |
| |
| static const result_type _M = result_type(~0); |
| |
| static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters"); |
| static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters"); |
| public: |
| static const result_type _Min = __c == 0u ? 1u: 0u; |
| static const result_type _Max = __m - 1u; |
| static_assert(_Min < _Max, "linear_congruential_engine invalid parameters"); |
| |
| // engine characteristics |
| static const/*expr*/ result_type multiplier = __a; |
| static const/*expr*/ result_type increment = __c; |
| static const/*expr*/ result_type modulus = __m; |
| static const/*expr*/ result_type min() {return _Min;} |
| static const/*expr*/ result_type max() {return _Max;} |
| static const/*expr*/ result_type default_seed = 1u; |
| |
| // constructors and seeding functions |
| explicit linear_congruential_engine(result_type __s = default_seed) |
| {seed(__s);} |
| template<class _Sseq> explicit linear_congruential_engine(_Sseq& __q) |
| {seed(__q);} |
| void seed(result_type __s = default_seed) |
| {seed(integral_constant<bool, __m == 0>(), |
| integral_constant<bool, __c == 0>(), __s);} |
| template<class _Sseq> |
| typename enable_if |
| < |
| !is_convertible<_Sseq, result_type>::value, |
| void |
| >::type |
| seed(_Sseq& __q) |
| {__seed(__q, integral_constant<unsigned, |
| 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32 |
| : (__m-1) / 0x100000000ull)>());} |
| |
| // generating functions |
| result_type operator()() |
| {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _M>::next(__x_));} |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| friend bool operator==(const linear_congruential_engine& __x, |
| const linear_congruential_engine& __y) |
| {return __x.__x_ == __y.__x_;} |
| friend bool operator!=(const linear_congruential_engine& __x, |
| const linear_congruential_engine& __y) |
| {return !(__x == __y);} |
| |
| private: |
| |
| void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;} |
| void seed(true_type, false_type, result_type __s) {__x_ = __s;} |
| void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ? |
| 1 : __s % __m;} |
| void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;} |
| |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 1>); |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 2>); |
| |
| template <class _CharT, class _Traits, |
| class _U, _U _A, _U _C, _U _N> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const linear_congruential_engine<_U, _A, _C, _N>&); |
| |
| template <class _CharT, class _Traits, |
| class _U, _U _A, _U _C, _U _N> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| linear_congruential_engine<_U, _A, _C, _N>& __x); |
| }; |
| |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| template<class _Sseq> |
| void |
| linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, |
| integral_constant<unsigned, 1>) |
| { |
| const unsigned __k = 1; |
| uint32_t __ar[__k+3]; |
| __q.generate(__ar, __ar + __k + 3); |
| result_type __s = static_cast<result_type>(__ar[3] % __m); |
| __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; |
| } |
| |
| template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| template<class _Sseq> |
| void |
| linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q, |
| integral_constant<unsigned, 2>) |
| { |
| const unsigned __k = 2; |
| uint32_t __ar[__k+3]; |
| __q.generate(__ar, __ar + __k + 3); |
| result_type __s = static_cast<result_type>((__ar[3] + |
| (uint64_t)__ar[4] << 32) % __m); |
| __x_ = __c == 0 && __s == 0 ? result_type(1) : __s; |
| } |
| |
| template <class _CharT, class _Traits> |
| class __save_flags |
| { |
| typedef basic_ios<_CharT, _Traits> __stream_type; |
| typedef typename __stream_type::fmtflags fmtflags; |
| |
| __stream_type& __stream_; |
| fmtflags __fmtflags_; |
| _CharT __fill_; |
| |
| __save_flags(const __save_flags&); |
| __save_flags& operator=(const __save_flags&); |
| public: |
| explicit __save_flags(__stream_type& __stream) |
| : __stream_(__stream), |
| __fmtflags_(__stream.flags()), |
| __fill_(__stream.fill()) |
| {} |
| ~__save_flags() |
| { |
| __stream_.flags(__fmtflags_); |
| __stream_.fill(__fill_); |
| } |
| }; |
| |
| template <class _CharT, class _Traits, |
| class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| inline |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const linear_congruential_engine<_UIntType, __a, __c, __m>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| __os.fill(__os.widen(' ')); |
| return __os << __x.__x_; |
| } |
| |
| template <class _CharT, class _Traits, |
| class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| linear_congruential_engine<_UIntType, __a, __c, __m>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| _UIntType __t; |
| __is >> __t; |
| if (!__is.fail()) |
| __x.__x_ = __t; |
| return __is; |
| } |
| |
| typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647> |
| minstd_rand0; |
| typedef minstd_rand0 default_random_engine; |
| typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647> |
| minstd_rand; |
| // mersenne_twister_engine |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| class mersenne_twister_engine; |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| bool |
| operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y); |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| bool |
| operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x); |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| class mersenne_twister_engine |
| { |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| result_type __x_[__n]; |
| size_t __i_; |
| |
| static_assert( 0 < __m, "mersenne_twister_engine invalid parameters"); |
| static_assert(__m <= __n, "mersenne_twister_engine invalid parameters"); |
| static const result_type _Dt = numeric_limits<result_type>::digits; |
| static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters"); |
| static_assert( 2 <= __w, "mersenne_twister_engine invalid parameters"); |
| static_assert(__r <= __w, "mersenne_twister_engine invalid parameters"); |
| static_assert(__u <= __w, "mersenne_twister_engine invalid parameters"); |
| static_assert(__s <= __w, "mersenne_twister_engine invalid parameters"); |
| static_assert(__t <= __w, "mersenne_twister_engine invalid parameters"); |
| static_assert(__l <= __w, "mersenne_twister_engine invalid parameters"); |
| public: |
| static const result_type _Min = 0; |
| static const result_type _Max = __w == _Dt ? result_type(~0) : |
| (result_type(1) << __w) - result_type(1); |
| static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters"); |
| static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters"); |
| static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters"); |
| static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters"); |
| static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters"); |
| static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters"); |
| |
| // engine characteristics |
| static const/*expr*/ size_t word_size = __w; |
| static const/*expr*/ size_t state_size = __n; |
| static const/*expr*/ size_t shift_size = __m; |
| static const/*expr*/ size_t mask_bits = __r; |
| static const/*expr*/ result_type xor_mask = __a; |
| static const/*expr*/ size_t tempering_u = __u; |
| static const/*expr*/ result_type tempering_d = __d; |
| static const/*expr*/ size_t tempering_s = __s; |
| static const/*expr*/ result_type tempering_b = __b; |
| static const/*expr*/ size_t tempering_t = __t; |
| static const/*expr*/ result_type tempering_c = __c; |
| static const/*expr*/ size_t tempering_l = __l; |
| static const/*expr*/ result_type initialization_multiplier = __f; |
| static const/*expr*/ result_type min() { return _Min; } |
| static const/*expr*/ result_type max() { return _Max; } |
| static const/*expr*/ result_type default_seed = 5489u; |
| |
| // constructors and seeding functions |
| explicit mersenne_twister_engine(result_type __sd = default_seed) |
| {seed(__sd);} |
| template<class _Sseq> explicit mersenne_twister_engine(_Sseq& __q) |
| {seed(__q);} |
| void seed(result_type __sd = default_seed); |
| template<class _Sseq> |
| typename enable_if |
| < |
| !is_convertible<_Sseq, result_type>::value, |
| void |
| >::type |
| seed(_Sseq& __q) |
| {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());} |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| friend |
| bool |
| operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y); |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| friend |
| bool |
| operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x); |
| private: |
| |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 1>); |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 2>); |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| __count < __w, |
| result_type |
| >::type |
| __lshift(result_type __x) {return (__x << __count) & _Max;} |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| (__count >= __w), |
| result_type |
| >::type |
| __lshift(result_type __x) {return result_type(0);} |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| __count < _Dt, |
| result_type |
| >::type |
| __rshift(result_type __x) {return __x >> __count;} |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| (__count >= _Dt), |
| result_type |
| >::type |
| __rshift(result_type __x) {return result_type(0);} |
| }; |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| void |
| mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, |
| __t, __c, __l, __f>::seed(result_type __sd) |
| { // __w >= 2 |
| __x_[0] = __sd & _Max; |
| for (size_t __i = 1; __i < __n; ++__i) |
| __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max; |
| __i_ = 0; |
| } |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| template<class _Sseq> |
| void |
| mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, |
| __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>) |
| { |
| const unsigned __k = 1; |
| uint32_t __ar[__n * __k]; |
| __q.generate(__ar, __ar + __n * __k); |
| for (size_t __i = 0; __i < __n; ++__i) |
| __x_[__i] = static_cast<result_type>(__ar[__i] & _Max); |
| const result_type __mask = __r == _Dt ? result_type(~0) : |
| (result_type(1) << __r) - result_type(1); |
| __i_ = 0; |
| if ((__x_[0] & ~__mask) == 0) |
| { |
| for (size_t __i = 1; __i < __n; ++__i) |
| if (__x_[__i] != 0) |
| return; |
| __x_[0] = _Max; |
| } |
| } |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| template<class _Sseq> |
| void |
| mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, |
| __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>) |
| { |
| const unsigned __k = 2; |
| uint32_t __ar[__n * __k]; |
| __q.generate(__ar, __ar + __n * __k); |
| for (size_t __i = 0; __i < __n; ++__i) |
| __x_[__i] = static_cast<result_type>( |
| (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max); |
| const result_type __mask = __r == _Dt ? result_type(~0) : |
| (result_type(1) << __r) - result_type(1); |
| __i_ = 0; |
| if ((__x_[0] & ~__mask) == 0) |
| { |
| for (size_t __i = 1; __i < __n; ++__i) |
| if (__x_[__i] != 0) |
| return; |
| __x_[0] = _Max; |
| } |
| } |
| |
| template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r, |
| _UIntType __a, size_t __u, _UIntType __d, size_t __s, |
| _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f> |
| _UIntType |
| mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, |
| __t, __c, __l, __f>::operator()() |
| { |
| const size_t __j = (__i_ + 1) % __n; |
| const result_type __mask = __r == _Dt ? result_type(~0) : |
| (result_type(1) << __r) - result_type(1); |
| const result_type _Y = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask); |
| const size_t __k = (__i_ + __m) % __n; |
| __x_[__i_] = __x_[__k] ^ __rshift<1>(_Y) ^ (__a * (_Y & 1)); |
| result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d); |
| __i_ = __j; |
| __z ^= __lshift<__s>(__z) & __b; |
| __z ^= __lshift<__t>(__z) & __c; |
| return __z ^ __rshift<__l>(__z); |
| } |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| bool |
| operator==(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y) |
| { |
| if (__x.__i_ == __y.__i_) |
| return _STD::equal(__x.__x_, __x.__x_ + _N, __y.__x_); |
| if (__x.__i_ == 0 || __y.__i_ == 0) |
| { |
| size_t __j = _STD::min(_N - __x.__i_, _N - __y.__i_); |
| if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, |
| __y.__x_ + __y.__i_)) |
| return false; |
| if (__x.__i_ == 0) |
| return _STD::equal(__x.__x_ + __j, __x.__x_ + _N, __y.__x_); |
| return _STD::equal(__x.__x_, __x.__x_ + (_N - __j), __y.__x_ + __j); |
| } |
| if (__x.__i_ < __y.__i_) |
| { |
| size_t __j = _N - __y.__i_; |
| if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), |
| __y.__x_ + __y.__i_)) |
| return false; |
| if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _N, |
| __y.__x_)) |
| return false; |
| return _STD::equal(__x.__x_, __x.__x_ + __x.__i_, |
| __y.__x_ + (_N - (__x.__i_ + __j))); |
| } |
| size_t __j = _N - __x.__i_; |
| if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), |
| __x.__x_ + __x.__i_)) |
| return false; |
| if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _N, |
| __x.__x_)) |
| return false; |
| return _STD::equal(__y.__x_, __y.__x_ + __y.__i_, |
| __x.__x_ + (_N - (__y.__i_ + __j))); |
| } |
| |
| template <class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| inline |
| bool |
| operator!=(const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| __os << __x.__x_[__x.__i_]; |
| for (size_t __j = __x.__i_ + 1; __j < _N; ++__j) |
| __os << __sp << __x.__x_[__j]; |
| for (size_t __j = 0; __j < __x.__i_; ++__j) |
| __os << __sp << __x.__x_[__j]; |
| return __os; |
| } |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _N, size_t _M, size_t _R, |
| _UI _A, size_t _U, _UI _D, size_t _S, |
| _UI _B, size_t _T, _UI _C, size_t _L, _UI _F> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| mersenne_twister_engine<_UI, _W, _N, _M, _R, _A, _U, _D, _S, |
| _B, _T, _C, _L, _F>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| _UI __t[_N]; |
| for (size_t __i = 0; __i < _N; ++__i) |
| __is >> __t[__i]; |
| if (!__is.fail()) |
| { |
| for (size_t __i = 0; __i < _N; ++__i) |
| __x.__x_[__i] = __t[__i]; |
| __x.__i_ = 0; |
| } |
| return __is; |
| } |
| |
| typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31, |
| 0x9908b0df, 11, 0xffffffff, |
| 7, 0x9d2c5680, |
| 15, 0xefc60000, |
| 18, 1812433253> mt19937; |
| typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31, |
| 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL, |
| 17, 0x71d67fffeda60000ULL, |
| 37, 0xfff7eee000000000ULL, |
| 43, 6364136223846793005ULL> mt19937_64; |
| |
| // subtract_with_carry_engine |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| class subtract_with_carry_engine; |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| bool |
| operator==( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y); |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| bool |
| operator!=( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| subtract_with_carry_engine<_UI, _W, _S, _R>& __x); |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| class subtract_with_carry_engine |
| { |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| result_type __x_[__r]; |
| result_type __c_; |
| size_t __i_; |
| |
| static const result_type _Dt = numeric_limits<result_type>::digits; |
| static_assert( 0 < __w, "subtract_with_carry_engine invalid parameters"); |
| static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters"); |
| static_assert( 0 < __s, "subtract_with_carry_engine invalid parameters"); |
| static_assert(__s < __r, "subtract_with_carry_engine invalid parameters"); |
| public: |
| static const result_type _Min = 0; |
| static const result_type _Max = __w == _Dt ? result_type(~0) : |
| (result_type(1) << __w) - result_type(1); |
| static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters"); |
| |
| // engine characteristics |
| static const/*expr*/ size_t word_size = __w; |
| static const/*expr*/ size_t short_lag = __s; |
| static const/*expr*/ size_t long_lag = __r; |
| static const/*expr*/ result_type min() { return _Min; } |
| static const/*expr*/ result_type max() { return _Max; } |
| static const/*expr*/ result_type default_seed = 19780503u; |
| |
| // constructors and seeding functions |
| explicit subtract_with_carry_engine(result_type __sd = default_seed) |
| {seed(__sd);} |
| template<class _Sseq> explicit subtract_with_carry_engine(_Sseq& __q) |
| {seed(__q);} |
| void seed(result_type __sd = default_seed) |
| {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());} |
| template<class _Sseq> |
| typename enable_if |
| < |
| !is_convertible<_Sseq, result_type>::value, |
| void |
| >::type |
| seed(_Sseq& __q) |
| {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());} |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| friend |
| bool |
| operator==( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y); |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| friend |
| bool |
| operator!=( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| subtract_with_carry_engine<_UI, _W, _S, _R>& __x); |
| |
| private: |
| |
| void seed(result_type __sd, integral_constant<unsigned, 1>); |
| void seed(result_type __sd, integral_constant<unsigned, 2>); |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 1>); |
| template<class _Sseq> |
| void __seed(_Sseq& __q, integral_constant<unsigned, 2>); |
| }; |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| void |
| subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, |
| integral_constant<unsigned, 1>) |
| { |
| linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> |
| __e(__sd == 0u ? default_seed : __sd); |
| for (size_t __i = 0; __i < __r; ++__i) |
| __x_[__i] = static_cast<result_type>(__e() & _Max); |
| __c_ = __x_[__r-1] == 0; |
| __i_ = 0; |
| } |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| void |
| subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd, |
| integral_constant<unsigned, 2>) |
| { |
| linear_congruential_engine<result_type, 40014u, 0u, 2147483563u> |
| __e(__sd == 0u ? default_seed : __sd); |
| for (size_t __i = 0; __i < __r; ++__i) |
| __x_[__i] = static_cast<result_type>( |
| (__e() + ((uint64_t)__e() << 32)) & _Max); |
| __c_ = __x_[__r-1] == 0; |
| __i_ = 0; |
| } |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| template<class _Sseq> |
| void |
| subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, |
| integral_constant<unsigned, 1>) |
| { |
| const unsigned __k = 1; |
| uint32_t __ar[__r * __k]; |
| __q.generate(__ar, __ar + __r * __k); |
| for (size_t __i = 0; __i < __r; ++__i) |
| __x_[__i] = static_cast<result_type>(__ar[__i] & _Max); |
| __c_ = __x_[__r-1] == 0; |
| __i_ = 0; |
| } |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| template<class _Sseq> |
| void |
| subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q, |
| integral_constant<unsigned, 2>) |
| { |
| const unsigned __k = 2; |
| uint32_t __ar[__r * __k]; |
| __q.generate(__ar, __ar + __r * __k); |
| for (size_t __i = 0; __i < __r; ++__i) |
| __x_[__i] = static_cast<result_type>( |
| (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max); |
| __c_ = __x_[__r-1] == 0; |
| __i_ = 0; |
| } |
| |
| template<class _UIntType, size_t __w, size_t __s, size_t __r> |
| _UIntType |
| subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()() |
| { |
| const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r]; |
| result_type& __xr = __x_[__i_]; |
| result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1; |
| __xr = (__xs - __xr - __c_) & _Max; |
| __c_ = __new_c; |
| __i_ = (__i_ + 1) % __r; |
| return __xr; |
| } |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| bool |
| operator==( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y) |
| { |
| if (__x.__c_ != __y.__c_) |
| return false; |
| if (__x.__i_ == __y.__i_) |
| return _STD::equal(__x.__x_, __x.__x_ + _R, __y.__x_); |
| if (__x.__i_ == 0 || __y.__i_ == 0) |
| { |
| size_t __j = _STD::min(_R - __x.__i_, _R - __y.__i_); |
| if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j, |
| __y.__x_ + __y.__i_)) |
| return false; |
| if (__x.__i_ == 0) |
| return _STD::equal(__x.__x_ + __j, __x.__x_ + _R, __y.__x_); |
| return _STD::equal(__x.__x_, __x.__x_ + (_R - __j), __y.__x_ + __j); |
| } |
| if (__x.__i_ < __y.__i_) |
| { |
| size_t __j = _R - __y.__i_; |
| if (!_STD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j), |
| __y.__x_ + __y.__i_)) |
| return false; |
| if (!_STD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _R, |
| __y.__x_)) |
| return false; |
| return _STD::equal(__x.__x_, __x.__x_ + __x.__i_, |
| __y.__x_ + (_R - (__x.__i_ + __j))); |
| } |
| size_t __j = _R - __x.__i_; |
| if (!_STD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j), |
| __x.__x_ + __x.__i_)) |
| return false; |
| if (!_STD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _R, |
| __x.__x_)) |
| return false; |
| return _STD::equal(__y.__x_, __y.__x_ + __y.__i_, |
| __x.__x_ + (_R - (__y.__i_ + __j))); |
| } |
| |
| template<class _UI, size_t _W, size_t _S, size_t _R> |
| inline |
| bool |
| operator!=( |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const subtract_with_carry_engine<_UI, _W, _S, _R>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| __os << __x.__x_[__x.__i_]; |
| for (size_t __j = __x.__i_ + 1; __j < _R; ++__j) |
| __os << __sp << __x.__x_[__j]; |
| for (size_t __j = 0; __j < __x.__i_; ++__j) |
| __os << __sp << __x.__x_[__j]; |
| __os << __sp << __x.__c_; |
| return __os; |
| } |
| |
| template <class _CharT, class _Traits, |
| class _UI, size_t _W, size_t _S, size_t _R> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| subtract_with_carry_engine<_UI, _W, _S, _R>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| _UI __t[_R+1]; |
| for (size_t __i = 0; __i < _R+1; ++__i) |
| __is >> __t[__i]; |
| if (!__is.fail()) |
| { |
| for (size_t __i = 0; __i < _R; ++__i) |
| __x.__x_[__i] = __t[__i]; |
| __x.__c_ = __t[_R]; |
| __x.__i_ = 0; |
| } |
| return __is; |
| } |
| |
| typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24> ranlux24_base; |
| typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12> ranlux48_base; |
| |
| // discard_block_engine |
| |
| template<class _Engine, size_t __p, size_t __r> |
| class discard_block_engine |
| { |
| _Engine __e_; |
| int __n_; |
| |
| static_assert( 0 < __r, "discard_block_engine invalid parameters"); |
| static_assert(__r <= __p, "discard_block_engine invalid parameters"); |
| public: |
| // types |
| typedef typename _Engine::result_type result_type; |
| |
| // engine characteristics |
| static const/*expr*/ size_t block_size = __p; |
| static const/*expr*/ size_t used_block = __r; |
| |
| // Temporary work around for lack of constexpr |
| static const result_type _Min = _Engine::_Min; |
| static const result_type _Max = _Engine::_Max; |
| |
| static const/*expr*/ result_type min() { return _Engine::min(); } |
| static const/*expr*/ result_type max() { return _Engine::max(); } |
| |
| // constructors and seeding functions |
| discard_block_engine() : __n_(0) {} |
| // explicit discard_block_engine(const _Engine& __e); |
| // explicit discard_block_engine(_Engine&& __e); |
| explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {} |
| template<class _Sseq> explicit discard_block_engine(_Sseq& __q) |
| : __e_(__q), __n_(0) {} |
| void seed() {__e_.seed(); __n_ = 0;} |
| void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;} |
| template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;} |
| |
| // generating functions |
| result_type operator()(); |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| // property functions |
| const _Engine& base() const {return __e_;} |
| |
| template<class _Eng, size_t _P, size_t _R> |
| friend |
| bool |
| operator==( |
| const discard_block_engine<_Eng, _P, _R>& __x, |
| const discard_block_engine<_Eng, _P, _R>& __y); |
| |
| template<class _Eng, size_t _P, size_t _R> |
| friend |
| bool |
| operator!=( |
| const discard_block_engine<_Eng, _P, _R>& __x, |
| const discard_block_engine<_Eng, _P, _R>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _P, size_t _R> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const discard_block_engine<_Eng, _P, _R>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _P, size_t _R> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| discard_block_engine<_Eng, _P, _R>& __x); |
| }; |
| |
| template<class _Engine, size_t __p, size_t __r> |
| typename discard_block_engine<_Engine, __p, __r>::result_type |
| discard_block_engine<_Engine, __p, __r>::operator()() |
| { |
| if (__n_ >= __r) |
| { |
| __e_.discard(__p - __r); |
| __n_ = 0; |
| } |
| ++__n_; |
| return __e_(); |
| } |
| |
| template<class _Eng, size_t _P, size_t _R> |
| inline |
| bool |
| operator==(const discard_block_engine<_Eng, _P, _R>& __x, |
| const discard_block_engine<_Eng, _P, _R>& __y) |
| { |
| return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_; |
| } |
| |
| template<class _Eng, size_t _P, size_t _R> |
| inline |
| bool |
| operator!=(const discard_block_engine<_Eng, _P, _R>& __x, |
| const discard_block_engine<_Eng, _P, _R>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _P, size_t _R> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const discard_block_engine<_Eng, _P, _R>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| return __os << __x.__e_ << __sp << __x.__n_; |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _P, size_t _R> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| discard_block_engine<_Eng, _P, _R>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| _Eng __e; |
| int __n; |
| __is >> __e >> __n; |
| if (!__is.fail()) |
| { |
| __x.__e_ = __e; |
| __x.__n_ = __n; |
| } |
| return __is; |
| } |
| |
| typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24; |
| typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48; |
| |
| // independent_bits_engine |
| |
| template <unsigned long long _X, size_t _R> |
| struct __log2_imp |
| { |
| static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R |
| : __log2_imp<_X, _R - 1>::value; |
| }; |
| |
| template <unsigned long long _X> |
| struct __log2_imp<_X, 0> |
| { |
| static const size_t value = 0; |
| }; |
| |
| template <size_t _R> |
| struct __log2_imp<0, _R> |
| { |
| static const size_t value = _R + 1; |
| }; |
| |
| template <class _UI, _UI _X> |
| struct __log2 |
| { |
| static const size_t value = __log2_imp<_X, |
| sizeof(_UI) * __CHAR_BIT__ - 1>::value; |
| }; |
| |
| template<class _Engine, size_t __w, class _UIntType> |
| class independent_bits_engine |
| { |
| template <class _UI, _UI _R0, size_t _W, size_t _M> |
| class __get_n |
| { |
| static const size_t _Dt = numeric_limits<_UI>::digits; |
| static const size_t _N = _W / _M + (_W % _M != 0); |
| static const size_t _W0 = _W / _N; |
| static const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0; |
| public: |
| static const size_t value = _R0 - _Y0 > _Y0 / _N ? _N + 1 : _N; |
| }; |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| _Engine __e_; |
| |
| static const result_type _Dt = numeric_limits<result_type>::digits; |
| static_assert( 0 < __w, "independent_bits_engine invalid parameters"); |
| static_assert(__w <= _Dt, "independent_bits_engine invalid parameters"); |
| |
| typedef typename _Engine::result_type _Engine_result_type; |
| typedef typename conditional |
| < |
| sizeof(_Engine_result_type) <= sizeof(result_type), |
| result_type, |
| _Engine_result_type |
| >::type _Working_result_type; |
| // Temporary work around for lack of constexpr |
| static const _Working_result_type _R = _Engine::_Max - _Engine::_Min |
| + _Working_result_type(1); |
| static const size_t __m = __log2<_Working_result_type, _R>::value; |
| static const size_t __n = __get_n<_Working_result_type, _R, __w, __m>::value; |
| static const size_t __w0 = __w / __n; |
| static const size_t __n0 = __n - __w % __n; |
| static const size_t _WDt = numeric_limits<_Working_result_type>::digits; |
| static const size_t _EDt = numeric_limits<_Engine_result_type>::digits; |
| static const _Working_result_type __y0 = __w0 >= _WDt ? 0 : |
| (_R >> __w0) << __w0; |
| static const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 : |
| (_R >> (__w0+1)) << (__w0+1); |
| static const _Engine_result_type __mask0 = __w0 > 0 ? |
| _Engine_result_type(~0) >> (_EDt - __w0) : |
| _Engine_result_type(0); |
| static const _Engine_result_type __mask1 = __w0 < _EDt - 1 ? |
| _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) : |
| _Engine_result_type(~0); |
| public: |
| static const result_type _Min = 0; |
| static const result_type _Max = __w == _Dt ? result_type(~0) : |
| (result_type(1) << __w) - result_type(1); |
| static_assert(_Min < _Max, "independent_bits_engine invalid parameters"); |
| |
| // engine characteristics |
| static const/*expr*/ result_type min() { return _Min; } |
| static const/*expr*/ result_type max() { return _Max; } |
| |
| // constructors and seeding functions |
| independent_bits_engine() {} |
| // explicit independent_bits_engine(const _Engine& __e); |
| // explicit independent_bits_engine(_Engine&& __e); |
| explicit independent_bits_engine(result_type __sd) : __e_(__sd) {} |
| template<class _Sseq> explicit independent_bits_engine(_Sseq& __q) |
| : __e_(__q) {} |
| void seed() {__e_.seed();} |
| void seed(result_type __sd) {__e_.seed(__sd);} |
| template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q);} |
| |
| // generating functions |
| result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| // property functions |
| const _Engine& base() const {return __e_;} |
| |
| template<class _Eng, size_t _W, class _UI> |
| friend |
| bool |
| operator==( |
| const independent_bits_engine<_Eng, _W, _UI>& __x, |
| const independent_bits_engine<_Eng, _W, _UI>& __y); |
| |
| template<class _Eng, size_t _W, class _UI> |
| friend |
| bool |
| operator!=( |
| const independent_bits_engine<_Eng, _W, _UI>& __x, |
| const independent_bits_engine<_Eng, _W, _UI>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _W, class _UI> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const independent_bits_engine<_Eng, _W, _UI>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _W, class _UI> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| independent_bits_engine<_Eng, _W, _UI>& __x); |
| |
| private: |
| result_type __eval(false_type); |
| result_type __eval(true_type); |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| __count < _Dt, |
| result_type |
| >::type |
| __lshift(result_type __x) {return __x << __count;} |
| |
| template <size_t __count> |
| static |
| typename enable_if |
| < |
| (__count >= _Dt), |
| result_type |
| >::type |
| __lshift(result_type __x) {return result_type(0);} |
| }; |
| |
| template<class _Engine, size_t __w, class _UIntType> |
| inline |
| _UIntType |
| independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type) |
| { |
| return static_cast<result_type>(__e_() & __mask0); |
| } |
| |
| template<class _Engine, size_t __w, class _UIntType> |
| _UIntType |
| independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type) |
| { |
| result_type _S = 0; |
| for (size_t __k = 0; __k < __n0; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y0); |
| _S = static_cast<result_type>(__lshift<__w0>(_S) + (__u & __mask0)); |
| } |
| for (size_t __k = __n0; __k < __n; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y1); |
| _S = static_cast<result_type>(__lshift<__w0+1>(_S) + (__u & __mask1)); |
| } |
| return _S; |
| } |
| |
| template<class _Eng, size_t _W, class _UI> |
| inline |
| bool |
| operator==( |
| const independent_bits_engine<_Eng, _W, _UI>& __x, |
| const independent_bits_engine<_Eng, _W, _UI>& __y) |
| { |
| return __x.base() == __y.base(); |
| } |
| |
| template<class _Eng, size_t _W, class _UI> |
| inline |
| bool |
| operator!=( |
| const independent_bits_engine<_Eng, _W, _UI>& __x, |
| const independent_bits_engine<_Eng, _W, _UI>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _W, class _UI> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const independent_bits_engine<_Eng, _W, _UI>& __x) |
| { |
| return __os << __x.base(); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _W, class _UI> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| independent_bits_engine<_Eng, _W, _UI>& __x) |
| { |
| _Eng __e; |
| __is >> __e; |
| if (!__is.fail()) |
| __x.__e_ = __e; |
| return __is; |
| } |
| |
| // shuffle_order_engine |
| |
| template <uint64_t _Xp, uint64_t _Yp> |
| struct __ugcd |
| { |
| static const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value; |
| }; |
| |
| template <uint64_t _Xp> |
| struct __ugcd<_Xp, 0> |
| { |
| static const uint64_t value = _Xp; |
| }; |
| |
| template <uint64_t _N, uint64_t _D> |
| class __uratio |
| { |
| static_assert(_D != 0, "__uratio divide by 0"); |
| static const uint64_t __gcd = __ugcd<_N, _D>::value; |
| public: |
| static const uint64_t num = _N / __gcd; |
| static const uint64_t den = _D / __gcd; |
| |
| typedef __uratio<num, den> type; |
| }; |
| |
| template<class _Engine, size_t __k> |
| class shuffle_order_engine |
| { |
| static_assert(0 < __k, "shuffle_order_engine invalid parameters"); |
| public: |
| // types |
| typedef typename _Engine::result_type result_type; |
| |
| private: |
| _Engine __e_; |
| result_type _V_[__k]; |
| result_type _Y_; |
| |
| public: |
| // engine characteristics |
| static const/*expr*/ size_t table_size = __k; |
| |
| static const result_type _Min = _Engine::_Min; |
| static const result_type _Max = _Engine::_Max; |
| static_assert(_Min < _Max, "shuffle_order_engine invalid parameters"); |
| static const/*expr*/ result_type min() { return _Min; } |
| static const/*expr*/ result_type max() { return _Max; } |
| |
| static const unsigned long long _R = _Max - _Min + 1ull; |
| |
| // constructors and seeding functions |
| shuffle_order_engine() {__init();} |
| // explicit shuffle_order_engine(const _Engine& __e); |
| // explicit shuffle_order_engine(_Engine&& e); |
| explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();} |
| template<class _Sseq> explicit shuffle_order_engine(_Sseq& __q) |
| : __e_(__q) {__init();} |
| void seed() {__e_.seed(); __init();} |
| void seed(result_type __sd) {__e_.seed(__sd); __init();} |
| template<class _Sseq> void seed(_Sseq& __q) {__e_.seed(__q); __init();} |
| |
| // generating functions |
| result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} |
| void discard(unsigned long long __z) {for (; __z; --__z) operator()();} |
| |
| // property functions |
| const _Engine& base() const {return __e_;} |
| |
| private: |
| template<class _Eng, size_t _K> |
| friend |
| bool |
| operator==( |
| const shuffle_order_engine<_Eng, _K>& __x, |
| const shuffle_order_engine<_Eng, _K>& __y); |
| |
| template<class _Eng, size_t _K> |
| friend |
| bool |
| operator!=( |
| const shuffle_order_engine<_Eng, _K>& __x, |
| const shuffle_order_engine<_Eng, _K>& __y); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _K> |
| friend |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const shuffle_order_engine<_Eng, _K>& __x); |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _K> |
| friend |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| shuffle_order_engine<_Eng, _K>& __x); |
| |
| void __init() |
| { |
| for (size_t __i = 0; __i < __k; ++__i) |
| _V_[__i] = __e_(); |
| _Y_ = __e_(); |
| } |
| |
| result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());} |
| result_type __eval(true_type) {return __eval(__uratio<__k, _R>());} |
| |
| result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());} |
| result_type __eval2(true_type) {return __evalf<__k, 0>();} |
| |
| template <uint64_t _N, uint64_t _D> |
| typename enable_if |
| < |
| (__uratio<_N, _D>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)), |
| result_type |
| >::type |
| __eval(__uratio<_N, _D>) |
| {return __evalf<__uratio<_N, _D>::num, __uratio<_N, _D>::den>();} |
| |
| template <uint64_t _N, uint64_t _D> |
| typename enable_if |
| < |
| __uratio<_N, _D>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min), |
| result_type |
| >::type |
| __eval(__uratio<_N, _D>) |
| { |
| const size_t __j = static_cast<size_t>(__uratio<_N, _D>::num * (_Y_ - _Min) |
| / __uratio<_N, _D>::den); |
| _Y_ = _V_[__j]; |
| _V_[__j] = __e_(); |
| return _Y_; |
| } |
| |
| template <uint64_t __n, uint64_t __d> |
| result_type __evalf() |
| { |
| const double _F = __d == 0 ? |
| __n / (2. * 0x8000000000000000ull) : |
| __n / (double)__d; |
| const size_t __j = static_cast<size_t>(_F * (_Y_ - _Min)); |
| _Y_ = _V_[__j]; |
| _V_[__j] = __e_(); |
| return _Y_; |
| } |
| }; |
| |
| template<class _Eng, size_t _K> |
| bool |
| operator==( |
| const shuffle_order_engine<_Eng, _K>& __x, |
| const shuffle_order_engine<_Eng, _K>& __y) |
| { |
| return __x._Y_ == __y._Y_ && _STD::equal(__x._V_, __x._V_ + _K, __y._V_) && |
| __x.__e_ == __y.__e_; |
| } |
| |
| template<class _Eng, size_t _K> |
| inline |
| bool |
| operator!=( |
| const shuffle_order_engine<_Eng, _K>& __x, |
| const shuffle_order_engine<_Eng, _K>& __y) |
| { |
| return !(__x == __y); |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _K> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const shuffle_order_engine<_Eng, _K>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| __os << __x.__e_ << __sp << __x._V_[0]; |
| for (size_t __i = 1; __i < _K; ++__i) |
| __os << __sp << __x._V_[__i]; |
| return __os << __sp << __x._Y_; |
| } |
| |
| template <class _CharT, class _Traits, |
| class _Eng, size_t _K> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| shuffle_order_engine<_Eng, _K>& __x) |
| { |
| typedef typename shuffle_order_engine<_Eng, _K>::result_type result_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| _Eng __e; |
| result_type _V[_K+1]; |
| __is >> __e; |
| for (size_t __i = 0; __i < _K+1; ++__i) |
| __is >> _V[__i]; |
| if (!__is.fail()) |
| { |
| __x.__e_ = __e; |
| for (size_t __i = 0; __i < _K; ++__i) |
| __x._V_[__i] = _V[__i]; |
| __x._Y_ = _V[_K]; |
| } |
| return __is; |
| } |
| |
| typedef shuffle_order_engine<minstd_rand0, 256> knuth_b; |
| |
| // random_device |
| |
| class random_device |
| { |
| int __f_; |
| public: |
| // types |
| typedef unsigned result_type; |
| |
| // generator characteristics |
| static const result_type _Min = 0; |
| static const result_type _Max = 0xFFFFFFFFu; |
| |
| static const/*expr*/ result_type min() { return _Min;} |
| static const/*expr*/ result_type max() { return _Max;} |
| |
| // constructors |
| explicit random_device(const string& __token = "/dev/urandom"); |
| ~random_device(); |
| |
| // generating functions |
| result_type operator()(); |
| |
| // property functions |
| double entropy() const; |
| |
| private: |
| // no copy functions |
| random_device(const random_device&); // = delete; |
| random_device& operator=(const random_device&); // = delete; |
| }; |
| |
| // seed_seq |
| |
| class seed_seq |
| { |
| public: |
| // types |
| typedef uint32_t result_type; |
| |
| private: |
| vector<result_type> __v_; |
| |
| template<class _InputIterator> |
| void init(_InputIterator __first, _InputIterator __last); |
| public: |
| // constructors |
| seed_seq() {} |
| template<class _Tp> |
| seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());} |
| |
| template<class _InputIterator> |
| seed_seq(_InputIterator __first, _InputIterator __last) |
| {init(__first, __last);} |
| |
| // generating functions |
| template<class _RandomAccessIterator> |
| void generate(_RandomAccessIterator __first, _RandomAccessIterator __last); |
| |
| // property functions |
| size_t size() const {return __v_.size();} |
| template<class _OutputIterator> |
| void param(_OutputIterator __dest) const |
| {_STD::copy(__v_.begin(), __v_.end(), __dest);} |
| |
| private: |
| // no copy functions |
| seed_seq(const seed_seq&); // = delete; |
| void operator=(const seed_seq&); // = delete; |
| |
| static result_type _T(result_type __x) {return __x ^ (__x >> 27);} |
| }; |
| |
| template<class _InputIterator> |
| void |
| seed_seq::init(_InputIterator __first, _InputIterator __last) |
| { |
| for (_InputIterator __s = __first; __s != __last; ++__s) |
| __v_.push_back(*__s & 0xFFFFFFFF); |
| } |
| |
| template<class _RandomAccessIterator> |
| void |
| seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last) |
| { |
| if (__first != __last) |
| { |
| _STD::fill(__first, __last, 0x8b8b8b8b); |
| const size_t __n = static_cast<size_t>(__last - __first); |
| const size_t __s = __v_.size(); |
| const size_t __t = (__n >= 623) ? 11 |
| : (__n >= 68) ? 7 |
| : (__n >= 39) ? 5 |
| : (__n >= 7) ? 3 |
| : (__n - 1) / 2; |
| const size_t __p = (__n - __t) / 2; |
| const size_t __q = __p + __t; |
| const size_t __m = _STD::max(__s + 1, __n); |
| // __k = 0; |
| { |
| result_type __r = 1664525 * _T(__first[0] ^ __first[__p] |
| ^ __first[__n - 1]); |
| __first[__p] += __r; |
| __r += __s; |
| __first[__q] += __r; |
| __first[0] = __r; |
| } |
| for (size_t __k = 1; __k <= __s; ++__k) |
| { |
| const size_t __kmodn = __k % __n; |
| const size_t __kpmodn = (__k + __p) % __n; |
| result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn] |
| ^ __first[(__k - 1) % __n]); |
| __first[__kpmodn] += __r; |
| __r += __kmodn + __v_[__k-1]; |
| __first[(__k + __q) % __n] += __r; |
| __first[__kmodn] = __r; |
| } |
| for (size_t __k = __s + 1; __k < __m; ++__k) |
| { |
| const size_t __kmodn = __k % __n; |
| const size_t __kpmodn = (__k + __p) % __n; |
| result_type __r = 1664525 * _T(__first[__kmodn] ^ __first[__kpmodn] |
| ^ __first[(__k - 1) % __n]); |
| __first[__kpmodn] += __r; |
| __r += __kmodn; |
| __first[(__k + __q) % __n] += __r; |
| __first[__kmodn] = __r; |
| } |
| for (size_t __k = __m; __k < __m + __n; ++__k) |
| { |
| const size_t __kmodn = __k % __n; |
| const size_t __kpmodn = (__k + __p) % __n; |
| result_type __r = 1566083941 * _T(__first[__kmodn] + |
| __first[__kpmodn] + |
| __first[(__k - 1) % __n]); |
| __first[__kpmodn] ^= __r; |
| __r -= __kmodn; |
| __first[(__k + __q) % __n] ^= __r; |
| __first[__kmodn] = __r; |
| } |
| } |
| } |
| |
| // generate_canonical |
| |
| template<class _RealType, size_t __bits, class _URNG> |
| _RealType |
| generate_canonical(_URNG& __g) |
| { |
| const size_t _Dt = numeric_limits<_RealType>::digits; |
| const size_t __b = _Dt < __bits ? _Dt : __bits; |
| const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value; |
| const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0); |
| const _RealType _R = _URNG::_Max - _URNG::_Min + _RealType(1); |
| _RealType __base = _R; |
| _RealType _S = __g() - _URNG::_Min; |
| for (size_t __i = 1; __i < __k; ++__i, __base *= _R) |
| _S += (__g() - _URNG::_Min) * __base; |
| return _S / __base; |
| } |
| |
| // __independent_bits_engine |
| |
| template<class _Engine, class _UIntType> |
| class __independent_bits_engine |
| { |
| public: |
| // types |
| typedef _UIntType result_type; |
| |
| private: |
| typedef typename _Engine::result_type _Engine_result_type; |
| typedef typename conditional |
| < |
| sizeof(_Engine_result_type) <= sizeof(result_type), |
| result_type, |
| _Engine_result_type |
| >::type _Working_result_type; |
| |
| _Engine& __e_; |
| size_t __w_; |
| size_t __w0_; |
| size_t __n_; |
| size_t __n0_; |
| _Working_result_type __y0_; |
| _Working_result_type __y1_; |
| _Engine_result_type __mask0_; |
| _Engine_result_type __mask1_; |
| |
| static const _Working_result_type _R = _Engine::_Max - _Engine::_Min |
| + _Working_result_type(1); |
| static const size_t __m = __log2<_Working_result_type, _R>::value; |
| static const size_t _WDt = numeric_limits<_Working_result_type>::digits; |
| static const size_t _EDt = numeric_limits<_Engine_result_type>::digits; |
| |
| public: |
| // constructors and seeding functions |
| __independent_bits_engine(_Engine& __e, size_t __w); |
| |
| // generating functions |
| result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} |
| |
| private: |
| result_type __eval(false_type); |
| result_type __eval(true_type); |
| }; |
| |
| template<class _Engine, class _UIntType> |
| __independent_bits_engine<_Engine, _UIntType> |
| ::__independent_bits_engine(_Engine& __e, size_t __w) |
| : __e_(__e), |
| __w_(__w) |
| { |
| __n_ = __w_ / __m + (__w_ % __m != 0); |
| __w0_ = __w_ / __n_; |
| if (_R == 0) |
| __y0_ = _R; |
| else if (__w0_ < _WDt) |
| __y0_ = (_R >> __w0_) << __w0_; |
| else |
| __y0_ = 0; |
| if (_R - __y0_ > __y0_ / __n_) |
| { |
| ++__n_; |
| __w0_ = __w_ / __n_; |
| if (__w0_ < _WDt) |
| __y0_ = (_R >> __w0_) << __w0_; |
| else |
| __y0_ = 0; |
| } |
| __n0_ = __n_ - __w_ % __n_; |
| if (__w0_ < _WDt - 1) |
| __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1); |
| else |
| __y1_ = 0; |
| __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : |
| _Engine_result_type(0); |
| __mask1_ = __w0_ < _EDt - 1 ? |
| _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : |
| _Engine_result_type(~0); |
| } |
| |
| template<class _Engine, class _UIntType> |
| inline |
| _UIntType |
| __independent_bits_engine<_Engine, _UIntType>::__eval(false_type) |
| { |
| return static_cast<result_type>(__e_() & __mask0_); |
| } |
| |
| template<class _Engine, class _UIntType> |
| _UIntType |
| __independent_bits_engine<_Engine, _UIntType>::__eval(true_type) |
| { |
| result_type _S = 0; |
| for (size_t __k = 0; __k < __n0_; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y0_); |
| if (__w0_ < _EDt) |
| _S <<= __w0_; |
| else |
| _S = 0; |
| _S += __u & __mask0_; |
| } |
| for (size_t __k = __n0_; __k < __n_; ++__k) |
| { |
| _Engine_result_type __u; |
| do |
| { |
| __u = __e_() - _Engine::min(); |
| } while (__u >= __y1_); |
| if (__w0_ < _EDt - 1) |
| _S <<= __w0_ + 1; |
| else |
| _S = 0; |
| _S += __u & __mask1_; |
| } |
| return _S; |
| } |
| |
| // uniform_int_distribution |
| |
| template<class _IntType = int> |
| class uniform_int_distribution |
| { |
| public: |
| // types |
| typedef _IntType result_type; |
| |
| class param_type |
| { |
| result_type __a_; |
| result_type __b_; |
| public: |
| typedef uniform_int_distribution distribution_type; |
| |
| explicit param_type(result_type __a = 0, |
| result_type __b = numeric_limits<result_type>::max()) |
| : __a_(__a), __b_(__b) {} |
| |
| result_type a() const {return __a_;} |
| result_type b() const {return __b_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| explicit uniform_int_distribution(result_type __a = 0, |
| result_type __b = numeric_limits<result_type>::max()) |
| : __p_(param_type(__a, __b)) {} |
| explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| result_type a() const {return __p_.a();} |
| result_type b() const {return __p_.b();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return a();} |
| result_type max() const {return b();} |
| |
| friend bool operator==(const uniform_int_distribution& __x, |
| const uniform_int_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const uniform_int_distribution& __x, |
| const uniform_int_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template<class _IntType> |
| template<class _URNG> |
| typename uniform_int_distribution<_IntType>::result_type |
| uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) |
| { |
| typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), |
| uint32_t, uint64_t>::type _UIntType; |
| const _UIntType _R = __p.b() - __p.a() + _UIntType(1); |
| if (_R == 1) |
| return __p.a(); |
| const size_t _Dt = numeric_limits<_UIntType>::digits; |
| typedef __independent_bits_engine<_URNG, _UIntType> _Eng; |
| if (_R == 0) |
| return static_cast<result_type>(_Eng(__g, _Dt)()); |
| size_t __w = _Dt - __clz(_R) - 1; |
| if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0) |
| ++__w; |
| _Eng __e(__g, __w); |
| _UIntType __u; |
| do |
| { |
| __u = __e(); |
| } while (__u >= _R); |
| return static_cast<result_type>(__u + __p.a()); |
| } |
| |
| template <class _CharT, class _Traits, class _IT> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const uniform_int_distribution<_IT>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| return __os << __x.a() << __sp << __x.b(); |
| } |
| |
| template <class _CharT, class _Traits, class _IT> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| uniform_int_distribution<_IT>& __x) |
| { |
| typedef uniform_int_distribution<_IT> _Eng; |
| typedef typename _Eng::result_type result_type; |
| typedef typename _Eng::param_type param_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| result_type __a; |
| result_type __b; |
| __is >> __a >> __b; |
| if (!__is.fail()) |
| __x.param(param_type(__a, __b)); |
| return __is; |
| } |
| |
| // uniform_real_distribution |
| |
| template<class _RealType = double> |
| class uniform_real_distribution |
| { |
| public: |
| // types |
| typedef _RealType result_type; |
| |
| class param_type |
| { |
| result_type __a_; |
| result_type __b_; |
| public: |
| typedef uniform_real_distribution distribution_type; |
| |
| explicit param_type(result_type __a = 0, |
| result_type __b = 1) |
| : __a_(__a), __b_(__b) {} |
| |
| result_type a() const {return __a_;} |
| result_type b() const {return __b_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1) |
| : __p_(param_type(__a, __b)) {} |
| explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| result_type a() const {return __p_.a();} |
| result_type b() const {return __p_.b();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return a();} |
| result_type max() const {return b();} |
| |
| friend bool operator==(const uniform_real_distribution& __x, |
| const uniform_real_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const uniform_real_distribution& __x, |
| const uniform_real_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template<class _RealType> |
| template<class _URNG> |
| inline |
| typename uniform_real_distribution<_RealType>::result_type |
| uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) |
| { |
| return (__p.b() - __p.a()) |
| * _STD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g) |
| + __p.a(); |
| } |
| |
| template <class _CharT, class _Traits, class _RT> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const uniform_real_distribution<_RT>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| return __os << __x.a() << __sp << __x.b(); |
| } |
| |
| template <class _CharT, class _Traits, class _RT> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| uniform_real_distribution<_RT>& __x) |
| { |
| typedef uniform_real_distribution<_RT> _Eng; |
| typedef typename _Eng::result_type result_type; |
| typedef typename _Eng::param_type param_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| result_type __a; |
| result_type __b; |
| __is >> __a >> __b; |
| if (!__is.fail()) |
| __x.param(param_type(__a, __b)); |
| return __is; |
| } |
| |
| // bernoulli_distribution |
| |
| class bernoulli_distribution |
| { |
| public: |
| // types |
| typedef bool result_type; |
| |
| class param_type |
| { |
| double __p_; |
| public: |
| typedef bernoulli_distribution distribution_type; |
| |
| explicit param_type(double __p = 0.5) : __p_(__p) {} |
| |
| double p() const {return __p_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| explicit bernoulli_distribution(double __p = 0.5) |
| : __p_(param_type(__p)) {} |
| explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| double p() const {return __p_.p();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return false;} |
| result_type max() const {return true;} |
| |
| friend bool operator==(const bernoulli_distribution& __x, |
| const bernoulli_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const bernoulli_distribution& __x, |
| const bernoulli_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template<class _URNG> |
| inline |
| bernoulli_distribution::result_type |
| bernoulli_distribution::operator()(_URNG& __g, const param_type& __p) |
| { |
| return (__g() - __g.min()) < __p.p() * (__g.max() - __g.min() + 1.); |
| } |
| |
| template <class _CharT, class _Traits> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| return __os << __x.p(); |
| } |
| |
| template <class _CharT, class _Traits> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x) |
| { |
| typedef bernoulli_distribution _Eng; |
| typedef typename _Eng::param_type param_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| double __p; |
| __is >> __p; |
| if (!__is.fail()) |
| __x.param(param_type(__p)); |
| return __is; |
| } |
| |
| // binomial_distribution |
| |
| template<class _IntType = int> |
| class binomial_distribution |
| { |
| public: |
| // types |
| typedef _IntType result_type; |
| |
| class param_type |
| { |
| result_type __t_; |
| double __p_; |
| public: |
| typedef binomial_distribution distribution_type; |
| |
| explicit param_type(result_type __t = 1, double __p = 0.5) |
| : __t_(__t), __p_(__p) {} |
| |
| result_type t() const {return __t_;} |
| double p() const {return __p_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| explicit binomial_distribution(result_type __t = 1, double __p = 0.5) |
| : __p_(param_type(__t, __p)) {} |
| explicit binomial_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| result_type t() const {return __p_.t();} |
| double p() const {return __p_.p();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return 0;} |
| result_type max() const {return t();} |
| |
| friend bool operator==(const binomial_distribution& __x, |
| const binomial_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const binomial_distribution& __x, |
| const binomial_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template<class _IntType> |
| template<class _URNG> |
| _IntType |
| binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p) |
| { |
| bernoulli_distribution __bd(__p.p()); |
| _IntType __r = 0; |
| _IntType __t = __p.t(); |
| for (_IntType __i = 0; __i < __t; ++__i) |
| __r += __bd(__g); |
| return __r; |
| } |
| |
| template <class _CharT, class _Traits, class _IntType> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const binomial_distribution<_IntType>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| _CharT __sp = __os.widen(' '); |
| __os.fill(__sp); |
| return __os << __x.t() << __sp << __x.p(); |
| } |
| |
| template <class _CharT, class _Traits, class _IntType> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| binomial_distribution<_IntType>& __x) |
| { |
| typedef binomial_distribution<_IntType> _Eng; |
| typedef typename _Eng::result_type result_type; |
| typedef typename _Eng::param_type param_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| result_type __t; |
| double __p; |
| __is >> __t >> __p; |
| if (!__is.fail()) |
| __x.param(param_type(__t, __p)); |
| return __is; |
| } |
| |
| // exponential_distribution |
| |
| template<class _RealType = double> |
| class exponential_distribution |
| { |
| public: |
| // types |
| typedef _RealType result_type; |
| |
| class param_type |
| { |
| result_type __lambda_; |
| public: |
| typedef exponential_distribution distribution_type; |
| |
| explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {} |
| |
| result_type lambda() const {return __lambda_;} |
| |
| friend bool operator==(const param_type& __x, const param_type& __y) |
| {return __x.__lambda_ == __y.__lambda_;} |
| friend bool operator!=(const param_type& __x, const param_type& __y) |
| {return !(__x == __y);} |
| }; |
| |
| private: |
| param_type __p_; |
| |
| public: |
| // constructors and reset functions |
| explicit exponential_distribution(result_type __lambda = 1) |
| : __p_(param_type(__lambda)) {} |
| explicit exponential_distribution(const param_type& __p) : __p_(__p) {} |
| void reset() {} |
| |
| // generating functions |
| template<class _URNG> result_type operator()(_URNG& __g) |
| {return (*this)(__g, __p_);} |
| template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); |
| |
| // property functions |
| result_type lambda() const {return __p_.lambda();} |
| |
| param_type param() const {return __p_;} |
| void param(const param_type& __p) {__p_ = __p;} |
| |
| result_type min() const {return 0;} |
| result_type max() const |
| {return -std::log(1-std::nextafter(result_type(1), result_type(-1))) / |
| __p_.lambda();} |
| |
| friend bool operator==(const exponential_distribution& __x, |
| const exponential_distribution& __y) |
| {return __x.__p_ == __y.__p_;} |
| friend bool operator!=(const exponential_distribution& __x, |
| const exponential_distribution& __y) |
| {return !(__x == __y);} |
| }; |
| |
| template <class _RealType> |
| template<class _URNG> |
| _RealType |
| exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p) |
| { |
| return -_STD::log |
| ( |
| result_type(1) - |
| _STD::generate_canonical<result_type, |
| numeric_limits<result_type>::digits>(__g) |
| ) |
| / __p.lambda(); |
| } |
| |
| template <class _CharT, class _Traits, class _RealType> |
| basic_ostream<_CharT, _Traits>& |
| operator<<(basic_ostream<_CharT, _Traits>& __os, |
| const exponential_distribution<_RealType>& __x) |
| { |
| __save_flags<_CharT, _Traits> _(__os); |
| __os.flags(ios_base::dec | ios_base::left); |
| return __os << __x.lambda(); |
| } |
| |
| template <class _CharT, class _Traits, class _RealType> |
| basic_istream<_CharT, _Traits>& |
| operator>>(basic_istream<_CharT, _Traits>& __is, |
| exponential_distribution<_RealType>& __x) |
| { |
| typedef exponential_distribution<_RealType> _Eng; |
| typedef typename _Eng::result_type result_type; |
| typedef typename _Eng::param_type param_type; |
| __save_flags<_CharT, _Traits> _(__is); |
| __is.flags(ios_base::dec | ios_base::skipws); |
| result_type __lambda; |
| __is >> __lambda; |
| if (!__is.fail()) |
| __x.param(param_type(__lambda)); |
| return __is; |
| } |
| |
| _LIBCPP_END_NAMESPACE_STD |
| |
| #endif // _LIBCPP_RANDOM |