lemon/dim2.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 314 2cc60866a0c9
child 714 98a30824fe36
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_DIM2_H
    20 #define LEMON_DIM2_H
    21 
    22 #include <iostream>
    23 
    24 ///\ingroup misc
    25 ///\file
    26 ///\brief A simple two dimensional vector and a bounding box implementation
    27 ///
    28 /// The class \ref lemon::dim2::Point "dim2::Point" implements
    29 /// a two dimensional vector with the usual operations.
    30 ///
    31 /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
    32 /// the rectangular bounding box of a set of
    33 /// \ref lemon::dim2::Point "dim2::Point"'s.
    34 
    35 namespace lemon {
    36 
    37   ///Tools for handling two dimensional coordinates
    38 
    39   ///This namespace is a storage of several
    40   ///tools for handling two dimensional coordinates
    41   namespace dim2 {
    42 
    43   /// \addtogroup misc
    44   /// @{
    45 
    46   /// Two dimensional vector (plain vector)
    47 
    48   /// A simple two dimensional vector (plain vector) implementation
    49   /// with the usual vector operations.
    50   template<typename T>
    51     class Point {
    52 
    53     public:
    54 
    55       typedef T Value;
    56 
    57       ///First coordinate
    58       T x;
    59       ///Second coordinate
    60       T y;
    61 
    62       ///Default constructor
    63       Point() {}
    64 
    65       ///Construct an instance from coordinates
    66       Point(T a, T b) : x(a), y(b) { }
    67 
    68       ///Returns the dimension of the vector (i.e. returns 2).
    69 
    70       ///The dimension of the vector.
    71       ///This function always returns 2.
    72       int size() const { return 2; }
    73 
    74       ///Subscripting operator
    75 
    76       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    77       ///
    78       T& operator[](int idx) { return idx == 0 ? x : y; }
    79 
    80       ///Const subscripting operator
    81 
    82       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    83       ///
    84       const T& operator[](int idx) const { return idx == 0 ? x : y; }
    85 
    86       ///Conversion constructor
    87       template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
    88 
    89       ///Give back the square of the norm of the vector
    90       T normSquare() const {
    91         return x*x+y*y;
    92       }
    93 
    94       ///Increment the left hand side by \c u
    95       Point<T>& operator +=(const Point<T>& u) {
    96         x += u.x;
    97         y += u.y;
    98         return *this;
    99       }
   100 
   101       ///Decrement the left hand side by \c u
   102       Point<T>& operator -=(const Point<T>& u) {
   103         x -= u.x;
   104         y -= u.y;
   105         return *this;
   106       }
   107 
   108       ///Multiply the left hand side with a scalar
   109       Point<T>& operator *=(const T &u) {
   110         x *= u;
   111         y *= u;
   112         return *this;
   113       }
   114 
   115       ///Divide the left hand side by a scalar
   116       Point<T>& operator /=(const T &u) {
   117         x /= u;
   118         y /= u;
   119         return *this;
   120       }
   121 
   122       ///Return the scalar product of two vectors
   123       T operator *(const Point<T>& u) const {
   124         return x*u.x+y*u.y;
   125       }
   126 
   127       ///Return the sum of two vectors
   128       Point<T> operator+(const Point<T> &u) const {
   129         Point<T> b=*this;
   130         return b+=u;
   131       }
   132 
   133       ///Return the negative of the vector
   134       Point<T> operator-() const {
   135         Point<T> b=*this;
   136         b.x=-b.x; b.y=-b.y;
   137         return b;
   138       }
   139 
   140       ///Return the difference of two vectors
   141       Point<T> operator-(const Point<T> &u) const {
   142         Point<T> b=*this;
   143         return b-=u;
   144       }
   145 
   146       ///Return a vector multiplied by a scalar
   147       Point<T> operator*(const T &u) const {
   148         Point<T> b=*this;
   149         return b*=u;
   150       }
   151 
   152       ///Return a vector divided by a scalar
   153       Point<T> operator/(const T &u) const {
   154         Point<T> b=*this;
   155         return b/=u;
   156       }
   157 
   158       ///Test equality
   159       bool operator==(const Point<T> &u) const {
   160         return (x==u.x) && (y==u.y);
   161       }
   162 
   163       ///Test inequality
   164       bool operator!=(Point u) const {
   165         return  (x!=u.x) || (y!=u.y);
   166       }
   167 
   168     };
   169 
   170   ///Return a Point
   171 
   172   ///Return a Point.
   173   ///\relates Point
   174   template <typename T>
   175   inline Point<T> makePoint(const T& x, const T& y) {
   176     return Point<T>(x, y);
   177   }
   178 
   179   ///Return a vector multiplied by a scalar
   180 
   181   ///Return a vector multiplied by a scalar.
   182   ///\relates Point
   183   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   184     return x*u;
   185   }
   186 
   187   ///Read a plain vector from a stream
   188 
   189   ///Read a plain vector from a stream.
   190   ///\relates Point
   191   ///
   192   template<typename T>
   193   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   194     char c;
   195     if (is >> c) {
   196       if (c != '(') is.putback(c);
   197     } else {
   198       is.clear();
   199     }
   200     if (!(is >> z.x)) return is;
   201     if (is >> c) {
   202       if (c != ',') is.putback(c);
   203     } else {
   204       is.clear();
   205     }
   206     if (!(is >> z.y)) return is;
   207     if (is >> c) {
   208       if (c != ')') is.putback(c);
   209     } else {
   210       is.clear();
   211     }
   212     return is;
   213   }
   214 
   215   ///Write a plain vector to a stream
   216 
   217   ///Write a plain vector to a stream.
   218   ///\relates Point
   219   ///
   220   template<typename T>
   221   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   222   {
   223     os << "(" << z.x << "," << z.y << ")";
   224     return os;
   225   }
   226 
   227   ///Rotate by 90 degrees
   228 
   229   ///Returns the parameter rotated by 90 degrees in positive direction.
   230   ///\relates Point
   231   ///
   232   template<typename T>
   233   inline Point<T> rot90(const Point<T> &z)
   234   {
   235     return Point<T>(-z.y,z.x);
   236   }
   237 
   238   ///Rotate by 180 degrees
   239 
   240   ///Returns the parameter rotated by 180 degrees.
   241   ///\relates Point
   242   ///
   243   template<typename T>
   244   inline Point<T> rot180(const Point<T> &z)
   245   {
   246     return Point<T>(-z.x,-z.y);
   247   }
   248 
   249   ///Rotate by 270 degrees
   250 
   251   ///Returns the parameter rotated by 90 degrees in negative direction.
   252   ///\relates Point
   253   ///
   254   template<typename T>
   255   inline Point<T> rot270(const Point<T> &z)
   256   {
   257     return Point<T>(z.y,-z.x);
   258   }
   259 
   260 
   261 
   262   /// Bounding box of plain vectors (points).
   263 
   264   /// A class to calculate or store the bounding box of plain vectors
   265   /// (\ref Point "points").
   266   template<typename T>
   267   class Box {
   268       Point<T> _bottom_left, _top_right;
   269       bool _empty;
   270     public:
   271 
   272       ///Default constructor: creates an empty box
   273       Box() { _empty = true; }
   274 
   275       ///Construct a box from one point
   276       Box(Point<T> a) {
   277         _bottom_left = _top_right = a;
   278         _empty = false;
   279       }
   280 
   281       ///Construct a box from two points
   282 
   283       ///Construct a box from two points.
   284       ///\param a The bottom left corner.
   285       ///\param b The top right corner.
   286       ///\warning The coordinates of the bottom left corner must be no more
   287       ///than those of the top right one.
   288       Box(Point<T> a,Point<T> b)
   289       {
   290         _bottom_left = a;
   291         _top_right = b;
   292         _empty = false;
   293       }
   294 
   295       ///Construct a box from four numbers
   296 
   297       ///Construct a box from four numbers.
   298       ///\param l The left side of the box.
   299       ///\param b The bottom of the box.
   300       ///\param r The right side of the box.
   301       ///\param t The top of the box.
   302       ///\warning The left side must be no more than the right side and
   303       ///bottom must be no more than the top.
   304       Box(T l,T b,T r,T t)
   305       {
   306         _bottom_left=Point<T>(l,b);
   307         _top_right=Point<T>(r,t);
   308         _empty = false;
   309       }
   310 
   311       ///Return \c true if the box is empty.
   312 
   313       ///Return \c true if the box is empty (i.e. return \c false
   314       ///if at least one point was added to the box or the coordinates of
   315       ///the box were set).
   316       ///
   317       ///The coordinates of an empty box are not defined.
   318       bool empty() const {
   319         return _empty;
   320       }
   321 
   322       ///Make the box empty
   323       void clear() {
   324         _empty = true;
   325       }
   326 
   327       ///Give back the bottom left corner of the box
   328 
   329       ///Give back the bottom left corner of the box.
   330       ///If the box is empty, then the return value is not defined.
   331       Point<T> bottomLeft() const {
   332         return _bottom_left;
   333       }
   334 
   335       ///Set the bottom left corner of the box
   336 
   337       ///Set the bottom left corner of the box.
   338       ///\pre The box must not be empty.
   339       void bottomLeft(Point<T> p) {
   340         _bottom_left = p;
   341       }
   342 
   343       ///Give back the top right corner of the box
   344 
   345       ///Give back the top right corner of the box.
   346       ///If the box is empty, then the return value is not defined.
   347       Point<T> topRight() const {
   348         return _top_right;
   349       }
   350 
   351       ///Set the top right corner of the box
   352 
   353       ///Set the top right corner of the box.
   354       ///\pre The box must not be empty.
   355       void topRight(Point<T> p) {
   356         _top_right = p;
   357       }
   358 
   359       ///Give back the bottom right corner of the box
   360 
   361       ///Give back the bottom right corner of the box.
   362       ///If the box is empty, then the return value is not defined.
   363       Point<T> bottomRight() const {
   364         return Point<T>(_top_right.x,_bottom_left.y);
   365       }
   366 
   367       ///Set the bottom right corner of the box
   368 
   369       ///Set the bottom right corner of the box.
   370       ///\pre The box must not be empty.
   371       void bottomRight(Point<T> p) {
   372         _top_right.x = p.x;
   373         _bottom_left.y = p.y;
   374       }
   375 
   376       ///Give back the top left corner of the box
   377 
   378       ///Give back the top left corner of the box.
   379       ///If the box is empty, then the return value is not defined.
   380       Point<T> topLeft() const {
   381         return Point<T>(_bottom_left.x,_top_right.y);
   382       }
   383 
   384       ///Set the top left corner of the box
   385 
   386       ///Set the top left corner of the box.
   387       ///\pre The box must not be empty.
   388       void topLeft(Point<T> p) {
   389         _top_right.y = p.y;
   390         _bottom_left.x = p.x;
   391       }
   392 
   393       ///Give back the bottom of the box
   394 
   395       ///Give back the bottom of the box.
   396       ///If the box is empty, then the return value is not defined.
   397       T bottom() const {
   398         return _bottom_left.y;
   399       }
   400 
   401       ///Set the bottom of the box
   402 
   403       ///Set the bottom of the box.
   404       ///\pre The box must not be empty.
   405       void bottom(T t) {
   406         _bottom_left.y = t;
   407       }
   408 
   409       ///Give back the top of the box
   410 
   411       ///Give back the top of the box.
   412       ///If the box is empty, then the return value is not defined.
   413       T top() const {
   414         return _top_right.y;
   415       }
   416 
   417       ///Set the top of the box
   418 
   419       ///Set the top of the box.
   420       ///\pre The box must not be empty.
   421       void top(T t) {
   422         _top_right.y = t;
   423       }
   424 
   425       ///Give back the left side of the box
   426 
   427       ///Give back the left side of the box.
   428       ///If the box is empty, then the return value is not defined.
   429       T left() const {
   430         return _bottom_left.x;
   431       }
   432 
   433       ///Set the left side of the box
   434 
   435       ///Set the left side of the box.
   436       ///\pre The box must not be empty.
   437       void left(T t) {
   438         _bottom_left.x = t;
   439       }
   440 
   441       /// Give back the right side of the box
   442 
   443       /// Give back the right side of the box.
   444       ///If the box is empty, then the return value is not defined.
   445       T right() const {
   446         return _top_right.x;
   447       }
   448 
   449       ///Set the right side of the box
   450 
   451       ///Set the right side of the box.
   452       ///\pre The box must not be empty.
   453       void right(T t) {
   454         _top_right.x = t;
   455       }
   456 
   457       ///Give back the height of the box
   458 
   459       ///Give back the height of the box.
   460       ///If the box is empty, then the return value is not defined.
   461       T height() const {
   462         return _top_right.y-_bottom_left.y;
   463       }
   464 
   465       ///Give back the width of the box
   466 
   467       ///Give back the width of the box.
   468       ///If the box is empty, then the return value is not defined.
   469       T width() const {
   470         return _top_right.x-_bottom_left.x;
   471       }
   472 
   473       ///Checks whether a point is inside the box
   474       bool inside(const Point<T>& u) const {
   475         if (_empty)
   476           return false;
   477         else {
   478           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
   479                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
   480         }
   481       }
   482 
   483       ///Increments the box with a point
   484 
   485       ///Increments the box with a point.
   486       ///
   487       Box& add(const Point<T>& u){
   488         if (_empty) {
   489           _bottom_left = _top_right = u;
   490           _empty = false;
   491         }
   492         else {
   493           if (_bottom_left.x > u.x) _bottom_left.x = u.x;
   494           if (_bottom_left.y > u.y) _bottom_left.y = u.y;
   495           if (_top_right.x < u.x) _top_right.x = u.x;
   496           if (_top_right.y < u.y) _top_right.y = u.y;
   497         }
   498         return *this;
   499       }
   500 
   501       ///Increments the box to contain another box
   502 
   503       ///Increments the box to contain another box.
   504       ///
   505       Box& add(const Box &u){
   506         if ( !u.empty() ){
   507           add(u._bottom_left);
   508           add(u._top_right);
   509         }
   510         return *this;
   511       }
   512 
   513       ///Intersection of two boxes
   514 
   515       ///Intersection of two boxes.
   516       ///
   517       Box operator&(const Box& u) const {
   518         Box b;
   519         if (_empty || u._empty) {
   520           b._empty = true;
   521         } else {
   522           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
   523           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
   524           b._top_right.x = std::min(_top_right.x, u._top_right.x);
   525           b._top_right.y = std::min(_top_right.y, u._top_right.y);
   526           b._empty = b._bottom_left.x > b._top_right.x ||
   527                      b._bottom_left.y > b._top_right.y;
   528         }
   529         return b;
   530       }
   531 
   532   };//class Box
   533 
   534 
   535   ///Read a box from a stream
   536 
   537   ///Read a box from a stream.
   538   ///\relates Box
   539   template<typename T>
   540   inline std::istream& operator>>(std::istream &is, Box<T>& b) {
   541     char c;
   542     Point<T> p;
   543     if (is >> c) {
   544       if (c != '(') is.putback(c);
   545     } else {
   546       is.clear();
   547     }
   548     if (!(is >> p)) return is;
   549     b.bottomLeft(p);
   550     if (is >> c) {
   551       if (c != ',') is.putback(c);
   552     } else {
   553       is.clear();
   554     }
   555     if (!(is >> p)) return is;
   556     b.topRight(p);
   557     if (is >> c) {
   558       if (c != ')') is.putback(c);
   559     } else {
   560       is.clear();
   561     }
   562     return is;
   563   }
   564 
   565   ///Write a box to a stream
   566 
   567   ///Write a box to a stream.
   568   ///\relates Box
   569   template<typename T>
   570   inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
   571   {
   572     os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
   573     return os;
   574   }
   575 
   576   ///Map of x-coordinates of a <tt>Point</tt>-map
   577 
   578   ///Map of x-coordinates of a \ref Point "Point"-map.
   579   ///
   580   template<class M>
   581   class XMap
   582   {
   583     M& _map;
   584   public:
   585 
   586     typedef typename M::Value::Value Value;
   587     typedef typename M::Key Key;
   588     ///\e
   589     XMap(M& map) : _map(map) {}
   590     Value operator[](Key k) const {return _map[k].x;}
   591     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
   592   };
   593 
   594   ///Returns an XMap class
   595 
   596   ///This function just returns an XMap class.
   597   ///\relates XMap
   598   template<class M>
   599   inline XMap<M> xMap(M &m)
   600   {
   601     return XMap<M>(m);
   602   }
   603 
   604   template<class M>
   605   inline XMap<M> xMap(const M &m)
   606   {
   607     return XMap<M>(m);
   608   }
   609 
   610   ///Constant (read only) version of XMap
   611 
   612   ///Constant (read only) version of XMap.
   613   ///
   614   template<class M>
   615   class ConstXMap
   616   {
   617     const M& _map;
   618   public:
   619 
   620     typedef typename M::Value::Value Value;
   621     typedef typename M::Key Key;
   622     ///\e
   623     ConstXMap(const M &map) : _map(map) {}
   624     Value operator[](Key k) const {return _map[k].x;}
   625   };
   626 
   627   ///Returns a ConstXMap class
   628 
   629   ///This function just returns a ConstXMap class.
   630   ///\relates ConstXMap
   631   template<class M>
   632   inline ConstXMap<M> xMap(const M &m)
   633   {
   634     return ConstXMap<M>(m);
   635   }
   636 
   637   ///Map of y-coordinates of a <tt>Point</tt>-map
   638 
   639   ///Map of y-coordinates of a \ref Point "Point"-map.
   640   ///
   641   template<class M>
   642   class YMap
   643   {
   644     M& _map;
   645   public:
   646 
   647     typedef typename M::Value::Value Value;
   648     typedef typename M::Key Key;
   649     ///\e
   650     YMap(M& map) : _map(map) {}
   651     Value operator[](Key k) const {return _map[k].y;}
   652     void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
   653   };
   654 
   655   ///Returns a YMap class
   656 
   657   ///This function just returns a YMap class.
   658   ///\relates YMap
   659   template<class M>
   660   inline YMap<M> yMap(M &m)
   661   {
   662     return YMap<M>(m);
   663   }
   664 
   665   template<class M>
   666   inline YMap<M> yMap(const M &m)
   667   {
   668     return YMap<M>(m);
   669   }
   670 
   671   ///Constant (read only) version of YMap
   672 
   673   ///Constant (read only) version of YMap.
   674   ///
   675   template<class M>
   676   class ConstYMap
   677   {
   678     const M& _map;
   679   public:
   680 
   681     typedef typename M::Value::Value Value;
   682     typedef typename M::Key Key;
   683     ///\e
   684     ConstYMap(const M &map) : _map(map) {}
   685     Value operator[](Key k) const {return _map[k].y;}
   686   };
   687 
   688   ///Returns a ConstYMap class
   689 
   690   ///This function just returns a ConstYMap class.
   691   ///\relates ConstYMap
   692   template<class M>
   693   inline ConstYMap<M> yMap(const M &m)
   694   {
   695     return ConstYMap<M>(m);
   696   }
   697 
   698 
   699   ///\brief Map of the normSquare() of a <tt>Point</tt>-map
   700   ///
   701   ///Map of the \ref Point::normSquare() "normSquare()"
   702   ///of a \ref Point "Point"-map.
   703   template<class M>
   704   class NormSquareMap
   705   {
   706     const M& _map;
   707   public:
   708 
   709     typedef typename M::Value::Value Value;
   710     typedef typename M::Key Key;
   711     ///\e
   712     NormSquareMap(const M &map) : _map(map) {}
   713     Value operator[](Key k) const {return _map[k].normSquare();}
   714   };
   715 
   716   ///Returns a NormSquareMap class
   717 
   718   ///This function just returns a NormSquareMap class.
   719   ///\relates NormSquareMap
   720   template<class M>
   721   inline NormSquareMap<M> normSquareMap(const M &m)
   722   {
   723     return NormSquareMap<M>(m);
   724   }
   725 
   726   /// @}
   727 
   728   } //namespce dim2
   729 
   730 } //namespace lemon
   731 
   732 #endif //LEMON_DIM2_H