COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dim2.h @ 2212:0ad3835449f8

Last change on this file since 2212:0ad3835449f8 was 2212:0ad3835449f8, checked in by Balazs Dezso, 13 years ago

Some small improvments

size() and subscription operators
compatibility with higher dimensions

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