COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/xy.h @ 1970:bd88ea06ab69

Last change on this file since 1970:bd88ea06ab69 was 1956:a055123339d5, checked in by Alpar Juttner, 15 years ago

Unified copyright notices

File size: 13.7 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/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  ///\author Attila Bernath
51  template<typename T>
52    class xy {
53
54    public:
55
56      typedef T Value;
57
58      T x,y;     
59     
60      ///Default constructor
61      xy() {}
62
63      ///Constructing the instance from coordinates
64      xy(T a, T b) : x(a), y(b) { }
65
66
67      ///Conversion constructor
68      template<class TT> xy(const xy<TT> &p) : x(p.x), y(p.y) {}
69
70      ///Gives back the square of the norm of the vector
71      T normSquare() const {
72        return x*x+y*y;
73      }
74 
75      ///Increments the left hand side by u
76      xy<T>& operator +=(const xy<T>& u) {
77        x += u.x;
78        y += u.y;
79        return *this;
80      }
81 
82      ///Decrements the left hand side by u
83      xy<T>& operator -=(const xy<T>& u) {
84        x -= u.x;
85        y -= u.y;
86        return *this;
87      }
88
89      ///Multiplying the left hand side with a scalar
90      xy<T>& operator *=(const T &u) {
91        x *= u;
92        y *= u;
93        return *this;
94      }
95
96      ///Dividing the left hand side by a scalar
97      xy<T>& operator /=(const T &u) {
98        x /= u;
99        y /= u;
100        return *this;
101      }
102 
103      ///Returns the scalar product of two vectors
104      T operator *(const xy<T>& u) const {
105        return x*u.x+y*u.y;
106      }
107 
108      ///Returns the sum of two vectors
109      xy<T> operator+(const xy<T> &u) const {
110        xy<T> b=*this;
111        return b+=u;
112      }
113
114      ///Returns the neg of the vectors
115      xy<T> operator-() const {
116        xy<T> b=*this;
117        b.x=-b.x; b.y=-b.y;
118        return b;
119      }
120
121      ///Returns the difference of two vectors
122      xy<T> operator-(const xy<T> &u) const {
123        xy<T> b=*this;
124        return b-=u;
125      }
126
127      ///Returns a vector multiplied by a scalar
128      xy<T> operator*(const T &u) const {
129        xy<T> b=*this;
130        return b*=u;
131      }
132
133      ///Returns a vector divided by a scalar
134      xy<T> operator/(const T &u) const {
135        xy<T> b=*this;
136        return b/=u;
137      }
138
139      ///Testing equality
140      bool operator==(const xy<T> &u) const {
141        return (x==u.x) && (y==u.y);
142      }
143
144      ///Testing inequality
145      bool operator!=(xy u) const {
146        return  (x!=u.x) || (y!=u.y);
147      }
148
149    };
150
151  ///Returns a vector multiplied by a scalar
152
153  ///Returns a vector multiplied by a scalar
154  ///\relates xy
155  template<typename T> xy<T> operator*(const T &u,const xy<T> &x) {
156    return x*u;
157  }
158
159  ///Read a plainvector from a stream
160
161  ///Read a plainvector from a stream
162  ///\relates xy
163  ///
164  template<typename T>
165  inline std::istream& operator>>(std::istream &is, xy<T> &z) {
166    char c;
167    if (is >> c) {
168      if (c != '(') is.putback(c);
169    } else {
170      is.clear();
171    }
172    if (!(is >> z.x)) return is;
173    if (is >> c) {
174      if (c != ',') is.putback(c);
175    } else {
176      is.clear();
177    }
178    if (!(is >> z.y)) return is;
179    if (is >> c) {
180      if (c != ')') is.putback(c);
181    } else {
182      is.clear();
183    }
184    return is;
185  }
186
187  ///Write a plainvector to a stream
188
189  ///Write a plainvector to a stream
190  ///\relates xy
191  ///
192  template<typename T>
193  inline std::ostream& operator<<(std::ostream &os, const xy<T>& z)
194  {
195    os << "(" << z.x << ", " << z.y << ")";
196    return os;
197  }
198
199  ///Rotate by 90 degrees
200
201  ///Returns its parameter rotated by 90 degrees in positive direction.
202  ///\relates xy
203  ///
204  template<typename T>
205  inline xy<T> rot90(const xy<T> &z)
206  {
207    return xy<T>(-z.y,z.x);
208  }
209
210  ///Rotate by 270 degrees
211
212  ///Returns its parameter rotated by 90 degrees in negative direction.
213  ///\relates xy
214  ///
215  template<typename T>
216  inline xy<T> rot270(const xy<T> &z)
217  {
218    return xy<T>(z.y,-z.x);
219  }
220
221 
222
223  /// A class to calculate or store the bounding box of plainvectors.
224
225  /// A class to calculate or store the bounding box of plainvectors.
226  ///
227  ///\author Attila Bernath
228  template<typename T>
229    class BoundingBox {
230      xy<T> bottom_left, top_right;
231      bool _empty;
232    public:
233     
234      ///Default constructor: creates an empty bounding box
235      BoundingBox() { _empty = true; }
236
237      ///Constructing the instance from one point
238      BoundingBox(xy<T> a) { bottom_left=top_right=a; _empty = false; }
239
240      ///Were any points added?
241      bool empty() const {
242        return _empty;
243      }
244
245      ///Makes the BoundingBox empty
246      void clear() {
247        _empty=1;
248      }
249
250      ///\brief Gives back the bottom left corner
251      ///(if the bounding box is empty, then the return value is not defined)
252      xy<T> bottomLeft() const {
253        return bottom_left;
254      }
255
256      ///\brief Sets the bottom left corner
257      ///(should only bee used for non-empty box)
258      void bottomLeft(xy<T> p) {
259        bottom_left = p;
260      }
261
262      ///\brief Gives back the top right corner
263      ///(if the bounding box is empty, then the return value is not defined)
264      xy<T> topRight() const {
265        return top_right;
266      }
267
268      ///\brief Sets the top right corner
269      ///(should only bee used for non-empty box)
270      void topRight(xy<T> p) {
271        top_right = p;
272      }
273
274      ///\brief Gives back the bottom right corner
275      ///(if the bounding box is empty, then the return value is not defined)
276      xy<T> bottomRight() const {
277        return xy<T>(top_right.x,bottom_left.y);
278      }
279
280      ///\brief Sets the bottom right corner
281      ///(should only bee used for non-empty box)
282      void bottomRight(xy<T> p) {
283        top_right.x = p.x;
284        bottom_left.y = p.y;
285      }
286
287      ///\brief Gives back the top left corner
288      ///(if the bounding box is empty, then the return value is not defined)
289      xy<T> topLeft() const {
290        return xy<T>(bottom_left.x,top_right.y);
291      }
292
293      ///\brief Sets the top left corner
294      ///(should only bee used for non-empty box)
295      void topLeft(xy<T> p) {
296        top_right.y = p.y;
297        bottom_left.x = p.x;
298      }
299
300      ///\brief Gives back the bottom of the box
301      ///(if the bounding box is empty, then the return value is not defined)
302      T bottom() const {
303        return bottom_left.y;
304      }
305
306      ///\brief Sets the bottom of the box
307      ///(should only bee used for non-empty box)
308      void bottom(T t) {
309        bottom_left.y = t;
310      }
311
312      ///\brief Gives back the top of the box
313      ///(if the bounding box is empty, then the return value is not defined)
314      T top() const {
315        return top_right.y;
316      }
317
318      ///\brief Sets the top of the box
319      ///(should only bee used for non-empty box)
320      void top(T t) {
321        top_right.y = t;
322      }
323
324      ///\brief Gives back the left side of the box
325      ///(if the bounding box is empty, then the return value is not defined)
326      T left() const {
327        return bottom_left.x;
328      }
329
330      ///\brief Sets the left side of the box
331      ///(should only bee used for non-empty box)
332      void left(T t) {
333        bottom_left.x = t;
334      }
335
336      ///\brief Gives back the right side of the box
337      ///(if the bounding box is empty, then the return value is not defined)
338      T right() const {
339        return top_right.x;
340      }
341
342      ///\brief Sets the right side of the box
343      ///(should only bee used for non-empty box)
344      void right(T t) {
345        top_right.x = t;
346      }
347
348      ///\brief Gives back the height of the box
349      ///(if the bounding box is empty, then the return value is not defined)
350      T height() const {
351        return top_right.y-bottom_left.y;
352      }
353
354      ///\brief Gives back the width of the box
355      ///(if the bounding box is empty, then the return value is not defined)
356      T width() const {
357        return top_right.x-bottom_left.x;
358      }
359
360      ///Checks whether a point is inside a bounding box
361      bool inside(const xy<T>& u){
362        if (_empty)
363          return false;
364        else{
365          return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
366              (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
367        }
368      }
369 
370      ///Increments a bounding box with a point
371      BoundingBox& add(const xy<T>& u){
372        if (_empty){
373          bottom_left=top_right=u;
374          _empty = false;
375        }
376        else{
377          if (bottom_left.x > u.x) bottom_left.x = u.x;
378          if (bottom_left.y > u.y) bottom_left.y = u.y;
379          if (top_right.x < u.x) top_right.x = u.x;
380          if (top_right.y < u.y) top_right.y = u.y;
381        }
382        return *this;
383      }
384 
385//       ///Sums a bounding box and a point
386//       BoundingBox operator +(const xy<T>& u){
387//         BoundingBox b = *this;
388//         return b += u;
389//       }
390
391      ///Increments a bounding box with an other bounding box
392      BoundingBox& add(const BoundingBox &u){
393        if ( !u.empty() ){
394          this->add(u.bottomLeft());
395          this->add(u.topRight());
396        }
397        return *this;
398      }
399 
400      ///Sums two bounding boxes
401      BoundingBox operator +(const BoundingBox& u){
402        BoundingBox b = *this;
403        return b.add(u);
404      }
405
406
407      ///Intersection of two bounding boxes
408      BoundingBox operator &(const BoundingBox& u){
409        BoundingBox b;
410        b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
411        b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
412        b.top_right.x=std::min(this->top_right.x,u.top_right.x);
413        b.top_right.y=std::min(this->top_right.y,u.top_right.y);
414        b._empty = this->_empty || u._empty ||
415          b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
416        return b;
417      }
418
419    };//class Boundingbox
420
421
422  ///Map of x-coordinates of an xy<>-map
423
424  ///\ingroup maps
425  ///
426  template<class M>
427  class XMap
428  {
429    M& _map;
430  public:
431
432    typedef typename M::Value::Value Value;
433    typedef typename M::Key Key;
434    ///\e
435    XMap(M& map) : _map(map) {}
436    Value operator[](Key k) const {return _map[k].x;}
437    void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
438  };
439   
440  ///Returns an \ref XMap class
441
442  ///This function just returns an \ref XMap class.
443  ///
444  ///\ingroup maps
445  ///\relates XMap
446  template<class M>
447  inline XMap<M> xMap(M &m)
448  {
449    return XMap<M>(m);
450  }
451
452  template<class M>
453  inline XMap<M> xMap(const M &m)
454  {
455    return XMap<M>(m);
456  }
457
458  ///Constant (read only) version of \ref XMap
459
460  ///\ingroup maps
461  ///
462  template<class M>
463  class ConstXMap
464  {
465    const M& _map;
466  public:
467
468    typedef typename M::Value::Value Value;
469    typedef typename M::Key Key;
470    ///\e
471    ConstXMap(const M &map) : _map(map) {}
472    Value operator[](Key k) const {return _map[k].x;}
473  };
474   
475  ///Returns a \ref ConstXMap class
476
477  ///This function just returns an \ref ConstXMap class.
478  ///
479  ///\ingroup maps
480  ///\relates ConstXMap
481  template<class M>
482  inline ConstXMap<M> xMap(const M &m)
483  {
484    return ConstXMap<M>(m);
485  }
486
487  ///Map of y-coordinates of an xy<>-map
488   
489  ///\ingroup maps
490  ///
491  template<class M>
492  class YMap
493  {
494    M& _map;
495  public:
496
497    typedef typename M::Value::Value Value;
498    typedef typename M::Key Key;
499    ///\e
500    YMap(M& map) : _map(map) {}
501    Value operator[](Key k) const {return _map[k].y;}
502    void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
503  };
504
505  ///Returns an \ref YMap class
506
507  ///This function just returns an \ref YMap class.
508  ///
509  ///\ingroup maps
510  ///\relates YMap
511  template<class M>
512  inline YMap<M> yMap(M &m)
513  {
514    return YMap<M>(m);
515  }
516
517  template<class M>
518  inline YMap<M> yMap(const M &m)
519  {
520    return YMap<M>(m);
521  }
522
523  ///Constant (read only) version of \ref YMap
524
525  ///\ingroup maps
526  ///
527  template<class M>
528  class ConstYMap
529  {
530    const M& _map;
531  public:
532
533    typedef typename M::Value::Value Value;
534    typedef typename M::Key Key;
535    ///\e
536    ConstYMap(const M &map) : _map(map) {}
537    Value operator[](Key k) const {return _map[k].y;}
538  };
539   
540  ///Returns a \ref ConstYMap class
541
542  ///This function just returns an \ref ConstYMap class.
543  ///
544  ///\ingroup maps
545  ///\relates ConstYMap
546  template<class M>
547  inline ConstYMap<M> yMap(const M &m)
548  {
549    return ConstYMap<M>(m);
550  }
551
552
553  ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map
554
555  ///Map of the \ref xy::normSquare() "normSquare()" of an \ref xy "xy"-map
556  ///\ingroup maps
557  ///
558  template<class M>
559  class NormSquareMap
560  {
561    const M& _map;
562  public:
563
564    typedef typename M::Value::Value Value;
565    typedef typename M::Key Key;
566    ///\e
567    NormSquareMap(const M &map) : _map(map) {}
568    Value operator[](Key k) const {return _map[k].normSquare();}
569  };
570   
571  ///Returns a \ref NormSquareMap class
572
573  ///This function just returns an \ref NormSquareMap class.
574  ///
575  ///\ingroup maps
576  ///\relates NormSquareMap
577  template<class M>
578  inline NormSquareMap<M> normSquareMap(const M &m)
579  {
580    return NormSquareMap<M>(m);
581  }
582
583  /// @}
584
585
586} //namespace lemon
587
588#endif //LEMON_XY_H
Note: See TracBrowser for help on using the repository browser.