contrib/llvm-project/libcxx/include/random

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