lemon/dim2.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 18 Aug 2008 20:33:11 +0200
changeset 249 f0b89f242745
parent 220 a5d8c039f218
child 250 d0aae16df1bb
permissions -rw-r--r--
Ignore the downloaded tag files
     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-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 
    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::BoundingBox "dim2::BoundingBox"
    32 /// can be used to determine
    33 /// the rectangular bounding box of a set of
    34 /// \ref lemon::dim2::Point "dim2::Point"'s.
    35 
    36 namespace lemon {
    37 
    38   ///Tools for handling two dimensional coordinates
    39 
    40   ///This namespace is a storage of several
    41   ///tools for handling two dimensional coordinates
    42   namespace dim2 {
    43 
    44   /// \addtogroup misc
    45   /// @{
    46 
    47   /// A simple two dimensional vector (plain vector) implementation
    48 
    49   /// A simple two dimensional vector (plain vector) implementation
    50   /// with the usual vector operations.
    51   template<typename T>
    52     class Point {
    53 
    54     public:
    55 
    56       typedef T Value;
    57 
    58       ///First coordinate
    59       T x;
    60       ///Second coordinate
    61       T y;
    62 
    63       ///Default constructor
    64       Point() {}
    65 
    66       ///Construct an instance from coordinates
    67       Point(T a, T b) : x(a), y(b) { }
    68 
    69       ///Returns the dimension of the vector (i.e. returns 2).
    70 
    71       ///The dimension of the vector.
    72       ///This function always returns 2.
    73       int size() const { return 2; }
    74 
    75       ///Subscripting operator
    76 
    77       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    78       ///
    79       T& operator[](int idx) { return idx == 0 ? x : y; }
    80 
    81       ///Const subscripting operator
    82 
    83       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    84       ///
    85       const T& operator[](int idx) const { return idx == 0 ? x : y; }
    86 
    87       ///Conversion constructor
    88       template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
    89 
    90       ///Give back the square of the norm of the vector
    91       T normSquare() const {
    92         return x*x+y*y;
    93       }
    94 
    95       ///Increment the left hand side by \c u
    96       Point<T>& operator +=(const Point<T>& u) {
    97         x += u.x;
    98         y += u.y;
    99         return *this;
   100       }
   101 
   102       ///Decrement the left hand side by \c u
   103       Point<T>& operator -=(const Point<T>& u) {
   104         x -= u.x;
   105         y -= u.y;
   106         return *this;
   107       }
   108 
   109       ///Multiply the left hand side with a scalar
   110       Point<T>& operator *=(const T &u) {
   111         x *= u;
   112         y *= u;
   113         return *this;
   114       }
   115 
   116       ///Divide the left hand side by a scalar
   117       Point<T>& operator /=(const T &u) {
   118         x /= u;
   119         y /= u;
   120         return *this;
   121       }
   122 
   123       ///Return the scalar product of two vectors
   124       T operator *(const Point<T>& u) const {
   125         return x*u.x+y*u.y;
   126       }
   127 
   128       ///Return the sum of two vectors
   129       Point<T> operator+(const Point<T> &u) const {
   130         Point<T> b=*this;
   131         return b+=u;
   132       }
   133 
   134       ///Return the negative of the vector
   135       Point<T> operator-() const {
   136         Point<T> b=*this;
   137         b.x=-b.x; b.y=-b.y;
   138         return b;
   139       }
   140 
   141       ///Return the difference of two vectors
   142       Point<T> operator-(const Point<T> &u) const {
   143         Point<T> b=*this;
   144         return b-=u;
   145       }
   146 
   147       ///Return a vector multiplied by a scalar
   148       Point<T> operator*(const T &u) const {
   149         Point<T> b=*this;
   150         return b*=u;
   151       }
   152 
   153       ///Return a vector divided by a scalar
   154       Point<T> operator/(const T &u) const {
   155         Point<T> b=*this;
   156         return b/=u;
   157       }
   158 
   159       ///Test equality
   160       bool operator==(const Point<T> &u) const {
   161         return (x==u.x) && (y==u.y);
   162       }
   163 
   164       ///Test inequality
   165       bool operator!=(Point u) const {
   166         return  (x!=u.x) || (y!=u.y);
   167       }
   168 
   169     };
   170 
   171   ///Return a Point
   172 
   173   ///Return a Point.
   174   ///\relates Point
   175   template <typename T>
   176   inline Point<T> makePoint(const T& x, const T& y) {
   177     return Point<T>(x, y);
   178   }
   179 
   180   ///Return a vector multiplied by a scalar
   181 
   182   ///Return a vector multiplied by a scalar.
   183   ///\relates Point
   184   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   185     return x*u;
   186   }
   187 
   188   ///Read a plain vector from a stream
   189 
   190   ///Read a plain vector from a stream.
   191   ///\relates Point
   192   ///
   193   template<typename T>
   194   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   195     char c;
   196     if (is >> c) {
   197       if (c != '(') is.putback(c);
   198     } else {
   199       is.clear();
   200     }
   201     if (!(is >> z.x)) return is;
   202     if (is >> c) {
   203       if (c != ',') is.putback(c);
   204     } else {
   205       is.clear();
   206     }
   207     if (!(is >> z.y)) return is;
   208     if (is >> c) {
   209       if (c != ')') is.putback(c);
   210     } else {
   211       is.clear();
   212     }
   213     return is;
   214   }
   215 
   216   ///Write a plain vector to a stream
   217 
   218   ///Write a plain vector to a stream.
   219   ///\relates Point
   220   ///
   221   template<typename T>
   222   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   223   {
   224     os << "(" << z.x << ", " << z.y << ")";
   225     return os;
   226   }
   227 
   228   ///Rotate by 90 degrees
   229 
   230   ///Returns the parameter rotated by 90 degrees in positive direction.
   231   ///\relates Point
   232   ///
   233   template<typename T>
   234   inline Point<T> rot90(const Point<T> &z)
   235   {
   236     return Point<T>(-z.y,z.x);
   237   }
   238 
   239   ///Rotate by 180 degrees
   240 
   241   ///Returns the parameter rotated by 180 degrees.
   242   ///\relates Point
   243   ///
   244   template<typename T>
   245   inline Point<T> rot180(const Point<T> &z)
   246   {
   247     return Point<T>(-z.x,-z.y);
   248   }
   249 
   250   ///Rotate by 270 degrees
   251 
   252   ///Returns the parameter rotated by 90 degrees in negative direction.
   253   ///\relates Point
   254   ///
   255   template<typename T>
   256   inline Point<T> rot270(const Point<T> &z)
   257   {
   258     return Point<T>(z.y,-z.x);
   259   }
   260 
   261 
   262 
   263     /// A class to calculate or store the bounding box of plain vectors.
   264 
   265     /// A class to calculate or store the bounding box of plain vectors.
   266     ///
   267     template<typename T>
   268     class BoundingBox {
   269       Point<T> _bottom_left, _top_right;
   270       bool _empty;
   271     public:
   272 
   273       ///Default constructor: creates an empty bounding box
   274       BoundingBox() { _empty = true; }
   275 
   276       ///Construct an instance from one point
   277       BoundingBox(Point<T> a) {
   278         _bottom_left = _top_right = a;
   279         _empty = false;
   280       }
   281 
   282       ///Construct an instance from two points
   283 
   284       ///Construct an instance from two points.
   285       ///\param a The bottom left corner.
   286       ///\param b The top right corner.
   287       ///\warning The coordinates of the bottom left corner must be no more
   288       ///than those of the top right one.
   289       BoundingBox(Point<T> a,Point<T> b)
   290       {
   291         _bottom_left = a;
   292         _top_right = b;
   293         _empty = false;
   294       }
   295 
   296       ///Construct an instance from four numbers
   297 
   298       ///Construct an instance from four numbers.
   299       ///\param l The left side of the box.
   300       ///\param b The bottom of the box.
   301       ///\param r The right side of the box.
   302       ///\param t The top of the box.
   303       ///\warning The left side must be no more than the right side and
   304       ///bottom must be no more than the top.
   305       BoundingBox(T l,T b,T r,T t)
   306       {
   307         _bottom_left=Point<T>(l,b);
   308         _top_right=Point<T>(r,t);
   309         _empty = false;
   310       }
   311 
   312       ///Return \c true if the bounding box is empty.
   313 
   314       ///Return \c true if the bounding box is empty (i.e. return \c false
   315       ///if at least one point was added to the box or the coordinates of
   316       ///the box were set).
   317       ///
   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 = true;
   326       }
   327 
   328       ///Give back the bottom left corner of the box
   329 
   330       ///Give back the bottom left corner of the box.
   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 of the box
   337 
   338       ///Set the bottom left corner of the box.
   339       ///\pre The box must not be empty.
   340       void bottomLeft(Point<T> p) {
   341         _bottom_left = p;
   342       }
   343 
   344       ///Give back the top right corner of the box
   345 
   346       ///Give back the top right corner of the box.
   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 of the box
   353 
   354       ///Set the top right corner of the box.
   355       ///\pre The box must not be empty.
   356       void topRight(Point<T> p) {
   357         _top_right = p;
   358       }
   359 
   360       ///Give back the bottom right corner of the box
   361 
   362       ///Give back the bottom right corner of the box.
   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 of the box
   369 
   370       ///Set the bottom right corner of the box.
   371       ///\pre The box must not be empty.
   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 of the box
   378 
   379       ///Give back the top left corner of the box.
   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 of the box
   386 
   387       ///Set the top left corner of the box.
   388       ///\pre The box must not be empty.
   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       ///\pre The box must not be empty.
   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       ///\pre The box must not be empty.
   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       ///\pre The box must not be empty.
   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       ///\pre The box must not be empty.
   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           add(u._bottom_left);
   509           add(u._top_right);
   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 (_empty || u._empty) {
   521           b._empty = true;
   522         } else {
   523           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
   524           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
   525           b._top_right.x = std::min(_top_right.x, u._top_right.x);
   526           b._top_right.y = std::min(_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   template<class M>
   678   class NormSquareMap
   679   {
   680     const M& _map;
   681   public:
   682 
   683     typedef typename M::Value::Value Value;
   684     typedef typename M::Key Key;
   685     ///\e
   686     NormSquareMap(const M &map) : _map(map) {}
   687     Value operator[](Key k) const {return _map[k].normSquare();}
   688   };
   689 
   690   ///Returns a \ref NormSquareMap class
   691 
   692   ///This function just returns a \ref NormSquareMap class.
   693   ///
   694   ///\ingroup maps
   695   ///\relates NormSquareMap
   696   template<class M>
   697   inline NormSquareMap<M> normSquareMap(const M &m)
   698   {
   699     return NormSquareMap<M>(m);
   700   }
   701 
   702   /// @}
   703 
   704   } //namespce dim2
   705 
   706 } //namespace lemon
   707 
   708 #endif //LEMON_DIM2_H