COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/xy.h @ 2162:6831fa007688

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