RhodeCode

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * 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

#include<lemon/tolerance.h>

#include<lemon/bits/invalid.h>

namespace lemon {

  float Tolerance<float>::def_epsilon = 1e-4;

  double Tolerance<double>::def_epsilon = 1e-10;

  long double Tolerance<long double>::def_epsilon = 1e-14;

#ifndef LEMON_ONLY_TEMPLATES

  const Invalid INVALID = Invalid();

#endif

 */

#ifndef LEMON_BITS_INVALID_H

#define LEMON_BITS_INVALID_H

///\file

///\brief Definition of INVALID.

namespace lemon {

  /// \brief Dummy type to make it easier to create invalid iterators.

  ///

  /// See \ref INVALID for the usage.

  struct Invalid {

  public:

    bool operator==(Invalid) { return true;  }

    bool operator!=(Invalid) { return false; }

    bool operator< (Invalid) { return false; }

  };

  /// \brief Invalid iterators.

  ///

  /// \ref Invalid is a global type that converts to each iterator

  /// in such a way that the value of the target iterator will be invalid.

#ifndef LEMON_DIM2_H

#define LEMON_DIM2_H

#include <iostream>

#include <lemon/bits/utility.h>

///\ingroup misc

///\file

///\brief A simple two dimensional vector and a bounding box implementation 

///

/// The class \ref lemon::dim2::Point "dim2::Point" implements

///

/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"

/// can be used to determine

/// the rectangular bounding box of a set of

/// \ref lemon::dim2::Point "dim2::Point"'s.

namespace lemon {

  ///Tools for handling two dimensional coordinates

  ///This namespace is a storage of several

  ///tools for handling two dimensional coordinates

  namespace dim2 {

  /// \addtogroup misc

  /// @{

  /// A simple two dimensional vector (plainvector) implementation

  /// A simple two dimensional vector (plainvector) implementation

  template<typename T>

    class Point {

    public:

      typedef T Value;

      ///First coordinate

      T x;

      ///Second coordinate

      T y;     

      ///Default constructor

      Point() {}

      ///Construct an instance from coordinates

      Point(T a, T b) : x(a), y(b) { }

      ///The dimension of the vector.

      ///This function always returns 2. 

      int size() const { return 2; }

      ///Subscripting operator

      ///\c p[0] is \c p.x and \c p[1] is \c p.y

      ///

      T& operator[](int idx) { return idx == 0 ? x : y; }

      ///Const subscripting operator

      ///\c p[0] is \c p.x and \c p[1] is \c p.y

      ///

      const T& operator[](int idx) const { return idx == 0 ? x : y; }

      ///Conversion constructor

      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}

      ///Give back the square of the norm of the vector

      T normSquare() const {

        return x*x+y*y;

      }

      Point<T>& operator +=(const Point<T>& u) {

        x += u.x;

        y += u.y;

        return *this;

      }

      Point<T>& operator -=(const Point<T>& u) {

        x -= u.x;

        y -= u.y;

        return *this;

      }

      ///Multiply the left hand side with a scalar

      Point<T>& operator *=(const T &u) {

        x *= u;

        y *= u;

        return *this;

      }

      BoundingBox(T l,T b,T r,T t)

      {

	bottom_left=Point<T>(l,b);

	top_right=Point<T>(r,t);

	_empty = false;

      }

      ///Return \c true if the bounding box is empty.

      ///Return \c true if the bounding box is empty (i.e. return \c false

      ///if at least one point was added to the box or the coordinates of

      ///the box were set).

      ///The coordinates of an empty bounding box are not defined. 

      bool empty() const {

        return _empty;

      }

      ///Make the BoundingBox empty

      void clear() {

        _empty=1;

      }

      ///If the bounding box is empty, then the return value is not defined.

      Point<T> bottomLeft() const {

        return bottom_left;

      }

      ///It should only be used for non-empty box.

      void bottomLeft(Point<T> p) {

	bottom_left = p;

      }

      ///If the bounding box is empty, then the return value is not defined.

      Point<T> topRight() const {

        return top_right;

      }

      ///It should only be used for non-empty box.

      void topRight(Point<T> p) {

	top_right = p;

      }

      ///If the bounding box is empty, then the return value is not defined.

      Point<T> bottomRight() const {

        return Point<T>(top_right.x,bottom_left.y);

      }

      ///It should only be used for non-empty box.

      void bottomRight(Point<T> p) {

	top_right.x = p.x;

	bottom_left.y = p.y;

      }

      ///If the bounding box is empty, then the return value is not defined.

      Point<T> topLeft() const {

        return Point<T>(bottom_left.x,top_right.y);

      }

      ///It should only be used for non-empty box.

      void topLeft(Point<T> p) {

	top_right.y = p.y;

	bottom_left.x = p.x;

      }

      ///Give back the bottom of the box

      ///Give back the bottom of the box.

      ///If the bounding box is empty, then the return value is not defined.

      T bottom() const {

        return bottom_left.y;

	  b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);

	  b.top_right.x = std::min(this->top_right.x,u.top_right.x);

	  b.top_right.y = std::min(this->top_right.y,u.top_right.y);

	  b._empty = b.bottom_left.x > b.top_right.x ||

	             b.bottom_left.y > b.top_right.y;

	} 

        return b;

      }

    };//class Boundingbox

  ///\ingroup maps

  ///

  template<class M>

  class XMap 

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    XMap(M& map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].x;}

  template<class M> 

  inline XMap<M> xMap(M &m) 

  {

    return XMap<M>(m);

  }

  template<class M> 

  inline XMap<M> xMap(const M &m) 

  {

    return XMap<M>(m);

  }

  ///\ingroup maps

  ///Constant (read only) version of \ref XMap

  ///

  template<class M>

  class ConstXMap 

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

  ///Returns a \ref ConstXMap class

  ///This function just returns a \ref ConstXMap class.

  ///

  ///\ingroup maps

  ///\relates ConstXMap

  template<class M> 

  inline ConstXMap<M> xMap(const M &m) 

  {

    return ConstXMap<M>(m);

  }

  ///\ingroup maps

  ///Map of y-coordinates of a \ref Point "Point"-map.

  ///

  template<class M>

  class YMap 

  {

    M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

  template<class M> 

  inline YMap<M> yMap(M &m) 

  {

    return YMap<M>(m);

  }

  template<class M> 

  inline YMap<M> yMap(const M &m) 

  {

    return YMap<M>(m);

  }

  ///\ingroup maps

  ///Constant (read only) version of \ref YMap

  ///

  template<class M>

  class ConstYMap 

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

  ///This function just returns a \ref ConstYMap class.

  ///

  ///\ingroup maps

  ///\relates ConstYMap

  template<class M> 

  inline ConstYMap<M> yMap(const M &m) 

  {

    return ConstYMap<M>(m);

  }

  template<class M>

  class NormSquareMap 

  {

    const M& _map;

  public:

    typedef typename M::Value::Value Value;

    typedef typename M::Key Key;

    ///\e

    NormSquareMap(const M &map) : _map(map) {}

    Value operator[](Key k) const {return _map[k].normSquare();}

  };

  /// 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

  ///

  /// 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:

    // Architecture word

    typedef unsigned long Word;

    _random_bits::RandomCore<Word> core;

    _random_bits::BoolProducer<Word> bool_producer;

  public:

    ///

    /// Constructor with constant seeding.

    Random() { core.initState(); }

    ///

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

    /// to the architecture word type.

    template <typename Number>

    Random(Number seed) { 

      _random_bits::Initializer<Number, Word>::init(core, seed);

    }

    ///

    /// Constructor with array seeding. The given range should contain

    /// any number type and the numbers will be converted to the

    /// architecture word type.

    template <typename Iterator>

    Random(Iterator begin, Iterator end) { 

      typedef typename std::iterator_traits<Iterator>::value_type Number;

      _random_bits::Initializer<Number, Word>::init(core, begin, end);

    }

    /// \brief Copy constructor

    ///

    /// of the generator and later use it to generate the same

    /// sequence.

    Random& operator=(const Random& other) {

      if (&other != this) {

        core.copyState(other.core);

      }

      return *this;

    }

    /// \brief Returns a random real number from the range [0, 1)

    ///

    /// It returns a random real number from the range [0, 1). The

    template <typename Number>

    Number real() {

      return _random_bits::RealConversion<Number, Word>::convert(core);

    }

    double real() {

      return real<double>();

    }

    /// \brief Returns a random real number the range [0, b)

    ///

    /// It returns a random real number from the range [0, b).

    /// \brief Returns a random integer from a range

    ///

    /// It returns a random integer from the range {0, 1, ..., b - 1}.

    template <typename Number>

    Number operator[](Number b) {

      return _random_bits::Mapping<Number, Word>::map(core, b);

    }

    /// \brief Returns a random non-negative integer

    ///

    /// It returns a random non-negative integer uniformly from the

    template <typename Number>

    Number uinteger() {

      return _random_bits::IntConversion<Number, Word>::convert(core);

    }

    unsigned int uinteger() {

      return uinteger<unsigned int>();

    }

    /// \brief Returns a random integer

    ///

    /// It returns a random integer uniformly from the whole range of

    /// the current \c Number type. The default result type of this

    template <typename Number>

    Number integer() {

      static const int nb = std::numeric_limits<Number>::digits + 

        (std::numeric_limits<Number>::is_signed ? 1 : 0);

      return _random_bits::IntConversion<Number, Word, nb>::convert(core);

    }

    int integer() {

      return integer<int>();

    }

    /// \brief Returns a random bool

    ///

    /// It returns a random bool. The generator holds a buffer for

    /// random bits. Every time when it become empty the generator makes

    /// a new random word and fill the buffer up.

    bool boolean() {

      return bool_producer.convert(core);

    }

    ///

    ///@{

    /// \brief Returns a random bool

    ///

    /// It returns a random bool with given probability of true result.

    bool boolean(double p) {

      return operator()() < p;

    }

    /// Standard Gauss distribution

///\todo It should be in a module like "Basic tools"

namespace lemon {

  /// \addtogroup misc

  /// @{

  ///\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.

  ///

  ///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

  ///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 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;}

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

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

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

    static bool positive(Value a) {return false;}

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

  ///\relates Tolerance

  template<>

  class Tolerance<float>

  {

    static float def_epsilon;

    float _epsilon;

  public:

    ///\e

    typedef float Value;

    ///Constructor setting the epsilon tolerance to the default value.

    Tolerance() : _epsilon(def_epsilon) {}

    Tolerance(float e) : _epsilon(e) {}

    Value epsilon() const {return _epsilon;}

    void epsilon(Value e) {_epsilon=e;}

    static Value defaultEpsilon() {return def_epsilon;}

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

    ///\name Comparisons

    ///@{

    ///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

  ///\relates Tolerance

  template<>

  class Tolerance<double>

  {

    static double def_epsilon;

    double _epsilon;

  public:

    ///\e

    typedef double Value;

    ///Constructor setting the epsilon tolerance to the default value.

    Tolerance() : _epsilon(def_epsilon) {}

    Tolerance(double e) : _epsilon(e) {}

    Value epsilon() const {return _epsilon;}

    void epsilon(Value e) {_epsilon=e;}

    static Value defaultEpsilon() {return def_epsilon;}

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

    ///\name Comparisons

    ///@{

    ///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

  ///\relates Tolerance

  template<>

  class Tolerance<long double>

  {

    static long double def_epsilon;

    long double _epsilon;

  public:

    ///\e

    typedef long double Value;

    ///Constructor setting the epsilon tolerance to the default value.

    Tolerance() : _epsilon(def_epsilon) {}

    Tolerance(long double e) : _epsilon(e) {}

    Value epsilon() const {return _epsilon;}

    void epsilon(Value e) {_epsilon=e;}

    static Value defaultEpsilon() {return def_epsilon;}

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

    ///\name Comparisons

    ///@{

    ///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

  ///Integer specialization of Tolerance.

  ///Integer specialization of Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<int>

  {

  public:

    ///\e

    typedef int Value;

    ///\name Comparisons

    ///@{

    ///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

  ///Unsigned integer specialization of Tolerance.

  ///Unsigned integer specialization of \ref Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<unsigned int>

  {

  public:

    ///\e

    typedef unsigned int Value;

    ///\name Comparisons

    ///@{

    ///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

  ///Long integer specialization of Tolerance.

  ///Long integer specialization of Tolerance.

  ///\sa Tolerance

  template<>

  class Tolerance<long int>

  {

  public:

    ///\e

    typedef long int Value;

    ///\name Comparisons

    ///@{

    ///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

  ///Unsigned long integer specialization of 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

    ///@{

    ///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