lemon/dim2.h
 author Alpar Juttner Mon, 07 Jan 2008 19:22:09 +0100 changeset 40 8f4e8273a458 parent 15 062f361aa520 child 42 3a98515e9bc3 permissions -rw-r--r--
Several doc files ported from svn -r3436

- groups.dox contains several incomlete references
     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 namespace lemon {

    39

    40   ///Tools for handling two dimensional coordinates

    41

    42   ///This namespace is a storage of several

    43   ///tools for handling two dimensional coordinates

    44   namespace dim2 {

    45

    46   /// \addtogroup misc

    47   /// @{

    48

    49   /// A simple two dimensional vector (plainvector) implementation

    50

    51   /// A simple two dimensional vector (plainvector) implementation

    52   ///with the usual vector

    53   /// operators.

    54   ///

    55   template<typename T>

    56     class Point {

    57

    58     public:

    59

    60       typedef T Value;

    61

    62       ///First coordinate

    63       T x;

    64       ///Second coordinate

    65       T y;

    66

    67       ///Default constructor

    68       Point() {}

    69

    70       ///Construct an instance from coordinates

    71       Point(T a, T b) : x(a), y(b) { }

    72

    73       ///The dimension of the vector.

    74

    75       ///The dimension of the vector.

    76       ///This function always returns 2.

    77       int size() const { return 2; }

    78

    79       ///Subscripting operator

    80

    81       ///\c p[0] is \c p.x and \c p[1] is \c p.y

    82       ///

    83       T& operator[](int idx) { return idx == 0 ? x : y; }

    84

    85       ///Const subscripting operator

    86

    87       ///\c p[0] is \c p.x and \c p[1] is \c p.y

    88       ///

    89       const T& operator[](int idx) const { return idx == 0 ? x : y; }

    90

    91       ///Conversion constructor

    92       template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}

    93

    94       ///Give back the square of the norm of the vector

    95       T normSquare() const {

    96         return x*x+y*y;

    97       }

    98

    99       ///Increment the left hand side by u

   100       Point<T>& operator +=(const Point<T>& u) {

   101         x += u.x;

   102         y += u.y;

   103         return *this;

   104       }

   105

   106       ///Decrement the left hand side by u

   107       Point<T>& operator -=(const Point<T>& u) {

   108         x -= u.x;

   109         y -= u.y;

   110         return *this;

   111       }

   112

   113       ///Multiply the left hand side with a scalar

   114       Point<T>& operator *=(const T &u) {

   115         x *= u;

   116         y *= u;

   117         return *this;

   118       }

   119

   120       ///Divide the left hand side by a scalar

   121       Point<T>& operator /=(const T &u) {

   122         x /= u;

   123         y /= u;

   124         return *this;

   125       }

   126

   127       ///Return the scalar product of two vectors

   128       T operator *(const Point<T>& u) const {

   129         return x*u.x+y*u.y;

   130       }

   131

   132       ///Return the sum of two vectors

   133       Point<T> operator+(const Point<T> &u) const {

   134         Point<T> b=*this;

   135         return b+=u;

   136       }

   137

   138       ///Return the negative of the vector

   139       Point<T> operator-() const {

   140         Point<T> b=*this;

   141         b.x=-b.x; b.y=-b.y;

   142         return b;

   143       }

   144

   145       ///Return the difference of two vectors

   146       Point<T> operator-(const Point<T> &u) const {

   147         Point<T> b=*this;

   148         return b-=u;

   149       }

   150

   151       ///Return a vector multiplied by a scalar

   152       Point<T> operator*(const T &u) const {

   153         Point<T> b=*this;

   154         return b*=u;

   155       }

   156

   157       ///Return a vector divided by a scalar

   158       Point<T> operator/(const T &u) const {

   159         Point<T> b=*this;

   160         return b/=u;

   161       }

   162

   163       ///Test equality

   164       bool operator==(const Point<T> &u) const {

   165         return (x==u.x) && (y==u.y);

   166       }

   167

   168       ///Test inequality

   169       bool operator!=(Point u) const {

   170         return  (x!=u.x) || (y!=u.y);

   171       }

   172

   173     };

   174

   175   ///Return a Point

   176

   177   ///Return a Point.

   178   ///\relates Point

   179   template <typename T>

   180   inline Point<T> makePoint(const T& x, const T& y) {

   181     return Point<T>(x, y);

   182   }

   183

   184   ///Return a vector multiplied by a scalar

   185

   186   ///Return a vector multiplied by a scalar.

   187   ///\relates Point

   188   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {

   189     return x*u;

   190   }

   191

   192   ///Read a plainvector from a stream

   193

   194   ///Read a plainvector from a stream.

   195   ///\relates Point

   196   ///

   197   template<typename T>

   198   inline std::istream& operator>>(std::istream &is, Point<T> &z) {

   199     char c;

   200     if (is >> c) {

   201       if (c != '(') is.putback(c);

   202     } else {

   203       is.clear();

   204     }

   205     if (!(is >> z.x)) return is;

   206     if (is >> c) {

   207       if (c != ',') is.putback(c);

   208     } else {

   209       is.clear();

   210     }

   211     if (!(is >> z.y)) return is;

   212     if (is >> c) {

   213       if (c != ')') is.putback(c);

   214     } else {

   215       is.clear();

   216     }

   217     return is;

   218   }

   219

   220   ///Write a plainvector to a stream

   221

   222   ///Write a plainvector to a stream.

   223   ///\relates Point

   224   ///

   225   template<typename T>

   226   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)

   227   {

   228     os << "(" << z.x << ", " << z.y << ")";

   229     return os;

   230   }

   231

   232   ///Rotate by 90 degrees

   233

   234   ///Returns the parameter rotated by 90 degrees in positive direction.

   235   ///\relates Point

   236   ///

   237   template<typename T>

   238   inline Point<T> rot90(const Point<T> &z)

   239   {

   240     return Point<T>(-z.y,z.x);

   241   }

   242

   243   ///Rotate by 180 degrees

   244

   245   ///Returns the parameter rotated by 180 degrees.

   246   ///\relates Point

   247   ///

   248   template<typename T>

   249   inline Point<T> rot180(const Point<T> &z)

   250   {

   251     return Point<T>(-z.x,-z.y);

   252   }

   253

   254   ///Rotate by 270 degrees

   255

   256   ///Returns the parameter rotated by 90 degrees in negative direction.

   257   ///\relates Point

   258   ///

   259   template<typename T>

   260   inline Point<T> rot270(const Point<T> &z)

   261   {

   262     return Point<T>(z.y,-z.x);

   263   }

   264

   265

   266

   267   /// A class to calculate or store the bounding box of plainvectors.

   268

   269   /// A class to calculate or store the bounding box of plainvectors.

   270   ///

   271     template<typename T>

   272     class BoundingBox {

   273       Point<T> bottom_left, top_right;

   274       bool _empty;

   275     public:

   276

   277       ///Default constructor: creates an empty bounding box

   278       BoundingBox() { _empty = true; }

   279

   280       ///Construct an instance from one point

   281       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }

   282

   283       ///Construct an instance from two points

   284

   285       ///Construct an instance from two points.

   286       ///\param a The bottom left corner.

   287       ///\param b The top right corner.

   288       ///\warning The coordinates of the bottom left corner must be no more

   289       ///than those of the top right one.

   290       BoundingBox(Point<T> a,Point<T> b)

   291       {

   292 	bottom_left=a;

   293 	top_right=b;

   294 	_empty = false;

   295       }

   296

   297       ///Construct an instance from four numbers

   298

   299       ///Construct an instance from four numbers.

   300       ///\param l The left side of the box.

   301       ///\param b The bottom of the box.

   302       ///\param r The right side of the box.

   303       ///\param t The top of the box.

   304       ///\warning The left side must be no more than the right side and

   305       ///bottom must be no more than the top.

   306       BoundingBox(T l,T b,T r,T t)

   307       {

   308 	bottom_left=Point<T>(l,b);

   309 	top_right=Point<T>(r,t);

   310 	_empty = false;

   311       }

   312

   313       ///Return \c true if the bounding box is empty.

   314

   315       ///Return \c true if the bounding box is empty (i.e. return \c false

   316       ///if at least one point was added to the box or the coordinates of

   317       ///the box were set).

   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=1;

   326       }

   327

   328       ///Give back the bottom left corner

   329

   330       ///Give back the bottom left corner.

   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

   337

   338       ///Set the bottom left corner.

   339       ///It should only be used for non-empty box.

   340       void bottomLeft(Point<T> p) {

   341 	bottom_left = p;

   342       }

   343

   344       ///Give back the top right corner

   345

   346       ///Give back the top right corner.

   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

   353

   354       ///Set the top right corner.

   355       ///It should only be used for non-empty box.

   356       void topRight(Point<T> p) {

   357 	top_right = p;

   358       }

   359

   360       ///Give back the bottom right corner

   361

   362       ///Give back the bottom right corner.

   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

   369

   370       ///Set the bottom right corner.

   371       ///It should only be used for non-empty box.

   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

   378

   379       ///Give back the top left corner.

   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

   386

   387       ///Set the top left corner.

   388       ///It should only be used for non-empty box.

   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       ///It should only be used for non-empty box.

   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       ///It should only be used for non-empty box.

   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       ///It should only be used for non-empty box.

   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       ///It should only be used for non-empty box.

   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           this->add(u.bottomLeft());

   509 	  this->add(u.topRight());

   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 (this->_empty || u._empty) {

   521 	  b._empty = true;

   522 	} else {

   523 	  b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);

   524 	  b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);

   525 	  b.top_right.x = std::min(this->top_right.x,u.top_right.x);

   526 	  b.top_right.y = std::min(this->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     ///

   678   template<class M>

   679   class NormSquareMap

   680   {

   681     const M& _map;

   682   public:

   683

   684     typedef typename M::Value::Value Value;

   685     typedef typename M::Key Key;

   686     ///\e

   687     NormSquareMap(const M &map) : _map(map) {}

   688     Value operator[](Key k) const {return _map[k].normSquare();}

   689   };

   690

   691   ///Returns a \ref NormSquareMap class

   692

   693   ///This function just returns a \ref NormSquareMap class.

   694   ///

   695   ///\ingroup maps

   696   ///\relates NormSquareMap

   697   template<class M>

   698   inline NormSquareMap<M> normSquareMap(const M &m)

   699   {

   700     return NormSquareMap<M>(m);

   701   }

   702

   703   /// @}

   704

   705   } //namespce dim2

   706

   707 } //namespace lemon

   708

   709 #endif //LEMON_DIM2_H