lemon/dim2.h
 author Alpar Juttner Thu, 04 Aug 2011 22:00:57 +0200 changeset 924 3dcb45a871c3 parent 313 64f8f7cc6168 child 440 88ed40ad0d4f permissions -rw-r--r--
Update the AUTHORS file
     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::Box "dim2::Box" can be used to determine

    32 /// the rectangular bounding box of a set of

    33 /// \ref lemon::dim2::Point "dim2::Point"'s.

    34

    35 namespace lemon {

    36

    37   ///Tools for handling two dimensional coordinates

    38

    39   ///This namespace is a storage of several

    40   ///tools for handling two dimensional coordinates

    41   namespace dim2 {

    42

    43   /// \addtogroup misc

    44   /// @{

    45

    46   /// Two dimensional vector (plain vector)

    47

    48   /// A simple two dimensional vector (plain vector) implementation

    49   /// with the usual vector operations.

    50   template<typename T>

    51     class Point {

    52

    53     public:

    54

    55       typedef T Value;

    56

    57       ///First coordinate

    58       T x;

    59       ///Second coordinate

    60       T y;

    61

    62       ///Default constructor

    63       Point() {}

    64

    65       ///Construct an instance from coordinates

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

    67

    68       ///Returns the dimension of the vector (i.e. returns 2).

    69

    70       ///The dimension of the vector.

    71       ///This function always returns 2.

    72       int size() const { return 2; }

    73

    74       ///Subscripting operator

    75

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

    77       ///

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

    79

    80       ///Const subscripting operator

    81

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

    83       ///

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

    85

    86       ///Conversion constructor

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

    88

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

    90       T normSquare() const {

    91         return x*x+y*y;

    92       }

    93

    94       ///Increment the left hand side by \c u

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

    96         x += u.x;

    97         y += u.y;

    98         return *this;

    99       }

   100

   101       ///Decrement the left hand side by \c u

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

   103         x -= u.x;

   104         y -= u.y;

   105         return *this;

   106       }

   107

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

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

   110         x *= u;

   111         y *= u;

   112         return *this;

   113       }

   114

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

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

   117         x /= u;

   118         y /= u;

   119         return *this;

   120       }

   121

   122       ///Return the scalar product of two vectors

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

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

   125       }

   126

   127       ///Return the sum of two vectors

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

   129         Point<T> b=*this;

   130         return b+=u;

   131       }

   132

   133       ///Return the negative of the vector

   134       Point<T> operator-() const {

   135         Point<T> b=*this;

   136         b.x=-b.x; b.y=-b.y;

   137         return b;

   138       }

   139

   140       ///Return the difference of two vectors

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

   142         Point<T> b=*this;

   143         return b-=u;

   144       }

   145

   146       ///Return a vector multiplied by a scalar

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

   148         Point<T> b=*this;

   149         return b*=u;

   150       }

   151

   152       ///Return a vector divided by a scalar

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

   154         Point<T> b=*this;

   155         return b/=u;

   156       }

   157

   158       ///Test equality

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

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

   161       }

   162

   163       ///Test inequality

   164       bool operator!=(Point u) const {

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

   166       }

   167

   168     };

   169

   170   ///Return a Point

   171

   172   ///Return a Point.

   173   ///\relates Point

   174   template <typename T>

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

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

   177   }

   178

   179   ///Return a vector multiplied by a scalar

   180

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

   182   ///\relates Point

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

   184     return x*u;

   185   }

   186

   187   ///Read a plain vector from a stream

   188

   189   ///Read a plain vector from a stream.

   190   ///\relates Point

   191   ///

   192   template<typename T>

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

   194     char c;

   195     if (is >> c) {

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

   197     } else {

   198       is.clear();

   199     }

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

   201     if (is >> c) {

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

   203     } else {

   204       is.clear();

   205     }

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

   207     if (is >> c) {

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

   209     } else {

   210       is.clear();

   211     }

   212     return is;

   213   }

   214

   215   ///Write a plain vector to a stream

   216

   217   ///Write a plain vector to a stream.

   218   ///\relates Point

   219   ///

   220   template<typename T>

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

   222   {

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

   224     return os;

   225   }

   226

   227   ///Rotate by 90 degrees

   228

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

   230   ///\relates Point

   231   ///

   232   template<typename T>

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

   234   {

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

   236   }

   237

   238   ///Rotate by 180 degrees

   239

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

   241   ///\relates Point

   242   ///

   243   template<typename T>

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

   245   {

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

   247   }

   248

   249   ///Rotate by 270 degrees

   250

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

   252   ///\relates Point

   253   ///

   254   template<typename T>

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

   256   {

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

   258   }

   259

   260

   261

   262   /// Bounding box of plain vectors (points).

   263

   264   /// A class to calculate or store the bounding box of plain vectors

   265   /// (\ref Point "points").

   266   template<typename T>

   267   class Box {

   268       Point<T> _bottom_left, _top_right;

   269       bool _empty;

   270     public:

   271

   272       ///Default constructor: creates an empty box

   273       Box() { _empty = true; }

   274

   275       ///Construct a box from one point

   276       Box(Point<T> a) {

   277         _bottom_left = _top_right = a;

   278         _empty = false;

   279       }

   280

   281       ///Construct a box from two points

   282

   283       ///Construct a box from two points.

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

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

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

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

   288       Box(Point<T> a,Point<T> b)

   289       {

   290         _bottom_left = a;

   291         _top_right = b;

   292         _empty = false;

   293       }

   294

   295       ///Construct a box from four numbers

   296

   297       ///Construct a box from four numbers.

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

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

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

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

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

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

   304       Box(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       ///Return \c true if the box is empty.

   312

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

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

   315       ///the box were set).

   316       ///

   317       ///The coordinates of an empty box are not defined.

   318       bool empty() const {

   319         return _empty;

   320       }

   321

   322       ///Make the box empty

   323       void clear() {

   324         _empty = true;

   325       }

   326

   327       ///Give back the bottom left corner of the box

   328

   329       ///Give back the bottom left corner of the box.

   330       ///If the box is empty, then the return value is not defined.

   331       Point<T> bottomLeft() const {

   332         return _bottom_left;

   333       }

   334

   335       ///Set the bottom left corner of the box

   336

   337       ///Set the bottom left corner of the box.

   338       ///\pre The box must not be empty.

   339       void bottomLeft(Point<T> p) {

   340         _bottom_left = p;

   341       }

   342

   343       ///Give back the top right corner of the box

   344

   345       ///Give back the top right corner of the box.

   346       ///If the box is empty, then the return value is not defined.

   347       Point<T> topRight() const {

   348         return _top_right;

   349       }

   350

   351       ///Set the top right corner of the box

   352

   353       ///Set the top right corner of the box.

   354       ///\pre The box must not be empty.

   355       void topRight(Point<T> p) {

   356         _top_right = p;

   357       }

   358

   359       ///Give back the bottom right corner of the box

   360

   361       ///Give back the bottom right corner of the box.

   362       ///If the box is empty, then the return value is not defined.

   363       Point<T> bottomRight() const {

   364         return Point<T>(_top_right.x,_bottom_left.y);

   365       }

   366

   367       ///Set the bottom right corner of the box

   368

   369       ///Set the bottom right corner of the box.

   370       ///\pre The box must not be empty.

   371       void bottomRight(Point<T> p) {

   372         _top_right.x = p.x;

   373         _bottom_left.y = p.y;

   374       }

   375

   376       ///Give back the top left corner of the box

   377

   378       ///Give back the top left corner of the box.

   379       ///If the box is empty, then the return value is not defined.

   380       Point<T> topLeft() const {

   381         return Point<T>(_bottom_left.x,_top_right.y);

   382       }

   383

   384       ///Set the top left corner of the box

   385

   386       ///Set the top left corner of the box.

   387       ///\pre The box must not be empty.

   388       void topLeft(Point<T> p) {

   389         _top_right.y = p.y;

   390         _bottom_left.x = p.x;

   391       }

   392

   393       ///Give back the bottom of the box

   394

   395       ///Give back the bottom of the box.

   396       ///If the box is empty, then the return value is not defined.

   397       T bottom() const {

   398         return _bottom_left.y;

   399       }

   400

   401       ///Set the bottom of the box

   402

   403       ///Set the bottom of the box.

   404       ///\pre The box must not be empty.

   405       void bottom(T t) {

   406         _bottom_left.y = t;

   407       }

   408

   409       ///Give back the top of the box

   410

   411       ///Give back the top of the box.

   412       ///If the box is empty, then the return value is not defined.

   413       T top() const {

   414         return _top_right.y;

   415       }

   416

   417       ///Set the top of the box

   418

   419       ///Set the top of the box.

   420       ///\pre The box must not be empty.

   421       void top(T t) {

   422         _top_right.y = t;

   423       }

   424

   425       ///Give back the left side of the box

   426

   427       ///Give back the left side of the box.

   428       ///If the box is empty, then the return value is not defined.

   429       T left() const {

   430         return _bottom_left.x;

   431       }

   432

   433       ///Set the left side of the box

   434

   435       ///Set the left side of the box.

   436       ///\pre The box must not be empty.

   437       void left(T t) {

   438         _bottom_left.x = t;

   439       }

   440

   441       /// Give back the right side of the box

   442

   443       /// Give back the right side of the box.

   444       ///If the box is empty, then the return value is not defined.

   445       T right() const {

   446         return _top_right.x;

   447       }

   448

   449       ///Set the right side of the box

   450

   451       ///Set the right side of the box.

   452       ///\pre The box must not be empty.

   453       void right(T t) {

   454         _top_right.x = t;

   455       }

   456

   457       ///Give back the height of the box

   458

   459       ///Give back the height of the box.

   460       ///If the box is empty, then the return value is not defined.

   461       T height() const {

   462         return _top_right.y-_bottom_left.y;

   463       }

   464

   465       ///Give back the width of the box

   466

   467       ///Give back the width of the box.

   468       ///If the box is empty, then the return value is not defined.

   469       T width() const {

   470         return _top_right.x-_bottom_left.x;

   471       }

   472

   473       ///Checks whether a point is inside the box

   474       bool inside(const Point<T>& u) const {

   475         if (_empty)

   476           return false;

   477         else {

   478           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&

   479                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );

   480         }

   481       }

   482

   483       ///Increments the box with a point

   484

   485       ///Increments the box with a point.

   486       ///

   487       Box& add(const Point<T>& u){

   488         if (_empty) {

   489           _bottom_left = _top_right = u;

   490           _empty = false;

   491         }

   492         else {

   493           if (_bottom_left.x > u.x) _bottom_left.x = u.x;

   494           if (_bottom_left.y > u.y) _bottom_left.y = u.y;

   495           if (_top_right.x < u.x) _top_right.x = u.x;

   496           if (_top_right.y < u.y) _top_right.y = u.y;

   497         }

   498         return *this;

   499       }

   500

   501       ///Increments the box to contain another box

   502

   503       ///Increments the box to contain another box.

   504       ///

   505       Box& add(const Box &u){

   506         if ( !u.empty() ){

   507           add(u._bottom_left);

   508           add(u._top_right);

   509         }

   510         return *this;

   511       }

   512

   513       ///Intersection of two boxes

   514

   515       ///Intersection of two boxes.

   516       ///

   517       Box operator&(const Box& u) const {

   518         Box b;

   519         if (_empty || u._empty) {

   520           b._empty = true;

   521         } else {

   522           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);

   523           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);

   524           b._top_right.x = std::min(_top_right.x, u._top_right.x);

   525           b._top_right.y = std::min(_top_right.y, u._top_right.y);

   526           b._empty = b._bottom_left.x > b._top_right.x ||

   527                      b._bottom_left.y > b._top_right.y;

   528         }

   529         return b;

   530       }

   531

   532   };//class Box

   533

   534

   535   ///Read a box from a stream

   536

   537   ///Read a box from a stream.

   538   ///\relates Box

   539   template<typename T>

   540   inline std::istream& operator>>(std::istream &is, Box<T>& b) {

   541     char c;

   542     Point<T> p;

   543     if (is >> c) {

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

   545     } else {

   546       is.clear();

   547     }

   548     if (!(is >> p)) return is;

   549     b.bottomLeft(p);

   550     if (is >> c) {

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

   552     } else {

   553       is.clear();

   554     }

   555     if (!(is >> p)) return is;

   556     b.topRight(p);

   557     if (is >> c) {

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

   559     } else {

   560       is.clear();

   561     }

   562     return is;

   563   }

   564

   565   ///Write a box to a stream

   566

   567   ///Write a box to a stream.

   568   ///\relates Box

   569   template<typename T>

   570   inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)

   571   {

   572     os << "(" << b.bottomLeft() << "," << b.topRight() << ")";

   573     return os;

   574   }

   575

   576   ///Map of x-coordinates of a <tt>Point</tt>-map

   577

   578   ///Map of x-coordinates of a \ref Point "Point"-map.

   579   ///

   580   template<class M>

   581   class XMap

   582   {

   583     M& _map;

   584   public:

   585

   586     typedef typename M::Value::Value Value;

   587     typedef typename M::Key Key;

   588     ///\e

   589     XMap(M& map) : _map(map) {}

   590     Value operator[](Key k) const {return _map[k].x;}

   591     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}

   592   };

   593

   594   ///Returns an XMap class

   595

   596   ///This function just returns an XMap class.

   597   ///\relates XMap

   598   template<class M>

   599   inline XMap<M> xMap(M &m)

   600   {

   601     return XMap<M>(m);

   602   }

   603

   604   template<class M>

   605   inline XMap<M> xMap(const M &m)

   606   {

   607     return XMap<M>(m);

   608   }

   609

   610   ///Constant (read only) version of XMap

   611

   612   ///Constant (read only) version of XMap.

   613   ///

   614   template<class M>

   615   class ConstXMap

   616   {

   617     const M& _map;

   618   public:

   619

   620     typedef typename M::Value::Value Value;

   621     typedef typename M::Key Key;

   622     ///\e

   623     ConstXMap(const M &map) : _map(map) {}

   624     Value operator[](Key k) const {return _map[k].x;}

   625   };

   626

   627   ///Returns a ConstXMap class

   628

   629   ///This function just returns a ConstXMap class.

   630   ///\relates ConstXMap

   631   template<class M>

   632   inline ConstXMap<M> xMap(const M &m)

   633   {

   634     return ConstXMap<M>(m);

   635   }

   636

   637   ///Map of y-coordinates of a <tt>Point</tt>-map

   638

   639   ///Map of y-coordinates of a \ref Point "Point"-map.

   640   ///

   641   template<class M>

   642   class YMap

   643   {

   644     M& _map;

   645   public:

   646

   647     typedef typename M::Value::Value Value;

   648     typedef typename M::Key Key;

   649     ///\e

   650     YMap(M& map) : _map(map) {}

   651     Value operator[](Key k) const {return _map[k].y;}

   652     void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}

   653   };

   654

   655   ///Returns a YMap class

   656

   657   ///This function just returns a YMap class.

   658   ///\relates YMap

   659   template<class M>

   660   inline YMap<M> yMap(M &m)

   661   {

   662     return YMap<M>(m);

   663   }

   664

   665   template<class M>

   666   inline YMap<M> yMap(const M &m)

   667   {

   668     return YMap<M>(m);

   669   }

   670

   671   ///Constant (read only) version of YMap

   672

   673   ///Constant (read only) version of YMap.

   674   ///

   675   template<class M>

   676   class ConstYMap

   677   {

   678     const M& _map;

   679   public:

   680

   681     typedef typename M::Value::Value Value;

   682     typedef typename M::Key Key;

   683     ///\e

   684     ConstYMap(const M &map) : _map(map) {}

   685     Value operator[](Key k) const {return _map[k].y;}

   686   };

   687

   688   ///Returns a ConstYMap class

   689

   690   ///This function just returns a ConstYMap class.

   691   ///\relates ConstYMap

   692   template<class M>

   693   inline ConstYMap<M> yMap(const M &m)

   694   {

   695     return ConstYMap<M>(m);

   696   }

   697

   698

   699   ///\brief Map of the normSquare() of a <tt>Point</tt>-map

   700   ///

   701   ///Map of the \ref Point::normSquare() "normSquare()"

   702   ///of a \ref Point "Point"-map.

   703   template<class M>

   704   class NormSquareMap

   705   {

   706     const M& _map;

   707   public:

   708

   709     typedef typename M::Value::Value Value;

   710     typedef typename M::Key Key;

   711     ///\e

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

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

   714   };

   715

   716   ///Returns a NormSquareMap class

   717

   718   ///This function just returns a NormSquareMap class.

   719   ///\relates NormSquareMap

   720   template<class M>

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

   722   {

   723     return NormSquareMap<M>(m);

   724   }

   725

   726   /// @}

   727

   728   } //namespce dim2

   729

   730 } //namespace lemon

   731

   732 #endif //LEMON_DIM2_H