COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dim2.h @ 2334:c1e936e6a46b

Last change on this file since 2334:c1e936e6a46b was 2217:4a10a45d55f6, checked in by Balazs Dezso, 18 years ago

Doc fix

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