contrib/libc++/include/random

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