COIN-OR::LEMON - Graph Library

source: lemon-1.2/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
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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
26///\brief A simple two dimensional vector and a bounding box implementation
27///
28/// The class \ref lemon::dim2::Point "dim2::Point" implements
29/// a two dimensional vector with the usual operations.
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
47  /// A simple two dimensional vector (plain vector) implementation
48
49  /// A simple two dimensional vector (plain vector) implementation
50  /// with the usual vector operations.
51  template<typename T>
52    class Point {
53
54    public:
55
56      typedef T Value;
57
58      ///First coordinate
59      T x;
60      ///Second coordinate
61      T y;
62
63      ///Default constructor
64      Point() {}
65
66      ///Construct an instance from coordinates
67      Point(T a, T b) : x(a), y(b) { }
68
69      ///Returns the dimension of the vector (i.e. returns 2).
70
71      ///The dimension of the vector.
72      ///This function always returns 2.
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      }
94
95      ///Increment the left hand side by \c u
96      Point<T>& operator +=(const Point<T>& u) {
97        x += u.x;
98        y += u.y;
99        return *this;
100      }
101
102      ///Decrement the left hand side by \c u
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      }
122
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      }
127
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
134      ///Return the negative of the vector
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
171  ///Return a Point
172
173  ///Return a Point.
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
182  ///Return a vector multiplied by a scalar.
183  ///\relates Point
184  template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
185    return x*u;
186  }
187
188  ///Read a plain vector from a stream
189
190  ///Read a plain vector from a stream.
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
216  ///Write a plain vector to a stream
217
218  ///Write a plain vector to a stream.
219  ///\relates Point
220  ///
221  template<typename T>
222  inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
223  {
224    os << "(" << z.x << "," << z.y << ")";
225    return os;
226  }
227
228  ///Rotate by 90 degrees
229
230  ///Returns the parameter rotated by 90 degrees in positive direction.
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
241  ///Returns the parameter rotated by 180 degrees.
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
252  ///Returns the parameter rotated by 90 degrees in negative direction.
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
261
262
263    /// A class to calculate or store the bounding box of plain vectors.
264
265    /// A class to calculate or store the bounding box of plain vectors.
266    ///
267    template<typename T>
268    class BoundingBox {
269      Point<T> _bottom_left, _top_right;
270      bool _empty;
271    public:
272
273      ///Default constructor: creates an empty bounding box
274      BoundingBox() { _empty = true; }
275
276      ///Construct an instance from one point
277      BoundingBox(Point<T> a) {
278        _bottom_left = _top_right = a;
279        _empty = false;
280      }
281
282      ///Construct an instance from two points
283
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.
289      BoundingBox(Point<T> a,Point<T> b)
290      {
291        _bottom_left = a;
292        _top_right = b;
293        _empty = false;
294      }
295
296      ///Construct an instance from four numbers
297
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
304      ///bottom must be no more than the top.
305      BoundingBox(T l,T b,T r,T t)
306      {
307        _bottom_left=Point<T>(l,b);
308        _top_right=Point<T>(r,t);
309        _empty = false;
310      }
311
312      ///Return \c true if the bounding box is empty.
313
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).
317      ///
318      ///The coordinates of an empty bounding box are not defined.
319      bool empty() const {
320        return _empty;
321      }
322
323      ///Make the BoundingBox empty
324      void clear() {
325        _empty = true;
326      }
327
328      ///Give back the bottom left corner of the box
329
330      ///Give back the bottom left corner of the box.
331      ///If the bounding box is empty, then the return value is not defined.
332      Point<T> bottomLeft() const {
333        return _bottom_left;
334      }
335
336      ///Set the bottom left corner of the box
337
338      ///Set the bottom left corner of the box.
339      ///\pre The box must not be empty.
340      void bottomLeft(Point<T> p) {
341        _bottom_left = p;
342      }
343
344      ///Give back the top right corner of the box
345
346      ///Give back the top right corner of the box.
347      ///If the bounding box is empty, then the return value is not defined.
348      Point<T> topRight() const {
349        return _top_right;
350      }
351
352      ///Set the top right corner of the box
353
354      ///Set the top right corner of the box.
355      ///\pre The box must not be empty.
356      void topRight(Point<T> p) {
357        _top_right = p;
358      }
359
360      ///Give back the bottom right corner of the box
361
362      ///Give back the bottom right corner of the box.
363      ///If the bounding box is empty, then the return value is not defined.
364      Point<T> bottomRight() const {
365        return Point<T>(_top_right.x,_bottom_left.y);
366      }
367
368      ///Set the bottom right corner of the box
369
370      ///Set the bottom right corner of the box.
371      ///\pre The box must not be empty.
372      void bottomRight(Point<T> p) {
373        _top_right.x = p.x;
374        _bottom_left.y = p.y;
375      }
376
377      ///Give back the top left corner of the box
378
379      ///Give back the top left corner of the box.
380      ///If the bounding box is empty, then the return value is not defined.
381      Point<T> topLeft() const {
382        return Point<T>(_bottom_left.x,_top_right.y);
383      }
384
385      ///Set the top left corner of the box
386
387      ///Set the top left corner of the box.
388      ///\pre The box must not be empty.
389      void topLeft(Point<T> p) {
390        _top_right.y = p.y;
391        _bottom_left.x = p.x;
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 {
399        return _bottom_left.y;
400      }
401
402      ///Set the bottom of the box
403
404      ///Set the bottom of the box.
405      ///\pre The box must not be empty.
406      void bottom(T t) {
407        _bottom_left.y = t;
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 {
415        return _top_right.y;
416      }
417
418      ///Set the top of the box
419
420      ///Set the top of the box.
421      ///\pre The box must not be empty.
422      void top(T t) {
423        _top_right.y = t;
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 {
431        return _bottom_left.x;
432      }
433
434      ///Set the left side of the box
435
436      ///Set the left side of the box.
437      ///\pre The box must not be empty.
438      void left(T t) {
439        _bottom_left.x = t;
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 {
447        return _top_right.x;
448      }
449
450      ///Set the right side of the box
451
452      ///Set the right side of the box.
453      ///\pre The box must not be empty.
454      void right(T t) {
455        _top_right.x = t;
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 {
463        return _top_right.y-_bottom_left.y;
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 {
471        return _top_right.x-_bottom_left.x;
472      }
473
474      ///Checks whether a point is inside a bounding box
475      bool inside(const Point<T>& u) const {
476        if (_empty)
477          return false;
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 );
481        }
482      }
483
484      ///Increments a bounding box with a point
485
486      ///Increments a bounding box with a point.
487      ///
488      BoundingBox& add(const Point<T>& u){
489        if (_empty) {
490          _bottom_left = _top_right = u;
491          _empty = false;
492        }
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;
498        }
499        return *this;
500      }
501
502      ///Increments a bounding box to contain another bounding box
503
504      ///Increments a bounding box to contain another bounding box.
505      ///
506      BoundingBox& add(const BoundingBox &u){
507        if ( !u.empty() ){
508          add(u._bottom_left);
509          add(u._top_right);
510        }
511        return *this;
512      }
513
514      ///Intersection of two bounding boxes
515
516      ///Intersection of two bounding boxes.
517      ///
518      BoundingBox operator&(const BoundingBox& u) const {
519        BoundingBox b;
520        if (_empty || u._empty) {
521          b._empty = true;
522        } else {
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;
529        }
530        return b;
531      }
532
533    };//class Boundingbox
534
535
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
577  ///Map of x-coordinates of a \ref Point "Point"-map
578
579  ///\ingroup maps
580  ///Map of x-coordinates of a \ref Point "Point"-map.
581  ///
582  template<class M>
583  class XMap
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  };
595
596  ///Returns an \ref XMap class
597
598  ///This function just returns an \ref XMap class.
599  ///
600  ///\ingroup maps
601  ///\relates XMap
602  template<class M>
603  inline XMap<M> xMap(M &m)
604  {
605    return XMap<M>(m);
606  }
607
608  template<class M>
609  inline XMap<M> xMap(const M &m)
610  {
611    return XMap<M>(m);
612  }
613
614  ///Constant (read only) version of \ref XMap
615
616  ///\ingroup maps
617  ///Constant (read only) version of \ref XMap
618  ///
619  template<class M>
620  class ConstXMap
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  };
631
632  ///Returns a \ref ConstXMap class
633
634  ///This function just returns a \ref ConstXMap class.
635  ///
636  ///\ingroup maps
637  ///\relates ConstXMap
638  template<class M>
639  inline ConstXMap<M> xMap(const M &m)
640  {
641    return ConstXMap<M>(m);
642  }
643
644  ///Map of y-coordinates of a \ref Point "Point"-map
645
646  ///\ingroup maps
647  ///Map of y-coordinates of a \ref Point "Point"-map.
648  ///
649  template<class M>
650  class YMap
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
663  ///Returns a \ref YMap class
664
665  ///This function just returns a \ref YMap class.
666  ///
667  ///\ingroup maps
668  ///\relates YMap
669  template<class M>
670  inline YMap<M> yMap(M &m)
671  {
672    return YMap<M>(m);
673  }
674
675  template<class M>
676  inline YMap<M> yMap(const M &m)
677  {
678    return YMap<M>(m);
679  }
680
681  ///Constant (read only) version of \ref YMap
682
683  ///\ingroup maps
684  ///Constant (read only) version of \ref YMap
685  ///
686  template<class M>
687  class ConstYMap
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  };
698
699  ///Returns a \ref ConstYMap class
700
701  ///This function just returns a \ref ConstYMap class.
702  ///
703  ///\ingroup maps
704  ///\relates ConstYMap
705  template<class M>
706  inline ConstYMap<M> yMap(const M &m)
707  {
708    return ConstYMap<M>(m);
709  }
710
711
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
718  template<class M>
719  class NormSquareMap
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  };
730
731  ///Returns a \ref NormSquareMap class
732
733  ///This function just returns a \ref NormSquareMap class.
734  ///
735  ///\ingroup maps
736  ///\relates NormSquareMap
737  template<class M>
738  inline NormSquareMap<M> normSquareMap(const M &m)
739  {
740    return NormSquareMap<M>(m);
741  }
742
743  /// @}
744
745  } //namespce dim2
746
747} //namespace lemon
748
749#endif //LEMON_DIM2_H
Note: See TracBrowser for help on using the repository browser.