libcxx initial import
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@103490 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/random b/include/random
new file mode 100644
index 0000000..f468020
--- /dev/null
+++ b/include/random
@@ -0,0 +1,2851 @@
+// -*- 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;
+
+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;
+
+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>
+
+#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;
+ }
+ }
+}
+
+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;
+}
+
+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;
+}
+
+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;
+}
+
+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)
+ {
+ return _STD::generate_canonical<double, numeric_limits<double>::digits>(__g)
+ < __p.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 _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;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_RANDOM