libstdc++-v3/include/bits/random.h

   1 // random number generation -*- C++ -*-
   2
   3 // Copyright (C) 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /**
  26  * @file bits/random.h
  27  *  This is an internal header file, included by other library headers.
  28  *  You should not attempt to use it directly.
  29  */
  30
  31 #include <vector>
  32
  33 namespace std
  34 {
  35   // [26.4] Random number generation
  36
  37   /**
  38    * @addtogroup std_random Random Number Generation
  39    * A facility for generating random numbers on selected distributions.
  40    * @{
  41    */
  42
  43   /**
  44    * @brief A function template for converting the output of a (integral)
  45    * uniform random number generator to a floatng point result in the range
  46    * [0-1).
  47    */
  48   template<typename _RealType, size_t __bits,
  49            typename _UniformRandomNumberGenerator>
  50     _RealType
  51     generate_canonical(_UniformRandomNumberGenerator& __g);
  52
  53   class seed_seq;
  54
  55   /*
  56    * Implementation-space details.
  57    */
  58   namespace __detail
  59   {
  60     template<typename _UIntType, size_t __w,
  61              bool = __w < static_cast<size_t>
  62                           (std::numeric_limits<_UIntType>::digits)>
  63       struct _Shift
  64       { static const _UIntType __value = 0; };
  65
  66     template<typename _UIntType, size_t __w>
  67       struct _Shift<_UIntType, __w, true>
  68       { static const _UIntType __value = _UIntType(1) << __w; };
  69
  70     template<typename _Tp, _Tp __m, _Tp __a, _Tp __c, bool>
  71       struct _Mod;
  72
  73     // Dispatch based on modulus value to prevent divide-by-zero compile-time
  74     // errors when m == 0.
  75     template<typename _Tp, _Tp __m, _Tp __a = 1, _Tp __c = 0>
  76       inline _Tp
  77       __mod(_Tp __x)
  78       { return _Mod<_Tp, __m, __a, __c, __m == 0>::__calc(__x); }
  79
  80     /*
  81      * An adaptor class for converting the output of any Generator into
  82      * the input for a specific Distribution.
  83      */
  84     template<typename _Engine, typename _DInputType>
  85       struct _Adaptor
  86       {
  87
  88       public:
  89         _Adaptor(_Engine& __g)
  90         : _M_g(__g) { }
  91
  92         _DInputType
  93         min() const
  94         { return _DInputType(0); }
  95
  96         _DInputType
  97         max() const
  98         { return _DInputType(1); }
  99
 100         /*
 101          * Converts a value generated by the adapted random number generator
 102          * into a value in the input domain for the dependent random number
 103          * distribution.
 104          */
 105         _DInputType
 106         operator()()
 107         {
 108           return std::generate_canonical<_DInputType,
 109                                     std::numeric_limits<_DInputType>::digits,
 110                                     _Engine>(_M_g);
 111         }
 112
 113       private:
 114         _Engine& _M_g;
 115       };
 116   } // namespace __detail
 117
 118   /**
 119    * @addtogroup std_random_generators Random Number Generators
 120    * @ingroup std_random
 121    *
 122    * These classes define objects which provide random or pseudorandom
 123    * numbers, either from a discrete or a continuous interval.  The
 124    * random number generator supplied as a part of this library are
 125    * all uniform random number generators which provide a sequence of
 126    * random number uniformly distributed over their range.
 127    *
 128    * A number generator is a function object with an operator() that
 129    * takes zero arguments and returns a number.
 130    *
 131    * A compliant random number generator must satisfy the following
 132    * requirements.  <table border=1 cellpadding=10 cellspacing=0>
 133    * <caption align=top>Random Number Generator Requirements</caption>
 134    * <tr><td>To be documented.</td></tr> </table>
 135    *
 136    * @{
 137    */
 138
 139   /**
 140    * @brief A model of a linear congruential random number generator.
 141    *
 142    * A random number generator that produces pseudorandom numbers using the
 143    * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
 144    *
 145    * The template parameter @p _UIntType must be an unsigned integral type
 146    * large enough to store values up to (__m-1). If the template parameter
 147    * @p __m is 0, the modulus @p __m used is
 148    * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
 149    * parameters @p __a and @p __c must be less than @p __m.
 150    *
 151    * The size of the state is @f$ 1 @f$.
 152    */
 153   template<typename _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
 154     class linear_congruential_engine
 155     {
 156       static_assert(std::is_unsigned<_UIntType>::value, "template argument "
 157                     "_UIntType not an unsigned integral type");
 158       static_assert(__m == 0u || (__a < __m && __c < __m),
 159                     "template argument __m out of bounds");
 160
 161     public:
 162       /** The type of the generated random value. */
 163       typedef _UIntType result_type;
 164
 165       /** The multiplier. */
 166       static const result_type multiplier   = __a;
 167       /** An increment. */
 168       static const result_type increment    = __c;
 169       /** The modulus. */
 170       static const result_type modulus      = __m;
 171       static const result_type default_seed = 1u;
 172
 173       /**
 174        * @brief Constructs a %linear_congruential_engine random number
 175        *        generator engine with seed @p __s.  The default seed value
 176        *        is 1.
 177        *
 178        * @param __s The initial seed value.
 179        */
 180       explicit
 181       linear_congruential_engine(result_type __s = default_seed)
 182       { this->seed(__s); }
 183
 184       /**
 185        * @brief Constructs a %linear_congruential_engine random number
 186        *        generator engine seeded from the seed sequence @p __q.
 187        *
 188        * @param __q the seed sequence.
 189        */
 190       explicit
 191       linear_congruential_engine(seed_seq& __q)
 192       { this->seed(__q); }
 193
 194       /**
 195        * @brief Reseeds the %linear_congruential_engine random number generator
 196        *        engine sequence to the seed @p __s.
 197        *
 198        * @param __s The new seed.
 199        */
 200       void
 201       seed(result_type __s = default_seed);
 202
 203       /**
 204        * @brief Reseeds the %linear_congruential_engine random number generator
 205        *        engine
 206        * sequence using values from the seed sequence @p __q.
 207        *
 208        * @param __q the seed sequence.
 209        */
 210       void
 211       seed(seed_seq& __q);
 212
 213       /**
 214        * @brief Gets the smallest possible value in the output range.
 215        *
 216        * The minimum depends on the @p __c parameter: if it is zero, the
 217        * minimum generated must be > 0, otherwise 0 is allowed.
 218        *
 219        * @todo This should be constexpr.
 220        */
 221       result_type
 222       min() const
 223       { return __c == 0u ? 1u : 0u; }
 224
 225       /**
 226        * @brief Gets the largest possible value in the output range.
 227        *
 228        * @todo This should be constexpr.
 229        */
 230       result_type
 231       max() const
 232       { return __m - 1u; }
 233
 234       /**
 235        * @brief Discard a sequence of random numbers.
 236        *
 237        * @todo Look for a faster way to do discard.
 238        */
 239       void
 240       discard(unsigned long long __z)
 241       {
 242         for (; __z != 0ULL; --__z)
 243           (*this)();
 244       }
 245
 246       /**
 247        * @brief Gets the next random number in the sequence.
 248        */
 249       result_type
 250       operator()()
 251       {
 252         _M_x = __detail::__mod<_UIntType, __m, __a, __c>(_M_x);
 253         return _M_x;
 254       }
 255
 256       /**
 257        * @brief Compares two linear congruential random number generator
 258        * objects of the same type for equality.
 259        *
 260        * @param __lhs A linear congruential random number generator object.
 261        * @param __rhs Another linear congruential random number generator
 262        *              object.
 263        *
 264        * @returns true if the two objects are equal, false otherwise.
 265        */
 266       friend bool
 267       operator==(const linear_congruential_engine& __lhs,
 268                  const linear_congruential_engine& __rhs)
 269       { return __lhs._M_x == __rhs._M_x; }
 270
 271       /**
 272        * @brief Writes the textual representation of the state x(i) of x to
 273        *        @p __os.
 274        *
 275        * @param __os  The output stream.
 276        * @param __lcr A % linear_congruential_engine random number generator.
 277        * @returns __os.
 278        */
 279       template<typename _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
 280                _UIntType1 __m1, typename _CharT, typename _Traits>
 281         friend std::basic_ostream<_CharT, _Traits>&
 282         operator<<(std::basic_ostream<_CharT, _Traits>&,
 283                    const std::linear_congruential_engine<_UIntType1,
 284                    __a1, __c1, __m1>&);
 285
 286       /**
 287        * @brief Sets the state of the engine by reading its textual
 288        *        representation from @p __is.
 289        *
 290        * The textual representation must have been previously written using
 291        * an output stream whose imbued locale and whose type's template
 292        * specialization arguments _CharT and _Traits were the same as those
 293        * of @p __is.
 294        *
 295        * @param __is  The input stream.
 296        * @param __lcr A % linear_congruential_engine random number generator.
 297        * @returns __is.
 298        */
 299       template<typename _UIntType1, _UIntType1 __a1, _UIntType1 __c1,
 300                _UIntType1 __m1, typename _CharT, typename _Traits>
 301         friend std::basic_istream<_CharT, _Traits>&
 302         operator>>(std::basic_istream<_CharT, _Traits>&,
 303                    std::linear_congruential_engine<_UIntType1, __a1,
 304                    __c1, __m1>&);
 305
 306     private:
 307       _UIntType _M_x;
 308     };
 309
 310
 311   /**
 312    * A generalized feedback shift register discrete random number generator.
 313    *
 314    * This algorithm avoids multiplication and division and is designed to be
 315    * friendly to a pipelined architecture.  If the parameters are chosen
 316    * correctly, this generator will produce numbers with a very long period and
 317    * fairly good apparent entropy, although still not cryptographically strong.
 318    *
 319    * The best way to use this generator is with the predefined mt19937 class.
 320    *
 321    * This algorithm was originally invented by Makoto Matsumoto and
 322    * Takuji Nishimura.
 323    *
 324    * @var word_size   The number of bits in each element of the state vector.
 325    * @var state_size  The degree of recursion.
 326    * @var shift_size  The period parameter.
 327    * @var mask_bits   The separation point bit index.
 328    * @var parameter_a The last row of the twist matrix.
 329    * @var output_u    The first right-shift tempering matrix parameter.
 330    * @var output_s    The first left-shift tempering matrix parameter.
 331    * @var output_b    The first left-shift tempering matrix mask.
 332    * @var output_t    The second left-shift tempering matrix parameter.
 333    * @var output_c    The second left-shift tempering matrix mask.
 334    * @var output_l    The second right-shift tempering matrix parameter.
 335    */
 336   template<typename _UIntType, size_t __w,
 337            size_t __n, size_t __m, size_t __r,
 338            _UIntType __a, size_t __u, _UIntType __d, size_t __s,
 339            _UIntType __b, size_t __t,
 340            _UIntType __c, size_t __l, _UIntType __f>
 341     class mersenne_twister_engine
 342     {
 343       static_assert(std::is_unsigned<_UIntType>::value, "template argument "
 344                     "_UIntType not an unsigned integral type");
 345       static_assert(1u <= __m && __m <= __n,
 346                     "template argument __m out of bounds");
 347       static_assert(__r <= __w, "template argument __r out of bound");
 348       static_assert(__u <= __w, "template argument __u out of bound");
 349       static_assert(__s <= __w, "template argument __s out of bound");
 350       static_assert(__t <= __w, "template argument __t out of bound");
 351       static_assert(__l <= __w, "template argument __l out of bound");
 352       static_assert(__w <= std::numeric_limits<_UIntType>::digits,
 353                     "template argument __w out of bound");
 354       static_assert(__a <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 355                     "template argument __a out of bound");
 356       static_assert(__b <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 357                     "template argument __b out of bound");
 358       static_assert(__c <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 359                     "template argument __c out of bound");
 360       static_assert(__d <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 361                     "template argument __d out of bound");
 362       static_assert(__f <= (__detail::_Shift<_UIntType, __w>::__value - 1),
 363                     "template argument __f out of bound");
 364
 365     public:
 366       /** The type of the generated random value. */
 367       typedef _UIntType result_type;
 368
 369       // parameter values
 370       static const size_t      word_size                 = __w;
 371       static const size_t      state_size                = __n;
 372       static const size_t      shift_size                = __m;
 373       static const size_t      mask_bits                 = __r;
 374       static const result_type xor_mask                  = __a;
 375       static const size_t      tempering_u               = __u;
 376       static const result_type tempering_d               = __d;
 377       static const size_t      tempering_s               = __s;
 378       static const result_type tempering_b               = __b;
 379       static const size_t      tempering_t               = __t;
 380       static const result_type tempering_c               = __c;
 381       static const size_t      tempering_l               = __l;
 382       static const result_type initialization_multiplier = __f;
 383       static const result_type default_seed = 5489u;
 384
 385       // constructors and member function
 386       explicit
 387       mersenne_twister_engine(result_type __sd = default_seed)
 388       { seed(__sd); }
 389
 390       /**
 391        * @brief Constructs a %mersenne_twister_engine random number generator
 392        *        engine seeded from the seed sequence @p __q.
 393        *
 394        * @param __q the seed sequence.
 395        */
 396       explicit
 397       mersenne_twister_engine(seed_seq& __q)
 398       { seed(__q); }
 399
 400       void
 401       seed(result_type __sd = default_seed);
 402
 403       void
 404       seed(seed_seq& __q);
 405
 406       /**
 407        * @brief Gets the smallest possible value in the output range.
 408        *
 409        * @todo This should be constexpr.
 410        */
 411       result_type
 412       min() const
 413       { return 0; };
 414
 415       /**
 416        * @brief Gets the largest possible value in the output range.
 417        *
 418        * @todo This should be constexpr.
 419        */
 420       result_type
 421       max() const
 422       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
 423
 424       /**
 425        * @brief Discard a sequence of random numbers.
 426        *
 427        * @todo Look for a faster way to do discard.
 428        */
 429       void
 430       discard(unsigned long long __z)
 431       {
 432         for (; __z != 0ULL; --__z)
 433           (*this)();
 434       }
 435
 436       result_type
 437       operator()();
 438
 439       /**
 440        * @brief Compares two % mersenne_twister_engine random number generator
 441        *        objects of the same type for equality.
 442        *
 443        * @param __lhs A % mersenne_twister_engine random number generator
 444        *              object.
 445        * @param __rhs Another % mersenne_twister_engine random number
 446        *              generator object.
 447        *
 448        * @returns true if the two objects are equal, false otherwise.
 449        */
 450       friend bool
 451       operator==(const mersenne_twister_engine& __lhs,
 452                  const mersenne_twister_engine& __rhs)
 453       { return std::equal(__lhs._M_x, __lhs._M_x + state_size, __rhs._M_x); }
 454
 455       /**
 456        * @brief Inserts the current state of a % mersenne_twister_engine
 457        *        random number generator engine @p __x into the output stream
 458        *        @p __os.
 459        *
 460        * @param __os An output stream.
 461        * @param __x  A % mersenne_twister_engine random number generator
 462        *             engine.
 463        *
 464        * @returns The output stream with the state of @p __x inserted or in
 465        * an error state.
 466        */
 467       template<typename _UIntType1,
 468                size_t __w1, size_t __n1,
 469                size_t __m1, size_t __r1,
 470                _UIntType1 __a1, size_t __u1,
 471                _UIntType1 __d1, size_t __s1,
 472                _UIntType1 __b1, size_t __t1,
 473                _UIntType1 __c1, size_t __l1, _UIntType1 __f1,
 474                typename _CharT, typename _Traits>
 475         friend std::basic_ostream<_CharT, _Traits>&
 476         operator<<(std::basic_ostream<_CharT, _Traits>&,
 477                    const std::mersenne_twister_engine<_UIntType1, __w1, __n1,
 478                    __m1, __r1, __a1, __u1, __d1, __s1, __b1, __t1, __c1,
 479                    __l1, __f1>&);
 480
 481       /**
 482        * @brief Extracts the current state of a % mersenne_twister_engine
 483        *        random number generator engine @p __x from the input stream
 484        *        @p __is.
 485        *
 486        * @param __is An input stream.
 487        * @param __x  A % mersenne_twister_engine random number generator
 488        *             engine.
 489        *
 490        * @returns The input stream with the state of @p __x extracted or in
 491        * an error state.
 492        */
 493       template<typename _UIntType1,
 494                size_t __w1, size_t __n1,
 495                size_t __m1, size_t __r1,
 496                _UIntType1 __a1, size_t __u1,
 497                _UIntType1 __d1, size_t __s1,
 498                _UIntType1 __b1, size_t __t1,
 499                _UIntType1 __c1, size_t __l1, _UIntType1 __f1,
 500                typename _CharT, typename _Traits>
 501         friend std::basic_istream<_CharT, _Traits>&
 502         operator>>(std::basic_istream<_CharT, _Traits>&,
 503                    std::mersenne_twister_engine<_UIntType1, __w1, __n1, __m1,
 504                    __r1, __a1, __u1, __d1, __s1, __b1, __t1, __c1,
 505                    __l1, __f1>&);
 506
 507     private:
 508       _UIntType _M_x[state_size];
 509       size_t    _M_p;
 510     };
 511
 512   /**
 513    * @brief The Marsaglia-Zaman generator.
 514    *
 515    * This is a model of a Generalized Fibonacci discrete random number
 516    * generator, sometimes referred to as the SWC generator.
 517    *
 518    * A discrete random number generator that produces pseudorandom
 519    * numbers using @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} -
 520    * carry_{i-1}) \bmod m @f$.
 521    *
 522    * The size of the state is @f$ r @f$
 523    * and the maximum period of the generator is @f$ m^r - m^s - 1 @f$.
 524    *
 525    * @var _M_x     The state of the generator.  This is a ring buffer.
 526    * @var _M_carry The carry.
 527    * @var _M_p     Current index of x(i - r).
 528    */
 529   template<typename _UIntType, size_t __w, size_t __s, size_t __r>
 530     class subtract_with_carry_engine
 531     {
 532       static_assert(std::is_unsigned<_UIntType>::value, "template argument "
 533                     "_UIntType not an unsigned integral type");
 534       static_assert(0u < __s && __s < __r,
 535                     "template argument __s out of bounds");
 536       static_assert(0u < __w && __w <= std::numeric_limits<_UIntType>::digits,
 537                     "template argument __w out of bounds");
 538
 539     public:
 540       /** The type of the generated random value. */
 541       typedef _UIntType result_type;
 542
 543       // parameter values
 544       static const size_t      word_size    = __w;
 545       static const size_t      short_lag    = __s;
 546       static const size_t      long_lag     = __r;
 547       static const result_type default_seed = 19780503u;
 548
 549       /**
 550        * @brief Constructs an explicitly seeded % subtract_with_carry_engine
 551        *        random number generator.
 552        */
 553       explicit
 554       subtract_with_carry_engine(result_type __sd = default_seed)
 555       { this->seed(__sd); }
 556
 557       /**
 558        * @brief Constructs a %subtract_with_carry_engine random number engine
 559        *        seeded from the seed sequence @p __q.
 560        *
 561        * @param __q the seed sequence.
 562        */
 563       explicit
 564       subtract_with_carry_engine(seed_seq& __q)
 565       { this->seed(__q); }
 566
 567       /**
 568        * @brief Seeds the initial state @f$ x_0 @f$ of the random number
 569        *        generator.
 570        *
 571        * N1688[4.19] modifies this as follows.  If @p __value == 0,
 572        * sets value to 19780503.  In any case, with a linear
 573        * congruential generator lcg(i) having parameters @f$ m_{lcg} =
 574        * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value
 575        * @f$, sets @f$ x_{-r} \dots x_{-1} @f$ to @f$ lcg(1) \bmod m
 576        * \dots lcg(r) \bmod m @f$ respectively.  If @f$ x_{-1} = 0 @f$
 577        * set carry to 1, otherwise sets carry to 0.
 578        */
 579       void
 580       seed(result_type __sd = default_seed);
 581
 582       /**
 583        * @brief Seeds the initial state @f$ x_0 @f$ of the
 584        * % subtract_with_carry_engine random number generator.
 585        */
 586       void
 587       seed(seed_seq& __q);
 588
 589       /**
 590        * @brief Gets the inclusive minimum value of the range of random
 591        * integers returned by this generator.
 592        *
 593        * @todo This should be constexpr.
 594        */
 595       result_type
 596       min() const
 597       { return 0; }
 598
 599       /**
 600        * @brief Gets the inclusive maximum value of the range of random
 601        * integers returned by this generator.
 602        *
 603        * @todo This should be constexpr.
 604        */
 605       result_type
 606       max() const
 607       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
 608
 609       /**
 610        * @brief Discard a sequence of random numbers.
 611        *
 612        * @todo Look for a faster way to do discard.
 613        */
 614       void
 615       discard(unsigned long long __z)
 616       {
 617         for (; __z != 0ULL; --__z)
 618           (*this)();
 619       }
 620
 621       /**
 622        * @brief Gets the next random number in the sequence.
 623        */
 624       result_type
 625       operator()();
 626
 627       /**
 628        * @brief Compares two % subtract_with_carry_engine random number
 629        *        generator objects of the same type for equality.
 630        *
 631        * @param __lhs A % subtract_with_carry_engine random number generator
 632        *              object.
 633        * @param __rhs Another % subtract_with_carry_engine random number
 634        *              generator object.
 635        *
 636        * @returns true if the two objects are equal, false otherwise.
 637        */
 638       friend bool
 639       operator==(const subtract_with_carry_engine& __lhs,
 640                  const subtract_with_carry_engine& __rhs)
 641       { return std::equal(__lhs._M_x, __lhs._M_x + long_lag, __rhs._M_x); }
 642
 643       /**
 644        * @brief Inserts the current state of a % subtract_with_carry_engine
 645        *        random number generator engine @p __x into the output stream
 646        *        @p __os.
 647        *
 648        * @param __os An output stream.
 649        * @param __x  A % subtract_with_carry_engine random number generator
 650        *             engine.
 651        *
 652        * @returns The output stream with the state of @p __x inserted or in
 653        * an error state.
 654        */
 655       template<typename _UIntType1, size_t __w1, size_t __s1, size_t __r1,
 656                typename _CharT, typename _Traits>
 657         friend std::basic_ostream<_CharT, _Traits>&
 658         operator<<(std::basic_ostream<_CharT, _Traits>&,
 659                    const std::subtract_with_carry_engine<_UIntType1, __w1,
 660                    __s1, __r1>&);
 661
 662       /**
 663        * @brief Extracts the current state of a % subtract_with_carry_engine
 664        *        random number generator engine @p __x from the input stream
 665        *        @p __is.
 666        *
 667        * @param __is An input stream.
 668        * @param __x  A % subtract_with_carry_engine random number generator engine.
 669        *
 670        * @returns The input stream with the state of @p __x extracted or in
 671        * an error state.
 672        */
 673       template<typename _UIntType1, size_t __w1, size_t __s1, size_t __r1,
 674                typename _CharT, typename _Traits>
 675         friend std::basic_istream<_CharT, _Traits>&
 676         operator>>(std::basic_istream<_CharT, _Traits>&,
 677                    std::subtract_with_carry_engine<_UIntType1, __w1,
 678                    __s1, __r1>&);
 679
 680     private:
 681       _UIntType  _M_x[long_lag];
 682       _UIntType  _M_carry;
 683       size_t     _M_p;
 684     };
 685
 686   /**
 687    * Produces random numbers from some base engine by discarding blocks of
 688    * data.
 689    *
 690    * 0 <= @p __r <= @p __p
 691    */
 692   template<typename _RandomNumberEngine, size_t __p, size_t __r>
 693     class discard_block_engine
 694     {
 695       static_assert(1 <= __r && __r <= __p,
 696                     "template argument __r out of bounds");
 697
 698     public:
 699       /** The type of the generated random value. */
 700       typedef typename _RandomNumberEngine::result_type result_type;
 701
 702       // parameter values
 703       static const size_t block_size = __p;
 704       static const size_t used_block = __r;
 705
 706       /**
 707        * @brief Constructs a default %discard_block_engine engine.
 708        *
 709        * The underlying engine is default constructed as well.
 710        */
 711       discard_block_engine()
 712       : _M_b(), _M_n(0) { }
 713
 714       /**
 715        * @brief Copy constructs a %discard_block_engine engine.
 716        *
 717        * Copies an existing base class random number generator.
 718        * @param rng An existing (base class) engine object.
 719        */
 720       explicit
 721       discard_block_engine(const _RandomNumberEngine& __rne)
 722       : _M_b(__rne), _M_n(0) { }
 723
 724       /**
 725        * @brief Move constructs a %discard_block_engine engine.
 726        *
 727        * Copies an existing base class random number generator.
 728        * @param rng An existing (base class) engine object.
 729        */
 730       explicit
 731       discard_block_engine(_RandomNumberEngine&& __rne)
 732       : _M_b(std::move(__rne)), _M_n(0) { }
 733
 734       /**
 735        * @brief Seed constructs a %discard_block_engine engine.
 736        *
 737        * Constructs the underlying generator engine seeded with @p __s.
 738        * @param __s A seed value for the base class engine.
 739        */
 740       explicit
 741       discard_block_engine(result_type __s)
 742       : _M_b(__s), _M_n(0) { }
 743
 744       /**
 745        * @brief Generator construct a %discard_block_engine engine.
 746        *
 747        * @param __q A seed sequence.
 748        */
 749       explicit
 750       discard_block_engine(seed_seq& __q)
 751       : _M_b(__q), _M_n(0)
 752       { }
 753
 754       /**
 755        * @brief Reseeds the %discard_block_engine object with the default
 756        *        seed for the underlying base class generator engine.
 757        */
 758       void
 759       seed()
 760       {
 761         _M_b.seed();
 762         _M_n = 0;
 763       }
 764
 765       /**
 766        * @brief Reseeds the %discard_block_engine object with the default
 767        *        seed for the underlying base class generator engine.
 768        */
 769       void
 770       seed(result_type __s)
 771       {
 772         _M_b.seed(__s);
 773         _M_n = 0;
 774       }
 775
 776       /**
 777        * @brief Reseeds the %discard_block_engine object with the given seed
 778        *        sequence.
 779        * @param __q A seed generator function.
 780        */
 781       void
 782       seed(seed_seq& __q)
 783       {
 784         _M_b.seed(__q);
 785         _M_n = 0;
 786       }
 787
 788       /**
 789        * @brief Gets a const reference to the underlying generator engine
 790        *        object.
 791        */
 792       const _RandomNumberEngine&
 793       base() const
 794       { return _M_b; }
 795
 796       /**
 797        * @brief Gets the minimum value in the generated random number range.
 798        *
 799        * @todo This should be constexpr.
 800        */
 801       result_type
 802       min() const
 803       { return _M_b.min(); }
 804
 805       /**
 806        * @brief Gets the maximum value in the generated random number range.
 807        *
 808        * @todo This should be constexpr.
 809        */
 810       result_type
 811       max() const
 812       { return _M_b.max(); }
 813
 814       /**
 815        * @brief Discard a sequence of random numbers.
 816        *
 817        * @todo Look for a faster way to do discard.
 818        */
 819       void
 820       discard(unsigned long long __z)
 821       {
 822         for (; __z != 0ULL; --__z)
 823           (*this)();
 824       }
 825
 826       /**
 827        * @brief Gets the next value in the generated random number sequence.
 828        */
 829       result_type
 830       operator()();
 831
 832       /**
 833        * @brief Compares two %discard_block_engine random number generator
 834        *        objects of the same type for equality.
 835        *
 836        * @param __lhs A %discard_block_engine random number generator object.
 837        * @param __rhs Another %discard_block_engine random number generator
 838        *              object.
 839        *
 840        * @returns true if the two objects are equal, false otherwise.
 841        */
 842       friend bool
 843       operator==(const discard_block_engine& __lhs,
 844                  const discard_block_engine& __rhs)
 845       { return (__lhs._M_b == __rhs._M_b) && (__lhs._M_n == __rhs._M_n); }
 846
 847       /**
 848        * @brief Inserts the current state of a %discard_block_engine random
 849        *        number generator engine @p __x into the output stream
 850        *        @p __os.
 851        *
 852        * @param __os An output stream.
 853        * @param __x  A %discard_block_engine random number generator engine.
 854        *
 855        * @returns The output stream with the state of @p __x inserted or in
 856        * an error state.
 857        */
 858       template<typename _RandomNumberEngine1, size_t __p1, size_t __r1,
 859                typename _CharT, typename _Traits>
 860         friend std::basic_ostream<_CharT, _Traits>&
 861         operator<<(std::basic_ostream<_CharT, _Traits>&,
 862                    const std::discard_block_engine<_RandomNumberEngine1,
 863                    __p1, __r1>&);
 864
 865       /**
 866        * @brief Extracts the current state of a % subtract_with_carry_engine
 867        *        random number generator engine @p __x from the input stream
 868        *        @p __is.
 869        *
 870        * @param __is An input stream.
 871        * @param __x  A %discard_block_engine random number generator engine.
 872        *
 873        * @returns The input stream with the state of @p __x extracted or in
 874        * an error state.
 875        */
 876       template<typename _RandomNumberEngine1, size_t __p1, size_t __r1,
 877                typename _CharT, typename _Traits>
 878         friend std::basic_istream<_CharT, _Traits>&
 879         operator>>(std::basic_istream<_CharT, _Traits>&,
 880                    std::discard_block_engine<_RandomNumberEngine1,
 881                    __p1, __r1>&);
 882
 883     private:
 884       _RandomNumberEngine _M_b;
 885       size_t _M_n;
 886     };
 887
 888   /**
 889    * Produces random numbers by combining random numbers from some base
 890    * engine to produce random numbers with a specifies number of bits @p __w.
 891    */
 892   template<typename _RandomNumberEngine, size_t __w, typename _UIntType>
 893     class independent_bits_engine
 894     {
 895       static_assert(std::is_unsigned<_UIntType>::value, "template argument "
 896                     "_UIntType not an unsigned integral type");
 897       static_assert(0u < __w && __w <= std::numeric_limits<_UIntType>::digits,
 898                     "template argument __w out of bounds");
 899
 900     public:
 901       /** The type of the generated random value. */
 902       typedef _UIntType result_type;
 903
 904       /**
 905        * @brief Constructs a default %independent_bits_engine engine.
 906        *
 907        * The underlying engine is default constructed as well.
 908        */
 909       independent_bits_engine()
 910       : _M_b() { }
 911
 912       /**
 913        * @brief Copy constructs a %independent_bits_engine engine.
 914        *
 915        * Copies an existing base class random number generator.
 916        * @param rng An existing (base class) engine object.
 917        */
 918       explicit
 919       independent_bits_engine(const _RandomNumberEngine& __rne)
 920       : _M_b(__rne) { }
 921
 922       /**
 923        * @brief Move constructs a %independent_bits_engine engine.
 924        *
 925        * Copies an existing base class random number generator.
 926        * @param rng An existing (base class) engine object.
 927        */
 928       explicit
 929       independent_bits_engine(_RandomNumberEngine&& __rne)
 930       : _M_b(std::move(__rne)) { }
 931
 932       /**
 933        * @brief Seed constructs a %independent_bits_engine engine.
 934        *
 935        * Constructs the underlying generator engine seeded with @p __s.
 936        * @param __s A seed value for the base class engine.
 937        */
 938       explicit
 939       independent_bits_engine(result_type __s)
 940       : _M_b(__s) { }
 941
 942       /**
 943        * @brief Generator construct a %independent_bits_engine engine.
 944        *
 945        * @param __q A seed sequence.
 946        */
 947       explicit
 948       independent_bits_engine(seed_seq& __q)
 949       : _M_b(__q)
 950       { }
 951
 952       /**
 953        * @brief Reseeds the %independent_bits_engine object with the default
 954        *        seed for the underlying base class generator engine.
 955        */
 956       void
 957       seed()
 958       { _M_b.seed(); }
 959
 960       /**
 961        * @brief Reseeds the %independent_bits_engine object with the default
 962        *        seed for the underlying base class generator engine.
 963        */
 964       void
 965       seed(result_type __s)
 966       { _M_b.seed(__s); }
 967
 968       /**
 969        * @brief Reseeds the %independent_bits_engine object with the given
 970        *        seed sequence.
 971        * @param __q A seed generator function.
 972        */
 973       void
 974       seed(seed_seq& __q)
 975       { _M_b.seed(__q); }
 976
 977       /**
 978        * @brief Gets a const reference to the underlying generator engine
 979        *        object.
 980        */
 981       const _RandomNumberEngine&
 982       base() const
 983       { return _M_b; }
 984
 985       /**
 986        * @brief Gets the minimum value in the generated random number range.
 987        *
 988        * @todo This should be constexpr.
 989        */
 990       result_type
 991       min() const
 992       { return 0U; }
 993
 994       /**
 995        * @brief Gets the maximum value in the generated random number range.
 996        *
 997        * @todo This should be constexpr.
 998        */
 999       result_type
1000       max() const
1001       { return __detail::_Shift<_UIntType, __w>::__value - 1; }
1002
1003       /**
1004        * @brief Discard a sequence of random numbers.
1005        *
1006        * @todo Look for a faster way to do discard.
1007        */
1008       void
1009       discard(unsigned long long __z)
1010       {
1011         for (; __z != 0ULL; --__z)
1012           (*this)();
1013       }
1014
1015       /**
1016        * @brief Gets the next value in the generated random number sequence.
1017        */
1018       result_type
1019       operator()();
1020
1021       /**
1022        * @brief Compares two %independent_bits_engine random number generator
1023        * objects of the same type for equality.
1024        *
1025        * @param __lhs A %independent_bits_engine random number generator
1026        *              object.
1027        * @param __rhs Another %independent_bits_engine random number generator
1028        *              object.
1029        *
1030        * @returns true if the two objects are equal, false otherwise.
1031        */
1032       friend bool
1033       operator==(const independent_bits_engine& __lhs,
1034                  const independent_bits_engine& __rhs)
1035       { return __lhs._M_b == __rhs._M_b; }
1036
1037       /**
1038        * @brief Extracts the current state of a % subtract_with_carry_engine
1039        *        random number generator engine @p __x from the input stream
1040        *        @p __is.
1041        *
1042        * @param __is An input stream.
1043        * @param __x  A %independent_bits_engine random number generator
1044        *             engine.
1045        *
1046        * @returns The input stream with the state of @p __x extracted or in
1047        *          an error state.
1048        */
1049       template<typename _CharT, typename _Traits>
1050         friend std::basic_istream<_CharT, _Traits>&
1051         operator>>(std::basic_istream<_CharT, _Traits>& __is,
1052                    std::independent_bits_engine<_RandomNumberEngine,
1053                    __w, _UIntType>& __x)
1054         {
1055           __is >> __x._M_b;
1056           return __is;
1057         }
1058
1059     private:
1060       _RandomNumberEngine _M_b;
1061     };
1062
1063   /**
1064    * @brief Inserts the current state of a %independent_bits_engine random
1065    *        number generator engine @p __x into the output stream @p __os.
1066    *
1067    * @param __os An output stream.
1068    * @param __x  A %independent_bits_engine random number generator engine.
1069    *
1070    * @returns The output stream with the state of @p __x inserted or in
1071    *          an error state.
1072    */
1073   template<typename _RandomNumberEngine, size_t __w, typename _UIntType,
1074            typename _CharT, typename _Traits>
1075     std::basic_ostream<_CharT, _Traits>&
1076     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1077                const std::independent_bits_engine<_RandomNumberEngine,
1078                __w, _UIntType>& __x)
1079     {
1080       __os << __x.base();
1081       return __os;
1082     }
1083
1084   /**
1085    * @brief Produces random numbers by combining random numbers from some
1086    * base engine to produce random numbers with a specifies number of bits
1087    * @p __w.
1088    */
1089   template<typename _RandomNumberEngine, size_t __k>
1090     class shuffle_order_engine
1091     {
1092       static_assert(1u <= __k, "template argument __k out of bound");
1093
1094     public:
1095       /** The type of the generated random value. */
1096       typedef typename _RandomNumberEngine::result_type result_type;
1097
1098       static const size_t table_size = __k;
1099
1100       /**
1101        * @brief Constructs a default %shuffle_order_engine engine.
1102        *
1103        * The underlying engine is default constructed as well.
1104        */
1105       shuffle_order_engine()
1106       : _M_b()
1107       { _M_initialize(); }
1108
1109       /**
1110        * @brief Copy constructs a %shuffle_order_engine engine.
1111        *
1112        * Copies an existing base class random number generator.
1113        * @param rng An existing (base class) engine object.
1114        */
1115       explicit
1116       shuffle_order_engine(const _RandomNumberEngine& __rne)
1117       : _M_b(__rne)
1118       { _M_initialize(); }
1119
1120       /**
1121        * @brief Move constructs a %shuffle_order_engine engine.
1122        *
1123        * Copies an existing base class random number generator.
1124        * @param rng An existing (base class) engine object.
1125        */
1126       explicit
1127       shuffle_order_engine(_RandomNumberEngine&& __rne)
1128       : _M_b(std::move(__rne))
1129       { _M_initialize(); }
1130
1131       /**
1132        * @brief Seed constructs a %shuffle_order_engine engine.
1133        *
1134        * Constructs the underlying generator engine seeded with @p __s.
1135        * @param __s A seed value for the base class engine.
1136        */
1137       explicit
1138       shuffle_order_engine(result_type __s)
1139       : _M_b(__s)
1140       { _M_initialize(); }
1141
1142       /**
1143        * @brief Generator construct a %shuffle_order_engine engine.
1144        *
1145        * @param __q A seed sequence.
1146        */
1147       explicit
1148       shuffle_order_engine(seed_seq& __q)
1149       : _M_b(__q)
1150       { _M_initialize(); }
1151
1152       /**
1153        * @brief Reseeds the %shuffle_order_engine object with the default seed
1154                 for the underlying base class generator engine.
1155        */
1156       void
1157       seed()
1158       {
1159         _M_b.seed();
1160         _M_initialize();
1161       }
1162
1163       /**
1164        * @brief Reseeds the %shuffle_order_engine object with the default seed
1165        *        for the underlying base class generator engine.
1166        */
1167       void
1168       seed(result_type __s)
1169       {
1170         _M_b.seed(__s);
1171         _M_initialize();
1172       }
1173
1174       /**
1175        * @brief Reseeds the %shuffle_order_engine object with the given seed
1176        *        sequence.
1177        * @param __q A seed generator function.
1178        */
1179       void
1180       seed(seed_seq& __q)
1181       {
1182         _M_b.seed(__q);
1183         _M_initialize();
1184       }
1185
1186       /**
1187        * Gets a const reference to the underlying generator engine object.
1188        */
1189       const _RandomNumberEngine&
1190       base() const
1191       { return _M_b; }
1192
1193       /**
1194        * Gets the minimum value in the generated random number range.
1195        *
1196        * @todo This should be constexpr.
1197        */
1198       result_type
1199       min() const
1200       { return _M_b.min(); }
1201
1202       /**
1203        * Gets the maximum value in the generated random number range.
1204        *
1205        * @todo This should be constexpr.
1206        */
1207       result_type
1208       max() const
1209       { return _M_b.max(); }
1210
1211       /**
1212        * Discard a sequence of random numbers.
1213        *
1214        * @todo Look for a faster way to do discard.
1215        */
1216       void
1217       discard(unsigned long long __z)
1218       {
1219         for (; __z != 0ULL; --__z)
1220           (*this)();
1221       }
1222
1223       /**
1224        * Gets the next value in the generated random number sequence.
1225        */
1226       result_type
1227       operator()();
1228
1229       /**
1230        * Compares two %shuffle_order_engine random number generator objects
1231        * of the same type for equality.
1232        *
1233        * @param __lhs A %shuffle_order_engine random number generator object.
1234        * @param __rhs Another %shuffle_order_engine random number generator
1235        *              object.
1236        *
1237        * @returns true if the two objects are equal, false otherwise.
1238        */
1239       friend bool
1240       operator==(const shuffle_order_engine& __lhs,
1241                  const shuffle_order_engine& __rhs)
1242       { return __lhs._M_b == __rhs._M_b; }
1243
1244       /**
1245        * @brief Inserts the current state of a %shuffle_order_engine random
1246        *        number generator engine @p __x into the output stream
1247         @p __os.
1248        *
1249        * @param __os An output stream.
1250        * @param __x  A %shuffle_order_engine random number generator engine.
1251        *
1252        * @returns The output stream with the state of @p __x inserted or in
1253        * an error state.
1254        */
1255       template<typename _RandomNumberEngine1, size_t __k1,
1256                typename _CharT, typename _Traits>
1257         friend std::basic_ostream<_CharT, _Traits>&
1258         operator<<(std::basic_ostream<_CharT, _Traits>&,
1259                    const std::shuffle_order_engine<_RandomNumberEngine1,
1260                    __k1>&);
1261
1262       /**
1263        * @brief Extracts the current state of a % subtract_with_carry_engine
1264        *        random number generator engine @p __x from the input stream
1265        *        @p __is.
1266        *
1267        * @param __is An input stream.
1268        * @param __x  A %shuffle_order_engine random number generator engine.
1269        *
1270        * @returns The input stream with the state of @p __x extracted or in
1271        * an error state.
1272        */
1273       template<typename _RandomNumberEngine1, size_t __k1,
1274                typename _CharT, typename _Traits>
1275         friend std::basic_istream<_CharT, _Traits>&
1276         operator>>(std::basic_istream<_CharT, _Traits>&,
1277                    std::shuffle_order_engine<_RandomNumberEngine1, __k1>&);
1278
1279     private:
1280       void _M_initialize()
1281       {
1282         for (size_t __i = 0; __i < __k; ++__i)
1283           _M_v[__i] = _M_b();
1284         _M_y = _M_b();
1285       }
1286
1287       _RandomNumberEngine _M_b;
1288       result_type _M_v[__k];
1289       result_type _M_y;
1290     };
1291
1292   /**
1293    * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
1294    */
1295   typedef linear_congruential_engine<uint_fast32_t, 16807UL, 0UL, 2147483647UL>
1296   minstd_rand0;
1297
1298   /**
1299    * An alternative LCR (Lehmer Generator function) .
1300    */
1301   typedef linear_congruential_engine<uint_fast32_t, 48271UL, 0UL, 2147483647UL>
1302   minstd_rand;
1303
1304   /**
1305    * The classic Mersenne Twister.
1306    *
1307    * Reference:
1308    * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
1309    * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
1310    * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
1311    */
1312   typedef mersenne_twister_engine<
1313     uint_fast32_t,
1314     32, 624, 397, 31,
1315     0x9908b0dfUL, 11,
1316     0xffffffffUL, 7,
1317     0x9d2c5680UL, 15,
1318     0xefc60000UL, 18, 1812433253UL> mt19937;
1319
1320   /**
1321    * An alternative Mersenne Twister.
1322    */
1323   typedef mersenne_twister_engine<
1324     uint_fast64_t,
1325     64, 312, 156, 31,
1326     0xb5026f5aa96619e9ULL, 29,
1327     0x5555555555555555ULL, 17,
1328     0x71d67fffeda60000ULL, 37,
1329     0xfff7eee000000000ULL, 43,
1330     6364136223846793005ULL> mt19937_64;
1331
1332   /**
1333    * .
1334    */
1335   typedef subtract_with_carry_engine<uint_fast32_t, 24, 10, 24>
1336     ranlux24_base;
1337
1338   typedef subtract_with_carry_engine<uint_fast64_t, 48, 5, 12>
1339     ranlux48_base;
1340
1341   typedef discard_block_engine<ranlux24_base, 223, 23> ranlux24;
1342
1343   typedef discard_block_engine<ranlux48_base, 389, 11> ranlux48;
1344
1345   /**
1346    * .
1347    */
1348   typedef shuffle_order_engine<minstd_rand0, 256> knuth_b;
1349
1350   /**
1351    * .
1352    */
1353   typedef minstd_rand0 default_random_engine;
1354
1355   /**
1356    * A standard interface to a platform-specific non-deterministic
1357    * random number generator (if any are available).
1358    */
1359   class random_device
1360   {
1361   public:
1362     /** The type of the generated random value. */
1363     typedef unsigned int result_type;
1364
1365     // constructors, destructors and member functions
1366
1367 #ifdef _GLIBCXX_USE_RANDOM_TR1
1368
1369     explicit
1370     random_device(const std::string& __token = "/dev/urandom")
1371     {
1372       if ((__token != "/dev/urandom" && __token != "/dev/random")
1373           || !(_M_file = std::fopen(__token.c_str(), "rb")))
1374         std::__throw_runtime_error(__N("random_device::"
1375                                        "random_device(const std::string&)"));
1376     }
1377
1378     ~random_device()
1379     { std::fclose(_M_file); }
1380
1381 #else
1382
1383     explicit
1384     random_device(const std::string& __token = "mt19937")
1385     : _M_mt(_M_strtoul(__token)) { }
1386
1387   private:
1388     static unsigned long
1389     _M_strtoul(const std::string& __str)
1390     {
1391       unsigned long __ret = 5489UL;
1392       if (__str != "mt19937")
1393         {
1394           const char* __nptr = __str.c_str();
1395           char* __endptr;
1396           __ret = std::strtoul(__nptr, &__endptr, 0);
1397           if (*__nptr == '\0' || *__endptr != '\0')
1398             std::__throw_runtime_error(__N("random_device::_M_strtoul"
1399                                            "(const std::string&)"));
1400         }
1401       return __ret;
1402     }
1403
1404   public:
1405
1406 #endif
1407
1408     result_type
1409     min() const
1410     { return std::numeric_limits<result_type>::min(); }
1411
1412     result_type
1413     max() const
1414     { return std::numeric_limits<result_type>::max(); }
1415
1416     double
1417     entropy() const
1418     { return 0.0; }
1419
1420     result_type
1421     operator()()
1422     {
1423 #ifdef _GLIBCXX_USE_RANDOM_TR1
1424       result_type __ret;
1425       std::fread(reinterpret_cast<void*>(&__ret), sizeof(result_type),
1426                  1, _M_file);
1427       return __ret;
1428 #else
1429       return _M_mt();
1430 #endif
1431     }
1432
1433     // No copy functions.
1434     random_device(const random_device&) = delete;
1435     void operator=(const random_device&) = delete;
1436
1437   private:
1438
1439 #ifdef _GLIBCXX_USE_RANDOM_TR1
1440     FILE*        _M_file;
1441 #else
1442     mt19937      _M_mt;
1443 #endif
1444   };
1445
1446   /* @} */ // group std_random_generators
1447
1448   /**
1449    * @addtogroup std_random_distributions Random Number Distributions
1450    * @ingroup std_random
1451    * @{
1452    */
1453
1454   /**
1455    * @addtogroup std_random_distributions_uniform Uniform Distributions
1456    * @ingroup std_random_distributions
1457    * @{
1458    */
1459
1460   /**
1461    * @brief Uniform discrete distribution for random numbers.
1462    * A discrete random distribution on the range @f$[min, max]@f$ with equal
1463    * probability throughout the range.
1464    */
1465   template<typename _IntType = int>
1466     class uniform_int_distribution
1467     {
1468       static_assert(std::is_integral<_IntType>::value,
1469                     "template argument not an integral type");
1470
1471     public:
1472       /** The type of the range of the distribution. */
1473       typedef _IntType result_type;
1474       /** Parameter type. */
1475       struct param_type
1476       {
1477         typedef uniform_int_distribution<_IntType> distribution_type;
1478
1479         explicit
1480         param_type(_IntType __a = 0,
1481                    _IntType __b = std::numeric_limits<_IntType>::max())
1482         : _M_a(__a), _M_b(__b)
1483         {
1484           _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
1485         }
1486
1487         result_type
1488         a() const
1489         { return _M_a; }
1490
1491         result_type
1492         b() const
1493         { return _M_b; }
1494
1495       private:
1496         _IntType _M_a;
1497         _IntType _M_b;
1498       };
1499
1500     public:
1501       /**
1502        * @brief Constructs a uniform distribution object.
1503        */
1504       explicit
1505       uniform_int_distribution(_IntType __a = 0,
1506                            _IntType __b = std::numeric_limits<_IntType>::max())
1507       : _M_param(__a, __b)
1508       { }
1509
1510       explicit
1511       uniform_int_distribution(const param_type& __p)
1512       : _M_param(__p)
1513       { }
1514
1515       /**
1516        * @brief Resets the distribution state.
1517        *
1518        * Does nothing for the uniform integer distribution.
1519        */
1520       void
1521       reset() { }
1522
1523       result_type
1524       a() const
1525       { return _M_param.a(); }
1526
1527       result_type
1528       b() const
1529       { return _M_param.b(); }
1530
1531       /**
1532        * @brief Returns the inclusive lower bound of the distribution range.
1533        */
1534       result_type
1535       min() const
1536       { return this->a(); }
1537
1538       /**
1539        * @brief Returns the inclusive upper bound of the distribution range.
1540        */
1541       result_type
1542       max() const
1543       { return this->b(); }
1544
1545       /**
1546        * @brief Returns the parameter set of the distribution.
1547        */
1548       param_type
1549       param() const
1550       { return _M_param; }
1551
1552       /**
1553        * @brief Sets the parameter set of the distribution.
1554        * @param __param The new parameter set of the distribution.
1555        */
1556       void
1557       param(const param_type& __param)
1558       { _M_param = __param; }
1559
1560       /**
1561        * Gets a uniformly distributed random number in the range
1562        * @f$(min, max)@f$.
1563        */
1564       template<typename _UniformRandomNumberGenerator>
1565         result_type
1566         operator()(_UniformRandomNumberGenerator& __urng)
1567         { return this->operator()(__urng, this->param()); }
1568
1569       /**
1570        * Gets a uniform random number in the range @f$[0, n)@f$.
1571        *
1572        * This function is aimed at use with std::random_shuffle.
1573        */
1574       template<typename _UniformRandomNumberGenerator>
1575         result_type
1576         operator()(_UniformRandomNumberGenerator& __urng,
1577                    const param_type& __p);
1578
1579       param_type _M_param;
1580     };
1581
1582   /**
1583    * @brief Inserts a %uniform_int_distribution random number
1584    *        distribution @p __x into the output stream @p os.
1585    *
1586    * @param __os An output stream.
1587    * @param __x  A %uniform_int_distribution random number distribution.
1588    *
1589    * @returns The output stream with the state of @p __x inserted or in
1590    * an error state.
1591    */
1592   template<typename _IntType, typename _CharT, typename _Traits>
1593     std::basic_ostream<_CharT, _Traits>&
1594     operator<<(std::basic_ostream<_CharT, _Traits>&,
1595                const std::uniform_int_distribution<_IntType>&);
1596
1597   /**
1598    * @brief Extracts a %uniform_int_distribution random number distribution
1599    * @p __x from the input stream @p __is.
1600    *
1601    * @param __is An input stream.
1602    * @param __x  A %uniform_int_distribution random number generator engine.
1603    *
1604    * @returns The input stream with @p __x extracted or in an error state.
1605    */
1606   template<typename _IntType, typename _CharT, typename _Traits>
1607     std::basic_istream<_CharT, _Traits>&
1608     operator>>(std::basic_istream<_CharT, _Traits>&,
1609                std::uniform_int_distribution<_IntType>&);
1610
1611
1612   /**
1613    * @brief Uniform continuous distribution for random numbers.
1614    *
1615    * A continuous random distribution on the range [min, max) with equal
1616    * probability throughout the range.  The URNG should be real-valued and
1617    * deliver number in the range [0, 1).
1618    */
1619   template<typename _RealType = double>
1620     class uniform_real_distribution
1621     {
1622       static_assert(std::is_floating_point<_RealType>::value,
1623                     "template argument not a floating point type");
1624
1625     public:
1626       /** The type of the range of the distribution. */
1627       typedef _RealType result_type;
1628       /** Parameter type. */
1629       struct param_type
1630       {
1631         typedef uniform_real_distribution<_RealType> distribution_type;
1632
1633         explicit
1634         param_type(_RealType __a = _RealType(0),
1635                    _RealType __b = _RealType(1))
1636         : _M_a(__a), _M_b(__b)
1637         {
1638           _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
1639         }
1640
1641         result_type
1642         a() const
1643         { return _M_a; }
1644
1645         result_type
1646         b() const
1647         { return _M_b; }
1648
1649       private:
1650         _RealType _M_a;
1651         _RealType _M_b;
1652       };
1653
1654     public:
1655       /**
1656        * @brief Constructs a uniform_real_distribution object.
1657        *
1658        * @param __min [IN]  The lower bound of the distribution.
1659        * @param __max [IN]  The upper bound of the distribution.
1660        */
1661       explicit
1662       uniform_real_distribution(_RealType __a = _RealType(0),
1663                                 _RealType __b = _RealType(1))
1664       : _M_param(__a, __b)
1665       { }
1666
1667       explicit
1668       uniform_real_distribution(const param_type& __p)
1669       : _M_param(__p)
1670       { }
1671
1672       /**
1673        * @brief Resets the distribution state.
1674        *
1675        * Does nothing for the uniform real distribution.
1676        */
1677       void
1678       reset() { }
1679
1680       result_type
1681       a() const
1682       { return _M_param.a(); }
1683
1684       result_type
1685       b() const
1686       { return _M_param.b(); }
1687
1688       /**
1689        * @brief Returns the inclusive lower bound of the distribution range.
1690        */
1691       result_type
1692       min() const
1693       { return this->a(); }
1694
1695       /**
1696        * @brief Returns the inclusive upper bound of the distribution range.
1697        */
1698       result_type
1699       max() const
1700       { return this->b(); }
1701
1702       /**
1703        * @brief Returns the parameter set of the distribution.
1704        */
1705       param_type
1706       param() const
1707       { return _M_param; }
1708
1709       /**
1710        * @brief Sets the parameter set of the distribution.
1711        * @param __param The new parameter set of the distribution.
1712        */
1713       void
1714       param(const param_type& __param)
1715       { _M_param = __param; }
1716
1717       template<typename _UniformRandomNumberGenerator>
1718         result_type
1719         operator()(_UniformRandomNumberGenerator& __urng)
1720         { return this->operator()(__urng, this->param()); }
1721
1722       template<typename _UniformRandomNumberGenerator>
1723         result_type
1724         operator()(_UniformRandomNumberGenerator& __urng,
1725                    const param_type& __p)
1726         {
1727           __detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
1728             __aurng(__urng);
1729           return (__aurng() * (__p.b() - __p.a())) + __p.a();
1730         }
1731
1732     private:
1733       param_type _M_param;
1734     };
1735
1736   /**
1737    * @brief Inserts a %uniform_real_distribution random number
1738    *        distribution @p __x into the output stream @p __os.
1739    *
1740    * @param __os An output stream.
1741    * @param __x  A %uniform_real_distribution random number distribution.
1742    *
1743    * @returns The output stream with the state of @p __x inserted or in
1744    *          an error state.
1745    */
1746   template<typename _RealType, typename _CharT, typename _Traits>
1747     std::basic_ostream<_CharT, _Traits>&
1748     operator<<(std::basic_ostream<_CharT, _Traits>&,
1749                const std::uniform_real_distribution<_RealType>&);
1750
1751   /**
1752    * @brief Extracts a %uniform_real_distribution random number distribution
1753    * @p __x from the input stream @p __is.
1754    *
1755    * @param __is An input stream.
1756    * @param __x  A %uniform_real_distribution random number generator engine.
1757    *
1758    * @returns The input stream with @p __x extracted or in an error state.
1759    */
1760   template<typename _RealType, typename _CharT, typename _Traits>
1761     std::basic_istream<_CharT, _Traits>&
1762     operator>>(std::basic_istream<_CharT, _Traits>&,
1763                std::uniform_real_distribution<_RealType>&);
1764
1765   /* @} */ // group std_random_distributions_uniform
1766
1767   /**
1768    * @addtogroup std_random_distributions_normal Normal Distributions
1769    * @ingroup std_random_distributions
1770    * @{
1771    */
1772
1773   /**
1774    * @brief A normal continuous distribution for random numbers.
1775    *
1776    * The formula for the normal probability density function is
1777    * @f$ p(x|\mu,\sigma) = \frac{1}{\sigma \sqrt{2 \pi}}
1778    *            e^{- \frac{{x - \mu}^ {2}}{2 \sigma ^ {2}} } @f$.
1779    */
1780   template<typename _RealType = double>
1781     class normal_distribution
1782     {
1783       static_assert(std::is_floating_point<_RealType>::value,
1784                     "template argument not a floating point type");
1785
1786     public:
1787       /** The type of the range of the distribution. */
1788       typedef _RealType result_type;
1789       /** Parameter type. */
1790       struct param_type
1791       {
1792         typedef normal_distribution<_RealType> distribution_type;
1793
1794         explicit
1795         param_type(_RealType __mean = _RealType(0),
1796                    _RealType __stddev = _RealType(1))
1797         : _M_mean(__mean), _M_stddev(__stddev)
1798         {
1799           _GLIBCXX_DEBUG_ASSERT(_M_stddev > _RealType(0));
1800         }
1801
1802         _RealType
1803         mean() const
1804         { return _M_mean; }
1805
1806         _RealType
1807         stddev() const
1808         { return _M_stddev; }
1809
1810       private:
1811         _RealType _M_mean;
1812         _RealType _M_stddev;
1813       };
1814
1815     public:
1816       /**
1817        * Constructs a normal distribution with parameters @f$ mean @f$ and
1818        * standard deviation.
1819        */
1820       explicit
1821       normal_distribution(result_type __mean = result_type(0),
1822                           result_type __stddev = result_type(1))
1823       : _M_param(__mean, __stddev), _M_saved_available(false)
1824       { }
1825
1826       explicit
1827       normal_distribution(const param_type& __p)
1828       : _M_param(__p), _M_saved_available(false)
1829       { }
1830
1831       /**
1832        * @brief Resets the distribution state.
1833        */
1834       void
1835       reset()
1836       { _M_saved_available = false; }
1837
1838       /**
1839        * @brief Returns the mean of the distribution.
1840        */
1841       _RealType
1842       mean() const
1843       { return _M_param.mean(); }
1844
1845       /**
1846        * @brief Returns the standard deviation of the distribution.
1847        */
1848       _RealType
1849       stddev() const
1850       { return _M_param.stddev(); }
1851
1852       /**
1853        * @brief Returns the parameter set of the distribution.
1854        */
1855       param_type
1856       param() const
1857       { return _M_param; }
1858
1859       /**
1860        * @brief Sets the parameter set of the distribution.
1861        * @param __param The new parameter set of the distribution.
1862        */
1863       void
1864       param(const param_type& __param)
1865       { _M_param = __param; }
1866
1867       /**
1868        * @brief Returns the greatest lower bound value of the distribution.
1869        */
1870       result_type
1871       min() const
1872       { return std::numeric_limits<result_type>::min(); }
1873
1874       /**
1875        * @brief Returns the least upper bound value of the distribution.
1876        */
1877       result_type
1878       max() const
1879       { return std::numeric_limits<result_type>::max(); }
1880
1881       template<typename _UniformRandomNumberGenerator>
1882         result_type
1883         operator()(_UniformRandomNumberGenerator& __urng)
1884         { return this->operator()(__urng, this->param()); }
1885
1886       template<typename _UniformRandomNumberGenerator>
1887         result_type
1888         operator()(_UniformRandomNumberGenerator& __urng,
1889                    const param_type& __p);
1890
1891       /**
1892        * @brief Inserts a %normal_distribution random number distribution
1893        * @p __x into the output stream @p __os.
1894        *
1895        * @param __os An output stream.
1896        * @param __x  A %normal_distribution random number distribution.
1897        *
1898        * @returns The output stream with the state of @p __x inserted or in
1899        * an error state.
1900        */
1901       template<typename _RealType1, typename _CharT, typename _Traits>
1902         friend std::basic_ostream<_CharT, _Traits>&
1903         operator<<(std::basic_ostream<_CharT, _Traits>&,
1904                    const std::normal_distribution<_RealType1>&);
1905
1906       /**
1907        * @brief Extracts a %normal_distribution random number distribution
1908        * @p __x from the input stream @p __is.
1909        *
1910        * @param __is An input stream.
1911        * @param __x  A %normal_distribution random number generator engine.
1912        *
1913        * @returns The input stream with @p __x extracted or in an error
1914        *          state.
1915        */
1916       template<typename _RealType1, typename _CharT, typename _Traits>
1917         friend std::basic_istream<_CharT, _Traits>&
1918         operator>>(std::basic_istream<_CharT, _Traits>&,
1919                    std::normal_distribution<_RealType1>&);
1920
1921     private:
1922       param_type  _M_param;
1923       result_type _M_saved;
1924       bool        _M_saved_available;
1925     };
1926
1927
1928   /**
1929    * @brief A lognormal_distribution random number distribution.
1930    *
1931    * The formula for the normal probability mass function is
1932    * @f$ p(x|m,s) = \frac{1}{sx\sqrt{2\pi}}
1933    *             \exp{-\frac{(\ln{x} - m)^2}{2s^2}} @f$
1934    */
1935   template<typename _RealType = double>
1936     class lognormal_distribution
1937     {
1938       static_assert(std::is_floating_point<_RealType>::value,
1939                     "template argument not a floating point type");
1940
1941     public:
1942       /** The type of the range of the distribution. */
1943       typedef _RealType result_type;
1944       /** Parameter type. */
1945       struct param_type
1946       {
1947         typedef lognormal_distribution<_RealType> distribution_type;
1948
1949         explicit
1950         param_type(_RealType __m = _RealType(0),
1951                    _RealType __s = _RealType(1))
1952         : _M_m(__m), _M_s(__s)
1953         { }
1954
1955         _RealType
1956         m() const
1957         { return _M_m; }
1958
1959         _RealType
1960         s() const
1961         { return _M_s; }
1962
1963       private:
1964         _RealType _M_m;
1965         _RealType _M_s;
1966       };
1967
1968       explicit
1969       lognormal_distribution(_RealType __m = _RealType(0),
1970                              _RealType __s = _RealType(1))
1971       : _M_param(__m, __s), _M_nd()
1972       { }
1973
1974       explicit
1975       lognormal_distribution(const param_type& __p)
1976       : _M_param(__p), _M_nd()
1977       { }
1978
1979       /**
1980        * Resets the distribution state.
1981        */
1982       void
1983       reset()
1984       { _M_nd.reset(); }
1985
1986       /**
1987        *
1988        */
1989       _RealType
1990       m() const
1991       { return _M_param.m(); }
1992
1993       _RealType
1994       s() const
1995       { return _M_param.s(); }
1996
1997       /**
1998        * @brief Returns the parameter set of the distribution.
1999        */
2000       param_type
2001       param() const
2002       { return _M_param; }
2003
2004       /**
2005        * @brief Sets the parameter set of the distribution.
2006        * @param __param The new parameter set of the distribution.
2007        */
2008       void
2009       param(const param_type& __param)
2010       { _M_param = __param; }
2011
2012       /**
2013        * @brief Returns the greatest lower bound value of the distribution.
2014        */
2015       result_type
2016       min() const
2017       { return result_type(0); }
2018
2019       /**
2020        * @brief Returns the least upper bound value of the distribution.
2021        */
2022       result_type
2023       max() const
2024       { return std::numeric_limits<result_type>::max(); }
2025
2026       template<typename _UniformRandomNumberGenerator>
2027         result_type
2028         operator()(_UniformRandomNumberGenerator& __urng)
2029         { return this->operator()(__urng, this->param()); }
2030
2031       template<typename _UniformRandomNumberGenerator>
2032         result_type
2033         operator()(_UniformRandomNumberGenerator& __urng,
2034                    const param_type& __p)
2035         { return std::exp(__p.s() * _M_nd(__urng) + __p.m()); }
2036
2037       /**
2038        * @brief Inserts a %lognormal_distribution random number distribution
2039        * @p __x into the output stream @p __os.
2040        *
2041        * @param __os An output stream.
2042        * @param __x  A %lognormal_distribution random number distribution.
2043        *
2044        * @returns The output stream with the state of @p __x inserted or in
2045        * an error state.
2046        */
2047       template<typename _RealType1, typename _CharT, typename _Traits>
2048         friend std::basic_ostream<_CharT, _Traits>&
2049         operator<<(std::basic_ostream<_CharT, _Traits>&,
2050                    const std::lognormal_distribution<_RealType1>&);
2051
2052       /**
2053        * @brief Extracts a %lognormal_distribution random number distribution
2054        * @p __x from the input stream @p __is.
2055        *
2056        * @param __is An input stream.
2057        * @param __x A %lognormal_distribution random number
2058        *            generator engine.
2059        *
2060        * @returns The input stream with @p __x extracted or in an error state.
2061        */
2062       template<typename _RealType1, typename _CharT, typename _Traits>
2063         friend std::basic_istream<_CharT, _Traits>&
2064         operator>>(std::basic_istream<_CharT, _Traits>&,
2065                    std::lognormal_distribution<_RealType1>&);
2066
2067     private:
2068       param_type _M_param;
2069
2070       std::normal_distribution<result_type> _M_nd;
2071     };
2072
2073
2074   /**
2075    * @brief A gamma continuous distribution for random numbers.
2076    *
2077    * The formula for the gamma probability density function is
2078    * @f$ p(x|\alpha,\beta) = \frac{1}{\beta\Gamma(\alpha)}
2079    *                         (x/\beta)^{\alpha - 1} e^{-x/\beta} @f$.
2080    */
2081   template<typename _RealType = double>
2082     class gamma_distribution
2083     {
2084       static_assert(std::is_floating_point<_RealType>::value,
2085                     "template argument not a floating point type");
2086
2087     public:
2088       /** The type of the range of the distribution. */
2089       typedef _RealType result_type;
2090       /** Parameter type. */
2091       struct param_type
2092       {
2093         typedef gamma_distribution<_RealType> distribution_type;
2094         friend class gamma_distribution<_RealType>;
2095
2096         explicit
2097         param_type(_RealType __alpha_val = _RealType(1),
2098                    _RealType __beta_val = _RealType(1))
2099         : _M_alpha(__alpha_val), _M_beta(__beta_val)
2100         {
2101           _GLIBCXX_DEBUG_ASSERT(_M_alpha > _RealType(0));
2102           _M_initialize();
2103         }
2104
2105         _RealType
2106         alpha() const
2107         { return _M_alpha; }
2108
2109         _RealType
2110         beta() const
2111         { return _M_beta; }
2112
2113       private:
2114         void
2115         _M_initialize();
2116
2117         _RealType _M_alpha;
2118         _RealType _M_beta;
2119
2120         _RealType _M_malpha, _M_a2;
2121       };
2122
2123     public:
2124       /**
2125        * @brief Constructs a gamma distribution with parameters
2126        * @f$ \alpha @f$ and @f$ \beta @f$.
2127        */
2128       explicit
2129       gamma_distribution(_RealType __alpha_val = _RealType(1),
2130                          _RealType __beta_val = _RealType(1))
2131       : _M_param(__alpha_val, __beta_val), _M_nd()
2132       { }
2133
2134       explicit
2135       gamma_distribution(const param_type& __p)
2136       : _M_param(__p), _M_nd()
2137       { }
2138
2139       /**
2140        * @brief Resets the distribution state.
2141        */
2142       void
2143       reset()
2144       { _M_nd.reset(); }
2145
2146       /**
2147        * @brief Returns the @f$ \alpha @f$ of the distribution.
2148        */
2149       _RealType
2150       alpha() const
2151       { return _M_param.alpha(); }
2152
2153       /**
2154        * @brief Returns the @f$ \beta @f$ of the distribution.
2155        */
2156       _RealType
2157       beta() const
2158       { return _M_param.beta(); }
2159
2160       /**
2161        * @brief Returns the parameter set of the distribution.
2162        */
2163       param_type
2164       param() const
2165       { return _M_param; }
2166
2167       /**
2168        * @brief Sets the parameter set of the distribution.
2169        * @param __param The new parameter set of the distribution.
2170        */
2171       void
2172       param(const param_type& __param)
2173       { _M_param = __param; }
2174
2175       /**
2176        * @brief Returns the greatest lower bound value of the distribution.
2177        */
2178       result_type
2179       min() const
2180       { return result_type(0); }
2181
2182       /**
2183        * @brief Returns the least upper bound value of the distribution.
2184        */
2185       result_type
2186       max() const
2187       { return std::numeric_limits<result_type>::max(); }
2188
2189       template<typename _UniformRandomNumberGenerator>
2190         result_type
2191         operator()(_UniformRandomNumberGenerator& __urng)
2192         { return this->operator()(__urng, this->param()); }
2193
2194       template<typename _UniformRandomNumberGenerator>
2195         result_type
2196         operator()(_UniformRandomNumberGenerator& __urng,
2197                    const param_type& __p);
2198
2199       /**
2200        * @brief Inserts a %gamma_distribution random number distribution
2201        * @p __x into the output stream @p __os.
2202        *
2203        * @param __os An output stream.
2204        * @param __x  A %gamma_distribution random number distribution.
2205        *
2206        * @returns The output stream with the state of @p __x inserted or in
2207        * an error state.
2208        */
2209       template<typename _RealType1, typename _CharT, typename _Traits>
2210         friend std::basic_ostream<_CharT, _Traits>&
2211         operator<<(std::basic_ostream<_CharT, _Traits>&,
2212                    const std::gamma_distribution<_RealType1>&);
2213
2214       /**
2215        * @brief Extracts a %gamma_distribution random number distribution
2216        * @p __x from the input stream @p __is.
2217        *
2218        * @param __is An input stream.
2219        * @param __x  A %gamma_distribution random number generator engine.
2220        *
2221        * @returns The input stream with @p __x extracted or in an error state.
2222        */
2223       template<typename _RealType1, typename _CharT, typename _Traits>
2224         friend std::basic_istream<_CharT, _Traits>&
2225         operator>>(std::basic_istream<_CharT, _Traits>&,
2226                    std::gamma_distribution<_RealType1>&);
2227
2228     private:
2229       param_type _M_param;
2230
2231       std::normal_distribution<result_type> _M_nd;
2232     };
2233
2234
2235   /**
2236    * @brief A chi_squared_distribution random number distribution.
2237    *
2238    * The formula for the normal probability mass function is
2239    * @f$ p(x|n) = \frac{x^{(n/2) - 1}e^{-x/2}}{\Gamma(n/2) 2^{n/2}} @f$
2240    */
2241   template<typename _RealType = double>
2242     class chi_squared_distribution
2243     {
2244       static_assert(std::is_floating_point<_RealType>::value,
2245                     "template argument not a floating point type");
2246
2247     public:
2248       /** The type of the range of the distribution. */
2249       typedef _RealType result_type;
2250       /** Parameter type. */
2251       struct param_type
2252       {
2253         typedef chi_squared_distribution<_RealType> distribution_type;
2254
2255         explicit
2256         param_type(_RealType __n = _RealType(1))
2257         : _M_n(__n)
2258         { }
2259
2260         _RealType
2261         n() const
2262         { return _M_n; }
2263
2264       private:
2265         _RealType _M_n;
2266       };
2267
2268       explicit
2269       chi_squared_distribution(_RealType __n = _RealType(1))
2270       : _M_param(__n), _M_gd(__n / 2)
2271       { }
2272
2273       explicit
2274       chi_squared_distribution(const param_type& __p)
2275       : _M_param(__p), _M_gd(__p.n() / 2)
2276       { }
2277
2278       /**
2279        * @brief Resets the distribution state.
2280        */
2281       void
2282       reset()
2283       { _M_gd.reset(); }
2284
2285       /**
2286        *
2287        */
2288       _RealType
2289       n() const
2290       { return _M_param.n(); }
2291
2292       /**
2293        * @brief Returns the parameter set of the distribution.
2294        */
2295       param_type
2296       param() const
2297       { return _M_param; }
2298
2299       /**
2300        * @brief Sets the parameter set of the distribution.
2301        * @param __param The new parameter set of the distribution.
2302        */
2303       void
2304       param(const param_type& __param)
2305       { _M_param = __param; }
2306
2307       /**
2308        * @brief Returns the greatest lower bound value of the distribution.
2309        */
2310       result_type
2311       min() const
2312       { return result_type(0); }
2313
2314       /**
2315        * @brief Returns the least upper bound value of the distribution.
2316        */
2317       result_type
2318       max() const
2319       { return std::numeric_limits<result_type>::max(); }
2320
2321       template<typename _UniformRandomNumberGenerator>
2322         result_type
2323         operator()(_UniformRandomNumberGenerator& __urng)
2324         { return 2 * _M_gd(__urng); }
2325
2326       template<typename _UniformRandomNumberGenerator>
2327         result_type
2328         operator()(_UniformRandomNumberGenerator& __urng,
2329                    const param_type& __p)
2330         {
2331           typedef typename std::gamma_distribution<result_type>::param_type
2332             param_type;
2333           return 2 * _M_gd(__urng, param_type(__p.n() / 2));
2334         }
2335
2336       /**
2337        * @brief Inserts a %chi_squared_distribution random number distribution
2338        * @p __x into the output stream @p __os.
2339        *
2340        * @param __os An output stream.
2341        * @param __x  A %chi_squared_distribution random number distribution.
2342        *
2343        * @returns The output stream with the state of @p __x inserted or in
2344        * an error state.
2345        */
2346       template<typename _RealType1, typename _CharT, typename _Traits>
2347         friend std::basic_ostream<_CharT, _Traits>&
2348         operator<<(std::basic_ostream<_CharT, _Traits>&,
2349                    const std::chi_squared_distribution<_RealType1>&);
2350
2351       /**
2352        * @brief Extracts a %chi_squared_distribution random number distribution
2353        * @p __x from the input stream @p __is.
2354        *
2355        * @param __is An input stream.
2356        * @param __x A %chi_squared_distribution random number
2357        *            generator engine.
2358        *
2359        * @returns The input stream with @p __x extracted or in an error state.
2360        */
2361       template<typename _RealType1, typename _CharT, typename _Traits>
2362         friend std::basic_istream<_CharT, _Traits>&
2363         operator>>(std::basic_istream<_CharT, _Traits>&,
2364                    std::chi_squared_distribution<_RealType1>&);
2365
2366     private:
2367       param_type _M_param;
2368
2369       std::gamma_distribution<result_type> _M_gd;
2370     };
2371
2372
2373   /**
2374    * @brief A cauchy_distribution random number distribution.
2375    *
2376    * The formula for the normal probability mass function is
2377    * @f$ p(x|a,b) = (\pi b (1 + (\frac{x-a}{b})^2))^{-1} @f$
2378    */
2379   template<typename _RealType = double>
2380     class cauchy_distribution
2381     {
2382       static_assert(std::is_floating_point<_RealType>::value,
2383                     "template argument not a floating point type");
2384
2385     public:
2386       /** The type of the range of the distribution. */
2387       typedef _RealType result_type;
2388       /** Parameter type. */
2389       struct param_type
2390       {
2391         typedef cauchy_distribution<_RealType> distribution_type;
2392
2393         explicit
2394         param_type(_RealType __a = _RealType(0),
2395                    _RealType __b = _RealType(1))
2396         : _M_a(__a), _M_b(__b)
2397         { }
2398
2399         _RealType
2400         a() const
2401         { return _M_a; }
2402
2403         _RealType
2404         b() const
2405         { return _M_b; }
2406
2407       private:
2408         _RealType _M_a;
2409         _RealType _M_b;
2410       };
2411
2412       explicit
2413       cauchy_distribution(_RealType __a = _RealType(0),
2414                           _RealType __b = _RealType(1))
2415       : _M_param(__a, __b)
2416       { }
2417
2418       explicit
2419       cauchy_distribution(const param_type& __p)
2420       : _M_param(__p)
2421       { }
2422
2423       /**
2424        * @brief Resets the distribution state.
2425        */
2426       void
2427       reset()
2428       { }
2429
2430       /**
2431        *
2432        */
2433       _RealType
2434       a() const
2435       { return _M_param.a(); }
2436
2437       _RealType
2438       b() const
2439       { return _M_param.b(); }
2440
2441       /**
2442        * @brief Returns the parameter set of the distribution.
2443        */
2444       param_type
2445       param() const
2446       { return _M_param; }
2447
2448       /**
2449        * @brief Sets the parameter set of the distribution.
2450        * @param __param The new parameter set of the distribution.
2451        */
2452       void
2453       param(const param_type& __param)
2454       { _M_param = __param; }
2455
2456       /**
2457        * @brief Returns the greatest lower bound value of the distribution.
2458        */
2459       result_type
2460       min() const
2461       { return std::numeric_limits<result_type>::min(); }
2462
2463       /**
2464        * @brief Returns the least upper bound value of the distribution.
2465        */
2466       result_type
2467       max() const
2468       { return std::numeric_limits<result_type>::max(); }
2469
2470       template<typename _UniformRandomNumberGenerator>
2471         result_type
2472         operator()(_UniformRandomNumberGenerator& __urng)
2473         { return this->operator()(__urng, this->param()); }
2474
2475       template<typename _UniformRandomNumberGenerator>
2476         result_type
2477         operator()(_UniformRandomNumberGenerator& __urng,
2478                    const param_type& __p);
2479
2480     private:
2481       param_type _M_param;
2482     };
2483
2484   /**
2485    * @brief Inserts a %cauchy_distribution random number distribution
2486    * @p __x into the output stream @p __os.
2487    *
2488    * @param __os An output stream.
2489    * @param __x  A %cauchy_distribution random number distribution.
2490    *
2491    * @returns The output stream with the state of @p __x inserted or in
2492    * an error state.
2493    */
2494   template<typename _RealType, typename _CharT, typename _Traits>
2495     std::basic_ostream<_CharT, _Traits>&
2496     operator<<(std::basic_ostream<_CharT, _Traits>&,
2497                const std::cauchy_distribution<_RealType>&);
2498
2499   /**
2500    * @brief Extracts a %cauchy_distribution random number distribution
2501    * @p __x from the input stream @p __is.
2502    *
2503    * @param __is An input stream.
2504    * @param __x A %cauchy_distribution random number
2505    *            generator engine.
2506    *
2507    * @returns The input stream with @p __x extracted or in an error state.
2508    */
2509   template<typename _RealType, typename _CharT, typename _Traits>
2510     std::basic_istream<_CharT, _Traits>&
2511     operator>>(std::basic_istream<_CharT, _Traits>&,
2512                std::cauchy_distribution<_RealType>&);
2513
2514
2515   /**
2516    * @brief A fisher_f_distribution random number distribution.
2517    *
2518    * The formula for the normal probability mass function is
2519    * @f$ p(x|m,n) = \frac{\Gamma((m+n)/2)}{\Gamma(m/2)\Gamma(n/2)}
2520    *                (\frac{m}{n})^{m/2} x^{(m/2)-1}
2521    *                (1 + \frac{mx}{n})^{-(m+n)/2} @f$
2522    */
2523   template<typename _RealType = double>
2524     class fisher_f_distribution
2525     {
2526       static_assert(std::is_floating_point<_RealType>::value,
2527                     "template argument not a floating point type");
2528
2529     public:
2530       /** The type of the range of the distribution. */
2531       typedef _RealType result_type;
2532       /** Parameter type. */
2533       struct param_type
2534       {
2535         typedef fisher_f_distribution<_RealType> distribution_type;
2536
2537         explicit
2538         param_type(_RealType __m = _RealType(1),
2539                    _RealType __n = _RealType(1))
2540         : _M_m(__m), _M_n(__n)
2541         { }
2542
2543         _RealType
2544         m() const
2545         { return _M_m; }
2546
2547         _RealType
2548         n() const
2549         { return _M_n; }
2550
2551       private:
2552         _RealType _M_m;
2553         _RealType _M_n;
2554       };
2555
2556       explicit
2557       fisher_f_distribution(_RealType __m = _RealType(1),
2558                             _RealType __n = _RealType(1))
2559       : _M_param(__m, __n), _M_gd_x(__m / 2), _M_gd_y(__n / 2)
2560       { }
2561
2562       explicit
2563       fisher_f_distribution(const param_type& __p)
2564       : _M_param(__p), _M_gd_x(__p.m() / 2), _M_gd_y(__p.n() / 2)
2565       { }
2566
2567       /**
2568        * @brief Resets the distribution state.
2569        */
2570       void
2571       reset()
2572       {
2573         _M_gd_x.reset();
2574         _M_gd_y.reset();
2575       }
2576
2577       /**
2578        *
2579        */
2580       _RealType
2581       m() const
2582       { return _M_param.m(); }
2583
2584       _RealType
2585       n() const
2586       { return _M_param.n(); }
2587
2588       /**
2589        * @brief Returns the parameter set of the distribution.
2590        */
2591       param_type
2592       param() const
2593       { return _M_param; }
2594
2595       /**
2596        * @brief Sets the parameter set of the distribution.
2597        * @param __param The new parameter set of the distribution.
2598        */
2599       void
2600       param(const param_type& __param)
2601       { _M_param = __param; }
2602
2603       /**
2604        * @brief Returns the greatest lower bound value of the distribution.
2605        */
2606       result_type
2607       min() const
2608       { return result_type(0); }
2609
2610       /**
2611        * @brief Returns the least upper bound value of the distribution.
2612        */
2613       result_type
2614       max() const
2615       { return std::numeric_limits<result_type>::max(); }
2616
2617       template<typename _UniformRandomNumberGenerator>
2618         result_type
2619         operator()(_UniformRandomNumberGenerator& __urng)
2620         { return (_M_gd_x(__urng) * n()) / (_M_gd_y(__urng) * m()); }
2621
2622       template<typename _UniformRandomNumberGenerator>
2623         result_type
2624         operator()(_UniformRandomNumberGenerator& __urng,
2625                    const param_type& __p)
2626         {
2627           typedef typename std::gamma_distribution<result_type>::param_type
2628             param_type;
2629           return ((_M_gd_x(__urng, param_type(__p.m() / 2)) * n())
2630                   / (_M_gd_y(__urng, param_type(__p.n() / 2)) * m()));
2631         }
2632
2633       /**
2634        * @brief Inserts a %fisher_f_distribution random number distribution
2635        * @p __x into the output stream @p __os.
2636        *
2637        * @param __os An output stream.
2638        * @param __x  A %fisher_f_distribution random number distribution.
2639        *
2640        * @returns The output stream with the state of @p __x inserted or in
2641        * an error state.
2642        */
2643       template<typename _RealType1, typename _CharT, typename _Traits>
2644         friend std::basic_ostream<_CharT, _Traits>&
2645         operator<<(std::basic_ostream<_CharT, _Traits>&,
2646                    const std::fisher_f_distribution<_RealType1>&);
2647
2648       /**
2649        * @brief Extracts a %fisher_f_distribution random number distribution
2650        * @p __x from the input stream @p __is.
2651        *
2652        * @param __is An input stream.
2653        * @param __x A %fisher_f_distribution random number
2654        *            generator engine.
2655        *
2656        * @returns The input stream with @p __x extracted or in an error state.
2657        */
2658       template<typename _RealType1, typename _CharT, typename _Traits>
2659         friend std::basic_istream<_CharT, _Traits>&
2660         operator>>(std::basic_istream<_CharT, _Traits>&,
2661                    std::fisher_f_distribution<_RealType1>&);
2662
2663     private:
2664       param_type _M_param;
2665
2666       std::gamma_distribution<result_type> _M_gd_x, _M_gd_y;
2667     };
2668
2669
2670   /**
2671    * @brief A student_t_distribution random number distribution.
2672    *
2673    * The formula for the normal probability mass function is
2674    * @f$ p(x|n) = \frac{1}{\sqrt(n\pi)} \frac{\Gamma((n+1)/2)}{\Gamma(n/2)}
2675    *              (1 + \frac{x^2}{n}) ^{-(n+1)/2} @f$
2676    */
2677   template<typename _RealType = double>
2678     class student_t_distribution
2679     {
2680       static_assert(std::is_floating_point<_RealType>::value,
2681                     "template argument not a floating point type");
2682
2683     public:
2684       /** The type of the range of the distribution. */
2685       typedef _RealType result_type;
2686       /** Parameter type. */
2687       struct param_type
2688       {
2689         typedef student_t_distribution<_RealType> distribution_type;
2690
2691         explicit
2692         param_type(_RealType __n = _RealType(1))
2693         : _M_n(__n)
2694         { }
2695
2696         _RealType
2697         n() const
2698         { return _M_n; }
2699
2700       private:
2701         _RealType _M_n;
2702       };
2703
2704       explicit
2705       student_t_distribution(_RealType __n = _RealType(1))
2706       : _M_param(__n), _M_nd(), _M_gd(__n / 2, 2)
2707       { }
2708
2709       explicit
2710       student_t_distribution(const param_type& __p)
2711       : _M_param(__p), _M_nd(), _M_gd(__p.n() / 2, 2)
2712       { }
2713
2714       /**
2715        * @brief Resets the distribution state.
2716        */
2717       void
2718       reset()
2719       {
2720         _M_nd.reset();
2721         _M_gd.reset();
2722       }
2723
2724       /**
2725        *
2726        */
2727       _RealType
2728       n() const
2729       { return _M_param.n(); }
2730
2731       /**
2732        * @brief Returns the parameter set of the distribution.
2733        */
2734       param_type
2735       param() const
2736       { return _M_param; }
2737
2738       /**
2739        * @brief Sets the parameter set of the distribution.
2740        * @param __param The new parameter set of the distribution.
2741        */
2742       void
2743       param(const param_type& __param)
2744       { _M_param = __param; }
2745
2746       /**
2747        * @brief Returns the greatest lower bound value of the distribution.
2748        */
2749       result_type
2750       min() const
2751       { return std::numeric_limits<result_type>::min(); }
2752
2753       /**
2754        * @brief Returns the least upper bound value of the distribution.
2755        */
2756       result_type
2757       max() const
2758       { return std::numeric_limits<result_type>::max(); }
2759
2760       template<typename _UniformRandomNumberGenerator>
2761         result_type
2762         operator()(_UniformRandomNumberGenerator& __urng)
2763         { return _M_nd(__urng) * std::sqrt(n() / _M_gd(__urng)); }
2764
2765       template<typename _UniformRandomNumberGenerator>
2766         result_type
2767         operator()(_UniformRandomNumberGenerator& __urng,
2768                    const param_type& __p)
2769         {
2770           typedef typename std::gamma_distribution<result_type>::param_type
2771             param_type;
2772
2773           const result_type __g = _M_gd(__urng, param_type(__p.n() / 2, 2));
2774           return _M_nd(__urng) * std::sqrt(__p.n() / __g);
2775         }
2776
2777       /**
2778        * @brief Inserts a %student_t_distribution random number distribution
2779        * @p __x into the output stream @p __os.
2780        *
2781        * @param __os An output stream.
2782        * @param __x  A %student_t_distribution random number distribution.
2783        *
2784        * @returns The output stream with the state of @p __x inserted or in
2785        * an error state.
2786        */
2787       template<typename _RealType1, typename _CharT, typename _Traits>
2788         friend std::basic_ostream<_CharT, _Traits>&
2789         operator<<(std::basic_ostream<_CharT, _Traits>&,
2790                    const std::student_t_distribution<_RealType1>&);
2791
2792       /**
2793        * @brief Extracts a %student_t_distribution random number distribution
2794        * @p __x from the input stream @p __is.
2795        *
2796        * @param __is An input stream.
2797        * @param __x A %student_t_distribution random number
2798        *            generator engine.
2799        *
2800        * @returns The input stream with @p __x extracted or in an error state.
2801        */
2802       template<typename _RealType1, typename _CharT, typename _Traits>
2803         friend std::basic_istream<_CharT, _Traits>&
2804         operator>>(std::basic_istream<_CharT, _Traits>&,
2805                    std::student_t_distribution<_RealType1>&);
2806
2807     private:
2808       param_type _M_param;
2809
2810       std::normal_distribution<result_type> _M_nd;
2811       std::gamma_distribution<result_type> _M_gd;
2812     };
2813
2814   /* @} */ // group std_random_distributions_normal
2815
2816   /**
2817    * @addtogroup std_random_distributions_bernoulli Bernoulli Distributions
2818    * @ingroup std_random_distributions
2819    * @{
2820    */
2821
2822   /**
2823    * @brief A Bernoulli random number distribution.
2824    *
2825    * Generates a sequence of true and false values with likelihood @f$ p @f$
2826    * that true will come up and @f$ (1 - p) @f$ that false will appear.
2827    */
2828   class bernoulli_distribution
2829   {
2830   public:
2831     /** The type of the range of the distribution. */
2832     typedef bool result_type;
2833     /** Parameter type. */
2834     struct param_type
2835     {
2836       typedef bernoulli_distribution distribution_type;
2837
2838       explicit
2839       param_type(double __p = 0.5)
2840       : _M_p(__p)
2841       {
2842         _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
2843       }
2844
2845       double
2846       p() const
2847       { return _M_p; }
2848
2849     private:
2850       double _M_p;
2851     };
2852
2853   public:
2854     /**
2855      * @brief Constructs a Bernoulli distribution with likelihood @p p.
2856      *
2857      * @param __p  [IN]  The likelihood of a true result being returned.
2858      *                   Must be in the interval @f$ [0, 1] @f$.
2859      */
2860     explicit
2861     bernoulli_distribution(double __p = 0.5)
2862     : _M_param(__p)
2863     { }
2864
2865     explicit
2866     bernoulli_distribution(const param_type& __p)
2867     : _M_param(__p)
2868     { }
2869
2870     /**
2871      * @brief Resets the distribution state.
2872      *
2873      * Does nothing for a Bernoulli distribution.
2874      */
2875     void
2876     reset() { }
2877
2878     /**
2879      * @brief Returns the @p p parameter of the distribution.
2880      */
2881     double
2882     p() const
2883     { return _M_param.p(); }
2884
2885     /**
2886      * @brief Returns the parameter set of the distribution.
2887      */
2888     param_type
2889     param() const
2890     { return _M_param; }
2891
2892     /**
2893      * @brief Sets the parameter set of the distribution.
2894      * @param __param The new parameter set of the distribution.
2895      */
2896     void
2897     param(const param_type& __param)
2898     { _M_param = __param; }
2899
2900     /**
2901      * @brief Returns the greatest lower bound value of the distribution.
2902      */
2903     result_type
2904     min() const
2905     { return std::numeric_limits<result_type>::min(); }
2906
2907     /**
2908      * @brief Returns the least upper bound value of the distribution.
2909      */
2910     result_type
2911     max() const
2912     { return std::numeric_limits<result_type>::max(); }
2913
2914     /**
2915      * @brief Returns the next value in the Bernoullian sequence.
2916      */
2917     template<typename _UniformRandomNumberGenerator>
2918       result_type
2919       operator()(_UniformRandomNumberGenerator& __urng)
2920       { return this->operator()(__urng, this->param()); }
2921
2922     template<typename _UniformRandomNumberGenerator>
2923       result_type
2924       operator()(_UniformRandomNumberGenerator& __urng,
2925                  const param_type& __p)
2926       {
2927         __detail::_Adaptor<_UniformRandomNumberGenerator, double>
2928           __aurng(__urng);
2929         if ((__aurng() - __aurng.min())
2930              < __p.p() * (__aurng.max() - __aurng.min()))
2931           return true;
2932         return false;
2933       }
2934
2935   private:
2936     param_type _M_param;
2937   };
2938
2939   /**
2940    * @brief Inserts a %bernoulli_distribution random number distribution
2941    * @p __x into the output stream @p __os.
2942    *
2943    * @param __os An output stream.
2944    * @param __x  A %bernoulli_distribution random number distribution.
2945    *
2946    * @returns The output stream with the state of @p __x inserted or in
2947    * an error state.
2948    */
2949   template<typename _CharT, typename _Traits>
2950     std::basic_ostream<_CharT, _Traits>&
2951     operator<<(std::basic_ostream<_CharT, _Traits>&,
2952                const std::bernoulli_distribution&);
2953
2954   /**
2955    * @brief Extracts a %bernoulli_distribution random number distribution
2956    * @p __x from the input stream @p __is.
2957    *
2958    * @param __is An input stream.
2959    * @param __x  A %bernoulli_distribution random number generator engine.
2960    *
2961    * @returns The input stream with @p __x extracted or in an error state.
2962    */
2963   template<typename _CharT, typename _Traits>
2964     std::basic_istream<_CharT, _Traits>&
2965     operator>>(std::basic_istream<_CharT, _Traits>& __is,
2966                std::bernoulli_distribution& __x)
2967     {
2968       double __p;
2969       __is >> __p;
2970       __x.param(bernoulli_distribution::param_type(__p));
2971       return __is;
2972     }
2973
2974
2975   /**
2976    * @brief A discrete binomial random number distribution.
2977    *
2978    * The formula for the binomial probability density function is
2979    * @f$ p(i|t,p) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
2980    * and @f$ p @f$ are the parameters of the distribution.
2981    */
2982   template<typename _IntType = int>
2983     class binomial_distribution
2984     {
2985       static_assert(std::is_integral<_IntType>::value,
2986                     "template argument not an integral type");
2987
2988     public:
2989       /** The type of the range of the distribution. */
2990       typedef _IntType result_type;
2991       /** Parameter type. */
2992       struct param_type
2993       {
2994         typedef binomial_distribution<_IntType> distribution_type;
2995         friend class binomial_distribution<_IntType>;
2996
2997         explicit
2998         param_type(_IntType __t = _IntType(1), double __p = 0.5)
2999         : _M_t(__t), _M_p(__p)
3000         {
3001           _GLIBCXX_DEBUG_ASSERT((_M_t >= _IntType(0))
3002                                 && (_M_p >= 0.0)
3003                                 && (_M_p <= 1.0));
3004           _M_initialize();
3005         }
3006
3007         _IntType
3008         t() const
3009         { return _M_t; }
3010
3011         double
3012         p() const
3013         { return _M_p; }
3014
3015       private:
3016         void
3017         _M_initialize();
3018
3019         _IntType _M_t;
3020         double _M_p;
3021
3022         double _M_q;
3023 #if _GLIBCXX_USE_C99_MATH_TR1
3024         double _M_d1, _M_d2, _M_s1, _M_s2, _M_c,
3025                _M_a1, _M_a123, _M_s, _M_lf, _M_lp1p;
3026 #endif
3027         bool   _M_easy;
3028       };
3029
3030       // constructors and member function
3031       explicit
3032       binomial_distribution(_IntType __t = _IntType(1),
3033                             double __p = 0.5)
3034       : _M_param(__t, __p), _M_nd()
3035       { }
3036
3037       explicit
3038       binomial_distribution(const param_type& __p)
3039       : _M_param(__p), _M_nd()
3040       { }
3041
3042       /**
3043        * @brief Resets the distribution state.
3044        */
3045       void
3046       reset()
3047       { _M_nd.reset(); }
3048
3049       /**
3050        * @brief Returns the distribution @p t parameter.
3051        */
3052       _IntType
3053       t() const
3054       { return _M_param.t(); }
3055
3056       /**
3057        * @brief Returns the distribution @p p parameter.
3058        */
3059       double
3060       p() const
3061       { return _M_param.p(); }
3062
3063       /**
3064        * @brief Returns the parameter set of the distribution.
3065        */
3066       param_type
3067       param() const
3068       { return _M_param; }
3069
3070       /**
3071        * @brief Sets the parameter set of the distribution.
3072        * @param __param The new parameter set of the distribution.
3073        */
3074       void
3075       param(const param_type& __param)
3076       { _M_param = __param; }
3077
3078       /**
3079        * @brief Returns the greatest lower bound value of the distribution.
3080        */
3081       result_type
3082       min() const
3083       { return 0; }
3084
3085       /**
3086        * @brief Returns the least upper bound value of the distribution.
3087        */
3088       result_type
3089       max() const
3090       { return _M_param.t(); }
3091
3092       template<typename _UniformRandomNumberGenerator>
3093         result_type
3094         operator()(_UniformRandomNumberGenerator& __urng)
3095         { return this->operator()(__urng, this->param()); }
3096
3097       template<typename _UniformRandomNumberGenerator>
3098         result_type
3099         operator()(_UniformRandomNumberGenerator& __urng,
3100                    const param_type& __p);
3101
3102       /**
3103        * @brief Inserts a %binomial_distribution random number distribution
3104        * @p __x into the output stream @p __os.
3105        *
3106        * @param __os An output stream.
3107        * @param __x  A %binomial_distribution random number distribution.
3108        *
3109        * @returns The output stream with the state of @p __x inserted or in
3110        * an error state.
3111        */
3112       template<typename _IntType1,
3113                typename _CharT, typename _Traits>
3114         friend std::basic_ostream<_CharT, _Traits>&
3115         operator<<(std::basic_ostream<_CharT, _Traits>&,
3116                    const std::binomial_distribution<_IntType1>&);
3117
3118       /**
3119        * @brief Extracts a %binomial_distribution random number distribution
3120        * @p __x from the input stream @p __is.
3121        *
3122        * @param __is An input stream.
3123        * @param __x  A %binomial_distribution random number generator engine.
3124        *
3125        * @returns The input stream with @p __x extracted or in an error
3126        *          state.
3127        */
3128       template<typename _IntType1,
3129                typename _CharT, typename _Traits>
3130         friend std::basic_istream<_CharT, _Traits>&
3131         operator>>(std::basic_istream<_CharT, _Traits>&,
3132                    std::binomial_distribution<_IntType1>&);
3133
3134     private:
3135       template<typename _UniformRandomNumberGenerator>
3136         result_type
3137         _M_waiting(_UniformRandomNumberGenerator& __urng, _IntType __t);
3138
3139       param_type _M_param;
3140
3141       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
3142       std::normal_distribution<double> _M_nd;
3143     };
3144
3145
3146   /**
3147    * @brief A discrete geometric random number distribution.
3148    *
3149    * The formula for the geometric probability density function is
3150    * @f$ p(i|p) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
3151    * distribution.
3152    */
3153   template<typename _IntType = int>
3154     class geometric_distribution
3155     {
3156       static_assert(std::is_integral<_IntType>::value,
3157                     "template argument not an integral type");
3158
3159     public:
3160       /** The type of the range of the distribution. */
3161       typedef _IntType  result_type;
3162       /** Parameter type. */
3163       struct param_type
3164       {
3165         typedef geometric_distribution<_IntType> distribution_type;
3166         friend class geometric_distribution<_IntType>;
3167
3168         explicit
3169         param_type(double __p = 0.5)
3170         : _M_p(__p)
3171         {
3172           _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0)
3173                              && (_M_p <= 1.0));
3174           _M_initialize();
3175         }
3176
3177         double
3178         p() const
3179         { return _M_p; }
3180
3181       private:
3182         void
3183         _M_initialize()
3184         { _M_log_p = std::log(_M_p); }
3185
3186         double _M_p;
3187
3188         double _M_log_p;
3189       };
3190
3191       // constructors and member function
3192       explicit
3193       geometric_distribution(double __p = 0.5)
3194       : _M_param(__p)
3195       { }
3196
3197       explicit
3198       geometric_distribution(const param_type& __p)
3199       : _M_param(__p)
3200       { }
3201
3202       /**
3203        * @brief Resets the distribution state.
3204        *
3205        * Does nothing for the geometric distribution.
3206        */
3207       void
3208       reset() { }
3209
3210       /**
3211        * @brief Returns the distribution parameter @p p.
3212        */
3213       double
3214       p() const
3215       { return _M_param.p(); }
3216
3217       /**
3218        * @brief Returns the parameter set of the distribution.
3219        */
3220       param_type
3221       param() const
3222       { return _M_param; }
3223
3224       /**
3225        * @brief Sets the parameter set of the distribution.
3226        * @param __param The new parameter set of the distribution.
3227        */
3228       void
3229       param(const param_type& __param)
3230       { _M_param = __param; }
3231
3232       /**
3233        * @brief Returns the greatest lower bound value of the distribution.
3234        */
3235       result_type
3236       min() const
3237       { return 0; }
3238
3239       /**
3240        * @brief Returns the least upper bound value of the distribution.
3241        */
3242       result_type
3243       max() const
3244       { return std::numeric_limits<result_type>::max(); }
3245
3246       template<typename _UniformRandomNumberGenerator>
3247         result_type
3248         operator()(_UniformRandomNumberGenerator& __urng)
3249         { return this->operator()(__urng, this->param()); }
3250
3251       template<typename _UniformRandomNumberGenerator>
3252         result_type
3253         operator()(_UniformRandomNumberGenerator& __urng,
3254                    const param_type& __p);
3255
3256     private:
3257       param_type _M_param;
3258     };
3259
3260   /**
3261    * @brief Inserts a %geometric_distribution random number distribution
3262    * @p __x into the output stream @p __os.
3263    *
3264    * @param __os An output stream.
3265    * @param __x  A %geometric_distribution random number distribution.
3266    *
3267    * @returns The output stream with the state of @p __x inserted or in
3268    * an error state.
3269    */
3270   template<typename _IntType,
3271            typename _CharT, typename _Traits>
3272     std::basic_ostream<_CharT, _Traits>&
3273     operator<<(std::basic_ostream<_CharT, _Traits>&,
3274                const std::geometric_distribution<_IntType>&);
3275
3276   /**
3277    * @brief Extracts a %geometric_distribution random number distribution
3278    * @p __x from the input stream @p __is.
3279    *
3280    * @param __is An input stream.
3281    * @param __x  A %geometric_distribution random number generator engine.
3282    *
3283    * @returns The input stream with @p __x extracted or in an error state.
3284    */
3285   template<typename _IntType,
3286            typename _CharT, typename _Traits>
3287     std::basic_istream<_CharT, _Traits>&
3288     operator>>(std::basic_istream<_CharT, _Traits>&,
3289                std::geometric_distribution<_IntType>&);
3290
3291
3292   /**
3293    * @brief A negative_binomial_distribution random number distribution.
3294    *
3295    * The formula for the negative binomial probability mass function is
3296    * @f$ p(i) = \binom{n}{i} p^i (1 - p)^{t - i} @f$ where @f$ t @f$
3297    * and @f$ p @f$ are the parameters of the distribution.
3298    */
3299   template<typename _IntType = int>
3300     class negative_binomial_distribution
3301     {
3302       static_assert(std::is_integral<_IntType>::value,
3303                     "template argument not an integral type");
3304
3305     public:
3306       /** The type of the range of the distribution. */
3307       typedef _IntType result_type;
3308       /** Parameter type. */
3309       struct param_type
3310       {
3311         typedef negative_binomial_distribution<_IntType> distribution_type;
3312
3313         explicit
3314         param_type(_IntType __k = 1, double __p = 0.5)
3315         : _M_k(__k), _M_p(__p)
3316         { }
3317
3318         _IntType
3319         k() const
3320         { return _M_k; }
3321
3322         double
3323         p() const
3324         { return _M_p; }
3325
3326       private:
3327         _IntType _M_k;
3328         double _M_p;
3329       };
3330
3331       explicit
3332       negative_binomial_distribution(_IntType __k = 1, double __p = 0.5)
3333       : _M_param(__k, __p), _M_gd(__k, __p / (1.0 - __p))
3334       { }
3335
3336       explicit
3337       negative_binomial_distribution(const param_type& __p)
3338       : _M_param(__p), _M_gd(__p.k(), __p.p() / (1.0 - __p.p()))
3339       { }
3340
3341       /**
3342        * @brief Resets the distribution state.
3343        */
3344       void
3345       reset()
3346       { _M_gd.reset(); }
3347
3348       /**
3349        * @brief Return the @f$ k @f$ parameter of the distribution.
3350        */
3351       _IntType
3352       k() const
3353       { return _M_param.k(); }
3354
3355       /**
3356        * @brief Return the @f$ p @f$ parameter of the distribution.
3357        */
3358       double
3359       p() const
3360       { return _M_param.p(); }
3361
3362       /**
3363        * @brief Returns the parameter set of the distribution.
3364        */
3365       param_type
3366       param() const
3367       { return _M_param; }
3368
3369       /**
3370        * @brief Sets the parameter set of the distribution.
3371        * @param __param The new parameter set of the distribution.
3372        */
3373       void
3374       param(const param_type& __param)
3375       { _M_param = __param; }
3376
3377       /**
3378        * @brief Returns the greatest lower bound value of the distribution.
3379        */
3380       result_type
3381       min() const
3382       { return result_type(0); }
3383
3384       /**
3385        * @brief Returns the least upper bound value of the distribution.
3386        */
3387       result_type
3388       max() const
3389       { return std::numeric_limits<result_type>::max(); }
3390
3391       template<typename _UniformRandomNumberGenerator>
3392         result_type
3393         operator()(_UniformRandomNumberGenerator& __urng);
3394
3395       template<typename _UniformRandomNumberGenerator>
3396         result_type
3397         operator()(_UniformRandomNumberGenerator& __urng,
3398                    const param_type& __p);
3399
3400       /**
3401        * @brief Inserts a %negative_binomial_distribution random
3402        *        number distribution @p __x into the output stream @p __os.
3403        *
3404        * @param __os An output stream.
3405        * @param __x  A %negative_binomial_distribution random number
3406        *             distribution.
3407        *
3408        * @returns The output stream with the state of @p __x inserted or in
3409        *          an error state.
3410        */
3411       template<typename _IntType1, typename _CharT, typename _Traits>
3412         friend std::basic_ostream<_CharT, _Traits>&
3413         operator<<(std::basic_ostream<_CharT, _Traits>&,
3414                    const std::negative_binomial_distribution<_IntType1>&);
3415
3416       /**
3417        * @brief Extracts a %negative_binomial_distribution random number
3418        *        distribution @p __x from the input stream @p __is.
3419        *
3420        * @param __is An input stream.
3421        * @param __x A %negative_binomial_distribution random number
3422        *            generator engine.
3423        *
3424        * @returns The input stream with @p __x extracted or in an error state.
3425        */
3426       template<typename _IntType1, typename _CharT, typename _Traits>
3427         friend std::basic_istream<_CharT, _Traits>&
3428         operator>>(std::basic_istream<_CharT, _Traits>&,
3429                    std::negative_binomial_distribution<_IntType1>&);
3430
3431     private:
3432       param_type _M_param;
3433
3434       std::gamma_distribution<double> _M_gd;
3435     };
3436
3437   /* @} */ // group std_random_distributions_bernoulli
3438
3439   /**
3440    * @addtogroup std_random_distributions_poisson Poisson Distributions
3441    * @ingroup std_random_distributions
3442    * @{
3443    */
3444
3445   /**
3446    * @brief A discrete Poisson random number distribution.
3447    *
3448    * The formula for the Poisson probability density function is
3449    * @f$ p(i|\mu) = \frac{\mu^i}{i!} e^{-\mu} @f$ where @f$ \mu @f$ is the
3450    * parameter of the distribution.
3451    */
3452   template<typename _IntType = int>
3453     class poisson_distribution
3454     {
3455       static_assert(std::is_integral<_IntType>::value,
3456                     "template argument not an integral type");
3457
3458     public:
3459       /** The type of the range of the distribution. */
3460       typedef _IntType  result_type;
3461       /** Parameter type. */
3462       struct param_type
3463       {
3464         typedef poisson_distribution<_IntType> distribution_type;
3465         friend class poisson_distribution<_IntType>;
3466
3467         explicit
3468         param_type(double __mean = 1.0)
3469         : _M_mean(__mean)
3470         {
3471           _GLIBCXX_DEBUG_ASSERT(_M_mean > 0.0);
3472           _M_initialize();
3473         }
3474
3475         double
3476         mean() const
3477         { return _M_mean; }
3478
3479       private:
3480         // Hosts either log(mean) or the threshold of the simple method.
3481         void
3482         _M_initialize();
3483
3484         double _M_mean;
3485
3486         double _M_lm_thr;
3487 #if _GLIBCXX_USE_C99_MATH_TR1
3488         double _M_lfm, _M_sm, _M_d, _M_scx, _M_1cx, _M_c2b, _M_cb;
3489 #endif
3490       };
3491
3492       // constructors and member function
3493       explicit
3494       poisson_distribution(double __mean = 1.0)
3495       : _M_param(__mean), _M_nd()
3496       { }
3497
3498       explicit
3499       poisson_distribution(const param_type& __p)
3500       : _M_param(__p), _M_nd()
3501       { }
3502
3503       /**
3504        * @brief Resets the distribution state.
3505        */
3506       void
3507       reset()
3508       { _M_nd.reset(); }
3509
3510       /**
3511        * @brief Returns the distribution parameter @p mean.
3512        */
3513       double
3514       mean() const
3515       { return _M_param.mean(); }
3516
3517       /**
3518        * @brief Returns the parameter set of the distribution.
3519        */
3520       param_type
3521       param() const
3522       { return _M_param; }
3523
3524       /**
3525        * @brief Sets the parameter set of the distribution.
3526        * @param __param The new parameter set of the distribution.
3527        */
3528       void
3529       param(const param_type& __param)
3530       { _M_param = __param; }
3531
3532       /**
3533        * @brief Returns the greatest lower bound value of the distribution.
3534        */
3535       result_type
3536       min() const
3537       { return 0; }
3538
3539       /**
3540        * @brief Returns the least upper bound value of the distribution.
3541        */
3542       result_type
3543       max() const
3544       { return std::numeric_limits<result_type>::max(); }
3545
3546       template<typename _UniformRandomNumberGenerator>
3547         result_type
3548         operator()(_UniformRandomNumberGenerator& __urng)
3549         { return this->operator()(__urng, this->param()); }
3550
3551       template<typename _UniformRandomNumberGenerator>
3552         result_type
3553         operator()(_UniformRandomNumberGenerator& __urng,
3554                    const param_type& __p);
3555
3556       /**
3557        * @brief Inserts a %poisson_distribution random number distribution
3558        * @p __x into the output stream @p __os.
3559        *
3560        * @param __os An output stream.
3561        * @param __x  A %poisson_distribution random number distribution.
3562        *
3563        * @returns The output stream with the state of @p __x inserted or in
3564        * an error state.
3565        */
3566       template<typename _IntType1, typename _CharT, typename _Traits>
3567         friend std::basic_ostream<_CharT, _Traits>&
3568         operator<<(std::basic_ostream<_CharT, _Traits>&,
3569                    const std::poisson_distribution<_IntType1>&);
3570
3571       /**
3572        * @brief Extracts a %poisson_distribution random number distribution
3573        * @p __x from the input stream @p __is.
3574        *
3575        * @param __is An input stream.
3576        * @param __x  A %poisson_distribution random number generator engine.
3577        *
3578        * @returns The input stream with @p __x extracted or in an error
3579        *          state.
3580        */
3581       template<typename _IntType1, typename _CharT, typename _Traits>
3582         friend std::basic_istream<_CharT, _Traits>&
3583         operator>>(std::basic_istream<_CharT, _Traits>&,
3584                    std::poisson_distribution<_IntType1>&);
3585
3586     private:
3587       param_type _M_param;
3588
3589       // NB: Unused when _GLIBCXX_USE_C99_MATH_TR1 is undefined.
3590       std::normal_distribution<double> _M_nd;
3591     };
3592
3593   /**
3594    * @brief An exponential continuous distribution for random numbers.
3595    *
3596    * The formula for the exponential probability density function is
3597    * @f$ p(x|\lambda) = \lambda e^{-\lambda x} @f$.
3598    *
3599    * <table border=1 cellpadding=10 cellspacing=0>
3600    * <caption align=top>Distribution Statistics</caption>
3601    * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
3602    * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
3603    * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
3604    * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
3605    * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
3606    * </table>
3607    */
3608   template<typename _RealType = double>
3609     class exponential_distribution
3610     {
3611       static_assert(std::is_floating_point<_RealType>::value,
3612                     "template argument not a floating point type");
3613
3614     public:
3615       /** The type of the range of the distribution. */
3616       typedef _RealType result_type;
3617       /** Parameter type. */
3618       struct param_type
3619       {
3620         typedef exponential_distribution<_RealType> distribution_type;
3621
3622         explicit
3623         param_type(_RealType __lambda = _RealType(1))
3624         : _M_lambda(__lambda)
3625         {
3626           _GLIBCXX_DEBUG_ASSERT(_M_lambda > _RealType(0));
3627         }
3628
3629         _RealType
3630         lambda() const
3631         { return _M_lambda; }
3632
3633       private:
3634         _RealType _M_lambda;
3635       };
3636
3637     public:
3638       /**
3639        * @brief Constructs an exponential distribution with inverse scale
3640        *        parameter @f$ \lambda @f$.
3641        */
3642       explicit
3643       exponential_distribution(const result_type& __lambda = result_type(1))
3644       : _M_param(__lambda)
3645       { }
3646
3647       explicit
3648       exponential_distribution(const param_type& __p)
3649       : _M_param(__p)
3650       { }
3651
3652       /**
3653        * @brief Resets the distribution state.
3654        *
3655        * Has no effect on exponential distributions.
3656        */
3657       void
3658       reset() { }
3659
3660       /**
3661        * @brief Returns the inverse scale parameter of the distribution.
3662        */
3663       _RealType
3664       lambda() const
3665       { return _M_param.lambda(); }
3666
3667       /**
3668        * @brief Returns the parameter set of the distribution.
3669        */
3670       param_type
3671       param() const
3672       { return _M_param; }
3673
3674       /**
3675        * @brief Sets the parameter set of the distribution.
3676        * @param __param The new parameter set of the distribution.
3677        */
3678       void
3679       param(const param_type& __param)
3680       { _M_param = __param; }
3681
3682       /**
3683        * @brief Returns the greatest lower bound value of the distribution.
3684        */
3685       result_type
3686       min() const
3687       { return result_type(0); }
3688
3689       /**
3690        * @brief Returns the least upper bound value of the distribution.
3691        */
3692       result_type
3693       max() const
3694       { return std::numeric_limits<result_type>::max(); }
3695
3696       template<typename _UniformRandomNumberGenerator>
3697         result_type
3698         operator()(_UniformRandomNumberGenerator& __urng)
3699         { return this->operator()(__urng, this->param()); }
3700
3701       template<typename _UniformRandomNumberGenerator>
3702         result_type
3703         operator()(_UniformRandomNumberGenerator& __urng,
3704                    const param_type& __p)
3705         {
3706           __detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
3707             __aurng(__urng);
3708           return -std::log(__aurng()) / __p.lambda();
3709         }
3710
3711     private:
3712       param_type _M_param;
3713     };
3714
3715   /**
3716    * @brief Inserts a %exponential_distribution random number distribution
3717    * @p __x into the output stream @p __os.
3718    *
3719    * @param __os An output stream.
3720    * @param __x  A %exponential_distribution random number distribution.
3721    *
3722    * @returns The output stream with the state of @p __x inserted or in
3723    * an error state.
3724    */
3725   template<typename _RealType, typename _CharT, typename _Traits>
3726     std::basic_ostream<_CharT, _Traits>&
3727     operator<<(std::basic_ostream<_CharT, _Traits>&,
3728                const std::exponential_distribution<_RealType>&);
3729
3730   /**
3731    * @brief Extracts a %exponential_distribution random number distribution
3732    * @p __x from the input stream @p __is.
3733    *
3734    * @param __is An input stream.
3735    * @param __x A %exponential_distribution random number
3736    *            generator engine.
3737    *
3738    * @returns The input stream with @p __x extracted or in an error state.
3739    */
3740   template<typename _RealType, typename _CharT, typename _Traits>
3741     std::basic_istream<_CharT, _Traits>&
3742     operator>>(std::basic_istream<_CharT, _Traits>&,
3743                std::exponential_distribution<_RealType>&);
3744
3745
3746   /**
3747    * @brief A weibull_distribution random number distribution.
3748    *
3749    * The formula for the normal probability density function is
3750    * @f$ p(x|\alpha,\beta) = \frac{a}{b} (frac{x}{b})^{a-1}
3751    *                         \exp{(-(frac{x}{b})^a)} @f$.
3752    */
3753   template<typename _RealType = double>
3754     class weibull_distribution
3755     {
3756       static_assert(std::is_floating_point<_RealType>::value,
3757                     "template argument not a floating point type");
3758
3759     public:
3760       /** The type of the range of the distribution. */
3761       typedef _RealType result_type;
3762       /** Parameter type. */
3763       struct param_type
3764       {
3765         typedef weibull_distribution<_RealType> distribution_type;
3766
3767         explicit
3768         param_type(_RealType __a = _RealType(1),
3769                    _RealType __b = _RealType(1))
3770         : _M_a(__a), _M_b(__b)
3771         { }
3772
3773         _RealType
3774         a() const
3775         { return _M_a; }
3776
3777         _RealType
3778         b() const
3779         { return _M_b; }
3780
3781       private:
3782         _RealType _M_a;
3783         _RealType _M_b;
3784       };
3785
3786       explicit
3787       weibull_distribution(_RealType __a = _RealType(1),
3788                            _RealType __b = _RealType(1))
3789       : _M_param(__a, __b)
3790       { }
3791
3792       explicit
3793       weibull_distribution(const param_type& __p)
3794       : _M_param(__p)
3795       { }
3796
3797       /**
3798        * @brief Resets the distribution state.
3799        */
3800       void
3801       reset()
3802       { }
3803
3804       /**
3805        * @brief Return the @f$ a @f$ parameter of the distribution.
3806        */
3807       _RealType
3808       a() const
3809       { return _M_param.a(); }
3810
3811       /**
3812        * @brief Return the @f$ b @f$ parameter of the distribution.
3813        */
3814       _RealType
3815       b() const
3816       { return _M_param.b(); }
3817
3818       /**
3819        * @brief Returns the parameter set of the distribution.
3820        */
3821       param_type
3822       param() const
3823       { return _M_param; }
3824
3825       /**
3826        * @brief Sets the parameter set of the distribution.
3827        * @param __param The new parameter set of the distribution.
3828        */
3829       void
3830       param(const param_type& __param)
3831       { _M_param = __param; }
3832
3833       /**
3834        * @brief Returns the greatest lower bound value of the distribution.
3835        */
3836       result_type
3837       min() const
3838       { return result_type(0); }
3839
3840       /**
3841        * @brief Returns the least upper bound value of the distribution.
3842        */
3843       result_type
3844       max() const
3845       { return std::numeric_limits<result_type>::max(); }
3846
3847       template<typename _UniformRandomNumberGenerator>
3848         result_type
3849         operator()(_UniformRandomNumberGenerator& __urng)
3850         { return this->operator()(__urng, this->param()); }
3851
3852       template<typename _UniformRandomNumberGenerator>
3853         result_type
3854         operator()(_UniformRandomNumberGenerator& __urng,
3855                    const param_type& __p);
3856
3857     private:
3858       param_type _M_param;
3859     };
3860
3861   /**
3862    * @brief Inserts a %weibull_distribution random number distribution
3863    * @p __x into the output stream @p __os.
3864    *
3865    * @param __os An output stream.
3866    * @param __x  A %weibull_distribution random number distribution.
3867    *
3868    * @returns The output stream with the state of @p __x inserted or in
3869    * an error state.
3870    */
3871   template<typename _RealType, typename _CharT, typename _Traits>
3872     std::basic_ostream<_CharT, _Traits>&
3873     operator<<(std::basic_ostream<_CharT, _Traits>&,
3874                const std::weibull_distribution<_RealType>&);
3875
3876   /**
3877    * @brief Extracts a %weibull_distribution random number distribution
3878    * @p __x from the input stream @p __is.
3879    *
3880    * @param __is An input stream.
3881    * @param __x A %weibull_distribution random number
3882    *            generator engine.
3883    *
3884    * @returns The input stream with @p __x extracted or in an error state.
3885    */
3886   template<typename _RealType, typename _CharT, typename _Traits>
3887     std::basic_istream<_CharT, _Traits>&
3888     operator>>(std::basic_istream<_CharT, _Traits>&,
3889                std::weibull_distribution<_RealType>&);
3890
3891
3892   /**
3893    * @brief A extreme_value_distribution random number distribution.
3894    *
3895    * The formula for the normal probability mass function is
3896    * @f$ p(x|a,b) = \frac{1}{b}
3897    *                \exp( \frac{a-x}{b} - \exp(\frac{a-x}{b})) @f$
3898    */
3899   template<typename _RealType = double>
3900     class extreme_value_distribution
3901     {
3902       static_assert(std::is_floating_point<_RealType>::value,
3903                     "template argument not a floating point type");
3904
3905     public:
3906       /** The type of the range of the distribution. */
3907       typedef _RealType result_type;
3908       /** Parameter type. */
3909       struct param_type
3910       {
3911         typedef extreme_value_distribution<_RealType> distribution_type;
3912
3913         explicit
3914         param_type(_RealType __a = _RealType(0),
3915                    _RealType __b = _RealType(1))
3916         : _M_a(__a), _M_b(__b)
3917         { }
3918
3919         _RealType
3920         a() const
3921         { return _M_a; }
3922
3923         _RealType
3924         b() const
3925         { return _M_b; }
3926
3927       private:
3928         _RealType _M_a;
3929         _RealType _M_b;
3930       };
3931
3932       explicit
3933       extreme_value_distribution(_RealType __a = _RealType(0),
3934                                  _RealType __b = _RealType(1))
3935       : _M_param(__a, __b)
3936       { }
3937
3938       explicit
3939       extreme_value_distribution(const param_type& __p)
3940       : _M_param(__p)
3941       { }
3942
3943       /**
3944        * @brief Resets the distribution state.
3945        */
3946       void
3947       reset()
3948       { }
3949
3950       /**
3951        * @brief Return the @f$ a @f$ parameter of the distribution.
3952        */
3953       _RealType
3954       a() const
3955       { return _M_param.a(); }
3956
3957       /**
3958        * @brief Return the @f$ b @f$ parameter of the distribution.
3959        */
3960       _RealType
3961       b() const
3962       { return _M_param.b(); }
3963
3964       /**
3965        * @brief Returns the parameter set of the distribution.
3966        */
3967       param_type
3968       param() const
3969       { return _M_param; }
3970
3971       /**
3972        * @brief Sets the parameter set of the distribution.
3973        * @param __param The new parameter set of the distribution.
3974        */
3975       void
3976       param(const param_type& __param)
3977       { _M_param = __param; }
3978
3979       /**
3980        * @brief Returns the greatest lower bound value of the distribution.
3981        */
3982       result_type
3983       min() const
3984       { return std::numeric_limits<result_type>::min(); }
3985
3986       /**
3987        * @brief Returns the least upper bound value of the distribution.
3988        */
3989       result_type
3990       max() const
3991       { return std::numeric_limits<result_type>::max(); }
3992
3993       template<typename _UniformRandomNumberGenerator>
3994         result_type
3995         operator()(_UniformRandomNumberGenerator& __urng)
3996         { return this->operator()(__urng, this->param()); }
3997
3998       template<typename _UniformRandomNumberGenerator>
3999         result_type
4000         operator()(_UniformRandomNumberGenerator& __urng,
4001                    const param_type& __p);
4002
4003     private:
4004       param_type _M_param;
4005     };
4006
4007   /**
4008    * @brief Inserts a %extreme_value_distribution random number distribution
4009    * @p __x into the output stream @p __os.
4010    *
4011    * @param __os An output stream.
4012    * @param __x  A %extreme_value_distribution random number distribution.
4013    *
4014    * @returns The output stream with the state of @p __x inserted or in
4015    * an error state.
4016    */
4017   template<typename _RealType, typename _CharT, typename _Traits>
4018     std::basic_ostream<_CharT, _Traits>&
4019     operator<<(std::basic_ostream<_CharT, _Traits>&,
4020                const std::extreme_value_distribution<_RealType>&);
4021
4022   /**
4023    * @brief Extracts a %extreme_value_distribution random number
4024    *        distribution @p __x from the input stream @p __is.
4025    *
4026    * @param __is An input stream.
4027    * @param __x A %extreme_value_distribution random number
4028    *            generator engine.
4029    *
4030    * @returns The input stream with @p __x extracted or in an error state.
4031    */
4032   template<typename _RealType, typename _CharT, typename _Traits>
4033     std::basic_istream<_CharT, _Traits>&
4034     operator>>(std::basic_istream<_CharT, _Traits>&,
4035                std::extreme_value_distribution<_RealType>&);
4036
4037
4038   /**
4039    * @brief A discrete_distribution random number distribution.
4040    *
4041    * The formula for the discrete probability mass function is
4042    *
4043    */
4044   template<typename _IntType = int>
4045     class discrete_distribution
4046     {
4047       static_assert(std::is_integral<_IntType>::value,
4048                     "template argument not an integral type");
4049
4050     public:
4051       /** The type of the range of the distribution. */
4052       typedef _IntType result_type;
4053       /** Parameter type. */
4054       struct param_type
4055       {
4056         typedef discrete_distribution<_IntType> distribution_type;
4057         friend class discrete_distribution<_IntType>;
4058
4059         param_type()
4060         : _M_prob(), _M_cp()
4061         { _M_initialize(); }
4062
4063         template<typename _InputIterator>
4064           param_type(_InputIterator __wbegin,
4065                      _InputIterator __wend)
4066           : _M_prob(__wbegin, __wend), _M_cp()
4067           { _M_initialize(); }
4068
4069         param_type(initializer_list<double> __wil)
4070         : _M_prob(__wil.begin(), __wil.end()), _M_cp()
4071         { _M_initialize(); }
4072
4073         template<typename _Func>
4074           param_type(size_t __nw, double __xmin, double __xmax,
4075                      _Func __fw);
4076
4077         std::vector<double>
4078         probabilities() const
4079         { return _M_prob; }
4080
4081       private:
4082         void
4083         _M_initialize();
4084
4085         std::vector<double> _M_prob;
4086         std::vector<double> _M_cp;
4087       };
4088
4089       discrete_distribution()
4090       : _M_param()
4091       { }
4092
4093       template<typename _InputIterator>
4094         discrete_distribution(_InputIterator __wbegin,
4095                               _InputIterator __wend)
4096         : _M_param(__wbegin, __wend)
4097         { }
4098
4099       discrete_distribution(initializer_list<double> __wl)
4100       : _M_param(__wl)
4101       { }
4102
4103       template<typename _Func>
4104         discrete_distribution(size_t __nw, double __xmin, double __xmax,
4105                               _Func __fw)
4106         : _M_param(__nw, __xmin, __xmax, __fw)
4107         { }
4108
4109       explicit
4110       discrete_distribution(const param_type& __p)
4111       : _M_param(__p)
4112       { }
4113
4114       /**
4115        * @brief Resets the distribution state.
4116        */
4117       void
4118       reset()
4119       { }
4120
4121       /**
4122        * @brief Returns the probabilities of the distribution.
4123        */
4124       std::vector<double>
4125       probabilities() const
4126       { return _M_param.probabilities(); }
4127
4128       /**
4129        * @brief Returns the parameter set of the distribution.
4130        */
4131       param_type
4132       param() const
4133       { return _M_param; }
4134
4135       /**
4136        * @brief Sets the parameter set of the distribution.
4137        * @param __param The new parameter set of the distribution.
4138        */
4139       void
4140       param(const param_type& __param)
4141       { _M_param = __param; }
4142
4143       /**
4144        * @brief Returns the greatest lower bound value of the distribution.
4145        */
4146       result_type
4147       min() const
4148       { return result_type(0); }
4149
4150       /**
4151        * @brief Returns the least upper bound value of the distribution.
4152        */
4153       result_type
4154       max() const
4155       { return this->_M_param._M_prob.size() - 1; }
4156
4157       template<typename _UniformRandomNumberGenerator>
4158         result_type
4159         operator()(_UniformRandomNumberGenerator& __urng)
4160         { return this->operator()(__urng, this->param()); }
4161
4162       template<typename _UniformRandomNumberGenerator>
4163         result_type
4164         operator()(_UniformRandomNumberGenerator& __urng,
4165                    const param_type& __p);
4166
4167       /**
4168        * @brief Inserts a %discrete_distribution random number distribution
4169        * @p __x into the output stream @p __os.
4170        *
4171        * @param __os An output stream.
4172        * @param __x  A %discrete_distribution random number distribution.
4173        *
4174        * @returns The output stream with the state of @p __x inserted or in
4175        * an error state.
4176        */
4177       template<typename _IntType1, typename _CharT, typename _Traits>
4178         friend std::basic_ostream<_CharT, _Traits>&
4179         operator<<(std::basic_ostream<_CharT, _Traits>&,
4180                    const std::discrete_distribution<_IntType1>&);
4181
4182       /**
4183        * @brief Extracts a %discrete_distribution random number distribution
4184        * @p __x from the input stream @p __is.
4185        *
4186        * @param __is An input stream.
4187        * @param __x A %discrete_distribution random number
4188        *            generator engine.
4189        *
4190        * @returns The input stream with @p __x extracted or in an error
4191        *          state.
4192        */
4193       template<typename _IntType1, typename _CharT, typename _Traits>
4194         friend std::basic_istream<_CharT, _Traits>&
4195         operator>>(std::basic_istream<_CharT, _Traits>&,
4196                    std::discrete_distribution<_IntType1>&);
4197
4198     private:
4199       param_type _M_param;
4200     };
4201
4202
4203   /**
4204    * @brief A piecewise_constant_distribution random number distribution.
4205    *
4206    * The formula for the piecewise constant probability mass function is
4207    *
4208    */
4209   template<typename _RealType = double>
4210     class piecewise_constant_distribution
4211     {
4212       static_assert(std::is_floating_point<_RealType>::value,
4213                     "template argument not a floating point type");
4214
4215     public:
4216       /** The type of the range of the distribution. */
4217       typedef _RealType result_type;
4218       /** Parameter type. */
4219       struct param_type
4220       {
4221         typedef piecewise_constant_distribution<_RealType> distribution_type;
4222         friend class piecewise_constant_distribution<_RealType>;
4223
4224         param_type()
4225         : _M_int(), _M_den(), _M_cp()
4226         { _M_initialize(); }
4227
4228         template<typename _InputIteratorB, typename _InputIteratorW>
4229           param_type(_InputIteratorB __bfirst,
4230                      _InputIteratorB __bend,
4231                      _InputIteratorW __wbegin);
4232
4233         template<typename _Func>
4234           param_type(initializer_list<_RealType> __bi, _Func __fw);
4235
4236         template<typename _Func>
4237           param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
4238                      _Func __fw);
4239
4240         std::vector<_RealType>
4241         intervals() const
4242         { return _M_int; }
4243
4244         std::vector<double>
4245         densities() const
4246         { return _M_den; }
4247
4248       private:
4249         void
4250         _M_initialize();
4251
4252         std::vector<_RealType> _M_int;
4253         std::vector<double> _M_den;
4254         std::vector<double> _M_cp;
4255       };
4256
4257       explicit
4258       piecewise_constant_distribution()
4259       : _M_param()
4260       { }
4261
4262       template<typename _InputIteratorB, typename _InputIteratorW>
4263         piecewise_constant_distribution(_InputIteratorB __bfirst,
4264                                         _InputIteratorB __bend,
4265                                         _InputIteratorW __wbegin)
4266         : _M_param(__bfirst, __bend, __wbegin)
4267         { }
4268
4269       template<typename _Func>
4270         piecewise_constant_distribution(initializer_list<_RealType> __bl,
4271                                         _Func __fw)
4272         : _M_param(__bl, __fw)
4273         { }
4274
4275       template<typename _Func>
4276         piecewise_constant_distribution(size_t __nw,
4277                                         _RealType __xmin, _RealType __xmax,
4278                                         _Func __fw)
4279         : _M_param(__nw, __xmin, __xmax, __fw)
4280         { }
4281
4282       explicit
4283       piecewise_constant_distribution(const param_type& __p)
4284       : _M_param(__p)
4285       { }
4286
4287       /**
4288        * @brief Resets the distribution state.
4289        */
4290       void
4291       reset()
4292       { }
4293
4294       /**
4295        * @brief Returns a vector of the intervals.
4296        */
4297       std::vector<_RealType>
4298       intervals() const
4299       { return _M_param.intervals(); }
4300
4301       /**
4302        * @brief Returns a vector of the probability densities.
4303        */
4304       std::vector<double>
4305       densities() const
4306       { return _M_param.densities(); }
4307
4308       /**
4309        * @brief Returns the parameter set of the distribution.
4310        */
4311       param_type
4312       param() const
4313       { return _M_param; }
4314
4315       /**
4316        * @brief Sets the parameter set of the distribution.
4317        * @param __param The new parameter set of the distribution.
4318        */
4319       void
4320       param(const param_type& __param)
4321       { _M_param = __param; }
4322
4323       /**
4324        * @brief Returns the greatest lower bound value of the distribution.
4325        */
4326       result_type
4327       min() const
4328       { return this->_M_param._M_int.front(); }
4329
4330       /**
4331        * @brief Returns the least upper bound value of the distribution.
4332        */
4333       result_type
4334       max() const
4335       { return this->_M_param._M_int.back(); }
4336
4337       template<typename _UniformRandomNumberGenerator>
4338         result_type
4339         operator()(_UniformRandomNumberGenerator& __urng)
4340         { return this->operator()(__urng, this->param()); }
4341
4342       template<typename _UniformRandomNumberGenerator>
4343         result_type
4344         operator()(_UniformRandomNumberGenerator& __urng,
4345                    const param_type& __p);
4346
4347       /**
4348        * @brief Inserts a %piecewise_constan_distribution random
4349        *        number distribution @p __x into the output stream @p __os.
4350        *
4351        * @param __os An output stream.
4352        * @param __x  A %piecewise_constan_distribution random number
4353        *             distribution.
4354        *
4355        * @returns The output stream with the state of @p __x inserted or in
4356        * an error state.
4357        */
4358       template<typename _RealType1, typename _CharT, typename _Traits>
4359         friend std::basic_ostream<_CharT, _Traits>&
4360         operator<<(std::basic_ostream<_CharT, _Traits>&,
4361                    const std::piecewise_constant_distribution<_RealType1>&);
4362
4363       /**
4364        * @brief Extracts a %piecewise_constan_distribution random
4365        *        number distribution @p __x from the input stream @p __is.
4366        *
4367        * @param __is An input stream.
4368        * @param __x A %piecewise_constan_distribution random number
4369        *            generator engine.
4370        *
4371        * @returns The input stream with @p __x extracted or in an error
4372        *          state.
4373        */
4374       template<typename _RealType1, typename _CharT, typename _Traits>
4375         friend std::basic_istream<_CharT, _Traits>&
4376         operator>>(std::basic_istream<_CharT, _Traits>&,
4377                    std::piecewise_constant_distribution<_RealType1>&);
4378
4379     private:
4380       param_type _M_param;
4381     };
4382
4383
4384   /**
4385    * @brief A piecewise_linear_distribution random number distribution.
4386    *
4387    * The formula for the piecewise linear probability mass function is
4388    *
4389    */
4390   template<typename _RealType = double>
4391     class piecewise_linear_distribution
4392     {
4393       static_assert(std::is_floating_point<_RealType>::value,
4394                     "template argument not a floating point type");
4395
4396     public:
4397       /** The type of the range of the distribution. */
4398       typedef _RealType result_type;
4399       /** Parameter type. */
4400       struct param_type
4401       {
4402         typedef piecewise_linear_distribution<_RealType> distribution_type;
4403         friend class piecewise_linear_distribution<_RealType>;
4404
4405         param_type()
4406         : _M_int(), _M_den(), _M_cp(), _M_m()
4407         { _M_initialize(); }
4408
4409         template<typename _InputIteratorB, typename _InputIteratorW>
4410           param_type(_InputIteratorB __bfirst,
4411                      _InputIteratorB __bend,
4412                      _InputIteratorW __wbegin);
4413
4414         template<typename _Func>
4415           param_type(initializer_list<_RealType> __bl, _Func __fw);
4416
4417         template<typename _Func>
4418           param_type(size_t __nw, _RealType __xmin, _RealType __xmax,
4419                      _Func __fw);
4420
4421         std::vector<_RealType>
4422         intervals() const
4423         { return _M_int; }
4424
4425         std::vector<double>
4426         densities() const
4427         { return _M_den; }
4428
4429       private:
4430         void
4431         _M_initialize();
4432
4433         std::vector<_RealType> _M_int;
4434         std::vector<double> _M_den;
4435         std::vector<double> _M_cp;
4436         std::vector<double> _M_m;
4437       };
4438
4439       explicit
4440       piecewise_linear_distribution()
4441       : _M_param()
4442       { }
4443
4444       template<typename _InputIteratorB, typename _InputIteratorW>
4445         piecewise_linear_distribution(_InputIteratorB __bfirst,
4446                                       _InputIteratorB __bend,
4447                                       _InputIteratorW __wbegin)
4448         : _M_param(__bfirst, __bend, __wbegin)
4449         { }
4450
4451       template<typename _Func>
4452         piecewise_linear_distribution(initializer_list<_RealType> __bl,
4453                                       _Func __fw)
4454         : _M_param(__bl, __fw)
4455         { }
4456
4457       template<typename _Func>
4458         piecewise_linear_distribution(size_t __nw,
4459                                       _RealType __xmin, _RealType __xmax,
4460                                       _Func __fw)
4461         : _M_param(__nw, __xmin, __xmax, __fw)
4462         { }
4463
4464       explicit
4465       piecewise_linear_distribution(const param_type& __p)
4466       : _M_param(__p)
4467       { }
4468
4469       /**
4470        * Resets the distribution state.
4471        */
4472       void
4473       reset()
4474       { }
4475
4476       /**
4477        * @brief Return the intervals of the distribution.
4478        */
4479       std::vector<_RealType>
4480       intervals() const
4481       { return _M_param.intervals(); }
4482
4483       /**
4484        * @brief Return a vector of the probability densities of the
4485        *        distribution.
4486        */
4487       std::vector<double>
4488       densities() const
4489       { return _M_param.densities(); }
4490
4491       /**
4492        * @brief Returns the parameter set of the distribution.
4493        */
4494       param_type
4495       param() const
4496       { return _M_param; }
4497
4498       /**
4499        * @brief Sets the parameter set of the distribution.
4500        * @param __param The new parameter set of the distribution.
4501        */
4502       void
4503       param(const param_type& __param)
4504       { _M_param = __param; }
4505
4506       /**
4507        * @brief Returns the greatest lower bound value of the distribution.
4508        */
4509       result_type
4510       min() const
4511       { return this->_M_param._M_int.front(); }
4512
4513       /**
4514        * @brief Returns the least upper bound value of the distribution.
4515        */
4516       result_type
4517       max() const
4518       { return this->_M_param._M_int.back(); }
4519
4520       template<typename _UniformRandomNumberGenerator>
4521         result_type
4522         operator()(_UniformRandomNumberGenerator& __urng)
4523         { return this->operator()(__urng, this->param()); }
4524
4525       template<typename _UniformRandomNumberGenerator>
4526         result_type
4527         operator()(_UniformRandomNumberGenerator& __urng,
4528                    const param_type& __p);
4529
4530       /**
4531        * @brief Inserts a %piecewise_linear_distribution random number
4532        *        distribution @p __x into the output stream @p __os.
4533        *
4534        * @param __os An output stream.
4535        * @param __x  A %piecewise_linear_distribution random number
4536        *             distribution.
4537        *
4538        * @returns The output stream with the state of @p __x inserted or in
4539        *          an error state.
4540        */
4541       template<typename _RealType1, typename _CharT, typename _Traits>
4542         friend std::basic_ostream<_CharT, _Traits>&
4543         operator<<(std::basic_ostream<_CharT, _Traits>&,
4544                    const std::piecewise_linear_distribution<_RealType1>&);
4545
4546       /**
4547        * @brief Extracts a %piecewise_linear_distribution random number
4548        *        distribution @p __x from the input stream @p __is.
4549        *
4550        * @param __is An input stream.
4551        * @param __x  A %piecewise_linear_distribution random number
4552        *             generator engine.
4553        *
4554        * @returns The input stream with @p __x extracted or in an error
4555        *          state.
4556        */
4557       template<typename _RealType1, typename _CharT, typename _Traits>
4558         friend std::basic_istream<_CharT, _Traits>&
4559         operator>>(std::basic_istream<_CharT, _Traits>&,
4560                    std::piecewise_linear_distribution<_RealType1>&);
4561
4562     private:
4563       param_type _M_param;
4564     };
4565
4566
4567   /* @} */ // group std_random_distributions_poisson
4568
4569   /* @} */ // group std_random_distributions
4570
4571   /**
4572    * @addtogroup std_random_utilities Random Number Utilities
4573    * @ingroup std_random
4574    * @{
4575    */
4576
4577   /**
4578    * @brief The seed_seq class generates sequences of seeds for random
4579    *        number generators.
4580    */
4581   class seed_seq
4582   {
4583
4584   public:
4585     /** The type of the seed vales. */
4586     typedef uint_least32_t result_type;
4587
4588     /** Default constructor. */
4589     seed_seq()
4590     : _M_v()
4591     { }
4592
4593     template<typename _IntType>
4594       seed_seq(std::initializer_list<_IntType> il);
4595
4596     template<typename _InputIterator>
4597       seed_seq(_InputIterator __begin, _InputIterator __end);
4598
4599     // generating functions
4600     template<typename _RandomAccessIterator>
4601       void
4602       generate(_RandomAccessIterator __begin, _RandomAccessIterator __end);
4603
4604     // property functions
4605     size_t size() const
4606     { return _M_v.size(); }
4607
4608     template<typename OutputIterator>
4609       void
4610       param(OutputIterator __dest) const
4611       { std::copy(_M_v.begin(), _M_v.end(), __dest); }
4612
4613   private:
4614     ///
4615     std::vector<result_type> _M_v;
4616   };
4617
4618   /* @} */ // group std_random_utilities
4619
4620   /* @} */ // group std_random
4621
4622 }
4623