COIN-OR::LEMON - Graph Library

source: lemon/lemon/dim2.h @ 250:d0aae16df1bb

Last change on this file since 250:d0aae16df1bb was 250:d0aae16df1bb, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Stream operators for Point and BoundingBox? classes (ticket #126)

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