blob: 4a8c2a79267be72460a513a7a7faeda292bd8918 [file] [log] [blame]
// -*- C++ -*-
//===--------------------------- random -----------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP_RANDOM
#define _LIBCPP_RANDOM
/*
random synopsis
#include <initializer_list>
namespace std
{
// [rand.req.urng], uniform random bit generator requirements
template<class G>
concept uniform_random_bit_generator = see below; // C++20
// 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); // before C++20
linear_congruential_engine() : linear_congruential_engine(default_seed) {} // C++20
explicit linear_congruential_engine(result_type s); // C++20
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 s = default_seed); // before C++20
mersenne_twister_engine() : mersenne_twister_engine(default_seed) {} // C++20
explicit mersenne_twister_engine(result_type s); // C++20
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); // before C++20
subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {} // C++20
explicit subtract_with_carry_engine(result_type value); // C++20
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 noexcept;
};
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 noexcept;
};
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 noexcept;
};
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_rand 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 = implementation-defined); // before C++20
random_device() : random_device(implementation-defined) {} // C++20
explicit random_device(const string& token); // C++20
// generating functions
result_type operator()();
// property functions
double entropy() const noexcept;
// 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()); // before C++20
uniform_int_distribution() : uniform_int_distribution(0) {} // C++20
explicit uniform_int_distribution(IntType a,
IntType b = numeric_limits<IntType>::max()); // C++20
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); // before C++20
uniform_real_distribution() : uniform_real_distribution(0.0) {} // C++20
explicit uniform_real_distribution(RealType a, RealType b = 1.0); // C++20
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); // before C++20
bernoulli_distribution() : bernoulli_distribution(0.5) {} // C++20
explicit bernoulli_distribution(double p); // C++20
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); // before C++20
binomial_distribution() : binomial_distribution(1) {} // C++20
explicit binomial_distribution(IntType t, double p = 0.5); // C++20
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
{
public:
// types
typedef IntType result_type;
class param_type
{
public:
typedef geometric_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 geometric_distribution(double p = 0.5); // before C++20
geometric_distribution() : geometric_distribution(0.5) {} // C++20
explicit geometric_distribution(double p); // C++20
explicit geometric_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 geometric_distribution& x,
const geometric_distribution& y);
friend bool operator!=(const geometric_distribution& x,
const geometric_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const geometric_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
geometric_distribution& x);
};
template<class IntType = int>
class negative_binomial_distribution
{
public:
// types
typedef IntType result_type;
class param_type
{
public:
typedef negative_binomial_distribution distribution_type;
explicit param_type(result_type k = 1, double p = 0.5);
result_type k() 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);
};
// constructor and reset functions
explicit negative_binomial_distribution(IntType k = 1, double p = 0.5); // before C++20
negative_binomial_distribution() : negative_binomial_distribution(1) {} // C++20
explicit negative_binomial_distribution(IntType k, double p = 0.5); // C++20
explicit negative_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
result_type k() 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 negative_binomial_distribution& x,
const negative_binomial_distribution& y);
friend bool operator!=(const negative_binomial_distribution& x,
const negative_binomial_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const negative_binomial_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
negative_binomial_distribution& x);
};
template<class IntType = int>
class poisson_distribution
{
public:
// types
typedef IntType result_type;
class param_type
{
public:
typedef poisson_distribution distribution_type;
explicit param_type(double mean = 1.0);
double mean() 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 poisson_distribution(double mean = 1.0); // before C++20
poisson_distribution() : poisson_distribution(1.0) {} // C++20
explicit poisson_distribution(double mean); // C++20
explicit poisson_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 mean() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const poisson_distribution& x,
const poisson_distribution& y);
friend bool operator!=(const poisson_distribution& x,
const poisson_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const poisson_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
poisson_distribution& x);
};
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(result_type lambda = 1.0);
result_type 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); // before C++20
exponential_distribution() : exponential_distribution(1.0) {} // C++20
explicit exponential_distribution(RealType lambda); // C++20
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
result_type 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
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef gamma_distribution distribution_type;
explicit param_type(result_type alpha = 1, result_type beta = 1);
result_type alpha() const;
result_type beta() 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 gamma_distribution(RealType alpha = 0.0, RealType beta = 1.0); // before C++20
gamma_distribution() : gamma_distribution(0.0) {} // C++20
explicit gamma_distribution(RealType alpha, RealType beta = 1.0); // C++20
explicit gamma_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 alpha() const;
result_type beta() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const gamma_distribution& x,
const gamma_distribution& y);
friend bool operator!=(const gamma_distribution& x,
const gamma_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const gamma_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
gamma_distribution& x);
};
template<class RealType = double>
class weibull_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef weibull_distribution distribution_type;
explicit param_type(result_type alpha = 1, result_type beta = 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);
};
// constructor and reset functions
explicit weibull_distribution(RealType a = 1.0, RealType b = 1.0); // before C++20
weibull_distribution() : weibull_distribution(1.0) {} // C++20
explicit weibull_distribution(RealType a, RealType b = 1.0); // C++20
explicit weibull_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 weibull_distribution& x,
const weibull_distribution& y);
friend bool operator!=(const weibull_distribution& x,
const weibull_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const weibull_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
weibull_distribution& x);
};
template<class RealType = double>
class extreme_value_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef extreme_value_distribution distribution_type;
explicit param_type(result_type a = 0, result_type 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);
};
// constructor and reset functions
explicit extreme_value_distribution(RealType a = 0.0, RealType b = 1.0); // before C++20
extreme_value_distribution() : extreme_value_distribution(0.0) {} // C++20
explicit extreme_value_distribution(RealType a, RealType b = 1.0); // C++20
explicit extreme_value_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 extreme_value_distribution& x,
const extreme_value_distribution& y);
friend bool operator!=(const extreme_value_distribution& x,
const extreme_value_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const extreme_value_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
extreme_value_distribution& x);
};
template<class RealType = double>
class normal_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef normal_distribution distribution_type;
explicit param_type(result_type mean = 0, result_type stddev = 1);
result_type mean() const;
result_type stddev() 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 normal_distribution(RealType mean = 0.0, RealType stddev = 1.0); // before C++20
normal_distribution() : normal_distribution(0.0) {} // C++20
explicit normal_distribution(RealType mean, RealType stddev = 1.0); // C++20
explicit normal_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 mean() const;
result_type stddev() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const normal_distribution& x,
const normal_distribution& y);
friend bool operator!=(const normal_distribution& x,
const normal_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const normal_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
normal_distribution& x);
};
template<class RealType = double>
class lognormal_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef lognormal_distribution distribution_type;
explicit param_type(result_type m = 0, result_type s = 1);
result_type m() const;
result_type s() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
explicit lognormal_distribution(RealType mean = 0.0, RealType stddev = 1.0); // before C++20
lognormal_distribution() : lognormal_distribution(0.0) {} // C++20
explicit lognormal_distribution(RealType mean, RealType stddev = 1.0); // C++20
explicit lognormal_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 m() const;
result_type s() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const lognormal_distribution& x,
const lognormal_distribution& y);
friend bool operator!=(const lognormal_distribution& x,
const lognormal_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const lognormal_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
lognormal_distribution& x);
};
template<class RealType = double>
class chi_squared_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef chi_squared_distribution distribution_type;
explicit param_type(result_type n = 1);
result_type n() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
explicit chi_squared_distribution(RealType n = 1.0); // before C++20
chi_squared_distribution() : chi_squared_distribution(1.0) {} // C++20
explicit chi_squared_distribution(RealType n); // C++20
explicit chi_squared_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 n() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const chi_squared_distribution& x,
const chi_squared_distribution& y);
friend bool operator!=(const chi_squared_distribution& x,
const chi_squared_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const chi_squared_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
chi_squared_distribution& x);
};
template<class RealType = double>
class cauchy_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef cauchy_distribution distribution_type;
explicit param_type(result_type a = 0, result_type 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);
};
// constructor and reset functions
explicit cauchy_distribution(RealType a = 0.0, RealType b = 1.0); // before C++20
cauchy_distribution() : cauchy_distribution(0.0) {} // C++20
explicit cauchy_distribution(RealType a, RealType b = 1.0); // C++20
explicit cauchy_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 cauchy_distribution& x,
const cauchy_distribution& y);
friend bool operator!=(const cauchy_distribution& x,
const cauchy_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const cauchy_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
cauchy_distribution& x);
};
template<class RealType = double>
class fisher_f_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef fisher_f_distribution distribution_type;
explicit param_type(result_type m = 1, result_type n = 1);
result_type m() const;
result_type n() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
explicit fisher_f_distribution(RealType m = 1.0, RealType n = 1.0); // before C++20
fisher_f_distribution() : fisher_f_distribution(1.0) {} // C++20
explicit fisher_f_distribution(RealType m, RealType n = 1.0); // C++20
explicit fisher_f_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 m() const;
result_type n() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const fisher_f_distribution& x,
const fisher_f_distribution& y);
friend bool operator!=(const fisher_f_distribution& x,
const fisher_f_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const fisher_f_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
fisher_f_distribution& x);
};
template<class RealType = double>
class student_t_distribution
{
public:
// types
typedef RealType result_type;
class param_type
{
public:
typedef student_t_distribution distribution_type;
explicit param_type(result_type n = 1);
result_type n() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
explicit student_t_distribution(RealType n = 1.0); // before C++20
student_t_distribution() : student_t_distribution(1.0) {} // C++20
explicit student_t_distribution(RealType n); // C++20
explicit student_t_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 n() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const student_t_distribution& x,
const student_t_distribution& y);
friend bool operator!=(const student_t_distribution& x,
const student_t_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const student_t_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
student_t_distribution& x);
};
template<class IntType = int>
class discrete_distribution
{
public:
// types
typedef IntType result_type;
class param_type
{
public:
typedef discrete_distribution distribution_type;
param_type();
template<class InputIterator>
param_type(InputIterator firstW, InputIterator lastW);
param_type(initializer_list<double> wl);
template<class UnaryOperation>
param_type(size_t nw, double xmin, double xmax, UnaryOperation fw);
vector<double> probabilities() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
discrete_distribution();
template<class InputIterator>
discrete_distribution(InputIterator firstW, InputIterator lastW);
discrete_distribution(initializer_list<double> wl);
template<class UnaryOperation>
discrete_distribution(size_t nw, double xmin, double xmax,
UnaryOperation fw);
explicit discrete_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
vector<double> probabilities() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const discrete_distribution& x,
const discrete_distribution& y);
friend bool operator!=(const discrete_distribution& x,
const discrete_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const discrete_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
discrete_distribution& x);
};
template<class RealType = double>
class piecewise_constant_distribution
{
// types
typedef RealType result_type;
class param_type
{
public:
typedef piecewise_constant_distribution distribution_type;
param_type();
template<class InputIteratorB, class InputIteratorW>
param_type(InputIteratorB firstB, InputIteratorB lastB,
InputIteratorW firstW);
template<class UnaryOperation>
param_type(initializer_list<result_type> bl, UnaryOperation fw);
template<class UnaryOperation>
param_type(size_t nw, result_type xmin, result_type xmax,
UnaryOperation fw);
vector<result_type> intervals() const;
vector<result_type> densities() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
piecewise_constant_distribution();
template<class InputIteratorB, class InputIteratorW>
piecewise_constant_distribution(InputIteratorB firstB,
InputIteratorB lastB,
InputIteratorW firstW);
template<class UnaryOperation>
piecewise_constant_distribution(initializer_list<result_type> bl,
UnaryOperation fw);
template<class UnaryOperation>
piecewise_constant_distribution(size_t nw, result_type xmin,
result_type xmax, UnaryOperation fw);
explicit piecewise_constant_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
vector<result_type> intervals() const;
vector<result_type> densities() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const piecewise_constant_distribution& x,
const piecewise_constant_distribution& y);
friend bool operator!=(const piecewise_constant_distribution& x,
const piecewise_constant_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const piecewise_constant_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
piecewise_constant_distribution& x);
};
template<class RealType = double>
class piecewise_linear_distribution
{
// types
typedef RealType result_type;
class param_type
{
public:
typedef piecewise_linear_distribution distribution_type;
param_type();
template<class InputIteratorB, class InputIteratorW>
param_type(InputIteratorB firstB, InputIteratorB lastB,
InputIteratorW firstW);
template<class UnaryOperation>
param_type(initializer_list<result_type> bl, UnaryOperation fw);
template<class UnaryOperation>
param_type(size_t nw, result_type xmin, result_type xmax,
UnaryOperation fw);
vector<result_type> intervals() const;
vector<result_type> densities() const;
friend bool operator==(const param_type& x, const param_type& y);
friend bool operator!=(const param_type& x, const param_type& y);
};
// constructor and reset functions
piecewise_linear_distribution();
template<class InputIteratorB, class InputIteratorW>
piecewise_linear_distribution(InputIteratorB firstB,
InputIteratorB lastB,
InputIteratorW firstW);
template<class UnaryOperation>
piecewise_linear_distribution(initializer_list<result_type> bl,
UnaryOperation fw);
template<class UnaryOperation>
piecewise_linear_distribution(size_t nw, result_type xmin,
result_type xmax, UnaryOperation fw);
explicit piecewise_linear_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
vector<result_type> intervals() const;
vector<result_type> densities() const;
param_type param() const;
void param(const param_type& parm);
result_type min() const;
result_type max() const;
friend bool operator==(const piecewise_linear_distribution& x,
const piecewise_linear_distribution& y);
friend bool operator!=(const piecewise_linear_distribution& x,
const piecewise_linear_distribution& y);
template <class charT, class traits>
friend
basic_ostream<charT, traits>&
operator<<(basic_ostream<charT, traits>& os,
const piecewise_linear_distribution& x);
template <class charT, class traits>
friend
basic_istream<charT, traits>&
operator>>(basic_istream<charT, traits>& is,
piecewise_linear_distribution& x);
};
} // std
*/
#include <__config>
#include <__random/uniform_int_distribution.h>
#include <algorithm>
#include <cmath>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iosfwd>
#include <limits>
#include <numeric>
#include <string>
#include <type_traits>
#include <vector>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
_LIBCPP_BEGIN_NAMESPACE_STD
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
// [rand.req.urng]
template<class _Gen>
concept uniform_random_bit_generator =
invocable<_Gen&> && unsigned_integral<invoke_result_t<_Gen&>> &&
requires {
{ _Gen::min() } -> same_as<invoke_result_t<_Gen&>>;
{ _Gen::max() } -> same_as<invoke_result_t<_Gen&>>;
requires bool_constant<(_Gen::min() < _Gen::max())>::value;
};
#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
// __is_seed_sequence
template <class _Sseq, class _Engine>
struct __is_seed_sequence
{
static _LIBCPP_CONSTEXPR const bool value =
!is_convertible<_Sseq, typename _Engine::result_type>::value &&
!is_same<typename remove_cv<_Sseq>::type, _Engine>::value;
};
// linear_congruential_engine
template <unsigned long long __a, unsigned long long __c,
unsigned long long __m, unsigned long long _Mp,
bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a),
bool _OverflowOK = ((__m | (__m-1)) > __m), // m = 2^n
bool _SchrageOK = (__a != 0 && __m != 0 && __m % __a <= __m / __a)> // r <= q
struct __lce_alg_picker
{
static_assert(__a != 0 || __m != 0 || !_MightOverflow || _OverflowOK || _SchrageOK,
"The current values of a, c, and m cannot generate a number "
"within bounds of linear_congruential_engine.");
static _LIBCPP_CONSTEXPR const bool __use_schrage = _MightOverflow &&
!_OverflowOK &&
_SchrageOK;
};
template <unsigned long long __a, unsigned long long __c,
unsigned long long __m, unsigned long long _Mp,
bool _UseSchrage = __lce_alg_picker<__a, __c, __m, _Mp>::__use_schrage>
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;
_LIBCPP_INLINE_VISIBILITY
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;
_LIBCPP_INLINE_VISIBILITY
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;
_LIBCPP_INLINE_VISIBILITY
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;
_LIBCPP_INLINE_VISIBILITY
static result_type next(result_type __x)
{
return __a * __x + __c;
}
};
// 32
template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true>
{
typedef unsigned result_type;
_LIBCPP_INLINE_VISIBILITY
static result_type next(result_type __x)
{
const result_type __a = static_cast<result_type>(_Ap);
const result_type __c = static_cast<result_type>(_Cp);
const result_type __m = static_cast<result_type>(_Mp);
// 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 _Ap, unsigned long long _Mp>
struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true>
{
typedef unsigned result_type;
_LIBCPP_INLINE_VISIBILITY
static result_type next(result_type __x)
{
const result_type __a = static_cast<result_type>(_Ap);
const result_type __m = static_cast<result_type>(_Mp);
// 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 _Ap, unsigned long long _Cp, unsigned long long _Mp>
struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false>
{
typedef unsigned result_type;
_LIBCPP_INLINE_VISIBILITY
static result_type next(result_type __x)
{
const result_type __a = static_cast<result_type>(_Ap);
const result_type __c = static_cast<result_type>(_Cp);
const result_type __m = static_cast<result_type>(_Mp);
return (__a * __x + __c) % __m;
}
};
template <unsigned long long _Ap, unsigned long long _Cp>
struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false>
{
typedef unsigned result_type;
_LIBCPP_INLINE_VISIBILITY
static result_type next(result_type __x)
{
const result_type __a = static_cast<result_type>(_Ap);
const result_type __c = static_cast<result_type>(_Cp);
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;
_LIBCPP_INLINE_VISIBILITY
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 _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
template <class _CharT, class _Traits,
class _Up, _Up _Ap, _Up _Cp, _Up _Np>
_LIBCPP_INLINE_VISIBILITY
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
template <class _CharT, class _Traits,
class _Up, _Up _Ap, _Up _Cp, _Up _Np>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
class _LIBCPP_TEMPLATE_VIS linear_congruential_engine
{
public:
// types
typedef _UIntType result_type;
private:
result_type __x_;
static _LIBCPP_CONSTEXPR const result_type _Mp = 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");
static_assert(is_unsigned<_UIntType>::value, "_UIntType must be unsigned type");
public:
static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u;
static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u;
static_assert(_Min < _Max, "linear_congruential_engine invalid parameters");
// engine characteristics
static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
static _LIBCPP_CONSTEXPR const result_type increment = __c;
static _LIBCPP_CONSTEXPR const result_type modulus = __m;
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
// constructors and seeding functions
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
linear_congruential_engine() : linear_congruential_engine(default_seed) {}
_LIBCPP_INLINE_VISIBILITY
explicit linear_congruential_engine(result_type __s) { seed(__s); }
#else
_LIBCPP_INLINE_VISIBILITY
explicit linear_congruential_engine(result_type __s = default_seed) {
seed(__s);
}
#endif
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
explicit linear_congruential_engine(_Sseq& __q,
typename enable_if<__is_seed_sequence<_Sseq, linear_congruential_engine>::value>::type* = 0)
{seed(__q);}
_LIBCPP_INLINE_VISIBILITY
void seed(result_type __s = default_seed)
{seed(integral_constant<bool, __m == 0>(),
integral_constant<bool, __c == 0>(), __s);}
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_seed_sequence<_Sseq, linear_congruential_engine>::value,
void
>::type
seed(_Sseq& __q)
{__seed(__q, integral_constant<unsigned,
1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
: (__m > 0x100000000ull))>());}
// generating functions
_LIBCPP_INLINE_VISIBILITY
result_type operator()()
{return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));}
_LIBCPP_INLINE_VISIBILITY
void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
friend _LIBCPP_INLINE_VISIBILITY
bool operator==(const linear_congruential_engine& __x,
const linear_congruential_engine& __y)
{return __x.__x_ == __y.__x_;}
friend _LIBCPP_INLINE_VISIBILITY
bool operator!=(const linear_congruential_engine& __x,
const linear_congruential_engine& __y)
{return !(__x == __y);}
private:
_LIBCPP_INLINE_VISIBILITY
void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
_LIBCPP_INLINE_VISIBILITY
void seed(true_type, false_type, result_type __s) {__x_ = __s;}
_LIBCPP_INLINE_VISIBILITY
void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
1 : __s % __m;}
_LIBCPP_INLINE_VISIBILITY
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 _Up, _Up _Ap, _Up _Cp, _Up _Np>
friend
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
template <class _CharT, class _Traits,
class _Up, _Up _Ap, _Up _Cp, _Up _Np>
friend
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
};
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
linear_congruential_engine<_UIntType, __a, __c, __m>::increment;
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
_LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
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 _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
inline _LIBCPP_INLINE_VISIBILITY
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
{
__save_flags<_CharT, _Traits> __lx(__os);
typedef basic_ostream<_CharT, _Traits> _Ostream;
__os.flags(_Ostream::dec | _Ostream::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> __lx(__is);
typedef basic_istream<_CharT, _Traits> _Istream;
__is.flags(_Istream::dec | _Istream::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 linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
minstd_rand;
typedef minstd_rand default_random_engine;
// 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 _LIBCPP_TEMPLATE_VIS mersenne_twister_engine;
template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
bool
operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y);
template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
_LIBCPP_INLINE_VISIBILITY
bool
operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __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 _LIBCPP_TEMPLATE_VIS 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 _LIBCPP_CONSTEXPR 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 _LIBCPP_CONSTEXPR const result_type _Min = 0;
static _LIBCPP_CONSTEXPR 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 _LIBCPP_CONSTEXPR const size_t word_size = __w;
static _LIBCPP_CONSTEXPR const size_t state_size = __n;
static _LIBCPP_CONSTEXPR const size_t shift_size = __m;
static _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
static _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
static _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
static _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
static _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
static _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
static _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
static _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
static _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
static _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
static _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
// constructors and seeding functions
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
mersenne_twister_engine() : mersenne_twister_engine(default_seed) {}
_LIBCPP_INLINE_VISIBILITY
explicit mersenne_twister_engine(result_type __sd) { seed(__sd); }
#else
_LIBCPP_INLINE_VISIBILITY
explicit mersenne_twister_engine(result_type __sd = default_seed) {
seed(__sd);
}
#endif
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
explicit mersenne_twister_engine(_Sseq& __q,
typename enable_if<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value>::type* = 0)
{seed(__q);}
void seed(result_type __sd = default_seed);
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_seed_sequence<_Sseq, mersenne_twister_engine>::value,
void
>::type
seed(_Sseq& __q)
{__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
// generating functions
result_type operator()();
_LIBCPP_INLINE_VISIBILITY
void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
friend
bool
operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y);
template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
friend
bool
operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
friend
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
friend
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __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>
_LIBCPP_INLINE_VISIBILITY
static
typename enable_if
<
__count < __w,
result_type
>::type
__lshift(result_type __x) {return (__x << __count) & _Max;}
template <size_t __count>
_LIBCPP_INLINE_VISIBILITY
static
typename enable_if
<
(__count >= __w),
result_type
>::type
__lshift(result_type) {return result_type(0);}
template <size_t __count>
_LIBCPP_INLINE_VISIBILITY
static
typename enable_if
<
__count < _Dt,
result_type
>::type
__rshift(result_type __x) {return __x >> __count;}
template <size_t __count>
_LIBCPP_INLINE_VISIBILITY
static
typename enable_if
<
(__count >= _Dt),
result_type
>::type
__rshift(result_type) {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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::word_size;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::state_size;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::shift_size;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mask_bits;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::xor_mask;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_u;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_d;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_s;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_b;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_t;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_c;
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>
_LIBCPP_CONSTEXPR const size_t
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_l;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::initialization_multiplier;
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>
_LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::default_seed;
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)
_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
{ // __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] = result_type(1) << (__w - 1);
}
}
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] = result_type(1) << (__w - 1);
}
}
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 _Yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
const size_t __k = (__i_ + __m) % __n;
__x_[__i_] = __x_[__k] ^ __rshift<1>(_Yp) ^ (__a * (_Yp & 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 _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
bool
operator==(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y)
{
if (__x.__i_ == __y.__i_)
return _VSTD::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
if (__x.__i_ == 0 || __y.__i_ == 0)
{
size_t __j = _VSTD::min(_Np - __x.__i_, _Np - __y.__i_);
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
__y.__x_ + __y.__i_))
return false;
if (__x.__i_ == 0)
return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
return _VSTD::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
}
if (__x.__i_ < __y.__i_)
{
size_t __j = _Np - __y.__i_;
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
__y.__x_ + __y.__i_))
return false;
if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np,
__y.__x_))
return false;
return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
__y.__x_ + (_Np - (__x.__i_ + __j)));
}
size_t __j = _Np - __x.__i_;
if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
__x.__x_ + __x.__i_))
return false;
if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np,
__x.__x_))
return false;
return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
__x.__x_ + (_Np - (__y.__i_ + __j)));
}
template <class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __y)
{
return !(__x == __y);
}
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__os);
typedef basic_ostream<_CharT, _Traits> _Ostream;
__os.flags(_Ostream::dec | _Ostream::left);
_CharT __sp = __os.widen(' ');
__os.fill(__sp);
__os << __x.__x_[__x.__i_];
for (size_t __j = __x.__i_ + 1; __j < _Np; ++__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 _UInt, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
_UInt _Ap, size_t _Up, _UInt _Dp, size_t _Sp,
_UInt _Bp, size_t _Tp, _UInt _Cp, size_t _Lp, _UInt _Fp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
mersenne_twister_engine<_UInt, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
_Bp, _Tp, _Cp, _Lp, _Fp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__is);
typedef basic_istream<_CharT, _Traits> _Istream;
__is.flags(_Istream::dec | _Istream::skipws);
_UInt __t[_Np];
for (size_t __i = 0; __i < _Np; ++__i)
__is >> __t[__i];
if (!__is.fail())
{
for (size_t __i = 0; __i < _Np; ++__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 _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
_LIBCPP_INLINE_VISIBILITY
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template<class _UIntType, size_t __w, size_t __s, size_t __r>
class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine
{
public:
// types
typedef _UIntType result_type;
private:
result_type __x_[__r];
result_type __c_;
size_t __i_;
static _LIBCPP_CONSTEXPR 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 _LIBCPP_CONSTEXPR const result_type _Min = 0;
static _LIBCPP_CONSTEXPR 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 _LIBCPP_CONSTEXPR const size_t word_size = __w;
static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
static _LIBCPP_CONSTEXPR const size_t long_lag = __r;
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
// constructors and seeding functions
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
subtract_with_carry_engine() : subtract_with_carry_engine(default_seed) {}
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(result_type __sd) { seed(__sd); }
#else
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(result_type __sd = default_seed) {
seed(__sd);
}
#endif
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
explicit subtract_with_carry_engine(_Sseq& __q,
typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0)
{seed(__q);}
_LIBCPP_INLINE_VISIBILITY
void seed(result_type __sd = default_seed)
{seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value,
void
>::type
seed(_Sseq& __q)
{__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
// generating functions
result_type operator()();
_LIBCPP_INLINE_VISIBILITY
void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x);
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
friend
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __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>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
template<class _UIntType, size_t __w, size_t __s, size_t __r>
_LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
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)
{
result_type __e0 = __e();
__x_[__i] = static_cast<result_type>(
(__e0 + ((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 _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
bool
operator==(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
{
if (__x.__c_ != __y.__c_)
return false;
if (__x.__i_ == __y.__i_)
return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
if (__x.__i_ == 0 || __y.__i_ == 0)
{
size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
__y.__x_ + __y.__i_))
return false;
if (__x.__i_ == 0)
return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
}
if (__x.__i_ < __y.__i_)
{
size_t __j = _Rp - __y.__i_;
if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
__y.__x_ + __y.__i_))
return false;
if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
__y.__x_))
return false;
return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
__y.__x_ + (_Rp - (__x.__i_ + __j)));
}
size_t __j = _Rp - __x.__i_;
if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
__x.__x_ + __x.__i_))
return false;
if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
__x.__x_))
return false;
return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
__x.__x_ + (_Rp - (__y.__i_ + __j)));
}
template<class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
inline _LIBCPP_INLINE_VISIBILITY
bool
operator!=(
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __y)
{
return !(__x == __y);
}
template <class _CharT, class _Traits,
class _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__os);
typedef basic_ostream<_CharT, _Traits> _Ostream;
__os.flags(_Ostream::dec | _Ostream::left);
_CharT __sp = __os.widen(' ');
__os.fill(__sp);
__os << __x.__x_[__x.__i_];
for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__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 _UInt, size_t _Wp, size_t _Sp, size_t _Rp>
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
subtract_with_carry_engine<_UInt, _Wp, _Sp, _Rp>& __x)
{
__save_flags<_CharT, _Traits> __lx(__is);
typedef basic_istream<_CharT, _Traits> _Istream;
__is.flags(_Istream::dec | _Istream::skipws);
_UInt __t[_Rp+1];
for (size_t __i = 0; __i < _Rp+1; ++__i)
__is >> __t[__i];
if (!__is.fail())
{
for (size_t __i = 0; __i < _Rp; ++__i)
__x.__x_[__i] = __t[__i];
__x.__c_ = __t[_Rp];
__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 _LIBCPP_TEMPLATE_VIS 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");
static_assert(__r <= INT_MAX, "discard_block_engine invalid parameters");
public:
// types
typedef typename _Engine::result_type result_type;
// engine characteristics
static _LIBCPP_CONSTEXPR const size_t block_size = __p;
static _LIBCPP_CONSTEXPR const size_t used_block = __r;
#ifdef _LIBCPP_CXX03_LANG
static const result_type _Min = _Engine::_Min;
static const result_type _Max = _Engine::_Max;
#else
static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
#endif
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type min() { return _Engine::min(); }
_LIBCPP_INLINE_VISIBILITY
static _LIBCPP_CONSTEXPR result_type max() { return _Engine::max(); }
// constructors and seeding functions
_LIBCPP_INLINE_VISIBILITY
discard_block_engine() : __n_(0) {}
_LIBCPP_INLINE_VISIBILITY
explicit discard_block_engine(const _Engine& __e)
: __e_(__e), __n_(0) {}
#ifndef _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
explicit discard_block_engine(_Engine&& __e)
: __e_(_VSTD::move(__e)), __n_(0) {}
#endif // _LIBCPP_CXX03_LANG
_LIBCPP_INLINE_VISIBILITY
explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
explicit discard_block_engine(_Sseq& __q,
typename enable_if<__is_seed_sequence<_Sseq, discard_block_engine>::value &&
!is_convertible<_Sseq, _Engine>::value>::type* = 0)
: __e_(__q), __n_(0) {}
_LIBCPP_INLINE_VISIBILITY
void seed() {__e_.seed(); __n_ = 0;}
_LIBCPP_INLINE_VISIBILITY
void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
template<class _Sseq>
_LIBCPP_INLINE_VISIBILITY
typename enable_if
<
__is_seed_sequence<_Sseq, discard_block_engine>::value,
void
>::type
seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
// generating functions
result_type operator()();
_LIBCPP_INLINE_VISIBILITY
void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
// property functions
_LIBCPP_INLINE_VISIBILITY
const _Engine& base() const _NOEXCEPT {return __e_;}
template<class _Eng, size_t _Pp, size_t _Rp>
friend
bool
operator==(
const discard_block_engine<_Eng, _Pp, _Rp>& __x,
const discard_block_engine<_Eng, _Pp, _Rp>& __y);
template<class _Eng, size_t _Pp, size_t _Rp>
friend
bool
operator!=(
const discard_block_engine<_Eng, _Pp, _Rp>& __x,
const discard_block_engine<_Eng, _Pp, _Rp>& __y);
template <class _CharT, class _Traits,
class _Eng, size_t _Pp, size_t _Rp>
friend
basic_ostream<_CharT, _Traits>&
operator<<(basic_ostream<_CharT, _Traits>& __os,
const discard_block_engine<_Eng, _Pp, _Rp>& __x);
template <class _CharT, class _Traits,
class _Eng, size_t _Pp, size_t _Rp>
friend
basic_istream<_CharT, _Traits>&
operator>>(basic_istream<_CharT, _Traits>& __is,
discard_block_engine<_Eng, _Pp, _Rp>& __x);
};
template<class _Engine, size_t __p, size_t __r>
_LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::block_size;
template<class _Engine, size_t __p, size_t __r>
_LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::used_block;
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_ >= static_cast<int>(__r))