lemon/dim2.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 314 2cc60866a0c9
child 714 98a30824fe36
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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
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