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