headers/libs/libc++/random

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