dim2.h is considered stable lemon-1.0
authoralpar
Fri, 15 Sep 2006 12:23:16 +0000
branchlemon-1.0
changeset 2658ecd07e5330b0
parent 2657 6e5e6208ed68
dim2.h is considered stable
lemon/Makefile.am
lemon/dim2.h
test/Makefile.am
test/dim_test.cc
     1.1 --- a/lemon/Makefile.am	Wed Aug 16 14:24:20 2006 +0000
     1.2 +++ b/lemon/Makefile.am	Fri Sep 15 12:23:16 2006 +0000
     1.3 @@ -40,6 +40,7 @@
     1.4  ##	lemon/dag_shortest_path.h \
     1.5  ##	lemon/dfs.h \
     1.6  ##	lemon/dijkstra.h \
     1.7 +	lemon/dim2.h \
     1.8  ##	lemon/dimacs.h \
     1.9  ##	lemon/edge_set.h \
    1.10  ##	lemon/edmonds_karp.h \
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/lemon/dim2.h	Fri Sep 15 12:23:16 2006 +0000
     2.3 @@ -0,0 +1,665 @@
     2.4 +/* -*- C++ -*-
     2.5 + *
     2.6 + * This file is a part of LEMON, a generic C++ optimization library
     2.7 + *
     2.8 + * Copyright (C) 2003-2006
     2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    2.11 + *
    2.12 + * Permission to use, modify and distribute this software is granted
    2.13 + * provided that this copyright notice appears in all copies. For
    2.14 + * precise terms see the accompanying LICENSE file.
    2.15 + *
    2.16 + * This software is provided "AS IS" with no warranty of any kind,
    2.17 + * express or implied, and with no claim as to its suitability for any
    2.18 + * purpose.
    2.19 + *
    2.20 + */
    2.21 +
    2.22 +#ifndef LEMON_DIM2_H
    2.23 +#define LEMON_DIM2_H
    2.24 +
    2.25 +#include <iostream>
    2.26 +#include <lemon/bits/utility.h>
    2.27 +
    2.28 +///\ingroup misc
    2.29 +///\file
    2.30 +///\brief A simple two dimensional vector and a bounding box implementation 
    2.31 +///
    2.32 +/// The class \ref lemon::dim2::Point "dim2::Point" implements
    2.33 +///a two dimensional vector with the usual
    2.34 +/// operations.
    2.35 +///
    2.36 +/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
    2.37 +/// can be used to determine
    2.38 +/// the rectangular bounding box of a set of
    2.39 +/// \ref lemon::dim2::Point "dim2::Point"'s.
    2.40 +///
    2.41 +///\author Attila Bernath
    2.42 +
    2.43 +
    2.44 +namespace lemon {
    2.45 +
    2.46 +  ///Tools for handling two dimensional coordinates
    2.47 +
    2.48 +  ///This namespace is a storage of several
    2.49 +  ///tools for handling two dimensional coordinates
    2.50 +  namespace dim2 {
    2.51 +
    2.52 +  /// \addtogroup misc
    2.53 +  /// @{
    2.54 +
    2.55 +  /// A simple two dimensional vector (plainvector) implementation
    2.56 +
    2.57 +  /// A simple two dimensional vector (plainvector) implementation
    2.58 +  ///with the usual vector
    2.59 +  /// operators.
    2.60 +  ///
    2.61 +  template<typename T>
    2.62 +    class Point {
    2.63 +
    2.64 +    public:
    2.65 +
    2.66 +      typedef T Value;
    2.67 +
    2.68 +      ///First co-ordinate
    2.69 +      T x;
    2.70 +      ///Second co-ordinate
    2.71 +      T y;     
    2.72 +      
    2.73 +      ///Default constructor
    2.74 +      Point() {}
    2.75 +
    2.76 +      ///Construct an instance from coordinates
    2.77 +      Point(T a, T b) : x(a), y(b) { }
    2.78 +
    2.79 +      ///The dimension of the vector.
    2.80 +
    2.81 +      ///This class give back always 2.
    2.82 +      ///
    2.83 +      int size() const { return 2; }
    2.84 +
    2.85 +      ///Subscripting operator
    2.86 +
    2.87 +      ///\c p[0] is \c p.x and \c p[1] is \c p.y
    2.88 +      ///
    2.89 +      T& operator[](int idx) { return idx == 0 ? x : y; }
    2.90 +
    2.91 +      ///Const subscripting operator
    2.92 +
    2.93 +      ///\c p[0] is \c p.x and \c p[1] is \c p.y
    2.94 +      ///
    2.95 +      const T& operator[](int idx) const { return idx == 0 ? x : y; }
    2.96 +
    2.97 +      ///Conversion constructor
    2.98 +      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
    2.99 +
   2.100 +      ///Give back the square of the norm of the vector
   2.101 +      T normSquare() const {
   2.102 +        return x*x+y*y;
   2.103 +      }
   2.104 +  
   2.105 +      ///Increment the left hand side by u
   2.106 +      Point<T>& operator +=(const Point<T>& u) {
   2.107 +        x += u.x;
   2.108 +        y += u.y;
   2.109 +        return *this;
   2.110 +      }
   2.111 +  
   2.112 +      ///Decrement the left hand side by u
   2.113 +      Point<T>& operator -=(const Point<T>& u) {
   2.114 +        x -= u.x;
   2.115 +        y -= u.y;
   2.116 +        return *this;
   2.117 +      }
   2.118 +
   2.119 +      ///Multiply the left hand side with a scalar
   2.120 +      Point<T>& operator *=(const T &u) {
   2.121 +        x *= u;
   2.122 +        y *= u;
   2.123 +        return *this;
   2.124 +      }
   2.125 +
   2.126 +      ///Divide the left hand side by a scalar
   2.127 +      Point<T>& operator /=(const T &u) {
   2.128 +        x /= u;
   2.129 +        y /= u;
   2.130 +        return *this;
   2.131 +      }
   2.132 +  
   2.133 +      ///Return the scalar product of two vectors
   2.134 +      T operator *(const Point<T>& u) const {
   2.135 +        return x*u.x+y*u.y;
   2.136 +      }
   2.137 +  
   2.138 +      ///Return the sum of two vectors
   2.139 +      Point<T> operator+(const Point<T> &u) const {
   2.140 +        Point<T> b=*this;
   2.141 +        return b+=u;
   2.142 +      }
   2.143 +
   2.144 +      ///Return the neg of the vectors
   2.145 +      Point<T> operator-() const {
   2.146 +        Point<T> b=*this;
   2.147 +        b.x=-b.x; b.y=-b.y;
   2.148 +        return b;
   2.149 +      }
   2.150 +
   2.151 +      ///Return the difference of two vectors
   2.152 +      Point<T> operator-(const Point<T> &u) const {
   2.153 +        Point<T> b=*this;
   2.154 +        return b-=u;
   2.155 +      }
   2.156 +
   2.157 +      ///Return a vector multiplied by a scalar
   2.158 +      Point<T> operator*(const T &u) const {
   2.159 +        Point<T> b=*this;
   2.160 +        return b*=u;
   2.161 +      }
   2.162 +
   2.163 +      ///Return a vector divided by a scalar
   2.164 +      Point<T> operator/(const T &u) const {
   2.165 +        Point<T> b=*this;
   2.166 +        return b/=u;
   2.167 +      }
   2.168 +
   2.169 +      ///Test equality
   2.170 +      bool operator==(const Point<T> &u) const {
   2.171 +        return (x==u.x) && (y==u.y);
   2.172 +      }
   2.173 +
   2.174 +      ///Test inequality
   2.175 +      bool operator!=(Point u) const {
   2.176 +        return  (x!=u.x) || (y!=u.y);
   2.177 +      }
   2.178 +
   2.179 +    };
   2.180 +
   2.181 +  ///Return an Point 
   2.182 +
   2.183 +  ///Return an Point
   2.184 +  ///\relates Point
   2.185 +  template <typename T>
   2.186 +  inline Point<T> makePoint(const T& x, const T& y) {
   2.187 +    return Point<T>(x, y);
   2.188 +  }
   2.189 +
   2.190 +  ///Return a vector multiplied by a scalar
   2.191 +
   2.192 +  ///Return a vector multiplied by a scalar
   2.193 +  ///\relates Point
   2.194 +  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
   2.195 +    return x*u;
   2.196 +  }
   2.197 +
   2.198 +  ///Read a plainvector from a stream
   2.199 +
   2.200 +  ///Read a plainvector from a stream
   2.201 +  ///\relates Point
   2.202 +  ///
   2.203 +  template<typename T>
   2.204 +  inline std::istream& operator>>(std::istream &is, Point<T> &z) {
   2.205 +    char c;
   2.206 +    if (is >> c) {
   2.207 +      if (c != '(') is.putback(c);
   2.208 +    } else {
   2.209 +      is.clear();
   2.210 +    }
   2.211 +    if (!(is >> z.x)) return is;
   2.212 +    if (is >> c) {
   2.213 +      if (c != ',') is.putback(c);
   2.214 +    } else {
   2.215 +      is.clear();
   2.216 +    }
   2.217 +    if (!(is >> z.y)) return is;
   2.218 +    if (is >> c) {
   2.219 +      if (c != ')') is.putback(c);
   2.220 +    } else {
   2.221 +      is.clear();
   2.222 +    }
   2.223 +    return is;
   2.224 +  }
   2.225 +
   2.226 +  ///Write a plainvector to a stream
   2.227 +
   2.228 +  ///Write a plainvector to a stream
   2.229 +  ///\relates Point
   2.230 +  ///
   2.231 +  template<typename T>
   2.232 +  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
   2.233 +  {
   2.234 +    os << "(" << z.x << ", " << z.y << ")";
   2.235 +    return os;
   2.236 +  }
   2.237 +
   2.238 +  ///Rotate by 90 degrees
   2.239 +
   2.240 +  ///Returns its parameter rotated by 90 degrees in positive direction.
   2.241 +  ///\relates Point
   2.242 +  ///
   2.243 +  template<typename T>
   2.244 +  inline Point<T> rot90(const Point<T> &z)
   2.245 +  {
   2.246 +    return Point<T>(-z.y,z.x);
   2.247 +  }
   2.248 +
   2.249 +  ///Rotate by 180 degrees
   2.250 +
   2.251 +  ///Returns its parameter rotated by 180 degrees.
   2.252 +  ///\relates Point
   2.253 +  ///
   2.254 +  template<typename T>
   2.255 +  inline Point<T> rot180(const Point<T> &z)
   2.256 +  {
   2.257 +    return Point<T>(-z.x,-z.y);
   2.258 +  }
   2.259 +
   2.260 +  ///Rotate by 270 degrees
   2.261 +
   2.262 +  ///Returns its parameter rotated by 90 degrees in negative direction.
   2.263 +  ///\relates Point
   2.264 +  ///
   2.265 +  template<typename T>
   2.266 +  inline Point<T> rot270(const Point<T> &z)
   2.267 +  {
   2.268 +    return Point<T>(z.y,-z.x);
   2.269 +  }
   2.270 +
   2.271 +  
   2.272 +
   2.273 +  /// A class to calculate or store the bounding box of plainvectors.
   2.274 +
   2.275 +  /// A class to calculate or store the bounding box of plainvectors.
   2.276 +  ///
   2.277 +  ///\author Attila Bernath
   2.278 +  template<typename T>
   2.279 +    class BoundingBox {
   2.280 +      Point<T> bottom_left, top_right;
   2.281 +      bool _empty;
   2.282 +    public:
   2.283 +      
   2.284 +      ///Default constructor: creates an empty bounding box
   2.285 +      BoundingBox() { _empty = true; }
   2.286 +
   2.287 +      ///Construct an instance from one point
   2.288 +      BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
   2.289 +
   2.290 +      ///Were any points added?
   2.291 +      bool empty() const {
   2.292 +        return _empty;
   2.293 +      }
   2.294 +
   2.295 +      ///Make the BoundingBox empty
   2.296 +      void clear() {
   2.297 +        _empty=1;
   2.298 +      }
   2.299 +
   2.300 +      ///Give back the bottom left corner
   2.301 +
   2.302 +      ///Give back the bottom left corner.
   2.303 +      ///If the bounding box is empty, then the return value is not defined.
   2.304 +      Point<T> bottomLeft() const {
   2.305 +        return bottom_left;
   2.306 +      }
   2.307 +
   2.308 +      ///Set the bottom left corner
   2.309 +
   2.310 +      ///Set the bottom left corner.
   2.311 +      ///It should only bee used for non-empty box.
   2.312 +      void bottomLeft(Point<T> p) {
   2.313 +	bottom_left = p;
   2.314 +      }
   2.315 +
   2.316 +      ///Give back the top right corner
   2.317 +
   2.318 +      ///Give back the top right corner.
   2.319 +      ///If the bounding box is empty, then the return value is not defined.
   2.320 +      Point<T> topRight() const {
   2.321 +        return top_right;
   2.322 +      }
   2.323 +
   2.324 +      ///Set the top right corner
   2.325 +
   2.326 +      ///Set the top right corner.
   2.327 +      ///It should only bee used for non-empty box.
   2.328 +      void topRight(Point<T> p) {
   2.329 +	top_right = p;
   2.330 +      }
   2.331 +
   2.332 +      ///Give back the bottom right corner
   2.333 +
   2.334 +      ///Give back the bottom right corner.
   2.335 +      ///If the bounding box is empty, then the return value is not defined.
   2.336 +      Point<T> bottomRight() const {
   2.337 +        return Point<T>(top_right.x,bottom_left.y);
   2.338 +      }
   2.339 +
   2.340 +      ///Set the bottom right corner
   2.341 +
   2.342 +      ///Set the bottom right corner.
   2.343 +      ///It should only bee used for non-empty box.
   2.344 +      void bottomRight(Point<T> p) {
   2.345 +	top_right.x = p.x;
   2.346 +	bottom_left.y = p.y;
   2.347 +      }
   2.348 + 
   2.349 +      ///Give back the top left corner
   2.350 +
   2.351 +      ///Give back the top left corner.
   2.352 +      ///If the bounding box is empty, then the return value is not defined.
   2.353 +      Point<T> topLeft() const {
   2.354 +        return Point<T>(bottom_left.x,top_right.y);
   2.355 +      }
   2.356 +
   2.357 +      ///Set the top left corner
   2.358 +
   2.359 +      ///Set the top left corner.
   2.360 +      ///It should only bee used for non-empty box.
   2.361 +      void topLeft(Point<T> p) {
   2.362 +	top_right.y = p.y;
   2.363 +	bottom_left.x = p.x;
   2.364 +      }
   2.365 +
   2.366 +      ///Give back the bottom of the box
   2.367 +
   2.368 +      ///Give back the bottom of the box.
   2.369 +      ///If the bounding box is empty, then the return value is not defined.
   2.370 +      T bottom() const {
   2.371 +        return bottom_left.y;
   2.372 +      }
   2.373 +
   2.374 +      ///Set the bottom of the box
   2.375 +
   2.376 +      ///Set the bottom of the box.
   2.377 +      ///It should only bee used for non-empty box.
   2.378 +      void bottom(T t) {
   2.379 +	bottom_left.y = t;
   2.380 +      }
   2.381 +
   2.382 +      ///Give back the top of the box
   2.383 +
   2.384 +      ///Give back the top of the box.
   2.385 +      ///If the bounding box is empty, then the return value is not defined.
   2.386 +      T top() const {
   2.387 +        return top_right.y;
   2.388 +      }
   2.389 +
   2.390 +      ///Set the top of the box
   2.391 +
   2.392 +      ///Set the top of the box.
   2.393 +      ///It should only bee used for non-empty box.
   2.394 +      void top(T t) {
   2.395 +	top_right.y = t;
   2.396 +      }
   2.397 +
   2.398 +      ///Give back the left side of the box
   2.399 +
   2.400 +      ///Give back the left side of the box.
   2.401 +      ///If the bounding box is empty, then the return value is not defined.
   2.402 +      T left() const {
   2.403 +        return bottom_left.x;
   2.404 +      }
   2.405 + 
   2.406 +      ///Set the left side of the box
   2.407 +
   2.408 +      ///Set the left side of the box.
   2.409 +      ///It should only bee used for non-empty box
   2.410 +      void left(T t) {
   2.411 +	bottom_left.x = t;
   2.412 +      }
   2.413 +
   2.414 +      /// Give back the right side of the box
   2.415 +
   2.416 +      /// Give back the right side of the box.
   2.417 +      ///If the bounding box is empty, then the return value is not defined.
   2.418 +      T right() const {
   2.419 +        return top_right.x;
   2.420 +      }
   2.421 +
   2.422 +      ///Set the right side of the box
   2.423 +
   2.424 +      ///Set the right side of the box.
   2.425 +      ///It should only bee used for non-empty box
   2.426 +      void right(T t) {
   2.427 +	top_right.x = t;
   2.428 +      }
   2.429 +
   2.430 +      ///Give back the height of the box
   2.431 +
   2.432 +      ///Give back the height of the box.
   2.433 +      ///If the bounding box is empty, then the return value is not defined.
   2.434 +      T height() const {
   2.435 +        return top_right.y-bottom_left.y;
   2.436 +      }
   2.437 +
   2.438 +      ///Give back the width of the box
   2.439 +
   2.440 +      ///Give back the width of the box.
   2.441 +      ///If the bounding box is empty, then the return value is not defined.
   2.442 +      T width() const {
   2.443 +        return top_right.x-bottom_left.x;
   2.444 +      }
   2.445 +
   2.446 +      ///Checks whether a point is inside a bounding box
   2.447 +      bool inside(const Point<T>& u){
   2.448 +        if (_empty)
   2.449 +          return false;
   2.450 +        else{
   2.451 +          return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
   2.452 +              (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
   2.453 +        }
   2.454 +      }
   2.455 +  
   2.456 +      ///Increments a bounding box with a point
   2.457 +      BoundingBox& add(const Point<T>& u){
   2.458 +        if (_empty){
   2.459 +          bottom_left=top_right=u;
   2.460 +          _empty = false;
   2.461 +        }
   2.462 +        else{
   2.463 +          if (bottom_left.x > u.x) bottom_left.x = u.x;
   2.464 +          if (bottom_left.y > u.y) bottom_left.y = u.y;
   2.465 +          if (top_right.x < u.x) top_right.x = u.x;
   2.466 +          if (top_right.y < u.y) top_right.y = u.y;
   2.467 +        }
   2.468 +        return *this;
   2.469 +      }
   2.470 +    
   2.471 +      ///Increments a bounding to contain another bounding box
   2.472 +      BoundingBox& add(const BoundingBox &u){
   2.473 +        if ( !u.empty() ){
   2.474 +          this->add(u.bottomLeft());
   2.475 +	  this->add(u.topRight());
   2.476 +        }
   2.477 +        return *this;
   2.478 +      }
   2.479 +  
   2.480 +      ///Intersection of two bounding boxes
   2.481 +      BoundingBox operator &(const BoundingBox& u){
   2.482 +        BoundingBox b;
   2.483 +	b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
   2.484 +	b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
   2.485 +	b.top_right.x=std::min(this->top_right.x,u.top_right.x);
   2.486 +	b.top_right.y=std::min(this->top_right.y,u.top_right.y);
   2.487 +	b._empty = this->_empty || u._empty ||
   2.488 +	  b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
   2.489 +        return b;
   2.490 +      }
   2.491 +
   2.492 +    };//class Boundingbox
   2.493 +
   2.494 +
   2.495 +  ///Map of x-coordinates of a dim2::Point<>-map
   2.496 +
   2.497 +  ///\ingroup maps
   2.498 +  ///Map of x-coordinates of a dim2::Point<>-map
   2.499 +  ///
   2.500 +  template<class M>
   2.501 +  class XMap 
   2.502 +  {
   2.503 +    M& _map;
   2.504 +  public:
   2.505 +
   2.506 +    typedef typename M::Value::Value Value;
   2.507 +    typedef typename M::Key Key;
   2.508 +    ///\e
   2.509 +    XMap(M& map) : _map(map) {}
   2.510 +    Value operator[](Key k) const {return _map[k].x;}
   2.511 +    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
   2.512 +  };
   2.513 +    
   2.514 +  ///Returns an \ref XMap class
   2.515 +
   2.516 +  ///This function just returns an \ref XMap class.
   2.517 +  ///
   2.518 +  ///\ingroup maps
   2.519 +  ///\relates XMap
   2.520 +  template<class M> 
   2.521 +  inline XMap<M> xMap(M &m) 
   2.522 +  {
   2.523 +    return XMap<M>(m);
   2.524 +  }
   2.525 +
   2.526 +  template<class M> 
   2.527 +  inline XMap<M> xMap(const M &m) 
   2.528 +  {
   2.529 +    return XMap<M>(m);
   2.530 +  }
   2.531 +
   2.532 +  ///Constant (read only) version of \ref XMap
   2.533 +
   2.534 +  ///\ingroup maps
   2.535 +  ///Constant (read only) version of \ref XMap
   2.536 +  ///
   2.537 +  template<class M>
   2.538 +  class ConstXMap 
   2.539 +  {
   2.540 +    const M& _map;
   2.541 +  public:
   2.542 +
   2.543 +    typedef typename M::Value::Value Value;
   2.544 +    typedef typename M::Key Key;
   2.545 +    ///\e
   2.546 +    ConstXMap(const M &map) : _map(map) {}
   2.547 +    Value operator[](Key k) const {return _map[k].x;}
   2.548 +  };
   2.549 +    
   2.550 +  ///Returns a \ref ConstXMap class
   2.551 +
   2.552 +  ///This function just returns an \ref ConstXMap class.
   2.553 +  ///
   2.554 +  ///\ingroup maps
   2.555 +  ///\relates ConstXMap
   2.556 +  template<class M> 
   2.557 +  inline ConstXMap<M> xMap(const M &m) 
   2.558 +  {
   2.559 +    return ConstXMap<M>(m);
   2.560 +  }
   2.561 +
   2.562 +  ///Map of y-coordinates of a dim2::Point<>-map
   2.563 +    
   2.564 +  ///\ingroup maps
   2.565 +  ///Map of y-coordinates of a dim2::Point<>-map
   2.566 +  ///
   2.567 +  template<class M>
   2.568 +  class YMap 
   2.569 +  {
   2.570 +    M& _map;
   2.571 +  public:
   2.572 +
   2.573 +    typedef typename M::Value::Value Value;
   2.574 +    typedef typename M::Key Key;
   2.575 +    ///\e
   2.576 +    YMap(M& map) : _map(map) {}
   2.577 +    Value operator[](Key k) const {return _map[k].y;}
   2.578 +    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
   2.579 +  };
   2.580 +
   2.581 +  ///Returns an \ref YMap class
   2.582 +
   2.583 +  ///This function just returns an \ref YMap class.
   2.584 +  ///
   2.585 +  ///\ingroup maps
   2.586 +  ///\relates YMap
   2.587 +  template<class M> 
   2.588 +  inline YMap<M> yMap(M &m) 
   2.589 +  {
   2.590 +    return YMap<M>(m);
   2.591 +  }
   2.592 +
   2.593 +  template<class M> 
   2.594 +  inline YMap<M> yMap(const M &m) 
   2.595 +  {
   2.596 +    return YMap<M>(m);
   2.597 +  }
   2.598 +
   2.599 +  ///Constant (read only) version of \ref YMap
   2.600 +
   2.601 +  ///\ingroup maps
   2.602 +  ///Constant (read only) version of \ref YMap
   2.603 +  ///
   2.604 +  template<class M>
   2.605 +  class ConstYMap 
   2.606 +  {
   2.607 +    const M& _map;
   2.608 +  public:
   2.609 +
   2.610 +    typedef typename M::Value::Value Value;
   2.611 +    typedef typename M::Key Key;
   2.612 +    ///\e
   2.613 +    ConstYMap(const M &map) : _map(map) {}
   2.614 +    Value operator[](Key k) const {return _map[k].y;}
   2.615 +  };
   2.616 +    
   2.617 +  ///Returns a \ref ConstYMap class
   2.618 +
   2.619 +  ///This function just returns an \ref ConstYMap class.
   2.620 +  ///
   2.621 +  ///\ingroup maps
   2.622 +  ///\relates ConstYMap
   2.623 +  template<class M> 
   2.624 +  inline ConstYMap<M> yMap(const M &m) 
   2.625 +  {
   2.626 +    return ConstYMap<M>(m);
   2.627 +  }
   2.628 +
   2.629 +
   2.630 +    ///\brief Map of the \ref Point::normSquare() "normSquare()"
   2.631 +    ///of an \ref Point "Point"-map
   2.632 +    ///
   2.633 +    ///Map of the \ref Point::normSquare() "normSquare()"
   2.634 +    ///of an \ref Point "Point"-map
   2.635 +    ///\ingroup maps
   2.636 +    ///
   2.637 +  template<class M>
   2.638 +  class NormSquareMap 
   2.639 +  {
   2.640 +    const M& _map;
   2.641 +  public:
   2.642 +
   2.643 +    typedef typename M::Value::Value Value;
   2.644 +    typedef typename M::Key Key;
   2.645 +    ///\e
   2.646 +    NormSquareMap(const M &map) : _map(map) {}
   2.647 +    Value operator[](Key k) const {return _map[k].normSquare();}
   2.648 +  };
   2.649 +    
   2.650 +  ///Returns a \ref NormSquareMap class
   2.651 +
   2.652 +  ///This function just returns an \ref NormSquareMap class.
   2.653 +  ///
   2.654 +  ///\ingroup maps
   2.655 +  ///\relates NormSquareMap
   2.656 +  template<class M> 
   2.657 +  inline NormSquareMap<M> normSquareMap(const M &m) 
   2.658 +  {
   2.659 +    return NormSquareMap<M>(m);
   2.660 +  }
   2.661 +
   2.662 +  /// @}
   2.663 +
   2.664 +  } //namespce dim2
   2.665 +  
   2.666 +} //namespace lemon
   2.667 +
   2.668 +#endif //LEMON_DIM2_H
     3.1 --- a/test/Makefile.am	Wed Aug 16 14:24:20 2006 +0000
     3.2 +++ b/test/Makefile.am	Fri Sep 15 12:23:16 2006 +0000
     3.3 @@ -18,6 +18,7 @@
     3.4  ##	test/counter_test \
     3.5  ##	test/dfs_test \
     3.6  ##	test/dijkstra_test \
     3.7 +	test/dim_test
     3.8  ##	test/edge_set_test \
     3.9  ##	test/graph_adaptor_test \
    3.10  ##	test/graph_test \
    3.11 @@ -39,8 +40,7 @@
    3.12  ##	test/test_tools_pass \
    3.13  ##	test/time_measure_test \
    3.14  ##	test/ugraph_test \
    3.15 -##	test/unionfind_test \
    3.16 -##	test/xy_test
    3.17 +##	test/unionfind_test
    3.18  
    3.19  if HAVE_GLPK
    3.20  ##check_PROGRAMS += test/lp_test
    3.21 @@ -60,6 +60,7 @@
    3.22  ##test_counter_test_SOURCES = test/counter_test.cc
    3.23  ##test_dfs_test_SOURCES = test/dfs_test.cc
    3.24  ##test_dijkstra_test_SOURCES = test/dijkstra_test.cc
    3.25 +test_dim_test_SOURCES = test/dim_test.cc
    3.26  ##test_edge_set_test_SOURCES = test/edge_set_test.cc
    3.27  ##test_graph_adaptor_test_SOURCES = test/graph_adaptor_test.cc
    3.28  ##test_graph_test_SOURCES = test/graph_test.cc
    3.29 @@ -82,7 +83,6 @@
    3.30  ##test_time_measure_test_SOURCES = test/time_measure_test.cc
    3.31  ##test_ugraph_test_SOURCES = test/ugraph_test.cc
    3.32  ##test_unionfind_test_SOURCES = test/unionfind_test.cc
    3.33 -##test_xy_test_SOURCES = test/xy_test.cc
    3.34  
    3.35  ##test_lp_test_SOURCES = test/lp_test.cc
    3.36  ##test_lp_test_CXXFLAGS = $(GLPK_CFLAGS) $(CPLEX_CFLAGS)
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/test/dim_test.cc	Fri Sep 15 12:23:16 2006 +0000
     4.3 @@ -0,0 +1,86 @@
     4.4 +/* -*- C++ -*-
     4.5 + *
     4.6 + * This file is a part of LEMON, a generic C++ optimization library
     4.7 + *
     4.8 + * Copyright (C) 2003-2006
     4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    4.11 + *
    4.12 + * Permission to use, modify and distribute this software is granted
    4.13 + * provided that this copyright notice appears in all copies. For
    4.14 + * precise terms see the accompanying LICENSE file.
    4.15 + *
    4.16 + * This software is provided "AS IS" with no warranty of any kind,
    4.17 + * express or implied, and with no claim as to its suitability for any
    4.18 + * purpose.
    4.19 + *
    4.20 + */
    4.21 +
    4.22 +#include <lemon/dim2.h>
    4.23 +#include <iostream>
    4.24 +#include "test_tools.h"
    4.25 +
    4.26 +using namespace std;
    4.27 +using namespace lemon;
    4.28 +int main()
    4.29 +{
    4.30 +
    4.31 +  cout << "Testing classes `dim2::Point' and `dim2::BoundingBox'." << endl;
    4.32 +
    4.33 +  typedef dim2::Point<int> Point;
    4.34 +	
    4.35 +  Point seged;
    4.36 +  check(seged.size()==2, "Wrong vector addition");
    4.37 +
    4.38 +  Point a(1,2);
    4.39 +  Point b(3,4);
    4.40 +
    4.41 +  check(a[0]==1 && a[1]==2, "Wrong vector addition");
    4.42 +
    4.43 +  seged = a+b;
    4.44 +  check(seged.x==4 && seged.y==6, "Wrong vector addition");
    4.45 +
    4.46 +  seged = a-b;
    4.47 +  check(seged.x==-2 && seged.y==-2, "a-b");
    4.48 +
    4.49 +  check(a.normSquare()==5,"Wrong norm calculation");
    4.50 +  check(a*b==11, "a*b");
    4.51 +
    4.52 +  int l=2;
    4.53 +  seged = a*l;
    4.54 +  check(seged.x==2 && seged.y==4, "a*l");
    4.55 +
    4.56 +  seged = b/l;
    4.57 +  check(seged.x==1 && seged.y==2, "b/l");
    4.58 +
    4.59 +  typedef dim2::BoundingBox<int> BB;
    4.60 +  BB doboz1;
    4.61 +  check(doboz1.empty(), "It should be empty.");
    4.62 +	
    4.63 +  doboz1.add(a);
    4.64 +  check(!doboz1.empty(), "It should not be empty.");
    4.65 +  doboz1.add(b);
    4.66 +
    4.67 +  check(doboz1.bottomLeft().x==1 && 
    4.68 +        doboz1.bottomLeft().y==2 &&
    4.69 +        doboz1.topRight().x==3 && 
    4.70 +        doboz1.topRight().y==4,  
    4.71 +        "added points to box");
    4.72 +
    4.73 +  seged.x=2;seged.y=3;
    4.74 +  check(doboz1.inside(seged),"It should be inside.");
    4.75 +
    4.76 +  seged.x=1;seged.y=3;
    4.77 +  check(doboz1.inside(seged),"It should be inside.");
    4.78 +
    4.79 +  seged.x=0;seged.y=3;
    4.80 +  check(!doboz1.inside(seged),"It should not be inside.");
    4.81 +
    4.82 +  BB doboz2(seged);
    4.83 +  check(!doboz2.empty(),
    4.84 +        "It should not be empty. Constructed from 1 point.");
    4.85 +
    4.86 +  doboz2.add(doboz1);
    4.87 +  check(doboz2.inside(seged),
    4.88 +        "It should be inside. Incremented a box with another one.");
    4.89 +}