lemon/dim2.h
changeset 215 17c644f5f98d
parent 49 9a556af88710
child 220 a5d8c039f218
equal deleted inserted replaced
4:0ec0a16fabe7 5:d87a1b88ab1a
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    22 #include <iostream>
    22 #include <iostream>
    23 #include <lemon/bits/utility.h>
    23 #include <lemon/bits/utility.h>
    24 
    24 
    25 ///\ingroup misc
    25 ///\ingroup misc
    26 ///\file
    26 ///\file
    27 ///\brief A simple two dimensional vector and a bounding box implementation 
    27 ///\brief A simple two dimensional vector and a bounding box implementation
    28 ///
    28 ///
    29 /// The class \ref lemon::dim2::Point "dim2::Point" implements
    29 /// The class \ref lemon::dim2::Point "dim2::Point" implements
    30 /// a two dimensional vector with the usual operations.
    30 /// a two dimensional vector with the usual operations.
    31 ///
    31 ///
    32 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    32 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    57       typedef T Value;
    57       typedef T Value;
    58 
    58 
    59       ///First coordinate
    59       ///First coordinate
    60       T x;
    60       T x;
    61       ///Second coordinate
    61       ///Second coordinate
    62       T y;     
    62       T y;
    63       
    63 
    64       ///Default constructor
    64       ///Default constructor
    65       Point() {}
    65       Point() {}
    66 
    66 
    67       ///Construct an instance from coordinates
    67       ///Construct an instance from coordinates
    68       Point(T a, T b) : x(a), y(b) { }
    68       Point(T a, T b) : x(a), y(b) { }
    69 
    69 
    70       ///Returns the dimension of the vector (i.e. returns 2).
    70       ///Returns the dimension of the vector (i.e. returns 2).
    71 
    71 
    72       ///The dimension of the vector.
    72       ///The dimension of the vector.
    73       ///This function always returns 2. 
    73       ///This function always returns 2.
    74       int size() const { return 2; }
    74       int size() const { return 2; }
    75 
    75 
    76       ///Subscripting operator
    76       ///Subscripting operator
    77 
    77 
    78       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    78       ///\c p[0] is \c p.x and \c p[1] is \c p.y
    90 
    90 
    91       ///Give back the square of the norm of the vector
    91       ///Give back the square of the norm of the vector
    92       T normSquare() const {
    92       T normSquare() const {
    93         return x*x+y*y;
    93         return x*x+y*y;
    94       }
    94       }
    95   
    95 
    96       ///Increment the left hand side by \c u
    96       ///Increment the left hand side by \c u
    97       Point<T>& operator +=(const Point<T>& u) {
    97       Point<T>& operator +=(const Point<T>& u) {
    98         x += u.x;
    98         x += u.x;
    99         y += u.y;
    99         y += u.y;
   100         return *this;
   100         return *this;
   101       }
   101       }
   102   
   102 
   103       ///Decrement the left hand side by \c u
   103       ///Decrement the left hand side by \c u
   104       Point<T>& operator -=(const Point<T>& u) {
   104       Point<T>& operator -=(const Point<T>& u) {
   105         x -= u.x;
   105         x -= u.x;
   106         y -= u.y;
   106         y -= u.y;
   107         return *this;
   107         return *this;
   118       Point<T>& operator /=(const T &u) {
   118       Point<T>& operator /=(const T &u) {
   119         x /= u;
   119         x /= u;
   120         y /= u;
   120         y /= u;
   121         return *this;
   121         return *this;
   122       }
   122       }
   123   
   123 
   124       ///Return the scalar product of two vectors
   124       ///Return the scalar product of two vectors
   125       T operator *(const Point<T>& u) const {
   125       T operator *(const Point<T>& u) const {
   126         return x*u.x+y*u.y;
   126         return x*u.x+y*u.y;
   127       }
   127       }
   128   
   128 
   129       ///Return the sum of two vectors
   129       ///Return the sum of two vectors
   130       Point<T> operator+(const Point<T> &u) const {
   130       Point<T> operator+(const Point<T> &u) const {
   131         Point<T> b=*this;
   131         Point<T> b=*this;
   132         return b+=u;
   132         return b+=u;
   133       }
   133       }
   167         return  (x!=u.x) || (y!=u.y);
   167         return  (x!=u.x) || (y!=u.y);
   168       }
   168       }
   169 
   169 
   170     };
   170     };
   171 
   171 
   172   ///Return a Point 
   172   ///Return a Point
   173 
   173 
   174   ///Return a Point.
   174   ///Return a Point.
   175   ///\relates Point
   175   ///\relates Point
   176   template <typename T>
   176   template <typename T>
   177   inline Point<T> makePoint(const T& x, const T& y) {
   177   inline Point<T> makePoint(const T& x, const T& y) {
   257   inline Point<T> rot270(const Point<T> &z)
   257   inline Point<T> rot270(const Point<T> &z)
   258   {
   258   {
   259     return Point<T>(z.y,-z.x);
   259     return Point<T>(z.y,-z.x);
   260   }
   260   }
   261 
   261 
   262   
   262 
   263 
   263 
   264   /// A class to calculate or store the bounding box of plainvectors.
   264   /// A class to calculate or store the bounding box of plainvectors.
   265 
   265 
   266   /// A class to calculate or store the bounding box of plainvectors.
   266   /// A class to calculate or store the bounding box of plainvectors.
   267   ///
   267   ///
   268     template<typename T>
   268     template<typename T>
   269     class BoundingBox {
   269     class BoundingBox {
   270       Point<T> bottom_left, top_right;
   270       Point<T> bottom_left, top_right;
   271       bool _empty;
   271       bool _empty;
   272     public:
   272     public:
   273       
   273 
   274       ///Default constructor: creates an empty bounding box
   274       ///Default constructor: creates an empty bounding box
   275       BoundingBox() { _empty = true; }
   275       BoundingBox() { _empty = true; }
   276 
   276 
   277       ///Construct an instance from one point
   277       ///Construct an instance from one point
   278       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   278       BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   279       
   279 
   280       ///Construct an instance from two points
   280       ///Construct an instance from two points
   281       
   281 
   282       ///Construct an instance from two points.
   282       ///Construct an instance from two points.
   283       ///\param a The bottom left corner.
   283       ///\param a The bottom left corner.
   284       ///\param b The top right corner.
   284       ///\param b The top right corner.
   285       ///\warning The coordinates of the bottom left corner must be no more
   285       ///\warning The coordinates of the bottom left corner must be no more
   286       ///than those of the top right one.
   286       ///than those of the top right one.
   287       BoundingBox(Point<T> a,Point<T> b)
   287       BoundingBox(Point<T> a,Point<T> b)
   288       {
   288       {
   289 	bottom_left=a;
   289         bottom_left=a;
   290 	top_right=b;
   290         top_right=b;
   291 	_empty = false;
   291         _empty = false;
   292       }
   292       }
   293       
   293 
   294       ///Construct an instance from four numbers
   294       ///Construct an instance from four numbers
   295 
   295 
   296       ///Construct an instance from four numbers.
   296       ///Construct an instance from four numbers.
   297       ///\param l The left side of the box.
   297       ///\param l The left side of the box.
   298       ///\param b The bottom of the box.
   298       ///\param b The bottom of the box.
   299       ///\param r The right side of the box.
   299       ///\param r The right side of the box.
   300       ///\param t The top of the box.
   300       ///\param t The top of the box.
   301       ///\warning The left side must be no more than the right side and
   301       ///\warning The left side must be no more than the right side and
   302       ///bottom must be no more than the top. 
   302       ///bottom must be no more than the top.
   303       BoundingBox(T l,T b,T r,T t)
   303       BoundingBox(T l,T b,T r,T t)
   304       {
   304       {
   305 	bottom_left=Point<T>(l,b);
   305         bottom_left=Point<T>(l,b);
   306 	top_right=Point<T>(r,t);
   306         top_right=Point<T>(r,t);
   307 	_empty = false;
   307         _empty = false;
   308       }
   308       }
   309       
   309 
   310       ///Return \c true if the bounding box is empty.
   310       ///Return \c true if the bounding box is empty.
   311       
   311 
   312       ///Return \c true if the bounding box is empty (i.e. return \c false
   312       ///Return \c true if the bounding box is empty (i.e. return \c false
   313       ///if at least one point was added to the box or the coordinates of
   313       ///if at least one point was added to the box or the coordinates of
   314       ///the box were set).
   314       ///the box were set).
   315       ///
   315       ///
   316       ///The coordinates of an empty bounding box are not defined. 
   316       ///The coordinates of an empty bounding box are not defined.
   317       bool empty() const {
   317       bool empty() const {
   318         return _empty;
   318         return _empty;
   319       }
   319       }
   320       
   320 
   321       ///Make the BoundingBox empty
   321       ///Make the BoundingBox empty
   322       void clear() {
   322       void clear() {
   323         _empty=1;
   323         _empty=1;
   324       }
   324       }
   325 
   325 
   334       ///Set the bottom left corner of the box
   334       ///Set the bottom left corner of the box
   335 
   335 
   336       ///Set the bottom left corner of the box.
   336       ///Set the bottom left corner of the box.
   337       ///It should only be used for non-empty box.
   337       ///It should only be used for non-empty box.
   338       void bottomLeft(Point<T> p) {
   338       void bottomLeft(Point<T> p) {
   339 	bottom_left = p;
   339         bottom_left = p;
   340       }
   340       }
   341 
   341 
   342       ///Give back the top right corner of the box
   342       ///Give back the top right corner of the box
   343 
   343 
   344       ///Give back the top right corner of the box.
   344       ///Give back the top right corner of the box.
   350       ///Set the top right corner of the box
   350       ///Set the top right corner of the box
   351 
   351 
   352       ///Set the top right corner of the box.
   352       ///Set the top right corner of the box.
   353       ///It should only be used for non-empty box.
   353       ///It should only be used for non-empty box.
   354       void topRight(Point<T> p) {
   354       void topRight(Point<T> p) {
   355 	top_right = p;
   355         top_right = p;
   356       }
   356       }
   357 
   357 
   358       ///Give back the bottom right corner of the box
   358       ///Give back the bottom right corner of the box
   359 
   359 
   360       ///Give back the bottom right corner of the box.
   360       ///Give back the bottom right corner of the box.
   366       ///Set the bottom right corner of the box
   366       ///Set the bottom right corner of the box
   367 
   367 
   368       ///Set the bottom right corner of the box.
   368       ///Set the bottom right corner of the box.
   369       ///It should only be used for non-empty box.
   369       ///It should only be used for non-empty box.
   370       void bottomRight(Point<T> p) {
   370       void bottomRight(Point<T> p) {
   371 	top_right.x = p.x;
   371         top_right.x = p.x;
   372 	bottom_left.y = p.y;
   372         bottom_left.y = p.y;
   373       }
   373       }
   374  
   374 
   375       ///Give back the top left corner of the box
   375       ///Give back the top left corner of the box
   376 
   376 
   377       ///Give back the top left corner of the box.
   377       ///Give back the top left corner of the box.
   378       ///If the bounding box is empty, then the return value is not defined.
   378       ///If the bounding box is empty, then the return value is not defined.
   379       Point<T> topLeft() const {
   379       Point<T> topLeft() const {
   383       ///Set the top left corner of the box
   383       ///Set the top left corner of the box
   384 
   384 
   385       ///Set the top left corner of the box.
   385       ///Set the top left corner of the box.
   386       ///It should only be used for non-empty box.
   386       ///It should only be used for non-empty box.
   387       void topLeft(Point<T> p) {
   387       void topLeft(Point<T> p) {
   388 	top_right.y = p.y;
   388         top_right.y = p.y;
   389 	bottom_left.x = p.x;
   389         bottom_left.x = p.x;
   390       }
   390       }
   391 
   391 
   392       ///Give back the bottom of the box
   392       ///Give back the bottom of the box
   393 
   393 
   394       ///Give back the bottom of the box.
   394       ///Give back the bottom of the box.
   400       ///Set the bottom of the box
   400       ///Set the bottom of the box
   401 
   401 
   402       ///Set the bottom of the box.
   402       ///Set the bottom of the box.
   403       ///It should only be used for non-empty box.
   403       ///It should only be used for non-empty box.
   404       void bottom(T t) {
   404       void bottom(T t) {
   405 	bottom_left.y = t;
   405         bottom_left.y = t;
   406       }
   406       }
   407 
   407 
   408       ///Give back the top of the box
   408       ///Give back the top of the box
   409 
   409 
   410       ///Give back the top of the box.
   410       ///Give back the top of the box.
   416       ///Set the top of the box
   416       ///Set the top of the box
   417 
   417 
   418       ///Set the top of the box.
   418       ///Set the top of the box.
   419       ///It should only be used for non-empty box.
   419       ///It should only be used for non-empty box.
   420       void top(T t) {
   420       void top(T t) {
   421 	top_right.y = t;
   421         top_right.y = t;
   422       }
   422       }
   423 
   423 
   424       ///Give back the left side of the box
   424       ///Give back the left side of the box
   425 
   425 
   426       ///Give back the left side of the box.
   426       ///Give back the left side of the box.
   427       ///If the bounding box is empty, then the return value is not defined.
   427       ///If the bounding box is empty, then the return value is not defined.
   428       T left() const {
   428       T left() const {
   429         return bottom_left.x;
   429         return bottom_left.x;
   430       }
   430       }
   431  
   431 
   432       ///Set the left side of the box
   432       ///Set the left side of the box
   433 
   433 
   434       ///Set the left side of the box.
   434       ///Set the left side of the box.
   435       ///It should only be used for non-empty box.
   435       ///It should only be used for non-empty box.
   436       void left(T t) {
   436       void left(T t) {
   437 	bottom_left.x = t;
   437         bottom_left.x = t;
   438       }
   438       }
   439 
   439 
   440       /// Give back the right side of the box
   440       /// Give back the right side of the box
   441 
   441 
   442       /// Give back the right side of the box.
   442       /// Give back the right side of the box.
   448       ///Set the right side of the box
   448       ///Set the right side of the box
   449 
   449 
   450       ///Set the right side of the box.
   450       ///Set the right side of the box.
   451       ///It should only be used for non-empty box.
   451       ///It should only be used for non-empty box.
   452       void right(T t) {
   452       void right(T t) {
   453 	top_right.x = t;
   453         top_right.x = t;
   454       }
   454       }
   455 
   455 
   456       ///Give back the height of the box
   456       ///Give back the height of the box
   457 
   457 
   458       ///Give back the height of the box.
   458       ///Give back the height of the box.
   476         else{
   476         else{
   477           return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
   477           return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
   478               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   478               (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   479         }
   479         }
   480       }
   480       }
   481   
   481 
   482       ///Increments a bounding box with a point
   482       ///Increments a bounding box with a point
   483 
   483 
   484       ///Increments a bounding box with a point.
   484       ///Increments a bounding box with a point.
   485       ///
   485       ///
   486       BoundingBox& add(const Point<T>& u){
   486       BoundingBox& add(const Point<T>& u){
   494           if (top_right.x < u.x) top_right.x = u.x;
   494           if (top_right.x < u.x) top_right.x = u.x;
   495           if (top_right.y < u.y) top_right.y = u.y;
   495           if (top_right.y < u.y) top_right.y = u.y;
   496         }
   496         }
   497         return *this;
   497         return *this;
   498       }
   498       }
   499     
   499 
   500       ///Increments a bounding box to contain another bounding box
   500       ///Increments a bounding box to contain another bounding box
   501       
   501 
   502       ///Increments a bounding box to contain another bounding box.
   502       ///Increments a bounding box to contain another bounding box.
   503       ///
   503       ///
   504       BoundingBox& add(const BoundingBox &u){
   504       BoundingBox& add(const BoundingBox &u){
   505         if ( !u.empty() ){
   505         if ( !u.empty() ){
   506           this->add(u.bottomLeft());
   506           this->add(u.bottomLeft());
   507 	  this->add(u.topRight());
   507           this->add(u.topRight());
   508         }
   508         }
   509         return *this;
   509         return *this;
   510       }
   510       }
   511   
   511 
   512       ///Intersection of two bounding boxes
   512       ///Intersection of two bounding boxes
   513 
   513 
   514       ///Intersection of two bounding boxes.
   514       ///Intersection of two bounding boxes.
   515       ///
   515       ///
   516       BoundingBox operator&(const BoundingBox& u) const {
   516       BoundingBox operator&(const BoundingBox& u) const {
   517         BoundingBox b;
   517         BoundingBox b;
   518         if (this->_empty || u._empty) {
   518         if (this->_empty || u._empty) {
   519 	  b._empty = true;
   519           b._empty = true;
   520 	} else {
   520         } else {
   521 	  b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
   521           b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
   522 	  b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
   522           b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
   523 	  b.top_right.x = std::min(this->top_right.x,u.top_right.x);
   523           b.top_right.x = std::min(this->top_right.x,u.top_right.x);
   524 	  b.top_right.y = std::min(this->top_right.y,u.top_right.y);
   524           b.top_right.y = std::min(this->top_right.y,u.top_right.y);
   525 	  b._empty = b.bottom_left.x > b.top_right.x ||
   525           b._empty = b.bottom_left.x > b.top_right.x ||
   526 	             b.bottom_left.y > b.top_right.y;
   526                      b.bottom_left.y > b.top_right.y;
   527 	} 
   527         }
   528         return b;
   528         return b;
   529       }
   529       }
   530 
   530 
   531     };//class Boundingbox
   531     };//class Boundingbox
   532 
   532 
   535 
   535 
   536   ///\ingroup maps
   536   ///\ingroup maps
   537   ///Map of x-coordinates of a \ref Point "Point"-map.
   537   ///Map of x-coordinates of a \ref Point "Point"-map.
   538   ///
   538   ///
   539   template<class M>
   539   template<class M>
   540   class XMap 
   540   class XMap
   541   {
   541   {
   542     M& _map;
   542     M& _map;
   543   public:
   543   public:
   544 
   544 
   545     typedef typename M::Value::Value Value;
   545     typedef typename M::Value::Value Value;
   547     ///\e
   547     ///\e
   548     XMap(M& map) : _map(map) {}
   548     XMap(M& map) : _map(map) {}
   549     Value operator[](Key k) const {return _map[k].x;}
   549     Value operator[](Key k) const {return _map[k].x;}
   550     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
   550     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
   551   };
   551   };
   552     
   552 
   553   ///Returns an \ref XMap class
   553   ///Returns an \ref XMap class
   554 
   554 
   555   ///This function just returns an \ref XMap class.
   555   ///This function just returns an \ref XMap class.
   556   ///
   556   ///
   557   ///\ingroup maps
   557   ///\ingroup maps
   558   ///\relates XMap
   558   ///\relates XMap
   559   template<class M> 
   559   template<class M>
   560   inline XMap<M> xMap(M &m) 
   560   inline XMap<M> xMap(M &m)
   561   {
   561   {
   562     return XMap<M>(m);
   562     return XMap<M>(m);
   563   }
   563   }
   564 
   564 
   565   template<class M> 
   565   template<class M>
   566   inline XMap<M> xMap(const M &m) 
   566   inline XMap<M> xMap(const M &m)
   567   {
   567   {
   568     return XMap<M>(m);
   568     return XMap<M>(m);
   569   }
   569   }
   570 
   570 
   571   ///Constant (read only) version of \ref XMap
   571   ///Constant (read only) version of \ref XMap
   572 
   572 
   573   ///\ingroup maps
   573   ///\ingroup maps
   574   ///Constant (read only) version of \ref XMap
   574   ///Constant (read only) version of \ref XMap
   575   ///
   575   ///
   576   template<class M>
   576   template<class M>
   577   class ConstXMap 
   577   class ConstXMap
   578   {
   578   {
   579     const M& _map;
   579     const M& _map;
   580   public:
   580   public:
   581 
   581 
   582     typedef typename M::Value::Value Value;
   582     typedef typename M::Value::Value Value;
   583     typedef typename M::Key Key;
   583     typedef typename M::Key Key;
   584     ///\e
   584     ///\e
   585     ConstXMap(const M &map) : _map(map) {}
   585     ConstXMap(const M &map) : _map(map) {}
   586     Value operator[](Key k) const {return _map[k].x;}
   586     Value operator[](Key k) const {return _map[k].x;}
   587   };
   587   };
   588     
   588 
   589   ///Returns a \ref ConstXMap class
   589   ///Returns a \ref ConstXMap class
   590 
   590 
   591   ///This function just returns a \ref ConstXMap class.
   591   ///This function just returns a \ref ConstXMap class.
   592   ///
   592   ///
   593   ///\ingroup maps
   593   ///\ingroup maps
   594   ///\relates ConstXMap
   594   ///\relates ConstXMap
   595   template<class M> 
   595   template<class M>
   596   inline ConstXMap<M> xMap(const M &m) 
   596   inline ConstXMap<M> xMap(const M &m)
   597   {
   597   {
   598     return ConstXMap<M>(m);
   598     return ConstXMap<M>(m);
   599   }
   599   }
   600 
   600 
   601   ///Map of y-coordinates of a \ref Point "Point"-map
   601   ///Map of y-coordinates of a \ref Point "Point"-map
   602     
   602 
   603   ///\ingroup maps
   603   ///\ingroup maps
   604   ///Map of y-coordinates of a \ref Point "Point"-map.
   604   ///Map of y-coordinates of a \ref Point "Point"-map.
   605   ///
   605   ///
   606   template<class M>
   606   template<class M>
   607   class YMap 
   607   class YMap
   608   {
   608   {
   609     M& _map;
   609     M& _map;
   610   public:
   610   public:
   611 
   611 
   612     typedef typename M::Value::Value Value;
   612     typedef typename M::Value::Value Value;
   621 
   621 
   622   ///This function just returns a \ref YMap class.
   622   ///This function just returns a \ref YMap class.
   623   ///
   623   ///
   624   ///\ingroup maps
   624   ///\ingroup maps
   625   ///\relates YMap
   625   ///\relates YMap
   626   template<class M> 
   626   template<class M>
   627   inline YMap<M> yMap(M &m) 
   627   inline YMap<M> yMap(M &m)
   628   {
   628   {
   629     return YMap<M>(m);
   629     return YMap<M>(m);
   630   }
   630   }
   631 
   631 
   632   template<class M> 
   632   template<class M>
   633   inline YMap<M> yMap(const M &m) 
   633   inline YMap<M> yMap(const M &m)
   634   {
   634   {
   635     return YMap<M>(m);
   635     return YMap<M>(m);
   636   }
   636   }
   637 
   637 
   638   ///Constant (read only) version of \ref YMap
   638   ///Constant (read only) version of \ref YMap
   639 
   639 
   640   ///\ingroup maps
   640   ///\ingroup maps
   641   ///Constant (read only) version of \ref YMap
   641   ///Constant (read only) version of \ref YMap
   642   ///
   642   ///
   643   template<class M>
   643   template<class M>
   644   class ConstYMap 
   644   class ConstYMap
   645   {
   645   {
   646     const M& _map;
   646     const M& _map;
   647   public:
   647   public:
   648 
   648 
   649     typedef typename M::Value::Value Value;
   649     typedef typename M::Value::Value Value;
   650     typedef typename M::Key Key;
   650     typedef typename M::Key Key;
   651     ///\e
   651     ///\e
   652     ConstYMap(const M &map) : _map(map) {}
   652     ConstYMap(const M &map) : _map(map) {}
   653     Value operator[](Key k) const {return _map[k].y;}
   653     Value operator[](Key k) const {return _map[k].y;}
   654   };
   654   };
   655     
   655 
   656   ///Returns a \ref ConstYMap class
   656   ///Returns a \ref ConstYMap class
   657 
   657 
   658   ///This function just returns a \ref ConstYMap class.
   658   ///This function just returns a \ref ConstYMap class.
   659   ///
   659   ///
   660   ///\ingroup maps
   660   ///\ingroup maps
   661   ///\relates ConstYMap
   661   ///\relates ConstYMap
   662   template<class M> 
   662   template<class M>
   663   inline ConstYMap<M> yMap(const M &m) 
   663   inline ConstYMap<M> yMap(const M &m)
   664   {
   664   {
   665     return ConstYMap<M>(m);
   665     return ConstYMap<M>(m);
   666   }
   666   }
   667 
   667 
   668 
   668 
   671   ///
   671   ///
   672   ///Map of the \ref Point::normSquare() "normSquare()"
   672   ///Map of the \ref Point::normSquare() "normSquare()"
   673   ///of a \ref Point "Point"-map.
   673   ///of a \ref Point "Point"-map.
   674   ///\ingroup maps
   674   ///\ingroup maps
   675   template<class M>
   675   template<class M>
   676   class NormSquareMap 
   676   class NormSquareMap
   677   {
   677   {
   678     const M& _map;
   678     const M& _map;
   679   public:
   679   public:
   680 
   680 
   681     typedef typename M::Value::Value Value;
   681     typedef typename M::Value::Value Value;
   682     typedef typename M::Key Key;
   682     typedef typename M::Key Key;
   683     ///\e
   683     ///\e
   684     NormSquareMap(const M &map) : _map(map) {}
   684     NormSquareMap(const M &map) : _map(map) {}
   685     Value operator[](Key k) const {return _map[k].normSquare();}
   685     Value operator[](Key k) const {return _map[k].normSquare();}
   686   };
   686   };
   687     
   687 
   688   ///Returns a \ref NormSquareMap class
   688   ///Returns a \ref NormSquareMap class
   689 
   689 
   690   ///This function just returns a \ref NormSquareMap class.
   690   ///This function just returns a \ref NormSquareMap class.
   691   ///
   691   ///
   692   ///\ingroup maps
   692   ///\ingroup maps
   693   ///\relates NormSquareMap
   693   ///\relates NormSquareMap
   694   template<class M> 
   694   template<class M>
   695   inline NormSquareMap<M> normSquareMap(const M &m) 
   695   inline NormSquareMap<M> normSquareMap(const M &m)
   696   {
   696   {
   697     return NormSquareMap<M>(m);
   697     return NormSquareMap<M>(m);
   698   }
   698   }
   699 
   699 
   700   /// @}
   700   /// @}
   701 
   701 
   702   } //namespce dim2
   702   } //namespce dim2
   703   
   703 
   704 } //namespace lemon
   704 } //namespace lemon
   705 
   705 
   706 #endif //LEMON_DIM2_H
   706 #endif //LEMON_DIM2_H