lemon/dim2.h
 author Balazs Dezso Sun, 25 May 2008 17:01:11 +0200 changeset 158 500f3cbff9e4 parent 42 3a98515e9bc3 child 209 765619b7cbb2 permissions -rw-r--r--
Wrong member variable settings bug fix. (Ticket #95)
     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