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