contrib/libc++/include/random

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