lemon/dim2.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 01 Sep 2008 22:00:40 +0200
changeset 257 8d76a7bf9961
parent 220 a5d8c039f218
child 250 d0aae16df1bb
permissions -rw-r--r--
Rename Def* to Set* in Bfs, Dfs, Dijkstra (ticket #134)
- DefXyzMap --> SetXyzMap
- DefHeap --> SetHeap
- DefStandardHeap --> SetStandardHeap
- DefOperationTraits --> SetOperationTraits
- DefProcessedMapToBeDefaultMap --> SetStandardProcessedMap
- Bug fix: SetStandardProcessedMap shouldn't be template
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@8
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@8
     4
 *
alpar@39
     5
 * Copyright (C) 2003-2008
alpar@8
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@8
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@8
     8
 *
alpar@8
     9
 * Permission to use, modify and distribute this software is granted
alpar@8
    10
 * provided that this copyright notice appears in all copies. For
alpar@8
    11
 * precise terms see the accompanying LICENSE file.
alpar@8
    12
 *
alpar@8
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@8
    14
 * express or implied, and with no claim as to its suitability for any
alpar@8
    15
 * purpose.
alpar@8
    16
 *
alpar@8
    17
 */
alpar@8
    18
alpar@8
    19
#ifndef LEMON_DIM2_H
alpar@8
    20
#define LEMON_DIM2_H
alpar@8
    21
alpar@8
    22
#include <iostream>
alpar@8
    23
alpar@8
    24
///\ingroup misc
alpar@8
    25
///\file
alpar@209
    26
///\brief A simple two dimensional vector and a bounding box implementation
alpar@8
    27
///
alpar@8
    28
/// The class \ref lemon::dim2::Point "dim2::Point" implements
kpeter@49
    29
/// a two dimensional vector with the usual operations.
alpar@8
    30
///
alpar@8
    31
/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
alpar@8
    32
/// can be used to determine
alpar@8
    33
/// the rectangular bounding box of a set of
alpar@8
    34
/// \ref lemon::dim2::Point "dim2::Point"'s.
alpar@8
    35
alpar@8
    36
namespace lemon {
alpar@8
    37
alpar@8
    38
  ///Tools for handling two dimensional coordinates
alpar@8
    39
alpar@8
    40
  ///This namespace is a storage of several
alpar@8
    41
  ///tools for handling two dimensional coordinates
alpar@8
    42
  namespace dim2 {
alpar@8
    43
alpar@8
    44
  /// \addtogroup misc
alpar@8
    45
  /// @{
alpar@8
    46
kpeter@241
    47
  /// A simple two dimensional vector (plain vector) implementation
alpar@8
    48
kpeter@241
    49
  /// A simple two dimensional vector (plain vector) implementation
kpeter@49
    50
  /// with the usual vector operations.
alpar@8
    51
  template<typename T>
alpar@8
    52
    class Point {
alpar@8
    53
alpar@8
    54
    public:
alpar@8
    55
alpar@8
    56
      typedef T Value;
alpar@8
    57
kpeter@15
    58
      ///First coordinate
alpar@8
    59
      T x;
kpeter@15
    60
      ///Second coordinate
alpar@209
    61
      T y;
alpar@209
    62
alpar@8
    63
      ///Default constructor
alpar@8
    64
      Point() {}
alpar@8
    65
alpar@8
    66
      ///Construct an instance from coordinates
alpar@8
    67
      Point(T a, T b) : x(a), y(b) { }
alpar@8
    68
kpeter@49
    69
      ///Returns the dimension of the vector (i.e. returns 2).
alpar@8
    70
kpeter@15
    71
      ///The dimension of the vector.
alpar@209
    72
      ///This function always returns 2.
alpar@8
    73
      int size() const { return 2; }
alpar@8
    74
alpar@8
    75
      ///Subscripting operator
alpar@8
    76
alpar@8
    77
      ///\c p[0] is \c p.x and \c p[1] is \c p.y
alpar@8
    78
      ///
alpar@8
    79
      T& operator[](int idx) { return idx == 0 ? x : y; }
alpar@8
    80
alpar@8
    81
      ///Const subscripting operator
alpar@8
    82
alpar@8
    83
      ///\c p[0] is \c p.x and \c p[1] is \c p.y
alpar@8
    84
      ///
alpar@8
    85
      const T& operator[](int idx) const { return idx == 0 ? x : y; }
alpar@8
    86
alpar@8
    87
      ///Conversion constructor
alpar@8
    88
      template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
alpar@8
    89
alpar@8
    90
      ///Give back the square of the norm of the vector
alpar@8
    91
      T normSquare() const {
alpar@8
    92
        return x*x+y*y;
alpar@8
    93
      }
alpar@209
    94
kpeter@49
    95
      ///Increment the left hand side by \c u
alpar@8
    96
      Point<T>& operator +=(const Point<T>& u) {
alpar@8
    97
        x += u.x;
alpar@8
    98
        y += u.y;
alpar@8
    99
        return *this;
alpar@8
   100
      }
alpar@209
   101
kpeter@49
   102
      ///Decrement the left hand side by \c u
alpar@8
   103
      Point<T>& operator -=(const Point<T>& u) {
alpar@8
   104
        x -= u.x;
alpar@8
   105
        y -= u.y;
alpar@8
   106
        return *this;
alpar@8
   107
      }
alpar@8
   108
alpar@8
   109
      ///Multiply the left hand side with a scalar
alpar@8
   110
      Point<T>& operator *=(const T &u) {
alpar@8
   111
        x *= u;
alpar@8
   112
        y *= u;
alpar@8
   113
        return *this;
alpar@8
   114
      }
alpar@8
   115
alpar@8
   116
      ///Divide the left hand side by a scalar
alpar@8
   117
      Point<T>& operator /=(const T &u) {
alpar@8
   118
        x /= u;
alpar@8
   119
        y /= u;
alpar@8
   120
        return *this;
alpar@8
   121
      }
alpar@209
   122
alpar@8
   123
      ///Return the scalar product of two vectors
alpar@8
   124
      T operator *(const Point<T>& u) const {
alpar@8
   125
        return x*u.x+y*u.y;
alpar@8
   126
      }
alpar@209
   127
alpar@8
   128
      ///Return the sum of two vectors
alpar@8
   129
      Point<T> operator+(const Point<T> &u) const {
alpar@8
   130
        Point<T> b=*this;
alpar@8
   131
        return b+=u;
alpar@8
   132
      }
alpar@8
   133
kpeter@15
   134
      ///Return the negative of the vector
alpar@8
   135
      Point<T> operator-() const {
alpar@8
   136
        Point<T> b=*this;
alpar@8
   137
        b.x=-b.x; b.y=-b.y;
alpar@8
   138
        return b;
alpar@8
   139
      }
alpar@8
   140
alpar@8
   141
      ///Return the difference of two vectors
alpar@8
   142
      Point<T> operator-(const Point<T> &u) const {
alpar@8
   143
        Point<T> b=*this;
alpar@8
   144
        return b-=u;
alpar@8
   145
      }
alpar@8
   146
alpar@8
   147
      ///Return a vector multiplied by a scalar
alpar@8
   148
      Point<T> operator*(const T &u) const {
alpar@8
   149
        Point<T> b=*this;
alpar@8
   150
        return b*=u;
alpar@8
   151
      }
alpar@8
   152
alpar@8
   153
      ///Return a vector divided by a scalar
alpar@8
   154
      Point<T> operator/(const T &u) const {
alpar@8
   155
        Point<T> b=*this;
alpar@8
   156
        return b/=u;
alpar@8
   157
      }
alpar@8
   158
alpar@8
   159
      ///Test equality
alpar@8
   160
      bool operator==(const Point<T> &u) const {
alpar@8
   161
        return (x==u.x) && (y==u.y);
alpar@8
   162
      }
alpar@8
   163
alpar@8
   164
      ///Test inequality
alpar@8
   165
      bool operator!=(Point u) const {
alpar@8
   166
        return  (x!=u.x) || (y!=u.y);
alpar@8
   167
      }
alpar@8
   168
alpar@8
   169
    };
alpar@8
   170
alpar@209
   171
  ///Return a Point
alpar@8
   172
kpeter@15
   173
  ///Return a Point.
alpar@8
   174
  ///\relates Point
alpar@8
   175
  template <typename T>
alpar@8
   176
  inline Point<T> makePoint(const T& x, const T& y) {
alpar@8
   177
    return Point<T>(x, y);
alpar@8
   178
  }
alpar@8
   179
alpar@8
   180
  ///Return a vector multiplied by a scalar
alpar@8
   181
kpeter@15
   182
  ///Return a vector multiplied by a scalar.
alpar@8
   183
  ///\relates Point
alpar@8
   184
  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
alpar@8
   185
    return x*u;
alpar@8
   186
  }
alpar@8
   187
kpeter@241
   188
  ///Read a plain vector from a stream
alpar@8
   189
kpeter@241
   190
  ///Read a plain vector from a stream.
alpar@8
   191
  ///\relates Point
alpar@8
   192
  ///
alpar@8
   193
  template<typename T>
alpar@8
   194
  inline std::istream& operator>>(std::istream &is, Point<T> &z) {
alpar@8
   195
    char c;
alpar@8
   196
    if (is >> c) {
alpar@8
   197
      if (c != '(') is.putback(c);
alpar@8
   198
    } else {
alpar@8
   199
      is.clear();
alpar@8
   200
    }
alpar@8
   201
    if (!(is >> z.x)) return is;
alpar@8
   202
    if (is >> c) {
alpar@8
   203
      if (c != ',') is.putback(c);
alpar@8
   204
    } else {
alpar@8
   205
      is.clear();
alpar@8
   206
    }
alpar@8
   207
    if (!(is >> z.y)) return is;
alpar@8
   208
    if (is >> c) {
alpar@8
   209
      if (c != ')') is.putback(c);
alpar@8
   210
    } else {
alpar@8
   211
      is.clear();
alpar@8
   212
    }
alpar@8
   213
    return is;
alpar@8
   214
  }
alpar@8
   215
kpeter@241
   216
  ///Write a plain vector to a stream
alpar@8
   217
kpeter@241
   218
  ///Write a plain vector to a stream.
alpar@8
   219
  ///\relates Point
alpar@8
   220
  ///
alpar@8
   221
  template<typename T>
alpar@8
   222
  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
alpar@8
   223
  {
alpar@8
   224
    os << "(" << z.x << ", " << z.y << ")";
alpar@8
   225
    return os;
alpar@8
   226
  }
alpar@8
   227
alpar@8
   228
  ///Rotate by 90 degrees
alpar@8
   229
kpeter@15
   230
  ///Returns the parameter rotated by 90 degrees in positive direction.
alpar@8
   231
  ///\relates Point
alpar@8
   232
  ///
alpar@8
   233
  template<typename T>
alpar@8
   234
  inline Point<T> rot90(const Point<T> &z)
alpar@8
   235
  {
alpar@8
   236
    return Point<T>(-z.y,z.x);
alpar@8
   237
  }
alpar@8
   238
alpar@8
   239
  ///Rotate by 180 degrees
alpar@8
   240
kpeter@15
   241
  ///Returns the parameter rotated by 180 degrees.
alpar@8
   242
  ///\relates Point
alpar@8
   243
  ///
alpar@8
   244
  template<typename T>
alpar@8
   245
  inline Point<T> rot180(const Point<T> &z)
alpar@8
   246
  {
alpar@8
   247
    return Point<T>(-z.x,-z.y);
alpar@8
   248
  }
alpar@8
   249
alpar@8
   250
  ///Rotate by 270 degrees
alpar@8
   251
kpeter@15
   252
  ///Returns the parameter rotated by 90 degrees in negative direction.
alpar@8
   253
  ///\relates Point
alpar@8
   254
  ///
alpar@8
   255
  template<typename T>
alpar@8
   256
  inline Point<T> rot270(const Point<T> &z)
alpar@8
   257
  {
alpar@8
   258
    return Point<T>(z.y,-z.x);
alpar@8
   259
  }
alpar@8
   260
alpar@209
   261
alpar@8
   262
kpeter@241
   263
    /// A class to calculate or store the bounding box of plain vectors.
alpar@8
   264
kpeter@241
   265
    /// A class to calculate or store the bounding box of plain vectors.
kpeter@241
   266
    ///
alpar@8
   267
    template<typename T>
alpar@8
   268
    class BoundingBox {
kpeter@241
   269
      Point<T> _bottom_left, _top_right;
alpar@8
   270
      bool _empty;
alpar@8
   271
    public:
alpar@209
   272
alpar@8
   273
      ///Default constructor: creates an empty bounding box
alpar@8
   274
      BoundingBox() { _empty = true; }
alpar@8
   275
alpar@8
   276
      ///Construct an instance from one point
kpeter@241
   277
      BoundingBox(Point<T> a) {
kpeter@241
   278
        _bottom_left = _top_right = a;
kpeter@241
   279
        _empty = false;
kpeter@241
   280
      }
alpar@209
   281
alpar@8
   282
      ///Construct an instance from two points
alpar@209
   283
kpeter@15
   284
      ///Construct an instance from two points.
kpeter@15
   285
      ///\param a The bottom left corner.
kpeter@15
   286
      ///\param b The top right corner.
kpeter@15
   287
      ///\warning The coordinates of the bottom left corner must be no more
kpeter@15
   288
      ///than those of the top right one.
alpar@8
   289
      BoundingBox(Point<T> a,Point<T> b)
alpar@8
   290
      {
kpeter@241
   291
        _bottom_left = a;
kpeter@241
   292
        _top_right = b;
alpar@209
   293
        _empty = false;
alpar@8
   294
      }
alpar@209
   295
alpar@8
   296
      ///Construct an instance from four numbers
alpar@8
   297
kpeter@15
   298
      ///Construct an instance from four numbers.
kpeter@15
   299
      ///\param l The left side of the box.
kpeter@15
   300
      ///\param b The bottom of the box.
kpeter@15
   301
      ///\param r The right side of the box.
kpeter@15
   302
      ///\param t The top of the box.
kpeter@15
   303
      ///\warning The left side must be no more than the right side and
alpar@209
   304
      ///bottom must be no more than the top.
alpar@8
   305
      BoundingBox(T l,T b,T r,T t)
alpar@8
   306
      {
kpeter@241
   307
        _bottom_left=Point<T>(l,b);
kpeter@241
   308
        _top_right=Point<T>(r,t);
alpar@209
   309
        _empty = false;
alpar@8
   310
      }
alpar@209
   311
kpeter@15
   312
      ///Return \c true if the bounding box is empty.
alpar@209
   313
kpeter@15
   314
      ///Return \c true if the bounding box is empty (i.e. return \c false
kpeter@15
   315
      ///if at least one point was added to the box or the coordinates of
kpeter@15
   316
      ///the box were set).
kpeter@49
   317
      ///
alpar@209
   318
      ///The coordinates of an empty bounding box are not defined.
alpar@8
   319
      bool empty() const {
alpar@8
   320
        return _empty;
alpar@8
   321
      }
alpar@209
   322
alpar@8
   323
      ///Make the BoundingBox empty
alpar@8
   324
      void clear() {
kpeter@241
   325
        _empty = true;
alpar@8
   326
      }
alpar@8
   327
kpeter@49
   328
      ///Give back the bottom left corner of the box
alpar@8
   329
kpeter@49
   330
      ///Give back the bottom left corner of the box.
alpar@8
   331
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   332
      Point<T> bottomLeft() const {
kpeter@241
   333
        return _bottom_left;
alpar@8
   334
      }
alpar@8
   335
kpeter@49
   336
      ///Set the bottom left corner of the box
alpar@8
   337
kpeter@49
   338
      ///Set the bottom left corner of the box.
kpeter@241
   339
      ///\pre The box must not be empty.
alpar@8
   340
      void bottomLeft(Point<T> p) {
kpeter@241
   341
        _bottom_left = p;
alpar@8
   342
      }
alpar@8
   343
kpeter@49
   344
      ///Give back the top right corner of the box
alpar@8
   345
kpeter@49
   346
      ///Give back the top right corner of the box.
alpar@8
   347
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   348
      Point<T> topRight() const {
kpeter@241
   349
        return _top_right;
alpar@8
   350
      }
alpar@8
   351
kpeter@49
   352
      ///Set the top right corner of the box
alpar@8
   353
kpeter@49
   354
      ///Set the top right corner of the box.
kpeter@241
   355
      ///\pre The box must not be empty.
alpar@8
   356
      void topRight(Point<T> p) {
kpeter@241
   357
        _top_right = p;
alpar@8
   358
      }
alpar@8
   359
kpeter@49
   360
      ///Give back the bottom right corner of the box
alpar@8
   361
kpeter@49
   362
      ///Give back the bottom right corner of the box.
alpar@8
   363
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   364
      Point<T> bottomRight() const {
kpeter@241
   365
        return Point<T>(_top_right.x,_bottom_left.y);
alpar@8
   366
      }
alpar@8
   367
kpeter@49
   368
      ///Set the bottom right corner of the box
alpar@8
   369
kpeter@49
   370
      ///Set the bottom right corner of the box.
kpeter@241
   371
      ///\pre The box must not be empty.
alpar@8
   372
      void bottomRight(Point<T> p) {
kpeter@241
   373
        _top_right.x = p.x;
kpeter@241
   374
        _bottom_left.y = p.y;
alpar@8
   375
      }
alpar@209
   376
kpeter@49
   377
      ///Give back the top left corner of the box
alpar@8
   378
kpeter@49
   379
      ///Give back the top left corner of the box.
alpar@8
   380
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   381
      Point<T> topLeft() const {
kpeter@241
   382
        return Point<T>(_bottom_left.x,_top_right.y);
alpar@8
   383
      }
alpar@8
   384
kpeter@49
   385
      ///Set the top left corner of the box
alpar@8
   386
kpeter@49
   387
      ///Set the top left corner of the box.
kpeter@241
   388
      ///\pre The box must not be empty.
alpar@8
   389
      void topLeft(Point<T> p) {
kpeter@241
   390
        _top_right.y = p.y;
kpeter@241
   391
        _bottom_left.x = p.x;
alpar@8
   392
      }
alpar@8
   393
alpar@8
   394
      ///Give back the bottom of the box
alpar@8
   395
alpar@8
   396
      ///Give back the bottom of the box.
alpar@8
   397
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   398
      T bottom() const {
kpeter@241
   399
        return _bottom_left.y;
alpar@8
   400
      }
alpar@8
   401
alpar@8
   402
      ///Set the bottom of the box
alpar@8
   403
alpar@8
   404
      ///Set the bottom of the box.
kpeter@241
   405
      ///\pre The box must not be empty.
alpar@8
   406
      void bottom(T t) {
kpeter@241
   407
        _bottom_left.y = t;
alpar@8
   408
      }
alpar@8
   409
alpar@8
   410
      ///Give back the top of the box
alpar@8
   411
alpar@8
   412
      ///Give back the top of the box.
alpar@8
   413
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   414
      T top() const {
kpeter@241
   415
        return _top_right.y;
alpar@8
   416
      }
alpar@8
   417
alpar@8
   418
      ///Set the top of the box
alpar@8
   419
alpar@8
   420
      ///Set the top of the box.
kpeter@241
   421
      ///\pre The box must not be empty.
alpar@8
   422
      void top(T t) {
kpeter@241
   423
        _top_right.y = t;
alpar@8
   424
      }
alpar@8
   425
alpar@8
   426
      ///Give back the left side of the box
alpar@8
   427
alpar@8
   428
      ///Give back the left side of the box.
alpar@8
   429
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   430
      T left() const {
kpeter@241
   431
        return _bottom_left.x;
alpar@8
   432
      }
alpar@209
   433
alpar@8
   434
      ///Set the left side of the box
alpar@8
   435
alpar@8
   436
      ///Set the left side of the box.
kpeter@241
   437
      ///\pre The box must not be empty.
alpar@8
   438
      void left(T t) {
kpeter@241
   439
        _bottom_left.x = t;
alpar@8
   440
      }
alpar@8
   441
alpar@8
   442
      /// Give back the right side of the box
alpar@8
   443
alpar@8
   444
      /// Give back the right side of the box.
alpar@8
   445
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   446
      T right() const {
kpeter@241
   447
        return _top_right.x;
alpar@8
   448
      }
alpar@8
   449
alpar@8
   450
      ///Set the right side of the box
alpar@8
   451
alpar@8
   452
      ///Set the right side of the box.
kpeter@241
   453
      ///\pre The box must not be empty.
alpar@8
   454
      void right(T t) {
kpeter@241
   455
        _top_right.x = t;
alpar@8
   456
      }
alpar@8
   457
alpar@8
   458
      ///Give back the height of the box
alpar@8
   459
alpar@8
   460
      ///Give back the height of the box.
alpar@8
   461
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   462
      T height() const {
kpeter@241
   463
        return _top_right.y-_bottom_left.y;
alpar@8
   464
      }
alpar@8
   465
alpar@8
   466
      ///Give back the width of the box
alpar@8
   467
alpar@8
   468
      ///Give back the width of the box.
alpar@8
   469
      ///If the bounding box is empty, then the return value is not defined.
alpar@8
   470
      T width() const {
kpeter@241
   471
        return _top_right.x-_bottom_left.x;
alpar@8
   472
      }
alpar@8
   473
alpar@8
   474
      ///Checks whether a point is inside a bounding box
kpeter@15
   475
      bool inside(const Point<T>& u) const {
alpar@8
   476
        if (_empty)
alpar@8
   477
          return false;
kpeter@241
   478
        else {
kpeter@241
   479
          return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 &&
kpeter@241
   480
                   (u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 );
alpar@8
   481
        }
alpar@8
   482
      }
alpar@209
   483
alpar@8
   484
      ///Increments a bounding box with a point
kpeter@15
   485
kpeter@15
   486
      ///Increments a bounding box with a point.
kpeter@15
   487
      ///
alpar@8
   488
      BoundingBox& add(const Point<T>& u){
kpeter@241
   489
        if (_empty) {
kpeter@241
   490
          _bottom_left = _top_right = u;
alpar@8
   491
          _empty = false;
alpar@8
   492
        }
kpeter@241
   493
        else {
kpeter@241
   494
          if (_bottom_left.x > u.x) _bottom_left.x = u.x;
kpeter@241
   495
          if (_bottom_left.y > u.y) _bottom_left.y = u.y;
kpeter@241
   496
          if (_top_right.x < u.x) _top_right.x = u.x;
kpeter@241
   497
          if (_top_right.y < u.y) _top_right.y = u.y;
alpar@8
   498
        }
alpar@8
   499
        return *this;
alpar@8
   500
      }
alpar@209
   501
kpeter@15
   502
      ///Increments a bounding box to contain another bounding box
alpar@209
   503
kpeter@15
   504
      ///Increments a bounding box to contain another bounding box.
kpeter@15
   505
      ///
alpar@8
   506
      BoundingBox& add(const BoundingBox &u){
alpar@8
   507
        if ( !u.empty() ){
kpeter@241
   508
          add(u._bottom_left);
kpeter@241
   509
          add(u._top_right);
alpar@8
   510
        }
alpar@8
   511
        return *this;
alpar@8
   512
      }
alpar@209
   513
alpar@8
   514
      ///Intersection of two bounding boxes
kpeter@15
   515
kpeter@15
   516
      ///Intersection of two bounding boxes.
kpeter@15
   517
      ///
kpeter@15
   518
      BoundingBox operator&(const BoundingBox& u) const {
alpar@8
   519
        BoundingBox b;
kpeter@241
   520
        if (_empty || u._empty) {
alpar@209
   521
          b._empty = true;
alpar@209
   522
        } else {
kpeter@241
   523
          b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x);
kpeter@241
   524
          b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y);
kpeter@241
   525
          b._top_right.x = std::min(_top_right.x, u._top_right.x);
kpeter@241
   526
          b._top_right.y = std::min(_top_right.y, u._top_right.y);
kpeter@241
   527
          b._empty = b._bottom_left.x > b._top_right.x ||
kpeter@241
   528
                     b._bottom_left.y > b._top_right.y;
alpar@209
   529
        }
alpar@8
   530
        return b;
alpar@8
   531
      }
alpar@8
   532
alpar@8
   533
    };//class Boundingbox
alpar@8
   534
alpar@8
   535
kpeter@49
   536
  ///Map of x-coordinates of a \ref Point "Point"-map
alpar@8
   537
alpar@8
   538
  ///\ingroup maps
kpeter@49
   539
  ///Map of x-coordinates of a \ref Point "Point"-map.
alpar@8
   540
  ///
alpar@8
   541
  template<class M>
alpar@209
   542
  class XMap
alpar@8
   543
  {
alpar@8
   544
    M& _map;
alpar@8
   545
  public:
alpar@8
   546
alpar@8
   547
    typedef typename M::Value::Value Value;
alpar@8
   548
    typedef typename M::Key Key;
alpar@8
   549
    ///\e
alpar@8
   550
    XMap(M& map) : _map(map) {}
alpar@8
   551
    Value operator[](Key k) const {return _map[k].x;}
alpar@8
   552
    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
alpar@8
   553
  };
alpar@209
   554
alpar@8
   555
  ///Returns an \ref XMap class
alpar@8
   556
alpar@8
   557
  ///This function just returns an \ref XMap class.
alpar@8
   558
  ///
alpar@8
   559
  ///\ingroup maps
alpar@8
   560
  ///\relates XMap
alpar@209
   561
  template<class M>
alpar@209
   562
  inline XMap<M> xMap(M &m)
alpar@8
   563
  {
alpar@8
   564
    return XMap<M>(m);
alpar@8
   565
  }
alpar@8
   566
alpar@209
   567
  template<class M>
alpar@209
   568
  inline XMap<M> xMap(const M &m)
alpar@8
   569
  {
alpar@8
   570
    return XMap<M>(m);
alpar@8
   571
  }
alpar@8
   572
kpeter@49
   573
  ///Constant (read only) version of \ref XMap
alpar@8
   574
alpar@8
   575
  ///\ingroup maps
alpar@8
   576
  ///Constant (read only) version of \ref XMap
alpar@8
   577
  ///
alpar@8
   578
  template<class M>
alpar@209
   579
  class ConstXMap
alpar@8
   580
  {
alpar@8
   581
    const M& _map;
alpar@8
   582
  public:
alpar@8
   583
alpar@8
   584
    typedef typename M::Value::Value Value;
alpar@8
   585
    typedef typename M::Key Key;
alpar@8
   586
    ///\e
alpar@8
   587
    ConstXMap(const M &map) : _map(map) {}
alpar@8
   588
    Value operator[](Key k) const {return _map[k].x;}
alpar@8
   589
  };
alpar@209
   590
alpar@8
   591
  ///Returns a \ref ConstXMap class
alpar@8
   592
kpeter@15
   593
  ///This function just returns a \ref ConstXMap class.
alpar@8
   594
  ///
alpar@8
   595
  ///\ingroup maps
alpar@8
   596
  ///\relates ConstXMap
alpar@209
   597
  template<class M>
alpar@209
   598
  inline ConstXMap<M> xMap(const M &m)
alpar@8
   599
  {
alpar@8
   600
    return ConstXMap<M>(m);
alpar@8
   601
  }
alpar@8
   602
kpeter@49
   603
  ///Map of y-coordinates of a \ref Point "Point"-map
alpar@209
   604
alpar@8
   605
  ///\ingroup maps
kpeter@15
   606
  ///Map of y-coordinates of a \ref Point "Point"-map.
alpar@8
   607
  ///
alpar@8
   608
  template<class M>
alpar@209
   609
  class YMap
alpar@8
   610
  {
alpar@8
   611
    M& _map;
alpar@8
   612
  public:
alpar@8
   613
alpar@8
   614
    typedef typename M::Value::Value Value;
alpar@8
   615
    typedef typename M::Key Key;
alpar@8
   616
    ///\e
alpar@8
   617
    YMap(M& map) : _map(map) {}
alpar@8
   618
    Value operator[](Key k) const {return _map[k].y;}
alpar@8
   619
    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
alpar@8
   620
  };
alpar@8
   621
kpeter@15
   622
  ///Returns a \ref YMap class
alpar@8
   623
kpeter@15
   624
  ///This function just returns a \ref YMap class.
alpar@8
   625
  ///
alpar@8
   626
  ///\ingroup maps
alpar@8
   627
  ///\relates YMap
alpar@209
   628
  template<class M>
alpar@209
   629
  inline YMap<M> yMap(M &m)
alpar@8
   630
  {
alpar@8
   631
    return YMap<M>(m);
alpar@8
   632
  }
alpar@8
   633
alpar@209
   634
  template<class M>
alpar@209
   635
  inline YMap<M> yMap(const M &m)
alpar@8
   636
  {
alpar@8
   637
    return YMap<M>(m);
alpar@8
   638
  }
alpar@8
   639
kpeter@49
   640
  ///Constant (read only) version of \ref YMap
alpar@8
   641
alpar@8
   642
  ///\ingroup maps
alpar@8
   643
  ///Constant (read only) version of \ref YMap
alpar@8
   644
  ///
alpar@8
   645
  template<class M>
alpar@209
   646
  class ConstYMap
alpar@8
   647
  {
alpar@8
   648
    const M& _map;
alpar@8
   649
  public:
alpar@8
   650
alpar@8
   651
    typedef typename M::Value::Value Value;
alpar@8
   652
    typedef typename M::Key Key;
alpar@8
   653
    ///\e
alpar@8
   654
    ConstYMap(const M &map) : _map(map) {}
alpar@8
   655
    Value operator[](Key k) const {return _map[k].y;}
alpar@8
   656
  };
alpar@209
   657
alpar@8
   658
  ///Returns a \ref ConstYMap class
alpar@8
   659
kpeter@15
   660
  ///This function just returns a \ref ConstYMap class.
alpar@8
   661
  ///
alpar@8
   662
  ///\ingroup maps
alpar@8
   663
  ///\relates ConstYMap
alpar@209
   664
  template<class M>
alpar@209
   665
  inline ConstYMap<M> yMap(const M &m)
alpar@8
   666
  {
alpar@8
   667
    return ConstYMap<M>(m);
alpar@8
   668
  }
alpar@8
   669
alpar@8
   670
kpeter@49
   671
  ///\brief Map of the \ref Point::normSquare() "normSquare()"
kpeter@49
   672
  ///of a \ref Point "Point"-map
kpeter@49
   673
  ///
kpeter@49
   674
  ///Map of the \ref Point::normSquare() "normSquare()"
kpeter@49
   675
  ///of a \ref Point "Point"-map.
kpeter@49
   676
  ///\ingroup maps
alpar@8
   677
  template<class M>
alpar@209
   678
  class NormSquareMap
alpar@8
   679
  {
alpar@8
   680
    const M& _map;
alpar@8
   681
  public:
alpar@8
   682
alpar@8
   683
    typedef typename M::Value::Value Value;
alpar@8
   684
    typedef typename M::Key Key;
alpar@8
   685
    ///\e
alpar@8
   686
    NormSquareMap(const M &map) : _map(map) {}
alpar@8
   687
    Value operator[](Key k) const {return _map[k].normSquare();}
alpar@8
   688
  };
alpar@209
   689
alpar@8
   690
  ///Returns a \ref NormSquareMap class
alpar@8
   691
kpeter@15
   692
  ///This function just returns a \ref NormSquareMap class.
alpar@8
   693
  ///
alpar@8
   694
  ///\ingroup maps
alpar@8
   695
  ///\relates NormSquareMap
alpar@209
   696
  template<class M>
alpar@209
   697
  inline NormSquareMap<M> normSquareMap(const M &m)
alpar@8
   698
  {
alpar@8
   699
    return NormSquareMap<M>(m);
alpar@8
   700
  }
alpar@8
   701
alpar@8
   702
  /// @}
alpar@8
   703
alpar@8
   704
  } //namespce dim2
alpar@209
   705
alpar@8
   706
} //namespace lemon
alpar@8
   707
alpar@8
   708
#endif //LEMON_DIM2_H