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