RhodeCode

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

///\file

///\brief Instantiation of the Random class.

#include <lemon/random.h>

namespace lemon {

  /// \brief Global random number generator instance

  ///

  Random rnd;

}

 */

#ifndef LEMON_RANDOM_H

#define LEMON_RANDOM_H

#include <algorithm>

#include <iterator>

#include <vector>

#include <ctime>

#include <cmath>

#include <lemon/dim2.h>

///\ingroup misc

///\file

///\brief Mersenne Twister random number generator

namespace lemon {

  namespace _random_bits {

    template <typename _Word, int _bits = std::numeric_limits<_Word>::digits>

    struct RandomTraits {};

    template <typename _Word>

    struct RandomTraits<_Word, 32> {

      typedef _Word Word;

      static const int bits = 32;

      static const int length = 624;

      static const int shift = 397;

  /// double c = rnd(1.0, 2.0);             // [1.0, 2.0)

  /// // double c = rnd.real(1.0, 2.0);     // [1.0, 2.0)

  /// int d = rnd[100000];                  // 0..99999

  /// // int d = rnd.integer(100000);       // 0..99999

  /// int e = rnd[6] + 1;                   // 1..6

  /// // int e = rnd.integer(1, 1 + 6);     // 1..6

  /// int b = rnd.uinteger<int>();          // 0 .. 2^31 - 1

  /// int c = rnd.integer<int>();           // - 2^31 .. 2^31 - 1

  /// bool g = rnd.boolean();               // P(g = true) = 0.5

  /// bool h = rnd.boolean(0.8);            // P(h = true) = 0.8

  ///\endcode

  ///

  /// The lemon provides a global instance of the random number

  /// generator which name is \ref lemon::rnd "rnd". Usually it is a

  /// good programming convenience to use this global generator to get

  /// random numbers.

  class Random {

  private:

    typedef unsigned long Word;

    _random_bits::RandomCore<Word> core;

    _random_bits::BoolProducer<Word> bool_producer;

  public:

    /// \brief Constructor

    ///

    /// Constructor with constant seeding.

    Random() { core.initState(); }

    /// \brief Constructor

    ///

    /// Constructor with seed. The current number type will be converted

    /// Standard Gauss distribution.

    /// \note The Cartesian form of the Box-Muller

    /// transformation is used to generate a random normal distribution.

    /// \todo Consider using the "ziggurat" method instead.

    double gauss() 

    {

      double V1,V2,S;

      do {

	V1=2*real<double>()-1;

	V2=2*real<double>()-1;

	S=V1*V1+V2*V2;

      } while(S>=1);

      return std::sqrt(-2*std::log(S)/S)*V1;

    }

    /// Gauss distribution with given mean and standard deviation

    /// \sa gauss()

    double gauss(double mean,double std_dev)

    {

      return gauss()*std_dev+mean;

    }

    /// Exponential distribution with given mean

    /// This function generates an exponential distribution random number

    /// with mean <tt>1/lambda</tt>.

    ///

    double exponential(double lambda=1.0)

    {

      return -std::log(1.0-real<double>())/lambda;

    }

    /// Gamma distribution with given integer shape

    ///\param k shape parameter (<tt>k>0</tt>)

    ///\param x_min location parameter (<tt>x_min>0</tt>)

    ///

    double pareto(double k,double x_min)

    {

      return exponential(gamma(k,1.0/x_min));

    }  

    ///@}

    ///\name Two dimensional distributions

    ///

    ///@{

    /// Uniform distribution on the full unit circle.

    dim2::Point<double> disc() 

    {

      double V1,V2;

      do {

	V1=2*real<double>()-1;

	V2=2*real<double>()-1;

      } while(V1*V1+V2*V2>=1);

      return dim2::Point<double>(V1,V2);

    }

    /// A kind of two dimensional Gauss distribution

    /// This function provides a turning symmetric two-dimensional distribution.

    /// Both coordinates are of standard normal distribution, but they are not

    /// independent.

    ///

  ///\brief A class to provide a basic way to

  ///handle the comparison of numbers that are obtained

  ///as a result of a probably inexact computation.

  ///

  ///Tolerance is a class to provide a basic way to

  ///handle the comparison of numbers that are obtained

  ///as a result of a probably inexact computation.

  ///

  ///This is an abstract class, it should be specialized for all numerical

  ///data types. These specialized classes like \ref Tolerance\<double\>

  ///may offer additional tuning parameters.

  ///

  ///\sa Tolerance<float>

  ///\sa Tolerance<double>

  ///\sa Tolerance<long double>

  ///\sa Tolerance<int>

  ///\sa Tolerance<long long int>

  ///\sa Tolerance<unsigned int>

  ///\sa Tolerance<unsigned long long int>

  template<class T>

  class Tolerance

  {

  public:

    typedef T Value;

    ///\name Comparisons

    ///The concept is that these bool functions return with \c true only if

    ///the related comparisons hold even if some numerical error appeared

    ///during the computations.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) {return false;}

    static void defaultEpsilon(Value e) {def_epsilon=e;}

    ///\name Comparisons

    ///See class Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    bool less(Value a,Value b) const {return a+_epsilon<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }

    ///Returns \c true if \c a is \e surely positive

    bool positive(Value a) const { return _epsilon<a; }

    ///Returns \c true if \c a is \e surely negative

    bool negative(Value a) const { return -_epsilon>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Double specialization of \ref Tolerance.

  ///Double specialization of \ref Tolerance.

  ///\sa Tolerance

  ///\relates Tolerance

  template<>

  class Tolerance<double>

  {

    static double def_epsilon;

    static void defaultEpsilon(Value e) {def_epsilon=e;}

    ///\name Comparisons

    ///See class Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    bool less(Value a,Value b) const {return a+_epsilon<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }

    ///Returns \c true if \c a is \e surely positive

    bool positive(Value a) const { return _epsilon<a; }

    ///Returns \c true if \c a is \e surely negative

    bool negative(Value a) const { return -_epsilon>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Long double specialization of \ref Tolerance.

  ///Long double specialization of \ref Tolerance.

  ///\sa Tolerance

  ///\relates Tolerance

  template<>

  class Tolerance<long double>

  {

    static long double def_epsilon;

    static void defaultEpsilon(Value e) {def_epsilon=e;}

    ///\name Comparisons

    ///See class Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    bool less(Value a,Value b) const {return a+_epsilon<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    bool different(Value a,Value b) const { return less(a,b)||less(b,a); }

    ///Returns \c true if \c a is \e surely positive

    bool positive(Value a) const { return _epsilon<a; }

    ///Returns \c true if \c a is \e surely negative

    bool negative(Value a) const { return -_epsilon>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Integer specialization of \ref Tolerance.

  ///Integer specialization of \ref Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<int>

  {

  public:

    ///\e

    typedef int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value a) { return 0>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Unsigned integer specialization of \ref Tolerance.

  ///Unsigned integer specialization of \ref Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<unsigned int>

  {

  public:

    ///\e

    typedef unsigned int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value) { return false; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Long integer specialization of \ref Tolerance.

  ///Long integer specialization of \ref Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<long int>

  {

  public:

    typedef long int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value a) { return 0>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Unsigned long integer specialization of \ref Tolerance.

  ///Unsigned long integer specialization of \ref Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<unsigned long int>

  {

  public:

    ///\e

    typedef unsigned long int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value) { return false; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

#if defined __GNUC__ && !defined __STRICT_ANSI__

  ///Long long integer specialization of \ref Tolerance.

  ///Long long integer specialization of \ref Tolerance.

  ///\warning This class (more exactly, type <tt>long long</tt>)

  ///is not ansi compatible.

  ///\sa Tolerance

  template<>

    typedef long long int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value a) { return 0>a; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///Unsigned long long integer specialization of \ref Tolerance.

  ///Unsigned long long integer specialization of \ref Tolerance.

  ///\warning This class (more exactly, type <tt>unsigned long long</tt>)

  ///is not ansi compatible.

  ///\sa Tolerance

  template<>

  class Tolerance<unsigned long long int>

  {

    typedef unsigned long long int Value;

    ///\name Comparisons

    ///See \ref Tolerance for more details.

    ///@{

    ///Returns \c true if \c a is \e surely strictly less than \c b

    static bool less(Value a,Value b) { return a<b;}

    ///Returns \c true if \c a is \e surely different from \c b

    static bool different(Value a,Value b) { return a!=b; }

    ///Returns \c true if \c a is \e surely positive

    static bool positive(Value a) { return 0<a; }

    ///Returns \c true if \c a is \e surely negative

    static bool negative(Value) { return false; }

    ///Returns \c true if \c a is \e surely non-zero

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

#endif

  /// @}

} //namespace lemon

#endif //LEMON_TOLERANCE_H