contrib/libc++/include/random

   1 // -*- C++ -*-
   2 //===--------------------------- random -----------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_RANDOM
  12 #define _LIBCPP_RANDOM
  13
  14 /*
  15     random synopsis
  16
  17 #include <initializer_list>
  18
  19 namespace std
  20 {
  21
  22 // Engines
  23
  24 template <class UIntType, UIntType a, UIntType c, UIntType m>
  25 class linear_congruential_engine
  26 {
  27 public:
  28     // types
  29     typedef UIntType result_type;
  30
  31     // engine characteristics
  32     static constexpr result_type multiplier = a;
  33     static constexpr result_type increment = c;
  34     static constexpr result_type modulus = m;
  35     static constexpr result_type min() { return c == 0u ? 1u: 0u;}
  36     static constexpr result_type max() { return m - 1u;}
  37     static constexpr result_type default_seed = 1u;
  38
  39     // constructors and seeding functions
  40     explicit linear_congruential_engine(result_type s = default_seed);
  41     template<class Sseq> explicit linear_congruential_engine(Sseq& q);
  42     void seed(result_type s = default_seed);
  43     template<class Sseq> void seed(Sseq& q);
  44
  45     // generating functions
  46     result_type operator()();
  47     void discard(unsigned long long z);
  48 };
  49
  50 template <class UIntType, UIntType a, UIntType c, UIntType m>
  51 bool
  52 operator==(const linear_congruential_engine<UIntType, a, c, m>& x,
  53            const linear_congruential_engine<UIntType, a, c, m>& y);
  54
  55 template <class UIntType, UIntType a, UIntType c, UIntType m>
  56 bool
  57 operator!=(const linear_congruential_engine<UIntType, a, c, m>& x,
  58            const linear_congruential_engine<UIntType, a, c, m>& y);
  59
  60 template <class charT, class traits,
  61           class UIntType, UIntType a, UIntType c, UIntType m>
  62 basic_ostream<charT, traits>&
  63 operator<<(basic_ostream<charT, traits>& os,
  64            const linear_congruential_engine<UIntType, a, c, m>& x);
  65
  66 template <class charT, class traits,
  67           class UIntType, UIntType a, UIntType c, UIntType m>
  68 basic_istream<charT, traits>&
  69 operator>>(basic_istream<charT, traits>& is,
  70            linear_congruential_engine<UIntType, a, c, m>& x);
  71
  72 template <class UIntType, size_t w, size_t n, size_t m, size_t r,
  73           UIntType a, size_t u, UIntType d, size_t s,
  74           UIntType b, size_t t, UIntType c, size_t l, UIntType f>
  75 class mersenne_twister_engine
  76 {
  77 public:
  78     // types
  79     typedef UIntType result_type;
  80
  81     // engine characteristics
  82     static constexpr size_t word_size = w;
  83     static constexpr size_t state_size = n;
  84     static constexpr size_t shift_size = m;
  85     static constexpr size_t mask_bits = r;
  86     static constexpr result_type xor_mask = a;
  87     static constexpr size_t tempering_u = u;
  88     static constexpr result_type tempering_d = d;
  89     static constexpr size_t tempering_s = s;
  90     static constexpr result_type tempering_b = b;
  91     static constexpr size_t tempering_t = t;
  92     static constexpr result_type tempering_c = c;
  93     static constexpr size_t tempering_l = l;
  94     static constexpr result_type initialization_multiplier = f;
  95     static constexpr result_type min () { return 0; }
  96     static constexpr result_type max() { return 2^w - 1; }
  97     static constexpr result_type default_seed = 5489u;
  98
  99     // constructors and seeding functions
 100     explicit mersenne_twister_engine(result_type value = default_seed);
 101     template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
 102     void seed(result_type value = default_seed);
 103     template<class Sseq> void seed(Sseq& q);
 104
 105     // generating functions
 106     result_type operator()();
 107     void discard(unsigned long long z);
 108 };
 109
 110 template <class UIntType, size_t w, size_t n, size_t m, size_t r,
 111           UIntType a, size_t u, UIntType d, size_t s,
 112           UIntType b, size_t t, UIntType c, size_t l, UIntType f>
 113 bool
 114 operator==(
 115     const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
 116     const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
 117
 118 template <class UIntType, size_t w, size_t n, size_t m, size_t r,
 119           UIntType a, size_t u, UIntType d, size_t s,
 120           UIntType b, size_t t, UIntType c, size_t l, UIntType f>
 121 bool
 122 operator!=(
 123     const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x,
 124     const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& y);
 125
 126 template <class charT, class traits,
 127           class UIntType, size_t w, size_t n, size_t m, size_t r,
 128           UIntType a, size_t u, UIntType d, size_t s,
 129           UIntType b, size_t t, UIntType c, size_t l, UIntType f>
 130 basic_ostream<charT, traits>&
 131 operator<<(basic_ostream<charT, traits>& os,
 132            const mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
 133
 134 template <class charT, class traits,
 135           class UIntType, size_t w, size_t n, size_t m, size_t r,
 136           UIntType a, size_t u, UIntType d, size_t s,
 137           UIntType b, size_t t, UIntType c, size_t l, UIntType f>
 138 basic_istream<charT, traits>&
 139 operator>>(basic_istream<charT, traits>& is,
 140            mersenne_twister_engine<UIntType, w, n, m, r, a, u, d, s, b, t, c, l, f>& x);
 141
 142 template<class UIntType, size_t w, size_t s, size_t r>
 143 class subtract_with_carry_engine
 144 {
 145 public:
 146     // types
 147     typedef UIntType result_type;
 148
 149     // engine characteristics
 150     static constexpr size_t word_size = w;
 151     static constexpr size_t short_lag = s;
 152     static constexpr size_t long_lag = r;
 153     static constexpr result_type min() { return 0; }
 154     static constexpr result_type max() { return m-1; }
 155     static constexpr result_type default_seed = 19780503u;
 156
 157     // constructors and seeding functions
 158     explicit subtract_with_carry_engine(result_type value = default_seed);
 159     template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
 160     void seed(result_type value = default_seed);
 161     template<class Sseq> void seed(Sseq& q);
 162
 163     // generating functions
 164     result_type operator()();
 165     void discard(unsigned long long z);
 166 };
 167
 168 template<class UIntType, size_t w, size_t s, size_t r>
 169 bool
 170 operator==(
 171     const subtract_with_carry_engine<UIntType, w, s, r>& x,
 172     const subtract_with_carry_engine<UIntType, w, s, r>& y);
 173
 174 template<class UIntType, size_t w, size_t s, size_t r>
 175 bool
 176 operator!=(
 177     const subtract_with_carry_engine<UIntType, w, s, r>& x,
 178     const subtract_with_carry_engine<UIntType, w, s, r>& y);
 179
 180 template <class charT, class traits,
 181           class UIntType, size_t w, size_t s, size_t r>
 182 basic_ostream<charT, traits>&
 183 operator<<(basic_ostream<charT, traits>& os,
 184            const subtract_with_carry_engine<UIntType, w, s, r>& x);
 185
 186 template <class charT, class traits,
 187           class UIntType, size_t w, size_t s, size_t r>
 188 basic_istream<charT, traits>&
 189 operator>>(basic_istream<charT, traits>& is,
 190            subtract_with_carry_engine<UIntType, w, s, r>& x);
 191
 192 template<class Engine, size_t p, size_t r>
 193 class discard_block_engine
 194 {
 195 public:
 196     // types
 197     typedef typename Engine::result_type result_type;
 198
 199     // engine characteristics
 200     static constexpr size_t block_size = p;
 201     static constexpr size_t used_block = r;
 202     static constexpr result_type min() { return Engine::min(); }
 203     static constexpr result_type max() { return Engine::max(); }
 204
 205     // constructors and seeding functions
 206     discard_block_engine();
 207     explicit discard_block_engine(const Engine& e);
 208     explicit discard_block_engine(Engine&& e);
 209     explicit discard_block_engine(result_type s);
 210     template<class Sseq> explicit discard_block_engine(Sseq& q);
 211     void seed();
 212     void seed(result_type s);
 213     template<class Sseq> void seed(Sseq& q);
 214
 215     // generating functions
 216     result_type operator()();
 217     void discard(unsigned long long z);
 218
 219     // property functions
 220     const Engine& base() const noexcept;
 221 };
 222
 223 template<class Engine, size_t p, size_t r>
 224 bool
 225 operator==(
 226     const discard_block_engine<Engine, p, r>& x,
 227     const discard_block_engine<Engine, p, r>& y);
 228
 229 template<class Engine, size_t p, size_t r>
 230 bool
 231 operator!=(
 232     const discard_block_engine<Engine, p, r>& x,
 233     const discard_block_engine<Engine, p, r>& y);
 234
 235 template <class charT, class traits,
 236           class Engine, size_t p, size_t r>
 237 basic_ostream<charT, traits>&
 238 operator<<(basic_ostream<charT, traits>& os,
 239            const discard_block_engine<Engine, p, r>& x);
 240
 241 template <class charT, class traits,
 242           class Engine, size_t p, size_t r>
 243 basic_istream<charT, traits>&
 244 operator>>(basic_istream<charT, traits>& is,
 245            discard_block_engine<Engine, p, r>& x);
 246
 247 template<class Engine, size_t w, class UIntType>
 248 class independent_bits_engine
 249 {
 250 public:
 251     // types
 252     typedef UIntType result_type;
 253
 254     // engine characteristics
 255     static constexpr result_type min() { return 0; }
 256     static constexpr result_type max() { return 2^w - 1; }
 257
 258     // constructors and seeding functions
 259     independent_bits_engine();
 260     explicit independent_bits_engine(const Engine& e);
 261     explicit independent_bits_engine(Engine&& e);
 262     explicit independent_bits_engine(result_type s);
 263     template<class Sseq> explicit independent_bits_engine(Sseq& q);
 264     void seed();
 265     void seed(result_type s);
 266     template<class Sseq> void seed(Sseq& q);
 267
 268     // generating functions
 269     result_type operator()(); void discard(unsigned long long z);
 270
 271     // property functions
 272     const Engine& base() const noexcept;
 273 };
 274
 275 template<class Engine, size_t w, class UIntType>
 276 bool
 277 operator==(
 278     const independent_bits_engine<Engine, w, UIntType>& x,
 279     const independent_bits_engine<Engine, w, UIntType>& y);
 280
 281 template<class Engine, size_t w, class UIntType>
 282 bool
 283 operator!=(
 284     const independent_bits_engine<Engine, w, UIntType>& x,
 285     const independent_bits_engine<Engine, w, UIntType>& y);
 286
 287 template <class charT, class traits,
 288           class Engine, size_t w, class UIntType>
 289 basic_ostream<charT, traits>&
 290 operator<<(basic_ostream<charT, traits>& os,
 291            const independent_bits_engine<Engine, w, UIntType>& x);
 292
 293 template <class charT, class traits,
 294           class Engine, size_t w, class UIntType>
 295 basic_istream<charT, traits>&
 296 operator>>(basic_istream<charT, traits>& is,
 297            independent_bits_engine<Engine, w, UIntType>& x);
 298
 299 template<class Engine, size_t k>
 300 class shuffle_order_engine
 301 {
 302 public:
 303     // types
 304     typedef typename Engine::result_type result_type;
 305
 306     // engine characteristics
 307     static constexpr size_t table_size = k;
 308     static constexpr result_type min() { return Engine::min; }
 309     static constexpr result_type max() { return Engine::max; }
 310
 311     // constructors and seeding functions
 312     shuffle_order_engine();
 313     explicit shuffle_order_engine(const Engine& e);
 314     explicit shuffle_order_engine(Engine&& e);
 315     explicit shuffle_order_engine(result_type s);
 316     template<class Sseq> explicit shuffle_order_engine(Sseq& q);
 317     void seed();
 318     void seed(result_type s);
 319     template<class Sseq> void seed(Sseq& q);
 320
 321     // generating functions
 322     result_type operator()();
 323     void discard(unsigned long long z);
 324
 325     // property functions
 326     const Engine& base() const noexcept;
 327 };
 328
 329 template<class Engine, size_t k>
 330 bool
 331 operator==(
 332     const shuffle_order_engine<Engine, k>& x,
 333     const shuffle_order_engine<Engine, k>& y);
 334
 335 template<class Engine, size_t k>
 336 bool
 337 operator!=(
 338     const shuffle_order_engine<Engine, k>& x,
 339     const shuffle_order_engine<Engine, k>& y);
 340
 341 template <class charT, class traits,
 342           class Engine, size_t k>
 343 basic_ostream<charT, traits>&
 344 operator<<(basic_ostream<charT, traits>& os,
 345            const shuffle_order_engine<Engine, k>& x);
 346
 347 template <class charT, class traits,
 348           class Engine, size_t k>
 349 basic_istream<charT, traits>&
 350 operator>>(basic_istream<charT, traits>& is,
 351            shuffle_order_engine<Engine, k>& x);
 352
 353 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
 354                                                                    minstd_rand0;
 355 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
 356                                                                     minstd_rand;
 357 typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
 358                                 0x9908b0df,
 359                                 11, 0xffffffff,
 360                                 7,  0x9d2c5680,
 361                                 15, 0xefc60000,
 362                                 18, 1812433253>                         mt19937;
 363 typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
 364                                 0xb5026f5aa96619e9,
 365                                 29, 0x5555555555555555,
 366                                 17, 0x71d67fffeda60000,
 367                                 37, 0xfff7eee000000000,
 368                                 43, 6364136223846793005>             mt19937_64;
 369 typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>     ranlux24_base;
 370 typedef subtract_with_carry_engine<uint_fast64_t, 48,  5, 12>     ranlux48_base;
 371 typedef discard_block_engine<ranlux24_base, 223, 23>                   ranlux24;
 372 typedef discard_block_engine<ranlux48_base, 389, 11>                   ranlux48;
 373 typedef shuffle_order_engine<minstd_rand0, 256>                         knuth_b;
 374 typedef minstd_rand                                       default_random_engine;
 375
 376 // Generators
 377
 378 class random_device
 379 {
 380 public:
 381     // types
 382     typedef unsigned int result_type;
 383
 384     // generator characteristics
 385     static constexpr result_type min() { return numeric_limits<result_type>::min(); }
 386     static constexpr result_type max() { return numeric_limits<result_type>::max(); }
 387
 388     // constructors
 389     explicit random_device(const string& token = "/dev/urandom");
 390
 391     // generating functions
 392     result_type operator()();
 393
 394     // property functions
 395     double entropy() const noexcept;
 396
 397     // no copy functions
 398     random_device(const random_device& ) = delete;
 399     void operator=(const random_device& ) = delete;
 400 };
 401
 402 // Utilities
 403
 404 class seed_seq
 405 {
 406 public:
 407     // types
 408     typedef uint_least32_t result_type;
 409
 410     // constructors
 411     seed_seq();
 412     template<class T>
 413         seed_seq(initializer_list<T> il);
 414     template<class InputIterator>
 415         seed_seq(InputIterator begin, InputIterator end);
 416
 417     // generating functions
 418     template<class RandomAccessIterator>
 419         void generate(RandomAccessIterator begin, RandomAccessIterator end);
 420
 421     // property functions
 422     size_t size() const;
 423     template<class OutputIterator>
 424         void param(OutputIterator dest) const;
 425
 426     // no copy functions
 427     seed_seq(const seed_seq&) = delete;
 428     void operator=(const seed_seq& ) = delete;
 429 };
 430
 431 template<class RealType, size_t bits, class URNG>
 432     RealType generate_canonical(URNG& g);
 433
 434 // Distributions
 435
 436 template<class IntType = int>
 437 class uniform_int_distribution
 438 {
 439 public:
 440     // types
 441     typedef IntType result_type;
 442
 443     class param_type
 444     {
 445     public:
 446         typedef uniform_int_distribution distribution_type;
 447
 448         explicit param_type(IntType a = 0,
 449                                     IntType b = numeric_limits<IntType>::max());
 450
 451         result_type a() const;
 452         result_type b() const;
 453
 454         friend bool operator==(const param_type& x, const param_type& y);
 455         friend bool operator!=(const param_type& x, const param_type& y);
 456     };
 457
 458     // constructors and reset functions
 459     explicit uniform_int_distribution(IntType a = 0,
 460                                     IntType b = numeric_limits<IntType>::max());
 461     explicit uniform_int_distribution(const param_type& parm);
 462     void reset();
 463
 464     // generating functions
 465     template<class URNG> result_type operator()(URNG& g);
 466     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 467
 468     // property functions
 469     result_type a() const;
 470     result_type b() const;
 471
 472     param_type param() const;
 473     void param(const param_type& parm);
 474
 475     result_type min() const;
 476     result_type max() const;
 477
 478     friend bool operator==(const uniform_int_distribution& x,
 479                            const uniform_int_distribution& y);
 480     friend bool operator!=(const uniform_int_distribution& x,
 481                            const uniform_int_distribution& y);
 482
 483     template <class charT, class traits>
 484     friend
 485     basic_ostream<charT, traits>&
 486     operator<<(basic_ostream<charT, traits>& os,
 487                const uniform_int_distribution& x);
 488
 489     template <class charT, class traits>
 490     friend
 491     basic_istream<charT, traits>&
 492     operator>>(basic_istream<charT, traits>& is,
 493                uniform_int_distribution& x);
 494 };
 495
 496 template<class RealType = double>
 497 class uniform_real_distribution
 498 {
 499 public:
 500     // types
 501     typedef RealType result_type;
 502
 503     class param_type
 504     {
 505     public:
 506         typedef uniform_real_distribution distribution_type;
 507
 508         explicit param_type(RealType a = 0,
 509                             RealType b = 1);
 510
 511         result_type a() const;
 512         result_type b() const;
 513
 514         friend bool operator==(const param_type& x, const param_type& y);
 515         friend bool operator!=(const param_type& x, const param_type& y);
 516     };
 517
 518     // constructors and reset functions
 519     explicit uniform_real_distribution(RealType a = 0.0, RealType b = 1.0);
 520     explicit uniform_real_distribution(const param_type& parm);
 521     void reset();
 522
 523     // generating functions
 524     template<class URNG> result_type operator()(URNG& g);
 525     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 526
 527     // property functions
 528     result_type a() const;
 529     result_type b() const;
 530
 531     param_type param() const;
 532     void param(const param_type& parm);
 533
 534     result_type min() const;
 535     result_type max() const;
 536
 537     friend bool operator==(const uniform_real_distribution& x,
 538                            const uniform_real_distribution& y);
 539     friend bool operator!=(const uniform_real_distribution& x,
 540                            const uniform_real_distribution& y);
 541
 542     template <class charT, class traits>
 543     friend
 544     basic_ostream<charT, traits>&
 545     operator<<(basic_ostream<charT, traits>& os,
 546                const uniform_real_distribution& x);
 547
 548     template <class charT, class traits>
 549     friend
 550     basic_istream<charT, traits>&
 551     operator>>(basic_istream<charT, traits>& is,
 552                uniform_real_distribution& x);
 553 };
 554
 555 class bernoulli_distribution
 556 {
 557 public:
 558     // types
 559     typedef bool result_type;
 560
 561     class param_type
 562     {
 563     public:
 564         typedef bernoulli_distribution distribution_type;
 565
 566         explicit param_type(double p = 0.5);
 567
 568         double p() const;
 569
 570         friend bool operator==(const param_type& x, const param_type& y);
 571         friend bool operator!=(const param_type& x, const param_type& y);
 572     };
 573
 574     // constructors and reset functions
 575     explicit bernoulli_distribution(double p = 0.5);
 576     explicit bernoulli_distribution(const param_type& parm);
 577     void reset();
 578
 579     // generating functions
 580     template<class URNG> result_type operator()(URNG& g);
 581     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 582
 583     // property functions
 584     double p() const;
 585
 586     param_type param() const;
 587     void param(const param_type& parm);
 588
 589     result_type min() const;
 590     result_type max() const;
 591
 592     friend bool operator==(const bernoulli_distribution& x,
 593                            const bernoulli_distribution& y);
 594     friend bool operator!=(const bernoulli_distribution& x,
 595                            const bernoulli_distribution& y);
 596
 597     template <class charT, class traits>
 598     friend
 599     basic_ostream<charT, traits>&
 600     operator<<(basic_ostream<charT, traits>& os,
 601                const bernoulli_distribution& x);
 602
 603     template <class charT, class traits>
 604     friend
 605     basic_istream<charT, traits>&
 606     operator>>(basic_istream<charT, traits>& is,
 607                bernoulli_distribution& x);
 608 };
 609
 610 template<class IntType = int>
 611 class binomial_distribution
 612 {
 613 public:
 614     // types
 615     typedef IntType result_type;
 616
 617     class param_type
 618     {
 619     public:
 620         typedef binomial_distribution distribution_type;
 621
 622         explicit param_type(IntType t = 1, double p = 0.5);
 623
 624         IntType t() const;
 625         double p() const;
 626
 627         friend bool operator==(const param_type& x, const param_type& y);
 628         friend bool operator!=(const param_type& x, const param_type& y);
 629     };
 630
 631     // constructors and reset functions
 632     explicit binomial_distribution(IntType t = 1, double p = 0.5);
 633     explicit binomial_distribution(const param_type& parm);
 634     void reset();
 635
 636     // generating functions
 637     template<class URNG> result_type operator()(URNG& g);
 638     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 639
 640     // property functions
 641     IntType t() const;
 642     double p() const;
 643
 644     param_type param() const;
 645     void param(const param_type& parm);
 646
 647     result_type min() const;
 648     result_type max() const;
 649
 650     friend bool operator==(const binomial_distribution& x,
 651                            const binomial_distribution& y);
 652     friend bool operator!=(const binomial_distribution& x,
 653                            const binomial_distribution& y);
 654
 655     template <class charT, class traits>
 656     friend
 657     basic_ostream<charT, traits>&
 658     operator<<(basic_ostream<charT, traits>& os,
 659                const binomial_distribution& x);
 660
 661     template <class charT, class traits>
 662     friend
 663     basic_istream<charT, traits>&
 664     operator>>(basic_istream<charT, traits>& is,
 665                binomial_distribution& x);
 666 };
 667
 668 template<class IntType = int>
 669 class geometric_distribution
 670 {
 671 public:
 672     // types
 673     typedef IntType result_type;
 674
 675     class param_type
 676     {
 677     public:
 678         typedef geometric_distribution distribution_type;
 679
 680         explicit param_type(double p = 0.5);
 681
 682         double p() const;
 683
 684         friend bool operator==(const param_type& x, const param_type& y);
 685         friend bool operator!=(const param_type& x, const param_type& y);
 686     };
 687
 688     // constructors and reset functions
 689     explicit geometric_distribution(double p = 0.5);
 690     explicit geometric_distribution(const param_type& parm);
 691     void reset();
 692
 693     // generating functions
 694     template<class URNG> result_type operator()(URNG& g);
 695     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 696
 697     // property functions
 698     double p() const;
 699
 700     param_type param() const;
 701     void param(const param_type& parm);
 702
 703     result_type min() const;
 704     result_type max() const;
 705
 706     friend bool operator==(const geometric_distribution& x,
 707                            const geometric_distribution& y);
 708     friend bool operator!=(const geometric_distribution& x,
 709                            const geometric_distribution& y);
 710
 711     template <class charT, class traits>
 712     friend
 713     basic_ostream<charT, traits>&
 714     operator<<(basic_ostream<charT, traits>& os,
 715                const geometric_distribution& x);
 716
 717     template <class charT, class traits>
 718     friend
 719     basic_istream<charT, traits>&
 720     operator>>(basic_istream<charT, traits>& is,
 721                geometric_distribution& x);
 722 };
 723
 724 template<class IntType = int>
 725 class negative_binomial_distribution
 726 {
 727 public:
 728     // types
 729     typedef IntType result_type;
 730
 731     class param_type
 732     {
 733     public:
 734         typedef negative_binomial_distribution distribution_type;
 735
 736         explicit param_type(result_type k = 1, double p = 0.5);
 737
 738         result_type k() const;
 739         double p() const;
 740
 741         friend bool operator==(const param_type& x, const param_type& y);
 742         friend bool operator!=(const param_type& x, const param_type& y);
 743     };
 744
 745     // constructor and reset functions
 746     explicit negative_binomial_distribution(result_type k = 1, double p = 0.5);
 747     explicit negative_binomial_distribution(const param_type& parm);
 748     void reset();
 749
 750     // generating functions
 751     template<class URNG> result_type operator()(URNG& g);
 752     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 753
 754     // property functions
 755     result_type k() const;
 756     double p() const;
 757
 758     param_type param() const;
 759     void param(const param_type& parm);
 760
 761     result_type min() const;
 762     result_type max() const;
 763
 764     friend bool operator==(const negative_binomial_distribution& x,
 765                            const negative_binomial_distribution& y);
 766     friend bool operator!=(const negative_binomial_distribution& x,
 767                            const negative_binomial_distribution& y);
 768
 769     template <class charT, class traits>
 770     friend
 771     basic_ostream<charT, traits>&
 772     operator<<(basic_ostream<charT, traits>& os,
 773                const negative_binomial_distribution& x);
 774
 775     template <class charT, class traits>
 776     friend
 777     basic_istream<charT, traits>&
 778     operator>>(basic_istream<charT, traits>& is,
 779                negative_binomial_distribution& x);
 780 };
 781
 782 template<class IntType = int>
 783 class poisson_distribution
 784 {
 785 public:
 786     // types
 787     typedef IntType result_type;
 788
 789     class param_type
 790     {
 791     public:
 792         typedef poisson_distribution distribution_type;
 793
 794         explicit param_type(double mean = 1.0);
 795
 796         double mean() const;
 797
 798         friend bool operator==(const param_type& x, const param_type& y);
 799         friend bool operator!=(const param_type& x, const param_type& y);
 800     };
 801
 802     // constructors and reset functions
 803     explicit poisson_distribution(double mean = 1.0);
 804     explicit poisson_distribution(const param_type& parm);
 805     void reset();
 806
 807     // generating functions
 808     template<class URNG> result_type operator()(URNG& g);
 809     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 810
 811     // property functions
 812     double mean() const;
 813
 814     param_type param() const;
 815     void param(const param_type& parm);
 816
 817     result_type min() const;
 818     result_type max() const;
 819
 820     friend bool operator==(const poisson_distribution& x,
 821                            const poisson_distribution& y);
 822     friend bool operator!=(const poisson_distribution& x,
 823                            const poisson_distribution& y);
 824
 825     template <class charT, class traits>
 826     friend
 827     basic_ostream<charT, traits>&
 828     operator<<(basic_ostream<charT, traits>& os,
 829                const poisson_distribution& x);
 830
 831     template <class charT, class traits>
 832     friend
 833     basic_istream<charT, traits>&
 834     operator>>(basic_istream<charT, traits>& is,
 835                poisson_distribution& x);
 836 };
 837
 838 template<class RealType = double>
 839 class exponential_distribution
 840 {
 841 public:
 842     // types
 843     typedef RealType result_type;
 844
 845     class param_type
 846     {
 847     public:
 848         typedef exponential_distribution distribution_type;
 849
 850         explicit param_type(result_type lambda = 1.0);
 851
 852         result_type lambda() const;
 853
 854         friend bool operator==(const param_type& x, const param_type& y);
 855         friend bool operator!=(const param_type& x, const param_type& y);
 856     };
 857
 858     // constructors and reset functions
 859     explicit exponential_distribution(result_type lambda = 1.0);
 860     explicit exponential_distribution(const param_type& parm);
 861     void reset();
 862
 863     // generating functions
 864     template<class URNG> result_type operator()(URNG& g);
 865     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 866
 867     // property functions
 868     result_type lambda() const;
 869
 870     param_type param() const;
 871     void param(const param_type& parm);
 872
 873     result_type min() const;
 874     result_type max() const;
 875
 876     friend bool operator==(const exponential_distribution& x,
 877                            const exponential_distribution& y);
 878     friend bool operator!=(const exponential_distribution& x,
 879                            const exponential_distribution& y);
 880
 881     template <class charT, class traits>
 882     friend
 883     basic_ostream<charT, traits>&
 884     operator<<(basic_ostream<charT, traits>& os,
 885                const exponential_distribution& x);
 886
 887     template <class charT, class traits>
 888     friend
 889     basic_istream<charT, traits>&
 890     operator>>(basic_istream<charT, traits>& is,
 891                exponential_distribution& x);
 892 };
 893
 894 template<class RealType = double>
 895 class gamma_distribution
 896 {
 897 public:
 898     // types
 899     typedef RealType result_type;
 900
 901     class param_type
 902     {
 903     public:
 904         typedef gamma_distribution distribution_type;
 905
 906         explicit param_type(result_type alpha = 1, result_type beta = 1);
 907
 908         result_type alpha() const;
 909         result_type beta() const;
 910
 911         friend bool operator==(const param_type& x, const param_type& y);
 912         friend bool operator!=(const param_type& x, const param_type& y);
 913     };
 914
 915     // constructors and reset functions
 916     explicit gamma_distribution(result_type alpha = 1, result_type beta = 1);
 917     explicit gamma_distribution(const param_type& parm);
 918     void reset();
 919
 920     // generating functions
 921     template<class URNG> result_type operator()(URNG& g);
 922     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 923
 924     // property functions
 925     result_type alpha() const;
 926     result_type beta() const;
 927
 928     param_type param() const;
 929     void param(const param_type& parm);
 930
 931     result_type min() const;
 932     result_type max() const;
 933
 934     friend bool operator==(const gamma_distribution& x,
 935                            const gamma_distribution& y);
 936     friend bool operator!=(const gamma_distribution& x,
 937                            const gamma_distribution& y);
 938
 939     template <class charT, class traits>
 940     friend
 941     basic_ostream<charT, traits>&
 942     operator<<(basic_ostream<charT, traits>& os,
 943                const gamma_distribution& x);
 944
 945     template <class charT, class traits>
 946     friend
 947     basic_istream<charT, traits>&
 948     operator>>(basic_istream<charT, traits>& is,
 949                gamma_distribution& x);
 950 };
 951
 952 template<class RealType = double>
 953 class weibull_distribution
 954 {
 955 public:
 956     // types
 957     typedef RealType result_type;
 958
 959     class param_type
 960     {
 961     public:
 962         typedef weibull_distribution distribution_type;
 963
 964         explicit param_type(result_type alpha = 1, result_type beta = 1);
 965
 966         result_type a() const;
 967         result_type b() const;
 968
 969         friend bool operator==(const param_type& x, const param_type& y);
 970         friend bool operator!=(const param_type& x, const param_type& y);
 971     };
 972
 973     // constructor and reset functions
 974     explicit weibull_distribution(result_type a = 1, result_type b = 1);
 975     explicit weibull_distribution(const param_type& parm);
 976     void reset();
 977
 978     // generating functions
 979     template<class URNG> result_type operator()(URNG& g);
 980     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
 981
 982     // property functions
 983     result_type a() const;
 984     result_type b() const;
 985
 986     param_type param() const;
 987     void param(const param_type& parm);
 988
 989     result_type min() const;
 990     result_type max() const;
 991
 992     friend bool operator==(const weibull_distribution& x,
 993                            const weibull_distribution& y);
 994     friend bool operator!=(const weibull_distribution& x,
 995                            const weibull_distribution& y);
 996
 997     template <class charT, class traits>
 998     friend
 999     basic_ostream<charT, traits>&
1000     operator<<(basic_ostream<charT, traits>& os,
1001                const weibull_distribution& x);
1002
1003     template <class charT, class traits>
1004     friend
1005     basic_istream<charT, traits>&
1006     operator>>(basic_istream<charT, traits>& is,
1007                weibull_distribution& x);
1008 };
1009
1010 template<class RealType = double>
1011 class extreme_value_distribution
1012 {
1013 public:
1014     // types
1015     typedef RealType result_type;
1016
1017     class param_type
1018     {
1019     public:
1020         typedef extreme_value_distribution distribution_type;
1021
1022         explicit param_type(result_type a = 0, result_type b = 1);
1023
1024         result_type a() const;
1025         result_type b() const;
1026
1027         friend bool operator==(const param_type& x, const param_type& y);
1028         friend bool operator!=(const param_type& x, const param_type& y);
1029     };
1030
1031     // constructor and reset functions
1032     explicit extreme_value_distribution(result_type a = 0, result_type b = 1);
1033     explicit extreme_value_distribution(const param_type& parm);
1034     void reset();
1035
1036     // generating functions
1037     template<class URNG> result_type operator()(URNG& g);
1038     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1039
1040     // property functions
1041     result_type a() const;
1042     result_type b() const;
1043
1044     param_type param() const;
1045     void param(const param_type& parm);
1046
1047     result_type min() const;
1048     result_type max() const;
1049
1050     friend bool operator==(const extreme_value_distribution& x,
1051                            const extreme_value_distribution& y);
1052     friend bool operator!=(const extreme_value_distribution& x,
1053                            const extreme_value_distribution& y);
1054
1055     template <class charT, class traits>
1056     friend
1057     basic_ostream<charT, traits>&
1058     operator<<(basic_ostream<charT, traits>& os,
1059                const extreme_value_distribution& x);
1060
1061     template <class charT, class traits>
1062     friend
1063     basic_istream<charT, traits>&
1064     operator>>(basic_istream<charT, traits>& is,
1065                extreme_value_distribution& x);
1066 };
1067
1068 template<class RealType = double>
1069 class normal_distribution
1070 {
1071 public:
1072     // types
1073     typedef RealType result_type;
1074
1075     class param_type
1076     {
1077     public:
1078         typedef normal_distribution distribution_type;
1079
1080         explicit param_type(result_type mean = 0, result_type stddev = 1);
1081
1082         result_type mean() const;
1083         result_type stddev() const;
1084
1085         friend bool operator==(const param_type& x, const param_type& y);
1086         friend bool operator!=(const param_type& x, const param_type& y);
1087     };
1088
1089     // constructors and reset functions
1090     explicit normal_distribution(result_type mean = 0, result_type stddev = 1);
1091     explicit normal_distribution(const param_type& parm);
1092     void reset();
1093
1094     // generating functions
1095     template<class URNG> result_type operator()(URNG& g);
1096     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1097
1098     // property functions
1099     result_type mean() const;
1100     result_type stddev() const;
1101
1102     param_type param() const;
1103     void param(const param_type& parm);
1104
1105     result_type min() const;
1106     result_type max() const;
1107
1108     friend bool operator==(const normal_distribution& x,
1109                            const normal_distribution& y);
1110     friend bool operator!=(const normal_distribution& x,
1111                            const normal_distribution& y);
1112
1113     template <class charT, class traits>
1114     friend
1115     basic_ostream<charT, traits>&
1116     operator<<(basic_ostream<charT, traits>& os,
1117                const normal_distribution& x);
1118
1119     template <class charT, class traits>
1120     friend
1121     basic_istream<charT, traits>&
1122     operator>>(basic_istream<charT, traits>& is,
1123                normal_distribution& x);
1124 };
1125
1126 template<class RealType = double>
1127 class lognormal_distribution
1128 {
1129 public:
1130     // types
1131     typedef RealType result_type;
1132
1133     class param_type
1134     {
1135     public:
1136         typedef lognormal_distribution distribution_type;
1137
1138         explicit param_type(result_type m = 0, result_type s = 1);
1139
1140         result_type m() const;
1141         result_type s() const;
1142
1143         friend bool operator==(const param_type& x, const param_type& y);
1144         friend bool operator!=(const param_type& x, const param_type& y);
1145     };
1146
1147     // constructor and reset functions
1148     explicit lognormal_distribution(result_type m = 0, result_type s = 1);
1149     explicit lognormal_distribution(const param_type& parm);
1150     void reset();
1151
1152     // generating functions
1153     template<class URNG> result_type operator()(URNG& g);
1154     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1155
1156     // property functions
1157     result_type m() const;
1158     result_type s() const;
1159
1160     param_type param() const;
1161     void param(const param_type& parm);
1162
1163     result_type min() const;
1164     result_type max() const;
1165
1166     friend bool operator==(const lognormal_distribution& x,
1167                            const lognormal_distribution& y);
1168     friend bool operator!=(const lognormal_distribution& x,
1169                            const lognormal_distribution& y);
1170
1171     template <class charT, class traits>
1172     friend
1173     basic_ostream<charT, traits>&
1174     operator<<(basic_ostream<charT, traits>& os,
1175                const lognormal_distribution& x);
1176
1177     template <class charT, class traits>
1178     friend
1179     basic_istream<charT, traits>&
1180     operator>>(basic_istream<charT, traits>& is,
1181                lognormal_distribution& x);
1182 };
1183
1184 template<class RealType = double>
1185 class chi_squared_distribution
1186 {
1187 public:
1188     // types
1189     typedef RealType result_type;
1190
1191     class param_type
1192     {
1193     public:
1194         typedef chi_squared_distribution distribution_type;
1195
1196         explicit param_type(result_type n = 1);
1197
1198         result_type n() const;
1199
1200         friend bool operator==(const param_type& x, const param_type& y);
1201         friend bool operator!=(const param_type& x, const param_type& y);
1202     };
1203
1204     // constructor and reset functions
1205     explicit chi_squared_distribution(result_type n = 1);
1206     explicit chi_squared_distribution(const param_type& parm);
1207     void reset();
1208
1209     // generating functions
1210     template<class URNG> result_type operator()(URNG& g);
1211     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1212
1213     // property functions
1214     result_type n() const;
1215
1216     param_type param() const;
1217     void param(const param_type& parm);
1218
1219     result_type min() const;
1220     result_type max() const;
1221
1222     friend bool operator==(const chi_squared_distribution& x,
1223                            const chi_squared_distribution& y);
1224     friend bool operator!=(const chi_squared_distribution& x,
1225                            const chi_squared_distribution& y);
1226
1227     template <class charT, class traits>
1228     friend
1229     basic_ostream<charT, traits>&
1230     operator<<(basic_ostream<charT, traits>& os,
1231                const chi_squared_distribution& x);
1232
1233     template <class charT, class traits>
1234     friend
1235     basic_istream<charT, traits>&
1236     operator>>(basic_istream<charT, traits>& is,
1237                chi_squared_distribution& x);
1238 };
1239
1240 template<class RealType = double>
1241 class cauchy_distribution
1242 {
1243 public:
1244     // types
1245     typedef RealType result_type;
1246
1247     class param_type
1248     {
1249     public:
1250         typedef cauchy_distribution distribution_type;
1251
1252         explicit param_type(result_type a = 0, result_type b = 1);
1253
1254         result_type a() const;
1255         result_type b() const;
1256
1257         friend bool operator==(const param_type& x, const param_type& y);
1258         friend bool operator!=(const param_type& x, const param_type& y);
1259     };
1260
1261     // constructor and reset functions
1262     explicit cauchy_distribution(result_type a = 0, result_type b = 1);
1263     explicit cauchy_distribution(const param_type& parm);
1264     void reset();
1265
1266     // generating functions
1267     template<class URNG> result_type operator()(URNG& g);
1268     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1269
1270     // property functions
1271     result_type a() const;
1272     result_type b() const;
1273
1274     param_type param() const;
1275     void param(const param_type& parm);
1276
1277     result_type min() const;
1278     result_type max() const;
1279
1280     friend bool operator==(const cauchy_distribution& x,
1281                            const cauchy_distribution& y);
1282     friend bool operator!=(const cauchy_distribution& x,
1283                            const cauchy_distribution& y);
1284
1285     template <class charT, class traits>
1286     friend
1287     basic_ostream<charT, traits>&
1288     operator<<(basic_ostream<charT, traits>& os,
1289                const cauchy_distribution& x);
1290
1291     template <class charT, class traits>
1292     friend
1293     basic_istream<charT, traits>&
1294     operator>>(basic_istream<charT, traits>& is,
1295                cauchy_distribution& x);
1296 };
1297
1298 template<class RealType = double>
1299 class fisher_f_distribution
1300 {
1301 public:
1302     // types
1303     typedef RealType result_type;
1304
1305     class param_type
1306     {
1307     public:
1308         typedef fisher_f_distribution distribution_type;
1309
1310         explicit param_type(result_type m = 1, result_type n = 1);
1311
1312         result_type m() const;
1313         result_type n() const;
1314
1315         friend bool operator==(const param_type& x, const param_type& y);
1316         friend bool operator!=(const param_type& x, const param_type& y);
1317     };
1318
1319     // constructor and reset functions
1320     explicit fisher_f_distribution(result_type m = 1, result_type n = 1);
1321     explicit fisher_f_distribution(const param_type& parm);
1322     void reset();
1323
1324     // generating functions
1325     template<class URNG> result_type operator()(URNG& g);
1326     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1327
1328     // property functions
1329     result_type m() const;
1330     result_type n() const;
1331
1332     param_type param() const;
1333     void param(const param_type& parm);
1334
1335     result_type min() const;
1336     result_type max() const;
1337
1338     friend bool operator==(const fisher_f_distribution& x,
1339                            const fisher_f_distribution& y);
1340     friend bool operator!=(const fisher_f_distribution& x,
1341                            const fisher_f_distribution& y);
1342
1343     template <class charT, class traits>
1344     friend
1345     basic_ostream<charT, traits>&
1346     operator<<(basic_ostream<charT, traits>& os,
1347                const fisher_f_distribution& x);
1348
1349     template <class charT, class traits>
1350     friend
1351     basic_istream<charT, traits>&
1352     operator>>(basic_istream<charT, traits>& is,
1353                fisher_f_distribution& x);
1354 };
1355
1356 template<class RealType = double>
1357 class student_t_distribution
1358 {
1359 public:
1360     // types
1361     typedef RealType result_type;
1362
1363     class param_type
1364     {
1365     public:
1366         typedef student_t_distribution distribution_type;
1367
1368         explicit param_type(result_type n = 1);
1369
1370         result_type n() const;
1371
1372         friend bool operator==(const param_type& x, const param_type& y);
1373         friend bool operator!=(const param_type& x, const param_type& y);
1374     };
1375
1376     // constructor and reset functions
1377     explicit student_t_distribution(result_type n = 1);
1378     explicit student_t_distribution(const param_type& parm);
1379     void reset();
1380
1381     // generating functions
1382     template<class URNG> result_type operator()(URNG& g);
1383     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1384
1385     // property functions
1386     result_type n() const;
1387
1388     param_type param() const;
1389     void param(const param_type& parm);
1390
1391     result_type min() const;
1392     result_type max() const;
1393
1394     friend bool operator==(const student_t_distribution& x,
1395                            const student_t_distribution& y);
1396     friend bool operator!=(const student_t_distribution& x,
1397                            const student_t_distribution& y);
1398
1399     template <class charT, class traits>
1400     friend
1401     basic_ostream<charT, traits>&
1402     operator<<(basic_ostream<charT, traits>& os,
1403                const student_t_distribution& x);
1404
1405     template <class charT, class traits>
1406     friend
1407     basic_istream<charT, traits>&
1408     operator>>(basic_istream<charT, traits>& is,
1409                student_t_distribution& x);
1410 };
1411
1412 template<class IntType = int>
1413 class discrete_distribution
1414 {
1415 public:
1416     // types
1417     typedef IntType result_type;
1418
1419     class param_type
1420     {
1421     public:
1422         typedef discrete_distribution distribution_type;
1423
1424         param_type();
1425         template<class InputIterator>
1426             param_type(InputIterator firstW, InputIterator lastW);
1427         param_type(initializer_list<double> wl);
1428         template<class UnaryOperation>
1429             param_type(size_t nw, double xmin, double xmax, UnaryOperation fw);
1430
1431         vector<double> probabilities() const;
1432
1433         friend bool operator==(const param_type& x, const param_type& y);
1434         friend bool operator!=(const param_type& x, const param_type& y);
1435     };
1436
1437     // constructor and reset functions
1438     discrete_distribution();
1439     template<class InputIterator>
1440         discrete_distribution(InputIterator firstW, InputIterator lastW);
1441     discrete_distribution(initializer_list<double> wl);
1442     template<class UnaryOperation>
1443         discrete_distribution(size_t nw, double xmin, double xmax,
1444                               UnaryOperation fw);
1445     explicit discrete_distribution(const param_type& parm);
1446     void reset();
1447
1448     // generating functions
1449     template<class URNG> result_type operator()(URNG& g);
1450     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1451
1452     // property functions
1453     vector<double> probabilities() const;
1454
1455     param_type param() const;
1456     void param(const param_type& parm);
1457
1458     result_type min() const;
1459     result_type max() const;
1460
1461     friend bool operator==(const discrete_distribution& x,
1462                            const discrete_distribution& y);
1463     friend bool operator!=(const discrete_distribution& x,
1464                            const discrete_distribution& y);
1465
1466     template <class charT, class traits>
1467     friend
1468     basic_ostream<charT, traits>&
1469     operator<<(basic_ostream<charT, traits>& os,
1470                const discrete_distribution& x);
1471
1472     template <class charT, class traits>
1473     friend
1474     basic_istream<charT, traits>&
1475     operator>>(basic_istream<charT, traits>& is,
1476                discrete_distribution& x);
1477 };
1478
1479 template<class RealType = double>
1480 class piecewise_constant_distribution
1481 {
1482     // types
1483     typedef RealType result_type;
1484
1485     class param_type
1486     {
1487     public:
1488         typedef piecewise_constant_distribution distribution_type;
1489
1490         param_type();
1491         template<class InputIteratorB, class InputIteratorW>
1492             param_type(InputIteratorB firstB, InputIteratorB lastB,
1493                        InputIteratorW firstW);
1494         template<class UnaryOperation>
1495             param_type(initializer_list<result_type> bl, UnaryOperation fw);
1496         template<class UnaryOperation>
1497             param_type(size_t nw, result_type xmin, result_type xmax,
1498                        UnaryOperation fw);
1499
1500         vector<result_type> intervals() const;
1501         vector<result_type> densities() const;
1502
1503         friend bool operator==(const param_type& x, const param_type& y);
1504         friend bool operator!=(const param_type& x, const param_type& y);
1505     };
1506
1507     // constructor and reset functions
1508     piecewise_constant_distribution();
1509     template<class InputIteratorB, class InputIteratorW>
1510         piecewise_constant_distribution(InputIteratorB firstB,
1511                                         InputIteratorB lastB,
1512                                         InputIteratorW firstW);
1513     template<class UnaryOperation>
1514         piecewise_constant_distribution(initializer_list<result_type> bl,
1515                                         UnaryOperation fw);
1516     template<class UnaryOperation>
1517         piecewise_constant_distribution(size_t nw, result_type xmin,
1518                                         result_type xmax, UnaryOperation fw);
1519     explicit piecewise_constant_distribution(const param_type& parm);
1520     void reset();
1521
1522     // generating functions
1523     template<class URNG> result_type operator()(URNG& g);
1524     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1525
1526     // property functions
1527     vector<result_type> intervals() const;
1528     vector<result_type> densities() const;
1529
1530     param_type param() const;
1531     void param(const param_type& parm);
1532
1533     result_type min() const;
1534     result_type max() const;
1535
1536     friend bool operator==(const piecewise_constant_distribution& x,
1537                            const piecewise_constant_distribution& y);
1538     friend bool operator!=(const piecewise_constant_distribution& x,
1539                            const piecewise_constant_distribution& y);
1540
1541     template <class charT, class traits>
1542     friend
1543     basic_ostream<charT, traits>&
1544     operator<<(basic_ostream<charT, traits>& os,
1545                const piecewise_constant_distribution& x);
1546
1547     template <class charT, class traits>
1548     friend
1549     basic_istream<charT, traits>&
1550     operator>>(basic_istream<charT, traits>& is,
1551                piecewise_constant_distribution& x);
1552 };
1553
1554 template<class RealType = double>
1555 class piecewise_linear_distribution
1556 {
1557     // types
1558     typedef RealType result_type;
1559
1560     class param_type
1561     {
1562     public:
1563         typedef piecewise_linear_distribution distribution_type;
1564
1565         param_type();
1566         template<class InputIteratorB, class InputIteratorW>
1567             param_type(InputIteratorB firstB, InputIteratorB lastB,
1568                        InputIteratorW firstW);
1569         template<class UnaryOperation>
1570             param_type(initializer_list<result_type> bl, UnaryOperation fw);
1571         template<class UnaryOperation>
1572             param_type(size_t nw, result_type xmin, result_type xmax,
1573                        UnaryOperation fw);
1574
1575         vector<result_type> intervals() const;
1576         vector<result_type> densities() const;
1577
1578         friend bool operator==(const param_type& x, const param_type& y);
1579         friend bool operator!=(const param_type& x, const param_type& y);
1580     };
1581
1582     // constructor and reset functions
1583     piecewise_linear_distribution();
1584     template<class InputIteratorB, class InputIteratorW>
1585         piecewise_linear_distribution(InputIteratorB firstB,
1586                                       InputIteratorB lastB,
1587                                       InputIteratorW firstW);
1588
1589     template<class UnaryOperation>
1590         piecewise_linear_distribution(initializer_list<result_type> bl,
1591                                       UnaryOperation fw);
1592
1593     template<class UnaryOperation>
1594         piecewise_linear_distribution(size_t nw, result_type xmin,
1595                                       result_type xmax, UnaryOperation fw);
1596
1597     explicit piecewise_linear_distribution(const param_type& parm);
1598     void reset();
1599
1600     // generating functions
1601     template<class URNG> result_type operator()(URNG& g);
1602     template<class URNG> result_type operator()(URNG& g, const param_type& parm);
1603
1604     // property functions
1605     vector<result_type> intervals() const;
1606     vector<result_type> densities() const;
1607
1608     param_type param() const;
1609     void param(const param_type& parm);
1610
1611     result_type min() const;
1612     result_type max() const;
1613
1614     friend bool operator==(const piecewise_linear_distribution& x,
1615                            const piecewise_linear_distribution& y);
1616     friend bool operator!=(const piecewise_linear_distribution& x,
1617                            const piecewise_linear_distribution& y);
1618
1619     template <class charT, class traits>
1620     friend
1621     basic_ostream<charT, traits>&
1622     operator<<(basic_ostream<charT, traits>& os,
1623                const piecewise_linear_distribution& x);
1624
1625     template <class charT, class traits>
1626     friend
1627     basic_istream<charT, traits>&
1628     operator>>(basic_istream<charT, traits>& is,
1629                piecewise_linear_distribution& x);
1630 };
1631
1632 } // std
1633 */
1634
1635 #include <__config>
1636 #include <cstddef>
1637 #include <cstdint>
1638 #include <cmath>
1639 #include <type_traits>
1640 #include <initializer_list>
1641 #include <limits>
1642 #include <algorithm>
1643 #include <numeric>
1644 #include <vector>
1645 #include <string>
1646 #include <istream>
1647 #include <ostream>
1648
1649 #include <__undef_min_max>
1650
1651 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
1652 #pragma GCC system_header
1653 #endif
1654
1655 _LIBCPP_BEGIN_NAMESPACE_STD
1656
1657 // __is_seed_sequence
1658
1659 template <class _Sseq, class _Engine>
1660 struct __is_seed_sequence
1661 {
1662     static _LIBCPP_CONSTEXPR const bool value =
1663               !is_convertible<_Sseq, typename _Engine::result_type>::value &&
1664               !is_same<typename remove_cv<_Sseq>::type, _Engine>::value;
1665 };
1666
1667 // linear_congruential_engine
1668
1669 template <unsigned long long __a, unsigned long long __c,
1670           unsigned long long __m, unsigned long long _Mp,
1671           bool _MightOverflow = (__a != 0 && __m != 0 && __m-1 > (_Mp-__c)/__a)>
1672 struct __lce_ta;
1673
1674 // 64
1675
1676 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1677 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), true>
1678 {
1679     typedef unsigned long long result_type;
1680     _LIBCPP_INLINE_VISIBILITY
1681     static result_type next(result_type __x)
1682     {
1683         // Schrage's algorithm
1684         const result_type __q = __m / __a;
1685         const result_type __r = __m % __a;
1686         const result_type __t0 = __a * (__x % __q);
1687         const result_type __t1 = __r * (__x / __q);
1688         __x = __t0 + (__t0 < __t1) * __m - __t1;
1689         __x += __c - (__x >= __m - __c) * __m;
1690         return __x;
1691     }
1692 };
1693
1694 template <unsigned long long __a, unsigned long long __m>
1695 struct __lce_ta<__a, 0, __m, (unsigned long long)(~0), true>
1696 {
1697     typedef unsigned long long result_type;
1698     _LIBCPP_INLINE_VISIBILITY
1699     static result_type next(result_type __x)
1700     {
1701         // Schrage's algorithm
1702         const result_type __q = __m / __a;
1703         const result_type __r = __m % __a;
1704         const result_type __t0 = __a * (__x % __q);
1705         const result_type __t1 = __r * (__x / __q);
1706         __x = __t0 + (__t0 < __t1) * __m - __t1;
1707         return __x;
1708     }
1709 };
1710
1711 template <unsigned long long __a, unsigned long long __c, unsigned long long __m>
1712 struct __lce_ta<__a, __c, __m, (unsigned long long)(~0), false>
1713 {
1714     typedef unsigned long long result_type;
1715     _LIBCPP_INLINE_VISIBILITY
1716     static result_type next(result_type __x)
1717     {
1718         return (__a * __x + __c) % __m;
1719     }
1720 };
1721
1722 template <unsigned long long __a, unsigned long long __c>
1723 struct __lce_ta<__a, __c, 0, (unsigned long long)(~0), false>
1724 {
1725     typedef unsigned long long result_type;
1726     _LIBCPP_INLINE_VISIBILITY
1727     static result_type next(result_type __x)
1728     {
1729         return __a * __x + __c;
1730     }
1731 };
1732
1733 // 32
1734
1735 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
1736 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), true>
1737 {
1738     typedef unsigned result_type;
1739     _LIBCPP_INLINE_VISIBILITY
1740     static result_type next(result_type __x)
1741     {
1742         const result_type __a = static_cast<result_type>(_Ap);
1743         const result_type __c = static_cast<result_type>(_Cp);
1744         const result_type __m = static_cast<result_type>(_Mp);
1745         // Schrage's algorithm
1746         const result_type __q = __m / __a;
1747         const result_type __r = __m % __a;
1748         const result_type __t0 = __a * (__x % __q);
1749         const result_type __t1 = __r * (__x / __q);
1750         __x = __t0 + (__t0 < __t1) * __m - __t1;
1751         __x += __c - (__x >= __m - __c) * __m;
1752         return __x;
1753     }
1754 };
1755
1756 template <unsigned long long _Ap, unsigned long long _Mp>
1757 struct __lce_ta<_Ap, 0, _Mp, unsigned(~0), true>
1758 {
1759     typedef unsigned result_type;
1760     _LIBCPP_INLINE_VISIBILITY
1761     static result_type next(result_type __x)
1762     {
1763         const result_type __a = static_cast<result_type>(_Ap);
1764         const result_type __m = static_cast<result_type>(_Mp);
1765         // Schrage's algorithm
1766         const result_type __q = __m / __a;
1767         const result_type __r = __m % __a;
1768         const result_type __t0 = __a * (__x % __q);
1769         const result_type __t1 = __r * (__x / __q);
1770         __x = __t0 + (__t0 < __t1) * __m - __t1;
1771         return __x;
1772     }
1773 };
1774
1775 template <unsigned long long _Ap, unsigned long long _Cp, unsigned long long _Mp>
1776 struct __lce_ta<_Ap, _Cp, _Mp, unsigned(~0), false>
1777 {
1778     typedef unsigned result_type;
1779     _LIBCPP_INLINE_VISIBILITY
1780     static result_type next(result_type __x)
1781     {
1782         const result_type __a = static_cast<result_type>(_Ap);
1783         const result_type __c = static_cast<result_type>(_Cp);
1784         const result_type __m = static_cast<result_type>(_Mp);
1785         return (__a * __x + __c) % __m;
1786     }
1787 };
1788
1789 template <unsigned long long _Ap, unsigned long long _Cp>
1790 struct __lce_ta<_Ap, _Cp, 0, unsigned(~0), false>
1791 {
1792     typedef unsigned result_type;
1793     _LIBCPP_INLINE_VISIBILITY
1794     static result_type next(result_type __x)
1795     {
1796         const result_type __a = static_cast<result_type>(_Ap);
1797         const result_type __c = static_cast<result_type>(_Cp);
1798         return __a * __x + __c;
1799     }
1800 };
1801
1802 // 16
1803
1804 template <unsigned long long __a, unsigned long long __c, unsigned long long __m, bool __b>
1805 struct __lce_ta<__a, __c, __m, (unsigned short)(~0), __b>
1806 {
1807     typedef unsigned short result_type;
1808     _LIBCPP_INLINE_VISIBILITY
1809     static result_type next(result_type __x)
1810     {
1811         return static_cast<result_type>(__lce_ta<__a, __c, __m, unsigned(~0)>::next(__x));
1812     }
1813 };
1814
1815 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1816 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine;
1817
1818 template <class _CharT, class _Traits,
1819           class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1820 _LIBCPP_INLINE_VISIBILITY
1821 basic_ostream<_CharT, _Traits>&
1822 operator<<(basic_ostream<_CharT, _Traits>& __os,
1823            const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
1824
1825 template <class _CharT, class _Traits,
1826           class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1827 basic_istream<_CharT, _Traits>&
1828 operator>>(basic_istream<_CharT, _Traits>& __is,
1829            linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
1830
1831 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1832 class _LIBCPP_TEMPLATE_VIS linear_congruential_engine
1833 {
1834 public:
1835     // types
1836     typedef _UIntType result_type;
1837
1838 private:
1839     result_type __x_;
1840
1841     static _LIBCPP_CONSTEXPR const result_type _Mp = result_type(~0);
1842
1843     static_assert(__m == 0 || __a < __m, "linear_congruential_engine invalid parameters");
1844     static_assert(__m == 0 || __c < __m, "linear_congruential_engine invalid parameters");
1845 public:
1846     static _LIBCPP_CONSTEXPR const result_type _Min = __c == 0u ? 1u: 0u;
1847     static _LIBCPP_CONSTEXPR const result_type _Max = __m - 1u;
1848     static_assert(_Min < _Max,           "linear_congruential_engine invalid parameters");
1849
1850     // engine characteristics
1851     static _LIBCPP_CONSTEXPR const result_type multiplier = __a;
1852     static _LIBCPP_CONSTEXPR const result_type increment = __c;
1853     static _LIBCPP_CONSTEXPR const result_type modulus = __m;
1854     _LIBCPP_INLINE_VISIBILITY
1855     static _LIBCPP_CONSTEXPR result_type min() {return _Min;}
1856     _LIBCPP_INLINE_VISIBILITY
1857     static _LIBCPP_CONSTEXPR result_type max() {return _Max;}
1858     static _LIBCPP_CONSTEXPR const result_type default_seed = 1u;
1859
1860     // constructors and seeding functions
1861     _LIBCPP_INLINE_VISIBILITY
1862     explicit linear_congruential_engine(result_type __s = default_seed)
1863         {seed(__s);}
1864     template<class _Sseq>
1865         _LIBCPP_INLINE_VISIBILITY
1866         explicit linear_congruential_engine(_Sseq& __q,
1867         typename enable_if<__is_seed_sequence<_Sseq, linear_congruential_engine>::value>::type* = 0)
1868         {seed(__q);}
1869     _LIBCPP_INLINE_VISIBILITY
1870     void seed(result_type __s = default_seed)
1871         {seed(integral_constant<bool, __m == 0>(),
1872               integral_constant<bool, __c == 0>(), __s);}
1873     template<class _Sseq>
1874         _LIBCPP_INLINE_VISIBILITY
1875         typename enable_if
1876         <
1877             __is_seed_sequence<_Sseq, linear_congruential_engine>::value,
1878             void
1879         >::type
1880         seed(_Sseq& __q)
1881             {__seed(__q, integral_constant<unsigned,
1882                 1 + (__m == 0 ? (sizeof(result_type) * __CHAR_BIT__ - 1)/32
1883                              :  (__m > 0x100000000ull))>());}
1884
1885     // generating functions
1886     _LIBCPP_INLINE_VISIBILITY
1887     result_type operator()()
1888         {return __x_ = static_cast<result_type>(__lce_ta<__a, __c, __m, _Mp>::next(__x_));}
1889     _LIBCPP_INLINE_VISIBILITY
1890     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
1891
1892     friend _LIBCPP_INLINE_VISIBILITY
1893     bool operator==(const linear_congruential_engine& __x,
1894                     const linear_congruential_engine& __y)
1895         {return __x.__x_ == __y.__x_;}
1896     friend _LIBCPP_INLINE_VISIBILITY
1897     bool operator!=(const linear_congruential_engine& __x,
1898                     const linear_congruential_engine& __y)
1899         {return !(__x == __y);}
1900
1901 private:
1902
1903     _LIBCPP_INLINE_VISIBILITY
1904     void seed(true_type, true_type, result_type __s) {__x_ = __s == 0 ? 1 : __s;}
1905     _LIBCPP_INLINE_VISIBILITY
1906     void seed(true_type, false_type, result_type __s) {__x_ = __s;}
1907     _LIBCPP_INLINE_VISIBILITY
1908     void seed(false_type, true_type, result_type __s) {__x_ = __s % __m == 0 ?
1909                                                                  1 : __s % __m;}
1910     _LIBCPP_INLINE_VISIBILITY
1911     void seed(false_type, false_type, result_type __s) {__x_ = __s % __m;}
1912
1913     template<class _Sseq>
1914         void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
1915     template<class _Sseq>
1916         void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
1917
1918     template <class _CharT, class _Traits,
1919               class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1920     friend
1921     basic_ostream<_CharT, _Traits>&
1922     operator<<(basic_ostream<_CharT, _Traits>& __os,
1923                const linear_congruential_engine<_Up, _Ap, _Cp, _Np>&);
1924
1925     template <class _CharT, class _Traits,
1926               class _Up, _Up _Ap, _Up _Cp, _Up _Np>
1927     friend
1928     basic_istream<_CharT, _Traits>&
1929     operator>>(basic_istream<_CharT, _Traits>& __is,
1930                linear_congruential_engine<_Up, _Ap, _Cp, _Np>& __x);
1931 };
1932
1933 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1934     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1935     linear_congruential_engine<_UIntType, __a, __c, __m>::multiplier;
1936
1937 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1938     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1939     linear_congruential_engine<_UIntType, __a, __c, __m>::increment;
1940
1941 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1942     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1943     linear_congruential_engine<_UIntType, __a, __c, __m>::modulus;
1944
1945 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1946     _LIBCPP_CONSTEXPR const typename linear_congruential_engine<_UIntType, __a, __c, __m>::result_type
1947     linear_congruential_engine<_UIntType, __a, __c, __m>::default_seed;
1948
1949 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1950 template<class _Sseq>
1951 void
1952 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1953                                                  integral_constant<unsigned, 1>)
1954 {
1955     const unsigned __k = 1;
1956     uint32_t __ar[__k+3];
1957     __q.generate(__ar, __ar + __k + 3);
1958     result_type __s = static_cast<result_type>(__ar[3] % __m);
1959     __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1960 }
1961
1962 template <class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1963 template<class _Sseq>
1964 void
1965 linear_congruential_engine<_UIntType, __a, __c, __m>::__seed(_Sseq& __q,
1966                                                  integral_constant<unsigned, 2>)
1967 {
1968     const unsigned __k = 2;
1969     uint32_t __ar[__k+3];
1970     __q.generate(__ar, __ar + __k + 3);
1971     result_type __s = static_cast<result_type>((__ar[3] +
1972                                               ((uint64_t)__ar[4] << 32)) % __m);
1973     __x_ = __c == 0 && __s == 0 ? result_type(1) : __s;
1974 }
1975
1976 template <class _CharT, class _Traits,
1977           class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1978 inline _LIBCPP_INLINE_VISIBILITY
1979 basic_ostream<_CharT, _Traits>&
1980 operator<<(basic_ostream<_CharT, _Traits>& __os,
1981            const linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1982 {
1983     __save_flags<_CharT, _Traits> __lx(__os);
1984     __os.flags(ios_base::dec | ios_base::left);
1985     __os.fill(__os.widen(' '));
1986     return __os << __x.__x_;
1987 }
1988
1989 template <class _CharT, class _Traits,
1990           class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
1991 basic_istream<_CharT, _Traits>&
1992 operator>>(basic_istream<_CharT, _Traits>& __is,
1993            linear_congruential_engine<_UIntType, __a, __c, __m>& __x)
1994 {
1995     __save_flags<_CharT, _Traits> __lx(__is);
1996     __is.flags(ios_base::dec | ios_base::skipws);
1997     _UIntType __t;
1998     __is >> __t;
1999     if (!__is.fail())
2000         __x.__x_ = __t;
2001     return __is;
2002 }
2003
2004 typedef linear_congruential_engine<uint_fast32_t, 16807, 0, 2147483647>
2005                                                                    minstd_rand0;
2006 typedef linear_congruential_engine<uint_fast32_t, 48271, 0, 2147483647>
2007                                                                     minstd_rand;
2008 typedef minstd_rand                                       default_random_engine;
2009 // mersenne_twister_engine
2010
2011 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2012           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2013           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2014 class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine;
2015
2016 template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2017           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2018           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2019 bool
2020 operator==(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2021                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2022            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2023                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2024
2025 template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2026           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2027           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2028 _LIBCPP_INLINE_VISIBILITY
2029 bool
2030 operator!=(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2031                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2032            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2033                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2034
2035 template <class _CharT, class _Traits,
2036           class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2037           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2038           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2039 basic_ostream<_CharT, _Traits>&
2040 operator<<(basic_ostream<_CharT, _Traits>& __os,
2041            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2042                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2043
2044 template <class _CharT, class _Traits,
2045           class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2046           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2047           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2048 basic_istream<_CharT, _Traits>&
2049 operator>>(basic_istream<_CharT, _Traits>& __is,
2050            mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2051                                    _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2052
2053 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2054           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2055           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2056 class _LIBCPP_TEMPLATE_VIS mersenne_twister_engine
2057 {
2058 public:
2059     // types
2060     typedef _UIntType result_type;
2061
2062 private:
2063     result_type __x_[__n];
2064     size_t      __i_;
2065
2066     static_assert(  0 <  __m, "mersenne_twister_engine invalid parameters");
2067     static_assert(__m <= __n, "mersenne_twister_engine invalid parameters");
2068     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
2069     static_assert(__w <= _Dt, "mersenne_twister_engine invalid parameters");
2070     static_assert(  2 <= __w, "mersenne_twister_engine invalid parameters");
2071     static_assert(__r <= __w, "mersenne_twister_engine invalid parameters");
2072     static_assert(__u <= __w, "mersenne_twister_engine invalid parameters");
2073     static_assert(__s <= __w, "mersenne_twister_engine invalid parameters");
2074     static_assert(__t <= __w, "mersenne_twister_engine invalid parameters");
2075     static_assert(__l <= __w, "mersenne_twister_engine invalid parameters");
2076 public:
2077     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
2078     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
2079                                                       (result_type(1) << __w) - result_type(1);
2080     static_assert(_Min < _Max, "mersenne_twister_engine invalid parameters");
2081     static_assert(__a <= _Max, "mersenne_twister_engine invalid parameters");
2082     static_assert(__b <= _Max, "mersenne_twister_engine invalid parameters");
2083     static_assert(__c <= _Max, "mersenne_twister_engine invalid parameters");
2084     static_assert(__d <= _Max, "mersenne_twister_engine invalid parameters");
2085     static_assert(__f <= _Max, "mersenne_twister_engine invalid parameters");
2086
2087     // engine characteristics
2088     static _LIBCPP_CONSTEXPR const size_t word_size = __w;
2089     static _LIBCPP_CONSTEXPR const size_t state_size = __n;
2090     static _LIBCPP_CONSTEXPR const size_t shift_size = __m;
2091     static _LIBCPP_CONSTEXPR const size_t mask_bits = __r;
2092     static _LIBCPP_CONSTEXPR const result_type xor_mask = __a;
2093     static _LIBCPP_CONSTEXPR const size_t tempering_u = __u;
2094     static _LIBCPP_CONSTEXPR const result_type tempering_d = __d;
2095     static _LIBCPP_CONSTEXPR const size_t tempering_s = __s;
2096     static _LIBCPP_CONSTEXPR const result_type tempering_b = __b;
2097     static _LIBCPP_CONSTEXPR const size_t tempering_t = __t;
2098     static _LIBCPP_CONSTEXPR const result_type tempering_c = __c;
2099     static _LIBCPP_CONSTEXPR const size_t tempering_l = __l;
2100     static _LIBCPP_CONSTEXPR const result_type initialization_multiplier = __f;
2101     _LIBCPP_INLINE_VISIBILITY
2102     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
2103     _LIBCPP_INLINE_VISIBILITY
2104     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
2105     static _LIBCPP_CONSTEXPR const result_type default_seed = 5489u;
2106
2107     // constructors and seeding functions
2108     _LIBCPP_INLINE_VISIBILITY
2109     explicit mersenne_twister_engine(result_type __sd = default_seed)
2110         {seed(__sd);}
2111     template<class _Sseq>
2112         _LIBCPP_INLINE_VISIBILITY
2113         explicit mersenne_twister_engine(_Sseq& __q,
2114         typename enable_if<__is_seed_sequence<_Sseq, mersenne_twister_engine>::value>::type* = 0)
2115         {seed(__q);}
2116     void seed(result_type __sd = default_seed);
2117     template<class _Sseq>
2118         _LIBCPP_INLINE_VISIBILITY
2119         typename enable_if
2120         <
2121             __is_seed_sequence<_Sseq, mersenne_twister_engine>::value,
2122             void
2123         >::type
2124         seed(_Sseq& __q)
2125             {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2126
2127     // generating functions
2128     result_type operator()();
2129     _LIBCPP_INLINE_VISIBILITY
2130     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2131
2132     template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2133               _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2134               _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2135     friend
2136     bool
2137     operator==(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2138                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2139                const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2140                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2141
2142     template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2143               _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2144               _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2145     friend
2146     bool
2147     operator!=(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2148                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2149                const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2150                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __y);
2151
2152     template <class _CharT, class _Traits,
2153               class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2154               _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2155               _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2156     friend
2157     basic_ostream<_CharT, _Traits>&
2158     operator<<(basic_ostream<_CharT, _Traits>& __os,
2159                const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2160                                              _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2161
2162     template <class _CharT, class _Traits,
2163               class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2164               _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2165               _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2166     friend
2167     basic_istream<_CharT, _Traits>&
2168     operator>>(basic_istream<_CharT, _Traits>& __is,
2169                mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2170                                        _Bp, _Tp, _Cp, _Lp, _Fp>& __x);
2171 private:
2172
2173     template<class _Sseq>
2174         void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2175     template<class _Sseq>
2176         void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2177
2178     template <size_t __count>
2179         _LIBCPP_INLINE_VISIBILITY
2180         static
2181         typename enable_if
2182         <
2183             __count < __w,
2184             result_type
2185         >::type
2186         __lshift(result_type __x) {return (__x << __count) & _Max;}
2187
2188     template <size_t __count>
2189         _LIBCPP_INLINE_VISIBILITY
2190         static
2191         typename enable_if
2192         <
2193             (__count >= __w),
2194             result_type
2195         >::type
2196         __lshift(result_type) {return result_type(0);}
2197
2198     template <size_t __count>
2199         _LIBCPP_INLINE_VISIBILITY
2200         static
2201         typename enable_if
2202         <
2203             __count < _Dt,
2204             result_type
2205         >::type
2206         __rshift(result_type __x) {return __x >> __count;}
2207
2208     template <size_t __count>
2209         _LIBCPP_INLINE_VISIBILITY
2210         static
2211         typename enable_if
2212         <
2213             (__count >= _Dt),
2214             result_type
2215         >::type
2216         __rshift(result_type) {return result_type(0);}
2217 };
2218
2219 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2220           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2221           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2222     _LIBCPP_CONSTEXPR const size_t
2223     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::word_size;
2224
2225 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2226           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2227           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2228     _LIBCPP_CONSTEXPR const size_t
2229     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::state_size;
2230
2231 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2232           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2233           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2234     _LIBCPP_CONSTEXPR const size_t
2235     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::shift_size;
2236
2237 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2238           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2239           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2240     _LIBCPP_CONSTEXPR const size_t
2241     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::mask_bits;
2242
2243 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2244           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2245           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2246     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2247     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::xor_mask;
2248
2249 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2250           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2251           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2252     _LIBCPP_CONSTEXPR const size_t
2253     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_u;
2254
2255 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2256           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2257           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2258     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2259     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_d;
2260
2261 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2262           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2263           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2264     _LIBCPP_CONSTEXPR const size_t
2265     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_s;
2266
2267 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2268           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2269           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2270     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2271     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_b;
2272
2273 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2274           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2275           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2276     _LIBCPP_CONSTEXPR const size_t
2277     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_t;
2278
2279 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2280           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2281           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2282     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2283     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_c;
2284
2285 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2286           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2287           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2288     _LIBCPP_CONSTEXPR const size_t
2289     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::tempering_l;
2290
2291 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2292           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2293           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2294     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2295     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::initialization_multiplier;
2296
2297 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2298           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2299           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2300     _LIBCPP_CONSTEXPR const typename mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::result_type
2301     mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b, __t, __c, __l, __f>::default_seed;
2302
2303 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2304           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2305           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2306 void
2307 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2308     __t, __c, __l, __f>::seed(result_type __sd)
2309 {   // __w >= 2
2310     __x_[0] = __sd & _Max;
2311     for (size_t __i = 1; __i < __n; ++__i)
2312         __x_[__i] = (__f * (__x_[__i-1] ^ __rshift<__w - 2>(__x_[__i-1])) + __i) & _Max;
2313     __i_ = 0;
2314 }
2315
2316 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2317           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2318           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2319 template<class _Sseq>
2320 void
2321 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2322     __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 1>)
2323 {
2324     const unsigned __k = 1;
2325     uint32_t __ar[__n * __k];
2326     __q.generate(__ar, __ar + __n * __k);
2327     for (size_t __i = 0; __i < __n; ++__i)
2328         __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2329     const result_type __mask = __r == _Dt ? result_type(~0) :
2330                                        (result_type(1) << __r) - result_type(1);
2331     __i_ = 0;
2332     if ((__x_[0] & ~__mask) == 0)
2333     {
2334         for (size_t __i = 1; __i < __n; ++__i)
2335             if (__x_[__i] != 0)
2336                 return;
2337         __x_[0] = _Max;
2338     }
2339 }
2340
2341 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2342           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2343           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2344 template<class _Sseq>
2345 void
2346 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2347     __t, __c, __l, __f>::__seed(_Sseq& __q, integral_constant<unsigned, 2>)
2348 {
2349     const unsigned __k = 2;
2350     uint32_t __ar[__n * __k];
2351     __q.generate(__ar, __ar + __n * __k);
2352     for (size_t __i = 0; __i < __n; ++__i)
2353         __x_[__i] = static_cast<result_type>(
2354             (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2355     const result_type __mask = __r == _Dt ? result_type(~0) :
2356                                        (result_type(1) << __r) - result_type(1);
2357     __i_ = 0;
2358     if ((__x_[0] & ~__mask) == 0)
2359     {
2360         for (size_t __i = 1; __i < __n; ++__i)
2361             if (__x_[__i] != 0)
2362                 return;
2363         __x_[0] = _Max;
2364     }
2365 }
2366
2367 template <class _UIntType, size_t __w, size_t __n, size_t __m, size_t __r,
2368           _UIntType __a, size_t __u, _UIntType __d, size_t __s,
2369           _UIntType __b, size_t __t, _UIntType __c, size_t __l, _UIntType __f>
2370 _UIntType
2371 mersenne_twister_engine<_UIntType, __w, __n, __m, __r, __a, __u, __d, __s, __b,
2372     __t, __c, __l, __f>::operator()()
2373 {
2374     const size_t __j = (__i_ + 1) % __n;
2375     const result_type __mask = __r == _Dt ? result_type(~0) :
2376                                        (result_type(1) << __r) - result_type(1);
2377     const result_type _Yp = (__x_[__i_] & ~__mask) | (__x_[__j] & __mask);
2378     const size_t __k = (__i_ + __m) % __n;
2379     __x_[__i_] = __x_[__k] ^ __rshift<1>(_Yp) ^ (__a * (_Yp & 1));
2380     result_type __z = __x_[__i_] ^ (__rshift<__u>(__x_[__i_]) & __d);
2381     __i_ = __j;
2382     __z ^= __lshift<__s>(__z) & __b;
2383     __z ^= __lshift<__t>(__z) & __c;
2384     return __z ^ __rshift<__l>(__z);
2385 }
2386
2387 template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2388           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2389           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2390 bool
2391 operator==(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2392                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2393            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2394                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
2395 {
2396     if (__x.__i_ == __y.__i_)
2397         return _VSTD::equal(__x.__x_, __x.__x_ + _Np, __y.__x_);
2398     if (__x.__i_ == 0 || __y.__i_ == 0)
2399     {
2400         size_t __j = _VSTD::min(_Np - __x.__i_, _Np - __y.__i_);
2401         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2402                          __y.__x_ + __y.__i_))
2403             return false;
2404         if (__x.__i_ == 0)
2405             return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Np, __y.__x_);
2406         return _VSTD::equal(__x.__x_, __x.__x_ + (_Np - __j), __y.__x_ + __j);
2407     }
2408     if (__x.__i_ < __y.__i_)
2409     {
2410         size_t __j = _Np - __y.__i_;
2411         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2412                          __y.__x_ + __y.__i_))
2413             return false;
2414         if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Np,
2415                          __y.__x_))
2416             return false;
2417         return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
2418                            __y.__x_ + (_Np - (__x.__i_ + __j)));
2419     }
2420     size_t __j = _Np - __x.__i_;
2421     if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2422                      __x.__x_ + __x.__i_))
2423         return false;
2424     if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Np,
2425                      __x.__x_))
2426         return false;
2427     return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
2428                        __x.__x_ + (_Np - (__y.__i_ + __j)));
2429 }
2430
2431 template <class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2432           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2433           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2434 inline _LIBCPP_INLINE_VISIBILITY
2435 bool
2436 operator!=(const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2437                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x,
2438            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2439                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __y)
2440 {
2441     return !(__x == __y);
2442 }
2443
2444 template <class _CharT, class _Traits,
2445           class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2446           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2447           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2448 basic_ostream<_CharT, _Traits>&
2449 operator<<(basic_ostream<_CharT, _Traits>& __os,
2450            const mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2451                                          _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
2452 {
2453     __save_flags<_CharT, _Traits> __lx(__os);
2454     __os.flags(ios_base::dec | ios_base::left);
2455     _CharT __sp = __os.widen(' ');
2456     __os.fill(__sp);
2457     __os << __x.__x_[__x.__i_];
2458     for (size_t __j = __x.__i_ + 1; __j < _Np; ++__j)
2459         __os << __sp << __x.__x_[__j];
2460     for (size_t __j = 0; __j < __x.__i_; ++__j)
2461         __os << __sp << __x.__x_[__j];
2462     return __os;
2463 }
2464
2465 template <class _CharT, class _Traits,
2466           class _UI, size_t _Wp, size_t _Np, size_t _Mp, size_t _Rp,
2467           _UI _Ap, size_t _Up, _UI _Dp, size_t _Sp,
2468           _UI _Bp, size_t _Tp, _UI _Cp, size_t _Lp, _UI _Fp>
2469 basic_istream<_CharT, _Traits>&
2470 operator>>(basic_istream<_CharT, _Traits>& __is,
2471            mersenne_twister_engine<_UI, _Wp, _Np, _Mp, _Rp, _Ap, _Up, _Dp, _Sp,
2472                                    _Bp, _Tp, _Cp, _Lp, _Fp>& __x)
2473 {
2474     __save_flags<_CharT, _Traits> __lx(__is);
2475     __is.flags(ios_base::dec | ios_base::skipws);
2476     _UI __t[_Np];
2477     for (size_t __i = 0; __i < _Np; ++__i)
2478         __is >> __t[__i];
2479     if (!__is.fail())
2480     {
2481         for (size_t __i = 0; __i < _Np; ++__i)
2482             __x.__x_[__i] = __t[__i];
2483         __x.__i_ = 0;
2484     }
2485     return __is;
2486 }
2487
2488 typedef mersenne_twister_engine<uint_fast32_t, 32, 624, 397, 31,
2489                                 0x9908b0df, 11, 0xffffffff,
2490                                 7,  0x9d2c5680,
2491                                 15, 0xefc60000,
2492                                 18, 1812433253>                         mt19937;
2493 typedef mersenne_twister_engine<uint_fast64_t, 64, 312, 156, 31,
2494                                 0xb5026f5aa96619e9ULL, 29, 0x5555555555555555ULL,
2495                                 17, 0x71d67fffeda60000ULL,
2496                                 37, 0xfff7eee000000000ULL,
2497                                 43, 6364136223846793005ULL>          mt19937_64;
2498
2499 // subtract_with_carry_engine
2500
2501 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2502 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine;
2503
2504 template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2505 bool
2506 operator==(
2507     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2508     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y);
2509
2510 template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2511 _LIBCPP_INLINE_VISIBILITY
2512 bool
2513 operator!=(
2514     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2515     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y);
2516
2517 template <class _CharT, class _Traits,
2518           class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2519 basic_ostream<_CharT, _Traits>&
2520 operator<<(basic_ostream<_CharT, _Traits>& __os,
2521            const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x);
2522
2523 template <class _CharT, class _Traits,
2524           class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2525 basic_istream<_CharT, _Traits>&
2526 operator>>(basic_istream<_CharT, _Traits>& __is,
2527            subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x);
2528
2529 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2530 class _LIBCPP_TEMPLATE_VIS subtract_with_carry_engine
2531 {
2532 public:
2533     // types
2534     typedef _UIntType result_type;
2535
2536 private:
2537     result_type __x_[__r];
2538     result_type  __c_;
2539     size_t      __i_;
2540
2541     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
2542     static_assert(  0 <  __w, "subtract_with_carry_engine invalid parameters");
2543     static_assert(__w <= _Dt, "subtract_with_carry_engine invalid parameters");
2544     static_assert(  0 <  __s, "subtract_with_carry_engine invalid parameters");
2545     static_assert(__s <  __r, "subtract_with_carry_engine invalid parameters");
2546 public:
2547     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
2548     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
2549                                                       (result_type(1) << __w) - result_type(1);
2550     static_assert(_Min < _Max, "subtract_with_carry_engine invalid parameters");
2551
2552     // engine characteristics
2553     static _LIBCPP_CONSTEXPR const size_t word_size = __w;
2554     static _LIBCPP_CONSTEXPR const size_t short_lag = __s;
2555     static _LIBCPP_CONSTEXPR const size_t long_lag = __r;
2556     _LIBCPP_INLINE_VISIBILITY
2557     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
2558     _LIBCPP_INLINE_VISIBILITY
2559     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
2560     static _LIBCPP_CONSTEXPR const result_type default_seed = 19780503u;
2561
2562     // constructors and seeding functions
2563     _LIBCPP_INLINE_VISIBILITY
2564     explicit subtract_with_carry_engine(result_type __sd = default_seed)
2565         {seed(__sd);}
2566     template<class _Sseq>
2567         _LIBCPP_INLINE_VISIBILITY
2568         explicit subtract_with_carry_engine(_Sseq& __q,
2569         typename enable_if<__is_seed_sequence<_Sseq, subtract_with_carry_engine>::value>::type* = 0)
2570         {seed(__q);}
2571     _LIBCPP_INLINE_VISIBILITY
2572     void seed(result_type __sd = default_seed)
2573         {seed(__sd, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2574     template<class _Sseq>
2575         _LIBCPP_INLINE_VISIBILITY
2576         typename enable_if
2577         <
2578             __is_seed_sequence<_Sseq, subtract_with_carry_engine>::value,
2579             void
2580         >::type
2581         seed(_Sseq& __q)
2582             {__seed(__q, integral_constant<unsigned, 1 + (__w - 1) / 32>());}
2583
2584     // generating functions
2585     result_type operator()();
2586     _LIBCPP_INLINE_VISIBILITY
2587     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2588
2589     template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2590     friend
2591     bool
2592     operator==(
2593         const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2594         const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y);
2595
2596     template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2597     friend
2598     bool
2599     operator!=(
2600         const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2601         const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y);
2602
2603     template <class _CharT, class _Traits,
2604               class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2605     friend
2606     basic_ostream<_CharT, _Traits>&
2607     operator<<(basic_ostream<_CharT, _Traits>& __os,
2608                const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x);
2609
2610     template <class _CharT, class _Traits,
2611               class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2612     friend
2613     basic_istream<_CharT, _Traits>&
2614     operator>>(basic_istream<_CharT, _Traits>& __is,
2615                subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x);
2616
2617 private:
2618
2619     void seed(result_type __sd, integral_constant<unsigned, 1>);
2620     void seed(result_type __sd, integral_constant<unsigned, 2>);
2621     template<class _Sseq>
2622         void __seed(_Sseq& __q, integral_constant<unsigned, 1>);
2623     template<class _Sseq>
2624         void __seed(_Sseq& __q, integral_constant<unsigned, 2>);
2625 };
2626
2627 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2628     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::word_size;
2629
2630 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2631     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::short_lag;
2632
2633 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2634     _LIBCPP_CONSTEXPR const size_t subtract_with_carry_engine<_UIntType, __w, __s, __r>::long_lag;
2635
2636 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2637     _LIBCPP_CONSTEXPR const typename subtract_with_carry_engine<_UIntType, __w, __s, __r>::result_type
2638     subtract_with_carry_engine<_UIntType, __w, __s, __r>::default_seed;
2639
2640 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2641 void
2642 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2643         integral_constant<unsigned, 1>)
2644 {
2645     linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2646         __e(__sd == 0u ? default_seed : __sd);
2647     for (size_t __i = 0; __i < __r; ++__i)
2648         __x_[__i] = static_cast<result_type>(__e() & _Max);
2649     __c_ = __x_[__r-1] == 0;
2650     __i_ = 0;
2651 }
2652
2653 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2654 void
2655 subtract_with_carry_engine<_UIntType, __w, __s, __r>::seed(result_type __sd,
2656         integral_constant<unsigned, 2>)
2657 {
2658     linear_congruential_engine<result_type, 40014u, 0u, 2147483563u>
2659         __e(__sd == 0u ? default_seed : __sd);
2660     for (size_t __i = 0; __i < __r; ++__i)
2661     {
2662         result_type __e0 = __e();
2663         __x_[__i] = static_cast<result_type>(
2664                                     (__e0 + ((uint64_t)__e() << 32)) & _Max);
2665     }
2666     __c_ = __x_[__r-1] == 0;
2667     __i_ = 0;
2668 }
2669
2670 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2671 template<class _Sseq>
2672 void
2673 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2674         integral_constant<unsigned, 1>)
2675 {
2676     const unsigned __k = 1;
2677     uint32_t __ar[__r * __k];
2678     __q.generate(__ar, __ar + __r * __k);
2679     for (size_t __i = 0; __i < __r; ++__i)
2680         __x_[__i] = static_cast<result_type>(__ar[__i] & _Max);
2681     __c_ = __x_[__r-1] == 0;
2682     __i_ = 0;
2683 }
2684
2685 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2686 template<class _Sseq>
2687 void
2688 subtract_with_carry_engine<_UIntType, __w, __s, __r>::__seed(_Sseq& __q,
2689         integral_constant<unsigned, 2>)
2690 {
2691     const unsigned __k = 2;
2692     uint32_t __ar[__r * __k];
2693     __q.generate(__ar, __ar + __r * __k);
2694     for (size_t __i = 0; __i < __r; ++__i)
2695         __x_[__i] = static_cast<result_type>(
2696                   (__ar[2 * __i] + ((uint64_t)__ar[2 * __i + 1] << 32)) & _Max);
2697     __c_ = __x_[__r-1] == 0;
2698     __i_ = 0;
2699 }
2700
2701 template<class _UIntType, size_t __w, size_t __s, size_t __r>
2702 _UIntType
2703 subtract_with_carry_engine<_UIntType, __w, __s, __r>::operator()()
2704 {
2705     const result_type& __xs = __x_[(__i_ + (__r - __s)) % __r];
2706     result_type& __xr = __x_[__i_];
2707     result_type __new_c = __c_ == 0 ? __xs < __xr : __xs != 0 ? __xs <= __xr : 1;
2708     __xr = (__xs - __xr - __c_) & _Max;
2709     __c_ = __new_c;
2710     __i_ = (__i_ + 1) % __r;
2711     return __xr;
2712 }
2713
2714 template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2715 bool
2716 operator==(
2717     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2718     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y)
2719 {
2720     if (__x.__c_ != __y.__c_)
2721         return false;
2722     if (__x.__i_ == __y.__i_)
2723         return _VSTD::equal(__x.__x_, __x.__x_ + _Rp, __y.__x_);
2724     if (__x.__i_ == 0 || __y.__i_ == 0)
2725     {
2726         size_t __j = _VSTD::min(_Rp - __x.__i_, _Rp - __y.__i_);
2727         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + __x.__i_ + __j,
2728                          __y.__x_ + __y.__i_))
2729             return false;
2730         if (__x.__i_ == 0)
2731             return _VSTD::equal(__x.__x_ + __j, __x.__x_ + _Rp, __y.__x_);
2732         return _VSTD::equal(__x.__x_, __x.__x_ + (_Rp - __j), __y.__x_ + __j);
2733     }
2734     if (__x.__i_ < __y.__i_)
2735     {
2736         size_t __j = _Rp - __y.__i_;
2737         if (!_VSTD::equal(__x.__x_ + __x.__i_, __x.__x_ + (__x.__i_ + __j),
2738                          __y.__x_ + __y.__i_))
2739             return false;
2740         if (!_VSTD::equal(__x.__x_ + (__x.__i_ + __j), __x.__x_ + _Rp,
2741                          __y.__x_))
2742             return false;
2743         return _VSTD::equal(__x.__x_, __x.__x_ + __x.__i_,
2744                            __y.__x_ + (_Rp - (__x.__i_ + __j)));
2745     }
2746     size_t __j = _Rp - __x.__i_;
2747     if (!_VSTD::equal(__y.__x_ + __y.__i_, __y.__x_ + (__y.__i_ + __j),
2748                      __x.__x_ + __x.__i_))
2749         return false;
2750     if (!_VSTD::equal(__y.__x_ + (__y.__i_ + __j), __y.__x_ + _Rp,
2751                      __x.__x_))
2752         return false;
2753     return _VSTD::equal(__y.__x_, __y.__x_ + __y.__i_,
2754                        __x.__x_ + (_Rp - (__y.__i_ + __j)));
2755 }
2756
2757 template<class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2758 inline _LIBCPP_INLINE_VISIBILITY
2759 bool
2760 operator!=(
2761     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x,
2762     const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __y)
2763 {
2764     return !(__x == __y);
2765 }
2766
2767 template <class _CharT, class _Traits,
2768           class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2769 basic_ostream<_CharT, _Traits>&
2770 operator<<(basic_ostream<_CharT, _Traits>& __os,
2771            const subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x)
2772 {
2773     __save_flags<_CharT, _Traits> __lx(__os);
2774     __os.flags(ios_base::dec | ios_base::left);
2775     _CharT __sp = __os.widen(' ');
2776     __os.fill(__sp);
2777     __os << __x.__x_[__x.__i_];
2778     for (size_t __j = __x.__i_ + 1; __j < _Rp; ++__j)
2779         __os << __sp << __x.__x_[__j];
2780     for (size_t __j = 0; __j < __x.__i_; ++__j)
2781         __os << __sp << __x.__x_[__j];
2782     __os << __sp << __x.__c_;
2783     return __os;
2784 }
2785
2786 template <class _CharT, class _Traits,
2787           class _UI, size_t _Wp, size_t _Sp, size_t _Rp>
2788 basic_istream<_CharT, _Traits>&
2789 operator>>(basic_istream<_CharT, _Traits>& __is,
2790            subtract_with_carry_engine<_UI, _Wp, _Sp, _Rp>& __x)
2791 {
2792     __save_flags<_CharT, _Traits> __lx(__is);
2793     __is.flags(ios_base::dec | ios_base::skipws);
2794     _UI __t[_Rp+1];
2795     for (size_t __i = 0; __i < _Rp+1; ++__i)
2796         __is >> __t[__i];
2797     if (!__is.fail())
2798     {
2799         for (size_t __i = 0; __i < _Rp; ++__i)
2800             __x.__x_[__i] = __t[__i];
2801         __x.__c_ = __t[_Rp];
2802         __x.__i_ = 0;
2803     }
2804     return __is;
2805 }
2806
2807 typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>     ranlux24_base;
2808 typedef subtract_with_carry_engine<uint_fast64_t, 48,  5, 12>     ranlux48_base;
2809
2810 // discard_block_engine
2811
2812 template<class _Engine, size_t __p, size_t __r>
2813 class _LIBCPP_TEMPLATE_VIS discard_block_engine
2814 {
2815     _Engine __e_;
2816     int     __n_;
2817
2818     static_assert(  0 <  __r, "discard_block_engine invalid parameters");
2819     static_assert(__r <= __p, "discard_block_engine invalid parameters");
2820     static_assert(__r <= INT_MAX, "discard_block_engine invalid parameters");
2821 public:
2822     // types
2823     typedef typename _Engine::result_type result_type;
2824
2825     // engine characteristics
2826     static _LIBCPP_CONSTEXPR const size_t block_size = __p;
2827     static _LIBCPP_CONSTEXPR const size_t used_block = __r;
2828
2829 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2830     static const result_type _Min = _Engine::_Min;
2831     static const result_type _Max = _Engine::_Max;
2832 #else
2833     static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
2834     static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
2835 #endif
2836
2837     _LIBCPP_INLINE_VISIBILITY
2838     static _LIBCPP_CONSTEXPR result_type min() { return _Engine::min(); }
2839     _LIBCPP_INLINE_VISIBILITY
2840     static _LIBCPP_CONSTEXPR result_type max() { return _Engine::max(); }
2841
2842     // constructors and seeding functions
2843     _LIBCPP_INLINE_VISIBILITY
2844     discard_block_engine() : __n_(0) {}
2845     _LIBCPP_INLINE_VISIBILITY
2846     explicit discard_block_engine(const _Engine& __e)
2847         : __e_(__e), __n_(0) {}
2848 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2849     _LIBCPP_INLINE_VISIBILITY
2850     explicit discard_block_engine(_Engine&& __e)
2851         : __e_(_VSTD::move(__e)), __n_(0) {}
2852 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2853     _LIBCPP_INLINE_VISIBILITY
2854     explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
2855     template<class _Sseq>
2856         _LIBCPP_INLINE_VISIBILITY
2857         explicit discard_block_engine(_Sseq& __q,
2858         typename enable_if<__is_seed_sequence<_Sseq, discard_block_engine>::value &&
2859                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
2860         : __e_(__q), __n_(0) {}
2861     _LIBCPP_INLINE_VISIBILITY
2862     void seed() {__e_.seed(); __n_ = 0;}
2863     _LIBCPP_INLINE_VISIBILITY
2864     void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
2865     template<class _Sseq>
2866         _LIBCPP_INLINE_VISIBILITY
2867         typename enable_if
2868         <
2869             __is_seed_sequence<_Sseq, discard_block_engine>::value,
2870             void
2871         >::type
2872         seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
2873
2874     // generating functions
2875     result_type operator()();
2876     _LIBCPP_INLINE_VISIBILITY
2877     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2878
2879     // property functions
2880     _LIBCPP_INLINE_VISIBILITY
2881     const _Engine& base() const _NOEXCEPT {return __e_;}
2882
2883     template<class _Eng, size_t _Pp, size_t _Rp>
2884     friend
2885     bool
2886     operator==(
2887         const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2888         const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2889
2890     template<class _Eng, size_t _Pp, size_t _Rp>
2891     friend
2892     bool
2893     operator!=(
2894         const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2895         const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2896
2897     template <class _CharT, class _Traits,
2898               class _Eng, size_t _Pp, size_t _Rp>
2899     friend
2900     basic_ostream<_CharT, _Traits>&
2901     operator<<(basic_ostream<_CharT, _Traits>& __os,
2902                const discard_block_engine<_Eng, _Pp, _Rp>& __x);
2903
2904     template <class _CharT, class _Traits,
2905               class _Eng, size_t _Pp, size_t _Rp>
2906     friend
2907     basic_istream<_CharT, _Traits>&
2908     operator>>(basic_istream<_CharT, _Traits>& __is,
2909                discard_block_engine<_Eng, _Pp, _Rp>& __x);
2910 };
2911
2912 template<class _Engine, size_t __p, size_t __r>
2913     _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::block_size;
2914
2915 template<class _Engine, size_t __p, size_t __r>
2916     _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::used_block;
2917
2918 template<class _Engine, size_t __p, size_t __r>
2919 typename discard_block_engine<_Engine, __p, __r>::result_type
2920 discard_block_engine<_Engine, __p, __r>::operator()()
2921 {
2922     if (__n_ >= static_cast<int>(__r))
2923     {
2924         __e_.discard(__p - __r);
2925         __n_ = 0;
2926     }
2927     ++__n_;
2928     return __e_();
2929 }
2930
2931 template<class _Eng, size_t _Pp, size_t _Rp>
2932 inline _LIBCPP_INLINE_VISIBILITY
2933 bool
2934 operator==(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2935            const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2936 {
2937     return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
2938 }
2939
2940 template<class _Eng, size_t _Pp, size_t _Rp>
2941 inline _LIBCPP_INLINE_VISIBILITY
2942 bool
2943 operator!=(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2944            const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2945 {
2946     return !(__x == __y);
2947 }
2948
2949 template <class _CharT, class _Traits,
2950           class _Eng, size_t _Pp, size_t _Rp>
2951 basic_ostream<_CharT, _Traits>&
2952 operator<<(basic_ostream<_CharT, _Traits>& __os,
2953            const discard_block_engine<_Eng, _Pp, _Rp>& __x)
2954 {
2955     __save_flags<_CharT, _Traits> __lx(__os);
2956     __os.flags(ios_base::dec | ios_base::left);
2957     _CharT __sp = __os.widen(' ');
2958     __os.fill(__sp);
2959     return __os << __x.__e_ << __sp << __x.__n_;
2960 }
2961
2962 template <class _CharT, class _Traits,
2963           class _Eng, size_t _Pp, size_t _Rp>
2964 basic_istream<_CharT, _Traits>&
2965 operator>>(basic_istream<_CharT, _Traits>& __is,
2966            discard_block_engine<_Eng, _Pp, _Rp>& __x)
2967 {
2968     __save_flags<_CharT, _Traits> __lx(__is);
2969     __is.flags(ios_base::dec | ios_base::skipws);
2970     _Eng __e;
2971     int __n;
2972     __is >> __e >> __n;
2973     if (!__is.fail())
2974     {
2975         __x.__e_ = __e;
2976         __x.__n_ = __n;
2977     }
2978     return __is;
2979 }
2980
2981 typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
2982 typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
2983
2984 // independent_bits_engine
2985
2986 template<class _Engine, size_t __w, class _UIntType>
2987 class _LIBCPP_TEMPLATE_VIS independent_bits_engine
2988 {
2989     template <class _UI, _UI _R0, size_t _Wp, size_t _Mp>
2990     class __get_n
2991     {
2992         static _LIBCPP_CONSTEXPR const size_t _Dt = numeric_limits<_UI>::digits;
2993         static _LIBCPP_CONSTEXPR const size_t _Np = _Wp / _Mp + (_Wp % _Mp != 0);
2994         static _LIBCPP_CONSTEXPR const size_t _W0 = _Wp / _Np;
2995         static _LIBCPP_CONSTEXPR const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
2996     public:
2997         static _LIBCPP_CONSTEXPR const size_t value = _R0 - _Y0 > _Y0 / _Np ? _Np + 1 : _Np;
2998     };
2999 public:
3000     // types
3001     typedef _UIntType result_type;
3002
3003 private:
3004     _Engine __e_;
3005
3006     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
3007     static_assert(  0 <  __w, "independent_bits_engine invalid parameters");
3008     static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
3009
3010     typedef typename _Engine::result_type _Engine_result_type;
3011     typedef typename conditional
3012         <
3013             sizeof(_Engine_result_type) <= sizeof(result_type),
3014                 result_type,
3015                 _Engine_result_type
3016         >::type _Working_result_type;
3017 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3018     static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
3019                                           + _Working_result_type(1);
3020 #else
3021     static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
3022                                                             + _Working_result_type(1);
3023 #endif
3024     static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
3025     static _LIBCPP_CONSTEXPR const size_t __n = __get_n<_Working_result_type, _Rp, __w, __m>::value;
3026     static _LIBCPP_CONSTEXPR const size_t __w0 = __w / __n;
3027     static _LIBCPP_CONSTEXPR const size_t __n0 = __n - __w % __n;
3028     static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
3029     static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
3030     static _LIBCPP_CONSTEXPR const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
3031                                                                (_Rp >> __w0) << __w0;
3032     static _LIBCPP_CONSTEXPR const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
3033                                                                (_Rp >> (__w0+1)) << (__w0+1);
3034     static _LIBCPP_CONSTEXPR const _Engine_result_type __mask0 = __w0 > 0 ?
3035                                 _Engine_result_type(~0) >> (_EDt - __w0) :
3036                                 _Engine_result_type(0);
3037     static _LIBCPP_CONSTEXPR const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
3038                                 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
3039                                 _Engine_result_type(~0);
3040 public:
3041     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3042     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
3043                                                       (result_type(1) << __w) - result_type(1);
3044     static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
3045
3046     // engine characteristics
3047     _LIBCPP_INLINE_VISIBILITY
3048     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3049     _LIBCPP_INLINE_VISIBILITY
3050     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3051
3052     // constructors and seeding functions
3053     _LIBCPP_INLINE_VISIBILITY
3054     independent_bits_engine() {}
3055     _LIBCPP_INLINE_VISIBILITY
3056     explicit independent_bits_engine(const _Engine& __e)
3057         : __e_(__e) {}
3058 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3059     _LIBCPP_INLINE_VISIBILITY
3060     explicit independent_bits_engine(_Engine&& __e)
3061         : __e_(_VSTD::move(__e)) {}
3062 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3063     _LIBCPP_INLINE_VISIBILITY
3064     explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
3065     template<class _Sseq>
3066         _LIBCPP_INLINE_VISIBILITY
3067         explicit independent_bits_engine(_Sseq& __q,
3068         typename enable_if<__is_seed_sequence<_Sseq, independent_bits_engine>::value &&
3069                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3070          : __e_(__q) {}
3071     _LIBCPP_INLINE_VISIBILITY
3072     void seed() {__e_.seed();}
3073     _LIBCPP_INLINE_VISIBILITY
3074     void seed(result_type __sd) {__e_.seed(__sd);}
3075     template<class _Sseq>
3076         _LIBCPP_INLINE_VISIBILITY
3077         typename enable_if
3078         <
3079             __is_seed_sequence<_Sseq, independent_bits_engine>::value,
3080             void
3081         >::type
3082         seed(_Sseq& __q) {__e_.seed(__q);}
3083
3084     // generating functions
3085     _LIBCPP_INLINE_VISIBILITY
3086     result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3087     _LIBCPP_INLINE_VISIBILITY
3088     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3089
3090     // property functions
3091     _LIBCPP_INLINE_VISIBILITY
3092     const _Engine& base() const _NOEXCEPT {return __e_;}
3093
3094     template<class _Eng, size_t _Wp, class _UI>
3095     friend
3096     bool
3097     operator==(
3098         const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3099         const independent_bits_engine<_Eng, _Wp, _UI>& __y);
3100
3101     template<class _Eng, size_t _Wp, class _UI>
3102     friend
3103     bool
3104     operator!=(
3105         const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3106         const independent_bits_engine<_Eng, _Wp, _UI>& __y);
3107
3108     template <class _CharT, class _Traits,
3109               class _Eng, size_t _Wp, class _UI>
3110     friend
3111     basic_ostream<_CharT, _Traits>&
3112     operator<<(basic_ostream<_CharT, _Traits>& __os,
3113                const independent_bits_engine<_Eng, _Wp, _UI>& __x);
3114
3115     template <class _CharT, class _Traits,
3116               class _Eng, size_t _Wp, class _UI>
3117     friend
3118     basic_istream<_CharT, _Traits>&
3119     operator>>(basic_istream<_CharT, _Traits>& __is,
3120                independent_bits_engine<_Eng, _Wp, _UI>& __x);
3121
3122 private:
3123     _LIBCPP_INLINE_VISIBILITY
3124     result_type __eval(false_type);
3125     result_type __eval(true_type);
3126
3127     template <size_t __count>
3128         _LIBCPP_INLINE_VISIBILITY
3129         static
3130         typename enable_if
3131         <
3132             __count < _Dt,
3133             result_type
3134         >::type
3135         __lshift(result_type __x) {return __x << __count;}
3136
3137     template <size_t __count>
3138         _LIBCPP_INLINE_VISIBILITY
3139         static
3140         typename enable_if
3141         <
3142             (__count >= _Dt),
3143             result_type
3144         >::type
3145         __lshift(result_type) {return result_type(0);}
3146 };
3147
3148 template<class _Engine, size_t __w, class _UIntType>
3149 inline
3150 _UIntType
3151 independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
3152 {
3153     return static_cast<result_type>(__e_() & __mask0);
3154 }
3155
3156 template<class _Engine, size_t __w, class _UIntType>
3157 _UIntType
3158 independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
3159 {
3160     result_type _Sp = 0;
3161     for (size_t __k = 0; __k < __n0; ++__k)
3162     {
3163         _Engine_result_type __u;
3164         do
3165         {
3166             __u = __e_() - _Engine::min();
3167         } while (__u >= __y0);
3168         _Sp = static_cast<result_type>(__lshift<__w0>(_Sp) + (__u & __mask0));
3169     }
3170     for (size_t __k = __n0; __k < __n; ++__k)
3171     {
3172         _Engine_result_type __u;
3173         do
3174         {
3175             __u = __e_() - _Engine::min();
3176         } while (__u >= __y1);
3177         _Sp = static_cast<result_type>(__lshift<__w0+1>(_Sp) + (__u & __mask1));
3178     }
3179     return _Sp;
3180 }
3181
3182 template<class _Eng, size_t _Wp, class _UI>
3183 inline _LIBCPP_INLINE_VISIBILITY
3184 bool
3185 operator==(
3186     const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3187     const independent_bits_engine<_Eng, _Wp, _UI>& __y)
3188 {
3189     return __x.base() == __y.base();
3190 }
3191
3192 template<class _Eng, size_t _Wp, class _UI>
3193 inline _LIBCPP_INLINE_VISIBILITY
3194 bool
3195 operator!=(
3196     const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3197     const independent_bits_engine<_Eng, _Wp, _UI>& __y)
3198 {
3199     return !(__x == __y);
3200 }
3201
3202 template <class _CharT, class _Traits,
3203           class _Eng, size_t _Wp, class _UI>
3204 basic_ostream<_CharT, _Traits>&
3205 operator<<(basic_ostream<_CharT, _Traits>& __os,
3206            const independent_bits_engine<_Eng, _Wp, _UI>& __x)
3207 {
3208     return __os << __x.base();
3209 }
3210
3211 template <class _CharT, class _Traits,
3212           class _Eng, size_t _Wp, class _UI>
3213 basic_istream<_CharT, _Traits>&
3214 operator>>(basic_istream<_CharT, _Traits>& __is,
3215            independent_bits_engine<_Eng, _Wp, _UI>& __x)
3216 {
3217     _Eng __e;
3218     __is >> __e;
3219     if (!__is.fail())
3220         __x.__e_ = __e;
3221     return __is;
3222 }
3223
3224 // shuffle_order_engine
3225
3226 template <uint64_t _Xp, uint64_t _Yp>
3227 struct __ugcd
3228 {
3229     static _LIBCPP_CONSTEXPR const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
3230 };
3231
3232 template <uint64_t _Xp>
3233 struct __ugcd<_Xp, 0>
3234 {
3235     static _LIBCPP_CONSTEXPR const uint64_t value = _Xp;
3236 };
3237
3238 template <uint64_t _Np, uint64_t _Dp>
3239 class __uratio
3240 {
3241     static_assert(_Dp != 0, "__uratio divide by 0");
3242     static _LIBCPP_CONSTEXPR const uint64_t __gcd = __ugcd<_Np, _Dp>::value;
3243 public:
3244     static _LIBCPP_CONSTEXPR const uint64_t num = _Np / __gcd;
3245     static _LIBCPP_CONSTEXPR const uint64_t den = _Dp / __gcd;
3246
3247     typedef __uratio<num, den> type;
3248 };
3249
3250 template<class _Engine, size_t __k>
3251 class _LIBCPP_TEMPLATE_VIS shuffle_order_engine
3252 {
3253     static_assert(0 < __k, "shuffle_order_engine invalid parameters");
3254 public:
3255     // types
3256     typedef typename _Engine::result_type result_type;
3257
3258 private:
3259     _Engine __e_;
3260     result_type _V_[__k];
3261     result_type _Y_;
3262
3263 public:
3264     // engine characteristics
3265     static _LIBCPP_CONSTEXPR const size_t table_size = __k;
3266
3267 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3268     static const result_type _Min = _Engine::_Min;
3269     static const result_type _Max = _Engine::_Max;
3270 #else
3271     static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
3272     static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
3273 #endif
3274     static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
3275     _LIBCPP_INLINE_VISIBILITY
3276     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3277     _LIBCPP_INLINE_VISIBILITY
3278     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3279
3280     static _LIBCPP_CONSTEXPR const unsigned long long _Rp = _Max - _Min + 1ull;
3281
3282     // constructors and seeding functions
3283     _LIBCPP_INLINE_VISIBILITY
3284     shuffle_order_engine() {__init();}
3285     _LIBCPP_INLINE_VISIBILITY
3286     explicit shuffle_order_engine(const _Engine& __e)
3287         : __e_(__e) {__init();}
3288 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3289     _LIBCPP_INLINE_VISIBILITY
3290     explicit shuffle_order_engine(_Engine&& __e)
3291         : __e_(_VSTD::move(__e)) {__init();}
3292 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3293     _LIBCPP_INLINE_VISIBILITY
3294     explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
3295     template<class _Sseq>
3296         _LIBCPP_INLINE_VISIBILITY
3297         explicit shuffle_order_engine(_Sseq& __q,
3298         typename enable_if<__is_seed_sequence<_Sseq, shuffle_order_engine>::value &&
3299                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3300          : __e_(__q) {__init();}
3301     _LIBCPP_INLINE_VISIBILITY
3302     void seed() {__e_.seed(); __init();}
3303     _LIBCPP_INLINE_VISIBILITY
3304     void seed(result_type __sd) {__e_.seed(__sd); __init();}
3305     template<class _Sseq>
3306         _LIBCPP_INLINE_VISIBILITY
3307         typename enable_if
3308         <
3309             __is_seed_sequence<_Sseq, shuffle_order_engine>::value,
3310             void
3311         >::type
3312         seed(_Sseq& __q) {__e_.seed(__q); __init();}
3313
3314     // generating functions
3315     _LIBCPP_INLINE_VISIBILITY
3316     result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3317     _LIBCPP_INLINE_VISIBILITY
3318     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3319
3320     // property functions
3321     _LIBCPP_INLINE_VISIBILITY
3322     const _Engine& base() const _NOEXCEPT {return __e_;}
3323
3324 private:
3325     template<class _Eng, size_t _Kp>
3326     friend
3327     bool
3328     operator==(
3329         const shuffle_order_engine<_Eng, _Kp>& __x,
3330         const shuffle_order_engine<_Eng, _Kp>& __y);
3331
3332     template<class _Eng, size_t _Kp>
3333     friend
3334     bool
3335     operator!=(
3336         const shuffle_order_engine<_Eng, _Kp>& __x,
3337         const shuffle_order_engine<_Eng, _Kp>& __y);
3338
3339     template <class _CharT, class _Traits,
3340               class _Eng, size_t _Kp>
3341     friend
3342     basic_ostream<_CharT, _Traits>&
3343     operator<<(basic_ostream<_CharT, _Traits>& __os,
3344                const shuffle_order_engine<_Eng, _Kp>& __x);
3345
3346     template <class _CharT, class _Traits,
3347               class _Eng, size_t _Kp>
3348     friend
3349     basic_istream<_CharT, _Traits>&
3350     operator>>(basic_istream<_CharT, _Traits>& __is,
3351                shuffle_order_engine<_Eng, _Kp>& __x);
3352
3353     _LIBCPP_INLINE_VISIBILITY
3354     void __init()
3355     {
3356         for (size_t __i = 0; __i < __k; ++__i)
3357             _V_[__i] = __e_();
3358         _Y_ = __e_();
3359     }
3360
3361     _LIBCPP_INLINE_VISIBILITY
3362     result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
3363     _LIBCPP_INLINE_VISIBILITY
3364     result_type __eval(true_type) {return __eval(__uratio<__k, _Rp>());}
3365
3366     _LIBCPP_INLINE_VISIBILITY
3367     result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
3368     _LIBCPP_INLINE_VISIBILITY
3369     result_type __eval2(true_type) {return __evalf<__k, 0>();}
3370
3371     template <uint64_t _Np, uint64_t _Dp>
3372         _LIBCPP_INLINE_VISIBILITY
3373         typename enable_if
3374         <
3375             (__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
3376             result_type
3377         >::type
3378         __eval(__uratio<_Np, _Dp>)
3379             {return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();}
3380
3381     template <uint64_t _Np, uint64_t _Dp>
3382         _LIBCPP_INLINE_VISIBILITY
3383         typename enable_if
3384         <
3385             __uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
3386             result_type
3387         >::type
3388         __eval(__uratio<_Np, _Dp>)
3389         {
3390             const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (_Y_ - _Min)
3391                                                    / __uratio<_Np, _Dp>::den);
3392             _Y_ = _V_[__j];
3393             _V_[__j] = __e_();
3394             return _Y_;
3395         }
3396
3397     template <uint64_t __n, uint64_t __d>
3398         _LIBCPP_INLINE_VISIBILITY
3399         result_type __evalf()
3400         {
3401             const double _Fp = __d == 0 ?
3402                 __n / (2. * 0x8000000000000000ull) :
3403                 __n / (double)__d;
3404             const size_t __j = static_cast<size_t>(_Fp * (_Y_ - _Min));
3405             _Y_ = _V_[__j];
3406             _V_[__j] = __e_();
3407             return _Y_;
3408         }
3409 };
3410
3411 template<class _Engine, size_t __k>
3412     _LIBCPP_CONSTEXPR const size_t shuffle_order_engine<_Engine, __k>::table_size;
3413
3414 template<class _Eng, size_t _Kp>
3415 bool
3416 operator==(
3417     const shuffle_order_engine<_Eng, _Kp>& __x,
3418     const shuffle_order_engine<_Eng, _Kp>& __y)
3419 {
3420     return __x._Y_ == __y._Y_ && _VSTD::equal(__x._V_, __x._V_ + _Kp, __y._V_) &&
3421            __x.__e_ == __y.__e_;
3422 }
3423
3424 template<class _Eng, size_t _Kp>
3425 inline _LIBCPP_INLINE_VISIBILITY
3426 bool
3427 operator!=(
3428     const shuffle_order_engine<_Eng, _Kp>& __x,
3429     const shuffle_order_engine<_Eng, _Kp>& __y)
3430 {
3431     return !(__x == __y);
3432 }
3433
3434 template <class _CharT, class _Traits,
3435           class _Eng, size_t _Kp>
3436 basic_ostream<_CharT, _Traits>&
3437 operator<<(basic_ostream<_CharT, _Traits>& __os,
3438            const shuffle_order_engine<_Eng, _Kp>& __x)
3439 {
3440     __save_flags<_CharT, _Traits> __lx(__os);
3441     __os.flags(ios_base::dec | ios_base::left);
3442     _CharT __sp = __os.widen(' ');
3443     __os.fill(__sp);
3444     __os << __x.__e_ << __sp << __x._V_[0];
3445     for (size_t __i = 1; __i < _Kp; ++__i)
3446         __os << __sp << __x._V_[__i];
3447     return __os << __sp << __x._Y_;
3448 }
3449
3450 template <class _CharT, class _Traits,
3451           class _Eng, size_t _Kp>
3452 basic_istream<_CharT, _Traits>&
3453 operator>>(basic_istream<_CharT, _Traits>& __is,
3454            shuffle_order_engine<_Eng, _Kp>& __x)
3455 {
3456     typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type;
3457     __save_flags<_CharT, _Traits> __lx(__is);
3458     __is.flags(ios_base::dec | ios_base::skipws);
3459     _Eng __e;
3460     result_type _Vp[_Kp+1];
3461     __is >> __e;
3462     for (size_t __i = 0; __i < _Kp+1; ++__i)
3463         __is >> _Vp[__i];
3464     if (!__is.fail())
3465     {
3466         __x.__e_ = __e;
3467         for (size_t __i = 0; __i < _Kp; ++__i)
3468             __x._V_[__i] = _Vp[__i];
3469         __x._Y_ = _Vp[_Kp];
3470     }
3471     return __is;
3472 }
3473
3474 typedef shuffle_order_engine<minstd_rand0, 256>                         knuth_b;
3475
3476 // random_device
3477
3478 class _LIBCPP_TYPE_VIS random_device
3479 {
3480 #ifdef _LIBCPP_USING_DEV_RANDOM
3481     int __f_;
3482 #endif // defined(_LIBCPP_USING_DEV_RANDOM)
3483 public:
3484     // types
3485     typedef unsigned result_type;
3486
3487     // generator characteristics
3488     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3489     static _LIBCPP_CONSTEXPR const result_type _Max = 0xFFFFFFFFu;
3490
3491     _LIBCPP_INLINE_VISIBILITY
3492     static _LIBCPP_CONSTEXPR result_type min() { return _Min;}
3493     _LIBCPP_INLINE_VISIBILITY
3494     static _LIBCPP_CONSTEXPR result_type max() { return _Max;}
3495
3496     // constructors
3497     explicit random_device(const string& __token = "/dev/urandom");
3498     ~random_device();
3499
3500     // generating functions
3501     result_type operator()();
3502
3503     // property functions
3504     double entropy() const _NOEXCEPT;
3505
3506 private:
3507     // no copy functions
3508     random_device(const random_device&); // = delete;
3509     random_device& operator=(const random_device&); // = delete;
3510 };
3511
3512 // seed_seq
3513
3514 class _LIBCPP_TEMPLATE_VIS seed_seq
3515 {
3516 public:
3517     // types
3518     typedef uint32_t result_type;
3519
3520 private:
3521     vector<result_type> __v_;
3522
3523     template<class _InputIterator>
3524         void init(_InputIterator __first, _InputIterator __last);
3525 public:
3526     // constructors
3527     _LIBCPP_INLINE_VISIBILITY
3528     seed_seq() _NOEXCEPT {}
3529 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
3530     template<class _Tp>
3531         _LIBCPP_INLINE_VISIBILITY
3532         seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
3533 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
3534
3535     template<class _InputIterator>
3536         _LIBCPP_INLINE_VISIBILITY
3537         seed_seq(_InputIterator __first, _InputIterator __last)
3538              {init(__first, __last);}
3539
3540     // generating functions
3541     template<class _RandomAccessIterator>
3542         void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
3543
3544     // property functions
3545     _LIBCPP_INLINE_VISIBILITY
3546     size_t size() const _NOEXCEPT {return __v_.size();}
3547     template<class _OutputIterator>
3548         _LIBCPP_INLINE_VISIBILITY
3549         void param(_OutputIterator __dest) const
3550             {_VSTD::copy(__v_.begin(), __v_.end(), __dest);}
3551
3552 private:
3553     // no copy functions
3554     seed_seq(const seed_seq&); // = delete;
3555     void operator=(const seed_seq&); // = delete;
3556
3557     _LIBCPP_INLINE_VISIBILITY
3558     static result_type _Tp(result_type __x) {return __x ^ (__x >> 27);}
3559 };
3560
3561 template<class _InputIterator>
3562 void
3563 seed_seq::init(_InputIterator __first, _InputIterator __last)
3564 {
3565     for (_InputIterator __s = __first; __s != __last; ++__s)
3566         __v_.push_back(*__s & 0xFFFFFFFF);
3567 }
3568
3569 template<class _RandomAccessIterator>
3570 void
3571 seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
3572 {
3573     if (__first != __last)
3574     {
3575         _VSTD::fill(__first, __last, 0x8b8b8b8b);
3576         const size_t __n = static_cast<size_t>(__last - __first);
3577         const size_t __s = __v_.size();
3578         const size_t __t = (__n >= 623) ? 11
3579                          : (__n >= 68) ? 7
3580                          : (__n >= 39) ? 5
3581                          : (__n >= 7)  ? 3
3582                          : (__n - 1) / 2;
3583         const size_t __p = (__n - __t) / 2;
3584         const size_t __q = __p + __t;
3585         const size_t __m = _VSTD::max(__s + 1, __n);
3586         // __k = 0;
3587         {
3588             result_type __r = 1664525 * _Tp(__first[0] ^ __first[__p]
3589                                                       ^  __first[__n - 1]);
3590             __first[__p] += __r;
3591             __r += __s;
3592             __first[__q] += __r;
3593             __first[0] = __r;
3594         }
3595         for (size_t __k = 1; __k <= __s; ++__k)
3596         {
3597             const size_t __kmodn = __k % __n;
3598             const size_t __kpmodn = (__k + __p) % __n;
3599             result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3600                                            ^ __first[(__k - 1) % __n]);
3601             __first[__kpmodn] += __r;
3602             __r +=  __kmodn + __v_[__k-1];
3603             __first[(__k + __q) % __n] += __r;
3604             __first[__kmodn] = __r;
3605         }
3606         for (size_t __k = __s + 1; __k < __m; ++__k)
3607         {
3608             const size_t __kmodn = __k % __n;
3609             const size_t __kpmodn = (__k + __p) % __n;
3610             result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3611                                            ^ __first[(__k - 1) % __n]);
3612             __first[__kpmodn] += __r;
3613             __r +=  __kmodn;
3614             __first[(__k + __q) % __n] += __r;
3615             __first[__kmodn] = __r;
3616         }
3617         for (size_t __k = __m; __k < __m + __n; ++__k)
3618         {
3619             const size_t __kmodn = __k % __n;
3620             const size_t __kpmodn = (__k + __p) % __n;
3621             result_type __r = 1566083941 * _Tp(__first[__kmodn] +
3622                                               __first[__kpmodn] +
3623                                               __first[(__k - 1) % __n]);
3624             __first[__kpmodn] ^= __r;
3625             __r -= __kmodn;
3626             __first[(__k + __q) % __n] ^= __r;
3627             __first[__kmodn] = __r;
3628         }
3629     }
3630 }
3631
3632 // generate_canonical
3633
3634 template<class _RealType, size_t __bits, class _URNG>
3635 _RealType
3636 generate_canonical(_URNG& __g)
3637 {
3638     const size_t _Dt = numeric_limits<_RealType>::digits;
3639     const size_t __b = _Dt < __bits ? _Dt : __bits;
3640 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3641     const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
3642 #else
3643     const size_t __logR = __log2<uint64_t, _URNG::max() - _URNG::min() + uint64_t(1)>::value;
3644 #endif
3645     const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
3646     const _RealType _Rp = _URNG::max() - _URNG::min() + _RealType(1);
3647     _RealType __base = _Rp;
3648     _RealType _Sp = __g() - _URNG::min();
3649     for (size_t __i = 1; __i < __k; ++__i, __base *= _Rp)
3650         _Sp += (__g() - _URNG::min()) * __base;
3651     return _Sp / __base;
3652 }
3653
3654 // uniform_int_distribution
3655
3656 // in <algorithm>
3657
3658 template <class _CharT, class _Traits, class _IT>
3659 basic_ostream<_CharT, _Traits>&
3660 operator<<(basic_ostream<_CharT, _Traits>& __os,
3661            const uniform_int_distribution<_IT>& __x)
3662 {
3663     __save_flags<_CharT, _Traits> __lx(__os);
3664     __os.flags(ios_base::dec | ios_base::left);
3665     _CharT __sp = __os.widen(' ');
3666     __os.fill(__sp);
3667     return __os << __x.a() << __sp << __x.b();
3668 }
3669
3670 template <class _CharT, class _Traits, class _IT>
3671 basic_istream<_CharT, _Traits>&
3672 operator>>(basic_istream<_CharT, _Traits>& __is,
3673            uniform_int_distribution<_IT>& __x)
3674 {
3675     typedef uniform_int_distribution<_IT> _Eng;
3676     typedef typename _Eng::result_type result_type;
3677     typedef typename _Eng::param_type param_type;
3678     __save_flags<_CharT, _Traits> __lx(__is);
3679     __is.flags(ios_base::dec | ios_base::skipws);
3680     result_type __a;
3681     result_type __b;
3682     __is >> __a >> __b;
3683     if (!__is.fail())
3684         __x.param(param_type(__a, __b));
3685     return __is;
3686 }
3687
3688 // uniform_real_distribution
3689
3690 template<class _RealType = double>
3691 class _LIBCPP_TEMPLATE_VIS uniform_real_distribution
3692 {
3693 public:
3694     // types
3695     typedef _RealType result_type;
3696
3697     class _LIBCPP_TEMPLATE_VIS param_type
3698     {
3699         result_type __a_;
3700         result_type __b_;
3701     public:
3702         typedef uniform_real_distribution distribution_type;
3703
3704         _LIBCPP_INLINE_VISIBILITY
3705         explicit param_type(result_type __a = 0,
3706                             result_type __b = 1)
3707             : __a_(__a), __b_(__b) {}
3708
3709         _LIBCPP_INLINE_VISIBILITY
3710         result_type a() const {return __a_;}
3711         _LIBCPP_INLINE_VISIBILITY
3712         result_type b() const {return __b_;}
3713
3714         friend _LIBCPP_INLINE_VISIBILITY
3715         bool operator==(const param_type& __x, const param_type& __y)
3716             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3717         friend _LIBCPP_INLINE_VISIBILITY
3718         bool operator!=(const param_type& __x, const param_type& __y)
3719             {return !(__x == __y);}
3720     };
3721
3722 private:
3723     param_type __p_;
3724
3725 public:
3726     // constructors and reset functions
3727     _LIBCPP_INLINE_VISIBILITY
3728     explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
3729         : __p_(param_type(__a, __b)) {}
3730     _LIBCPP_INLINE_VISIBILITY
3731     explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
3732     _LIBCPP_INLINE_VISIBILITY
3733     void reset() {}
3734
3735     // generating functions
3736     template<class _URNG>
3737         _LIBCPP_INLINE_VISIBILITY
3738         result_type operator()(_URNG& __g)
3739         {return (*this)(__g, __p_);}
3740     template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
3741
3742     // property functions
3743     _LIBCPP_INLINE_VISIBILITY
3744     result_type a() const {return __p_.a();}
3745     _LIBCPP_INLINE_VISIBILITY
3746     result_type b() const {return __p_.b();}
3747
3748     _LIBCPP_INLINE_VISIBILITY
3749     param_type param() const {return __p_;}
3750     _LIBCPP_INLINE_VISIBILITY
3751     void param(const param_type& __p) {__p_ = __p;}
3752
3753     _LIBCPP_INLINE_VISIBILITY
3754     result_type min() const {return a();}
3755     _LIBCPP_INLINE_VISIBILITY
3756     result_type max() const {return b();}
3757
3758     friend _LIBCPP_INLINE_VISIBILITY
3759         bool operator==(const uniform_real_distribution& __x,
3760                         const uniform_real_distribution& __y)
3761         {return __x.__p_ == __y.__p_;}
3762     friend _LIBCPP_INLINE_VISIBILITY
3763         bool operator!=(const uniform_real_distribution& __x,
3764                         const uniform_real_distribution& __y)
3765         {return !(__x == __y);}
3766 };
3767
3768 template<class _RealType>
3769 template<class _URNG>
3770 inline
3771 typename uniform_real_distribution<_RealType>::result_type
3772 uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3773 {
3774     return (__p.b() - __p.a())
3775         * _VSTD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
3776         + __p.a();
3777 }
3778
3779 template <class _CharT, class _Traits, class _RT>
3780 basic_ostream<_CharT, _Traits>&
3781 operator<<(basic_ostream<_CharT, _Traits>& __os,
3782            const uniform_real_distribution<_RT>& __x)
3783 {
3784     __save_flags<_CharT, _Traits> __lx(__os);
3785     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3786                ios_base::scientific);
3787     _CharT __sp = __os.widen(' ');
3788     __os.fill(__sp);
3789     return __os << __x.a() << __sp << __x.b();
3790 }
3791
3792 template <class _CharT, class _Traits, class _RT>
3793 basic_istream<_CharT, _Traits>&
3794 operator>>(basic_istream<_CharT, _Traits>& __is,
3795            uniform_real_distribution<_RT>& __x)
3796 {
3797     typedef uniform_real_distribution<_RT> _Eng;
3798     typedef typename _Eng::result_type result_type;
3799     typedef typename _Eng::param_type param_type;
3800     __save_flags<_CharT, _Traits> __lx(__is);
3801     __is.flags(ios_base::dec | ios_base::skipws);
3802     result_type __a;
3803     result_type __b;
3804     __is >> __a >> __b;
3805     if (!__is.fail())
3806         __x.param(param_type(__a, __b));
3807     return __is;
3808 }
3809
3810 // bernoulli_distribution
3811
3812 class _LIBCPP_TEMPLATE_VIS bernoulli_distribution
3813 {
3814 public:
3815     // types
3816     typedef bool result_type;
3817
3818     class _LIBCPP_TEMPLATE_VIS param_type
3819     {
3820         double __p_;
3821     public:
3822         typedef bernoulli_distribution distribution_type;
3823
3824         _LIBCPP_INLINE_VISIBILITY
3825         explicit param_type(double __p = 0.5) : __p_(__p) {}
3826
3827         _LIBCPP_INLINE_VISIBILITY
3828         double p() const {return __p_;}
3829
3830         friend _LIBCPP_INLINE_VISIBILITY
3831             bool operator==(const param_type& __x, const param_type& __y)
3832             {return __x.__p_ == __y.__p_;}
3833         friend _LIBCPP_INLINE_VISIBILITY
3834             bool operator!=(const param_type& __x, const param_type& __y)
3835             {return !(__x == __y);}
3836     };
3837
3838 private:
3839     param_type __p_;
3840
3841 public:
3842     // constructors and reset functions
3843     _LIBCPP_INLINE_VISIBILITY
3844     explicit bernoulli_distribution(double __p = 0.5)
3845         : __p_(param_type(__p)) {}
3846     _LIBCPP_INLINE_VISIBILITY
3847     explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
3848     _LIBCPP_INLINE_VISIBILITY
3849     void reset() {}
3850
3851     // generating functions
3852     template<class _URNG>
3853         _LIBCPP_INLINE_VISIBILITY
3854         result_type operator()(_URNG& __g)
3855         {return (*this)(__g, __p_);}
3856     template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
3857
3858     // property functions
3859     _LIBCPP_INLINE_VISIBILITY
3860     double p() const {return __p_.p();}
3861
3862     _LIBCPP_INLINE_VISIBILITY
3863     param_type param() const {return __p_;}
3864     _LIBCPP_INLINE_VISIBILITY
3865     void param(const param_type& __p) {__p_ = __p;}
3866
3867     _LIBCPP_INLINE_VISIBILITY
3868     result_type min() const {return false;}
3869     _LIBCPP_INLINE_VISIBILITY
3870     result_type max() const {return true;}
3871
3872     friend _LIBCPP_INLINE_VISIBILITY
3873         bool operator==(const bernoulli_distribution& __x,
3874                         const bernoulli_distribution& __y)
3875         {return __x.__p_ == __y.__p_;}
3876     friend _LIBCPP_INLINE_VISIBILITY
3877         bool operator!=(const bernoulli_distribution& __x,
3878                         const bernoulli_distribution& __y)
3879         {return !(__x == __y);}
3880 };
3881
3882 template<class _URNG>
3883 inline
3884 bernoulli_distribution::result_type
3885 bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
3886 {
3887     uniform_real_distribution<double> __gen;
3888     return __gen(__g) < __p.p();
3889 }
3890
3891 template <class _CharT, class _Traits>
3892 basic_ostream<_CharT, _Traits>&
3893 operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
3894 {
3895     __save_flags<_CharT, _Traits> __lx(__os);
3896     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3897                ios_base::scientific);
3898     _CharT __sp = __os.widen(' ');
3899     __os.fill(__sp);
3900     return __os << __x.p();
3901 }
3902
3903 template <class _CharT, class _Traits>
3904 basic_istream<_CharT, _Traits>&
3905 operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
3906 {
3907     typedef bernoulli_distribution _Eng;
3908     typedef typename _Eng::param_type param_type;
3909     __save_flags<_CharT, _Traits> __lx(__is);
3910     __is.flags(ios_base::dec | ios_base::skipws);
3911     double __p;
3912     __is >> __p;
3913     if (!__is.fail())
3914         __x.param(param_type(__p));
3915     return __is;
3916 }
3917
3918 // binomial_distribution
3919
3920 template<class _IntType = int>
3921 class _LIBCPP_TEMPLATE_VIS binomial_distribution
3922 {
3923 public:
3924     // types
3925     typedef _IntType result_type;
3926
3927     class _LIBCPP_TEMPLATE_VIS param_type
3928     {
3929         result_type __t_;
3930         double __p_;
3931         double __pr_;
3932         double __odds_ratio_;
3933         result_type __r0_;
3934     public:
3935         typedef binomial_distribution distribution_type;
3936
3937         explicit param_type(result_type __t = 1, double __p = 0.5);
3938
3939         _LIBCPP_INLINE_VISIBILITY
3940         result_type t() const {return __t_;}
3941         _LIBCPP_INLINE_VISIBILITY
3942         double p() const {return __p_;}
3943
3944         friend _LIBCPP_INLINE_VISIBILITY
3945             bool operator==(const param_type& __x, const param_type& __y)
3946             {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
3947         friend _LIBCPP_INLINE_VISIBILITY
3948             bool operator!=(const param_type& __x, const param_type& __y)
3949             {return !(__x == __y);}
3950
3951         friend class binomial_distribution;
3952     };
3953
3954 private:
3955     param_type __p_;
3956
3957 public:
3958     // constructors and reset functions
3959     _LIBCPP_INLINE_VISIBILITY
3960     explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
3961         : __p_(param_type(__t, __p)) {}
3962     _LIBCPP_INLINE_VISIBILITY
3963     explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
3964     _LIBCPP_INLINE_VISIBILITY
3965     void reset() {}
3966
3967     // generating functions
3968     template<class _URNG>
3969         _LIBCPP_INLINE_VISIBILITY
3970         result_type operator()(_URNG& __g)
3971         {return (*this)(__g, __p_);}
3972     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3973
3974     // property functions
3975     _LIBCPP_INLINE_VISIBILITY
3976     result_type t() const {return __p_.t();}
3977     _LIBCPP_INLINE_VISIBILITY
3978     double p() const {return __p_.p();}
3979
3980     _LIBCPP_INLINE_VISIBILITY
3981     param_type param() const {return __p_;}
3982     _LIBCPP_INLINE_VISIBILITY
3983     void param(const param_type& __p) {__p_ = __p;}
3984
3985     _LIBCPP_INLINE_VISIBILITY
3986     result_type min() const {return 0;}
3987     _LIBCPP_INLINE_VISIBILITY
3988     result_type max() const {return t();}
3989
3990     friend _LIBCPP_INLINE_VISIBILITY
3991         bool operator==(const binomial_distribution& __x,
3992                         const binomial_distribution& __y)
3993         {return __x.__p_ == __y.__p_;}
3994     friend _LIBCPP_INLINE_VISIBILITY
3995         bool operator!=(const binomial_distribution& __x,
3996                         const binomial_distribution& __y)
3997         {return !(__x == __y);}
3998 };
3999
4000 template<class _IntType>
4001 binomial_distribution<_IntType>::param_type::param_type(result_type __t, double __p)
4002     : __t_(__t), __p_(__p)
4003 {
4004     if (0 < __p_ && __p_ < 1)
4005     {
4006         __r0_ = static_cast<result_type>((__t_ + 1) * __p_);
4007         __pr_ = _VSTD::exp(_VSTD::lgamma(__t_ + 1.) - _VSTD::lgamma(__r0_ + 1.) -
4008                           _VSTD::lgamma(__t_ - __r0_ + 1.) + __r0_ * _VSTD::log(__p_) +
4009                           (__t_ - __r0_) * _VSTD::log(1 - __p_));
4010         __odds_ratio_ = __p_ / (1 - __p_);
4011     }
4012 }
4013
4014 // Reference: Kemp, C.D. (1986). `A modal method for generating binomial
4015 //           variables', Commun. Statist. - Theor. Meth. 15(3), 805-813.
4016 template<class _IntType>
4017 template<class _URNG>
4018 _IntType
4019 binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __pr)
4020 {
4021     if (__pr.__t_ == 0 || __pr.__p_ == 0)
4022         return 0;
4023     if (__pr.__p_ == 1)
4024         return __pr.__t_;
4025     uniform_real_distribution<double> __gen;
4026     double __u = __gen(__g) - __pr.__pr_;
4027     if (__u < 0)
4028         return __pr.__r0_;
4029     double __pu = __pr.__pr_;
4030     double __pd = __pu;
4031     result_type __ru = __pr.__r0_;
4032     result_type __rd = __ru;
4033     while (true)
4034     {
4035         if (__rd >= 1)
4036         {
4037             __pd *= __rd / (__pr.__odds_ratio_ * (__pr.__t_ - __rd + 1));
4038             __u -= __pd;
4039             if (__u < 0)
4040                 return __rd - 1;
4041         }
4042         if ( __rd != 0 )
4043             --__rd;
4044         ++__ru;
4045         if (__ru <= __pr.__t_)
4046         {
4047             __pu *= (__pr.__t_ - __ru + 1) * __pr.__odds_ratio_ / __ru;
4048             __u -= __pu;
4049             if (__u < 0)
4050                 return __ru;
4051         }
4052     }
4053 }
4054
4055 template <class _CharT, class _Traits, class _IntType>
4056 basic_ostream<_CharT, _Traits>&
4057 operator<<(basic_ostream<_CharT, _Traits>& __os,
4058            const binomial_distribution<_IntType>& __x)
4059 {
4060     __save_flags<_CharT, _Traits> __lx(__os);
4061     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4062                ios_base::scientific);
4063     _CharT __sp = __os.widen(' ');
4064     __os.fill(__sp);
4065     return __os << __x.t() << __sp << __x.p();
4066 }
4067
4068 template <class _CharT, class _Traits, class _IntType>
4069 basic_istream<_CharT, _Traits>&
4070 operator>>(basic_istream<_CharT, _Traits>& __is,
4071            binomial_distribution<_IntType>& __x)
4072 {
4073     typedef binomial_distribution<_IntType> _Eng;
4074     typedef typename _Eng::result_type result_type;
4075     typedef typename _Eng::param_type param_type;
4076     __save_flags<_CharT, _Traits> __lx(__is);
4077     __is.flags(ios_base::dec | ios_base::skipws);
4078     result_type __t;
4079     double __p;
4080     __is >> __t >> __p;
4081     if (!__is.fail())
4082         __x.param(param_type(__t, __p));
4083     return __is;
4084 }
4085
4086 // exponential_distribution
4087
4088 template<class _RealType = double>
4089 class _LIBCPP_TEMPLATE_VIS exponential_distribution
4090 {
4091 public:
4092     // types
4093     typedef _RealType result_type;
4094
4095     class _LIBCPP_TEMPLATE_VIS param_type
4096     {
4097         result_type __lambda_;
4098     public:
4099         typedef exponential_distribution distribution_type;
4100
4101         _LIBCPP_INLINE_VISIBILITY
4102         explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {}
4103
4104         _LIBCPP_INLINE_VISIBILITY
4105         result_type lambda() const {return __lambda_;}
4106
4107         friend _LIBCPP_INLINE_VISIBILITY
4108             bool operator==(const param_type& __x, const param_type& __y)
4109             {return __x.__lambda_ == __y.__lambda_;}
4110         friend _LIBCPP_INLINE_VISIBILITY
4111             bool operator!=(const param_type& __x, const param_type& __y)
4112             {return !(__x == __y);}
4113     };
4114
4115 private:
4116     param_type __p_;
4117
4118 public:
4119     // constructors and reset functions
4120     _LIBCPP_INLINE_VISIBILITY
4121     explicit exponential_distribution(result_type __lambda = 1)
4122         : __p_(param_type(__lambda)) {}
4123     _LIBCPP_INLINE_VISIBILITY
4124     explicit exponential_distribution(const param_type& __p) : __p_(__p) {}
4125     _LIBCPP_INLINE_VISIBILITY
4126     void reset() {}
4127
4128     // generating functions
4129     template<class _URNG>
4130         _LIBCPP_INLINE_VISIBILITY
4131         result_type operator()(_URNG& __g)
4132         {return (*this)(__g, __p_);}
4133     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4134
4135     // property functions
4136     _LIBCPP_INLINE_VISIBILITY
4137     result_type lambda() const {return __p_.lambda();}
4138
4139     _LIBCPP_INLINE_VISIBILITY
4140     param_type param() const {return __p_;}
4141     _LIBCPP_INLINE_VISIBILITY
4142     void param(const param_type& __p) {__p_ = __p;}
4143
4144     _LIBCPP_INLINE_VISIBILITY
4145     result_type min() const {return 0;}
4146     _LIBCPP_INLINE_VISIBILITY
4147     result_type max() const {return numeric_limits<result_type>::infinity();}
4148
4149     friend _LIBCPP_INLINE_VISIBILITY
4150         bool operator==(const exponential_distribution& __x,
4151                         const exponential_distribution& __y)
4152         {return __x.__p_ == __y.__p_;}
4153     friend _LIBCPP_INLINE_VISIBILITY
4154         bool operator!=(const exponential_distribution& __x,
4155                         const exponential_distribution& __y)
4156         {return !(__x == __y);}
4157 };
4158
4159 template <class _RealType>
4160 template<class _URNG>
4161 _RealType
4162 exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4163 {
4164     return -_VSTD::log
4165                   (
4166                       result_type(1) -
4167                       _VSTD::generate_canonical<result_type,
4168                                        numeric_limits<result_type>::digits>(__g)
4169                   )
4170                   / __p.lambda();
4171 }
4172
4173 template <class _CharT, class _Traits, class _RealType>
4174 basic_ostream<_CharT, _Traits>&
4175 operator<<(basic_ostream<_CharT, _Traits>& __os,
4176            const exponential_distribution<_RealType>& __x)
4177 {
4178     __save_flags<_CharT, _Traits> __lx(__os);
4179     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4180                ios_base::scientific);
4181     return __os << __x.lambda();
4182 }
4183
4184 template <class _CharT, class _Traits, class _RealType>
4185 basic_istream<_CharT, _Traits>&
4186 operator>>(basic_istream<_CharT, _Traits>& __is,
4187            exponential_distribution<_RealType>& __x)
4188 {
4189     typedef exponential_distribution<_RealType> _Eng;
4190     typedef typename _Eng::result_type result_type;
4191     typedef typename _Eng::param_type param_type;
4192     __save_flags<_CharT, _Traits> __lx(__is);
4193     __is.flags(ios_base::dec | ios_base::skipws);
4194     result_type __lambda;
4195     __is >> __lambda;
4196     if (!__is.fail())
4197         __x.param(param_type(__lambda));
4198     return __is;
4199 }
4200
4201 // normal_distribution
4202
4203 template<class _RealType = double>
4204 class _LIBCPP_TEMPLATE_VIS normal_distribution
4205 {
4206 public:
4207     // types
4208     typedef _RealType result_type;
4209
4210     class _LIBCPP_TEMPLATE_VIS param_type
4211     {
4212         result_type __mean_;
4213         result_type __stddev_;
4214     public:
4215         typedef normal_distribution distribution_type;
4216
4217         _LIBCPP_INLINE_VISIBILITY
4218         explicit param_type(result_type __mean = 0, result_type __stddev = 1)
4219             : __mean_(__mean), __stddev_(__stddev) {}
4220
4221         _LIBCPP_INLINE_VISIBILITY
4222         result_type mean() const {return __mean_;}
4223         _LIBCPP_INLINE_VISIBILITY
4224         result_type stddev() const {return __stddev_;}
4225
4226         friend _LIBCPP_INLINE_VISIBILITY
4227             bool operator==(const param_type& __x, const param_type& __y)
4228             {return __x.__mean_ == __y.__mean_ && __x.__stddev_ == __y.__stddev_;}
4229         friend _LIBCPP_INLINE_VISIBILITY
4230             bool operator!=(const param_type& __x, const param_type& __y)
4231             {return !(__x == __y);}
4232     };
4233
4234 private:
4235     param_type __p_;
4236     result_type _V_;
4237     bool _V_hot_;
4238
4239 public:
4240     // constructors and reset functions
4241     _LIBCPP_INLINE_VISIBILITY
4242     explicit normal_distribution(result_type __mean = 0, result_type __stddev = 1)
4243         : __p_(param_type(__mean, __stddev)), _V_hot_(false) {}
4244     _LIBCPP_INLINE_VISIBILITY
4245     explicit normal_distribution(const param_type& __p)
4246         : __p_(__p), _V_hot_(false) {}
4247     _LIBCPP_INLINE_VISIBILITY
4248     void reset() {_V_hot_ = false;}
4249
4250     // generating functions
4251     template<class _URNG>
4252         _LIBCPP_INLINE_VISIBILITY
4253         result_type operator()(_URNG& __g)
4254         {return (*this)(__g, __p_);}
4255     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4256
4257     // property functions
4258     _LIBCPP_INLINE_VISIBILITY
4259     result_type mean() const {return __p_.mean();}
4260     _LIBCPP_INLINE_VISIBILITY
4261     result_type stddev() const {return __p_.stddev();}
4262
4263     _LIBCPP_INLINE_VISIBILITY
4264     param_type param() const {return __p_;}
4265     _LIBCPP_INLINE_VISIBILITY
4266     void param(const param_type& __p) {__p_ = __p;}
4267
4268     _LIBCPP_INLINE_VISIBILITY
4269     result_type min() const {return -numeric_limits<result_type>::infinity();}
4270     _LIBCPP_INLINE_VISIBILITY
4271     result_type max() const {return numeric_limits<result_type>::infinity();}
4272
4273     friend _LIBCPP_INLINE_VISIBILITY
4274         bool operator==(const normal_distribution& __x,
4275                         const normal_distribution& __y)
4276         {return __x.__p_ == __y.__p_ && __x._V_hot_ == __y._V_hot_ &&
4277                 (!__x._V_hot_ || __x._V_ == __y._V_);}
4278     friend _LIBCPP_INLINE_VISIBILITY
4279         bool operator!=(const normal_distribution& __x,
4280                         const normal_distribution& __y)
4281         {return !(__x == __y);}
4282
4283     template <class _CharT, class _Traits, class _RT>
4284     friend
4285     basic_ostream<_CharT, _Traits>&
4286     operator<<(basic_ostream<_CharT, _Traits>& __os,
4287                const normal_distribution<_RT>& __x);
4288
4289     template <class _CharT, class _Traits, class _RT>
4290     friend
4291     basic_istream<_CharT, _Traits>&
4292     operator>>(basic_istream<_CharT, _Traits>& __is,
4293                normal_distribution<_RT>& __x);
4294 };
4295
4296 template <class _RealType>
4297 template<class _URNG>
4298 _RealType
4299 normal_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4300 {
4301     result_type _Up;
4302     if (_V_hot_)
4303     {
4304         _V_hot_ = false;
4305         _Up = _V_;
4306     }
4307     else
4308     {
4309         uniform_real_distribution<result_type> _Uni(-1, 1);
4310         result_type __u;
4311         result_type __v;
4312         result_type __s;
4313         do
4314         {
4315             __u = _Uni(__g);
4316             __v = _Uni(__g);
4317             __s = __u * __u + __v * __v;
4318         } while (__s > 1 || __s == 0);
4319         result_type _Fp = _VSTD::sqrt(-2 * _VSTD::log(__s) / __s);
4320         _V_ = __v * _Fp;
4321         _V_hot_ = true;
4322         _Up = __u * _Fp;
4323     }
4324     return _Up * __p.stddev() + __p.mean();
4325 }
4326
4327 template <class _CharT, class _Traits, class _RT>
4328 basic_ostream<_CharT, _Traits>&
4329 operator<<(basic_ostream<_CharT, _Traits>& __os,
4330            const normal_distribution<_RT>& __x)
4331 {
4332     __save_flags<_CharT, _Traits> __lx(__os);
4333     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4334                ios_base::scientific);
4335     _CharT __sp = __os.widen(' ');
4336     __os.fill(__sp);
4337     __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_;
4338     if (__x._V_hot_)
4339         __os << __sp << __x._V_;
4340     return __os;
4341 }
4342
4343 template <class _CharT, class _Traits, class _RT>
4344 basic_istream<_CharT, _Traits>&
4345 operator>>(basic_istream<_CharT, _Traits>& __is,
4346            normal_distribution<_RT>& __x)
4347 {
4348     typedef normal_distribution<_RT> _Eng;
4349     typedef typename _Eng::result_type result_type;
4350     typedef typename _Eng::param_type param_type;
4351     __save_flags<_CharT, _Traits> __lx(__is);
4352     __is.flags(ios_base::dec | ios_base::skipws);
4353     result_type __mean;
4354     result_type __stddev;
4355     result_type _Vp = 0;
4356     bool _V_hot = false;
4357     __is >> __mean >> __stddev >> _V_hot;
4358     if (_V_hot)
4359         __is >> _Vp;
4360     if (!__is.fail())
4361     {
4362         __x.param(param_type(__mean, __stddev));
4363         __x._V_hot_ = _V_hot;
4364         __x._V_ = _Vp;
4365     }
4366     return __is;
4367 }
4368
4369 // lognormal_distribution
4370
4371 template<class _RealType = double>
4372 class _LIBCPP_TEMPLATE_VIS lognormal_distribution
4373 {
4374 public:
4375     // types
4376     typedef _RealType result_type;
4377
4378     class _LIBCPP_TEMPLATE_VIS param_type
4379     {
4380         normal_distribution<result_type> __nd_;
4381     public:
4382         typedef lognormal_distribution distribution_type;
4383
4384         _LIBCPP_INLINE_VISIBILITY
4385         explicit param_type(result_type __m = 0, result_type __s = 1)
4386             : __nd_(__m, __s) {}
4387
4388         _LIBCPP_INLINE_VISIBILITY
4389         result_type m() const {return __nd_.mean();}
4390         _LIBCPP_INLINE_VISIBILITY
4391         result_type s() const {return __nd_.stddev();}
4392
4393         friend _LIBCPP_INLINE_VISIBILITY
4394             bool operator==(const param_type& __x, const param_type& __y)
4395             {return __x.__nd_ == __y.__nd_;}
4396         friend _LIBCPP_INLINE_VISIBILITY
4397             bool operator!=(const param_type& __x, const param_type& __y)
4398             {return !(__x == __y);}
4399         friend class lognormal_distribution;
4400
4401         template <class _CharT, class _Traits, class _RT>
4402         friend
4403         basic_ostream<_CharT, _Traits>&
4404         operator<<(basic_ostream<_CharT, _Traits>& __os,
4405                    const lognormal_distribution<_RT>& __x);
4406
4407         template <class _CharT, class _Traits, class _RT>
4408         friend
4409         basic_istream<_CharT, _Traits>&
4410         operator>>(basic_istream<_CharT, _Traits>& __is,
4411                    lognormal_distribution<_RT>& __x);
4412     };
4413
4414 private:
4415     param_type __p_;
4416
4417 public:
4418     // constructor and reset functions
4419     _LIBCPP_INLINE_VISIBILITY
4420     explicit lognormal_distribution(result_type __m = 0, result_type __s = 1)
4421         : __p_(param_type(__m, __s)) {}
4422     _LIBCPP_INLINE_VISIBILITY
4423     explicit lognormal_distribution(const param_type& __p)
4424         : __p_(__p) {}
4425     _LIBCPP_INLINE_VISIBILITY
4426     void reset() {__p_.__nd_.reset();}
4427
4428     // generating functions
4429     template<class _URNG>
4430         _LIBCPP_INLINE_VISIBILITY
4431         result_type operator()(_URNG& __g)
4432         {return (*this)(__g, __p_);}
4433     template<class _URNG>
4434         _LIBCPP_INLINE_VISIBILITY
4435         result_type operator()(_URNG& __g, const param_type& __p)
4436         {return _VSTD::exp(const_cast<normal_distribution<result_type>&>(__p.__nd_)(__g));}
4437
4438     // property functions
4439     _LIBCPP_INLINE_VISIBILITY
4440     result_type m() const {return __p_.m();}
4441     _LIBCPP_INLINE_VISIBILITY
4442     result_type s() const {return __p_.s();}
4443
4444     _LIBCPP_INLINE_VISIBILITY
4445     param_type param() const {return __p_;}
4446     _LIBCPP_INLINE_VISIBILITY
4447     void param(const param_type& __p) {__p_ = __p;}
4448
4449     _LIBCPP_INLINE_VISIBILITY
4450     result_type min() const {return 0;}
4451     _LIBCPP_INLINE_VISIBILITY
4452     result_type max() const {return numeric_limits<result_type>::infinity();}
4453
4454     friend _LIBCPP_INLINE_VISIBILITY
4455         bool operator==(const lognormal_distribution& __x,
4456                         const lognormal_distribution& __y)
4457         {return __x.__p_ == __y.__p_;}
4458     friend _LIBCPP_INLINE_VISIBILITY
4459         bool operator!=(const lognormal_distribution& __x,
4460                         const lognormal_distribution& __y)
4461         {return !(__x == __y);}
4462
4463     template <class _CharT, class _Traits, class _RT>
4464     friend
4465     basic_ostream<_CharT, _Traits>&
4466     operator<<(basic_ostream<_CharT, _Traits>& __os,
4467                const lognormal_distribution<_RT>& __x);
4468
4469     template <class _CharT, class _Traits, class _RT>
4470     friend
4471     basic_istream<_CharT, _Traits>&
4472     operator>>(basic_istream<_CharT, _Traits>& __is,
4473                lognormal_distribution<_RT>& __x);
4474 };
4475
4476 template <class _CharT, class _Traits, class _RT>
4477 inline _LIBCPP_INLINE_VISIBILITY
4478 basic_ostream<_CharT, _Traits>&
4479 operator<<(basic_ostream<_CharT, _Traits>& __os,
4480            const lognormal_distribution<_RT>& __x)
4481 {
4482     return __os << __x.__p_.__nd_;
4483 }
4484
4485 template <class _CharT, class _Traits, class _RT>
4486 inline _LIBCPP_INLINE_VISIBILITY
4487 basic_istream<_CharT, _Traits>&
4488 operator>>(basic_istream<_CharT, _Traits>& __is,
4489            lognormal_distribution<_RT>& __x)
4490 {
4491     return __is >> __x.__p_.__nd_;
4492 }
4493
4494 // poisson_distribution
4495
4496 template<class _IntType = int>
4497 class _LIBCPP_TEMPLATE_VIS poisson_distribution
4498 {
4499 public:
4500     // types
4501     typedef _IntType result_type;
4502
4503     class _LIBCPP_TEMPLATE_VIS param_type
4504     {
4505         double __mean_;
4506         double __s_;
4507         double __d_;
4508         double __l_;
4509         double __omega_;
4510         double __c0_;
4511         double __c1_;
4512         double __c2_;
4513         double __c3_;
4514         double __c_;
4515
4516     public:
4517         typedef poisson_distribution distribution_type;
4518
4519         explicit param_type(double __mean = 1.0);
4520
4521         _LIBCPP_INLINE_VISIBILITY
4522         double mean() const {return __mean_;}
4523
4524         friend _LIBCPP_INLINE_VISIBILITY
4525             bool operator==(const param_type& __x, const param_type& __y)
4526             {return __x.__mean_ == __y.__mean_;}
4527         friend _LIBCPP_INLINE_VISIBILITY
4528             bool operator!=(const param_type& __x, const param_type& __y)
4529             {return !(__x == __y);}
4530
4531         friend class poisson_distribution;
4532     };
4533
4534 private:
4535     param_type __p_;
4536
4537 public:
4538     // constructors and reset functions
4539     _LIBCPP_INLINE_VISIBILITY
4540     explicit poisson_distribution(double __mean = 1.0) : __p_(__mean) {}
4541     _LIBCPP_INLINE_VISIBILITY
4542     explicit poisson_distribution(const param_type& __p) : __p_(__p) {}
4543     _LIBCPP_INLINE_VISIBILITY
4544     void reset() {}
4545
4546     // generating functions
4547     template<class _URNG>
4548         _LIBCPP_INLINE_VISIBILITY
4549         result_type operator()(_URNG& __g)
4550         {return (*this)(__g, __p_);}
4551     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4552
4553     // property functions
4554     _LIBCPP_INLINE_VISIBILITY
4555     double mean() const {return __p_.mean();}
4556
4557     _LIBCPP_INLINE_VISIBILITY
4558     param_type param() const {return __p_;}
4559     _LIBCPP_INLINE_VISIBILITY
4560     void param(const param_type& __p) {__p_ = __p;}
4561
4562     _LIBCPP_INLINE_VISIBILITY
4563     result_type min() const {return 0;}
4564     _LIBCPP_INLINE_VISIBILITY
4565     result_type max() const {return numeric_limits<result_type>::max();}
4566
4567     friend _LIBCPP_INLINE_VISIBILITY
4568         bool operator==(const poisson_distribution& __x,
4569                         const poisson_distribution& __y)
4570         {return __x.__p_ == __y.__p_;}
4571     friend _LIBCPP_INLINE_VISIBILITY
4572         bool operator!=(const poisson_distribution& __x,
4573                         const poisson_distribution& __y)
4574         {return !(__x == __y);}
4575 };
4576
4577 template<class _IntType>
4578 poisson_distribution<_IntType>::param_type::param_type(double __mean)
4579     : __mean_(__mean)
4580 {
4581     if (__mean_ < 10)
4582     {
4583         __s_ = 0;
4584         __d_ = 0;
4585         __l_ = _VSTD::exp(-__mean_);
4586         __omega_ = 0;
4587         __c3_ = 0;
4588         __c2_ = 0;
4589         __c1_ = 0;
4590         __c0_ = 0;
4591         __c_ = 0;
4592     }
4593     else
4594     {
4595         __s_ = _VSTD::sqrt(__mean_);
4596         __d_ = 6 * __mean_ * __mean_;
4597         __l_ = static_cast<result_type>(__mean_ - 1.1484);
4598         __omega_ = .3989423 / __s_;
4599         double __b1_ = .4166667E-1 / __mean_;
4600         double __b2_ = .3 * __b1_ * __b1_;
4601         __c3_ = .1428571 * __b1_ * __b2_;
4602         __c2_ = __b2_ - 15. * __c3_;
4603         __c1_ = __b1_ - 6. * __b2_ + 45. * __c3_;
4604         __c0_ = 1. - __b1_ + 3. * __b2_ - 15. * __c3_;
4605         __c_ = .1069 / __mean_;
4606     }
4607 }
4608
4609 template <class _IntType>
4610 template<class _URNG>
4611 _IntType
4612 poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4613 {
4614     result_type __x;
4615     uniform_real_distribution<double> __urd;
4616     if (__pr.__mean_ < 10)
4617     {
4618          __x = 0;
4619         for (double __p = __urd(__urng); __p > __pr.__l_; ++__x)
4620             __p *= __urd(__urng);
4621     }
4622     else
4623     {
4624         double __difmuk;
4625         double __g = __pr.__mean_ + __pr.__s_ * normal_distribution<double>()(__urng);
4626         double __u;
4627         if (__g > 0)
4628         {
4629             __x = static_cast<result_type>(__g);
4630             if (__x >= __pr.__l_)
4631                 return __x;
4632             __difmuk = __pr.__mean_ - __x;
4633             __u = __urd(__urng);
4634             if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk)
4635                 return __x;
4636         }
4637         exponential_distribution<double> __edist;
4638         for (bool __using_exp_dist = false; true; __using_exp_dist = true)
4639         {
4640             double __e;
4641             if (__using_exp_dist || __g < 0)
4642             {
4643                 double __t;
4644                 do
4645                 {
4646                     __e = __edist(__urng);
4647                     __u = __urd(__urng);
4648                     __u += __u - 1;
4649                     __t = 1.8 + (__u < 0 ? -__e : __e);
4650                 } while (__t <= -.6744);
4651                 __x = __pr.__mean_ + __pr.__s_ * __t;
4652                 __difmuk = __pr.__mean_ - __x;
4653                 __using_exp_dist = true;
4654             }
4655             double __px;
4656             double __py;
4657             if (__x < 10)
4658             {
4659                 const result_type __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040,
4660                                              40320, 362880};
4661                 __px = -__pr.__mean_;
4662                 __py = _VSTD::pow(__pr.__mean_, (double)__x) / __fac[__x];
4663             }
4664             else
4665             {
4666                 double __del = .8333333E-1 / __x;
4667                 __del -= 4.8 * __del * __del * __del;
4668                 double __v = __difmuk / __x;
4669                 if (_VSTD::abs(__v) > 0.25)
4670                     __px = __x * _VSTD::log(1 + __v) - __difmuk - __del;
4671                 else
4672                     __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) *
4673                            __v + .1421878) * __v + -.1661269) * __v + .2000118) *
4674                            __v + -.2500068) * __v + .3333333) * __v + -.5) - __del;
4675                 __py = .3989423 / _VSTD::sqrt(__x);
4676             }
4677             double __r = (0.5 - __difmuk) / __pr.__s_;
4678             double __r2 = __r * __r;
4679             double __fx = -0.5 * __r2;
4680             double __fy = __pr.__omega_ * (((__pr.__c3_ * __r2 + __pr.__c2_) *
4681                                         __r2 + __pr.__c1_) * __r2 + __pr.__c0_);
4682             if (__using_exp_dist)
4683             {
4684                 if (__pr.__c_ * _VSTD::abs(__u) <= __py * _VSTD::exp(__px + __e) -
4685                                                    __fy * _VSTD::exp(__fx + __e))
4686                     break;
4687             }
4688             else
4689             {
4690                 if (__fy - __u * __fy <= __py * _VSTD::exp(__px - __fx))
4691                     break;
4692             }
4693         }
4694     }
4695     return __x;
4696 }
4697
4698 template <class _CharT, class _Traits, class _IntType>
4699 basic_ostream<_CharT, _Traits>&
4700 operator<<(basic_ostream<_CharT, _Traits>& __os,
4701            const poisson_distribution<_IntType>& __x)
4702 {
4703     __save_flags<_CharT, _Traits> __lx(__os);
4704     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4705                ios_base::scientific);
4706     return __os << __x.mean();
4707 }
4708
4709 template <class _CharT, class _Traits, class _IntType>
4710 basic_istream<_CharT, _Traits>&
4711 operator>>(basic_istream<_CharT, _Traits>& __is,
4712            poisson_distribution<_IntType>& __x)
4713 {
4714     typedef poisson_distribution<_IntType> _Eng;
4715     typedef typename _Eng::param_type param_type;
4716     __save_flags<_CharT, _Traits> __lx(__is);
4717     __is.flags(ios_base::dec | ios_base::skipws);
4718     double __mean;
4719     __is >> __mean;
4720     if (!__is.fail())
4721         __x.param(param_type(__mean));
4722     return __is;
4723 }
4724
4725 // weibull_distribution
4726
4727 template<class _RealType = double>
4728 class _LIBCPP_TEMPLATE_VIS weibull_distribution
4729 {
4730 public:
4731     // types
4732     typedef _RealType result_type;
4733
4734     class _LIBCPP_TEMPLATE_VIS param_type
4735     {
4736         result_type __a_;
4737         result_type __b_;
4738     public:
4739         typedef weibull_distribution distribution_type;
4740
4741         _LIBCPP_INLINE_VISIBILITY
4742         explicit param_type(result_type __a = 1, result_type __b = 1)
4743             : __a_(__a), __b_(__b) {}
4744
4745         _LIBCPP_INLINE_VISIBILITY
4746         result_type a() const {return __a_;}
4747         _LIBCPP_INLINE_VISIBILITY
4748         result_type b() const {return __b_;}
4749
4750         friend _LIBCPP_INLINE_VISIBILITY
4751             bool operator==(const param_type& __x, const param_type& __y)
4752             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4753         friend _LIBCPP_INLINE_VISIBILITY
4754             bool operator!=(const param_type& __x, const param_type& __y)
4755             {return !(__x == __y);}
4756     };
4757
4758 private:
4759     param_type __p_;
4760
4761 public:
4762     // constructor and reset functions
4763     _LIBCPP_INLINE_VISIBILITY
4764     explicit weibull_distribution(result_type __a = 1, result_type __b = 1)
4765         : __p_(param_type(__a, __b)) {}
4766     _LIBCPP_INLINE_VISIBILITY
4767     explicit weibull_distribution(const param_type& __p)
4768         : __p_(__p) {}
4769     _LIBCPP_INLINE_VISIBILITY
4770     void reset() {}
4771
4772     // generating functions
4773     template<class _URNG>
4774         _LIBCPP_INLINE_VISIBILITY
4775         result_type operator()(_URNG& __g)
4776         {return (*this)(__g, __p_);}
4777     template<class _URNG>
4778         _LIBCPP_INLINE_VISIBILITY
4779         result_type operator()(_URNG& __g, const param_type& __p)
4780         {return __p.b() *
4781             _VSTD::pow(exponential_distribution<result_type>()(__g), 1/__p.a());}
4782
4783     // property functions
4784     _LIBCPP_INLINE_VISIBILITY
4785     result_type a() const {return __p_.a();}
4786     _LIBCPP_INLINE_VISIBILITY
4787     result_type b() const {return __p_.b();}
4788
4789     _LIBCPP_INLINE_VISIBILITY
4790     param_type param() const {return __p_;}
4791     _LIBCPP_INLINE_VISIBILITY
4792     void param(const param_type& __p) {__p_ = __p;}
4793
4794     _LIBCPP_INLINE_VISIBILITY
4795     result_type min() const {return 0;}
4796     _LIBCPP_INLINE_VISIBILITY
4797     result_type max() const {return numeric_limits<result_type>::infinity();}
4798
4799     friend _LIBCPP_INLINE_VISIBILITY
4800         bool operator==(const weibull_distribution& __x,
4801                         const weibull_distribution& __y)
4802         {return __x.__p_ == __y.__p_;}
4803     friend _LIBCPP_INLINE_VISIBILITY
4804         bool operator!=(const weibull_distribution& __x,
4805                         const weibull_distribution& __y)
4806         {return !(__x == __y);}
4807 };
4808
4809 template <class _CharT, class _Traits, class _RT>
4810 basic_ostream<_CharT, _Traits>&
4811 operator<<(basic_ostream<_CharT, _Traits>& __os,
4812            const weibull_distribution<_RT>& __x)
4813 {
4814     __save_flags<_CharT, _Traits> __lx(__os);
4815     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4816                ios_base::scientific);
4817     _CharT __sp = __os.widen(' ');
4818     __os.fill(__sp);
4819     __os << __x.a() << __sp << __x.b();
4820     return __os;
4821 }
4822
4823 template <class _CharT, class _Traits, class _RT>
4824 basic_istream<_CharT, _Traits>&
4825 operator>>(basic_istream<_CharT, _Traits>& __is,
4826            weibull_distribution<_RT>& __x)
4827 {
4828     typedef weibull_distribution<_RT> _Eng;
4829     typedef typename _Eng::result_type result_type;
4830     typedef typename _Eng::param_type param_type;
4831     __save_flags<_CharT, _Traits> __lx(__is);
4832     __is.flags(ios_base::dec | ios_base::skipws);
4833     result_type __a;
4834     result_type __b;
4835     __is >> __a >> __b;
4836     if (!__is.fail())
4837         __x.param(param_type(__a, __b));
4838     return __is;
4839 }
4840
4841 template<class _RealType = double>
4842 class _LIBCPP_TEMPLATE_VIS extreme_value_distribution
4843 {
4844 public:
4845     // types
4846     typedef _RealType result_type;
4847
4848     class _LIBCPP_TEMPLATE_VIS param_type
4849     {
4850         result_type __a_;
4851         result_type __b_;
4852     public:
4853         typedef extreme_value_distribution distribution_type;
4854
4855         _LIBCPP_INLINE_VISIBILITY
4856         explicit param_type(result_type __a = 0, result_type __b = 1)
4857             : __a_(__a), __b_(__b) {}
4858
4859         _LIBCPP_INLINE_VISIBILITY
4860         result_type a() const {return __a_;}
4861         _LIBCPP_INLINE_VISIBILITY
4862         result_type b() const {return __b_;}
4863
4864         friend _LIBCPP_INLINE_VISIBILITY
4865             bool operator==(const param_type& __x, const param_type& __y)
4866             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4867         friend _LIBCPP_INLINE_VISIBILITY
4868             bool operator!=(const param_type& __x, const param_type& __y)
4869             {return !(__x == __y);}
4870     };
4871
4872 private:
4873     param_type __p_;
4874
4875 public:
4876     // constructor and reset functions
4877     _LIBCPP_INLINE_VISIBILITY
4878     explicit extreme_value_distribution(result_type __a = 0, result_type __b = 1)
4879         : __p_(param_type(__a, __b)) {}
4880     _LIBCPP_INLINE_VISIBILITY
4881     explicit extreme_value_distribution(const param_type& __p)
4882         : __p_(__p) {}
4883     _LIBCPP_INLINE_VISIBILITY
4884     void reset() {}
4885
4886     // generating functions
4887     template<class _URNG>
4888         _LIBCPP_INLINE_VISIBILITY
4889         result_type operator()(_URNG& __g)
4890         {return (*this)(__g, __p_);}
4891     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4892
4893     // property functions
4894     _LIBCPP_INLINE_VISIBILITY
4895     result_type a() const {return __p_.a();}
4896     _LIBCPP_INLINE_VISIBILITY
4897     result_type b() const {return __p_.b();}
4898
4899     _LIBCPP_INLINE_VISIBILITY
4900     param_type param() const {return __p_;}
4901     _LIBCPP_INLINE_VISIBILITY
4902     void param(const param_type& __p) {__p_ = __p;}
4903
4904     _LIBCPP_INLINE_VISIBILITY
4905     result_type min() const {return -numeric_limits<result_type>::infinity();}
4906     _LIBCPP_INLINE_VISIBILITY
4907     result_type max() const {return numeric_limits<result_type>::infinity();}
4908
4909     friend _LIBCPP_INLINE_VISIBILITY
4910         bool operator==(const extreme_value_distribution& __x,
4911                         const extreme_value_distribution& __y)
4912         {return __x.__p_ == __y.__p_;}
4913     friend _LIBCPP_INLINE_VISIBILITY
4914         bool operator!=(const extreme_value_distribution& __x,
4915                         const extreme_value_distribution& __y)
4916         {return !(__x == __y);}
4917 };
4918
4919 template<class _RealType>
4920 template<class _URNG>
4921 _RealType
4922 extreme_value_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4923 {
4924     return __p.a() - __p.b() *
4925          _VSTD::log(-_VSTD::log(1-uniform_real_distribution<result_type>()(__g)));
4926 }
4927
4928 template <class _CharT, class _Traits, class _RT>
4929 basic_ostream<_CharT, _Traits>&
4930 operator<<(basic_ostream<_CharT, _Traits>& __os,
4931            const extreme_value_distribution<_RT>& __x)
4932 {
4933     __save_flags<_CharT, _Traits> __lx(__os);
4934     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4935                ios_base::scientific);
4936     _CharT __sp = __os.widen(' ');
4937     __os.fill(__sp);
4938     __os << __x.a() << __sp << __x.b();
4939     return __os;
4940 }
4941
4942 template <class _CharT, class _Traits, class _RT>
4943 basic_istream<_CharT, _Traits>&
4944 operator>>(basic_istream<_CharT, _Traits>& __is,
4945            extreme_value_distribution<_RT>& __x)
4946 {
4947     typedef extreme_value_distribution<_RT> _Eng;
4948     typedef typename _Eng::result_type result_type;
4949     typedef typename _Eng::param_type param_type;
4950     __save_flags<_CharT, _Traits> __lx(__is);
4951     __is.flags(ios_base::dec | ios_base::skipws);
4952     result_type __a;
4953     result_type __b;
4954     __is >> __a >> __b;
4955     if (!__is.fail())
4956         __x.param(param_type(__a, __b));
4957     return __is;
4958 }
4959
4960 // gamma_distribution
4961
4962 template<class _RealType = double>
4963 class _LIBCPP_TEMPLATE_VIS gamma_distribution
4964 {
4965 public:
4966     // types
4967     typedef _RealType result_type;
4968
4969     class _LIBCPP_TEMPLATE_VIS param_type
4970     {
4971         result_type __alpha_;
4972         result_type __beta_;
4973     public:
4974         typedef gamma_distribution distribution_type;
4975
4976         _LIBCPP_INLINE_VISIBILITY
4977         explicit param_type(result_type __alpha = 1, result_type __beta = 1)
4978             : __alpha_(__alpha), __beta_(__beta) {}
4979
4980         _LIBCPP_INLINE_VISIBILITY
4981         result_type alpha() const {return __alpha_;}
4982         _LIBCPP_INLINE_VISIBILITY
4983         result_type beta() const {return __beta_;}
4984
4985         friend _LIBCPP_INLINE_VISIBILITY
4986             bool operator==(const param_type& __x, const param_type& __y)
4987             {return __x.__alpha_ == __y.__alpha_ && __x.__beta_ == __y.__beta_;}
4988         friend _LIBCPP_INLINE_VISIBILITY
4989             bool operator!=(const param_type& __x, const param_type& __y)
4990             {return !(__x == __y);}
4991     };
4992
4993 private:
4994     param_type __p_;
4995
4996 public:
4997     // constructors and reset functions
4998     _LIBCPP_INLINE_VISIBILITY
4999     explicit gamma_distribution(result_type __alpha = 1, result_type __beta = 1)
5000         : __p_(param_type(__alpha, __beta)) {}
5001     _LIBCPP_INLINE_VISIBILITY
5002     explicit gamma_distribution(const param_type& __p)
5003         : __p_(__p) {}
5004     _LIBCPP_INLINE_VISIBILITY
5005     void reset() {}
5006
5007     // generating functions
5008     template<class _URNG>
5009         _LIBCPP_INLINE_VISIBILITY
5010         result_type operator()(_URNG& __g)
5011         {return (*this)(__g, __p_);}
5012     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5013
5014     // property functions
5015     _LIBCPP_INLINE_VISIBILITY
5016     result_type alpha() const {return __p_.alpha();}
5017     _LIBCPP_INLINE_VISIBILITY
5018     result_type beta() const {return __p_.beta();}
5019
5020     _LIBCPP_INLINE_VISIBILITY
5021     param_type param() const {return __p_;}
5022     _LIBCPP_INLINE_VISIBILITY
5023     void param(const param_type& __p) {__p_ = __p;}
5024
5025     _LIBCPP_INLINE_VISIBILITY
5026     result_type min() const {return 0;}
5027     _LIBCPP_INLINE_VISIBILITY
5028     result_type max() const {return numeric_limits<result_type>::infinity();}
5029
5030     friend _LIBCPP_INLINE_VISIBILITY
5031         bool operator==(const gamma_distribution& __x,
5032                         const gamma_distribution& __y)
5033         {return __x.__p_ == __y.__p_;}
5034     friend _LIBCPP_INLINE_VISIBILITY
5035         bool operator!=(const gamma_distribution& __x,
5036                         const gamma_distribution& __y)
5037         {return !(__x == __y);}
5038 };
5039
5040 template <class _RealType>
5041 template<class _URNG>
5042 _RealType
5043 gamma_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5044 {
5045     result_type __a = __p.alpha();
5046     uniform_real_distribution<result_type> __gen(0, 1);
5047     exponential_distribution<result_type> __egen;
5048     result_type __x;
5049     if (__a == 1)
5050         __x = __egen(__g);
5051     else if (__a > 1)
5052     {
5053         const result_type __b = __a - 1;
5054         const result_type __c = 3 * __a - result_type(0.75);
5055         while (true)
5056         {
5057             const result_type __u = __gen(__g);
5058             const result_type __v = __gen(__g);
5059             const result_type __w = __u * (1 - __u);
5060             if (__w != 0)
5061             {
5062                 const result_type __y = _VSTD::sqrt(__c / __w) *
5063                                         (__u - result_type(0.5));
5064                 __x = __b + __y;
5065                 if (__x >= 0)
5066                 {
5067                     const result_type __z = 64 * __w * __w * __w * __v * __v;
5068                     if (__z <= 1 - 2 * __y * __y / __x)
5069                         break;
5070                     if (_VSTD::log(__z) <= 2 * (__b * _VSTD::log(__x / __b) - __y))
5071                         break;
5072                 }
5073             }
5074         }
5075     }
5076     else  // __a < 1
5077     {
5078         while (true)
5079         {
5080             const result_type __u = __gen(__g);
5081             const result_type __es = __egen(__g);
5082             if (__u <= 1 - __a)
5083             {
5084                 __x = _VSTD::pow(__u, 1 / __a);
5085                 if (__x <= __es)
5086                     break;
5087             }
5088             else
5089             {
5090                 const result_type __e = -_VSTD::log((1-__u)/__a);
5091                 __x = _VSTD::pow(1 - __a + __a * __e, 1 / __a);
5092                 if (__x <= __e + __es)
5093                     break;
5094             }
5095         }
5096     }
5097     return __x * __p.beta();
5098 }
5099
5100 template <class _CharT, class _Traits, class _RT>
5101 basic_ostream<_CharT, _Traits>&
5102 operator<<(basic_ostream<_CharT, _Traits>& __os,
5103            const gamma_distribution<_RT>& __x)
5104 {
5105     __save_flags<_CharT, _Traits> __lx(__os);
5106     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5107                ios_base::scientific);
5108     _CharT __sp = __os.widen(' ');
5109     __os.fill(__sp);
5110     __os << __x.alpha() << __sp << __x.beta();
5111     return __os;
5112 }
5113
5114 template <class _CharT, class _Traits, class _RT>
5115 basic_istream<_CharT, _Traits>&
5116 operator>>(basic_istream<_CharT, _Traits>& __is,
5117            gamma_distribution<_RT>& __x)
5118 {
5119     typedef gamma_distribution<_RT> _Eng;
5120     typedef typename _Eng::result_type result_type;
5121     typedef typename _Eng::param_type param_type;
5122     __save_flags<_CharT, _Traits> __lx(__is);
5123     __is.flags(ios_base::dec | ios_base::skipws);
5124     result_type __alpha;
5125     result_type __beta;
5126     __is >> __alpha >> __beta;
5127     if (!__is.fail())
5128         __x.param(param_type(__alpha, __beta));
5129     return __is;
5130 }
5131
5132 // negative_binomial_distribution
5133
5134 template<class _IntType = int>
5135 class _LIBCPP_TEMPLATE_VIS negative_binomial_distribution
5136 {
5137 public:
5138     // types
5139     typedef _IntType result_type;
5140
5141     class _LIBCPP_TEMPLATE_VIS param_type
5142     {
5143         result_type __k_;
5144         double __p_;
5145     public:
5146         typedef negative_binomial_distribution distribution_type;
5147
5148         _LIBCPP_INLINE_VISIBILITY
5149         explicit param_type(result_type __k = 1, double __p = 0.5)
5150             : __k_(__k), __p_(__p) {}
5151
5152         _LIBCPP_INLINE_VISIBILITY
5153         result_type k() const {return __k_;}
5154         _LIBCPP_INLINE_VISIBILITY
5155         double p() const {return __p_;}
5156
5157         friend _LIBCPP_INLINE_VISIBILITY
5158             bool operator==(const param_type& __x, const param_type& __y)
5159             {return __x.__k_ == __y.__k_ && __x.__p_ == __y.__p_;}
5160         friend _LIBCPP_INLINE_VISIBILITY
5161             bool operator!=(const param_type& __x, const param_type& __y)
5162             {return !(__x == __y);}
5163     };
5164
5165 private:
5166     param_type __p_;
5167
5168 public:
5169     // constructor and reset functions
5170     _LIBCPP_INLINE_VISIBILITY
5171     explicit negative_binomial_distribution(result_type __k = 1, double __p = 0.5)
5172         : __p_(__k, __p) {}
5173     _LIBCPP_INLINE_VISIBILITY
5174     explicit negative_binomial_distribution(const param_type& __p) : __p_(__p) {}
5175     _LIBCPP_INLINE_VISIBILITY
5176     void reset() {}
5177
5178     // generating functions
5179     template<class _URNG>
5180         _LIBCPP_INLINE_VISIBILITY
5181         result_type operator()(_URNG& __g)
5182         {return (*this)(__g, __p_);}
5183     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5184
5185     // property functions
5186     _LIBCPP_INLINE_VISIBILITY
5187     result_type k() const {return __p_.k();}
5188     _LIBCPP_INLINE_VISIBILITY
5189     double p() const {return __p_.p();}
5190
5191     _LIBCPP_INLINE_VISIBILITY
5192     param_type param() const {return __p_;}
5193     _LIBCPP_INLINE_VISIBILITY
5194     void param(const param_type& __p) {__p_ = __p;}
5195
5196     _LIBCPP_INLINE_VISIBILITY
5197     result_type min() const {return 0;}
5198     _LIBCPP_INLINE_VISIBILITY
5199     result_type max() const {return numeric_limits<result_type>::max();}
5200
5201     friend _LIBCPP_INLINE_VISIBILITY
5202         bool operator==(const negative_binomial_distribution& __x,
5203                         const negative_binomial_distribution& __y)
5204         {return __x.__p_ == __y.__p_;}
5205     friend _LIBCPP_INLINE_VISIBILITY
5206         bool operator!=(const negative_binomial_distribution& __x,
5207                         const negative_binomial_distribution& __y)
5208         {return !(__x == __y);}
5209 };
5210
5211 template <class _IntType>
5212 template<class _URNG>
5213 _IntType
5214 negative_binomial_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
5215 {
5216     result_type __k = __pr.k();
5217     double __p = __pr.p();
5218     if (__k <= 21 * __p)
5219     {
5220         bernoulli_distribution __gen(__p);
5221         result_type __f = 0;
5222         result_type __s = 0;
5223         while (__s < __k)
5224         {
5225             if (__gen(__urng))
5226                 ++__s;
5227             else
5228                 ++__f;
5229         }
5230         return __f;
5231     }
5232     return poisson_distribution<result_type>(gamma_distribution<double>
5233                                             (__k, (1-__p)/__p)(__urng))(__urng);
5234 }
5235
5236 template <class _CharT, class _Traits, class _IntType>
5237 basic_ostream<_CharT, _Traits>&
5238 operator<<(basic_ostream<_CharT, _Traits>& __os,
5239            const negative_binomial_distribution<_IntType>& __x)
5240 {
5241     __save_flags<_CharT, _Traits> __lx(__os);
5242     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5243                ios_base::scientific);
5244     _CharT __sp = __os.widen(' ');
5245     __os.fill(__sp);
5246     return __os << __x.k() << __sp << __x.p();
5247 }
5248
5249 template <class _CharT, class _Traits, class _IntType>
5250 basic_istream<_CharT, _Traits>&
5251 operator>>(basic_istream<_CharT, _Traits>& __is,
5252            negative_binomial_distribution<_IntType>& __x)
5253 {
5254     typedef negative_binomial_distribution<_IntType> _Eng;
5255     typedef typename _Eng::result_type result_type;
5256     typedef typename _Eng::param_type param_type;
5257     __save_flags<_CharT, _Traits> __lx(__is);
5258     __is.flags(ios_base::dec | ios_base::skipws);
5259     result_type __k;
5260     double __p;
5261     __is >> __k >> __p;
5262     if (!__is.fail())
5263         __x.param(param_type(__k, __p));
5264     return __is;
5265 }
5266
5267 // geometric_distribution
5268
5269 template<class _IntType = int>
5270 class _LIBCPP_TEMPLATE_VIS geometric_distribution
5271 {
5272 public:
5273     // types
5274     typedef _IntType result_type;
5275
5276     class _LIBCPP_TEMPLATE_VIS param_type
5277     {
5278         double __p_;
5279     public:
5280         typedef geometric_distribution distribution_type;
5281
5282         _LIBCPP_INLINE_VISIBILITY
5283         explicit param_type(double __p = 0.5) : __p_(__p) {}
5284
5285         _LIBCPP_INLINE_VISIBILITY
5286         double p() const {return __p_;}
5287
5288         friend _LIBCPP_INLINE_VISIBILITY
5289             bool operator==(const param_type& __x, const param_type& __y)
5290             {return __x.__p_ == __y.__p_;}
5291         friend _LIBCPP_INLINE_VISIBILITY
5292             bool operator!=(const param_type& __x, const param_type& __y)
5293             {return !(__x == __y);}
5294     };
5295
5296 private:
5297     param_type __p_;
5298
5299 public:
5300     // constructors and reset functions
5301     _LIBCPP_INLINE_VISIBILITY
5302     explicit geometric_distribution(double __p = 0.5) : __p_(__p) {}
5303     _LIBCPP_INLINE_VISIBILITY
5304     explicit geometric_distribution(const param_type& __p) : __p_(__p) {}
5305     _LIBCPP_INLINE_VISIBILITY
5306     void reset() {}
5307
5308     // generating functions
5309     template<class _URNG>
5310         _LIBCPP_INLINE_VISIBILITY
5311         result_type operator()(_URNG& __g)
5312         {return (*this)(__g, __p_);}
5313     template<class _URNG>
5314         _LIBCPP_INLINE_VISIBILITY
5315         result_type operator()(_URNG& __g, const param_type& __p)
5316         {return negative_binomial_distribution<result_type>(1, __p.p())(__g);}
5317
5318     // property functions
5319     _LIBCPP_INLINE_VISIBILITY
5320     double p() const {return __p_.p();}
5321
5322     _LIBCPP_INLINE_VISIBILITY
5323     param_type param() const {return __p_;}
5324     _LIBCPP_INLINE_VISIBILITY
5325     void param(const param_type& __p) {__p_ = __p;}
5326
5327     _LIBCPP_INLINE_VISIBILITY
5328     result_type min() const {return 0;}
5329     _LIBCPP_INLINE_VISIBILITY
5330     result_type max() const {return numeric_limits<result_type>::max();}
5331
5332     friend _LIBCPP_INLINE_VISIBILITY
5333         bool operator==(const geometric_distribution& __x,
5334                         const geometric_distribution& __y)
5335         {return __x.__p_ == __y.__p_;}
5336     friend _LIBCPP_INLINE_VISIBILITY
5337         bool operator!=(const geometric_distribution& __x,
5338                         const geometric_distribution& __y)
5339         {return !(__x == __y);}
5340 };
5341
5342 template <class _CharT, class _Traits, class _IntType>
5343 basic_ostream<_CharT, _Traits>&
5344 operator<<(basic_ostream<_CharT, _Traits>& __os,
5345            const geometric_distribution<_IntType>& __x)
5346 {
5347     __save_flags<_CharT, _Traits> __lx(__os);
5348     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5349                ios_base::scientific);
5350     return __os << __x.p();
5351 }
5352
5353 template <class _CharT, class _Traits, class _IntType>
5354 basic_istream<_CharT, _Traits>&
5355 operator>>(basic_istream<_CharT, _Traits>& __is,
5356            geometric_distribution<_IntType>& __x)
5357 {
5358     typedef geometric_distribution<_IntType> _Eng;
5359     typedef typename _Eng::param_type param_type;
5360     __save_flags<_CharT, _Traits> __lx(__is);
5361     __is.flags(ios_base::dec | ios_base::skipws);
5362     double __p;
5363     __is >> __p;
5364     if (!__is.fail())
5365         __x.param(param_type(__p));
5366     return __is;
5367 }
5368
5369 // chi_squared_distribution
5370
5371 template<class _RealType = double>
5372 class _LIBCPP_TEMPLATE_VIS chi_squared_distribution
5373 {
5374 public:
5375     // types
5376     typedef _RealType result_type;
5377
5378     class _LIBCPP_TEMPLATE_VIS param_type
5379     {
5380         result_type __n_;
5381     public:
5382         typedef chi_squared_distribution distribution_type;
5383
5384         _LIBCPP_INLINE_VISIBILITY
5385         explicit param_type(result_type __n = 1) : __n_(__n) {}
5386
5387         _LIBCPP_INLINE_VISIBILITY
5388         result_type n() const {return __n_;}
5389
5390         friend _LIBCPP_INLINE_VISIBILITY
5391             bool operator==(const param_type& __x, const param_type& __y)
5392             {return __x.__n_ == __y.__n_;}
5393         friend _LIBCPP_INLINE_VISIBILITY
5394             bool operator!=(const param_type& __x, const param_type& __y)
5395             {return !(__x == __y);}
5396     };
5397
5398 private:
5399     param_type __p_;
5400
5401 public:
5402     // constructor and reset functions
5403     _LIBCPP_INLINE_VISIBILITY
5404     explicit chi_squared_distribution(result_type __n = 1)
5405         : __p_(param_type(__n)) {}
5406     _LIBCPP_INLINE_VISIBILITY
5407     explicit chi_squared_distribution(const param_type& __p)
5408         : __p_(__p) {}
5409     _LIBCPP_INLINE_VISIBILITY
5410     void reset() {}
5411
5412     // generating functions
5413     template<class _URNG>
5414         _LIBCPP_INLINE_VISIBILITY
5415         result_type operator()(_URNG& __g)
5416         {return (*this)(__g, __p_);}
5417     template<class _URNG>
5418         _LIBCPP_INLINE_VISIBILITY
5419         result_type operator()(_URNG& __g, const param_type& __p)
5420         {return gamma_distribution<result_type>(__p.n() / 2, 2)(__g);}
5421
5422     // property functions
5423     _LIBCPP_INLINE_VISIBILITY
5424     result_type n() const {return __p_.n();}
5425
5426     _LIBCPP_INLINE_VISIBILITY
5427     param_type param() const {return __p_;}
5428     _LIBCPP_INLINE_VISIBILITY
5429     void param(const param_type& __p) {__p_ = __p;}
5430
5431     _LIBCPP_INLINE_VISIBILITY
5432     result_type min() const {return 0;}
5433     _LIBCPP_INLINE_VISIBILITY
5434     result_type max() const {return numeric_limits<result_type>::infinity();}
5435
5436     friend _LIBCPP_INLINE_VISIBILITY
5437         bool operator==(const chi_squared_distribution& __x,
5438                         const chi_squared_distribution& __y)
5439         {return __x.__p_ == __y.__p_;}
5440     friend _LIBCPP_INLINE_VISIBILITY
5441         bool operator!=(const chi_squared_distribution& __x,
5442                         const chi_squared_distribution& __y)
5443         {return !(__x == __y);}
5444 };
5445
5446 template <class _CharT, class _Traits, class _RT>
5447 basic_ostream<_CharT, _Traits>&
5448 operator<<(basic_ostream<_CharT, _Traits>& __os,
5449            const chi_squared_distribution<_RT>& __x)
5450 {
5451     __save_flags<_CharT, _Traits> __lx(__os);
5452     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5453                ios_base::scientific);
5454     __os << __x.n();
5455     return __os;
5456 }
5457
5458 template <class _CharT, class _Traits, class _RT>
5459 basic_istream<_CharT, _Traits>&
5460 operator>>(basic_istream<_CharT, _Traits>& __is,
5461            chi_squared_distribution<_RT>& __x)
5462 {
5463     typedef chi_squared_distribution<_RT> _Eng;
5464     typedef typename _Eng::result_type result_type;
5465     typedef typename _Eng::param_type param_type;
5466     __save_flags<_CharT, _Traits> __lx(__is);
5467     __is.flags(ios_base::dec | ios_base::skipws);
5468     result_type __n;
5469     __is >> __n;
5470     if (!__is.fail())
5471         __x.param(param_type(__n));
5472     return __is;
5473 }
5474
5475 // cauchy_distribution
5476
5477 template<class _RealType = double>
5478 class _LIBCPP_TEMPLATE_VIS cauchy_distribution
5479 {
5480 public:
5481     // types
5482     typedef _RealType result_type;
5483
5484     class _LIBCPP_TEMPLATE_VIS param_type
5485     {
5486         result_type __a_;
5487         result_type __b_;
5488     public:
5489         typedef cauchy_distribution distribution_type;
5490
5491         _LIBCPP_INLINE_VISIBILITY
5492         explicit param_type(result_type __a = 0, result_type __b = 1)
5493             : __a_(__a), __b_(__b) {}
5494
5495         _LIBCPP_INLINE_VISIBILITY
5496         result_type a() const {return __a_;}
5497         _LIBCPP_INLINE_VISIBILITY
5498         result_type b() const {return __b_;}
5499
5500         friend _LIBCPP_INLINE_VISIBILITY
5501             bool operator==(const param_type& __x, const param_type& __y)
5502             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
5503         friend _LIBCPP_INLINE_VISIBILITY
5504             bool operator!=(const param_type& __x, const param_type& __y)
5505             {return !(__x == __y);}
5506     };
5507
5508 private:
5509     param_type __p_;
5510
5511 public:
5512     // constructor and reset functions
5513     _LIBCPP_INLINE_VISIBILITY
5514     explicit cauchy_distribution(result_type __a = 0, result_type __b = 1)
5515         : __p_(param_type(__a, __b)) {}
5516     _LIBCPP_INLINE_VISIBILITY
5517     explicit cauchy_distribution(const param_type& __p)
5518         : __p_(__p) {}
5519     _LIBCPP_INLINE_VISIBILITY
5520     void reset() {}
5521
5522     // generating functions
5523     template<class _URNG>
5524         _LIBCPP_INLINE_VISIBILITY
5525         result_type operator()(_URNG& __g)
5526         {return (*this)(__g, __p_);}
5527     template<class _URNG> _LIBCPP_INLINE_VISIBILITY result_type operator()(_URNG& __g, const param_type& __p);
5528
5529     // property functions
5530     _LIBCPP_INLINE_VISIBILITY
5531     result_type a() const {return __p_.a();}
5532     _LIBCPP_INLINE_VISIBILITY
5533     result_type b() const {return __p_.b();}
5534
5535     _LIBCPP_INLINE_VISIBILITY
5536     param_type param() const {return __p_;}
5537     _LIBCPP_INLINE_VISIBILITY
5538     void param(const param_type& __p) {__p_ = __p;}
5539
5540     _LIBCPP_INLINE_VISIBILITY
5541     result_type min() const {return -numeric_limits<result_type>::infinity();}
5542     _LIBCPP_INLINE_VISIBILITY
5543     result_type max() const {return numeric_limits<result_type>::infinity();}
5544
5545     friend _LIBCPP_INLINE_VISIBILITY
5546         bool operator==(const cauchy_distribution& __x,
5547                         const cauchy_distribution& __y)
5548         {return __x.__p_ == __y.__p_;}
5549     friend _LIBCPP_INLINE_VISIBILITY
5550         bool operator!=(const cauchy_distribution& __x,
5551                         const cauchy_distribution& __y)
5552         {return !(__x == __y);}
5553 };
5554
5555 template <class _RealType>
5556 template<class _URNG>
5557 inline
5558 _RealType
5559 cauchy_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5560 {
5561     uniform_real_distribution<result_type> __gen;
5562     // purposefully let tan arg get as close to pi/2 as it wants, tan will return a finite
5563     return __p.a() + __p.b() * _VSTD::tan(3.1415926535897932384626433832795 * __gen(__g));
5564 }
5565
5566 template <class _CharT, class _Traits, class _RT>
5567 basic_ostream<_CharT, _Traits>&
5568 operator<<(basic_ostream<_CharT, _Traits>& __os,
5569            const cauchy_distribution<_RT>& __x)
5570 {
5571     __save_flags<_CharT, _Traits> __lx(__os);
5572     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5573                ios_base::scientific);
5574     _CharT __sp = __os.widen(' ');
5575     __os.fill(__sp);
5576     __os << __x.a() << __sp << __x.b();
5577     return __os;
5578 }
5579
5580 template <class _CharT, class _Traits, class _RT>
5581 basic_istream<_CharT, _Traits>&
5582 operator>>(basic_istream<_CharT, _Traits>& __is,
5583            cauchy_distribution<_RT>& __x)
5584 {
5585     typedef cauchy_distribution<_RT> _Eng;
5586     typedef typename _Eng::result_type result_type;
5587     typedef typename _Eng::param_type param_type;
5588     __save_flags<_CharT, _Traits> __lx(__is);
5589     __is.flags(ios_base::dec | ios_base::skipws);
5590     result_type __a;
5591     result_type __b;
5592     __is >> __a >> __b;
5593     if (!__is.fail())
5594         __x.param(param_type(__a, __b));
5595     return __is;
5596 }
5597
5598 // fisher_f_distribution
5599
5600 template<class _RealType = double>
5601 class _LIBCPP_TEMPLATE_VIS fisher_f_distribution
5602 {
5603 public:
5604     // types
5605     typedef _RealType result_type;
5606
5607     class _LIBCPP_TEMPLATE_VIS param_type
5608     {
5609         result_type __m_;
5610         result_type __n_;
5611     public:
5612         typedef fisher_f_distribution distribution_type;
5613
5614         _LIBCPP_INLINE_VISIBILITY
5615         explicit param_type(result_type __m = 1, result_type __n = 1)
5616             : __m_(__m), __n_(__n) {}
5617
5618         _LIBCPP_INLINE_VISIBILITY
5619         result_type m() const {return __m_;}
5620         _LIBCPP_INLINE_VISIBILITY
5621         result_type n() const {return __n_;}
5622
5623         friend _LIBCPP_INLINE_VISIBILITY
5624             bool operator==(const param_type& __x, const param_type& __y)
5625             {return __x.__m_ == __y.__m_ && __x.__n_ == __y.__n_;}
5626         friend _LIBCPP_INLINE_VISIBILITY
5627             bool operator!=(const param_type& __x, const param_type& __y)
5628             {return !(__x == __y);}
5629     };
5630
5631 private:
5632     param_type __p_;
5633
5634 public:
5635     // constructor and reset functions
5636     _LIBCPP_INLINE_VISIBILITY
5637     explicit fisher_f_distribution(result_type __m = 1, result_type __n = 1)
5638         : __p_(param_type(__m, __n)) {}
5639     _LIBCPP_INLINE_VISIBILITY
5640     explicit fisher_f_distribution(const param_type& __p)
5641         : __p_(__p) {}
5642     _LIBCPP_INLINE_VISIBILITY
5643     void reset() {}
5644
5645     // generating functions
5646     template<class _URNG>
5647         _LIBCPP_INLINE_VISIBILITY
5648         result_type operator()(_URNG& __g)
5649         {return (*this)(__g, __p_);}
5650     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5651
5652     // property functions
5653     _LIBCPP_INLINE_VISIBILITY
5654     result_type m() const {return __p_.m();}
5655     _LIBCPP_INLINE_VISIBILITY
5656     result_type n() const {return __p_.n();}
5657
5658     _LIBCPP_INLINE_VISIBILITY
5659     param_type param() const {return __p_;}
5660     _LIBCPP_INLINE_VISIBILITY
5661     void param(const param_type& __p) {__p_ = __p;}
5662
5663     _LIBCPP_INLINE_VISIBILITY
5664     result_type min() const {return 0;}
5665     _LIBCPP_INLINE_VISIBILITY
5666     result_type max() const {return numeric_limits<result_type>::infinity();}
5667
5668     friend _LIBCPP_INLINE_VISIBILITY
5669         bool operator==(const fisher_f_distribution& __x,
5670                         const fisher_f_distribution& __y)
5671         {return __x.__p_ == __y.__p_;}
5672     friend _LIBCPP_INLINE_VISIBILITY
5673         bool operator!=(const fisher_f_distribution& __x,
5674                         const fisher_f_distribution& __y)
5675         {return !(__x == __y);}
5676 };
5677
5678 template <class _RealType>
5679 template<class _URNG>
5680 _RealType
5681 fisher_f_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5682 {
5683     gamma_distribution<result_type> __gdm(__p.m() * result_type(.5));
5684     gamma_distribution<result_type> __gdn(__p.n() * result_type(.5));
5685     return __p.n() * __gdm(__g) / (__p.m() * __gdn(__g));
5686 }
5687
5688 template <class _CharT, class _Traits, class _RT>
5689 basic_ostream<_CharT, _Traits>&
5690 operator<<(basic_ostream<_CharT, _Traits>& __os,
5691            const fisher_f_distribution<_RT>& __x)
5692 {
5693     __save_flags<_CharT, _Traits> __lx(__os);
5694     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5695                ios_base::scientific);
5696     _CharT __sp = __os.widen(' ');
5697     __os.fill(__sp);
5698     __os << __x.m() << __sp << __x.n();
5699     return __os;
5700 }
5701
5702 template <class _CharT, class _Traits, class _RT>
5703 basic_istream<_CharT, _Traits>&
5704 operator>>(basic_istream<_CharT, _Traits>& __is,
5705            fisher_f_distribution<_RT>& __x)
5706 {
5707     typedef fisher_f_distribution<_RT> _Eng;
5708     typedef typename _Eng::result_type result_type;
5709     typedef typename _Eng::param_type param_type;
5710     __save_flags<_CharT, _Traits> __lx(__is);
5711     __is.flags(ios_base::dec | ios_base::skipws);
5712     result_type __m;
5713     result_type __n;
5714     __is >> __m >> __n;
5715     if (!__is.fail())
5716         __x.param(param_type(__m, __n));
5717     return __is;
5718 }
5719
5720 // student_t_distribution
5721
5722 template<class _RealType = double>
5723 class _LIBCPP_TEMPLATE_VIS student_t_distribution
5724 {
5725 public:
5726     // types
5727     typedef _RealType result_type;
5728
5729     class _LIBCPP_TEMPLATE_VIS param_type
5730     {
5731         result_type __n_;
5732     public:
5733         typedef student_t_distribution distribution_type;
5734
5735         _LIBCPP_INLINE_VISIBILITY
5736         explicit param_type(result_type __n = 1) : __n_(__n) {}
5737
5738         _LIBCPP_INLINE_VISIBILITY
5739         result_type n() const {return __n_;}
5740
5741         friend _LIBCPP_INLINE_VISIBILITY
5742             bool operator==(const param_type& __x, const param_type& __y)
5743             {return __x.__n_ == __y.__n_;}
5744         friend _LIBCPP_INLINE_VISIBILITY
5745             bool operator!=(const param_type& __x, const param_type& __y)
5746             {return !(__x == __y);}
5747     };
5748
5749 private:
5750     param_type __p_;
5751     normal_distribution<result_type> __nd_;
5752
5753 public:
5754     // constructor and reset functions
5755     _LIBCPP_INLINE_VISIBILITY
5756     explicit student_t_distribution(result_type __n = 1)
5757         : __p_(param_type(__n)) {}
5758     _LIBCPP_INLINE_VISIBILITY
5759     explicit student_t_distribution(const param_type& __p)
5760         : __p_(__p) {}
5761     _LIBCPP_INLINE_VISIBILITY
5762     void reset() {__nd_.reset();}
5763
5764     // generating functions
5765     template<class _URNG>
5766         _LIBCPP_INLINE_VISIBILITY
5767         result_type operator()(_URNG& __g)
5768         {return (*this)(__g, __p_);}
5769     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5770
5771     // property functions
5772     _LIBCPP_INLINE_VISIBILITY
5773     result_type n() const {return __p_.n();}
5774
5775     _LIBCPP_INLINE_VISIBILITY
5776     param_type param() const {return __p_;}
5777     _LIBCPP_INLINE_VISIBILITY
5778     void param(const param_type& __p) {__p_ = __p;}
5779
5780     _LIBCPP_INLINE_VISIBILITY
5781     result_type min() const {return -numeric_limits<result_type>::infinity();}
5782     _LIBCPP_INLINE_VISIBILITY
5783     result_type max() const {return numeric_limits<result_type>::infinity();}
5784
5785     friend _LIBCPP_INLINE_VISIBILITY
5786         bool operator==(const student_t_distribution& __x,
5787                         const student_t_distribution& __y)
5788         {return __x.__p_ == __y.__p_;}
5789     friend _LIBCPP_INLINE_VISIBILITY
5790         bool operator!=(const student_t_distribution& __x,
5791                         const student_t_distribution& __y)
5792         {return !(__x == __y);}
5793 };
5794
5795 template <class _RealType>
5796 template<class _URNG>
5797 _RealType
5798 student_t_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5799 {
5800     gamma_distribution<result_type> __gd(__p.n() * .5, 2);
5801     return __nd_(__g) * _VSTD::sqrt(__p.n()/__gd(__g));
5802 }
5803
5804 template <class _CharT, class _Traits, class _RT>
5805 basic_ostream<_CharT, _Traits>&
5806 operator<<(basic_ostream<_CharT, _Traits>& __os,
5807            const student_t_distribution<_RT>& __x)
5808 {
5809     __save_flags<_CharT, _Traits> __lx(__os);
5810     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5811                ios_base::scientific);
5812     __os << __x.n();
5813     return __os;
5814 }
5815
5816 template <class _CharT, class _Traits, class _RT>
5817 basic_istream<_CharT, _Traits>&
5818 operator>>(basic_istream<_CharT, _Traits>& __is,
5819            student_t_distribution<_RT>& __x)
5820 {
5821     typedef student_t_distribution<_RT> _Eng;
5822     typedef typename _Eng::result_type result_type;
5823     typedef typename _Eng::param_type param_type;
5824     __save_flags<_CharT, _Traits> __lx(__is);
5825     __is.flags(ios_base::dec | ios_base::skipws);
5826     result_type __n;
5827     __is >> __n;
5828     if (!__is.fail())
5829         __x.param(param_type(__n));
5830     return __is;
5831 }
5832
5833 // discrete_distribution
5834
5835 template<class _IntType = int>
5836 class _LIBCPP_TEMPLATE_VIS discrete_distribution
5837 {
5838 public:
5839     // types
5840     typedef _IntType result_type;
5841
5842     class _LIBCPP_TEMPLATE_VIS param_type
5843     {
5844         vector<double> __p_;
5845     public:
5846         typedef discrete_distribution distribution_type;
5847
5848         _LIBCPP_INLINE_VISIBILITY
5849         param_type() {}
5850         template<class _InputIterator>
5851             _LIBCPP_INLINE_VISIBILITY
5852             param_type(_InputIterator __f, _InputIterator __l)
5853             : __p_(__f, __l) {__init();}
5854 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5855         _LIBCPP_INLINE_VISIBILITY
5856         param_type(initializer_list<double> __wl)
5857             : __p_(__wl.begin(), __wl.end()) {__init();}
5858 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5859         template<class _UnaryOperation>
5860             param_type(size_t __nw, double __xmin, double __xmax,
5861                        _UnaryOperation __fw);
5862
5863         vector<double> probabilities() const;
5864
5865         friend _LIBCPP_INLINE_VISIBILITY
5866             bool operator==(const param_type& __x, const param_type& __y)
5867             {return __x.__p_ == __y.__p_;}
5868         friend _LIBCPP_INLINE_VISIBILITY
5869             bool operator!=(const param_type& __x, const param_type& __y)
5870             {return !(__x == __y);}
5871
5872     private:
5873         void __init();
5874
5875         friend class discrete_distribution;
5876
5877         template <class _CharT, class _Traits, class _IT>
5878         friend
5879         basic_ostream<_CharT, _Traits>&
5880         operator<<(basic_ostream<_CharT, _Traits>& __os,
5881                    const discrete_distribution<_IT>& __x);
5882
5883         template <class _CharT, class _Traits, class _IT>
5884         friend
5885         basic_istream<_CharT, _Traits>&
5886         operator>>(basic_istream<_CharT, _Traits>& __is,
5887                    discrete_distribution<_IT>& __x);
5888     };
5889
5890 private:
5891     param_type __p_;
5892
5893 public:
5894     // constructor and reset functions
5895     _LIBCPP_INLINE_VISIBILITY
5896     discrete_distribution() {}
5897     template<class _InputIterator>
5898         _LIBCPP_INLINE_VISIBILITY
5899         discrete_distribution(_InputIterator __f, _InputIterator __l)
5900             : __p_(__f, __l) {}
5901 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5902     _LIBCPP_INLINE_VISIBILITY
5903     discrete_distribution(initializer_list<double> __wl)
5904         : __p_(__wl) {}
5905 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5906     template<class _UnaryOperation>
5907         _LIBCPP_INLINE_VISIBILITY
5908         discrete_distribution(size_t __nw, double __xmin, double __xmax,
5909                               _UnaryOperation __fw)
5910         : __p_(__nw, __xmin, __xmax, __fw) {}
5911     _LIBCPP_INLINE_VISIBILITY
5912     explicit discrete_distribution(const param_type& __p)
5913         : __p_(__p) {}
5914     _LIBCPP_INLINE_VISIBILITY
5915     void reset() {}
5916
5917     // generating functions
5918     template<class _URNG>
5919         _LIBCPP_INLINE_VISIBILITY
5920         result_type operator()(_URNG& __g)
5921         {return (*this)(__g, __p_);}
5922     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5923
5924     // property functions
5925     _LIBCPP_INLINE_VISIBILITY
5926     vector<double> probabilities() const {return __p_.probabilities();}
5927
5928     _LIBCPP_INLINE_VISIBILITY
5929     param_type param() const {return __p_;}
5930     _LIBCPP_INLINE_VISIBILITY
5931     void param(const param_type& __p) {__p_ = __p;}
5932
5933     _LIBCPP_INLINE_VISIBILITY
5934     result_type min() const {return 0;}
5935     _LIBCPP_INLINE_VISIBILITY
5936     result_type max() const {return __p_.__p_.size();}
5937
5938     friend _LIBCPP_INLINE_VISIBILITY
5939         bool operator==(const discrete_distribution& __x,
5940                         const discrete_distribution& __y)
5941         {return __x.__p_ == __y.__p_;}
5942     friend _LIBCPP_INLINE_VISIBILITY
5943         bool operator!=(const discrete_distribution& __x,
5944                         const discrete_distribution& __y)
5945         {return !(__x == __y);}
5946
5947     template <class _CharT, class _Traits, class _IT>
5948     friend
5949     basic_ostream<_CharT, _Traits>&
5950     operator<<(basic_ostream<_CharT, _Traits>& __os,
5951                const discrete_distribution<_IT>& __x);
5952
5953     template <class _CharT, class _Traits, class _IT>
5954     friend
5955     basic_istream<_CharT, _Traits>&
5956     operator>>(basic_istream<_CharT, _Traits>& __is,
5957                discrete_distribution<_IT>& __x);
5958 };
5959
5960 template<class _IntType>
5961 template<class _UnaryOperation>
5962 discrete_distribution<_IntType>::param_type::param_type(size_t __nw,
5963                                                         double __xmin,
5964                                                         double __xmax,
5965                                                         _UnaryOperation __fw)
5966 {
5967     if (__nw > 1)
5968     {
5969         __p_.reserve(__nw - 1);
5970         double __d = (__xmax - __xmin) / __nw;
5971         double __d2 = __d / 2;
5972         for (size_t __k = 0; __k < __nw; ++__k)
5973             __p_.push_back(__fw(__xmin + __k * __d + __d2));
5974         __init();
5975     }
5976 }
5977
5978 template<class _IntType>
5979 void
5980 discrete_distribution<_IntType>::param_type::__init()
5981 {
5982     if (!__p_.empty())
5983     {
5984         if (__p_.size() > 1)
5985         {
5986             double __s = _VSTD::accumulate(__p_.begin(), __p_.end(), 0.0);
5987             for (_VSTD::vector<double>::iterator __i = __p_.begin(), __e = __p_.end();
5988                                                                        __i < __e; ++__i)
5989                 *__i /= __s;
5990             vector<double> __t(__p_.size() - 1);
5991             _VSTD::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin());
5992             swap(__p_, __t);
5993         }
5994         else
5995         {
5996             __p_.clear();
5997             __p_.shrink_to_fit();
5998         }
5999     }
6000 }
6001
6002 template<class _IntType>
6003 vector<double>
6004 discrete_distribution<_IntType>::param_type::probabilities() const
6005 {
6006     size_t __n = __p_.size();
6007     _VSTD::vector<double> __p(__n+1);
6008     _VSTD::adjacent_difference(__p_.begin(), __p_.end(), __p.begin());
6009     if (__n > 0)
6010         __p[__n] = 1 - __p_[__n-1];
6011     else
6012         __p[0] = 1;
6013     return __p;
6014 }
6015
6016 template<class _IntType>
6017 template<class _URNG>
6018 _IntType
6019 discrete_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
6020 {
6021     uniform_real_distribution<double> __gen;
6022     return static_cast<_IntType>(
6023            _VSTD::upper_bound(__p.__p_.begin(), __p.__p_.end(), __gen(__g)) -
6024                                                               __p.__p_.begin());
6025 }
6026
6027 template <class _CharT, class _Traits, class _IT>
6028 basic_ostream<_CharT, _Traits>&
6029 operator<<(basic_ostream<_CharT, _Traits>& __os,
6030            const discrete_distribution<_IT>& __x)
6031 {
6032     __save_flags<_CharT, _Traits> __lx(__os);
6033     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6034                ios_base::scientific);
6035     _CharT __sp = __os.widen(' ');
6036     __os.fill(__sp);
6037     size_t __n = __x.__p_.__p_.size();
6038     __os << __n;
6039     for (size_t __i = 0; __i < __n; ++__i)
6040         __os << __sp << __x.__p_.__p_[__i];
6041     return __os;
6042 }
6043
6044 template <class _CharT, class _Traits, class _IT>
6045 basic_istream<_CharT, _Traits>&
6046 operator>>(basic_istream<_CharT, _Traits>& __is,
6047            discrete_distribution<_IT>& __x)
6048 {
6049     __save_flags<_CharT, _Traits> __lx(__is);
6050     __is.flags(ios_base::dec | ios_base::skipws);
6051     size_t __n;
6052     __is >> __n;
6053     vector<double> __p(__n);
6054     for (size_t __i = 0; __i < __n; ++__i)
6055         __is >> __p[__i];
6056     if (!__is.fail())
6057         swap(__x.__p_.__p_, __p);
6058     return __is;
6059 }
6060
6061 // piecewise_constant_distribution
6062
6063 template<class _RealType = double>
6064 class _LIBCPP_TEMPLATE_VIS piecewise_constant_distribution
6065 {
6066 public:
6067     // types
6068     typedef _RealType result_type;
6069
6070     class _LIBCPP_TEMPLATE_VIS param_type
6071     {
6072         vector<result_type> __b_;
6073         vector<result_type> __densities_;
6074         vector<result_type> __areas_;
6075     public:
6076         typedef piecewise_constant_distribution distribution_type;
6077
6078         param_type();
6079         template<class _InputIteratorB, class _InputIteratorW>
6080             param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6081                        _InputIteratorW __fW);
6082 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6083         template<class _UnaryOperation>
6084             param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6085 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6086         template<class _UnaryOperation>
6087             param_type(size_t __nw, result_type __xmin, result_type __xmax,
6088                        _UnaryOperation __fw);
6089         param_type & operator=(const param_type& __rhs);
6090
6091         _LIBCPP_INLINE_VISIBILITY
6092         vector<result_type> intervals() const {return __b_;}
6093         _LIBCPP_INLINE_VISIBILITY
6094         vector<result_type> densities() const {return __densities_;}
6095
6096         friend _LIBCPP_INLINE_VISIBILITY
6097             bool operator==(const param_type& __x, const param_type& __y)
6098             {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6099         friend _LIBCPP_INLINE_VISIBILITY
6100             bool operator!=(const param_type& __x, const param_type& __y)
6101             {return !(__x == __y);}
6102
6103     private:
6104         void __init();
6105
6106         friend class piecewise_constant_distribution;
6107
6108         template <class _CharT, class _Traits, class _RT>
6109         friend
6110         basic_ostream<_CharT, _Traits>&
6111         operator<<(basic_ostream<_CharT, _Traits>& __os,
6112                    const piecewise_constant_distribution<_RT>& __x);
6113
6114         template <class _CharT, class _Traits, class _RT>
6115         friend
6116         basic_istream<_CharT, _Traits>&
6117         operator>>(basic_istream<_CharT, _Traits>& __is,
6118                    piecewise_constant_distribution<_RT>& __x);
6119     };
6120
6121 private:
6122     param_type __p_;
6123
6124 public:
6125     // constructor and reset functions
6126     _LIBCPP_INLINE_VISIBILITY
6127     piecewise_constant_distribution() {}
6128     template<class _InputIteratorB, class _InputIteratorW>
6129         _LIBCPP_INLINE_VISIBILITY
6130         piecewise_constant_distribution(_InputIteratorB __fB,
6131                                         _InputIteratorB __lB,
6132                                         _InputIteratorW __fW)
6133         : __p_(__fB, __lB, __fW) {}
6134
6135 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6136     template<class _UnaryOperation>
6137         _LIBCPP_INLINE_VISIBILITY
6138         piecewise_constant_distribution(initializer_list<result_type> __bl,
6139                                         _UnaryOperation __fw)
6140         : __p_(__bl, __fw) {}
6141 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6142
6143     template<class _UnaryOperation>
6144         _LIBCPP_INLINE_VISIBILITY
6145         piecewise_constant_distribution(size_t __nw, result_type __xmin,
6146                                         result_type __xmax, _UnaryOperation __fw)
6147         : __p_(__nw, __xmin, __xmax, __fw) {}
6148
6149     _LIBCPP_INLINE_VISIBILITY
6150     explicit piecewise_constant_distribution(const param_type& __p)
6151         : __p_(__p) {}
6152
6153     _LIBCPP_INLINE_VISIBILITY
6154     void reset() {}
6155
6156     // generating functions
6157     template<class _URNG>
6158         _LIBCPP_INLINE_VISIBILITY
6159         result_type operator()(_URNG& __g)
6160         {return (*this)(__g, __p_);}
6161     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6162
6163     // property functions
6164     _LIBCPP_INLINE_VISIBILITY
6165     vector<result_type> intervals() const {return __p_.intervals();}
6166     _LIBCPP_INLINE_VISIBILITY
6167     vector<result_type> densities() const {return __p_.densities();}
6168
6169     _LIBCPP_INLINE_VISIBILITY
6170     param_type param() const {return __p_;}
6171     _LIBCPP_INLINE_VISIBILITY
6172     void param(const param_type& __p) {__p_ = __p;}
6173
6174     _LIBCPP_INLINE_VISIBILITY
6175     result_type min() const {return __p_.__b_.front();}
6176     _LIBCPP_INLINE_VISIBILITY
6177     result_type max() const {return __p_.__b_.back();}
6178
6179     friend _LIBCPP_INLINE_VISIBILITY
6180         bool operator==(const piecewise_constant_distribution& __x,
6181                         const piecewise_constant_distribution& __y)
6182         {return __x.__p_ == __y.__p_;}
6183     friend _LIBCPP_INLINE_VISIBILITY
6184         bool operator!=(const piecewise_constant_distribution& __x,
6185                            const piecewise_constant_distribution& __y)
6186         {return !(__x == __y);}
6187
6188     template <class _CharT, class _Traits, class _RT>
6189     friend
6190     basic_ostream<_CharT, _Traits>&
6191     operator<<(basic_ostream<_CharT, _Traits>& __os,
6192                const piecewise_constant_distribution<_RT>& __x);
6193
6194     template <class _CharT, class _Traits, class _RT>
6195     friend
6196     basic_istream<_CharT, _Traits>&
6197     operator>>(basic_istream<_CharT, _Traits>& __is,
6198                piecewise_constant_distribution<_RT>& __x);
6199 };
6200
6201 template<class _RealType>
6202 typename piecewise_constant_distribution<_RealType>::param_type &
6203 piecewise_constant_distribution<_RealType>::param_type::operator=
6204                                                        (const param_type& __rhs)
6205 {
6206 //  These can throw
6207     __b_.reserve        (__rhs.__b_.size ());
6208     __densities_.reserve(__rhs.__densities_.size());
6209     __areas_.reserve    (__rhs.__areas_.size());
6210
6211 //  These can not throw
6212     __b_         = __rhs.__b_;
6213     __densities_ = __rhs.__densities_;
6214     __areas_     =  __rhs.__areas_;
6215     return *this;
6216 }
6217
6218 template<class _RealType>
6219 void
6220 piecewise_constant_distribution<_RealType>::param_type::__init()
6221 {
6222     // __densities_ contains non-normalized areas
6223     result_type __total_area = _VSTD::accumulate(__densities_.begin(),
6224                                                 __densities_.end(),
6225                                                 result_type());
6226     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6227         __densities_[__i] /= __total_area;
6228     // __densities_ contains normalized areas
6229     __areas_.assign(__densities_.size(), result_type());
6230     _VSTD::partial_sum(__densities_.begin(), __densities_.end() - 1,
6231                                                           __areas_.begin() + 1);
6232     // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1]
6233     __densities_.back() = 1 - __areas_.back();  // correct round off error
6234     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6235         __densities_[__i] /= (__b_[__i+1] - __b_[__i]);
6236     // __densities_ now contains __densities_
6237 }
6238
6239 template<class _RealType>
6240 piecewise_constant_distribution<_RealType>::param_type::param_type()
6241     : __b_(2),
6242       __densities_(1, 1.0),
6243       __areas_(1, 0.0)
6244 {
6245     __b_[1] = 1;
6246 }
6247
6248 template<class _RealType>
6249 template<class _InputIteratorB, class _InputIteratorW>
6250 piecewise_constant_distribution<_RealType>::param_type::param_type(
6251         _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6252     : __b_(__fB, __lB)
6253 {
6254     if (__b_.size() < 2)
6255     {
6256         __b_.resize(2);
6257         __b_[0] = 0;
6258         __b_[1] = 1;
6259         __densities_.assign(1, 1.0);
6260         __areas_.assign(1, 0.0);
6261     }
6262     else
6263     {
6264         __densities_.reserve(__b_.size() - 1);
6265         for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__fW)
6266             __densities_.push_back(*__fW);
6267         __init();
6268     }
6269 }
6270
6271 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6272
6273 template<class _RealType>
6274 template<class _UnaryOperation>
6275 piecewise_constant_distribution<_RealType>::param_type::param_type(
6276         initializer_list<result_type> __bl, _UnaryOperation __fw)
6277     : __b_(__bl.begin(), __bl.end())
6278 {
6279     if (__b_.size() < 2)
6280     {
6281         __b_.resize(2);
6282         __b_[0] = 0;
6283         __b_[1] = 1;
6284         __densities_.assign(1, 1.0);
6285         __areas_.assign(1, 0.0);
6286     }
6287     else
6288     {
6289         __densities_.reserve(__b_.size() - 1);
6290         for (size_t __i = 0; __i < __b_.size() - 1; ++__i)
6291             __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5));
6292         __init();
6293     }
6294 }
6295
6296 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6297
6298 template<class _RealType>
6299 template<class _UnaryOperation>
6300 piecewise_constant_distribution<_RealType>::param_type::param_type(
6301         size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6302     : __b_(__nw == 0 ? 2 : __nw + 1)
6303 {
6304     size_t __n = __b_.size() - 1;
6305     result_type __d = (__xmax - __xmin) / __n;
6306     __densities_.reserve(__n);
6307     for (size_t __i = 0; __i < __n; ++__i)
6308     {
6309         __b_[__i] = __xmin + __i * __d;
6310         __densities_.push_back(__fw(__b_[__i] + __d*.5));
6311     }
6312     __b_[__n] = __xmax;
6313     __init();
6314 }
6315
6316 template<class _RealType>
6317 template<class _URNG>
6318 _RealType
6319 piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6320 {
6321     typedef uniform_real_distribution<result_type> _Gen;
6322     result_type __u = _Gen()(__g);
6323     ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6324                                       __u) - __p.__areas_.begin() - 1;
6325     return (__u - __p.__areas_[__k]) / __p.__densities_[__k] + __p.__b_[__k];
6326 }
6327
6328 template <class _CharT, class _Traits, class _RT>
6329 basic_ostream<_CharT, _Traits>&
6330 operator<<(basic_ostream<_CharT, _Traits>& __os,
6331            const piecewise_constant_distribution<_RT>& __x)
6332 {
6333     __save_flags<_CharT, _Traits> __lx(__os);
6334     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6335                ios_base::scientific);
6336     _CharT __sp = __os.widen(' ');
6337     __os.fill(__sp);
6338     size_t __n = __x.__p_.__b_.size();
6339     __os << __n;
6340     for (size_t __i = 0; __i < __n; ++__i)
6341         __os << __sp << __x.__p_.__b_[__i];
6342     __n = __x.__p_.__densities_.size();
6343     __os << __sp << __n;
6344     for (size_t __i = 0; __i < __n; ++__i)
6345         __os << __sp << __x.__p_.__densities_[__i];
6346     __n = __x.__p_.__areas_.size();
6347     __os << __sp << __n;
6348     for (size_t __i = 0; __i < __n; ++__i)
6349         __os << __sp << __x.__p_.__areas_[__i];
6350     return __os;
6351 }
6352
6353 template <class _CharT, class _Traits, class _RT>
6354 basic_istream<_CharT, _Traits>&
6355 operator>>(basic_istream<_CharT, _Traits>& __is,
6356            piecewise_constant_distribution<_RT>& __x)
6357 {
6358     typedef piecewise_constant_distribution<_RT> _Eng;
6359     typedef typename _Eng::result_type result_type;
6360     __save_flags<_CharT, _Traits> __lx(__is);
6361     __is.flags(ios_base::dec | ios_base::skipws);
6362     size_t __n;
6363     __is >> __n;
6364     vector<result_type> __b(__n);
6365     for (size_t __i = 0; __i < __n; ++__i)
6366         __is >> __b[__i];
6367     __is >> __n;
6368     vector<result_type> __densities(__n);
6369     for (size_t __i = 0; __i < __n; ++__i)
6370         __is >> __densities[__i];
6371     __is >> __n;
6372     vector<result_type> __areas(__n);
6373     for (size_t __i = 0; __i < __n; ++__i)
6374         __is >> __areas[__i];
6375     if (!__is.fail())
6376     {
6377         swap(__x.__p_.__b_, __b);
6378         swap(__x.__p_.__densities_, __densities);
6379         swap(__x.__p_.__areas_, __areas);
6380     }
6381     return __is;
6382 }
6383
6384 // piecewise_linear_distribution
6385
6386 template<class _RealType = double>
6387 class _LIBCPP_TEMPLATE_VIS piecewise_linear_distribution
6388 {
6389 public:
6390     // types
6391     typedef _RealType result_type;
6392
6393     class _LIBCPP_TEMPLATE_VIS param_type
6394     {
6395         vector<result_type> __b_;
6396         vector<result_type> __densities_;
6397         vector<result_type> __areas_;
6398     public:
6399         typedef piecewise_linear_distribution distribution_type;
6400
6401         param_type();
6402         template<class _InputIteratorB, class _InputIteratorW>
6403             param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6404                        _InputIteratorW __fW);
6405 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6406         template<class _UnaryOperation>
6407             param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6408 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6409         template<class _UnaryOperation>
6410             param_type(size_t __nw, result_type __xmin, result_type __xmax,
6411                        _UnaryOperation __fw);
6412         param_type & operator=(const param_type& __rhs);
6413
6414         _LIBCPP_INLINE_VISIBILITY
6415         vector<result_type> intervals() const {return __b_;}
6416         _LIBCPP_INLINE_VISIBILITY
6417         vector<result_type> densities() const {return __densities_;}
6418
6419         friend _LIBCPP_INLINE_VISIBILITY
6420             bool operator==(const param_type& __x, const param_type& __y)
6421             {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6422         friend _LIBCPP_INLINE_VISIBILITY
6423             bool operator!=(const param_type& __x, const param_type& __y)
6424             {return !(__x == __y);}
6425
6426     private:
6427         void __init();
6428
6429         friend class piecewise_linear_distribution;
6430
6431         template <class _CharT, class _Traits, class _RT>
6432         friend
6433         basic_ostream<_CharT, _Traits>&
6434         operator<<(basic_ostream<_CharT, _Traits>& __os,
6435                    const piecewise_linear_distribution<_RT>& __x);
6436
6437         template <class _CharT, class _Traits, class _RT>
6438         friend
6439         basic_istream<_CharT, _Traits>&
6440         operator>>(basic_istream<_CharT, _Traits>& __is,
6441                    piecewise_linear_distribution<_RT>& __x);
6442     };
6443
6444 private:
6445     param_type __p_;
6446
6447 public:
6448     // constructor and reset functions
6449     _LIBCPP_INLINE_VISIBILITY
6450     piecewise_linear_distribution() {}
6451     template<class _InputIteratorB, class _InputIteratorW>
6452         _LIBCPP_INLINE_VISIBILITY
6453         piecewise_linear_distribution(_InputIteratorB __fB,
6454                                       _InputIteratorB __lB,
6455                                       _InputIteratorW __fW)
6456         : __p_(__fB, __lB, __fW) {}
6457
6458 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6459     template<class _UnaryOperation>
6460         _LIBCPP_INLINE_VISIBILITY
6461         piecewise_linear_distribution(initializer_list<result_type> __bl,
6462                                       _UnaryOperation __fw)
6463         : __p_(__bl, __fw) {}
6464 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6465
6466     template<class _UnaryOperation>
6467         _LIBCPP_INLINE_VISIBILITY
6468         piecewise_linear_distribution(size_t __nw, result_type __xmin,
6469                                       result_type __xmax, _UnaryOperation __fw)
6470         : __p_(__nw, __xmin, __xmax, __fw) {}
6471
6472     _LIBCPP_INLINE_VISIBILITY
6473     explicit piecewise_linear_distribution(const param_type& __p)
6474         : __p_(__p) {}
6475
6476     _LIBCPP_INLINE_VISIBILITY
6477     void reset() {}
6478
6479     // generating functions
6480     template<class _URNG>
6481         _LIBCPP_INLINE_VISIBILITY
6482         result_type operator()(_URNG& __g)
6483         {return (*this)(__g, __p_);}
6484     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6485
6486     // property functions
6487     _LIBCPP_INLINE_VISIBILITY
6488     vector<result_type> intervals() const {return __p_.intervals();}
6489     _LIBCPP_INLINE_VISIBILITY
6490     vector<result_type> densities() const {return __p_.densities();}
6491
6492     _LIBCPP_INLINE_VISIBILITY
6493     param_type param() const {return __p_;}
6494     _LIBCPP_INLINE_VISIBILITY
6495     void param(const param_type& __p) {__p_ = __p;}
6496
6497     _LIBCPP_INLINE_VISIBILITY
6498     result_type min() const {return __p_.__b_.front();}
6499     _LIBCPP_INLINE_VISIBILITY
6500     result_type max() const {return __p_.__b_.back();}
6501
6502     friend _LIBCPP_INLINE_VISIBILITY
6503         bool operator==(const piecewise_linear_distribution& __x,
6504                         const piecewise_linear_distribution& __y)
6505         {return __x.__p_ == __y.__p_;}
6506     friend _LIBCPP_INLINE_VISIBILITY
6507         bool operator!=(const piecewise_linear_distribution& __x,
6508                         const piecewise_linear_distribution& __y)
6509         {return !(__x == __y);}
6510
6511     template <class _CharT, class _Traits, class _RT>
6512     friend
6513     basic_ostream<_CharT, _Traits>&
6514     operator<<(basic_ostream<_CharT, _Traits>& __os,
6515                const piecewise_linear_distribution<_RT>& __x);
6516
6517     template <class _CharT, class _Traits, class _RT>
6518     friend
6519     basic_istream<_CharT, _Traits>&
6520     operator>>(basic_istream<_CharT, _Traits>& __is,
6521                piecewise_linear_distribution<_RT>& __x);
6522 };
6523
6524 template<class _RealType>
6525 typename piecewise_linear_distribution<_RealType>::param_type &
6526 piecewise_linear_distribution<_RealType>::param_type::operator=
6527                                                        (const param_type& __rhs)
6528 {
6529 //  These can throw
6530     __b_.reserve        (__rhs.__b_.size ());
6531     __densities_.reserve(__rhs.__densities_.size());
6532     __areas_.reserve    (__rhs.__areas_.size());
6533
6534 //  These can not throw
6535     __b_         = __rhs.__b_;
6536     __densities_ = __rhs.__densities_;
6537     __areas_     =  __rhs.__areas_;
6538     return *this;
6539 }
6540
6541
6542 template<class _RealType>
6543 void
6544 piecewise_linear_distribution<_RealType>::param_type::__init()
6545 {
6546     __areas_.assign(__densities_.size() - 1, result_type());
6547     result_type _Sp = 0;
6548     for (size_t __i = 0; __i < __areas_.size(); ++__i)
6549     {
6550         __areas_[__i] = (__densities_[__i+1] + __densities_[__i]) *
6551                         (__b_[__i+1] - __b_[__i]) * .5;
6552         _Sp += __areas_[__i];
6553     }
6554     for (size_t __i = __areas_.size(); __i > 1;)
6555     {
6556         --__i;
6557         __areas_[__i] = __areas_[__i-1] / _Sp;
6558     }
6559     __areas_[0] = 0;
6560     for (size_t __i = 1; __i < __areas_.size(); ++__i)
6561         __areas_[__i] += __areas_[__i-1];
6562     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6563         __densities_[__i] /= _Sp;
6564 }
6565
6566 template<class _RealType>
6567 piecewise_linear_distribution<_RealType>::param_type::param_type()
6568     : __b_(2),
6569       __densities_(2, 1.0),
6570       __areas_(1, 0.0)
6571 {
6572     __b_[1] = 1;
6573 }
6574
6575 template<class _RealType>
6576 template<class _InputIteratorB, class _InputIteratorW>
6577 piecewise_linear_distribution<_RealType>::param_type::param_type(
6578         _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6579     : __b_(__fB, __lB)
6580 {
6581     if (__b_.size() < 2)
6582     {
6583         __b_.resize(2);
6584         __b_[0] = 0;
6585         __b_[1] = 1;
6586         __densities_.assign(2, 1.0);
6587         __areas_.assign(1, 0.0);
6588     }
6589     else
6590     {
6591         __densities_.reserve(__b_.size());
6592         for (size_t __i = 0; __i < __b_.size(); ++__i, ++__fW)
6593             __densities_.push_back(*__fW);
6594         __init();
6595     }
6596 }
6597
6598 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6599
6600 template<class _RealType>
6601 template<class _UnaryOperation>
6602 piecewise_linear_distribution<_RealType>::param_type::param_type(
6603         initializer_list<result_type> __bl, _UnaryOperation __fw)
6604     : __b_(__bl.begin(), __bl.end())
6605 {
6606     if (__b_.size() < 2)
6607     {
6608         __b_.resize(2);
6609         __b_[0] = 0;
6610         __b_[1] = 1;
6611         __densities_.assign(2, 1.0);
6612         __areas_.assign(1, 0.0);
6613     }
6614     else
6615     {
6616         __densities_.reserve(__b_.size());
6617         for (size_t __i = 0; __i < __b_.size(); ++__i)
6618             __densities_.push_back(__fw(__b_[__i]));
6619         __init();
6620     }
6621 }
6622
6623 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6624
6625 template<class _RealType>
6626 template<class _UnaryOperation>
6627 piecewise_linear_distribution<_RealType>::param_type::param_type(
6628         size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6629     : __b_(__nw == 0 ? 2 : __nw + 1)
6630 {
6631     size_t __n = __b_.size() - 1;
6632     result_type __d = (__xmax - __xmin) / __n;
6633     __densities_.reserve(__b_.size());
6634     for (size_t __i = 0; __i < __n; ++__i)
6635     {
6636         __b_[__i] = __xmin + __i * __d;
6637         __densities_.push_back(__fw(__b_[__i]));
6638     }
6639     __b_[__n] = __xmax;
6640     __densities_.push_back(__fw(__b_[__n]));
6641     __init();
6642 }
6643
6644 template<class _RealType>
6645 template<class _URNG>
6646 _RealType
6647 piecewise_linear_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6648 {
6649     typedef uniform_real_distribution<result_type> _Gen;
6650     result_type __u = _Gen()(__g);
6651     ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6652                                       __u) - __p.__areas_.begin() - 1;
6653     __u -= __p.__areas_[__k];
6654     const result_type __dk = __p.__densities_[__k];
6655     const result_type __dk1 = __p.__densities_[__k+1];
6656     const result_type __deltad = __dk1 - __dk;
6657     const result_type __bk = __p.__b_[__k];
6658     if (__deltad == 0)
6659         return __u / __dk + __bk;
6660     const result_type __bk1 = __p.__b_[__k+1];
6661     const result_type __deltab = __bk1 - __bk;
6662     return (__bk * __dk1 - __bk1 * __dk +
6663         _VSTD::sqrt(__deltab * (__deltab * __dk * __dk + 2 * __deltad * __u))) /
6664         __deltad;
6665 }
6666
6667 template <class _CharT, class _Traits, class _RT>
6668 basic_ostream<_CharT, _Traits>&
6669 operator<<(basic_ostream<_CharT, _Traits>& __os,
6670            const piecewise_linear_distribution<_RT>& __x)
6671 {
6672     __save_flags<_CharT, _Traits> __lx(__os);
6673     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6674                ios_base::scientific);
6675     _CharT __sp = __os.widen(' ');
6676     __os.fill(__sp);
6677     size_t __n = __x.__p_.__b_.size();
6678     __os << __n;
6679     for (size_t __i = 0; __i < __n; ++__i)
6680         __os << __sp << __x.__p_.__b_[__i];
6681     __n = __x.__p_.__densities_.size();
6682     __os << __sp << __n;
6683     for (size_t __i = 0; __i < __n; ++__i)
6684         __os << __sp << __x.__p_.__densities_[__i];
6685     __n = __x.__p_.__areas_.size();
6686     __os << __sp << __n;
6687     for (size_t __i = 0; __i < __n; ++__i)
6688         __os << __sp << __x.__p_.__areas_[__i];
6689     return __os;
6690 }
6691
6692 template <class _CharT, class _Traits, class _RT>
6693 basic_istream<_CharT, _Traits>&
6694 operator>>(basic_istream<_CharT, _Traits>& __is,
6695            piecewise_linear_distribution<_RT>& __x)
6696 {
6697     typedef piecewise_linear_distribution<_RT> _Eng;
6698     typedef typename _Eng::result_type result_type;
6699     __save_flags<_CharT, _Traits> __lx(__is);
6700     __is.flags(ios_base::dec | ios_base::skipws);
6701     size_t __n;
6702     __is >> __n;
6703     vector<result_type> __b(__n);
6704     for (size_t __i = 0; __i < __n; ++__i)
6705         __is >> __b[__i];
6706     __is >> __n;
6707     vector<result_type> __densities(__n);
6708     for (size_t __i = 0; __i < __n; ++__i)
6709         __is >> __densities[__i];
6710     __is >> __n;
6711     vector<result_type> __areas(__n);
6712     for (size_t __i = 0; __i < __n; ++__i)
6713         __is >> __areas[__i];
6714     if (!__is.fail())
6715     {
6716         swap(__x.__p_.__b_, __b);
6717         swap(__x.__p_.__densities_, __densities);
6718         swap(__x.__p_.__areas_, __areas);
6719     }
6720     return __is;
6721 }
6722
6723 _LIBCPP_END_NAMESPACE_STD
6724
6725 #endif  // _LIBCPP_RANDOM