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