lemon/dim2.h
 author Alpar Juttner Mon, 06 Oct 2008 11:01:03 +0100 changeset 297 92b193385702 parent 250 d0aae16df1bb child 313 64f8f7cc6168 permissions -rw-r--r--
Merge
     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 (\ref Point 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 \ref Point "Point"-map

   577

   578   ///\ingroup maps

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

   580   ///

   581   template<class M>

   582   class XMap

   583   {

   584     M& _map;

   585   public:

   586

   587     typedef typename M::Value::Value Value;

   588     typedef typename M::Key Key;

   589     ///\e

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

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

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

   593   };

   594

   595   ///Returns an \ref XMap class

   596

   597   ///This function just returns an \ref XMap class.

   598   ///

   599   ///\ingroup maps

   600   ///\relates XMap

   601   template<class M>

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

   603   {

   604     return XMap<M>(m);

   605   }

   606

   607   template<class M>

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

   609   {

   610     return XMap<M>(m);

   611   }

   612

   613   ///Constant (read only) version of \ref XMap

   614

   615   ///\ingroup maps

   616   ///Constant (read only) version of \ref XMap

   617   ///

   618   template<class M>

   619   class ConstXMap

   620   {

   621     const M& _map;

   622   public:

   623

   624     typedef typename M::Value::Value Value;

   625     typedef typename M::Key Key;

   626     ///\e

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

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

   629   };

   630

   631   ///Returns a \ref ConstXMap class

   632

   633   ///This function just returns a \ref ConstXMap class.

   634   ///

   635   ///\ingroup maps

   636   ///\relates ConstXMap

   637   template<class M>

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

   639   {

   640     return ConstXMap<M>(m);

   641   }

   642

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

   644

   645   ///\ingroup maps

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

   647   ///

   648   template<class M>

   649   class YMap

   650   {

   651     M& _map;

   652   public:

   653

   654     typedef typename M::Value::Value Value;

   655     typedef typename M::Key Key;

   656     ///\e

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

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

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

   660   };

   661

   662   ///Returns a \ref YMap class

   663

   664   ///This function just returns a \ref YMap class.

   665   ///

   666   ///\ingroup maps

   667   ///\relates YMap

   668   template<class M>

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

   670   {

   671     return YMap<M>(m);

   672   }

   673

   674   template<class M>

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

   676   {

   677     return YMap<M>(m);

   678   }

   679

   680   ///Constant (read only) version of \ref YMap

   681

   682   ///\ingroup maps

   683   ///Constant (read only) version of \ref YMap

   684   ///

   685   template<class M>

   686   class ConstYMap

   687   {

   688     const M& _map;

   689   public:

   690

   691     typedef typename M::Value::Value Value;

   692     typedef typename M::Key Key;

   693     ///\e

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

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

   696   };

   697

   698   ///Returns a \ref ConstYMap class

   699

   700   ///This function just returns a \ref ConstYMap class.

   701   ///

   702   ///\ingroup maps

   703   ///\relates ConstYMap

   704   template<class M>

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

   706   {

   707     return ConstYMap<M>(m);

   708   }

   709

   710

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

   712   ///of a \ref Point "Point"-map

   713   ///

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

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

   716   ///\ingroup maps

   717   template<class M>

   718   class NormSquareMap

   719   {

   720     const M& _map;

   721   public:

   722

   723     typedef typename M::Value::Value Value;

   724     typedef typename M::Key Key;

   725     ///\e

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

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

   728   };

   729

   730   ///Returns a \ref NormSquareMap class

   731

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

   733   ///

   734   ///\ingroup maps

   735   ///\relates NormSquareMap

   736   template<class M>

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

   738   {

   739     return NormSquareMap<M>(m);

   740   }

   741

   742   /// @}

   743

   744   } //namespce dim2

   745

   746 } //namespace lemon

   747

   748 #endif //LEMON_DIM2_H