RhodeCode

      }

      /// Give back the right side of the box

      /// Give back the right side of the box.

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

      T right() const {

        return top_right.x;

      }

      ///Set the right side of the box

      ///Set the right side of the box.

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

      void right(T t) {

	top_right.x = t;

      }

      ///Give back the height of the box

      ///Give back the height of the box.

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

      T height() const {

        return top_right.y-bottom_left.y;

      }

      ///Give back the width of the box

      ///Give back the width of the box.

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

      T width() const {

        return top_right.x-bottom_left.x;

      }

      ///Checks whether a point is inside a bounding box

      bool inside(const Point<T>& u) const {

        if (_empty)

          return false;

        else{

          return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&

              (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );

        }

      }

      ///Increments a bounding box with a point

      ///Increments a bounding box with a point.

      ///

      BoundingBox& add(const Point<T>& u){

        if (_empty){

          bottom_left=top_right=u;

          _empty = false;

        }

        else{

          if (bottom_left.x > u.x) bottom_left.x = u.x;

          if (bottom_left.y > u.y) bottom_left.y = u.y;

          if (top_right.x < u.x) top_right.x = u.x;

          if (top_right.y < u.y) top_right.y = u.y;

        }

        return *this;

      }

      ///Increments a bounding box to contain another bounding box

      ///Increments a bounding box to contain another bounding box.

      ///

      BoundingBox& add(const BoundingBox &u){

        if ( !u.empty() ){

          this->add(u.bottomLeft());

	  this->add(u.topRight());

        }

        return *this;

      }

      ///Intersection of two bounding boxes

      ///Intersection of two bounding boxes.

      ///

      BoundingBox operator&(const BoundingBox& u) const {

        BoundingBox b;

        if (this->_empty || u._empty) {

	  b._empty = true;

	} else {

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

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

    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}

  };

  ///Returns an \ref XMap class

  ///This function just returns an \ref XMap class.

  ///

  ///\ingroup maps

  ///\relates XMap

  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;

    ///\e

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

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

  };

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

    ///\e

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

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

    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}

  };

  ///Returns a \ref YMap class

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

  ///

  ///\ingroup maps

  ///\relates YMap

  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;

    ///\e

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

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

  };

  ///Returns a \ref ConstYMap class

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

  }

    ///

    ///Map of the \ref Point::normSquare() "normSquare()"

    ///of a \ref Point "Point"-map.

    ///\ingroup maps

    ///

  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();}

  };

  ///Returns a \ref NormSquareMap class

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

  ///

  ///\ingroup maps

  ///\relates NormSquareMap

  template<class M> 

  inline NormSquareMap<M> normSquareMap(const M &m) 

  {

    return NormSquareMap<M>(m);

  }

  /// @}

  } //namespce dim2

} //namespace lemon

#endif //LEMON_DIM2_H

  /// Constant map.

  /// This is a readable map which assigns a specified value to each key.

  /// In other aspects it is equivalent to the \c NullMap.

  template<typename K, typename T>

  class ConstMap : public MapBase<K, T> {

  private:

    T v;

  public:

    typedef MapBase<K, T> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    /// Default constructor

    /// Default constructor.

    /// The value of the map will be uninitialized. 

    /// (More exactly it will be default constructed.)

    ConstMap() {}

    /// Constructor with specified initial value

    /// Constructor with specified initial value.

    /// \param _v is the initial value of the map.

    ConstMap(const T &_v) : v(_v) {}

    ///\e

    T operator[](const K&) const { return v; }

    ///\e

    void setAll(const T &t) {

      v = t;

    }    

    template<typename T1>

    struct rebind {

      typedef ConstMap<K, T1> other;

    };

    template<typename T1>

    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}

  };

  ///Returns a \c ConstMap class

  ///This function just returns a \c ConstMap class.

  ///\relates ConstMap

  template<typename K, typename V> 

  inline ConstMap<K, V> constMap(const V &v) {

    return ConstMap<K, V>(v);

  }

  template<typename T, T v>

  struct Const { };

  /// Constant map with inlined constant value.

  /// This is a readable map which assigns a specified value to each key.

  /// In other aspects it is equivalent to the \c NullMap.

  template<typename K, typename V, V v>

  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {

  public:

    typedef MapBase<K, V> Parent;

    typedef typename Parent::Key Key;

    typedef typename Parent::Value Value;

    ConstMap() { }

    ///\e

    V operator[](const K&) const { return v; }

    ///\e

    void set(const K&, const V&) { }

  };

  ///Returns a \c ConstMap class

  ///This function just returns a \c ConstMap class with inlined value.

  ///\relates ConstMap

  template<typename K, typename V, V v> 

  inline ConstMap<K, Const<V, v> > constMap() {

    return ConstMap<K, Const<V, v> >();

  }

  ///Map based on std::map

  ///This is essentially a wrapper for \c std::map with addition that

  ///you can specify a default value different from \c Value().

  template <typename K, typename T, typename Compare = std::less<K> >

  class StdMap {

    template <typename K1, typename T1, typename C1>

    friend class StdMap;

  public:

    typedef True ReferenceMapTag;

    typedef K Key;

    typedef T Value;

    typedef T& Reference;

    typedef const T& ConstReference;

  private:

    typedef std::map<K, T, Compare> Map;

    Value _value;

    Map _map;

  public:

    /// Constructor with specified default value

    StdMap(const T& value = T()) : _value(value) {}

    /// \brief Constructs the map from an appropriate std::map, and explicitly

    /// specifies a default value.

    template <typename T1, typename Comp1>

    StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 

      : _map(map.begin(), map.end()), _value(value) {}

    /// \brief Constructs a map from an other StdMap.

    template<typename T1, typename Comp1>

    StdMap(const StdMap<Key, T1, Comp1> &c) 

      : _map(c._map.begin(), c._map.end()), _value(c._value) {}

  private:

    StdMap& operator=(const StdMap&);

  public:

    ///\e

    Reference operator[](const Key &k) {

      typename Map::iterator it = _map.lower_bound(k);

      if (it != _map.end() && !_map.key_comp()(k, it->first))

	return it->second;

      else

	return _map.insert(it, std::make_pair(k, _value))->second;

    }

    /// \e 

    ConstReference operator[](const Key &k) const {

      typename Map::const_iterator it = _map.find(k);

      if (it != _map.end())

	return it->second;

      else

	return _value;

    }

    /// \e 

    void set(const Key &k, const T &t) {

      typename Map::iterator it = _map.lower_bound(k);

      if (it != _map.end() && !_map.key_comp()(k, it->first))

	it->second = t;

      else

	_map.insert(it, std::make_pair(k, t));

    }

    /// \e

    void setAll(const T &t) {

      _value = t;

      _map.clear();

    }    

    template <typename T1, typename C1 = std::less<T1> >

    struct rebind {

      typedef StdMap<Key, T1, C1> other;

    };

  };

  /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>

  ///

  /// The current map has the <tt>[0..size-1]</tt> keyset and the values

  /// are stored in a \c std::vector<T>  container. It can be used with

  /// some data structures, for example \c UnionFind, \c BinHeap, when 

  /// the used items are small integer numbers. 

  ///

  /// \todo Revise its name

  template <typename T>

  class IntegerMap {

    template <typename T1>

    friend class IntegerMap;

  public:

    typedef True ReferenceMapTag;

    ///\e

    typedef int Key;

    ///\e

    typedef T Value;

    ///\e

    typedef T& Reference;

    ///\e

    typedef const T& ConstReference;

  private:

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * 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.

 *

 */

#ifndef LEMON_TOLERANCE_H

#define LEMON_TOLERANCE_H

///\ingroup misc

///\file

///\brief A basic tool to handle the anomalies of calculation with

///floating point numbers.

///

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

  ///

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

  ///may offer additional tuning parameters.

  ///

  ///\sa Tolerance<float>

  ///\sa Tolerance<double>

  ///\sa Tolerance<long double>

  ///\sa Tolerance<int>

#if defined __GNUC__ && !defined __STRICT_ANSI__  

  ///\sa Tolerance<long long int>

#endif

  ///\sa Tolerance<unsigned int>

#if defined __GNUC__ && !defined __STRICT_ANSI__  

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

#endif

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

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

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

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

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

    ///@}

    ///Returns the zero value.

    static Value zero() {return T();}

    //   static bool finite(Value a) {}

    //   static Value big() {}

    //   static Value negativeBig() {}

  };

  ///\sa Tolerance

  ///\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) {}

    ///Constructor setting the epsilon tolerance.

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

    ///Return the epsilon value.

    Value epsilon() const {return _epsilon;}

    ///Set the epsilon value.

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

    ///Return the default epsilon value.

    static Value defaultEpsilon() {return def_epsilon;}

    ///Set the default epsilon value.

    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

    bool nonZero(Value a) const { return positive(a)||negative(a); }

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///\sa Tolerance

  ///\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) {}

    ///Constructor setting the epsilon tolerance.

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

    ///Return the epsilon value.

    Value epsilon() const {return _epsilon;}

    ///Set the epsilon value.

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

    ///Return the default epsilon value.

    static Value defaultEpsilon() {return def_epsilon;}

    ///Set the default epsilon value.

    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

    bool nonZero(Value a) const { return positive(a)||negative(a); }

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

  ///\sa Tolerance

  ///\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) {}

    ///Constructor setting the epsilon tolerance.

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

    ///Return the epsilon value.

    Value epsilon() const {return _epsilon;}

    ///Set the epsilon value.

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

    ///Return the default epsilon value.

    static Value defaultEpsilon() {return def_epsilon;}

    ///Set the default epsilon value.

    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

    bool nonZero(Value a) const { return positive(a)||negative(a); }

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

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

    static bool nonZero(Value a) { return a!=0; }

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

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

    static bool nonZero(Value a) { return a!=0; }

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

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

    static bool nonZero(Value a) { return a!=0;}

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

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

    static bool nonZero(Value a) { return a!=0;}

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

#if defined __GNUC__ && !defined __STRICT_ANSI__

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

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

  ///is not ansi compatible.

  ///\sa Tolerance

  template<>

  class Tolerance<long long int>

  {

  public:

    ///\e

    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

    static bool nonZero(Value a) { return a!=0;}

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

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

  {

  public:

    ///\e

    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

    static bool nonZero(Value a) { return a!=0;}

    ///@}

    ///Returns zero

    static Value zero() {return 0;}

  };

#endif

  /// @}

} //namespace lemon

#endif //LEMON_TOLERANCE_H