lemon/dim2.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 21 Dec 2008 20:45:25 +0100
changeset 438 81d40f1c850c
parent 313 64f8f7cc6168
child 440 88ed40ad0d4f
permissions -rw-r--r--
Bug fix in heap unionfind (ticket #197)

The previous bugfix set the minimum value in internal nodes
wrongly. It corrects the problem.
     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