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