external/bsd/libc++/dist/libcxx/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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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_TYPE_VIS_ONLY 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 public:
2821     // types
2822     typedef typename _Engine::result_type result_type;
2823
2824     // engine characteristics
2825     static _LIBCPP_CONSTEXPR const size_t block_size = __p;
2826     static _LIBCPP_CONSTEXPR const size_t used_block = __r;
2827
2828 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
2829     static const result_type _Min = _Engine::_Min;
2830     static const result_type _Max = _Engine::_Max;
2831 #else
2832     static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
2833     static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
2834 #endif
2835
2836     _LIBCPP_INLINE_VISIBILITY
2837     static _LIBCPP_CONSTEXPR result_type min() { return _Engine::min(); }
2838     _LIBCPP_INLINE_VISIBILITY
2839     static _LIBCPP_CONSTEXPR result_type max() { return _Engine::max(); }
2840
2841     // constructors and seeding functions
2842     _LIBCPP_INLINE_VISIBILITY
2843     discard_block_engine() : __n_(0) {}
2844     _LIBCPP_INLINE_VISIBILITY
2845     explicit discard_block_engine(const _Engine& __e)
2846         : __e_(__e), __n_(0) {}
2847 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2848     _LIBCPP_INLINE_VISIBILITY
2849     explicit discard_block_engine(_Engine&& __e)
2850         : __e_(_VSTD::move(__e)), __n_(0) {}
2851 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2852     _LIBCPP_INLINE_VISIBILITY
2853     explicit discard_block_engine(result_type __sd) : __e_(__sd), __n_(0) {}
2854     template<class _Sseq>
2855         _LIBCPP_INLINE_VISIBILITY
2856         explicit discard_block_engine(_Sseq& __q,
2857         typename enable_if<__is_seed_sequence<_Sseq, discard_block_engine>::value &&
2858                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
2859         : __e_(__q), __n_(0) {}
2860     _LIBCPP_INLINE_VISIBILITY
2861     void seed() {__e_.seed(); __n_ = 0;}
2862     _LIBCPP_INLINE_VISIBILITY
2863     void seed(result_type __sd) {__e_.seed(__sd); __n_ = 0;}
2864     template<class _Sseq>
2865         _LIBCPP_INLINE_VISIBILITY
2866         typename enable_if
2867         <
2868             __is_seed_sequence<_Sseq, discard_block_engine>::value,
2869             void
2870         >::type
2871         seed(_Sseq& __q) {__e_.seed(__q); __n_ = 0;}
2872
2873     // generating functions
2874     result_type operator()();
2875     _LIBCPP_INLINE_VISIBILITY
2876     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
2877
2878     // property functions
2879     _LIBCPP_INLINE_VISIBILITY
2880     const _Engine& base() const _NOEXCEPT {return __e_;}
2881
2882     template<class _Eng, size_t _Pp, size_t _Rp>
2883     friend
2884     bool
2885     operator==(
2886         const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2887         const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2888
2889     template<class _Eng, size_t _Pp, size_t _Rp>
2890     friend
2891     bool
2892     operator!=(
2893         const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2894         const discard_block_engine<_Eng, _Pp, _Rp>& __y);
2895
2896     template <class _CharT, class _Traits,
2897               class _Eng, size_t _Pp, size_t _Rp>
2898     friend
2899     basic_ostream<_CharT, _Traits>&
2900     operator<<(basic_ostream<_CharT, _Traits>& __os,
2901                const discard_block_engine<_Eng, _Pp, _Rp>& __x);
2902
2903     template <class _CharT, class _Traits,
2904               class _Eng, size_t _Pp, size_t _Rp>
2905     friend
2906     basic_istream<_CharT, _Traits>&
2907     operator>>(basic_istream<_CharT, _Traits>& __is,
2908                discard_block_engine<_Eng, _Pp, _Rp>& __x);
2909 };
2910
2911 template<class _Engine, size_t __p, size_t __r>
2912     _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::block_size;
2913
2914 template<class _Engine, size_t __p, size_t __r>
2915     _LIBCPP_CONSTEXPR const size_t discard_block_engine<_Engine, __p, __r>::used_block;
2916
2917 template<class _Engine, size_t __p, size_t __r>
2918 typename discard_block_engine<_Engine, __p, __r>::result_type
2919 discard_block_engine<_Engine, __p, __r>::operator()()
2920 {
2921     if (__n_ >= __r)
2922     {
2923         __e_.discard(__p - __r);
2924         __n_ = 0;
2925     }
2926     ++__n_;
2927     return __e_();
2928 }
2929
2930 template<class _Eng, size_t _Pp, size_t _Rp>
2931 inline _LIBCPP_INLINE_VISIBILITY
2932 bool
2933 operator==(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2934            const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2935 {
2936     return __x.__n_ == __y.__n_ && __x.__e_ == __y.__e_;
2937 }
2938
2939 template<class _Eng, size_t _Pp, size_t _Rp>
2940 inline _LIBCPP_INLINE_VISIBILITY
2941 bool
2942 operator!=(const discard_block_engine<_Eng, _Pp, _Rp>& __x,
2943            const discard_block_engine<_Eng, _Pp, _Rp>& __y)
2944 {
2945     return !(__x == __y);
2946 }
2947
2948 template <class _CharT, class _Traits,
2949           class _Eng, size_t _Pp, size_t _Rp>
2950 basic_ostream<_CharT, _Traits>&
2951 operator<<(basic_ostream<_CharT, _Traits>& __os,
2952            const discard_block_engine<_Eng, _Pp, _Rp>& __x)
2953 {
2954     __save_flags<_CharT, _Traits> __lx(__os);
2955     __os.flags(ios_base::dec | ios_base::left);
2956     _CharT __sp = __os.widen(' ');
2957     __os.fill(__sp);
2958     return __os << __x.__e_ << __sp << __x.__n_;
2959 }
2960
2961 template <class _CharT, class _Traits,
2962           class _Eng, size_t _Pp, size_t _Rp>
2963 basic_istream<_CharT, _Traits>&
2964 operator>>(basic_istream<_CharT, _Traits>& __is,
2965            discard_block_engine<_Eng, _Pp, _Rp>& __x)
2966 {
2967     __save_flags<_CharT, _Traits> __lx(__is);
2968     __is.flags(ios_base::dec | ios_base::skipws);
2969     _Eng __e;
2970     int __n;
2971     __is >> __e >> __n;
2972     if (!__is.fail())
2973     {
2974         __x.__e_ = __e;
2975         __x.__n_ = __n;
2976     }
2977     return __is;
2978 }
2979
2980 typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
2981 typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
2982
2983 // independent_bits_engine
2984
2985 template<class _Engine, size_t __w, class _UIntType>
2986 class _LIBCPP_TYPE_VIS_ONLY independent_bits_engine
2987 {
2988     template <class _UI, _UI _R0, size_t _Wp, size_t _Mp>
2989     class __get_n
2990     {
2991         static _LIBCPP_CONSTEXPR const size_t _Dt = numeric_limits<_UI>::digits;
2992         static _LIBCPP_CONSTEXPR const size_t _Np = _Wp / _Mp + (_Wp % _Mp != 0);
2993         static _LIBCPP_CONSTEXPR const size_t _W0 = _Wp / _Np;
2994         static _LIBCPP_CONSTEXPR const _UI _Y0 = _W0 >= _Dt ? 0 : (_R0 >> _W0) << _W0;
2995     public:
2996         static _LIBCPP_CONSTEXPR const size_t value = _R0 - _Y0 > _Y0 / _Np ? _Np + 1 : _Np;
2997     };
2998 public:
2999     // types
3000     typedef _UIntType result_type;
3001
3002 private:
3003     _Engine __e_;
3004
3005     static _LIBCPP_CONSTEXPR const result_type _Dt = numeric_limits<result_type>::digits;
3006     static_assert(  0 <  __w, "independent_bits_engine invalid parameters");
3007     static_assert(__w <= _Dt, "independent_bits_engine invalid parameters");
3008
3009     typedef typename _Engine::result_type _Engine_result_type;
3010     typedef typename conditional
3011         <
3012             sizeof(_Engine_result_type) <= sizeof(result_type),
3013                 result_type,
3014                 _Engine_result_type
3015         >::type _Working_result_type;
3016 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3017     static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min
3018                                           + _Working_result_type(1);
3019 #else
3020     static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min()
3021                                                             + _Working_result_type(1);
3022 #endif
3023     static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value;
3024     static _LIBCPP_CONSTEXPR const size_t __n = __get_n<_Working_result_type, _Rp, __w, __m>::value;
3025     static _LIBCPP_CONSTEXPR const size_t __w0 = __w / __n;
3026     static _LIBCPP_CONSTEXPR const size_t __n0 = __n - __w % __n;
3027     static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits;
3028     static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
3029     static _LIBCPP_CONSTEXPR const _Working_result_type __y0 = __w0 >= _WDt ? 0 :
3030                                                                (_Rp >> __w0) << __w0;
3031     static _LIBCPP_CONSTEXPR const _Working_result_type __y1 = __w0 >= _WDt - 1 ? 0 :
3032                                                                (_Rp >> (__w0+1)) << (__w0+1);
3033     static _LIBCPP_CONSTEXPR const _Engine_result_type __mask0 = __w0 > 0 ?
3034                                 _Engine_result_type(~0) >> (_EDt - __w0) :
3035                                 _Engine_result_type(0);
3036     static _LIBCPP_CONSTEXPR const _Engine_result_type __mask1 = __w0 < _EDt - 1 ?
3037                                 _Engine_result_type(~0) >> (_EDt - (__w0 + 1)) :
3038                                 _Engine_result_type(~0);
3039 public:
3040     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3041     static _LIBCPP_CONSTEXPR const result_type _Max = __w == _Dt ? result_type(~0) :
3042                                                       (result_type(1) << __w) - result_type(1);
3043     static_assert(_Min < _Max, "independent_bits_engine invalid parameters");
3044
3045     // engine characteristics
3046     _LIBCPP_INLINE_VISIBILITY
3047     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3048     _LIBCPP_INLINE_VISIBILITY
3049     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3050
3051     // constructors and seeding functions
3052     _LIBCPP_INLINE_VISIBILITY
3053     independent_bits_engine() {}
3054     _LIBCPP_INLINE_VISIBILITY
3055     explicit independent_bits_engine(const _Engine& __e)
3056         : __e_(__e) {}
3057 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3058     _LIBCPP_INLINE_VISIBILITY
3059     explicit independent_bits_engine(_Engine&& __e)
3060         : __e_(_VSTD::move(__e)) {}
3061 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3062     _LIBCPP_INLINE_VISIBILITY
3063     explicit independent_bits_engine(result_type __sd) : __e_(__sd) {}
3064     template<class _Sseq>
3065         _LIBCPP_INLINE_VISIBILITY
3066         explicit independent_bits_engine(_Sseq& __q,
3067         typename enable_if<__is_seed_sequence<_Sseq, independent_bits_engine>::value &&
3068                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3069          : __e_(__q) {}
3070     _LIBCPP_INLINE_VISIBILITY
3071     void seed() {__e_.seed();}
3072     _LIBCPP_INLINE_VISIBILITY
3073     void seed(result_type __sd) {__e_.seed(__sd);}
3074     template<class _Sseq>
3075         _LIBCPP_INLINE_VISIBILITY
3076         typename enable_if
3077         <
3078             __is_seed_sequence<_Sseq, independent_bits_engine>::value,
3079             void
3080         >::type
3081         seed(_Sseq& __q) {__e_.seed(__q);}
3082
3083     // generating functions
3084     _LIBCPP_INLINE_VISIBILITY
3085     result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3086     _LIBCPP_INLINE_VISIBILITY
3087     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3088
3089     // property functions
3090     _LIBCPP_INLINE_VISIBILITY
3091     const _Engine& base() const _NOEXCEPT {return __e_;}
3092
3093     template<class _Eng, size_t _Wp, class _UI>
3094     friend
3095     bool
3096     operator==(
3097         const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3098         const independent_bits_engine<_Eng, _Wp, _UI>& __y);
3099
3100     template<class _Eng, size_t _Wp, class _UI>
3101     friend
3102     bool
3103     operator!=(
3104         const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3105         const independent_bits_engine<_Eng, _Wp, _UI>& __y);
3106
3107     template <class _CharT, class _Traits,
3108               class _Eng, size_t _Wp, class _UI>
3109     friend
3110     basic_ostream<_CharT, _Traits>&
3111     operator<<(basic_ostream<_CharT, _Traits>& __os,
3112                const independent_bits_engine<_Eng, _Wp, _UI>& __x);
3113
3114     template <class _CharT, class _Traits,
3115               class _Eng, size_t _Wp, class _UI>
3116     friend
3117     basic_istream<_CharT, _Traits>&
3118     operator>>(basic_istream<_CharT, _Traits>& __is,
3119                independent_bits_engine<_Eng, _Wp, _UI>& __x);
3120
3121 private:
3122     result_type __eval(false_type);
3123     result_type __eval(true_type);
3124
3125     template <size_t __count>
3126         _LIBCPP_INLINE_VISIBILITY
3127         static
3128         typename enable_if
3129         <
3130             __count < _Dt,
3131             result_type
3132         >::type
3133         __lshift(result_type __x) {return __x << __count;}
3134
3135     template <size_t __count>
3136         _LIBCPP_INLINE_VISIBILITY
3137         static
3138         typename enable_if
3139         <
3140             (__count >= _Dt),
3141             result_type
3142         >::type
3143         __lshift(result_type) {return result_type(0);}
3144 };
3145
3146 template<class _Engine, size_t __w, class _UIntType>
3147 inline _LIBCPP_INLINE_VISIBILITY
3148 _UIntType
3149 independent_bits_engine<_Engine, __w, _UIntType>::__eval(false_type)
3150 {
3151     return static_cast<result_type>(__e_() & __mask0);
3152 }
3153
3154 template<class _Engine, size_t __w, class _UIntType>
3155 _UIntType
3156 independent_bits_engine<_Engine, __w, _UIntType>::__eval(true_type)
3157 {
3158     result_type _Sp = 0;
3159     for (size_t __k = 0; __k < __n0; ++__k)
3160     {
3161         _Engine_result_type __u;
3162         do
3163         {
3164             __u = __e_() - _Engine::min();
3165         } while (__u >= __y0);
3166         _Sp = static_cast<result_type>(__lshift<__w0>(_Sp) + (__u & __mask0));
3167     }
3168     for (size_t __k = __n0; __k < __n; ++__k)
3169     {
3170         _Engine_result_type __u;
3171         do
3172         {
3173             __u = __e_() - _Engine::min();
3174         } while (__u >= __y1);
3175         _Sp = static_cast<result_type>(__lshift<__w0+1>(_Sp) + (__u & __mask1));
3176     }
3177     return _Sp;
3178 }
3179
3180 template<class _Eng, size_t _Wp, class _UI>
3181 inline _LIBCPP_INLINE_VISIBILITY
3182 bool
3183 operator==(
3184     const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3185     const independent_bits_engine<_Eng, _Wp, _UI>& __y)
3186 {
3187     return __x.base() == __y.base();
3188 }
3189
3190 template<class _Eng, size_t _Wp, class _UI>
3191 inline _LIBCPP_INLINE_VISIBILITY
3192 bool
3193 operator!=(
3194     const independent_bits_engine<_Eng, _Wp, _UI>& __x,
3195     const independent_bits_engine<_Eng, _Wp, _UI>& __y)
3196 {
3197     return !(__x == __y);
3198 }
3199
3200 template <class _CharT, class _Traits,
3201           class _Eng, size_t _Wp, class _UI>
3202 basic_ostream<_CharT, _Traits>&
3203 operator<<(basic_ostream<_CharT, _Traits>& __os,
3204            const independent_bits_engine<_Eng, _Wp, _UI>& __x)
3205 {
3206     return __os << __x.base();
3207 }
3208
3209 template <class _CharT, class _Traits,
3210           class _Eng, size_t _Wp, class _UI>
3211 basic_istream<_CharT, _Traits>&
3212 operator>>(basic_istream<_CharT, _Traits>& __is,
3213            independent_bits_engine<_Eng, _Wp, _UI>& __x)
3214 {
3215     _Eng __e;
3216     __is >> __e;
3217     if (!__is.fail())
3218         __x.__e_ = __e;
3219     return __is;
3220 }
3221
3222 // shuffle_order_engine
3223
3224 template <uint64_t _Xp, uint64_t _Yp>
3225 struct __ugcd
3226 {
3227     static _LIBCPP_CONSTEXPR const uint64_t value = __ugcd<_Yp, _Xp % _Yp>::value;
3228 };
3229
3230 template <uint64_t _Xp>
3231 struct __ugcd<_Xp, 0>
3232 {
3233     static _LIBCPP_CONSTEXPR const uint64_t value = _Xp;
3234 };
3235
3236 template <uint64_t _Np, uint64_t _Dp>
3237 class __uratio
3238 {
3239     static_assert(_Dp != 0, "__uratio divide by 0");
3240     static _LIBCPP_CONSTEXPR const uint64_t __gcd = __ugcd<_Np, _Dp>::value;
3241 public:
3242     static _LIBCPP_CONSTEXPR const uint64_t num = _Np / __gcd;
3243     static _LIBCPP_CONSTEXPR const uint64_t den = _Dp / __gcd;
3244
3245     typedef __uratio<num, den> type;
3246 };
3247
3248 template<class _Engine, size_t __k>
3249 class _LIBCPP_TYPE_VIS_ONLY shuffle_order_engine
3250 {
3251     static_assert(0 < __k, "shuffle_order_engine invalid parameters");
3252 public:
3253     // types
3254     typedef typename _Engine::result_type result_type;
3255
3256 private:
3257     _Engine __e_;
3258     result_type _V_[__k];
3259     result_type _Y_;
3260
3261 public:
3262     // engine characteristics
3263     static _LIBCPP_CONSTEXPR const size_t table_size = __k;
3264
3265 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3266     static const result_type _Min = _Engine::_Min;
3267     static const result_type _Max = _Engine::_Max;
3268 #else
3269     static _LIBCPP_CONSTEXPR const result_type _Min = _Engine::min();
3270     static _LIBCPP_CONSTEXPR const result_type _Max = _Engine::max();
3271 #endif
3272     static_assert(_Min < _Max, "shuffle_order_engine invalid parameters");
3273     _LIBCPP_INLINE_VISIBILITY
3274     static _LIBCPP_CONSTEXPR result_type min() { return _Min; }
3275     _LIBCPP_INLINE_VISIBILITY
3276     static _LIBCPP_CONSTEXPR result_type max() { return _Max; }
3277
3278     static _LIBCPP_CONSTEXPR const unsigned long long _Rp = _Max - _Min + 1ull;
3279
3280     // constructors and seeding functions
3281     _LIBCPP_INLINE_VISIBILITY
3282     shuffle_order_engine() {__init();}
3283     _LIBCPP_INLINE_VISIBILITY
3284     explicit shuffle_order_engine(const _Engine& __e)
3285         : __e_(__e) {__init();}
3286 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3287     _LIBCPP_INLINE_VISIBILITY
3288     explicit shuffle_order_engine(_Engine&& __e)
3289         : __e_(_VSTD::move(__e)) {__init();}
3290 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3291     _LIBCPP_INLINE_VISIBILITY
3292     explicit shuffle_order_engine(result_type __sd) : __e_(__sd) {__init();}
3293     template<class _Sseq>
3294         _LIBCPP_INLINE_VISIBILITY
3295         explicit shuffle_order_engine(_Sseq& __q,
3296         typename enable_if<__is_seed_sequence<_Sseq, shuffle_order_engine>::value &&
3297                            !is_convertible<_Sseq, _Engine>::value>::type* = 0)
3298          : __e_(__q) {__init();}
3299     _LIBCPP_INLINE_VISIBILITY
3300     void seed() {__e_.seed(); __init();}
3301     _LIBCPP_INLINE_VISIBILITY
3302     void seed(result_type __sd) {__e_.seed(__sd); __init();}
3303     template<class _Sseq>
3304         _LIBCPP_INLINE_VISIBILITY
3305         typename enable_if
3306         <
3307             __is_seed_sequence<_Sseq, shuffle_order_engine>::value,
3308             void
3309         >::type
3310         seed(_Sseq& __q) {__e_.seed(__q); __init();}
3311
3312     // generating functions
3313     _LIBCPP_INLINE_VISIBILITY
3314     result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}
3315     _LIBCPP_INLINE_VISIBILITY
3316     void discard(unsigned long long __z) {for (; __z; --__z) operator()();}
3317
3318     // property functions
3319     _LIBCPP_INLINE_VISIBILITY
3320     const _Engine& base() const _NOEXCEPT {return __e_;}
3321
3322 private:
3323     template<class _Eng, size_t _Kp>
3324     friend
3325     bool
3326     operator==(
3327         const shuffle_order_engine<_Eng, _Kp>& __x,
3328         const shuffle_order_engine<_Eng, _Kp>& __y);
3329
3330     template<class _Eng, size_t _Kp>
3331     friend
3332     bool
3333     operator!=(
3334         const shuffle_order_engine<_Eng, _Kp>& __x,
3335         const shuffle_order_engine<_Eng, _Kp>& __y);
3336
3337     template <class _CharT, class _Traits,
3338               class _Eng, size_t _Kp>
3339     friend
3340     basic_ostream<_CharT, _Traits>&
3341     operator<<(basic_ostream<_CharT, _Traits>& __os,
3342                const shuffle_order_engine<_Eng, _Kp>& __x);
3343
3344     template <class _CharT, class _Traits,
3345               class _Eng, size_t _Kp>
3346     friend
3347     basic_istream<_CharT, _Traits>&
3348     operator>>(basic_istream<_CharT, _Traits>& __is,
3349                shuffle_order_engine<_Eng, _Kp>& __x);
3350
3351     _LIBCPP_INLINE_VISIBILITY
3352     void __init()
3353     {
3354         for (size_t __i = 0; __i < __k; ++__i)
3355             _V_[__i] = __e_();
3356         _Y_ = __e_();
3357     }
3358
3359     _LIBCPP_INLINE_VISIBILITY
3360     result_type __eval(false_type) {return __eval2(integral_constant<bool, __k & 1>());}
3361     _LIBCPP_INLINE_VISIBILITY
3362     result_type __eval(true_type) {return __eval(__uratio<__k, _Rp>());}
3363
3364     _LIBCPP_INLINE_VISIBILITY
3365     result_type __eval2(false_type) {return __eval(__uratio<__k/2, 0x8000000000000000ull>());}
3366     _LIBCPP_INLINE_VISIBILITY
3367     result_type __eval2(true_type) {return __evalf<__k, 0>();}
3368
3369     template <uint64_t _Np, uint64_t _Dp>
3370         _LIBCPP_INLINE_VISIBILITY
3371         typename enable_if
3372         <
3373             (__uratio<_Np, _Dp>::num > 0xFFFFFFFFFFFFFFFFull / (_Max - _Min)),
3374             result_type
3375         >::type
3376         __eval(__uratio<_Np, _Dp>)
3377             {return __evalf<__uratio<_Np, _Dp>::num, __uratio<_Np, _Dp>::den>();}
3378
3379     template <uint64_t _Np, uint64_t _Dp>
3380         _LIBCPP_INLINE_VISIBILITY
3381         typename enable_if
3382         <
3383             __uratio<_Np, _Dp>::num <= 0xFFFFFFFFFFFFFFFFull / (_Max - _Min),
3384             result_type
3385         >::type
3386         __eval(__uratio<_Np, _Dp>)
3387         {
3388             const size_t __j = static_cast<size_t>(__uratio<_Np, _Dp>::num * (_Y_ - _Min)
3389                                                    / __uratio<_Np, _Dp>::den);
3390             _Y_ = _V_[__j];
3391             _V_[__j] = __e_();
3392             return _Y_;
3393         }
3394
3395     template <uint64_t __n, uint64_t __d>
3396         _LIBCPP_INLINE_VISIBILITY
3397         result_type __evalf()
3398         {
3399             const double _Fp = __d == 0 ?
3400                 __n / (2. * 0x8000000000000000ull) :
3401                 __n / (double)__d;
3402             const size_t __j = static_cast<size_t>(_Fp * (_Y_ - _Min));
3403             _Y_ = _V_[__j];
3404             _V_[__j] = __e_();
3405             return _Y_;
3406         }
3407 };
3408
3409 template<class _Engine, size_t __k>
3410     _LIBCPP_CONSTEXPR const size_t shuffle_order_engine<_Engine, __k>::table_size;
3411
3412 template<class _Eng, size_t _Kp>
3413 bool
3414 operator==(
3415     const shuffle_order_engine<_Eng, _Kp>& __x,
3416     const shuffle_order_engine<_Eng, _Kp>& __y)
3417 {
3418     return __x._Y_ == __y._Y_ && _VSTD::equal(__x._V_, __x._V_ + _Kp, __y._V_) &&
3419            __x.__e_ == __y.__e_;
3420 }
3421
3422 template<class _Eng, size_t _Kp>
3423 inline _LIBCPP_INLINE_VISIBILITY
3424 bool
3425 operator!=(
3426     const shuffle_order_engine<_Eng, _Kp>& __x,
3427     const shuffle_order_engine<_Eng, _Kp>& __y)
3428 {
3429     return !(__x == __y);
3430 }
3431
3432 template <class _CharT, class _Traits,
3433           class _Eng, size_t _Kp>
3434 basic_ostream<_CharT, _Traits>&
3435 operator<<(basic_ostream<_CharT, _Traits>& __os,
3436            const shuffle_order_engine<_Eng, _Kp>& __x)
3437 {
3438     __save_flags<_CharT, _Traits> __lx(__os);
3439     __os.flags(ios_base::dec | ios_base::left);
3440     _CharT __sp = __os.widen(' ');
3441     __os.fill(__sp);
3442     __os << __x.__e_ << __sp << __x._V_[0];
3443     for (size_t __i = 1; __i < _Kp; ++__i)
3444         __os << __sp << __x._V_[__i];
3445     return __os << __sp << __x._Y_;
3446 }
3447
3448 template <class _CharT, class _Traits,
3449           class _Eng, size_t _Kp>
3450 basic_istream<_CharT, _Traits>&
3451 operator>>(basic_istream<_CharT, _Traits>& __is,
3452            shuffle_order_engine<_Eng, _Kp>& __x)
3453 {
3454     typedef typename shuffle_order_engine<_Eng, _Kp>::result_type result_type;
3455     __save_flags<_CharT, _Traits> __lx(__is);
3456     __is.flags(ios_base::dec | ios_base::skipws);
3457     _Eng __e;
3458     result_type _Vp[_Kp+1];
3459     __is >> __e;
3460     for (size_t __i = 0; __i < _Kp+1; ++__i)
3461         __is >> _Vp[__i];
3462     if (!__is.fail())
3463     {
3464         __x.__e_ = __e;
3465         for (size_t __i = 0; __i < _Kp; ++__i)
3466             __x._V_[__i] = _Vp[__i];
3467         __x._Y_ = _Vp[_Kp];
3468     }
3469     return __is;
3470 }
3471
3472 typedef shuffle_order_engine<minstd_rand0, 256>                         knuth_b;
3473
3474 // random_device
3475
3476 class _LIBCPP_TYPE_VIS random_device
3477 {
3478 #ifdef _LIBCPP_USING_DEV_RANDOM
3479     int __f_;
3480 #endif // defined(_LIBCPP_USING_DEV_RANDOM)
3481 public:
3482     // types
3483     typedef unsigned result_type;
3484
3485     // generator characteristics
3486     static _LIBCPP_CONSTEXPR const result_type _Min = 0;
3487     static _LIBCPP_CONSTEXPR const result_type _Max = 0xFFFFFFFFu;
3488
3489     _LIBCPP_INLINE_VISIBILITY
3490     static _LIBCPP_CONSTEXPR result_type min() { return _Min;}
3491     _LIBCPP_INLINE_VISIBILITY
3492     static _LIBCPP_CONSTEXPR result_type max() { return _Max;}
3493
3494     // constructors
3495     explicit random_device(const string& __token = "/dev/urandom");
3496     ~random_device();
3497
3498     // generating functions
3499     result_type operator()();
3500
3501     // property functions
3502     double entropy() const _NOEXCEPT;
3503
3504 private:
3505     // no copy functions
3506     random_device(const random_device&); // = delete;
3507     random_device& operator=(const random_device&); // = delete;
3508 };
3509
3510 // seed_seq
3511
3512 class _LIBCPP_TYPE_VIS_ONLY seed_seq
3513 {
3514 public:
3515     // types
3516     typedef uint32_t result_type;
3517
3518 private:
3519     vector<result_type> __v_;
3520
3521     template<class _InputIterator>
3522         void init(_InputIterator __first, _InputIterator __last);
3523 public:
3524     // constructors
3525     _LIBCPP_INLINE_VISIBILITY
3526     seed_seq() _NOEXCEPT {}
3527 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
3528     template<class _Tp>
3529         _LIBCPP_INLINE_VISIBILITY
3530         seed_seq(initializer_list<_Tp> __il) {init(__il.begin(), __il.end());}
3531 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
3532
3533     template<class _InputIterator>
3534         _LIBCPP_INLINE_VISIBILITY
3535         seed_seq(_InputIterator __first, _InputIterator __last)
3536              {init(__first, __last);}
3537
3538     // generating functions
3539     template<class _RandomAccessIterator>
3540         void generate(_RandomAccessIterator __first, _RandomAccessIterator __last);
3541
3542     // property functions
3543     _LIBCPP_INLINE_VISIBILITY
3544     size_t size() const _NOEXCEPT {return __v_.size();}
3545     template<class _OutputIterator>
3546         _LIBCPP_INLINE_VISIBILITY
3547         void param(_OutputIterator __dest) const
3548             {_VSTD::copy(__v_.begin(), __v_.end(), __dest);}
3549
3550 private:
3551     // no copy functions
3552     seed_seq(const seed_seq&); // = delete;
3553     void operator=(const seed_seq&); // = delete;
3554
3555     _LIBCPP_INLINE_VISIBILITY
3556     static result_type _Tp(result_type __x) {return __x ^ (__x >> 27);}
3557 };
3558
3559 template<class _InputIterator>
3560 void
3561 seed_seq::init(_InputIterator __first, _InputIterator __last)
3562 {
3563     for (_InputIterator __s = __first; __s != __last; ++__s)
3564         __v_.push_back(*__s & 0xFFFFFFFF);
3565 }
3566
3567 template<class _RandomAccessIterator>
3568 void
3569 seed_seq::generate(_RandomAccessIterator __first, _RandomAccessIterator __last)
3570 {
3571     if (__first != __last)
3572     {
3573         _VSTD::fill(__first, __last, 0x8b8b8b8b);
3574         const size_t __n = static_cast<size_t>(__last - __first);
3575         const size_t __s = __v_.size();
3576         const size_t __t = (__n >= 623) ? 11
3577                          : (__n >= 68) ? 7
3578                          : (__n >= 39) ? 5
3579                          : (__n >= 7)  ? 3
3580                          : (__n - 1) / 2;
3581         const size_t __p = (__n - __t) / 2;
3582         const size_t __q = __p + __t;
3583         const size_t __m = _VSTD::max(__s + 1, __n);
3584         // __k = 0;
3585         {
3586             result_type __r = 1664525 * _Tp(__first[0] ^ __first[__p]
3587                                                       ^  __first[__n - 1]);
3588             __first[__p] += __r;
3589             __r += __s;
3590             __first[__q] += __r;
3591             __first[0] = __r;
3592         }
3593         for (size_t __k = 1; __k <= __s; ++__k)
3594         {
3595             const size_t __kmodn = __k % __n;
3596             const size_t __kpmodn = (__k + __p) % __n;
3597             result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3598                                            ^ __first[(__k - 1) % __n]);
3599             __first[__kpmodn] += __r;
3600             __r +=  __kmodn + __v_[__k-1];
3601             __first[(__k + __q) % __n] += __r;
3602             __first[__kmodn] = __r;
3603         }
3604         for (size_t __k = __s + 1; __k < __m; ++__k)
3605         {
3606             const size_t __kmodn = __k % __n;
3607             const size_t __kpmodn = (__k + __p) % __n;
3608             result_type __r = 1664525 * _Tp(__first[__kmodn] ^ __first[__kpmodn]
3609                                            ^ __first[(__k - 1) % __n]);
3610             __first[__kpmodn] += __r;
3611             __r +=  __kmodn;
3612             __first[(__k + __q) % __n] += __r;
3613             __first[__kmodn] = __r;
3614         }
3615         for (size_t __k = __m; __k < __m + __n; ++__k)
3616         {
3617             const size_t __kmodn = __k % __n;
3618             const size_t __kpmodn = (__k + __p) % __n;
3619             result_type __r = 1566083941 * _Tp(__first[__kmodn] +
3620                                               __first[__kpmodn] +
3621                                               __first[(__k - 1) % __n]);
3622             __first[__kpmodn] ^= __r;
3623             __r -= __kmodn;
3624             __first[(__k + __q) % __n] ^= __r;
3625             __first[__kmodn] = __r;
3626         }
3627     }
3628 }
3629
3630 // generate_canonical
3631
3632 template<class _RealType, size_t __bits, class _URNG>
3633 _RealType
3634 generate_canonical(_URNG& __g)
3635 {
3636     const size_t _Dt = numeric_limits<_RealType>::digits;
3637     const size_t __b = _Dt < __bits ? _Dt : __bits;
3638 #ifdef _LIBCPP_HAS_NO_CONSTEXPR
3639     const size_t __logR = __log2<uint64_t, _URNG::_Max - _URNG::_Min + uint64_t(1)>::value;
3640 #else
3641     const size_t __logR = __log2<uint64_t, _URNG::max() - _URNG::min() + uint64_t(1)>::value;
3642 #endif
3643     const size_t __k = __b / __logR + (__b % __logR != 0) + (__b == 0);
3644     const _RealType _Rp = _URNG::max() - _URNG::min() + _RealType(1);
3645     _RealType __base = _Rp;
3646     _RealType _Sp = __g() - _URNG::min();
3647     for (size_t __i = 1; __i < __k; ++__i, __base *= _Rp)
3648         _Sp += (__g() - _URNG::min()) * __base;
3649     return _Sp / __base;
3650 }
3651
3652 // uniform_int_distribution
3653
3654 // in <algorithm>
3655
3656 template <class _CharT, class _Traits, class _IT>
3657 basic_ostream<_CharT, _Traits>&
3658 operator<<(basic_ostream<_CharT, _Traits>& __os,
3659            const uniform_int_distribution<_IT>& __x)
3660 {
3661     __save_flags<_CharT, _Traits> __lx(__os);
3662     __os.flags(ios_base::dec | ios_base::left);
3663     _CharT __sp = __os.widen(' ');
3664     __os.fill(__sp);
3665     return __os << __x.a() << __sp << __x.b();
3666 }
3667
3668 template <class _CharT, class _Traits, class _IT>
3669 basic_istream<_CharT, _Traits>&
3670 operator>>(basic_istream<_CharT, _Traits>& __is,
3671            uniform_int_distribution<_IT>& __x)
3672 {
3673     typedef uniform_int_distribution<_IT> _Eng;
3674     typedef typename _Eng::result_type result_type;
3675     typedef typename _Eng::param_type param_type;
3676     __save_flags<_CharT, _Traits> __lx(__is);
3677     __is.flags(ios_base::dec | ios_base::skipws);
3678     result_type __a;
3679     result_type __b;
3680     __is >> __a >> __b;
3681     if (!__is.fail())
3682         __x.param(param_type(__a, __b));
3683     return __is;
3684 }
3685
3686 // uniform_real_distribution
3687
3688 template<class _RealType = double>
3689 class _LIBCPP_TYPE_VIS_ONLY uniform_real_distribution
3690 {
3691 public:
3692     // types
3693     typedef _RealType result_type;
3694
3695     class _LIBCPP_TYPE_VIS_ONLY param_type
3696     {
3697         result_type __a_;
3698         result_type __b_;
3699     public:
3700         typedef uniform_real_distribution distribution_type;
3701
3702         _LIBCPP_INLINE_VISIBILITY
3703         explicit param_type(result_type __a = 0,
3704                             result_type __b = 1)
3705             : __a_(__a), __b_(__b) {}
3706
3707         _LIBCPP_INLINE_VISIBILITY
3708         result_type a() const {return __a_;}
3709         _LIBCPP_INLINE_VISIBILITY
3710         result_type b() const {return __b_;}
3711
3712         friend _LIBCPP_INLINE_VISIBILITY
3713         bool operator==(const param_type& __x, const param_type& __y)
3714             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
3715         friend _LIBCPP_INLINE_VISIBILITY
3716         bool operator!=(const param_type& __x, const param_type& __y)
3717             {return !(__x == __y);}
3718     };
3719
3720 private:
3721     param_type __p_;
3722
3723 public:
3724     // constructors and reset functions
3725     _LIBCPP_INLINE_VISIBILITY
3726     explicit uniform_real_distribution(result_type __a = 0, result_type __b = 1)
3727         : __p_(param_type(__a, __b)) {}
3728     _LIBCPP_INLINE_VISIBILITY
3729     explicit uniform_real_distribution(const param_type& __p) : __p_(__p) {}
3730     _LIBCPP_INLINE_VISIBILITY
3731     void reset() {}
3732
3733     // generating functions
3734     template<class _URNG>
3735         _LIBCPP_INLINE_VISIBILITY
3736         result_type operator()(_URNG& __g)
3737         {return (*this)(__g, __p_);}
3738     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3739
3740     // property functions
3741     _LIBCPP_INLINE_VISIBILITY
3742     result_type a() const {return __p_.a();}
3743     _LIBCPP_INLINE_VISIBILITY
3744     result_type b() const {return __p_.b();}
3745
3746     _LIBCPP_INLINE_VISIBILITY
3747     param_type param() const {return __p_;}
3748     _LIBCPP_INLINE_VISIBILITY
3749     void param(const param_type& __p) {__p_ = __p;}
3750
3751     _LIBCPP_INLINE_VISIBILITY
3752     result_type min() const {return a();}
3753     _LIBCPP_INLINE_VISIBILITY
3754     result_type max() const {return b();}
3755
3756     friend _LIBCPP_INLINE_VISIBILITY
3757         bool operator==(const uniform_real_distribution& __x,
3758                         const uniform_real_distribution& __y)
3759         {return __x.__p_ == __y.__p_;}
3760     friend _LIBCPP_INLINE_VISIBILITY
3761         bool operator!=(const uniform_real_distribution& __x,
3762                         const uniform_real_distribution& __y)
3763         {return !(__x == __y);}
3764 };
3765
3766 template<class _RealType>
3767 template<class _URNG>
3768 inline _LIBCPP_INLINE_VISIBILITY
3769 typename uniform_real_distribution<_RealType>::result_type
3770 uniform_real_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
3771 {
3772     return (__p.b() - __p.a())
3773         * _VSTD::generate_canonical<_RealType, numeric_limits<_RealType>::digits>(__g)
3774         + __p.a();
3775 }
3776
3777 template <class _CharT, class _Traits, class _RT>
3778 basic_ostream<_CharT, _Traits>&
3779 operator<<(basic_ostream<_CharT, _Traits>& __os,
3780            const uniform_real_distribution<_RT>& __x)
3781 {
3782     __save_flags<_CharT, _Traits> __lx(__os);
3783     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3784                ios_base::scientific);
3785     _CharT __sp = __os.widen(' ');
3786     __os.fill(__sp);
3787     return __os << __x.a() << __sp << __x.b();
3788 }
3789
3790 template <class _CharT, class _Traits, class _RT>
3791 basic_istream<_CharT, _Traits>&
3792 operator>>(basic_istream<_CharT, _Traits>& __is,
3793            uniform_real_distribution<_RT>& __x)
3794 {
3795     typedef uniform_real_distribution<_RT> _Eng;
3796     typedef typename _Eng::result_type result_type;
3797     typedef typename _Eng::param_type param_type;
3798     __save_flags<_CharT, _Traits> __lx(__is);
3799     __is.flags(ios_base::dec | ios_base::skipws);
3800     result_type __a;
3801     result_type __b;
3802     __is >> __a >> __b;
3803     if (!__is.fail())
3804         __x.param(param_type(__a, __b));
3805     return __is;
3806 }
3807
3808 // bernoulli_distribution
3809
3810 class _LIBCPP_TYPE_VIS_ONLY bernoulli_distribution
3811 {
3812 public:
3813     // types
3814     typedef bool result_type;
3815
3816     class _LIBCPP_TYPE_VIS_ONLY param_type
3817     {
3818         double __p_;
3819     public:
3820         typedef bernoulli_distribution distribution_type;
3821
3822         _LIBCPP_INLINE_VISIBILITY
3823         explicit param_type(double __p = 0.5) : __p_(__p) {}
3824
3825         _LIBCPP_INLINE_VISIBILITY
3826         double p() const {return __p_;}
3827
3828         friend _LIBCPP_INLINE_VISIBILITY
3829             bool operator==(const param_type& __x, const param_type& __y)
3830             {return __x.__p_ == __y.__p_;}
3831         friend _LIBCPP_INLINE_VISIBILITY
3832             bool operator!=(const param_type& __x, const param_type& __y)
3833             {return !(__x == __y);}
3834     };
3835
3836 private:
3837     param_type __p_;
3838
3839 public:
3840     // constructors and reset functions
3841     _LIBCPP_INLINE_VISIBILITY
3842     explicit bernoulli_distribution(double __p = 0.5)
3843         : __p_(param_type(__p)) {}
3844     _LIBCPP_INLINE_VISIBILITY
3845     explicit bernoulli_distribution(const param_type& __p) : __p_(__p) {}
3846     _LIBCPP_INLINE_VISIBILITY
3847     void reset() {}
3848
3849     // generating functions
3850     template<class _URNG>
3851         _LIBCPP_INLINE_VISIBILITY
3852         result_type operator()(_URNG& __g)
3853         {return (*this)(__g, __p_);}
3854     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3855
3856     // property functions
3857     _LIBCPP_INLINE_VISIBILITY
3858     double p() const {return __p_.p();}
3859
3860     _LIBCPP_INLINE_VISIBILITY
3861     param_type param() const {return __p_;}
3862     _LIBCPP_INLINE_VISIBILITY
3863     void param(const param_type& __p) {__p_ = __p;}
3864
3865     _LIBCPP_INLINE_VISIBILITY
3866     result_type min() const {return false;}
3867     _LIBCPP_INLINE_VISIBILITY
3868     result_type max() const {return true;}
3869
3870     friend _LIBCPP_INLINE_VISIBILITY
3871         bool operator==(const bernoulli_distribution& __x,
3872                         const bernoulli_distribution& __y)
3873         {return __x.__p_ == __y.__p_;}
3874     friend _LIBCPP_INLINE_VISIBILITY
3875         bool operator!=(const bernoulli_distribution& __x,
3876                         const bernoulli_distribution& __y)
3877         {return !(__x == __y);}
3878 };
3879
3880 template<class _URNG>
3881 inline _LIBCPP_INLINE_VISIBILITY
3882 bernoulli_distribution::result_type
3883 bernoulli_distribution::operator()(_URNG& __g, const param_type& __p)
3884 {
3885     uniform_real_distribution<double> __gen;
3886     return __gen(__g) < __p.p();
3887 }
3888
3889 template <class _CharT, class _Traits>
3890 basic_ostream<_CharT, _Traits>&
3891 operator<<(basic_ostream<_CharT, _Traits>& __os, const bernoulli_distribution& __x)
3892 {
3893     __save_flags<_CharT, _Traits> __lx(__os);
3894     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
3895                ios_base::scientific);
3896     _CharT __sp = __os.widen(' ');
3897     __os.fill(__sp);
3898     return __os << __x.p();
3899 }
3900
3901 template <class _CharT, class _Traits>
3902 basic_istream<_CharT, _Traits>&
3903 operator>>(basic_istream<_CharT, _Traits>& __is, bernoulli_distribution& __x)
3904 {
3905     typedef bernoulli_distribution _Eng;
3906     typedef typename _Eng::param_type param_type;
3907     __save_flags<_CharT, _Traits> __lx(__is);
3908     __is.flags(ios_base::dec | ios_base::skipws);
3909     double __p;
3910     __is >> __p;
3911     if (!__is.fail())
3912         __x.param(param_type(__p));
3913     return __is;
3914 }
3915
3916 // binomial_distribution
3917
3918 template<class _IntType = int>
3919 class _LIBCPP_TYPE_VIS_ONLY binomial_distribution
3920 {
3921 public:
3922     // types
3923     typedef _IntType result_type;
3924
3925     class _LIBCPP_TYPE_VIS_ONLY param_type
3926     {
3927         result_type __t_;
3928         double __p_;
3929         double __pr_;
3930         double __odds_ratio_;
3931         result_type __r0_;
3932     public:
3933         typedef binomial_distribution distribution_type;
3934
3935         explicit param_type(result_type __t = 1, double __p = 0.5);
3936
3937         _LIBCPP_INLINE_VISIBILITY
3938         result_type t() const {return __t_;}
3939         _LIBCPP_INLINE_VISIBILITY
3940         double p() const {return __p_;}
3941
3942         friend _LIBCPP_INLINE_VISIBILITY
3943             bool operator==(const param_type& __x, const param_type& __y)
3944             {return __x.__t_ == __y.__t_ && __x.__p_ == __y.__p_;}
3945         friend _LIBCPP_INLINE_VISIBILITY
3946             bool operator!=(const param_type& __x, const param_type& __y)
3947             {return !(__x == __y);}
3948
3949         friend class binomial_distribution;
3950     };
3951
3952 private:
3953     param_type __p_;
3954
3955 public:
3956     // constructors and reset functions
3957     _LIBCPP_INLINE_VISIBILITY
3958     explicit binomial_distribution(result_type __t = 1, double __p = 0.5)
3959         : __p_(param_type(__t, __p)) {}
3960     _LIBCPP_INLINE_VISIBILITY
3961     explicit binomial_distribution(const param_type& __p) : __p_(__p) {}
3962     _LIBCPP_INLINE_VISIBILITY
3963     void reset() {}
3964
3965     // generating functions
3966     template<class _URNG>
3967         _LIBCPP_INLINE_VISIBILITY
3968         result_type operator()(_URNG& __g)
3969         {return (*this)(__g, __p_);}
3970     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
3971
3972     // property functions
3973     _LIBCPP_INLINE_VISIBILITY
3974     result_type t() const {return __p_.t();}
3975     _LIBCPP_INLINE_VISIBILITY
3976     double p() const {return __p_.p();}
3977
3978     _LIBCPP_INLINE_VISIBILITY
3979     param_type param() const {return __p_;}
3980     _LIBCPP_INLINE_VISIBILITY
3981     void param(const param_type& __p) {__p_ = __p;}
3982
3983     _LIBCPP_INLINE_VISIBILITY
3984     result_type min() const {return 0;}
3985     _LIBCPP_INLINE_VISIBILITY
3986     result_type max() const {return t();}
3987
3988     friend _LIBCPP_INLINE_VISIBILITY
3989         bool operator==(const binomial_distribution& __x,
3990                         const binomial_distribution& __y)
3991         {return __x.__p_ == __y.__p_;}
3992     friend _LIBCPP_INLINE_VISIBILITY
3993         bool operator!=(const binomial_distribution& __x,
3994                         const binomial_distribution& __y)
3995         {return !(__x == __y);}
3996 };
3997
3998 template<class _IntType>
3999 binomial_distribution<_IntType>::param_type::param_type(result_type __t, double __p)
4000     : __t_(__t), __p_(__p)
4001 {
4002     if (0 < __p_ && __p_ < 1)
4003     {
4004         __r0_ = static_cast<result_type>((__t_ + 1) * __p_);
4005         __pr_ = _VSTD::exp(_VSTD::lgamma(__t_ + 1.) - _VSTD::lgamma(__r0_ + 1.) -
4006                           _VSTD::lgamma(__t_ - __r0_ + 1.) + __r0_ * _VSTD::log(__p_) +
4007                           (__t_ - __r0_) * _VSTD::log(1 - __p_));
4008         __odds_ratio_ = __p_ / (1 - __p_);
4009     }
4010 }
4011
4012 // Reference: Kemp, C.D. (1986). `A modal method for generating binomial
4013 //           variables', Commun. Statist. - Theor. Meth. 15(3), 805-813.
4014 template<class _IntType>
4015 template<class _URNG>
4016 _IntType
4017 binomial_distribution<_IntType>::operator()(_URNG& __g, const param_type& __pr)
4018 {
4019     if (__pr.__t_ == 0 || __pr.__p_ == 0)
4020         return 0;
4021     if (__pr.__p_ == 1)
4022         return __pr.__t_;
4023     uniform_real_distribution<double> __gen;
4024     double __u = __gen(__g) - __pr.__pr_;
4025     if (__u < 0)
4026         return __pr.__r0_;
4027     double __pu = __pr.__pr_;
4028     double __pd = __pu;
4029     result_type __ru = __pr.__r0_;
4030     result_type __rd = __ru;
4031     while (true)
4032     {
4033         if (__rd >= 1)
4034         {
4035             __pd *= __rd / (__pr.__odds_ratio_ * (__pr.__t_ - __rd + 1));
4036             __u -= __pd;
4037             if (__u < 0)
4038                 return __rd - 1;
4039         }
4040         if ( __rd != 0 )
4041             --__rd;
4042         ++__ru;
4043         if (__ru <= __pr.__t_)
4044         {
4045             __pu *= (__pr.__t_ - __ru + 1) * __pr.__odds_ratio_ / __ru;
4046             __u -= __pu;
4047             if (__u < 0)
4048                 return __ru;
4049         }
4050     }
4051 }
4052
4053 template <class _CharT, class _Traits, class _IntType>
4054 basic_ostream<_CharT, _Traits>&
4055 operator<<(basic_ostream<_CharT, _Traits>& __os,
4056            const binomial_distribution<_IntType>& __x)
4057 {
4058     __save_flags<_CharT, _Traits> __lx(__os);
4059     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4060                ios_base::scientific);
4061     _CharT __sp = __os.widen(' ');
4062     __os.fill(__sp);
4063     return __os << __x.t() << __sp << __x.p();
4064 }
4065
4066 template <class _CharT, class _Traits, class _IntType>
4067 basic_istream<_CharT, _Traits>&
4068 operator>>(basic_istream<_CharT, _Traits>& __is,
4069            binomial_distribution<_IntType>& __x)
4070 {
4071     typedef binomial_distribution<_IntType> _Eng;
4072     typedef typename _Eng::result_type result_type;
4073     typedef typename _Eng::param_type param_type;
4074     __save_flags<_CharT, _Traits> __lx(__is);
4075     __is.flags(ios_base::dec | ios_base::skipws);
4076     result_type __t;
4077     double __p;
4078     __is >> __t >> __p;
4079     if (!__is.fail())
4080         __x.param(param_type(__t, __p));
4081     return __is;
4082 }
4083
4084 // exponential_distribution
4085
4086 template<class _RealType = double>
4087 class _LIBCPP_TYPE_VIS_ONLY exponential_distribution
4088 {
4089 public:
4090     // types
4091     typedef _RealType result_type;
4092
4093     class _LIBCPP_TYPE_VIS_ONLY param_type
4094     {
4095         result_type __lambda_;
4096     public:
4097         typedef exponential_distribution distribution_type;
4098
4099         _LIBCPP_INLINE_VISIBILITY
4100         explicit param_type(result_type __lambda = 1) : __lambda_(__lambda) {}
4101
4102         _LIBCPP_INLINE_VISIBILITY
4103         result_type lambda() const {return __lambda_;}
4104
4105         friend _LIBCPP_INLINE_VISIBILITY
4106             bool operator==(const param_type& __x, const param_type& __y)
4107             {return __x.__lambda_ == __y.__lambda_;}
4108         friend _LIBCPP_INLINE_VISIBILITY
4109             bool operator!=(const param_type& __x, const param_type& __y)
4110             {return !(__x == __y);}
4111     };
4112
4113 private:
4114     param_type __p_;
4115
4116 public:
4117     // constructors and reset functions
4118     _LIBCPP_INLINE_VISIBILITY
4119     explicit exponential_distribution(result_type __lambda = 1)
4120         : __p_(param_type(__lambda)) {}
4121     _LIBCPP_INLINE_VISIBILITY
4122     explicit exponential_distribution(const param_type& __p) : __p_(__p) {}
4123     _LIBCPP_INLINE_VISIBILITY
4124     void reset() {}
4125
4126     // generating functions
4127     template<class _URNG>
4128         _LIBCPP_INLINE_VISIBILITY
4129         result_type operator()(_URNG& __g)
4130         {return (*this)(__g, __p_);}
4131     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4132
4133     // property functions
4134     _LIBCPP_INLINE_VISIBILITY
4135     result_type lambda() const {return __p_.lambda();}
4136
4137     _LIBCPP_INLINE_VISIBILITY
4138     param_type param() const {return __p_;}
4139     _LIBCPP_INLINE_VISIBILITY
4140     void param(const param_type& __p) {__p_ = __p;}
4141
4142     _LIBCPP_INLINE_VISIBILITY
4143     result_type min() const {return 0;}
4144     _LIBCPP_INLINE_VISIBILITY
4145     result_type max() const {return numeric_limits<result_type>::infinity();}
4146
4147     friend _LIBCPP_INLINE_VISIBILITY
4148         bool operator==(const exponential_distribution& __x,
4149                         const exponential_distribution& __y)
4150         {return __x.__p_ == __y.__p_;}
4151     friend _LIBCPP_INLINE_VISIBILITY
4152         bool operator!=(const exponential_distribution& __x,
4153                         const exponential_distribution& __y)
4154         {return !(__x == __y);}
4155 };
4156
4157 template <class _RealType>
4158 template<class _URNG>
4159 _RealType
4160 exponential_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4161 {
4162     return -_VSTD::log
4163                   (
4164                       result_type(1) -
4165                       _VSTD::generate_canonical<result_type,
4166                                        numeric_limits<result_type>::digits>(__g)
4167                   )
4168                   / __p.lambda();
4169 }
4170
4171 template <class _CharT, class _Traits, class _RealType>
4172 basic_ostream<_CharT, _Traits>&
4173 operator<<(basic_ostream<_CharT, _Traits>& __os,
4174            const exponential_distribution<_RealType>& __x)
4175 {
4176     __save_flags<_CharT, _Traits> __lx(__os);
4177     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4178                ios_base::scientific);
4179     return __os << __x.lambda();
4180 }
4181
4182 template <class _CharT, class _Traits, class _RealType>
4183 basic_istream<_CharT, _Traits>&
4184 operator>>(basic_istream<_CharT, _Traits>& __is,
4185            exponential_distribution<_RealType>& __x)
4186 {
4187     typedef exponential_distribution<_RealType> _Eng;
4188     typedef typename _Eng::result_type result_type;
4189     typedef typename _Eng::param_type param_type;
4190     __save_flags<_CharT, _Traits> __lx(__is);
4191     __is.flags(ios_base::dec | ios_base::skipws);
4192     result_type __lambda;
4193     __is >> __lambda;
4194     if (!__is.fail())
4195         __x.param(param_type(__lambda));
4196     return __is;
4197 }
4198
4199 // normal_distribution
4200
4201 template<class _RealType = double>
4202 class _LIBCPP_TYPE_VIS_ONLY normal_distribution
4203 {
4204 public:
4205     // types
4206     typedef _RealType result_type;
4207
4208     class _LIBCPP_TYPE_VIS_ONLY param_type
4209     {
4210         result_type __mean_;
4211         result_type __stddev_;
4212     public:
4213         typedef normal_distribution distribution_type;
4214
4215         _LIBCPP_INLINE_VISIBILITY
4216         explicit param_type(result_type __mean = 0, result_type __stddev = 1)
4217             : __mean_(__mean), __stddev_(__stddev) {}
4218
4219         _LIBCPP_INLINE_VISIBILITY
4220         result_type mean() const {return __mean_;}
4221         _LIBCPP_INLINE_VISIBILITY
4222         result_type stddev() const {return __stddev_;}
4223
4224         friend _LIBCPP_INLINE_VISIBILITY
4225             bool operator==(const param_type& __x, const param_type& __y)
4226             {return __x.__mean_ == __y.__mean_ && __x.__stddev_ == __y.__stddev_;}
4227         friend _LIBCPP_INLINE_VISIBILITY
4228             bool operator!=(const param_type& __x, const param_type& __y)
4229             {return !(__x == __y);}
4230     };
4231
4232 private:
4233     param_type __p_;
4234     result_type _V_;
4235     bool _V_hot_;
4236
4237 public:
4238     // constructors and reset functions
4239     _LIBCPP_INLINE_VISIBILITY
4240     explicit normal_distribution(result_type __mean = 0, result_type __stddev = 1)
4241         : __p_(param_type(__mean, __stddev)), _V_hot_(false) {}
4242     _LIBCPP_INLINE_VISIBILITY
4243     explicit normal_distribution(const param_type& __p)
4244         : __p_(__p), _V_hot_(false) {}
4245     _LIBCPP_INLINE_VISIBILITY
4246     void reset() {_V_hot_ = false;}
4247
4248     // generating functions
4249     template<class _URNG>
4250         _LIBCPP_INLINE_VISIBILITY
4251         result_type operator()(_URNG& __g)
4252         {return (*this)(__g, __p_);}
4253     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4254
4255     // property functions
4256     _LIBCPP_INLINE_VISIBILITY
4257     result_type mean() const {return __p_.mean();}
4258     _LIBCPP_INLINE_VISIBILITY
4259     result_type stddev() const {return __p_.stddev();}
4260
4261     _LIBCPP_INLINE_VISIBILITY
4262     param_type param() const {return __p_;}
4263     _LIBCPP_INLINE_VISIBILITY
4264     void param(const param_type& __p) {__p_ = __p;}
4265
4266     _LIBCPP_INLINE_VISIBILITY
4267     result_type min() const {return -numeric_limits<result_type>::infinity();}
4268     _LIBCPP_INLINE_VISIBILITY
4269     result_type max() const {return numeric_limits<result_type>::infinity();}
4270
4271     friend _LIBCPP_INLINE_VISIBILITY
4272         bool operator==(const normal_distribution& __x,
4273                         const normal_distribution& __y)
4274         {return __x.__p_ == __y.__p_ && __x._V_hot_ == __y._V_hot_ &&
4275                 (!__x._V_hot_ || __x._V_ == __y._V_);}
4276     friend _LIBCPP_INLINE_VISIBILITY
4277         bool operator!=(const normal_distribution& __x,
4278                         const normal_distribution& __y)
4279         {return !(__x == __y);}
4280
4281     template <class _CharT, class _Traits, class _RT>
4282     friend
4283     basic_ostream<_CharT, _Traits>&
4284     operator<<(basic_ostream<_CharT, _Traits>& __os,
4285                const normal_distribution<_RT>& __x);
4286
4287     template <class _CharT, class _Traits, class _RT>
4288     friend
4289     basic_istream<_CharT, _Traits>&
4290     operator>>(basic_istream<_CharT, _Traits>& __is,
4291                normal_distribution<_RT>& __x);
4292 };
4293
4294 template <class _RealType>
4295 template<class _URNG>
4296 _RealType
4297 normal_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4298 {
4299     result_type _Up;
4300     if (_V_hot_)
4301     {
4302         _V_hot_ = false;
4303         _Up = _V_;
4304     }
4305     else
4306     {
4307         uniform_real_distribution<result_type> _Uni(-1, 1);
4308         result_type __u;
4309         result_type __v;
4310         result_type __s;
4311         do
4312         {
4313             __u = _Uni(__g);
4314             __v = _Uni(__g);
4315             __s = __u * __u + __v * __v;
4316         } while (__s > 1 || __s == 0);
4317         result_type _Fp = _VSTD::sqrt(-2 * _VSTD::log(__s) / __s);
4318         _V_ = __v * _Fp;
4319         _V_hot_ = true;
4320         _Up = __u * _Fp;
4321     }
4322     return _Up * __p.stddev() + __p.mean();
4323 }
4324
4325 template <class _CharT, class _Traits, class _RT>
4326 basic_ostream<_CharT, _Traits>&
4327 operator<<(basic_ostream<_CharT, _Traits>& __os,
4328            const normal_distribution<_RT>& __x)
4329 {
4330     __save_flags<_CharT, _Traits> __lx(__os);
4331     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4332                ios_base::scientific);
4333     _CharT __sp = __os.widen(' ');
4334     __os.fill(__sp);
4335     __os << __x.mean() << __sp << __x.stddev() << __sp << __x._V_hot_;
4336     if (__x._V_hot_)
4337         __os << __sp << __x._V_;
4338     return __os;
4339 }
4340
4341 template <class _CharT, class _Traits, class _RT>
4342 basic_istream<_CharT, _Traits>&
4343 operator>>(basic_istream<_CharT, _Traits>& __is,
4344            normal_distribution<_RT>& __x)
4345 {
4346     typedef normal_distribution<_RT> _Eng;
4347     typedef typename _Eng::result_type result_type;
4348     typedef typename _Eng::param_type param_type;
4349     __save_flags<_CharT, _Traits> __lx(__is);
4350     __is.flags(ios_base::dec | ios_base::skipws);
4351     result_type __mean;
4352     result_type __stddev;
4353     result_type _Vp = 0;
4354     bool _V_hot = false;
4355     __is >> __mean >> __stddev >> _V_hot;
4356     if (_V_hot)
4357         __is >> _Vp;
4358     if (!__is.fail())
4359     {
4360         __x.param(param_type(__mean, __stddev));
4361         __x._V_hot_ = _V_hot;
4362         __x._V_ = _Vp;
4363     }
4364     return __is;
4365 }
4366
4367 // lognormal_distribution
4368
4369 template<class _RealType = double>
4370 class _LIBCPP_TYPE_VIS_ONLY lognormal_distribution
4371 {
4372 public:
4373     // types
4374     typedef _RealType result_type;
4375
4376     class _LIBCPP_TYPE_VIS_ONLY param_type
4377     {
4378         normal_distribution<result_type> __nd_;
4379     public:
4380         typedef lognormal_distribution distribution_type;
4381
4382         _LIBCPP_INLINE_VISIBILITY
4383         explicit param_type(result_type __m = 0, result_type __s = 1)
4384             : __nd_(__m, __s) {}
4385
4386         _LIBCPP_INLINE_VISIBILITY
4387         result_type m() const {return __nd_.mean();}
4388         _LIBCPP_INLINE_VISIBILITY
4389         result_type s() const {return __nd_.stddev();}
4390
4391         friend _LIBCPP_INLINE_VISIBILITY
4392             bool operator==(const param_type& __x, const param_type& __y)
4393             {return __x.__nd_ == __y.__nd_;}
4394         friend _LIBCPP_INLINE_VISIBILITY
4395             bool operator!=(const param_type& __x, const param_type& __y)
4396             {return !(__x == __y);}
4397         friend class lognormal_distribution;
4398
4399         template <class _CharT, class _Traits, class _RT>
4400         friend
4401         basic_ostream<_CharT, _Traits>&
4402         operator<<(basic_ostream<_CharT, _Traits>& __os,
4403                    const lognormal_distribution<_RT>& __x);
4404
4405         template <class _CharT, class _Traits, class _RT>
4406         friend
4407         basic_istream<_CharT, _Traits>&
4408         operator>>(basic_istream<_CharT, _Traits>& __is,
4409                    lognormal_distribution<_RT>& __x);
4410     };
4411
4412 private:
4413     param_type __p_;
4414
4415 public:
4416     // constructor and reset functions
4417     _LIBCPP_INLINE_VISIBILITY
4418     explicit lognormal_distribution(result_type __m = 0, result_type __s = 1)
4419         : __p_(param_type(__m, __s)) {}
4420     _LIBCPP_INLINE_VISIBILITY
4421     explicit lognormal_distribution(const param_type& __p)
4422         : __p_(__p) {}
4423     _LIBCPP_INLINE_VISIBILITY
4424     void reset() {__p_.__nd_.reset();}
4425
4426     // generating functions
4427     template<class _URNG>
4428         _LIBCPP_INLINE_VISIBILITY
4429         result_type operator()(_URNG& __g)
4430         {return (*this)(__g, __p_);}
4431     template<class _URNG>
4432         _LIBCPP_INLINE_VISIBILITY
4433         result_type operator()(_URNG& __g, const param_type& __p)
4434         {return _VSTD::exp(const_cast<normal_distribution<result_type>&>(__p.__nd_)(__g));}
4435
4436     // property functions
4437     _LIBCPP_INLINE_VISIBILITY
4438     result_type m() const {return __p_.m();}
4439     _LIBCPP_INLINE_VISIBILITY
4440     result_type s() const {return __p_.s();}
4441
4442     _LIBCPP_INLINE_VISIBILITY
4443     param_type param() const {return __p_;}
4444     _LIBCPP_INLINE_VISIBILITY
4445     void param(const param_type& __p) {__p_ = __p;}
4446
4447     _LIBCPP_INLINE_VISIBILITY
4448     result_type min() const {return 0;}
4449     _LIBCPP_INLINE_VISIBILITY
4450     result_type max() const {return numeric_limits<result_type>::infinity();}
4451
4452     friend _LIBCPP_INLINE_VISIBILITY
4453         bool operator==(const lognormal_distribution& __x,
4454                         const lognormal_distribution& __y)
4455         {return __x.__p_ == __y.__p_;}
4456     friend _LIBCPP_INLINE_VISIBILITY
4457         bool operator!=(const lognormal_distribution& __x,
4458                         const lognormal_distribution& __y)
4459         {return !(__x == __y);}
4460
4461     template <class _CharT, class _Traits, class _RT>
4462     friend
4463     basic_ostream<_CharT, _Traits>&
4464     operator<<(basic_ostream<_CharT, _Traits>& __os,
4465                const lognormal_distribution<_RT>& __x);
4466
4467     template <class _CharT, class _Traits, class _RT>
4468     friend
4469     basic_istream<_CharT, _Traits>&
4470     operator>>(basic_istream<_CharT, _Traits>& __is,
4471                lognormal_distribution<_RT>& __x);
4472 };
4473
4474 template <class _CharT, class _Traits, class _RT>
4475 inline _LIBCPP_INLINE_VISIBILITY
4476 basic_ostream<_CharT, _Traits>&
4477 operator<<(basic_ostream<_CharT, _Traits>& __os,
4478            const lognormal_distribution<_RT>& __x)
4479 {
4480     return __os << __x.__p_.__nd_;
4481 }
4482
4483 template <class _CharT, class _Traits, class _RT>
4484 inline _LIBCPP_INLINE_VISIBILITY
4485 basic_istream<_CharT, _Traits>&
4486 operator>>(basic_istream<_CharT, _Traits>& __is,
4487            lognormal_distribution<_RT>& __x)
4488 {
4489     return __is >> __x.__p_.__nd_;
4490 }
4491
4492 // poisson_distribution
4493
4494 template<class _IntType = int>
4495 class _LIBCPP_TYPE_VIS_ONLY poisson_distribution
4496 {
4497 public:
4498     // types
4499     typedef _IntType result_type;
4500
4501     class _LIBCPP_TYPE_VIS_ONLY param_type
4502     {
4503         double __mean_;
4504         double __s_;
4505         double __d_;
4506         double __l_;
4507         double __omega_;
4508         double __c0_;
4509         double __c1_;
4510         double __c2_;
4511         double __c3_;
4512         double __c_;
4513
4514     public:
4515         typedef poisson_distribution distribution_type;
4516
4517         explicit param_type(double __mean = 1.0);
4518
4519         _LIBCPP_INLINE_VISIBILITY
4520         double mean() const {return __mean_;}
4521
4522         friend _LIBCPP_INLINE_VISIBILITY
4523             bool operator==(const param_type& __x, const param_type& __y)
4524             {return __x.__mean_ == __y.__mean_;}
4525         friend _LIBCPP_INLINE_VISIBILITY
4526             bool operator!=(const param_type& __x, const param_type& __y)
4527             {return !(__x == __y);}
4528
4529         friend class poisson_distribution;
4530     };
4531
4532 private:
4533     param_type __p_;
4534
4535 public:
4536     // constructors and reset functions
4537     _LIBCPP_INLINE_VISIBILITY
4538     explicit poisson_distribution(double __mean = 1.0) : __p_(__mean) {}
4539     _LIBCPP_INLINE_VISIBILITY
4540     explicit poisson_distribution(const param_type& __p) : __p_(__p) {}
4541     _LIBCPP_INLINE_VISIBILITY
4542     void reset() {}
4543
4544     // generating functions
4545     template<class _URNG>
4546         _LIBCPP_INLINE_VISIBILITY
4547         result_type operator()(_URNG& __g)
4548         {return (*this)(__g, __p_);}
4549     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4550
4551     // property functions
4552     _LIBCPP_INLINE_VISIBILITY
4553     double mean() const {return __p_.mean();}
4554
4555     _LIBCPP_INLINE_VISIBILITY
4556     param_type param() const {return __p_;}
4557     _LIBCPP_INLINE_VISIBILITY
4558     void param(const param_type& __p) {__p_ = __p;}
4559
4560     _LIBCPP_INLINE_VISIBILITY
4561     result_type min() const {return 0;}
4562     _LIBCPP_INLINE_VISIBILITY
4563     result_type max() const {return numeric_limits<result_type>::max();}
4564
4565     friend _LIBCPP_INLINE_VISIBILITY
4566         bool operator==(const poisson_distribution& __x,
4567                         const poisson_distribution& __y)
4568         {return __x.__p_ == __y.__p_;}
4569     friend _LIBCPP_INLINE_VISIBILITY
4570         bool operator!=(const poisson_distribution& __x,
4571                         const poisson_distribution& __y)
4572         {return !(__x == __y);}
4573 };
4574
4575 template<class _IntType>
4576 poisson_distribution<_IntType>::param_type::param_type(double __mean)
4577     : __mean_(__mean)
4578 {
4579     if (__mean_ < 10)
4580     {
4581         __s_ = 0;
4582         __d_ = 0;
4583         __l_ = _VSTD::exp(-__mean_);
4584         __omega_ = 0;
4585         __c3_ = 0;
4586         __c2_ = 0;
4587         __c1_ = 0;
4588         __c0_ = 0;
4589         __c_ = 0;
4590     }
4591     else
4592     {
4593         __s_ = _VSTD::sqrt(__mean_);
4594         __d_ = 6 * __mean_ * __mean_;
4595         __l_ = static_cast<result_type>(__mean_ - 1.1484);
4596         __omega_ = .3989423 / __s_;
4597         double __b1_ = .4166667E-1 / __mean_;
4598         double __b2_ = .3 * __b1_ * __b1_;
4599         __c3_ = .1428571 * __b1_ * __b2_;
4600         __c2_ = __b2_ - 15. * __c3_;
4601         __c1_ = __b1_ - 6. * __b2_ + 45. * __c3_;
4602         __c0_ = 1. - __b1_ + 3. * __b2_ - 15. * __c3_;
4603         __c_ = .1069 / __mean_;
4604     }
4605 }
4606
4607 template <class _IntType>
4608 template<class _URNG>
4609 _IntType
4610 poisson_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
4611 {
4612     result_type __x;
4613     uniform_real_distribution<double> __urd;
4614     if (__pr.__mean_ < 10)
4615     {
4616          __x = 0;
4617         for (double __p = __urd(__urng); __p > __pr.__l_; ++__x)
4618             __p *= __urd(__urng);
4619     }
4620     else
4621     {
4622         double __difmuk;
4623         double __g = __pr.__mean_ + __pr.__s_ * normal_distribution<double>()(__urng);
4624         double __u;
4625         if (__g > 0)
4626         {
4627             __x = static_cast<result_type>(__g);
4628             if (__x >= __pr.__l_)
4629                 return __x;
4630             __difmuk = __pr.__mean_ - __x;
4631             __u = __urd(__urng);
4632             if (__pr.__d_ * __u >= __difmuk * __difmuk * __difmuk)
4633                 return __x;
4634         }
4635         exponential_distribution<double> __edist;
4636         for (bool __using_exp_dist = false; true; __using_exp_dist = true)
4637         {
4638             double __e;
4639             if (__using_exp_dist || __g < 0)
4640             {
4641                 double __t;
4642                 do
4643                 {
4644                     __e = __edist(__urng);
4645                     __u = __urd(__urng);
4646                     __u += __u - 1;
4647                     __t = 1.8 + (__u < 0 ? -__e : __e);
4648                 } while (__t <= -.6744);
4649                 __x = __pr.__mean_ + __pr.__s_ * __t;
4650                 __difmuk = __pr.__mean_ - __x;
4651                 __using_exp_dist = true;
4652             }
4653             double __px;
4654             double __py;
4655             if (__x < 10)
4656             {
4657                 const result_type __fac[] = {1, 1, 2, 6, 24, 120, 720, 5040,
4658                                              40320, 362880};
4659                 __px = -__pr.__mean_;
4660                 __py = _VSTD::pow(__pr.__mean_, (double)__x) / __fac[__x];
4661             }
4662             else
4663             {
4664                 double __del = .8333333E-1 / __x;
4665                 __del -= 4.8 * __del * __del * __del;
4666                 double __v = __difmuk / __x;
4667                 if (_VSTD::abs(__v) > 0.25)
4668                     __px = __x * _VSTD::log(1 + __v) - __difmuk - __del;
4669                 else
4670                     __px = __x * __v * __v * (((((((.1250060 * __v + -.1384794) *
4671                            __v + .1421878) * __v + -.1661269) * __v + .2000118) *
4672                            __v + -.2500068) * __v + .3333333) * __v + -.5) - __del;
4673                 __py = .3989423 / _VSTD::sqrt(__x);
4674             }
4675             double __r = (0.5 - __difmuk) / __pr.__s_;
4676             double __r2 = __r * __r;
4677             double __fx = -0.5 * __r2;
4678             double __fy = __pr.__omega_ * (((__pr.__c3_ * __r2 + __pr.__c2_) *
4679                                         __r2 + __pr.__c1_) * __r2 + __pr.__c0_);
4680             if (__using_exp_dist)
4681             {
4682                 if (__pr.__c_ * _VSTD::abs(__u) <= __py * _VSTD::exp(__px + __e) -
4683                                                    __fy * _VSTD::exp(__fx + __e))
4684                     break;
4685             }
4686             else
4687             {
4688                 if (__fy - __u * __fy <= __py * _VSTD::exp(__px - __fx))
4689                     break;
4690             }
4691         }
4692     }
4693     return __x;
4694 }
4695
4696 template <class _CharT, class _Traits, class _IntType>
4697 basic_ostream<_CharT, _Traits>&
4698 operator<<(basic_ostream<_CharT, _Traits>& __os,
4699            const poisson_distribution<_IntType>& __x)
4700 {
4701     __save_flags<_CharT, _Traits> __lx(__os);
4702     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4703                ios_base::scientific);
4704     return __os << __x.mean();
4705 }
4706
4707 template <class _CharT, class _Traits, class _IntType>
4708 basic_istream<_CharT, _Traits>&
4709 operator>>(basic_istream<_CharT, _Traits>& __is,
4710            poisson_distribution<_IntType>& __x)
4711 {
4712     typedef poisson_distribution<_IntType> _Eng;
4713     typedef typename _Eng::param_type param_type;
4714     __save_flags<_CharT, _Traits> __lx(__is);
4715     __is.flags(ios_base::dec | ios_base::skipws);
4716     double __mean;
4717     __is >> __mean;
4718     if (!__is.fail())
4719         __x.param(param_type(__mean));
4720     return __is;
4721 }
4722
4723 // weibull_distribution
4724
4725 template<class _RealType = double>
4726 class _LIBCPP_TYPE_VIS_ONLY weibull_distribution
4727 {
4728 public:
4729     // types
4730     typedef _RealType result_type;
4731
4732     class _LIBCPP_TYPE_VIS_ONLY param_type
4733     {
4734         result_type __a_;
4735         result_type __b_;
4736     public:
4737         typedef weibull_distribution distribution_type;
4738
4739         _LIBCPP_INLINE_VISIBILITY
4740         explicit param_type(result_type __a = 1, result_type __b = 1)
4741             : __a_(__a), __b_(__b) {}
4742
4743         _LIBCPP_INLINE_VISIBILITY
4744         result_type a() const {return __a_;}
4745         _LIBCPP_INLINE_VISIBILITY
4746         result_type b() const {return __b_;}
4747
4748         friend _LIBCPP_INLINE_VISIBILITY
4749             bool operator==(const param_type& __x, const param_type& __y)
4750             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4751         friend _LIBCPP_INLINE_VISIBILITY
4752             bool operator!=(const param_type& __x, const param_type& __y)
4753             {return !(__x == __y);}
4754     };
4755
4756 private:
4757     param_type __p_;
4758
4759 public:
4760     // constructor and reset functions
4761     _LIBCPP_INLINE_VISIBILITY
4762     explicit weibull_distribution(result_type __a = 1, result_type __b = 1)
4763         : __p_(param_type(__a, __b)) {}
4764     _LIBCPP_INLINE_VISIBILITY
4765     explicit weibull_distribution(const param_type& __p)
4766         : __p_(__p) {}
4767     _LIBCPP_INLINE_VISIBILITY
4768     void reset() {}
4769
4770     // generating functions
4771     template<class _URNG>
4772         _LIBCPP_INLINE_VISIBILITY
4773         result_type operator()(_URNG& __g)
4774         {return (*this)(__g, __p_);}
4775     template<class _URNG>
4776         _LIBCPP_INLINE_VISIBILITY
4777         result_type operator()(_URNG& __g, const param_type& __p)
4778         {return __p.b() *
4779             _VSTD::pow(exponential_distribution<result_type>()(__g), 1/__p.a());}
4780
4781     // property functions
4782     _LIBCPP_INLINE_VISIBILITY
4783     result_type a() const {return __p_.a();}
4784     _LIBCPP_INLINE_VISIBILITY
4785     result_type b() const {return __p_.b();}
4786
4787     _LIBCPP_INLINE_VISIBILITY
4788     param_type param() const {return __p_;}
4789     _LIBCPP_INLINE_VISIBILITY
4790     void param(const param_type& __p) {__p_ = __p;}
4791
4792     _LIBCPP_INLINE_VISIBILITY
4793     result_type min() const {return 0;}
4794     _LIBCPP_INLINE_VISIBILITY
4795     result_type max() const {return numeric_limits<result_type>::infinity();}
4796
4797     friend _LIBCPP_INLINE_VISIBILITY
4798         bool operator==(const weibull_distribution& __x,
4799                         const weibull_distribution& __y)
4800         {return __x.__p_ == __y.__p_;}
4801     friend _LIBCPP_INLINE_VISIBILITY
4802         bool operator!=(const weibull_distribution& __x,
4803                         const weibull_distribution& __y)
4804         {return !(__x == __y);}
4805 };
4806
4807 template <class _CharT, class _Traits, class _RT>
4808 basic_ostream<_CharT, _Traits>&
4809 operator<<(basic_ostream<_CharT, _Traits>& __os,
4810            const weibull_distribution<_RT>& __x)
4811 {
4812     __save_flags<_CharT, _Traits> __lx(__os);
4813     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4814                ios_base::scientific);
4815     _CharT __sp = __os.widen(' ');
4816     __os.fill(__sp);
4817     __os << __x.a() << __sp << __x.b();
4818     return __os;
4819 }
4820
4821 template <class _CharT, class _Traits, class _RT>
4822 basic_istream<_CharT, _Traits>&
4823 operator>>(basic_istream<_CharT, _Traits>& __is,
4824            weibull_distribution<_RT>& __x)
4825 {
4826     typedef weibull_distribution<_RT> _Eng;
4827     typedef typename _Eng::result_type result_type;
4828     typedef typename _Eng::param_type param_type;
4829     __save_flags<_CharT, _Traits> __lx(__is);
4830     __is.flags(ios_base::dec | ios_base::skipws);
4831     result_type __a;
4832     result_type __b;
4833     __is >> __a >> __b;
4834     if (!__is.fail())
4835         __x.param(param_type(__a, __b));
4836     return __is;
4837 }
4838
4839 template<class _RealType = double>
4840 class _LIBCPP_TYPE_VIS_ONLY extreme_value_distribution
4841 {
4842 public:
4843     // types
4844     typedef _RealType result_type;
4845
4846     class _LIBCPP_TYPE_VIS_ONLY param_type
4847     {
4848         result_type __a_;
4849         result_type __b_;
4850     public:
4851         typedef extreme_value_distribution distribution_type;
4852
4853         _LIBCPP_INLINE_VISIBILITY
4854         explicit param_type(result_type __a = 0, result_type __b = 1)
4855             : __a_(__a), __b_(__b) {}
4856
4857         _LIBCPP_INLINE_VISIBILITY
4858         result_type a() const {return __a_;}
4859         _LIBCPP_INLINE_VISIBILITY
4860         result_type b() const {return __b_;}
4861
4862         friend _LIBCPP_INLINE_VISIBILITY
4863             bool operator==(const param_type& __x, const param_type& __y)
4864             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
4865         friend _LIBCPP_INLINE_VISIBILITY
4866             bool operator!=(const param_type& __x, const param_type& __y)
4867             {return !(__x == __y);}
4868     };
4869
4870 private:
4871     param_type __p_;
4872
4873 public:
4874     // constructor and reset functions
4875     _LIBCPP_INLINE_VISIBILITY
4876     explicit extreme_value_distribution(result_type __a = 0, result_type __b = 1)
4877         : __p_(param_type(__a, __b)) {}
4878     _LIBCPP_INLINE_VISIBILITY
4879     explicit extreme_value_distribution(const param_type& __p)
4880         : __p_(__p) {}
4881     _LIBCPP_INLINE_VISIBILITY
4882     void reset() {}
4883
4884     // generating functions
4885     template<class _URNG>
4886         _LIBCPP_INLINE_VISIBILITY
4887         result_type operator()(_URNG& __g)
4888         {return (*this)(__g, __p_);}
4889     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
4890
4891     // property functions
4892     _LIBCPP_INLINE_VISIBILITY
4893     result_type a() const {return __p_.a();}
4894     _LIBCPP_INLINE_VISIBILITY
4895     result_type b() const {return __p_.b();}
4896
4897     _LIBCPP_INLINE_VISIBILITY
4898     param_type param() const {return __p_;}
4899     _LIBCPP_INLINE_VISIBILITY
4900     void param(const param_type& __p) {__p_ = __p;}
4901
4902     _LIBCPP_INLINE_VISIBILITY
4903     result_type min() const {return -numeric_limits<result_type>::infinity();}
4904     _LIBCPP_INLINE_VISIBILITY
4905     result_type max() const {return numeric_limits<result_type>::infinity();}
4906
4907     friend _LIBCPP_INLINE_VISIBILITY
4908         bool operator==(const extreme_value_distribution& __x,
4909                         const extreme_value_distribution& __y)
4910         {return __x.__p_ == __y.__p_;}
4911     friend _LIBCPP_INLINE_VISIBILITY
4912         bool operator!=(const extreme_value_distribution& __x,
4913                         const extreme_value_distribution& __y)
4914         {return !(__x == __y);}
4915 };
4916
4917 template<class _RealType>
4918 template<class _URNG>
4919 _RealType
4920 extreme_value_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
4921 {
4922     return __p.a() - __p.b() *
4923          _VSTD::log(-_VSTD::log(1-uniform_real_distribution<result_type>()(__g)));
4924 }
4925
4926 template <class _CharT, class _Traits, class _RT>
4927 basic_ostream<_CharT, _Traits>&
4928 operator<<(basic_ostream<_CharT, _Traits>& __os,
4929            const extreme_value_distribution<_RT>& __x)
4930 {
4931     __save_flags<_CharT, _Traits> __lx(__os);
4932     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
4933                ios_base::scientific);
4934     _CharT __sp = __os.widen(' ');
4935     __os.fill(__sp);
4936     __os << __x.a() << __sp << __x.b();
4937     return __os;
4938 }
4939
4940 template <class _CharT, class _Traits, class _RT>
4941 basic_istream<_CharT, _Traits>&
4942 operator>>(basic_istream<_CharT, _Traits>& __is,
4943            extreme_value_distribution<_RT>& __x)
4944 {
4945     typedef extreme_value_distribution<_RT> _Eng;
4946     typedef typename _Eng::result_type result_type;
4947     typedef typename _Eng::param_type param_type;
4948     __save_flags<_CharT, _Traits> __lx(__is);
4949     __is.flags(ios_base::dec | ios_base::skipws);
4950     result_type __a;
4951     result_type __b;
4952     __is >> __a >> __b;
4953     if (!__is.fail())
4954         __x.param(param_type(__a, __b));
4955     return __is;
4956 }
4957
4958 // gamma_distribution
4959
4960 template<class _RealType = double>
4961 class _LIBCPP_TYPE_VIS_ONLY gamma_distribution
4962 {
4963 public:
4964     // types
4965     typedef _RealType result_type;
4966
4967     class _LIBCPP_TYPE_VIS_ONLY param_type
4968     {
4969         result_type __alpha_;
4970         result_type __beta_;
4971     public:
4972         typedef gamma_distribution distribution_type;
4973
4974         _LIBCPP_INLINE_VISIBILITY
4975         explicit param_type(result_type __alpha = 1, result_type __beta = 1)
4976             : __alpha_(__alpha), __beta_(__beta) {}
4977
4978         _LIBCPP_INLINE_VISIBILITY
4979         result_type alpha() const {return __alpha_;}
4980         _LIBCPP_INLINE_VISIBILITY
4981         result_type beta() const {return __beta_;}
4982
4983         friend _LIBCPP_INLINE_VISIBILITY
4984             bool operator==(const param_type& __x, const param_type& __y)
4985             {return __x.__alpha_ == __y.__alpha_ && __x.__beta_ == __y.__beta_;}
4986         friend _LIBCPP_INLINE_VISIBILITY
4987             bool operator!=(const param_type& __x, const param_type& __y)
4988             {return !(__x == __y);}
4989     };
4990
4991 private:
4992     param_type __p_;
4993
4994 public:
4995     // constructors and reset functions
4996     _LIBCPP_INLINE_VISIBILITY
4997     explicit gamma_distribution(result_type __alpha = 1, result_type __beta = 1)
4998         : __p_(param_type(__alpha, __beta)) {}
4999     _LIBCPP_INLINE_VISIBILITY
5000     explicit gamma_distribution(const param_type& __p)
5001         : __p_(__p) {}
5002     _LIBCPP_INLINE_VISIBILITY
5003     void reset() {}
5004
5005     // generating functions
5006     template<class _URNG>
5007         _LIBCPP_INLINE_VISIBILITY
5008         result_type operator()(_URNG& __g)
5009         {return (*this)(__g, __p_);}
5010     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5011
5012     // property functions
5013     _LIBCPP_INLINE_VISIBILITY
5014     result_type alpha() const {return __p_.alpha();}
5015     _LIBCPP_INLINE_VISIBILITY
5016     result_type beta() const {return __p_.beta();}
5017
5018     _LIBCPP_INLINE_VISIBILITY
5019     param_type param() const {return __p_;}
5020     _LIBCPP_INLINE_VISIBILITY
5021     void param(const param_type& __p) {__p_ = __p;}
5022
5023     _LIBCPP_INLINE_VISIBILITY
5024     result_type min() const {return 0;}
5025     _LIBCPP_INLINE_VISIBILITY
5026     result_type max() const {return numeric_limits<result_type>::infinity();}
5027
5028     friend _LIBCPP_INLINE_VISIBILITY
5029         bool operator==(const gamma_distribution& __x,
5030                         const gamma_distribution& __y)
5031         {return __x.__p_ == __y.__p_;}
5032     friend _LIBCPP_INLINE_VISIBILITY
5033         bool operator!=(const gamma_distribution& __x,
5034                         const gamma_distribution& __y)
5035         {return !(__x == __y);}
5036 };
5037
5038 template <class _RealType>
5039 template<class _URNG>
5040 _RealType
5041 gamma_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5042 {
5043     result_type __a = __p.alpha();
5044     uniform_real_distribution<result_type> __gen(0, 1);
5045     exponential_distribution<result_type> __egen;
5046     result_type __x;
5047     if (__a == 1)
5048         __x = __egen(__g);
5049     else if (__a > 1)
5050     {
5051         const result_type __b = __a - 1;
5052         const result_type __c = 3 * __a - result_type(0.75);
5053         while (true)
5054         {
5055             const result_type __u = __gen(__g);
5056             const result_type __v = __gen(__g);
5057             const result_type __w = __u * (1 - __u);
5058             if (__w != 0)
5059             {
5060                 const result_type __y = _VSTD::sqrt(__c / __w) *
5061                                         (__u - result_type(0.5));
5062                 __x = __b + __y;
5063                 if (__x >= 0)
5064                 {
5065                     const result_type __z = 64 * __w * __w * __w * __v * __v;
5066                     if (__z <= 1 - 2 * __y * __y / __x)
5067                         break;
5068                     if (_VSTD::log(__z) <= 2 * (__b * _VSTD::log(__x / __b) - __y))
5069                         break;
5070                 }
5071             }
5072         }
5073     }
5074     else  // __a < 1
5075     {
5076         while (true)
5077         {
5078             const result_type __u = __gen(__g);
5079             const result_type __es = __egen(__g);
5080             if (__u <= 1 - __a)
5081             {
5082                 __x = _VSTD::pow(__u, 1 / __a);
5083                 if (__x <= __es)
5084                     break;
5085             }
5086             else
5087             {
5088                 const result_type __e = -_VSTD::log((1-__u)/__a);
5089                 __x = _VSTD::pow(1 - __a + __a * __e, 1 / __a);
5090                 if (__x <= __e + __es)
5091                     break;
5092             }
5093         }
5094     }
5095     return __x * __p.beta();
5096 }
5097
5098 template <class _CharT, class _Traits, class _RT>
5099 basic_ostream<_CharT, _Traits>&
5100 operator<<(basic_ostream<_CharT, _Traits>& __os,
5101            const gamma_distribution<_RT>& __x)
5102 {
5103     __save_flags<_CharT, _Traits> __lx(__os);
5104     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5105                ios_base::scientific);
5106     _CharT __sp = __os.widen(' ');
5107     __os.fill(__sp);
5108     __os << __x.alpha() << __sp << __x.beta();
5109     return __os;
5110 }
5111
5112 template <class _CharT, class _Traits, class _RT>
5113 basic_istream<_CharT, _Traits>&
5114 operator>>(basic_istream<_CharT, _Traits>& __is,
5115            gamma_distribution<_RT>& __x)
5116 {
5117     typedef gamma_distribution<_RT> _Eng;
5118     typedef typename _Eng::result_type result_type;
5119     typedef typename _Eng::param_type param_type;
5120     __save_flags<_CharT, _Traits> __lx(__is);
5121     __is.flags(ios_base::dec | ios_base::skipws);
5122     result_type __alpha;
5123     result_type __beta;
5124     __is >> __alpha >> __beta;
5125     if (!__is.fail())
5126         __x.param(param_type(__alpha, __beta));
5127     return __is;
5128 }
5129
5130 // negative_binomial_distribution
5131
5132 template<class _IntType = int>
5133 class _LIBCPP_TYPE_VIS_ONLY negative_binomial_distribution
5134 {
5135 public:
5136     // types
5137     typedef _IntType result_type;
5138
5139     class _LIBCPP_TYPE_VIS_ONLY param_type
5140     {
5141         result_type __k_;
5142         double __p_;
5143     public:
5144         typedef negative_binomial_distribution distribution_type;
5145
5146         _LIBCPP_INLINE_VISIBILITY
5147         explicit param_type(result_type __k = 1, double __p = 0.5)
5148             : __k_(__k), __p_(__p) {}
5149
5150         _LIBCPP_INLINE_VISIBILITY
5151         result_type k() const {return __k_;}
5152         _LIBCPP_INLINE_VISIBILITY
5153         double p() const {return __p_;}
5154
5155         friend _LIBCPP_INLINE_VISIBILITY
5156             bool operator==(const param_type& __x, const param_type& __y)
5157             {return __x.__k_ == __y.__k_ && __x.__p_ == __y.__p_;}
5158         friend _LIBCPP_INLINE_VISIBILITY
5159             bool operator!=(const param_type& __x, const param_type& __y)
5160             {return !(__x == __y);}
5161     };
5162
5163 private:
5164     param_type __p_;
5165
5166 public:
5167     // constructor and reset functions
5168     _LIBCPP_INLINE_VISIBILITY
5169     explicit negative_binomial_distribution(result_type __k = 1, double __p = 0.5)
5170         : __p_(__k, __p) {}
5171     _LIBCPP_INLINE_VISIBILITY
5172     explicit negative_binomial_distribution(const param_type& __p) : __p_(__p) {}
5173     _LIBCPP_INLINE_VISIBILITY
5174     void reset() {}
5175
5176     // generating functions
5177     template<class _URNG>
5178         _LIBCPP_INLINE_VISIBILITY
5179         result_type operator()(_URNG& __g)
5180         {return (*this)(__g, __p_);}
5181     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5182
5183     // property functions
5184     _LIBCPP_INLINE_VISIBILITY
5185     result_type k() const {return __p_.k();}
5186     _LIBCPP_INLINE_VISIBILITY
5187     double p() const {return __p_.p();}
5188
5189     _LIBCPP_INLINE_VISIBILITY
5190     param_type param() const {return __p_;}
5191     _LIBCPP_INLINE_VISIBILITY
5192     void param(const param_type& __p) {__p_ = __p;}
5193
5194     _LIBCPP_INLINE_VISIBILITY
5195     result_type min() const {return 0;}
5196     _LIBCPP_INLINE_VISIBILITY
5197     result_type max() const {return numeric_limits<result_type>::max();}
5198
5199     friend _LIBCPP_INLINE_VISIBILITY
5200         bool operator==(const negative_binomial_distribution& __x,
5201                         const negative_binomial_distribution& __y)
5202         {return __x.__p_ == __y.__p_;}
5203     friend _LIBCPP_INLINE_VISIBILITY
5204         bool operator!=(const negative_binomial_distribution& __x,
5205                         const negative_binomial_distribution& __y)
5206         {return !(__x == __y);}
5207 };
5208
5209 template <class _IntType>
5210 template<class _URNG>
5211 _IntType
5212 negative_binomial_distribution<_IntType>::operator()(_URNG& __urng, const param_type& __pr)
5213 {
5214     result_type __k = __pr.k();
5215     double __p = __pr.p();
5216     if (__k <= 21 * __p)
5217     {
5218         bernoulli_distribution __gen(__p);
5219         result_type __f = 0;
5220         result_type __s = 0;
5221         while (__s < __k)
5222         {
5223             if (__gen(__urng))
5224                 ++__s;
5225             else
5226                 ++__f;
5227         }
5228         return __f;
5229     }
5230     return poisson_distribution<result_type>(gamma_distribution<double>
5231                                             (__k, (1-__p)/__p)(__urng))(__urng);
5232 }
5233
5234 template <class _CharT, class _Traits, class _IntType>
5235 basic_ostream<_CharT, _Traits>&
5236 operator<<(basic_ostream<_CharT, _Traits>& __os,
5237            const negative_binomial_distribution<_IntType>& __x)
5238 {
5239     __save_flags<_CharT, _Traits> __lx(__os);
5240     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5241                ios_base::scientific);
5242     _CharT __sp = __os.widen(' ');
5243     __os.fill(__sp);
5244     return __os << __x.k() << __sp << __x.p();
5245 }
5246
5247 template <class _CharT, class _Traits, class _IntType>
5248 basic_istream<_CharT, _Traits>&
5249 operator>>(basic_istream<_CharT, _Traits>& __is,
5250            negative_binomial_distribution<_IntType>& __x)
5251 {
5252     typedef negative_binomial_distribution<_IntType> _Eng;
5253     typedef typename _Eng::result_type result_type;
5254     typedef typename _Eng::param_type param_type;
5255     __save_flags<_CharT, _Traits> __lx(__is);
5256     __is.flags(ios_base::dec | ios_base::skipws);
5257     result_type __k;
5258     double __p;
5259     __is >> __k >> __p;
5260     if (!__is.fail())
5261         __x.param(param_type(__k, __p));
5262     return __is;
5263 }
5264
5265 // geometric_distribution
5266
5267 template<class _IntType = int>
5268 class _LIBCPP_TYPE_VIS_ONLY geometric_distribution
5269 {
5270 public:
5271     // types
5272     typedef _IntType result_type;
5273
5274     class _LIBCPP_TYPE_VIS_ONLY param_type
5275     {
5276         double __p_;
5277     public:
5278         typedef geometric_distribution distribution_type;
5279
5280         _LIBCPP_INLINE_VISIBILITY
5281         explicit param_type(double __p = 0.5) : __p_(__p) {}
5282
5283         _LIBCPP_INLINE_VISIBILITY
5284         double p() const {return __p_;}
5285
5286         friend _LIBCPP_INLINE_VISIBILITY
5287             bool operator==(const param_type& __x, const param_type& __y)
5288             {return __x.__p_ == __y.__p_;}
5289         friend _LIBCPP_INLINE_VISIBILITY
5290             bool operator!=(const param_type& __x, const param_type& __y)
5291             {return !(__x == __y);}
5292     };
5293
5294 private:
5295     param_type __p_;
5296
5297 public:
5298     // constructors and reset functions
5299     _LIBCPP_INLINE_VISIBILITY
5300     explicit geometric_distribution(double __p = 0.5) : __p_(__p) {}
5301     _LIBCPP_INLINE_VISIBILITY
5302     explicit geometric_distribution(const param_type& __p) : __p_(__p) {}
5303     _LIBCPP_INLINE_VISIBILITY
5304     void reset() {}
5305
5306     // generating functions
5307     template<class _URNG>
5308         _LIBCPP_INLINE_VISIBILITY
5309         result_type operator()(_URNG& __g)
5310         {return (*this)(__g, __p_);}
5311     template<class _URNG>
5312         _LIBCPP_INLINE_VISIBILITY
5313         result_type operator()(_URNG& __g, const param_type& __p)
5314         {return negative_binomial_distribution<result_type>(1, __p.p())(__g);}
5315
5316     // property functions
5317     _LIBCPP_INLINE_VISIBILITY
5318     double p() const {return __p_.p();}
5319
5320     _LIBCPP_INLINE_VISIBILITY
5321     param_type param() const {return __p_;}
5322     _LIBCPP_INLINE_VISIBILITY
5323     void param(const param_type& __p) {__p_ = __p;}
5324
5325     _LIBCPP_INLINE_VISIBILITY
5326     result_type min() const {return 0;}
5327     _LIBCPP_INLINE_VISIBILITY
5328     result_type max() const {return numeric_limits<result_type>::max();}
5329
5330     friend _LIBCPP_INLINE_VISIBILITY
5331         bool operator==(const geometric_distribution& __x,
5332                         const geometric_distribution& __y)
5333         {return __x.__p_ == __y.__p_;}
5334     friend _LIBCPP_INLINE_VISIBILITY
5335         bool operator!=(const geometric_distribution& __x,
5336                         const geometric_distribution& __y)
5337         {return !(__x == __y);}
5338 };
5339
5340 template <class _CharT, class _Traits, class _IntType>
5341 basic_ostream<_CharT, _Traits>&
5342 operator<<(basic_ostream<_CharT, _Traits>& __os,
5343            const geometric_distribution<_IntType>& __x)
5344 {
5345     __save_flags<_CharT, _Traits> __lx(__os);
5346     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5347                ios_base::scientific);
5348     return __os << __x.p();
5349 }
5350
5351 template <class _CharT, class _Traits, class _IntType>
5352 basic_istream<_CharT, _Traits>&
5353 operator>>(basic_istream<_CharT, _Traits>& __is,
5354            geometric_distribution<_IntType>& __x)
5355 {
5356     typedef geometric_distribution<_IntType> _Eng;
5357     typedef typename _Eng::param_type param_type;
5358     __save_flags<_CharT, _Traits> __lx(__is);
5359     __is.flags(ios_base::dec | ios_base::skipws);
5360     double __p;
5361     __is >> __p;
5362     if (!__is.fail())
5363         __x.param(param_type(__p));
5364     return __is;
5365 }
5366
5367 // chi_squared_distribution
5368
5369 template<class _RealType = double>
5370 class _LIBCPP_TYPE_VIS_ONLY chi_squared_distribution
5371 {
5372 public:
5373     // types
5374     typedef _RealType result_type;
5375
5376     class _LIBCPP_TYPE_VIS_ONLY param_type
5377     {
5378         result_type __n_;
5379     public:
5380         typedef chi_squared_distribution distribution_type;
5381
5382         _LIBCPP_INLINE_VISIBILITY
5383         explicit param_type(result_type __n = 1) : __n_(__n) {}
5384
5385         _LIBCPP_INLINE_VISIBILITY
5386         result_type n() const {return __n_;}
5387
5388         friend _LIBCPP_INLINE_VISIBILITY
5389             bool operator==(const param_type& __x, const param_type& __y)
5390             {return __x.__n_ == __y.__n_;}
5391         friend _LIBCPP_INLINE_VISIBILITY
5392             bool operator!=(const param_type& __x, const param_type& __y)
5393             {return !(__x == __y);}
5394     };
5395
5396 private:
5397     param_type __p_;
5398
5399 public:
5400     // constructor and reset functions
5401     _LIBCPP_INLINE_VISIBILITY
5402     explicit chi_squared_distribution(result_type __n = 1)
5403         : __p_(param_type(__n)) {}
5404     _LIBCPP_INLINE_VISIBILITY
5405     explicit chi_squared_distribution(const param_type& __p)
5406         : __p_(__p) {}
5407     _LIBCPP_INLINE_VISIBILITY
5408     void reset() {}
5409
5410     // generating functions
5411     template<class _URNG>
5412         _LIBCPP_INLINE_VISIBILITY
5413         result_type operator()(_URNG& __g)
5414         {return (*this)(__g, __p_);}
5415     template<class _URNG>
5416         _LIBCPP_INLINE_VISIBILITY
5417         result_type operator()(_URNG& __g, const param_type& __p)
5418         {return gamma_distribution<result_type>(__p.n() / 2, 2)(__g);}
5419
5420     // property functions
5421     _LIBCPP_INLINE_VISIBILITY
5422     result_type n() const {return __p_.n();}
5423
5424     _LIBCPP_INLINE_VISIBILITY
5425     param_type param() const {return __p_;}
5426     _LIBCPP_INLINE_VISIBILITY
5427     void param(const param_type& __p) {__p_ = __p;}
5428
5429     _LIBCPP_INLINE_VISIBILITY
5430     result_type min() const {return 0;}
5431     _LIBCPP_INLINE_VISIBILITY
5432     result_type max() const {return numeric_limits<result_type>::infinity();}
5433
5434     friend _LIBCPP_INLINE_VISIBILITY
5435         bool operator==(const chi_squared_distribution& __x,
5436                         const chi_squared_distribution& __y)
5437         {return __x.__p_ == __y.__p_;}
5438     friend _LIBCPP_INLINE_VISIBILITY
5439         bool operator!=(const chi_squared_distribution& __x,
5440                         const chi_squared_distribution& __y)
5441         {return !(__x == __y);}
5442 };
5443
5444 template <class _CharT, class _Traits, class _RT>
5445 basic_ostream<_CharT, _Traits>&
5446 operator<<(basic_ostream<_CharT, _Traits>& __os,
5447            const chi_squared_distribution<_RT>& __x)
5448 {
5449     __save_flags<_CharT, _Traits> __lx(__os);
5450     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5451                ios_base::scientific);
5452     __os << __x.n();
5453     return __os;
5454 }
5455
5456 template <class _CharT, class _Traits, class _RT>
5457 basic_istream<_CharT, _Traits>&
5458 operator>>(basic_istream<_CharT, _Traits>& __is,
5459            chi_squared_distribution<_RT>& __x)
5460 {
5461     typedef chi_squared_distribution<_RT> _Eng;
5462     typedef typename _Eng::result_type result_type;
5463     typedef typename _Eng::param_type param_type;
5464     __save_flags<_CharT, _Traits> __lx(__is);
5465     __is.flags(ios_base::dec | ios_base::skipws);
5466     result_type __n;
5467     __is >> __n;
5468     if (!__is.fail())
5469         __x.param(param_type(__n));
5470     return __is;
5471 }
5472
5473 // cauchy_distribution
5474
5475 template<class _RealType = double>
5476 class _LIBCPP_TYPE_VIS_ONLY cauchy_distribution
5477 {
5478 public:
5479     // types
5480     typedef _RealType result_type;
5481
5482     class _LIBCPP_TYPE_VIS_ONLY param_type
5483     {
5484         result_type __a_;
5485         result_type __b_;
5486     public:
5487         typedef cauchy_distribution distribution_type;
5488
5489         _LIBCPP_INLINE_VISIBILITY
5490         explicit param_type(result_type __a = 0, result_type __b = 1)
5491             : __a_(__a), __b_(__b) {}
5492
5493         _LIBCPP_INLINE_VISIBILITY
5494         result_type a() const {return __a_;}
5495         _LIBCPP_INLINE_VISIBILITY
5496         result_type b() const {return __b_;}
5497
5498         friend _LIBCPP_INLINE_VISIBILITY
5499             bool operator==(const param_type& __x, const param_type& __y)
5500             {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
5501         friend _LIBCPP_INLINE_VISIBILITY
5502             bool operator!=(const param_type& __x, const param_type& __y)
5503             {return !(__x == __y);}
5504     };
5505
5506 private:
5507     param_type __p_;
5508
5509 public:
5510     // constructor and reset functions
5511     _LIBCPP_INLINE_VISIBILITY
5512     explicit cauchy_distribution(result_type __a = 0, result_type __b = 1)
5513         : __p_(param_type(__a, __b)) {}
5514     _LIBCPP_INLINE_VISIBILITY
5515     explicit cauchy_distribution(const param_type& __p)
5516         : __p_(__p) {}
5517     _LIBCPP_INLINE_VISIBILITY
5518     void reset() {}
5519
5520     // generating functions
5521     template<class _URNG>
5522         _LIBCPP_INLINE_VISIBILITY
5523         result_type operator()(_URNG& __g)
5524         {return (*this)(__g, __p_);}
5525     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5526
5527     // property functions
5528     _LIBCPP_INLINE_VISIBILITY
5529     result_type a() const {return __p_.a();}
5530     _LIBCPP_INLINE_VISIBILITY
5531     result_type b() const {return __p_.b();}
5532
5533     _LIBCPP_INLINE_VISIBILITY
5534     param_type param() const {return __p_;}
5535     _LIBCPP_INLINE_VISIBILITY
5536     void param(const param_type& __p) {__p_ = __p;}
5537
5538     _LIBCPP_INLINE_VISIBILITY
5539     result_type min() const {return -numeric_limits<result_type>::infinity();}
5540     _LIBCPP_INLINE_VISIBILITY
5541     result_type max() const {return numeric_limits<result_type>::infinity();}
5542
5543     friend _LIBCPP_INLINE_VISIBILITY
5544         bool operator==(const cauchy_distribution& __x,
5545                         const cauchy_distribution& __y)
5546         {return __x.__p_ == __y.__p_;}
5547     friend _LIBCPP_INLINE_VISIBILITY
5548         bool operator!=(const cauchy_distribution& __x,
5549                         const cauchy_distribution& __y)
5550         {return !(__x == __y);}
5551 };
5552
5553 template <class _RealType>
5554 template<class _URNG>
5555 inline _LIBCPP_INLINE_VISIBILITY
5556 _RealType
5557 cauchy_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5558 {
5559     uniform_real_distribution<result_type> __gen;
5560     // purposefully let tan arg get as close to pi/2 as it wants, tan will return a finite
5561     return __p.a() + __p.b() * _VSTD::tan(3.1415926535897932384626433832795 * __gen(__g));
5562 }
5563
5564 template <class _CharT, class _Traits, class _RT>
5565 basic_ostream<_CharT, _Traits>&
5566 operator<<(basic_ostream<_CharT, _Traits>& __os,
5567            const cauchy_distribution<_RT>& __x)
5568 {
5569     __save_flags<_CharT, _Traits> __lx(__os);
5570     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5571                ios_base::scientific);
5572     _CharT __sp = __os.widen(' ');
5573     __os.fill(__sp);
5574     __os << __x.a() << __sp << __x.b();
5575     return __os;
5576 }
5577
5578 template <class _CharT, class _Traits, class _RT>
5579 basic_istream<_CharT, _Traits>&
5580 operator>>(basic_istream<_CharT, _Traits>& __is,
5581            cauchy_distribution<_RT>& __x)
5582 {
5583     typedef cauchy_distribution<_RT> _Eng;
5584     typedef typename _Eng::result_type result_type;
5585     typedef typename _Eng::param_type param_type;
5586     __save_flags<_CharT, _Traits> __lx(__is);
5587     __is.flags(ios_base::dec | ios_base::skipws);
5588     result_type __a;
5589     result_type __b;
5590     __is >> __a >> __b;
5591     if (!__is.fail())
5592         __x.param(param_type(__a, __b));
5593     return __is;
5594 }
5595
5596 // fisher_f_distribution
5597
5598 template<class _RealType = double>
5599 class _LIBCPP_TYPE_VIS_ONLY fisher_f_distribution
5600 {
5601 public:
5602     // types
5603     typedef _RealType result_type;
5604
5605     class _LIBCPP_TYPE_VIS_ONLY param_type
5606     {
5607         result_type __m_;
5608         result_type __n_;
5609     public:
5610         typedef fisher_f_distribution distribution_type;
5611
5612         _LIBCPP_INLINE_VISIBILITY
5613         explicit param_type(result_type __m = 1, result_type __n = 1)
5614             : __m_(__m), __n_(__n) {}
5615
5616         _LIBCPP_INLINE_VISIBILITY
5617         result_type m() const {return __m_;}
5618         _LIBCPP_INLINE_VISIBILITY
5619         result_type n() const {return __n_;}
5620
5621         friend _LIBCPP_INLINE_VISIBILITY
5622             bool operator==(const param_type& __x, const param_type& __y)
5623             {return __x.__m_ == __y.__m_ && __x.__n_ == __y.__n_;}
5624         friend _LIBCPP_INLINE_VISIBILITY
5625             bool operator!=(const param_type& __x, const param_type& __y)
5626             {return !(__x == __y);}
5627     };
5628
5629 private:
5630     param_type __p_;
5631
5632 public:
5633     // constructor and reset functions
5634     _LIBCPP_INLINE_VISIBILITY
5635     explicit fisher_f_distribution(result_type __m = 1, result_type __n = 1)
5636         : __p_(param_type(__m, __n)) {}
5637     _LIBCPP_INLINE_VISIBILITY
5638     explicit fisher_f_distribution(const param_type& __p)
5639         : __p_(__p) {}
5640     _LIBCPP_INLINE_VISIBILITY
5641     void reset() {}
5642
5643     // generating functions
5644     template<class _URNG>
5645         _LIBCPP_INLINE_VISIBILITY
5646         result_type operator()(_URNG& __g)
5647         {return (*this)(__g, __p_);}
5648     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5649
5650     // property functions
5651     _LIBCPP_INLINE_VISIBILITY
5652     result_type m() const {return __p_.m();}
5653     _LIBCPP_INLINE_VISIBILITY
5654     result_type n() const {return __p_.n();}
5655
5656     _LIBCPP_INLINE_VISIBILITY
5657     param_type param() const {return __p_;}
5658     _LIBCPP_INLINE_VISIBILITY
5659     void param(const param_type& __p) {__p_ = __p;}
5660
5661     _LIBCPP_INLINE_VISIBILITY
5662     result_type min() const {return 0;}
5663     _LIBCPP_INLINE_VISIBILITY
5664     result_type max() const {return numeric_limits<result_type>::infinity();}
5665
5666     friend _LIBCPP_INLINE_VISIBILITY
5667         bool operator==(const fisher_f_distribution& __x,
5668                         const fisher_f_distribution& __y)
5669         {return __x.__p_ == __y.__p_;}
5670     friend _LIBCPP_INLINE_VISIBILITY
5671         bool operator!=(const fisher_f_distribution& __x,
5672                         const fisher_f_distribution& __y)
5673         {return !(__x == __y);}
5674 };
5675
5676 template <class _RealType>
5677 template<class _URNG>
5678 _RealType
5679 fisher_f_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5680 {
5681     gamma_distribution<result_type> __gdm(__p.m() * result_type(.5));
5682     gamma_distribution<result_type> __gdn(__p.n() * result_type(.5));
5683     return __p.n() * __gdm(__g) / (__p.m() * __gdn(__g));
5684 }
5685
5686 template <class _CharT, class _Traits, class _RT>
5687 basic_ostream<_CharT, _Traits>&
5688 operator<<(basic_ostream<_CharT, _Traits>& __os,
5689            const fisher_f_distribution<_RT>& __x)
5690 {
5691     __save_flags<_CharT, _Traits> __lx(__os);
5692     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5693                ios_base::scientific);
5694     _CharT __sp = __os.widen(' ');
5695     __os.fill(__sp);
5696     __os << __x.m() << __sp << __x.n();
5697     return __os;
5698 }
5699
5700 template <class _CharT, class _Traits, class _RT>
5701 basic_istream<_CharT, _Traits>&
5702 operator>>(basic_istream<_CharT, _Traits>& __is,
5703            fisher_f_distribution<_RT>& __x)
5704 {
5705     typedef fisher_f_distribution<_RT> _Eng;
5706     typedef typename _Eng::result_type result_type;
5707     typedef typename _Eng::param_type param_type;
5708     __save_flags<_CharT, _Traits> __lx(__is);
5709     __is.flags(ios_base::dec | ios_base::skipws);
5710     result_type __m;
5711     result_type __n;
5712     __is >> __m >> __n;
5713     if (!__is.fail())
5714         __x.param(param_type(__m, __n));
5715     return __is;
5716 }
5717
5718 // student_t_distribution
5719
5720 template<class _RealType = double>
5721 class _LIBCPP_TYPE_VIS_ONLY student_t_distribution
5722 {
5723 public:
5724     // types
5725     typedef _RealType result_type;
5726
5727     class _LIBCPP_TYPE_VIS_ONLY param_type
5728     {
5729         result_type __n_;
5730     public:
5731         typedef student_t_distribution distribution_type;
5732
5733         _LIBCPP_INLINE_VISIBILITY
5734         explicit param_type(result_type __n = 1) : __n_(__n) {}
5735
5736         _LIBCPP_INLINE_VISIBILITY
5737         result_type n() const {return __n_;}
5738
5739         friend _LIBCPP_INLINE_VISIBILITY
5740             bool operator==(const param_type& __x, const param_type& __y)
5741             {return __x.__n_ == __y.__n_;}
5742         friend _LIBCPP_INLINE_VISIBILITY
5743             bool operator!=(const param_type& __x, const param_type& __y)
5744             {return !(__x == __y);}
5745     };
5746
5747 private:
5748     param_type __p_;
5749     normal_distribution<result_type> __nd_;
5750
5751 public:
5752     // constructor and reset functions
5753     _LIBCPP_INLINE_VISIBILITY
5754     explicit student_t_distribution(result_type __n = 1)
5755         : __p_(param_type(__n)) {}
5756     _LIBCPP_INLINE_VISIBILITY
5757     explicit student_t_distribution(const param_type& __p)
5758         : __p_(__p) {}
5759     _LIBCPP_INLINE_VISIBILITY
5760     void reset() {__nd_.reset();}
5761
5762     // generating functions
5763     template<class _URNG>
5764         _LIBCPP_INLINE_VISIBILITY
5765         result_type operator()(_URNG& __g)
5766         {return (*this)(__g, __p_);}
5767     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5768
5769     // property functions
5770     _LIBCPP_INLINE_VISIBILITY
5771     result_type n() const {return __p_.n();}
5772
5773     _LIBCPP_INLINE_VISIBILITY
5774     param_type param() const {return __p_;}
5775     _LIBCPP_INLINE_VISIBILITY
5776     void param(const param_type& __p) {__p_ = __p;}
5777
5778     _LIBCPP_INLINE_VISIBILITY
5779     result_type min() const {return -numeric_limits<result_type>::infinity();}
5780     _LIBCPP_INLINE_VISIBILITY
5781     result_type max() const {return numeric_limits<result_type>::infinity();}
5782
5783     friend _LIBCPP_INLINE_VISIBILITY
5784         bool operator==(const student_t_distribution& __x,
5785                         const student_t_distribution& __y)
5786         {return __x.__p_ == __y.__p_;}
5787     friend _LIBCPP_INLINE_VISIBILITY
5788         bool operator!=(const student_t_distribution& __x,
5789                         const student_t_distribution& __y)
5790         {return !(__x == __y);}
5791 };
5792
5793 template <class _RealType>
5794 template<class _URNG>
5795 _RealType
5796 student_t_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
5797 {
5798     gamma_distribution<result_type> __gd(__p.n() * .5, 2);
5799     return __nd_(__g) * _VSTD::sqrt(__p.n()/__gd(__g));
5800 }
5801
5802 template <class _CharT, class _Traits, class _RT>
5803 basic_ostream<_CharT, _Traits>&
5804 operator<<(basic_ostream<_CharT, _Traits>& __os,
5805            const student_t_distribution<_RT>& __x)
5806 {
5807     __save_flags<_CharT, _Traits> __lx(__os);
5808     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
5809                ios_base::scientific);
5810     __os << __x.n();
5811     return __os;
5812 }
5813
5814 template <class _CharT, class _Traits, class _RT>
5815 basic_istream<_CharT, _Traits>&
5816 operator>>(basic_istream<_CharT, _Traits>& __is,
5817            student_t_distribution<_RT>& __x)
5818 {
5819     typedef student_t_distribution<_RT> _Eng;
5820     typedef typename _Eng::result_type result_type;
5821     typedef typename _Eng::param_type param_type;
5822     __save_flags<_CharT, _Traits> __lx(__is);
5823     __is.flags(ios_base::dec | ios_base::skipws);
5824     result_type __n;
5825     __is >> __n;
5826     if (!__is.fail())
5827         __x.param(param_type(__n));
5828     return __is;
5829 }
5830
5831 // discrete_distribution
5832
5833 template<class _IntType = int>
5834 class _LIBCPP_TYPE_VIS_ONLY discrete_distribution
5835 {
5836 public:
5837     // types
5838     typedef _IntType result_type;
5839
5840     class _LIBCPP_TYPE_VIS_ONLY param_type
5841     {
5842         vector<double> __p_;
5843     public:
5844         typedef discrete_distribution distribution_type;
5845
5846         _LIBCPP_INLINE_VISIBILITY
5847         param_type() {}
5848         template<class _InputIterator>
5849             _LIBCPP_INLINE_VISIBILITY
5850             param_type(_InputIterator __f, _InputIterator __l)
5851             : __p_(__f, __l) {__init();}
5852 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5853         _LIBCPP_INLINE_VISIBILITY
5854         param_type(initializer_list<double> __wl)
5855             : __p_(__wl.begin(), __wl.end()) {__init();}
5856 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5857         template<class _UnaryOperation>
5858             param_type(size_t __nw, double __xmin, double __xmax,
5859                        _UnaryOperation __fw);
5860
5861         vector<double> probabilities() const;
5862
5863         friend _LIBCPP_INLINE_VISIBILITY
5864             bool operator==(const param_type& __x, const param_type& __y)
5865             {return __x.__p_ == __y.__p_;}
5866         friend _LIBCPP_INLINE_VISIBILITY
5867             bool operator!=(const param_type& __x, const param_type& __y)
5868             {return !(__x == __y);}
5869
5870     private:
5871         void __init();
5872
5873         friend class discrete_distribution;
5874
5875         template <class _CharT, class _Traits, class _IT>
5876         friend
5877         basic_ostream<_CharT, _Traits>&
5878         operator<<(basic_ostream<_CharT, _Traits>& __os,
5879                    const discrete_distribution<_IT>& __x);
5880
5881         template <class _CharT, class _Traits, class _IT>
5882         friend
5883         basic_istream<_CharT, _Traits>&
5884         operator>>(basic_istream<_CharT, _Traits>& __is,
5885                    discrete_distribution<_IT>& __x);
5886     };
5887
5888 private:
5889     param_type __p_;
5890
5891 public:
5892     // constructor and reset functions
5893     _LIBCPP_INLINE_VISIBILITY
5894     discrete_distribution() {}
5895     template<class _InputIterator>
5896         _LIBCPP_INLINE_VISIBILITY
5897         discrete_distribution(_InputIterator __f, _InputIterator __l)
5898             : __p_(__f, __l) {}
5899 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5900     _LIBCPP_INLINE_VISIBILITY
5901     discrete_distribution(initializer_list<double> __wl)
5902         : __p_(__wl) {}
5903 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
5904     template<class _UnaryOperation>
5905         _LIBCPP_INLINE_VISIBILITY
5906         discrete_distribution(size_t __nw, double __xmin, double __xmax,
5907                               _UnaryOperation __fw)
5908         : __p_(__nw, __xmin, __xmax, __fw) {}
5909     _LIBCPP_INLINE_VISIBILITY
5910     explicit discrete_distribution(const param_type& __p)
5911         : __p_(__p) {}
5912     _LIBCPP_INLINE_VISIBILITY
5913     void reset() {}
5914
5915     // generating functions
5916     template<class _URNG>
5917         _LIBCPP_INLINE_VISIBILITY
5918         result_type operator()(_URNG& __g)
5919         {return (*this)(__g, __p_);}
5920     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
5921
5922     // property functions
5923     _LIBCPP_INLINE_VISIBILITY
5924     vector<double> probabilities() const {return __p_.probabilities();}
5925
5926     _LIBCPP_INLINE_VISIBILITY
5927     param_type param() const {return __p_;}
5928     _LIBCPP_INLINE_VISIBILITY
5929     void param(const param_type& __p) {__p_ = __p;}
5930
5931     _LIBCPP_INLINE_VISIBILITY
5932     result_type min() const {return 0;}
5933     _LIBCPP_INLINE_VISIBILITY
5934     result_type max() const {return __p_.__p_.size();}
5935
5936     friend _LIBCPP_INLINE_VISIBILITY
5937         bool operator==(const discrete_distribution& __x,
5938                         const discrete_distribution& __y)
5939         {return __x.__p_ == __y.__p_;}
5940     friend _LIBCPP_INLINE_VISIBILITY
5941         bool operator!=(const discrete_distribution& __x,
5942                         const discrete_distribution& __y)
5943         {return !(__x == __y);}
5944
5945     template <class _CharT, class _Traits, class _IT>
5946     friend
5947     basic_ostream<_CharT, _Traits>&
5948     operator<<(basic_ostream<_CharT, _Traits>& __os,
5949                const discrete_distribution<_IT>& __x);
5950
5951     template <class _CharT, class _Traits, class _IT>
5952     friend
5953     basic_istream<_CharT, _Traits>&
5954     operator>>(basic_istream<_CharT, _Traits>& __is,
5955                discrete_distribution<_IT>& __x);
5956 };
5957
5958 template<class _IntType>
5959 template<class _UnaryOperation>
5960 discrete_distribution<_IntType>::param_type::param_type(size_t __nw,
5961                                                         double __xmin,
5962                                                         double __xmax,
5963                                                         _UnaryOperation __fw)
5964 {
5965     if (__nw > 1)
5966     {
5967         __p_.reserve(__nw - 1);
5968         double __d = (__xmax - __xmin) / __nw;
5969         double __d2 = __d / 2;
5970         for (size_t __k = 0; __k < __nw; ++__k)
5971             __p_.push_back(__fw(__xmin + __k * __d + __d2));
5972         __init();
5973     }
5974 }
5975
5976 template<class _IntType>
5977 void
5978 discrete_distribution<_IntType>::param_type::__init()
5979 {
5980     if (!__p_.empty())
5981     {
5982         if (__p_.size() > 1)
5983         {
5984             double __s = _VSTD::accumulate(__p_.begin(), __p_.end(), 0.0);
5985             for (_VSTD::vector<double>::iterator __i = __p_.begin(), __e = __p_.end();
5986                                                                        __i < __e; ++__i)
5987                 *__i /= __s;
5988             vector<double> __t(__p_.size() - 1);
5989             _VSTD::partial_sum(__p_.begin(), __p_.end() - 1, __t.begin());
5990             swap(__p_, __t);
5991         }
5992         else
5993         {
5994             __p_.clear();
5995             __p_.shrink_to_fit();
5996         }
5997     }
5998 }
5999
6000 template<class _IntType>
6001 vector<double>
6002 discrete_distribution<_IntType>::param_type::probabilities() const
6003 {
6004     size_t __n = __p_.size();
6005     _VSTD::vector<double> __p(__n+1);
6006     _VSTD::adjacent_difference(__p_.begin(), __p_.end(), __p.begin());
6007     if (__n > 0)
6008         __p[__n] = 1 - __p_[__n-1];
6009     else
6010         __p[0] = 1;
6011     return __p;
6012 }
6013
6014 template<class _IntType>
6015 template<class _URNG>
6016 _IntType
6017 discrete_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
6018 {
6019     uniform_real_distribution<double> __gen;
6020     return static_cast<_IntType>(
6021            _VSTD::upper_bound(__p.__p_.begin(), __p.__p_.end(), __gen(__g)) -
6022                                                               __p.__p_.begin());
6023 }
6024
6025 template <class _CharT, class _Traits, class _IT>
6026 basic_ostream<_CharT, _Traits>&
6027 operator<<(basic_ostream<_CharT, _Traits>& __os,
6028            const discrete_distribution<_IT>& __x)
6029 {
6030     __save_flags<_CharT, _Traits> __lx(__os);
6031     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6032                ios_base::scientific);
6033     _CharT __sp = __os.widen(' ');
6034     __os.fill(__sp);
6035     size_t __n = __x.__p_.__p_.size();
6036     __os << __n;
6037     for (size_t __i = 0; __i < __n; ++__i)
6038         __os << __sp << __x.__p_.__p_[__i];
6039     return __os;
6040 }
6041
6042 template <class _CharT, class _Traits, class _IT>
6043 basic_istream<_CharT, _Traits>&
6044 operator>>(basic_istream<_CharT, _Traits>& __is,
6045            discrete_distribution<_IT>& __x)
6046 {
6047     __save_flags<_CharT, _Traits> __lx(__is);
6048     __is.flags(ios_base::dec | ios_base::skipws);
6049     size_t __n;
6050     __is >> __n;
6051     vector<double> __p(__n);
6052     for (size_t __i = 0; __i < __n; ++__i)
6053         __is >> __p[__i];
6054     if (!__is.fail())
6055         swap(__x.__p_.__p_, __p);
6056     return __is;
6057 }
6058
6059 // piecewise_constant_distribution
6060
6061 template<class _RealType = double>
6062 class _LIBCPP_TYPE_VIS_ONLY piecewise_constant_distribution
6063 {
6064 public:
6065     // types
6066     typedef _RealType result_type;
6067
6068     class _LIBCPP_TYPE_VIS_ONLY param_type
6069     {
6070         vector<result_type> __b_;
6071         vector<result_type> __densities_;
6072         vector<result_type> __areas_;
6073     public:
6074         typedef piecewise_constant_distribution distribution_type;
6075
6076         param_type();
6077         template<class _InputIteratorB, class _InputIteratorW>
6078             param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6079                        _InputIteratorW __fW);
6080 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6081         template<class _UnaryOperation>
6082             param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6083 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6084         template<class _UnaryOperation>
6085             param_type(size_t __nw, result_type __xmin, result_type __xmax,
6086                        _UnaryOperation __fw);
6087         param_type & operator=(const param_type& __rhs);
6088
6089         _LIBCPP_INLINE_VISIBILITY
6090         vector<result_type> intervals() const {return __b_;}
6091         _LIBCPP_INLINE_VISIBILITY
6092         vector<result_type> densities() const {return __densities_;}
6093
6094         friend _LIBCPP_INLINE_VISIBILITY
6095             bool operator==(const param_type& __x, const param_type& __y)
6096             {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6097         friend _LIBCPP_INLINE_VISIBILITY
6098             bool operator!=(const param_type& __x, const param_type& __y)
6099             {return !(__x == __y);}
6100
6101     private:
6102         void __init();
6103
6104         friend class piecewise_constant_distribution;
6105
6106         template <class _CharT, class _Traits, class _RT>
6107         friend
6108         basic_ostream<_CharT, _Traits>&
6109         operator<<(basic_ostream<_CharT, _Traits>& __os,
6110                    const piecewise_constant_distribution<_RT>& __x);
6111
6112         template <class _CharT, class _Traits, class _RT>
6113         friend
6114         basic_istream<_CharT, _Traits>&
6115         operator>>(basic_istream<_CharT, _Traits>& __is,
6116                    piecewise_constant_distribution<_RT>& __x);
6117     };
6118
6119 private:
6120     param_type __p_;
6121
6122 public:
6123     // constructor and reset functions
6124     _LIBCPP_INLINE_VISIBILITY
6125     piecewise_constant_distribution() {}
6126     template<class _InputIteratorB, class _InputIteratorW>
6127         _LIBCPP_INLINE_VISIBILITY
6128         piecewise_constant_distribution(_InputIteratorB __fB,
6129                                         _InputIteratorB __lB,
6130                                         _InputIteratorW __fW)
6131         : __p_(__fB, __lB, __fW) {}
6132
6133 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6134     template<class _UnaryOperation>
6135         _LIBCPP_INLINE_VISIBILITY
6136         piecewise_constant_distribution(initializer_list<result_type> __bl,
6137                                         _UnaryOperation __fw)
6138         : __p_(__bl, __fw) {}
6139 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6140
6141     template<class _UnaryOperation>
6142         _LIBCPP_INLINE_VISIBILITY
6143         piecewise_constant_distribution(size_t __nw, result_type __xmin,
6144                                         result_type __xmax, _UnaryOperation __fw)
6145         : __p_(__nw, __xmin, __xmax, __fw) {}
6146
6147     _LIBCPP_INLINE_VISIBILITY
6148     explicit piecewise_constant_distribution(const param_type& __p)
6149         : __p_(__p) {}
6150
6151     _LIBCPP_INLINE_VISIBILITY
6152     void reset() {}
6153
6154     // generating functions
6155     template<class _URNG>
6156         _LIBCPP_INLINE_VISIBILITY
6157         result_type operator()(_URNG& __g)
6158         {return (*this)(__g, __p_);}
6159     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6160
6161     // property functions
6162     _LIBCPP_INLINE_VISIBILITY
6163     vector<result_type> intervals() const {return __p_.intervals();}
6164     _LIBCPP_INLINE_VISIBILITY
6165     vector<result_type> densities() const {return __p_.densities();}
6166
6167     _LIBCPP_INLINE_VISIBILITY
6168     param_type param() const {return __p_;}
6169     _LIBCPP_INLINE_VISIBILITY
6170     void param(const param_type& __p) {__p_ = __p;}
6171
6172     _LIBCPP_INLINE_VISIBILITY
6173     result_type min() const {return __p_.__b_.front();}
6174     _LIBCPP_INLINE_VISIBILITY
6175     result_type max() const {return __p_.__b_.back();}
6176
6177     friend _LIBCPP_INLINE_VISIBILITY
6178         bool operator==(const piecewise_constant_distribution& __x,
6179                         const piecewise_constant_distribution& __y)
6180         {return __x.__p_ == __y.__p_;}
6181     friend _LIBCPP_INLINE_VISIBILITY
6182         bool operator!=(const piecewise_constant_distribution& __x,
6183                            const piecewise_constant_distribution& __y)
6184         {return !(__x == __y);}
6185
6186     template <class _CharT, class _Traits, class _RT>
6187     friend
6188     basic_ostream<_CharT, _Traits>&
6189     operator<<(basic_ostream<_CharT, _Traits>& __os,
6190                const piecewise_constant_distribution<_RT>& __x);
6191
6192     template <class _CharT, class _Traits, class _RT>
6193     friend
6194     basic_istream<_CharT, _Traits>&
6195     operator>>(basic_istream<_CharT, _Traits>& __is,
6196                piecewise_constant_distribution<_RT>& __x);
6197 };
6198
6199 template<class _RealType>
6200 typename piecewise_constant_distribution<_RealType>::param_type &
6201 piecewise_constant_distribution<_RealType>::param_type::operator=
6202                                                        (const param_type& __rhs)
6203 {
6204 //  These can throw
6205     __b_.reserve        (__rhs.__b_.size ());
6206     __densities_.reserve(__rhs.__densities_.size());
6207     __areas_.reserve    (__rhs.__areas_.size());
6208
6209 //  These can not throw
6210     __b_         = __rhs.__b_;
6211     __densities_ = __rhs.__densities_;
6212     __areas_     =  __rhs.__areas_;
6213     return *this;
6214 }
6215
6216 template<class _RealType>
6217 void
6218 piecewise_constant_distribution<_RealType>::param_type::__init()
6219 {
6220     // __densities_ contains non-normalized areas
6221     result_type __total_area = _VSTD::accumulate(__densities_.begin(),
6222                                                 __densities_.end(),
6223                                                 result_type());
6224     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6225         __densities_[__i] /= __total_area;
6226     // __densities_ contains normalized areas
6227     __areas_.assign(__densities_.size(), result_type());
6228     _VSTD::partial_sum(__densities_.begin(), __densities_.end() - 1,
6229                                                           __areas_.begin() + 1);
6230     // __areas_ contains partial sums of normalized areas: [0, __densities_ - 1]
6231     __densities_.back() = 1 - __areas_.back();  // correct round off error
6232     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6233         __densities_[__i] /= (__b_[__i+1] - __b_[__i]);
6234     // __densities_ now contains __densities_
6235 }
6236
6237 template<class _RealType>
6238 piecewise_constant_distribution<_RealType>::param_type::param_type()
6239     : __b_(2),
6240       __densities_(1, 1.0),
6241       __areas_(1, 0.0)
6242 {
6243     __b_[1] = 1;
6244 }
6245
6246 template<class _RealType>
6247 template<class _InputIteratorB, class _InputIteratorW>
6248 piecewise_constant_distribution<_RealType>::param_type::param_type(
6249         _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6250     : __b_(__fB, __lB)
6251 {
6252     if (__b_.size() < 2)
6253     {
6254         __b_.resize(2);
6255         __b_[0] = 0;
6256         __b_[1] = 1;
6257         __densities_.assign(1, 1.0);
6258         __areas_.assign(1, 0.0);
6259     }
6260     else
6261     {
6262         __densities_.reserve(__b_.size() - 1);
6263         for (size_t __i = 0; __i < __b_.size() - 1; ++__i, ++__fW)
6264             __densities_.push_back(*__fW);
6265         __init();
6266     }
6267 }
6268
6269 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6270
6271 template<class _RealType>
6272 template<class _UnaryOperation>
6273 piecewise_constant_distribution<_RealType>::param_type::param_type(
6274         initializer_list<result_type> __bl, _UnaryOperation __fw)
6275     : __b_(__bl.begin(), __bl.end())
6276 {
6277     if (__b_.size() < 2)
6278     {
6279         __b_.resize(2);
6280         __b_[0] = 0;
6281         __b_[1] = 1;
6282         __densities_.assign(1, 1.0);
6283         __areas_.assign(1, 0.0);
6284     }
6285     else
6286     {
6287         __densities_.reserve(__b_.size() - 1);
6288         for (size_t __i = 0; __i < __b_.size() - 1; ++__i)
6289             __densities_.push_back(__fw((__b_[__i+1] + __b_[__i])*.5));
6290         __init();
6291     }
6292 }
6293
6294 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6295
6296 template<class _RealType>
6297 template<class _UnaryOperation>
6298 piecewise_constant_distribution<_RealType>::param_type::param_type(
6299         size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6300     : __b_(__nw == 0 ? 2 : __nw + 1)
6301 {
6302     size_t __n = __b_.size() - 1;
6303     result_type __d = (__xmax - __xmin) / __n;
6304     __densities_.reserve(__n);
6305     for (size_t __i = 0; __i < __n; ++__i)
6306     {
6307         __b_[__i] = __xmin + __i * __d;
6308         __densities_.push_back(__fw(__b_[__i] + __d*.5));
6309     }
6310     __b_[__n] = __xmax;
6311     __init();
6312 }
6313
6314 template<class _RealType>
6315 template<class _URNG>
6316 _RealType
6317 piecewise_constant_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6318 {
6319     typedef uniform_real_distribution<result_type> _Gen;
6320     result_type __u = _Gen()(__g);
6321     ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6322                                       __u) - __p.__areas_.begin() - 1;
6323     return (__u - __p.__areas_[__k]) / __p.__densities_[__k] + __p.__b_[__k];
6324 }
6325
6326 template <class _CharT, class _Traits, class _RT>
6327 basic_ostream<_CharT, _Traits>&
6328 operator<<(basic_ostream<_CharT, _Traits>& __os,
6329            const piecewise_constant_distribution<_RT>& __x)
6330 {
6331     __save_flags<_CharT, _Traits> __lx(__os);
6332     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6333                ios_base::scientific);
6334     _CharT __sp = __os.widen(' ');
6335     __os.fill(__sp);
6336     size_t __n = __x.__p_.__b_.size();
6337     __os << __n;
6338     for (size_t __i = 0; __i < __n; ++__i)
6339         __os << __sp << __x.__p_.__b_[__i];
6340     __n = __x.__p_.__densities_.size();
6341     __os << __sp << __n;
6342     for (size_t __i = 0; __i < __n; ++__i)
6343         __os << __sp << __x.__p_.__densities_[__i];
6344     __n = __x.__p_.__areas_.size();
6345     __os << __sp << __n;
6346     for (size_t __i = 0; __i < __n; ++__i)
6347         __os << __sp << __x.__p_.__areas_[__i];
6348     return __os;
6349 }
6350
6351 template <class _CharT, class _Traits, class _RT>
6352 basic_istream<_CharT, _Traits>&
6353 operator>>(basic_istream<_CharT, _Traits>& __is,
6354            piecewise_constant_distribution<_RT>& __x)
6355 {
6356     typedef piecewise_constant_distribution<_RT> _Eng;
6357     typedef typename _Eng::result_type result_type;
6358     __save_flags<_CharT, _Traits> __lx(__is);
6359     __is.flags(ios_base::dec | ios_base::skipws);
6360     size_t __n;
6361     __is >> __n;
6362     vector<result_type> __b(__n);
6363     for (size_t __i = 0; __i < __n; ++__i)
6364         __is >> __b[__i];
6365     __is >> __n;
6366     vector<result_type> __densities(__n);
6367     for (size_t __i = 0; __i < __n; ++__i)
6368         __is >> __densities[__i];
6369     __is >> __n;
6370     vector<result_type> __areas(__n);
6371     for (size_t __i = 0; __i < __n; ++__i)
6372         __is >> __areas[__i];
6373     if (!__is.fail())
6374     {
6375         swap(__x.__p_.__b_, __b);
6376         swap(__x.__p_.__densities_, __densities);
6377         swap(__x.__p_.__areas_, __areas);
6378     }
6379     return __is;
6380 }
6381
6382 // piecewise_linear_distribution
6383
6384 template<class _RealType = double>
6385 class _LIBCPP_TYPE_VIS_ONLY piecewise_linear_distribution
6386 {
6387 public:
6388     // types
6389     typedef _RealType result_type;
6390
6391     class _LIBCPP_TYPE_VIS_ONLY param_type
6392     {
6393         vector<result_type> __b_;
6394         vector<result_type> __densities_;
6395         vector<result_type> __areas_;
6396     public:
6397         typedef piecewise_linear_distribution distribution_type;
6398
6399         param_type();
6400         template<class _InputIteratorB, class _InputIteratorW>
6401             param_type(_InputIteratorB __fB, _InputIteratorB __lB,
6402                        _InputIteratorW __fW);
6403 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6404         template<class _UnaryOperation>
6405             param_type(initializer_list<result_type> __bl, _UnaryOperation __fw);
6406 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6407         template<class _UnaryOperation>
6408             param_type(size_t __nw, result_type __xmin, result_type __xmax,
6409                        _UnaryOperation __fw);
6410         param_type & operator=(const param_type& __rhs);
6411
6412         _LIBCPP_INLINE_VISIBILITY
6413         vector<result_type> intervals() const {return __b_;}
6414         _LIBCPP_INLINE_VISIBILITY
6415         vector<result_type> densities() const {return __densities_;}
6416
6417         friend _LIBCPP_INLINE_VISIBILITY
6418             bool operator==(const param_type& __x, const param_type& __y)
6419             {return __x.__densities_ == __y.__densities_ && __x.__b_ == __y.__b_;}
6420         friend _LIBCPP_INLINE_VISIBILITY
6421             bool operator!=(const param_type& __x, const param_type& __y)
6422             {return !(__x == __y);}
6423
6424     private:
6425         void __init();
6426
6427         friend class piecewise_linear_distribution;
6428
6429         template <class _CharT, class _Traits, class _RT>
6430         friend
6431         basic_ostream<_CharT, _Traits>&
6432         operator<<(basic_ostream<_CharT, _Traits>& __os,
6433                    const piecewise_linear_distribution<_RT>& __x);
6434
6435         template <class _CharT, class _Traits, class _RT>
6436         friend
6437         basic_istream<_CharT, _Traits>&
6438         operator>>(basic_istream<_CharT, _Traits>& __is,
6439                    piecewise_linear_distribution<_RT>& __x);
6440     };
6441
6442 private:
6443     param_type __p_;
6444
6445 public:
6446     // constructor and reset functions
6447     _LIBCPP_INLINE_VISIBILITY
6448     piecewise_linear_distribution() {}
6449     template<class _InputIteratorB, class _InputIteratorW>
6450         _LIBCPP_INLINE_VISIBILITY
6451         piecewise_linear_distribution(_InputIteratorB __fB,
6452                                       _InputIteratorB __lB,
6453                                       _InputIteratorW __fW)
6454         : __p_(__fB, __lB, __fW) {}
6455
6456 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6457     template<class _UnaryOperation>
6458         _LIBCPP_INLINE_VISIBILITY
6459         piecewise_linear_distribution(initializer_list<result_type> __bl,
6460                                       _UnaryOperation __fw)
6461         : __p_(__bl, __fw) {}
6462 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6463
6464     template<class _UnaryOperation>
6465         _LIBCPP_INLINE_VISIBILITY
6466         piecewise_linear_distribution(size_t __nw, result_type __xmin,
6467                                       result_type __xmax, _UnaryOperation __fw)
6468         : __p_(__nw, __xmin, __xmax, __fw) {}
6469
6470     _LIBCPP_INLINE_VISIBILITY
6471     explicit piecewise_linear_distribution(const param_type& __p)
6472         : __p_(__p) {}
6473
6474     _LIBCPP_INLINE_VISIBILITY
6475     void reset() {}
6476
6477     // generating functions
6478     template<class _URNG>
6479         _LIBCPP_INLINE_VISIBILITY
6480         result_type operator()(_URNG& __g)
6481         {return (*this)(__g, __p_);}
6482     template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
6483
6484     // property functions
6485     _LIBCPP_INLINE_VISIBILITY
6486     vector<result_type> intervals() const {return __p_.intervals();}
6487     _LIBCPP_INLINE_VISIBILITY
6488     vector<result_type> densities() const {return __p_.densities();}
6489
6490     _LIBCPP_INLINE_VISIBILITY
6491     param_type param() const {return __p_;}
6492     _LIBCPP_INLINE_VISIBILITY
6493     void param(const param_type& __p) {__p_ = __p;}
6494
6495     _LIBCPP_INLINE_VISIBILITY
6496     result_type min() const {return __p_.__b_.front();}
6497     _LIBCPP_INLINE_VISIBILITY
6498     result_type max() const {return __p_.__b_.back();}
6499
6500     friend _LIBCPP_INLINE_VISIBILITY
6501         bool operator==(const piecewise_linear_distribution& __x,
6502                         const piecewise_linear_distribution& __y)
6503         {return __x.__p_ == __y.__p_;}
6504     friend _LIBCPP_INLINE_VISIBILITY
6505         bool operator!=(const piecewise_linear_distribution& __x,
6506                         const piecewise_linear_distribution& __y)
6507         {return !(__x == __y);}
6508
6509     template <class _CharT, class _Traits, class _RT>
6510     friend
6511     basic_ostream<_CharT, _Traits>&
6512     operator<<(basic_ostream<_CharT, _Traits>& __os,
6513                const piecewise_linear_distribution<_RT>& __x);
6514
6515     template <class _CharT, class _Traits, class _RT>
6516     friend
6517     basic_istream<_CharT, _Traits>&
6518     operator>>(basic_istream<_CharT, _Traits>& __is,
6519                piecewise_linear_distribution<_RT>& __x);
6520 };
6521
6522 template<class _RealType>
6523 typename piecewise_linear_distribution<_RealType>::param_type &
6524 piecewise_linear_distribution<_RealType>::param_type::operator=
6525                                                        (const param_type& __rhs)
6526 {
6527 //  These can throw
6528     __b_.reserve        (__rhs.__b_.size ());
6529     __densities_.reserve(__rhs.__densities_.size());
6530     __areas_.reserve    (__rhs.__areas_.size());
6531
6532 //  These can not throw
6533     __b_         = __rhs.__b_;
6534     __densities_ = __rhs.__densities_;
6535     __areas_     =  __rhs.__areas_;
6536     return *this;
6537 }
6538
6539
6540 template<class _RealType>
6541 void
6542 piecewise_linear_distribution<_RealType>::param_type::__init()
6543 {
6544     __areas_.assign(__densities_.size() - 1, result_type());
6545     result_type _Sp = 0;
6546     for (size_t __i = 0; __i < __areas_.size(); ++__i)
6547     {
6548         __areas_[__i] = (__densities_[__i+1] + __densities_[__i]) *
6549                         (__b_[__i+1] - __b_[__i]) * .5;
6550         _Sp += __areas_[__i];
6551     }
6552     for (size_t __i = __areas_.size(); __i > 1;)
6553     {
6554         --__i;
6555         __areas_[__i] = __areas_[__i-1] / _Sp;
6556     }
6557     __areas_[0] = 0;
6558     for (size_t __i = 1; __i < __areas_.size(); ++__i)
6559         __areas_[__i] += __areas_[__i-1];
6560     for (size_t __i = 0; __i < __densities_.size(); ++__i)
6561         __densities_[__i] /= _Sp;
6562 }
6563
6564 template<class _RealType>
6565 piecewise_linear_distribution<_RealType>::param_type::param_type()
6566     : __b_(2),
6567       __densities_(2, 1.0),
6568       __areas_(1, 0.0)
6569 {
6570     __b_[1] = 1;
6571 }
6572
6573 template<class _RealType>
6574 template<class _InputIteratorB, class _InputIteratorW>
6575 piecewise_linear_distribution<_RealType>::param_type::param_type(
6576         _InputIteratorB __fB, _InputIteratorB __lB, _InputIteratorW __fW)
6577     : __b_(__fB, __lB)
6578 {
6579     if (__b_.size() < 2)
6580     {
6581         __b_.resize(2);
6582         __b_[0] = 0;
6583         __b_[1] = 1;
6584         __densities_.assign(2, 1.0);
6585         __areas_.assign(1, 0.0);
6586     }
6587     else
6588     {
6589         __densities_.reserve(__b_.size());
6590         for (size_t __i = 0; __i < __b_.size(); ++__i, ++__fW)
6591             __densities_.push_back(*__fW);
6592         __init();
6593     }
6594 }
6595
6596 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6597
6598 template<class _RealType>
6599 template<class _UnaryOperation>
6600 piecewise_linear_distribution<_RealType>::param_type::param_type(
6601         initializer_list<result_type> __bl, _UnaryOperation __fw)
6602     : __b_(__bl.begin(), __bl.end())
6603 {
6604     if (__b_.size() < 2)
6605     {
6606         __b_.resize(2);
6607         __b_[0] = 0;
6608         __b_[1] = 1;
6609         __densities_.assign(2, 1.0);
6610         __areas_.assign(1, 0.0);
6611     }
6612     else
6613     {
6614         __densities_.reserve(__b_.size());
6615         for (size_t __i = 0; __i < __b_.size(); ++__i)
6616             __densities_.push_back(__fw(__b_[__i]));
6617         __init();
6618     }
6619 }
6620
6621 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
6622
6623 template<class _RealType>
6624 template<class _UnaryOperation>
6625 piecewise_linear_distribution<_RealType>::param_type::param_type(
6626         size_t __nw, result_type __xmin, result_type __xmax, _UnaryOperation __fw)
6627     : __b_(__nw == 0 ? 2 : __nw + 1)
6628 {
6629     size_t __n = __b_.size() - 1;
6630     result_type __d = (__xmax - __xmin) / __n;
6631     __densities_.reserve(__b_.size());
6632     for (size_t __i = 0; __i < __n; ++__i)
6633     {
6634         __b_[__i] = __xmin + __i * __d;
6635         __densities_.push_back(__fw(__b_[__i]));
6636     }
6637     __b_[__n] = __xmax;
6638     __densities_.push_back(__fw(__b_[__n]));
6639     __init();
6640 }
6641
6642 template<class _RealType>
6643 template<class _URNG>
6644 _RealType
6645 piecewise_linear_distribution<_RealType>::operator()(_URNG& __g, const param_type& __p)
6646 {
6647     typedef uniform_real_distribution<result_type> _Gen;
6648     result_type __u = _Gen()(__g);
6649     ptrdiff_t __k = _VSTD::upper_bound(__p.__areas_.begin(), __p.__areas_.end(),
6650                                       __u) - __p.__areas_.begin() - 1;
6651     __u -= __p.__areas_[__k];
6652     const result_type __dk = __p.__densities_[__k];
6653     const result_type __dk1 = __p.__densities_[__k+1];
6654     const result_type __deltad = __dk1 - __dk;
6655     const result_type __bk = __p.__b_[__k];
6656     if (__deltad == 0)
6657         return __u / __dk + __bk;
6658     const result_type __bk1 = __p.__b_[__k+1];
6659     const result_type __deltab = __bk1 - __bk;
6660     return (__bk * __dk1 - __bk1 * __dk +
6661         _VSTD::sqrt(__deltab * (__deltab * __dk * __dk + 2 * __deltad * __u))) /
6662         __deltad;
6663 }
6664
6665 template <class _CharT, class _Traits, class _RT>
6666 basic_ostream<_CharT, _Traits>&
6667 operator<<(basic_ostream<_CharT, _Traits>& __os,
6668            const piecewise_linear_distribution<_RT>& __x)
6669 {
6670     __save_flags<_CharT, _Traits> __lx(__os);
6671     __os.flags(ios_base::dec | ios_base::left | ios_base::fixed |
6672                ios_base::scientific);
6673     _CharT __sp = __os.widen(' ');
6674     __os.fill(__sp);
6675     size_t __n = __x.__p_.__b_.size();
6676     __os << __n;
6677     for (size_t __i = 0; __i < __n; ++__i)
6678         __os << __sp << __x.__p_.__b_[__i];
6679     __n = __x.__p_.__densities_.size();
6680     __os << __sp << __n;
6681     for (size_t __i = 0; __i < __n; ++__i)
6682         __os << __sp << __x.__p_.__densities_[__i];
6683     __n = __x.__p_.__areas_.size();
6684     __os << __sp << __n;
6685     for (size_t __i = 0; __i < __n; ++__i)
6686         __os << __sp << __x.__p_.__areas_[__i];
6687     return __os;
6688 }
6689
6690 template <class _CharT, class _Traits, class _RT>
6691 basic_istream<_CharT, _Traits>&
6692 operator>>(basic_istream<_CharT, _Traits>& __is,
6693            piecewise_linear_distribution<_RT>& __x)
6694 {
6695     typedef piecewise_linear_distribution<_RT> _Eng;
6696     typedef typename _Eng::result_type result_type;
6697     __save_flags<_CharT, _Traits> __lx(__is);
6698     __is.flags(ios_base::dec | ios_base::skipws);
6699     size_t __n;
6700     __is >> __n;
6701     vector<result_type> __b(__n);
6702     for (size_t __i = 0; __i < __n; ++__i)
6703         __is >> __b[__i];
6704     __is >> __n;
6705     vector<result_type> __densities(__n);
6706     for (size_t __i = 0; __i < __n; ++__i)
6707         __is >> __densities[__i];
6708     __is >> __n;
6709     vector<result_type> __areas(__n);
6710     for (size_t __i = 0; __i < __n; ++__i)
6711         __is >> __areas[__i];
6712     if (!__is.fail())
6713     {
6714         swap(__x.__p_.__b_, __b);
6715         swap(__x.__p_.__densities_, __densities);
6716         swap(__x.__p_.__areas_, __areas);
6717     }
6718     return __is;
6719 }
6720
6721 _LIBCPP_END_NAMESPACE_STD
6722
6723 #endif  // _LIBCPP_RANDOM