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