alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@8:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@8:  *
alpar@440:  * Copyright (C) 2003-2009
alpar@8:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@8:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@8:  *
alpar@8:  * Permission to use, modify and distribute this software is granted
alpar@8:  * provided that this copyright notice appears in all copies. For
alpar@8:  * precise terms see the accompanying LICENSE file.
alpar@8:  *
alpar@8:  * This software is provided "AS IS" with no warranty of any kind,
alpar@8:  * express or implied, and with no claim as to its suitability for any
alpar@8:  * purpose.
alpar@8:  *
alpar@8:  */
alpar@8: 
alpar@8: #ifndef LEMON_DIM2_H
alpar@8: #define LEMON_DIM2_H
alpar@8: 
alpar@8: #include <iostream>
alpar@8: 
alpar@8: ///\ingroup misc
alpar@8: ///\file
alpar@209: ///\brief A simple two dimensional vector and a bounding box implementation
alpar@8: ///
alpar@8: /// The class \ref lemon::dim2::Point "dim2::Point" implements
kpeter@49: /// a two dimensional vector with the usual operations.
alpar@8: ///
kpeter@253: /// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine
alpar@8: /// the rectangular bounding box of a set of
alpar@8: /// \ref lemon::dim2::Point "dim2::Point"'s.
alpar@8: 
alpar@8: namespace lemon {
alpar@8: 
alpar@8:   ///Tools for handling two dimensional coordinates
alpar@8: 
alpar@8:   ///This namespace is a storage of several
alpar@8:   ///tools for handling two dimensional coordinates
alpar@8:   namespace dim2 {
alpar@8: 
alpar@8:   /// \addtogroup misc
alpar@8:   /// @{
alpar@8: 
kpeter@253:   /// Two dimensional vector (plain vector)
alpar@8: 
kpeter@241:   /// A simple two dimensional vector (plain vector) implementation
kpeter@49:   /// with the usual vector operations.
alpar@8:   template<typename T>
alpar@8:     class Point {
alpar@8: 
alpar@8:     public:
alpar@8: 
alpar@8:       typedef T Value;
alpar@8: 
kpeter@15:       ///First coordinate
alpar@8:       T x;
kpeter@15:       ///Second coordinate
alpar@209:       T y;
alpar@209: 
alpar@8:       ///Default constructor
alpar@8:       Point() {}
alpar@8: 
alpar@8:       ///Construct an instance from coordinates
alpar@8:       Point(T a, T b) : x(a), y(b) { }
alpar@8: 
kpeter@49:       ///Returns the dimension of the vector (i.e. returns 2).
alpar@8: 
kpeter@15:       ///The dimension of the vector.
alpar@209:       ///This function always returns 2.
alpar@8:       int size() const { return 2; }
alpar@8: 
alpar@8:       ///Subscripting operator
alpar@8: 
alpar@8:       ///\c p[0] is \c p.x and \c p[1] is \c p.y
alpar@8:       ///
alpar@8:       T& operator[](int idx) { return idx == 0 ? x : y; }
alpar@8: 
alpar@8:       ///Const subscripting operator
alpar@8: 
alpar@8:       ///\c p[0] is \c p.x and \c p[1] is \c p.y
alpar@8:       ///
alpar@8:       const T& operator[](int idx) const { return idx == 0 ? x : y; }
alpar@8: 
alpar@8:       ///Conversion constructor
alpar@8:       template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
alpar@8: 
alpar@8:       ///Give back the square of the norm of the vector
alpar@8:       T normSquare() const {
alpar@8:         return x*x+y*y;
alpar@8:       }
alpar@209: 
kpeter@49:       ///Increment the left hand side by \c u
alpar@8:       Point<T>& operator +=(const Point<T>& u) {
alpar@8:         x += u.x;
alpar@8:         y += u.y;
alpar@8:         return *this;
alpar@8:       }
alpar@209: 
kpeter@49:       ///Decrement the left hand side by \c u
alpar@8:       Point<T>& operator -=(const Point<T>& u) {
alpar@8:         x -= u.x;
alpar@8:         y -= u.y;
alpar@8:         return *this;
alpar@8:       }
alpar@8: 
alpar@8:       ///Multiply the left hand side with a scalar
alpar@8:       Point<T>& operator *=(const T &u) {
alpar@8:         x *= u;
alpar@8:         y *= u;
alpar@8:         return *this;
alpar@8:       }
alpar@8: 
alpar@8:       ///Divide the left hand side by a scalar
alpar@8:       Point<T>& operator /=(const T &u) {
alpar@8:         x /= u;
alpar@8:         y /= u;
alpar@8:         return *this;
alpar@8:       }
alpar@209: 
alpar@8:       ///Return the scalar product of two vectors
alpar@8:       T operator *(const Point<T>& u) const {
alpar@8:         return x*u.x+y*u.y;
alpar@8:       }
alpar@209: 
alpar@8:       ///Return the sum of two vectors
alpar@8:       Point<T> operator+(const Point<T> &u) const {
alpar@8:         Point<T> b=*this;
alpar@8:         return b+=u;
alpar@8:       }
alpar@8: 
kpeter@15:       ///Return the negative of the vector
alpar@8:       Point<T> operator-() const {
alpar@8:         Point<T> b=*this;
alpar@8:         b.x=-b.x; b.y=-b.y;
alpar@8:         return b;
alpar@8:       }
alpar@8: 
alpar@8:       ///Return the difference of two vectors
alpar@8:       Point<T> operator-(const Point<T> &u) const {
alpar@8:         Point<T> b=*this;
alpar@8:         return b-=u;
alpar@8:       }
alpar@8: 
alpar@8:       ///Return a vector multiplied by a scalar
alpar@8:       Point<T> operator*(const T &u) const {
alpar@8:         Point<T> b=*this;
alpar@8:         return b*=u;
alpar@8:       }
alpar@8: 
alpar@8:       ///Return a vector divided by a scalar
alpar@8:       Point<T> operator/(const T &u) const {
alpar@8:         Point<T> b=*this;
alpar@8:         return b/=u;
alpar@8:       }
alpar@8: 
alpar@8:       ///Test equality
alpar@8:       bool operator==(const Point<T> &u) const {
alpar@8:         return (x==u.x) && (y==u.y);
alpar@8:       }
alpar@8: 
alpar@8:       ///Test inequality
alpar@8:       bool operator!=(Point u) const {
alpar@8:         return  (x!=u.x) || (y!=u.y);
alpar@8:       }
alpar@8: 
alpar@8:     };
alpar@8: 
alpar@209:   ///Return a Point
alpar@8: 
kpeter@15:   ///Return a Point.
alpar@8:   ///\relates Point
alpar@8:   template <typename T>
alpar@8:   inline Point<T> makePoint(const T& x, const T& y) {
alpar@8:     return Point<T>(x, y);
alpar@8:   }
alpar@8: 
alpar@8:   ///Return a vector multiplied by a scalar
alpar@8: 
kpeter@15:   ///Return a vector multiplied by a scalar.
alpar@8:   ///\relates Point
alpar@8:   template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
alpar@8:     return x*u;
alpar@8:   }
alpar@8: 
kpeter@241:   ///Read a plain vector from a stream
alpar@8: 
kpeter@241:   ///Read a plain vector from a stream.
alpar@8:   ///\relates Point
alpar@8:   ///
alpar@8:   template<typename T>
alpar@8:   inline std::istream& operator>>(std::istream &is, Point<T> &z) {
alpar@8:     char c;
alpar@8:     if (is >> c) {
alpar@8:       if (c != '(') is.putback(c);
alpar@8:     } else {
alpar@8:       is.clear();
alpar@8:     }
alpar@8:     if (!(is >> z.x)) return is;
alpar@8:     if (is >> c) {
alpar@8:       if (c != ',') is.putback(c);
alpar@8:     } else {
alpar@8:       is.clear();
alpar@8:     }
alpar@8:     if (!(is >> z.y)) return is;
alpar@8:     if (is >> c) {
alpar@8:       if (c != ')') is.putback(c);
alpar@8:     } else {
alpar@8:       is.clear();
alpar@8:     }
alpar@8:     return is;
alpar@8:   }
alpar@8: 
kpeter@241:   ///Write a plain vector to a stream
alpar@8: 
kpeter@241:   ///Write a plain vector to a stream.
alpar@8:   ///\relates Point
alpar@8:   ///
alpar@8:   template<typename T>
alpar@8:   inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
alpar@8:   {
kpeter@250:     os << "(" << z.x << "," << z.y << ")";
alpar@8:     return os;
alpar@8:   }
alpar@8: 
alpar@8:   ///Rotate by 90 degrees
alpar@8: 
kpeter@15:   ///Returns the parameter rotated by 90 degrees in positive direction.
alpar@8:   ///\relates Point
alpar@8:   ///
alpar@8:   template<typename T>
alpar@8:   inline Point<T> rot90(const Point<T> &z)
alpar@8:   {
alpar@8:     return Point<T>(-z.y,z.x);
alpar@8:   }
alpar@8: 
alpar@8:   ///Rotate by 180 degrees
alpar@8: 
kpeter@15:   ///Returns the parameter rotated by 180 degrees.
alpar@8:   ///\relates Point
alpar@8:   ///
alpar@8:   template<typename T>
alpar@8:   inline Point<T> rot180(const Point<T> &z)
alpar@8:   {
alpar@8:     return Point<T>(-z.x,-z.y);
alpar@8:   }
alpar@8: 
alpar@8:   ///Rotate by 270 degrees
alpar@8: 
kpeter@15:   ///Returns the parameter rotated by 90 degrees in negative direction.
alpar@8:   ///\relates Point
alpar@8:   ///
alpar@8:   template<typename T>
alpar@8:   inline Point<T> rot270(const Point<T> &z)
alpar@8:   {
alpar@8:     return Point<T>(z.y,-z.x);
alpar@8:   }
alpar@8: 
alpar@209: 
alpar@8: 
kpeter@313:   /// Bounding box of plain vectors (points).
alpar@8: 
kpeter@253:   /// A class to calculate or store the bounding box of plain vectors
kpeter@313:   /// (\ref Point "points").
kpeter@253:   template<typename T>
kpeter@253:   class Box {
kpeter@241:       Point<T> _bottom_left, _top_right;
alpar@8:       bool _empty;
alpar@8:     public:
alpar@209: 
kpeter@253:       ///Default constructor: creates an empty box
kpeter@253:       Box() { _empty = true; }
alpar@8: 
kpeter@253:       ///Construct a box from one point
kpeter@253:       Box(Point<T> a) {
kpeter@241:         _bottom_left = _top_right = a;
kpeter@241:         _empty = false;
kpeter@241:       }
alpar@209: 
kpeter@253:       ///Construct a box from two points
alpar@209: 
kpeter@253:       ///Construct a box from two points.
kpeter@15:       ///\param a The bottom left corner.
kpeter@15:       ///\param b The top right corner.
kpeter@15:       ///\warning The coordinates of the bottom left corner must be no more
kpeter@15:       ///than those of the top right one.
kpeter@253:       Box(Point<T> a,Point<T> b)
alpar@8:       {
kpeter@241:         _bottom_left = a;
kpeter@241:         _top_right = b;
alpar@209:         _empty = false;
alpar@8:       }
alpar@209: 
kpeter@253:       ///Construct a box from four numbers
alpar@8: 
kpeter@253:       ///Construct a box from four numbers.
kpeter@15:       ///\param l The left side of the box.
kpeter@15:       ///\param b The bottom of the box.
kpeter@15:       ///\param r The right side of the box.
kpeter@15:       ///\param t The top of the box.
kpeter@15:       ///\warning The left side must be no more than the right side and
alpar@209:       ///bottom must be no more than the top.
kpeter@253:       Box(T l,T b,T r,T t)
alpar@8:       {
kpeter@241:         _bottom_left=Point<T>(l,b);
kpeter@241:         _top_right=Point<T>(r,t);
alpar@209:         _empty = false;
alpar@8:       }
alpar@209: 
kpeter@253:       ///Return \c true if the box is empty.
alpar@209: 
kpeter@253:       ///Return \c true if the box is empty (i.e. return \c false
kpeter@15:       ///if at least one point was added to the box or the coordinates of
kpeter@15:       ///the box were set).
kpeter@49:       ///
kpeter@253:       ///The coordinates of an empty box are not defined.
alpar@8:       bool empty() const {
alpar@8:         return _empty;
alpar@8:       }
alpar@209: 
kpeter@253:       ///Make the box empty
alpar@8:       void clear() {
kpeter@241:         _empty = true;
alpar@8:       }
alpar@8: 
kpeter@49:       ///Give back the bottom left corner of the box
alpar@8: 
kpeter@49:       ///Give back the bottom left corner of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       Point<T> bottomLeft() const {
kpeter@241:         return _bottom_left;
alpar@8:       }
alpar@8: 
kpeter@49:       ///Set the bottom left corner of the box
alpar@8: 
kpeter@49:       ///Set the bottom left corner of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void bottomLeft(Point<T> p) {
kpeter@241:         _bottom_left = p;
alpar@8:       }
alpar@8: 
kpeter@49:       ///Give back the top right corner of the box
alpar@8: 
kpeter@49:       ///Give back the top right corner of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       Point<T> topRight() const {
kpeter@241:         return _top_right;
alpar@8:       }
alpar@8: 
kpeter@49:       ///Set the top right corner of the box
alpar@8: 
kpeter@49:       ///Set the top right corner of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void topRight(Point<T> p) {
kpeter@241:         _top_right = p;
alpar@8:       }
alpar@8: 
kpeter@49:       ///Give back the bottom right corner of the box
alpar@8: 
kpeter@49:       ///Give back the bottom right corner of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       Point<T> bottomRight() const {
kpeter@241:         return Point<T>(_top_right.x,_bottom_left.y);
alpar@8:       }
alpar@8: 
kpeter@49:       ///Set the bottom right corner of the box
alpar@8: 
kpeter@49:       ///Set the bottom right corner of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void bottomRight(Point<T> p) {
kpeter@241:         _top_right.x = p.x;
kpeter@241:         _bottom_left.y = p.y;
alpar@8:       }
alpar@209: 
kpeter@49:       ///Give back the top left corner of the box
alpar@8: 
kpeter@49:       ///Give back the top left corner of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       Point<T> topLeft() const {
kpeter@241:         return Point<T>(_bottom_left.x,_top_right.y);
alpar@8:       }
alpar@8: 
kpeter@49:       ///Set the top left corner of the box
alpar@8: 
kpeter@49:       ///Set the top left corner of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void topLeft(Point<T> p) {
kpeter@241:         _top_right.y = p.y;
kpeter@241:         _bottom_left.x = p.x;
alpar@8:       }
alpar@8: 
alpar@8:       ///Give back the bottom of the box
alpar@8: 
alpar@8:       ///Give back the bottom of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T bottom() const {
kpeter@241:         return _bottom_left.y;
alpar@8:       }
alpar@8: 
alpar@8:       ///Set the bottom of the box
alpar@8: 
alpar@8:       ///Set the bottom of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void bottom(T t) {
kpeter@241:         _bottom_left.y = t;
alpar@8:       }
alpar@8: 
alpar@8:       ///Give back the top of the box
alpar@8: 
alpar@8:       ///Give back the top of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T top() const {
kpeter@241:         return _top_right.y;
alpar@8:       }
alpar@8: 
alpar@8:       ///Set the top of the box
alpar@8: 
alpar@8:       ///Set the top of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void top(T t) {
kpeter@241:         _top_right.y = t;
alpar@8:       }
alpar@8: 
alpar@8:       ///Give back the left side of the box
alpar@8: 
alpar@8:       ///Give back the left side of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T left() const {
kpeter@241:         return _bottom_left.x;
alpar@8:       }
alpar@209: 
alpar@8:       ///Set the left side of the box
alpar@8: 
alpar@8:       ///Set the left side of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void left(T t) {
kpeter@241:         _bottom_left.x = t;
alpar@8:       }
alpar@8: 
alpar@8:       /// Give back the right side of the box
alpar@8: 
alpar@8:       /// Give back the right side of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T right() const {
kpeter@241:         return _top_right.x;
alpar@8:       }
alpar@8: 
alpar@8:       ///Set the right side of the box
alpar@8: 
alpar@8:       ///Set the right side of the box.
kpeter@241:       ///\pre The box must not be empty.
alpar@8:       void right(T t) {
kpeter@241:         _top_right.x = t;
alpar@8:       }
alpar@8: 
alpar@8:       ///Give back the height of the box
alpar@8: 
alpar@8:       ///Give back the height of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T height() const {
kpeter@241:         return _top_right.y-_bottom_left.y;
alpar@8:       }
alpar@8: 
alpar@8:       ///Give back the width of the box
alpar@8: 
alpar@8:       ///Give back the width of the box.
kpeter@253:       ///If the box is empty, then the return value is not defined.
alpar@8:       T width() const {
kpeter@241:         return _top_right.x-_bottom_left.x;
alpar@8:       }
alpar@8: 
kpeter@253:       ///Checks whether a point is inside the box
kpeter@15:       bool inside(const Point<T>& u) const {
alpar@8:         if (_empty)
alpar@8:           return false;
kpeter@241:         else {
kpeter@241:           return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
kpeter@241:                    (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
alpar@8:         }
alpar@8:       }
alpar@209: 
kpeter@253:       ///Increments the box with a point
kpeter@15: 
kpeter@253:       ///Increments the box with a point.
kpeter@15:       ///
kpeter@253:       Box& add(const Point<T>& u){
kpeter@241:         if (_empty) {
kpeter@241:           _bottom_left = _top_right = u;
alpar@8:           _empty = false;
alpar@8:         }
kpeter@241:         else {
kpeter@241:           if (_bottom_left.x > u.x) _bottom_left.x = u.x;
kpeter@241:           if (_bottom_left.y > u.y) _bottom_left.y = u.y;
kpeter@241:           if (_top_right.x < u.x) _top_right.x = u.x;
kpeter@241:           if (_top_right.y < u.y) _top_right.y = u.y;
alpar@8:         }
alpar@8:         return *this;
alpar@8:       }
alpar@209: 
kpeter@253:       ///Increments the box to contain another box
alpar@209: 
kpeter@253:       ///Increments the box to contain another box.
kpeter@15:       ///
kpeter@253:       Box& add(const Box &u){
alpar@8:         if ( !u.empty() ){
kpeter@241:           add(u._bottom_left);
kpeter@241:           add(u._top_right);
alpar@8:         }
alpar@8:         return *this;
alpar@8:       }
alpar@209: 
kpeter@253:       ///Intersection of two boxes
kpeter@15: 
kpeter@253:       ///Intersection of two boxes.
kpeter@15:       ///
kpeter@253:       Box operator&(const Box& u) const {
kpeter@253:         Box b;
kpeter@241:         if (_empty || u._empty) {
alpar@209:           b._empty = true;
alpar@209:         } else {
kpeter@241:           b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
kpeter@241:           b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
kpeter@241:           b._top_right.x = std::min(_top_right.x, u._top_right.x);
kpeter@241:           b._top_right.y = std::min(_top_right.y, u._top_right.y);
kpeter@241:           b._empty = b._bottom_left.x > b._top_right.x ||
kpeter@241:                      b._bottom_left.y > b._top_right.y;
alpar@209:         }
alpar@8:         return b;
alpar@8:       }
alpar@8: 
kpeter@253:   };//class Box
alpar@8: 
alpar@8: 
kpeter@253:   ///Read a box from a stream
kpeter@250: 
kpeter@253:   ///Read a box from a stream.
kpeter@253:   ///\relates Box
kpeter@250:   template<typename T>
kpeter@253:   inline std::istream& operator>>(std::istream &is, Box<T>& b) {
kpeter@250:     char c;
kpeter@250:     Point<T> p;
kpeter@250:     if (is >> c) {
kpeter@250:       if (c != '(') is.putback(c);
kpeter@250:     } else {
kpeter@250:       is.clear();
kpeter@250:     }
kpeter@250:     if (!(is >> p)) return is;
kpeter@250:     b.bottomLeft(p);
kpeter@250:     if (is >> c) {
kpeter@250:       if (c != ',') is.putback(c);
kpeter@250:     } else {
kpeter@250:       is.clear();
kpeter@250:     }
kpeter@250:     if (!(is >> p)) return is;
kpeter@250:     b.topRight(p);
kpeter@250:     if (is >> c) {
kpeter@250:       if (c != ')') is.putback(c);
kpeter@250:     } else {
kpeter@250:       is.clear();
kpeter@250:     }
kpeter@250:     return is;
kpeter@250:   }
kpeter@250: 
kpeter@253:   ///Write a box to a stream
kpeter@250: 
kpeter@253:   ///Write a box to a stream.
kpeter@253:   ///\relates Box
kpeter@250:   template<typename T>
kpeter@253:   inline std::ostream& operator<<(std::ostream &os, const Box<T>& b)
kpeter@250:   {
kpeter@250:     os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
kpeter@250:     return os;
kpeter@250:   }
kpeter@250: 
kpeter@313:   ///Map of x-coordinates of a <tt>Point</tt>-map
alpar@8: 
kpeter@313:   ///Map of x-coordinates of a \ref Point "Point"-map.
kpeter@314:   ///
alpar@8:   template<class M>
alpar@209:   class XMap
alpar@8:   {
alpar@8:     M& _map;
alpar@8:   public:
alpar@8: 
alpar@8:     typedef typename M::Value::Value Value;
alpar@8:     typedef typename M::Key Key;
alpar@8:     ///\e
alpar@8:     XMap(M& map) : _map(map) {}
alpar@8:     Value operator[](Key k) const {return _map[k].x;}
alpar@8:     void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
alpar@8:   };
alpar@209: 
kpeter@313:   ///Returns an XMap class
alpar@8: 
kpeter@313:   ///This function just returns an XMap class.
alpar@8:   ///\relates XMap
alpar@209:   template<class M>
alpar@209:   inline XMap<M> xMap(M &m)
alpar@8:   {
alpar@8:     return XMap<M>(m);
alpar@8:   }
alpar@8: 
alpar@209:   template<class M>
alpar@209:   inline XMap<M> xMap(const M &m)
alpar@8:   {
alpar@8:     return XMap<M>(m);
alpar@8:   }
alpar@8: 
kpeter@313:   ///Constant (read only) version of XMap
alpar@8: 
kpeter@313:   ///Constant (read only) version of XMap.
kpeter@314:   ///
alpar@8:   template<class M>
alpar@209:   class ConstXMap
alpar@8:   {
alpar@8:     const M& _map;
alpar@8:   public:
alpar@8: 
alpar@8:     typedef typename M::Value::Value Value;
alpar@8:     typedef typename M::Key Key;
alpar@8:     ///\e
alpar@8:     ConstXMap(const M &map) : _map(map) {}
alpar@8:     Value operator[](Key k) const {return _map[k].x;}
alpar@8:   };
alpar@209: 
kpeter@313:   ///Returns a ConstXMap class
alpar@8: 
kpeter@313:   ///This function just returns a ConstXMap class.
alpar@8:   ///\relates ConstXMap
alpar@209:   template<class M>
alpar@209:   inline ConstXMap<M> xMap(const M &m)
alpar@8:   {
alpar@8:     return ConstXMap<M>(m);
alpar@8:   }
alpar@8: 
kpeter@313:   ///Map of y-coordinates of a <tt>Point</tt>-map
alpar@209: 
kpeter@313:   ///Map of y-coordinates of a \ref Point "Point"-map.
kpeter@314:   ///
alpar@8:   template<class M>
alpar@209:   class YMap
alpar@8:   {
alpar@8:     M& _map;
alpar@8:   public:
alpar@8: 
alpar@8:     typedef typename M::Value::Value Value;
alpar@8:     typedef typename M::Key Key;
alpar@8:     ///\e
alpar@8:     YMap(M& map) : _map(map) {}
alpar@8:     Value operator[](Key k) const {return _map[k].y;}
alpar@8:     void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
alpar@8:   };
alpar@8: 
kpeter@313:   ///Returns a YMap class
alpar@8: 
kpeter@313:   ///This function just returns a YMap class.
alpar@8:   ///\relates YMap
alpar@209:   template<class M>
alpar@209:   inline YMap<M> yMap(M &m)
alpar@8:   {
alpar@8:     return YMap<M>(m);
alpar@8:   }
alpar@8: 
alpar@209:   template<class M>
alpar@209:   inline YMap<M> yMap(const M &m)
alpar@8:   {
alpar@8:     return YMap<M>(m);
alpar@8:   }
alpar@8: 
kpeter@313:   ///Constant (read only) version of YMap
alpar@8: 
kpeter@313:   ///Constant (read only) version of YMap.
kpeter@314:   ///
alpar@8:   template<class M>
alpar@209:   class ConstYMap
alpar@8:   {
alpar@8:     const M& _map;
alpar@8:   public:
alpar@8: 
alpar@8:     typedef typename M::Value::Value Value;
alpar@8:     typedef typename M::Key Key;
alpar@8:     ///\e
alpar@8:     ConstYMap(const M &map) : _map(map) {}
alpar@8:     Value operator[](Key k) const {return _map[k].y;}
alpar@8:   };
alpar@209: 
kpeter@313:   ///Returns a ConstYMap class
alpar@8: 
kpeter@313:   ///This function just returns a ConstYMap class.
alpar@8:   ///\relates ConstYMap
alpar@209:   template<class M>
alpar@209:   inline ConstYMap<M> yMap(const M &m)
alpar@8:   {
alpar@8:     return ConstYMap<M>(m);
alpar@8:   }
alpar@8: 
alpar@8: 
kpeter@313:   ///\brief Map of the normSquare() of a <tt>Point</tt>-map
kpeter@49:   ///
kpeter@49:   ///Map of the \ref Point::normSquare() "normSquare()"
kpeter@49:   ///of a \ref Point "Point"-map.
alpar@8:   template<class M>
alpar@209:   class NormSquareMap
alpar@8:   {
alpar@8:     const M& _map;
alpar@8:   public:
alpar@8: 
alpar@8:     typedef typename M::Value::Value Value;
alpar@8:     typedef typename M::Key Key;
alpar@8:     ///\e
alpar@8:     NormSquareMap(const M &map) : _map(map) {}
alpar@8:     Value operator[](Key k) const {return _map[k].normSquare();}
alpar@8:   };
alpar@209: 
kpeter@313:   ///Returns a NormSquareMap class
alpar@8: 
kpeter@313:   ///This function just returns a NormSquareMap class.
alpar@8:   ///\relates NormSquareMap
alpar@209:   template<class M>
alpar@209:   inline NormSquareMap<M> normSquareMap(const M &m)
alpar@8:   {
alpar@8:     return NormSquareMap<M>(m);
alpar@8:   }
alpar@8: 
alpar@8:   /// @}
alpar@8: 
alpar@8:   } //namespce dim2
alpar@209: 
alpar@8: } //namespace lemon
alpar@8: 
alpar@8: #endif //LEMON_DIM2_H