contrib/libc++/include/random

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