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