lemon/dim2.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 440 88ed40ad0d4f
child 1112 6aea07d5ca48
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

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