[thirdparty/gcc.git] / libstdc++-v3 / include / tr1 / random

// random number generation -*- C++ -*-

// Copyright (C) 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

#ifndef _STD_TR1_RANDOM
#define _STD_TR1_RANDOM 1

/**
 * @file 
 * This is a TR1 C++ Library header. 
 */

#include <algorithm>
#include <bits/concept_check.h>
#include <bits/cpp_type_traits.h>
#include <cmath>
#include <debug/debug.h>
#include <iterator>
#include <iosfwd>
#include <limits>
#include <tr1/type_traits>
#include <fstream>

namespace std
{
_GLIBCXX_BEGIN_NAMESPACE(tr1)

  // [5.1] Random number generation

  /**
   * @addtogroup tr1_random Random Number Generation
   * A facility for generating random numbers on selected distributions.
   * @{
   */

  /*
   * Implementation-space details.
   */
  namespace _Private
  {
    // Type selectors -- are these already implemented elsewhere?
    template<bool, typename _TpTrue, typename _TpFalse>
      struct _Select
      {
	typedef _TpTrue _Type;
      };

    template<typename _TpTrue, typename _TpFalse>
      struct _Select<false, _TpTrue, _TpFalse>
      {
	typedef _TpFalse _Type;
      };

    /*
     * An adaptor class for converting the output of any Generator into
     * the input for a specific Distribution.
     */
    template<typename _Generator, typename _Distribution>
      struct _Adaptor
      { 
	typedef typename _Generator::result_type   generated_type;
	typedef typename _Distribution::input_type result_type;

      public:
	_Adaptor(const _Generator& __g)
	: _M_g(__g) { }

	result_type
	operator()();

      private:
	_Generator _M_g;
      };

    /*
     * Converts a value generated by the adapted random number generator into a
     * value in the input domain for the dependent random number distribution.
     *
     * Because the type traits are compile time constants only the appropriate
     * clause of the if statements will actually be emitted by the compiler.
     */
    template<typename _Generator, typename _Distribution>
      typename _Adaptor<_Generator, _Distribution>::result_type
      _Adaptor<_Generator, _Distribution>::
      operator()()
      {
	result_type __return_value = 0;
	if (is_integral<generated_type>::value
	    && is_integral<result_type>::value)
	  __return_value = _M_g();
      	else if (is_integral<generated_type>::value
		 && !is_integral<result_type>::value)
	  __return_value = result_type(_M_g())
	    / result_type(_M_g.max() - _M_g.min() + 1);
	else if (!is_integral<generated_type>::value
		 && !is_integral<result_type>::value)
	  __return_value = result_type(_M_g())
	    / result_type(_M_g.max() - _M_g.min());
      	return __return_value;
      }

  } // namespace std::tr1::_Private


  /**
   * Produces random numbers on a given disribution function using a un uniform
   * random number generation engine.
   *
   * @todo the engine_value_type needs to be studied more carefully.
   */
  template<typename _Generator, typename _Dist>
    class variate_generator
    {
      // Concept requirements.
      __glibcxx_class_requires(_Generator, _CopyConstructibleConcept)
      //  __glibcxx_class_requires(_Generator, _GeneratorConcept)
      //  __glibcxx_class_requires(_Dist,      _GeneratorConcept)

    public:
      typedef _Generator                             engine_type;
      typedef _Private::_Adaptor<_Generator, _Dist>  engine_value_type;
      typedef _Dist                                  distribution_type;
      typedef typename _Dist::result_type            result_type;

      // tr1:5.1.1 table 5.1 requirement
      typedef typename std::__enable_if<result_type,
					is_arithmetic<result_type>::value
        >::__type _IsValidType;

    public:
      /**
       * Constructs a variate generator with the uniform random number
       * generator @p __eng for the random distribution @p __dist.
       *
       * @throws Any exceptions which may thrown by the copy constructors of
       * the @p _Generator or @p _Dist objects.
       */
      variate_generator(engine_type __eng, distribution_type __dist)
      : _M_engine(__eng), _M_dist(__dist) { }

      /**
       * Gets the next generated value on the distribution.
       */
      result_type
      operator()();

      template<typename _Tp>
        result_type
        operator()(_Tp __value);

      /**
       * Gets a reference to the underlying uniform random number generator
       * object.
       */
      engine_value_type&
      engine()
      { return _M_engine; }

      /**
       * Gets a const reference to the underlying uniform random number
       * generator object.
       */
      const engine_value_type&
      engine() const
      { return _M_engine; }

      /**
       * Gets a reference to the underlying random distribution.
       */
      distribution_type&
      distribution()
      { return _M_dist; }

      /**
       * Gets a const reference to the underlying random distribution.
       */
      const distribution_type&
      distribution() const
      { return _M_dist; }

      /**
       * Gets the closed lower bound of the distribution interval.
       */
      result_type
      min() const
      { return this->distribution().min(); }

      /**
       * Gets the closed upper bound of the distribution interval.
       */
      result_type
      max() const
      { return this->distribution().max(); }

    private:
      engine_value_type _M_engine;
      distribution_type _M_dist;
    };

  /**
   * Gets the next random value on the given distribution.
   */
  template<typename _Generator, typename _Dist>
    typename variate_generator<_Generator, _Dist>::result_type
    variate_generator<_Generator, _Dist>::
    operator()()
    { return _M_dist(_M_engine); }

  /**
   * WTF?
   */
  template<typename _Generator, typename _Dist>
    template<typename _Tp>
      typename variate_generator<_Generator, _Dist>::result_type
      variate_generator<_Generator, _Dist>::
      operator()(_Tp __value)
      { return _M_dist(_M_engine, __value); }


  /**
   * @addtogroup tr1_random_generators Random Number Generators
   * @ingroup tr1_random
   *
   * These classes define objects which provide random or pseudorandom numbers,
   * either from a discrete or a continuous interval.  The random number
   * generator supplied as a part of this library are all uniform random number
   * generators which provide a sequence of random number uniformly distributed
   * over their range.
   *
   * A number generator is a function object with an operator() that takes zero
   * arguments and returns a number.
   *
   * A compliant random number generator must satisy the following requirements.
   * <table border=1 cellpadding=10 cellspacing=0>
   * <caption align=top>Random Number Generator Requirements</caption>
   * <tr><td>To be documented.</td></tr>
   * </table>
   * 
   * @{
   */

  /**
   * @brief A model of a linear congruential random number generator.
   *
   * A random number generator that produces pseudorandom numbers using the
   * linear function @f$x_{i+1}\leftarrow(ax_{i} + c) \bmod m @f$.
   *
   * The template parameter @p _UIntType must be an unsigned integral type
   * large enough to store values up to (__m-1). If the template parameter
   * @p __m is 0, the modulus @p __m used is
   * std::numeric_limits<_UIntType>::max() plus 1. Otherwise, the template
   * parameters @p __a and @p __c must be less than @p __m.
   *
   * The size of the state is @f$ 1 @f$.
   */
  template<class _UIntType, _UIntType __a, _UIntType __c, _UIntType __m>
    class linear_congruential
    {
      __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)
      //  __glibcpp_class_requires(__a < __m && __c < __m)

    public:
      /** The type of the generated random value. */
      typedef _UIntType result_type;

      /** The multiplier. */
      static const _UIntType multiplier = __a;
      /** An increment. */
      static const _UIntType increment = __c;
      /** The modulus. */
      static const _UIntType modulus = __m;

      /**
       * Constructs a %linear_congruential random number generator engine with
       * seed @p __s.  The default seed value is 1.
       *
       * @param __s The initial seed value.
       */
      explicit linear_congruential(unsigned long __s = 1);

      /**
       * Constructs a %linear_congruential random number generator engine
       * seeded from the generator function @p __g.
       *
       * @param __g The seed generator function.
       */
      template<class _Gen>
        linear_congruential(_Gen& __g);

      /**
       * Reseeds the %linear_congruential random number generator engine
       * sequence to the seed @g __s.
       *
       * @param __s The new seed.
       */
      void
      seed(unsigned long __s = 1);

      /**
       * Reseeds the %linear_congruential random number generator engine
       * sequence using values from the generator function @p __g.
       *
       * @param __g the seed generator function.
       */
      template<class _Gen>
        void
        seed(_Gen& __g)
        { seed(__g, typename is_fundamental<_Gen>::type()); }

      /**
       * Gets the smallest possible value in the output range.
       */
      result_type
      min() const;

      /**
       * Gets the largest possible value in the output range.
       */
      result_type
      max() const;

      /**
       * Gets the next random number in the sequence.
       */
      result_type
      operator()();

      /**
       * Compares two linear congruential random number generator objects of the
       * same type for equality.
       *  
       * @param __lhs A linear congruential random number generator object.
       * @param __rhs Another linear congruential random number generator obj.
       *
       * @returns true if the two objects are equal, false otherwise.
       */
      friend bool
      operator==(const linear_congruential& __lhs,
		 const linear_congruential& __rhs)
      { return __lhs._M_x == __rhs._M_x; }

      /**
       * Compares two linear congruential random number generator objects of the
       * same type for inequality.
       *
       * @param __lhs A linear congruential random number generator object.
       * @param __rhs Another linear congruential random number generator obj.
       *
       * @returns true if the two objects are not equal, false otherwise.
       */
      friend bool
      operator!=(const linear_congruential& __lhs,
		 const linear_congruential& __rhs)
      { return !(__lhs == __rhs); }

      /**
       * Writes the textual representation of the state x(i) of x to @p __os.
       *
       * @param __os  The output stream.
       * @param __lcr A linear_congruential random number generator.
       * @returns __os.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const linear_congruential& __lcr)
        { return __os << __lcr._M_x; }

      /**
       * Sets the state of the engine by reading its textual
       * representation from @p __is.
       *
       * The textual representation must have been previously written using an
       * output stream whose imbued locale and whose type's template
       * specialization arguments _CharT and _Traits were the same as those of
       * @p __is.
       *
       * @param __is  The input stream.
       * @param __lcr A linear_congruential random number generator.
       * @returns __is.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   linear_congruential& __lcr)
        { return __is >> __lcr._M_x; }

    private:
      template<class _Gen>
        void
        seed(_Gen& __g, true_type)
        { return seed(static_cast<unsigned long>(__g)); }

      template<class _Gen>
        void
        seed(_Gen& __g, false_type);

    private:
      _UIntType _M_x;
    };

  /**
   * The classic Minimum Standard rand0 of Lewis, Goodman, and Miller.
   */
  typedef linear_congruential<unsigned int, 16807, 0, 2147483647> minstd_rand0;

  /**
   * An alternative LCR (Lehmer Generator function) .
   */
  typedef linear_congruential<unsigned int, 48271, 0, 2147483647> minstd_rand;


  /**
   * A generalized feedback shift register discrete random number generator.
   *
   * This algorithm avoind multiplication and division and is designed to be
   * friendly to a pipelined architecture.  If the parameters are chosen
   * correctly, this generator will produce numbers with a very long period and
   * fairly good apparent entropy, although still not cryptographically strong.
   *
   * The best way to use this generator is with the predefined mt19937 class.
   *
   * This algorithm was originally invented by Makoto Matsumoto and
   * Takuji Nishimura.
   *
   * @var word_size   The number of bits in each element of the state vector.
   * @var state_size  The degree of recursion.
   * @var shift_size  The period parameter.
   * @var mask_bits   The separation point bit index.
   * @var parameter_a The last row of the twist matrix.
   * @var output_u    The first right-shift tempering matrix parameter.
   * @var output_s    The first left-shift tempering matrix parameter.
   * @var output_b    The first left-shift tempering matrix mask.
   * @var output_t    The second left-shift tempering matrix parameter.
   * @var output_c    The second left-shift tempering matrix mask.
   * @var output_l    The second right-shift tempering matrix parameter.
   */
  template<class _UIntType, int __w, int __n, int __m, int __r,
	   _UIntType __a, int __u, int __s, _UIntType __b, int __t,
	   _UIntType __c, int __l>
    class mersenne_twister
    {
      __glibcxx_class_requires(_UIntType, _UnsignedIntegerConcept)

    public:
      // types
      typedef _UIntType result_type ;

      // parameter values
      static const int       word_size   = __w;
      static const int       state_size  = __n;
      static const int       shift_size  = __m;
      static const int       mask_bits   = __r;
      static const _UIntType parameter_a = __a;
      static const int       output_u    = __u;
      static const int       output_s    = __s;
      static const _UIntType output_b    = __b;
      static const int       output_t    = __t;
      static const _UIntType output_c    = __c;
      static const int       output_l    = __l;

      // constructors and member function
      mersenne_twister()
      { seed(); }

      explicit
      mersenne_twister(unsigned long __value)
      { seed(__value); }

      template<class _Gen>
        mersenne_twister(_Gen& __g)
        { seed(__g); }

      void
      seed()
      { seed(5489UL); }

      void
      seed(unsigned long __value);

      template<class _Gen>
        void
        seed(_Gen& __g)
        { seed(__g, typename is_fundamental<_Gen>::type()); }

      result_type
      min() const
      { return 0; };

      result_type
      max() const;

      result_type
      operator()();

      /**
       * Compares two % mersenne_twister random number generator objects of
       * the same type for equality.
       *
       * @param __lhs A % mersenne_twister random number generator object.
       * @param __rhs Another % mersenne_twister random number generator
       *              object.
       *
       * @returns true if the two objects are equal, false otherwise.
       */
      friend bool
      operator==(const mersenne_twister& __lhs,
		 const mersenne_twister& __rhs)
      { return std::equal(__lhs._M_x, __lhs._M_x + state_size, __rhs._M_x); }

      /**
       * Compares two % mersenne_twister random number generator objects of
       * the same type for inequality.
       *
       * @param __lhs A % mersenne_twister random number generator object.
       * @param __rhs Another % mersenne_twister random number generator
       *              object.
       *
       * @returns true if the two objects are not equal, false otherwise.
       */
      friend bool
      operator!=(const mersenne_twister& __lhs,
		 const mersenne_twister& __rhs)
      { return !(__lhs == __rhs); }

      /**
       * Inserts the current state of a % mersenne_twister random number
       * generator engine @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A % mersenne_twister random number generator engine.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const mersenne_twister& __x)
        {
	  std::copy(__x._M_x, __x._M_x + state_size,
		    std::ostream_iterator<_UIntType>(__os, " "));
	  return __os;
	}

      /**
       * Extracts the current state of a % mersenne_twister random number
       * generator engine @p __x from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __x  A % mersenne_twister random number generator engine.
       *
       * @returns The input stream with the state of @p __x extracted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   mersenne_twister& __x)
        {
	  for (int __i = 0; __i < state_size; ++__i)
	    __is >> __x._M_x[__i];
	  return __is;
	}

    private:
      template<class _Gen>
        void
        seed(_Gen& __g, true_type)
        { return seed(static_cast<unsigned long>(__g)); }

      template<class _Gen>
        void
        seed(_Gen& __g, false_type);

    private:
      _UIntType _M_x[state_size];
      int       _M_p;
    };

  /**
   * The classic Mersenne Twister.
   *
   * Reference:
   * M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-Dimensionally
   * Equidistributed Uniform Pseudo-Random Number Generator", ACM Transactions
   * on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp 3-30.
   */
  typedef mersenne_twister<
    unsigned long, 32, 624, 397, 31,
    0x9908b0dful, 11, 7,
    0x9d2c5680ul, 15,
    0xefc60000ul, 18
    > mt19937;


  /**
   * @brief The Marsaglia-Zaman generator.
   * 
   * This is a model of a Generalized Fibonacci discrete random number
   * generator, sometimes referred to as the SWC generator.
   *
   * A discrete random number generator that produces pseudorandom numbers using
   * @f$x_{i}\leftarrow(x_{i - s} - x_{i - r} - carry_{i-1}) \bmod m @f$.
   *
   * The size of the state is @f$ r @f$
   * and the maximum period of the generator is @f$ m^r - m^s -1 @f$.
   *
   * N1688[4.13] says "the template parameter _IntType shall denote an integral
   * type large enough to store values up to m."
   *
   * @if maint
   * @var _M_x     The state of te generator.  This is a ring buffer.
   * @var _M_carry The carry.
   * @var _M_p     Current index of x(i - r).
   * @endif
   */
  template<typename _IntType, _IntType __m, int __s, int __r>
    class subtract_with_carry
    {
      __glibcxx_class_requires(_IntType, _IntegerConcept)

    public:
      /** The type of the generated random value. */
      typedef _IntType result_type;
      
      // parameter values
      static const _IntType modulus   = __m;
      static const int      long_lag  = __r;
      static const int      short_lag = __s;

    public:
      /**
       * Constructs a default-initialized % subtract_with_carry random number
       * generator.
       */
      subtract_with_carry()
      { this->seed(); }

      /**
       * Constructs an explicitly seeded % subtract_with_carry random number
       * generator.
       */
      explicit
      subtract_with_carry(unsigned long __value)
      { this->seed(__value); }

      /**
       * Constructs a % subtract_with_carry random number generator seeded from
       * the PAD iterated by [__first, last).
       */
      template<class _Gen>
        subtract_with_carry(_Gen& __g)
        { this->seed(__g); }

      /**
       * Seeds the initial state @f$ x_0 @f$ of the random number generator.
       *
       * @note This implementation follows the tr1 specification but will
       * obviously not work correctly on all platforms, since it has hardcoded
       * values that may overflow ints on some platforms.
       *
       * N1688[4.19] modifies this as follows.
       * If @p __value == 0, sets value to 19780503.  In any case, with a linear
       * congruential generator lcg(i) having parameters @f$ m_{lcg} =
       * 2147483563, a_{lcg} = 40014, c_{lcg} = 0, and lcg(0) = value @f$, sets
       * @f$ x_{-r} \dots x_{-1} @f$ to
       * @f$ lcg(1) \bmod m \dots lcg(r) \bmod m @f$ respectively.
       * If @f$ x_{-1} = 0 @f$ set carry to 1, otherwise sets carry to 0.
       */
      void
      seed(unsigned long __value = 19780503);

      /**
       * Seeds the initial state @f$ x_0 @f$ of the % subtract_with_carry
       * random number generator.
       */
      template<class _Gen>
        void
        seed(_Gen& __g)
        { seed(__g, typename is_fundamental<_Gen>::type()); }

      /**
       * Gets the inclusive minimum value of the range of random integers
       * returned by this generator.
       */
      result_type
      min() const
      { return 0; }

      /**
       * Gets the inclusive maximum value of the range of random integers
       * returned by this generator.
       */
      result_type
      max() const
      { return this->modulus - 1; }

      /**
       * Gets the next random number in the sequence.
       */
      result_type
      operator()();

      /**
       * Compares two % subtract_with_carry random number generator objects of
       * the same type for equality.
       *
       * @param __lhs A % subtract_with_carry random number generator object.
       * @param __rhs Another % subtract_with_carry random number generator
       *              object.
       *
       * @returns true if the two objects are equal, false otherwise.
       */
      friend bool
      operator==(const subtract_with_carry& __lhs,
		 const subtract_with_carry& __rhs)
      { return std::equal(__lhs._M_x, __lhs._M_x + long_lag, __rhs._M_x); }

      /**
       * Compares two % subtract_with_carry random number generator objects of
       * the same type for inequality.
       *
       * @param __lhs A % subtract_with_carry random number generator object.
       * @param __rhs Another % subtract_with_carry random number generator
       *              object.
       *
       * @returns true if the two objects are not equal, false otherwise.
       */
      friend bool
      operator!=(const subtract_with_carry& __lhs,
		 const subtract_with_carry& __rhs)
      { return !(__lhs == __rhs); }

      /**
       * Inserts the current state of a % subtract_with_carry random number
       * generator engine @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A % subtract_with_carry random number generator engine.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const subtract_with_carry& __x)
        {
	  std::copy(__x._M_x, __x._M_x + long_lag,
		    std::ostream_iterator<_IntType>(__os, " "));
	  return __os << __x._M_carry;
	}

      /**
       * Extracts the current state of a % subtract_with_carry random number
       * generator engine @p __x from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __x  A % subtract_with_carry random number generator engine.
       *
       * @returns The input stream with the state of @p __x extracted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   subtract_with_carry& __x)
        {
	  for (int __i = 0; __i < long_lag; ++__i)
	    __is >> __x._M_x[__i];
	  __is >> __x._M_carry;
	  return __is;
	}

    private:
      template<class _Gen>
        void
        seed(_Gen& __g, true_type)
        { return seed(static_cast<unsigned long>(__g)); }

      template<class _Gen>
        void
        seed(_Gen& __g, false_type);

    private:
      int         _M_p;
      result_type _M_x[long_lag];
      result_type _M_carry;
    };


  /**
   * Produces random numbers from some base engine by discarding blocks of
   * data.
   *
   * 0 <= @p __r <= @p __p
   */
  template<class _UniformRandomNumberGenerator, int __p, int __r>
    class discard_block
    {
      // __glibcxx_class_requires(typename base_type::result_type,
      //                          ArithmeticTypeConcept)

    public:
      /** The type of the underlying generator engine. */
      typedef _UniformRandomNumberGenerator   base_type;
      /** The type of the generated random value. */
      typedef typename base_type::result_type result_type;

      // parameter values
      static const int block_size = __p;
      static const int used_block = __r;

      /**
       * Constructs a default %discard_block engine.
       *
       * The underlying engine is default constrcuted as well.
       */
      discard_block()
      : _M_n(0) { }

      /**
       * Copy constructs a %discard_block engine.
       *
       * Copies an existing base class random number geenerator.
       * @param rng An existing (base class) engine object.
       */
      explicit discard_block(const base_type& __rng)
      : _M_b(__rng) , _M_n(0) { }

      /**
       * Seed constructs a %discard_block engine.
       *
       * Constructs the underlying generator engine seeded with @p __s.
       * @param __s A seed value for the base class engine.
       */
      explicit discard_block(unsigned long __s)
      : _M_b(__s), _M_n(0) { }

      /**
       * Generator constructs a %discard_block engine.
       *
       * @param __g A seed generator function.
       */
      template<class _Gen>
        discard_block(_Gen& __g)
	: _M_b(__g), _M_n(0) { }

      /**
       * Reseeds the %discard_block object with the default seed for the
       * underlying base class generator engine.
       */
      void seed()
      {
	_M_b.seed();
	_M_n = 0;
      }

      /**
       * Reseeds the %discard_block object with the given seed generator
       * function.
       * @param __g A seed generator function.
       */
      template<class _Gen>
        void seed(_Gen& __g)
        {
	  _M_b.seed(__g);
	  _M_n = 0;
	}

      /**
       * Gets a const reference to the underlying generator engine object.
       */
      const base_type&
      base() const
      { return _M_b; }

      /**
       * Gets the minimum value in the generated random number range.
       */
      result_type
      min() const
      { return _M_b.min(); }

      /**
       * Gets the maximum value in the generated random number range.
       */
      result_type
      max() const
      { return _M_b.max(); }

      /**
       * Gets the next value in the generated random number sequence.
       */
      result_type
      operator()();

      /**
       * Compares two %discard_block random number generator objects of
       * the same type for equality.
       *
       * @param __lhs A %discard_block random number generator object.
       * @param __rhs Another %discard_block random number generator
       *              object.
       *
       * @returns true if the two objects are equal, false otherwise.
       */
      friend bool
      operator==(const discard_block& __lhs, const discard_block& __rhs)
      { return (__lhs._M_b == __rhs._M_b) && (__lhs._M_n == __rhs._M_n); }

      /**
       * Compares two %discard_block random number generator objects of
       * the same type for inequality.
       *
       * @param __lhs A %discard_block random number generator object.
       * @param __rhs Another %discard_block random number generator
       *              object.
       *
       * @returns true if the two objects are not equal, false otherwise.
       */
      friend bool
      operator!=(const discard_block& __lhs, const discard_block& __rhs)
      { return !(__lhs == __rhs); }

      /**
       * Inserts the current state of a %discard_block random number
       * generator engine @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A %discard_block random number generator engine.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const discard_block& __x)
        { return __os << __x._M_b << " " << __x._M_n; }

      /**
       * Extracts the current state of a % subtract_with_carry random number
       * generator engine @p __x from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __x  A %discard_block random number generator engine.
       *
       * @returns The input stream with the state of @p __x extracted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   discard_block& __x)
        { return __is >> __x._M_b >> __x._M_n; }

    private:
      base_type _M_b;
      int       _M_n;
    };


  /**
   * James's luxury-level-3 integer adaptation of Luescher's generator.
   */
  typedef discard_block<
    subtract_with_carry<int, (1 << 24), 10, 24>,
      223,
      24
      > ranlux3;

  /**
   * James's luxury-level-4 integer adaptation of Luescher's generator.
   */
  typedef discard_block<
    subtract_with_carry<int, (1 << 24), 10, 24>,
      389,
      24
      > ranlux4;


  /**
   * A random number generator adaptor class that combines two random number
   * generator engines into a single output sequence.
   */
  template<class _UniformRandomNumberGenerator1, int __s1,
	   class _UniformRandomNumberGenerator2, int __s2>
    class xor_combine
    {
      // __glibcxx_class_requires(typename _UniformRandomNumberGenerator1::
      //                          result_type, ArithmeticTypeConcept)
      // __glibcxx_class_requires(typename _UniformRandomNumberGenerator2::
      //                          result_type, ArithmeticTypeConcept)

    public:
      /** The type of the the first underlying generator engine. */
      typedef _UniformRandomNumberGenerator1   base1_type;
      /** The type of the the second underlying generator engine. */
      typedef _UniformRandomNumberGenerator2   base2_type;

    private:
      typedef typename base1_type::result_type _Result_type1;
      typedef typename base2_type::result_type _Result_type2;

    public:
      /** The type of the generated random value. */
      typedef typename _Private::_Select<
	(sizeof(_Result_type1) > sizeof(_Result_type2)),
	_Result_type1, _Result_type2>::_Type result_type;

      // parameter values
      static const int shift1 = __s1;
      static const int shift2 = __s2;

      // constructors and member function
      xor_combine() { }

      xor_combine(const base1_type& __rng1, const base2_type& __rng2)
      : _M_b1(__rng1), _M_b2(__rng2) { }

      xor_combine(unsigned long __s)
      : _M_b1(__s), _M_b2(__s + 1) { }

      template<class _Gen>
        xor_combine(_Gen& __g)
	: _M_b1(__g), _M_b2(__g) { }

      void
      seed()
      {
	_M_b1.seed();
	_M_b2.seed();
      }

      template<class _Gen>
        void
        seed(_Gen& __g)
        {
	  _M_b1.seed(__g);
	  _M_b2.seed(__g);
	}

      const base1_type&
      base1() const
      { return _M_b1; }

      const base2_type&
      base2() const
      { return _M_b2; }

      result_type
      min() const
      { return _M_b1.min() ^ _M_b2.min(); }

      result_type
      max() const
      { return _M_b1.max() | _M_b2.max(); }

      /**
       * Gets the next random number in the sequence.
       */
      result_type
      operator()()
      { return ((_M_b1() << shift1) ^ (_M_b2() << shift2)); }

      /**
       * Compares two %xor_combine random number generator objects of
       * the same type for equality.
       *
       * @param __lhs A %xor_combine random number generator object.
       * @param __rhs Another %xor_combine random number generator
       *              object.
       *
       * @returns true if the two objects are equal, false otherwise.
       */
      friend bool
      operator==(const xor_combine& __lhs, const xor_combine& __rhs)
      {
	return (__lhs.base1() == __rhs.base1())
	        && (__lhs.base2() == __rhs.base2());
      }

      /**
       * Compares two %xor_combine random number generator objects of
       * the same type for inequality.
       *
       * @param __lhs A %xor_combine random number generator object.
       * @param __rhs Another %xor_combine random number generator
       *              object.
       *
       * @returns true if the two objects are not equal, false otherwise.
       */
      friend bool
      operator!=(const xor_combine& __lhs, const xor_combine& __rhs)
      { return !(__lhs == __rhs); }

      /**
       * Inserts the current state of a %xor_combine random number
       * generator engine @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A %xor_combine random number generator engine.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const xor_combine& __x)
        { return __os << __x.base1() << " " << __x.base1(); }

      /**
       * Extracts the current state of a %xor_combine random number
       * generator engine @p __x from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __x  A %xor_combine random number generator engine.
       *
       * @returns The input stream with the state of @p __x extracted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   xor_combine& __x)
        { return __is >> __x._M_b1 >> __x._M_b2; }

    private:
      base1_type _M_b1;
      base2_type _M_b2;
    };


  /**
   * A standard interface to a platform-specific non-deterministic random number
   * generator (if any are available).
   */
  class random_device
  {
  public:
    // types
    typedef unsigned int result_type;

    // constructors, destructors and member functions

#ifdef _GLIBCXX_USE_RANDOM_TR1

    explicit
    random_device(const std::string& __token = "/dev/urandom")
    {
      if ((__token != "/dev/urandom" && __token != "/dev/random")
	  || !_M_filebuf.open(__token.c_str(),
			      std::ios_base::in | std::ios_base::binary))
	std::__throw_runtime_error(__N("random_device::"
				       "random_device(const std::string&)"));
    }

    ~random_device()
    { _M_filebuf.close(); }

#else

    explicit
    random_device(const std::string& __token = "mt19937")
    : _M_mt(_M_strtoul(__token)) { }

  private:
    static unsigned long
    _M_strtoul(const std::string& __str)
    {
      unsigned long __ret = 5489UL;
      if (__str != "mt19937")
	{
	  const char* __nptr = __str.c_str();
	  char* __endptr;
	  __ret = std::strtoul(__nptr, &__endptr, 0);
	  if (*__nptr == '\0' || *__endptr != '\0')
	    std::__throw_runtime_error(__N("random_device::_M_strtoul"
					   "(const std::string&)"));
	}
      return __ret;
    }

  public:

#endif

    result_type
    min() const
    { return std::numeric_limits<result_type>::min(); }

    result_type
    max() const
    { return std::numeric_limits<result_type>::max(); }

    double
    entropy() const
    { return 0.0; }

    result_type
    operator()()
    {
#ifdef _GLIBCXX_USE_RANDOM_TR1
      result_type __ret;
      _M_filebuf.sgetn(reinterpret_cast<char*>(&__ret), sizeof(result_type));
      return __ret;
#else
      return _M_mt();
#endif
    }

  private:
    random_device(const random_device&);
    void operator=(const random_device&);

#ifdef _GLIBCXX_USE_RANDOM_TR1
    std::filebuf _M_filebuf;
#else
    mt19937      _M_mt;
#endif
  };

  /* @} */ // group tr1_random_generators

  /**
   * @addtogroup tr1_random_distributions Random Number Distributions
   * @ingroup tr1_random
   * @{
   */

  /**
   * @addtogroup tr1_random_distributions_discrete Discrete Distributions
   * @ingroup tr1_random_distributions
   * @{
   */

  /**
   * @brief Uniform discrete distribution for random numbers.
   * A discrete random distribution on the range @f$[min, max]@f$ with equal
   * probability throughout the range.
   */
  template<typename _IntType = int>
    class uniform_int
    {
      __glibcxx_class_requires(_IntType, _IntegerConcept)
 
    public:
      /** The type of the parameters of the distribution. */
      typedef _IntType input_type;
      /** The type of the range of the distribution. */
      typedef _IntType result_type;

    public:
      /**
       * Constructs a uniform distribution object.
       */
      explicit
      uniform_int(_IntType __min = 0, _IntType __max = 9)
      : _M_min(__min), _M_max(__max)
      {
	_GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
      }

      /**
       * Gets the inclusive lower bound of the distribution range.
       */
      result_type
      min() const
      { return _M_min; }

      /**
       * Gets the inclusive upper bound of the distribution range.
       */
      result_type
      max() const
      { return _M_max; }

      /**
       * Resets the distribution state.
       *
       * Does nothing for the uniform integer distribution.
       */
      void
      reset() { }

      /**
       * Gets a uniformly distributed random number in the range
       * @f$(min, max)@f$.
       */
      template<typename _UniformRandomNumberGenerator>
        result_type
        operator()(_UniformRandomNumberGenerator& __urng)
        { return (__urng() % (_M_max - _M_min + 1)) + _M_min; }

      /**
       * Gets a uniform random number in the range @f$[0, n)@f$.
       *
       * This function is aimed at use with std::random_shuffle.
       */
      template<typename _UniformRandomNumberGenerator>
        result_type
        operator()(_UniformRandomNumberGenerator& __urng, result_type __n)
        { return __urng() % __n; }

      /**
       * Inserts a %uniform_int random number distribution @p __x into the
       * output stream @p os.
       *
       * @param __os An output stream.
       * @param __x  A %uniform_int random number distribution.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const uniform_int& __x)
        { return __os << __x._M_min << " " << __x._M_max; }

      /**
       * Extracts a %unform_int random number distribution
       * @p __u from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __u  A %uniform_int random number generator engine.
       *
       * @returns The input stream with @p __u extracted or in an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is, uniform_int& __u)
        { return __is >> __u._M_min >> __u._M_max; }

    private:
      _IntType _M_min;
      _IntType _M_max;
    };


  /**
   * @brief A Bernoulli random number distribution.
   *
   * Generates a sequence of true and false values with likelihood @f$ p @f$
   * that true will come up and @f$ (1 - p) @f$ that false will appear.
   */
  class bernoulli_distribution
  {
  public:
    typedef int  input_type;
    typedef bool result_type;

  public:
    /**
     * Constructs a Bernoulli distribution with likelihood @p p.
     *
     * @param __p  [IN]  The likelihood of a true result being returned.  Must
     * be in the interval @f$ [0, 1] @f$.
     */
    explicit
    bernoulli_distribution(double __p = 0.5)
    : _M_p(__p)
    { 
      _GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
    }

    /**
     * Gets the @p p parameter of the distribution.
     */
    double
    p() const
    { return _M_p; }

    /**
     * Gets the inclusive lower bound of the distribution range.
     */
    result_type
    min() const
    { return false; }

    /**
     * Gets the inclusive upper bound of the distribution range.
     */
    result_type
    max() const
    { return true; }

    /**
     * Resets the distribution state.
     *
     * Does nothing for a bernoulli distribution.
     */
    void
    reset() { }

    /**
     * Gets the next value in the Bernoullian sequence.
     */
    template<class UniformRandomNumberGenerator>
      result_type
      operator()(UniformRandomNumberGenerator& __urng)
      {
	if (__urng() < _M_p)
	  return true;
	return false;
      }

    /**
     * Inserts a %bernoulli_distribution random number distribution
     * @p __x into the output stream @p __os.
     *
     * @param __os An output stream.
     * @param __x  A %bernoulli_distribution random number distribution.
     *
     * @returns The output stream with the state of @p __x inserted or in
     * an error state.
     */
    template<typename _CharT, typename _Traits>
      friend std::basic_ostream<_CharT, _Traits>&
      operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		 const bernoulli_distribution& __x)
      { return __os << __x.p(); }

    /**
     * Extracts a %bernoulli_distribution random number distribution
     * @p __u from the input stream @p __is.
     *
     * @param __is An input stream.
     * @param __u  A %bernoulli_distribution random number generator engine.
     *
     * @returns The input stream with @p __u extracted or in an error state.
     */
    template<typename _CharT, typename _Traits>
      friend std::basic_istream<_CharT, _Traits>&
      operator>>(std::basic_istream<_CharT, _Traits>& __is,
		 bernoulli_distribution& __u)
      { return __is >> __u._M_p; }

  protected:
    double _M_p;
  };


  /**
   * @brief A discrete geometric random number distribution.
   *
   * The formula for the geometric probability mass function is 
   * @f$ p(i) = (1 - p)p^{i-1} @f$ where @f$ p @f$ is the parameter of the
   * distribution.
   */
  template<typename _IntType = int, typename _RealType = double>
    class geometric_distribution
    {
    public:
      // types
      typedef _RealType input_type;
      typedef _IntType  result_type;

      // constructors and member function
      
      explicit
      geometric_distribution(const _RealType& __p = _RealType(0.5))
      : _M_p(__p), _M_log_p(std::log(_M_p))
      {
	_GLIBCXX_DEBUG_ASSERT((_M_p >= 0.0) && (_M_p <= 1.0));
      }

      /**
       * Gets the distribution parameter @p p.
       */
      _RealType
      p() const
      { return _M_p; }

      /**
       * Gets the inclusive lower bound of the distribution range.
       */
      result_type
      min() const;

      /**
       * Gets the inclusive upper bound of the distribution range.
       */
      result_type
      max() const;

      void
      reset() { }

      template<class _UniformRandomNumberGenerator>
        result_type
        operator()(_UniformRandomNumberGenerator& __urng)
        {
	  return result_type(std::floor(std::log(_RealType(1.0) - __urng())
					/ _M_log_p)) + result_type(1);
	}

      /**
       * Inserts a %geometric_distribution random number distribution
       * @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A %geometric_distribution random number distribution.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const geometric_distribution& __x)
        { return __os << __x.p(); }

      /**
       * Extracts a %geometric_distribution random number distribution
       * @p __u from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __u  A %geometric_distribution random number generator engine.
       *
       * @returns The input stream with @p __u extracted or in an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   geometric_distribution& __u)
        {
	  __is >> __u._M_p;
	  __u._M_log_p = std::log(__u._M_p);
	  return __is;
	}

    protected:
      _RealType _M_p;
      _RealType _M_log_p;
    };

  /* @} */ // group tr1_random_distributions_discrete

  /**
   * @addtogroup tr1_random_distributions_continuous Continuous Distributions
   * @ingroup tr1_random_distributions
   * @{
   */

  /**
   * @brief Uniform continuous distribution for random numbers.
   *
   * A continuous random distribution on the range [min, max) with equal
   * probability throughout the range.  The URNG should be real-valued and
   * deliver number in the range [0, 1).
   */
  template<typename _RealType = double>
    class uniform_real
    {
    public:
      // types
      typedef _RealType input_type;
      typedef _RealType result_type;

    public:
      /**
       * Constructs a uniform_real object.
       *
       * @param __min [IN]  The lower bound of the distribution.
       * @param __max [IN]  The upper bound of the distribution.
       */
      explicit
      uniform_real(_RealType __min = _RealType(0),
		   _RealType __max = _RealType(1))
      : _M_min(__min), _M_max(__max)
      {
	_GLIBCXX_DEBUG_ASSERT(_M_min <= _M_max);
      }

      result_type
      min() const
      { return _M_min; }

      result_type
      max() const
      { return _M_max; }

      void
      reset() { }

      template<class _UniformRandomNumberGenerator>
        result_type
        operator()(_UniformRandomNumberGenerator& __urng)
        { return (__urng() * (_M_max - _M_min)) + _M_min; }

      /**
       * Inserts a %uniform_real random number distribution @p __x into the
       * output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A %uniform_real random number distribution.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const uniform_real& __x)
        { return __os << __x._M_min << " " << __x._M_max; }

      /**
       * Extracts a %unform_real random number distribution
       * @p __u from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __u  A %uniform_real random number generator engine.
       *
       * @returns The input stream with @p __u extracted or in an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   uniform_real& __u)
        { return __is >> __u._M_min >> __u._M_max; }

    protected:
      _RealType _M_min;
      _RealType _M_max;
    };


  /**
   * @brief An exponential continuous distribution for random numbers.
   *
   * The formula for the exponential probability mass function is 
   * @f$ p(x) = \lambda e^{-\lambda x} @f$.
   *
   * <table border=1 cellpadding=10 cellspacing=0>
   * <caption align=top>Distribution Statistics</caption>
   * <tr><td>Mean</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
   * <tr><td>Median</td><td>@f$ \frac{\ln 2}{\lambda} @f$</td></tr>
   * <tr><td>Mode</td><td>@f$ zero @f$</td></tr>
   * <tr><td>Range</td><td>@f$[0, \infty]@f$</td></tr>
   * <tr><td>Standard Deviation</td><td>@f$ \frac{1}{\lambda} @f$</td></tr>
   * </table>
   */
  template<typename _RealType = double>
    class exponential_distribution
    {
    public:
      // types
      typedef _RealType input_type;
      typedef _RealType result_type;

    public:
      /**
       * Constructs an exponential distribution with inverse scale parameter
       * @f$ \lambda @f$.
       */
      explicit
      exponential_distribution(const result_type& __lambda = result_type(1))
      : _M_lambda(__lambda) { }

      /**
       * Gets the inverse scale parameter of the distribution.
       */
      _RealType
      lambda() const
      { return _M_lambda; }

      /**
       * Resets the distribution.
       *
       * Has no effect on exponential distributions.
       */
      void
      reset() { }

      template<class _UniformRandomNumberGenerator>
        result_type
        operator()(_UniformRandomNumberGenerator& __urng)
        { return -std::log(__urng()) / _M_lambda; }

      /**
       * Inserts a %exponential_distribution random number distribution
       * @p __x into the output stream @p __os.
       *
       * @param __os An output stream.
       * @param __x  A %exponential_distribution random number distribution.
       *
       * @returns The output stream with the state of @p __x inserted or in
       * an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_ostream<_CharT, _Traits>&
        operator<<(std::basic_ostream<_CharT, _Traits>& __os,
		   const exponential_distribution& __x)
        { return __os << __x.lambda(); }

      /**
       * Extracts a %exponential_distribution random number distribution
       * @p __u from the input stream @p __is.
       *
       * @param __is An input stream.
       * @param __u  A %exponential_distribution random number generator engine.
       *
       * @returns The input stream with @p __u extracted or in an error state.
       */
      template<typename _CharT, typename _Traits>
        friend std::basic_istream<_CharT, _Traits>&
        operator>>(std::basic_istream<_CharT, _Traits>& __is,
		   exponential_distribution& __u)
        { return __is >> __u._M_lambda; }

    private:
      result_type _M_lambda;
    };

  /* @} */ // group tr1_random_distributions_continuous
  /* @} */ // group tr1_random_distributions
  /* @} */ // group tr1_random

_GLIBCXX_END_NAMESPACE
}

#include <tr1/random.tcc>

#endif // _STD_TR1_RANDOM