Unify the spelling of LEMON (#103).
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
23 #include <lemon/core.h>
27 ///\brief A simple two dimensional vector and a bounding box implementation
29 /// The class \ref lemon::dim2::Point "dim2::Point" implements
30 /// a two dimensional vector with the usual operations.
32 /// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
33 /// can be used to determine
34 /// the rectangular bounding box of a set of
35 /// \ref lemon::dim2::Point "dim2::Point"'s.
39 ///Tools for handling two dimensional coordinates
41 ///This namespace is a storage of several
42 ///tools for handling two dimensional coordinates
48 /// A simple two dimensional vector (plainvector) implementation
50 /// A simple two dimensional vector (plainvector) implementation
51 /// with the usual vector operations.
64 ///Default constructor
67 ///Construct an instance from coordinates
68 Point(T a, T b) : x(a), y(b) { }
70 ///Returns the dimension of the vector (i.e. returns 2).
72 ///The dimension of the vector.
73 ///This function always returns 2.
74 int size() const { return 2; }
76 ///Subscripting operator
78 ///\c p[0] is \c p.x and \c p[1] is \c p.y
80 T& operator[](int idx) { return idx == 0 ? x : y; }
82 ///Const subscripting operator
84 ///\c p[0] is \c p.x and \c p[1] is \c p.y
86 const T& operator[](int idx) const { return idx == 0 ? x : y; }
88 ///Conversion constructor
89 template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
91 ///Give back the square of the norm of the vector
92 T normSquare() const {
96 ///Increment the left hand side by \c u
97 Point<T>& operator +=(const Point<T>& u) {
103 ///Decrement the left hand side by \c u
104 Point<T>& operator -=(const Point<T>& u) {
110 ///Multiply the left hand side with a scalar
111 Point<T>& operator *=(const T &u) {
117 ///Divide the left hand side by a scalar
118 Point<T>& operator /=(const T &u) {
124 ///Return the scalar product of two vectors
125 T operator *(const Point<T>& u) const {
129 ///Return the sum of two vectors
130 Point<T> operator+(const Point<T> &u) const {
135 ///Return the negative of the vector
136 Point<T> operator-() const {
142 ///Return the difference of two vectors
143 Point<T> operator-(const Point<T> &u) const {
148 ///Return a vector multiplied by a scalar
149 Point<T> operator*(const T &u) const {
154 ///Return a vector divided by a scalar
155 Point<T> operator/(const T &u) const {
161 bool operator==(const Point<T> &u) const {
162 return (x==u.x) && (y==u.y);
166 bool operator!=(Point u) const {
167 return (x!=u.x) || (y!=u.y);
176 template <typename T>
177 inline Point<T> makePoint(const T& x, const T& y) {
178 return Point<T>(x, y);
181 ///Return a vector multiplied by a scalar
183 ///Return a vector multiplied by a scalar.
185 template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
189 ///Read a plainvector from a stream
191 ///Read a plainvector from a stream.
195 inline std::istream& operator>>(std::istream &is, Point<T> &z) {
198 if (c != '(') is.putback(c);
202 if (!(is >> z.x)) return is;
204 if (c != ',') is.putback(c);
208 if (!(is >> z.y)) return is;
210 if (c != ')') is.putback(c);
217 ///Write a plainvector to a stream
219 ///Write a plainvector to a stream.
223 inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
225 os << "(" << z.x << ", " << z.y << ")";
229 ///Rotate by 90 degrees
231 ///Returns the parameter rotated by 90 degrees in positive direction.
235 inline Point<T> rot90(const Point<T> &z)
237 return Point<T>(-z.y,z.x);
240 ///Rotate by 180 degrees
242 ///Returns the parameter rotated by 180 degrees.
246 inline Point<T> rot180(const Point<T> &z)
248 return Point<T>(-z.x,-z.y);
251 ///Rotate by 270 degrees
253 ///Returns the parameter rotated by 90 degrees in negative direction.
257 inline Point<T> rot270(const Point<T> &z)
259 return Point<T>(z.y,-z.x);
264 /// A class to calculate or store the bounding box of plainvectors.
266 /// A class to calculate or store the bounding box of plainvectors.
270 Point<T> bottom_left, top_right;
274 ///Default constructor: creates an empty bounding box
275 BoundingBox() { _empty = true; }
277 ///Construct an instance from one point
278 BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
280 ///Construct an instance from two points
282 ///Construct an instance from two points.
283 ///\param a The bottom left corner.
284 ///\param b The top right corner.
285 ///\warning The coordinates of the bottom left corner must be no more
286 ///than those of the top right one.
287 BoundingBox(Point<T> a,Point<T> b)
294 ///Construct an instance from four numbers
296 ///Construct an instance from four numbers.
297 ///\param l The left side of the box.
298 ///\param b The bottom of the box.
299 ///\param r The right side of the box.
300 ///\param t The top of the box.
301 ///\warning The left side must be no more than the right side and
302 ///bottom must be no more than the top.
303 BoundingBox(T l,T b,T r,T t)
305 bottom_left=Point<T>(l,b);
306 top_right=Point<T>(r,t);
310 ///Return \c true if the bounding box is empty.
312 ///Return \c true if the bounding box is empty (i.e. return \c false
313 ///if at least one point was added to the box or the coordinates of
314 ///the box were set).
316 ///The coordinates of an empty bounding box are not defined.
321 ///Make the BoundingBox empty
326 ///Give back the bottom left corner of the box
328 ///Give back the bottom left corner of the box.
329 ///If the bounding box is empty, then the return value is not defined.
330 Point<T> bottomLeft() const {
334 ///Set the bottom left corner of the box
336 ///Set the bottom left corner of the box.
337 ///It should only be used for non-empty box.
338 void bottomLeft(Point<T> p) {
342 ///Give back the top right corner of the box
344 ///Give back the top right corner of the box.
345 ///If the bounding box is empty, then the return value is not defined.
346 Point<T> topRight() const {
350 ///Set the top right corner of the box
352 ///Set the top right corner of the box.
353 ///It should only be used for non-empty box.
354 void topRight(Point<T> p) {
358 ///Give back the bottom right corner of the box
360 ///Give back the bottom right corner of the box.
361 ///If the bounding box is empty, then the return value is not defined.
362 Point<T> bottomRight() const {
363 return Point<T>(top_right.x,bottom_left.y);
366 ///Set the bottom right corner of the box
368 ///Set the bottom right corner of the box.
369 ///It should only be used for non-empty box.
370 void bottomRight(Point<T> p) {
375 ///Give back the top left corner of the box
377 ///Give back the top left corner of the box.
378 ///If the bounding box is empty, then the return value is not defined.
379 Point<T> topLeft() const {
380 return Point<T>(bottom_left.x,top_right.y);
383 ///Set the top left corner of the box
385 ///Set the top left corner of the box.
386 ///It should only be used for non-empty box.
387 void topLeft(Point<T> p) {
392 ///Give back the bottom of the box
394 ///Give back the bottom of the box.
395 ///If the bounding box is empty, then the return value is not defined.
397 return bottom_left.y;
400 ///Set the bottom of the box
402 ///Set the bottom of the box.
403 ///It should only be used for non-empty box.
408 ///Give back the top of the box
410 ///Give back the top of the box.
411 ///If the bounding box is empty, then the return value is not defined.
416 ///Set the top of the box
418 ///Set the top of the box.
419 ///It should only be used for non-empty box.
424 ///Give back the left side of the box
426 ///Give back the left side of the box.
427 ///If the bounding box is empty, then the return value is not defined.
429 return bottom_left.x;
432 ///Set the left side of the box
434 ///Set the left side of the box.
435 ///It should only be used for non-empty box.
440 /// Give back the right side of the box
442 /// Give back the right side of the box.
443 ///If the bounding box is empty, then the return value is not defined.
448 ///Set the right side of the box
450 ///Set the right side of the box.
451 ///It should only be used for non-empty box.
456 ///Give back the height of the box
458 ///Give back the height of the box.
459 ///If the bounding box is empty, then the return value is not defined.
461 return top_right.y-bottom_left.y;
464 ///Give back the width of the box
466 ///Give back the width of the box.
467 ///If the bounding box is empty, then the return value is not defined.
469 return top_right.x-bottom_left.x;
472 ///Checks whether a point is inside a bounding box
473 bool inside(const Point<T>& u) const {
477 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
478 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
482 ///Increments a bounding box with a point
484 ///Increments a bounding box with a point.
486 BoundingBox& add(const Point<T>& u){
488 bottom_left=top_right=u;
492 if (bottom_left.x > u.x) bottom_left.x = u.x;
493 if (bottom_left.y > u.y) bottom_left.y = u.y;
494 if (top_right.x < u.x) top_right.x = u.x;
495 if (top_right.y < u.y) top_right.y = u.y;
500 ///Increments a bounding box to contain another bounding box
502 ///Increments a bounding box to contain another bounding box.
504 BoundingBox& add(const BoundingBox &u){
506 this->add(u.bottomLeft());
507 this->add(u.topRight());
512 ///Intersection of two bounding boxes
514 ///Intersection of two bounding boxes.
516 BoundingBox operator&(const BoundingBox& u) const {
518 if (this->_empty || u._empty) {
521 b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
522 b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
523 b.top_right.x = std::min(this->top_right.x,u.top_right.x);
524 b.top_right.y = std::min(this->top_right.y,u.top_right.y);
525 b._empty = b.bottom_left.x > b.top_right.x ||
526 b.bottom_left.y > b.top_right.y;
531 };//class Boundingbox
534 ///Map of x-coordinates of a \ref Point "Point"-map
537 ///Map of x-coordinates of a \ref Point "Point"-map.
545 typedef typename M::Value::Value Value;
546 typedef typename M::Key Key;
548 XMap(M& map) : _map(map) {}
549 Value operator[](Key k) const {return _map[k].x;}
550 void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
553 ///Returns an \ref XMap class
555 ///This function just returns an \ref XMap class.
560 inline XMap<M> xMap(M &m)
566 inline XMap<M> xMap(const M &m)
571 ///Constant (read only) version of \ref XMap
574 ///Constant (read only) version of \ref XMap
582 typedef typename M::Value::Value Value;
583 typedef typename M::Key Key;
585 ConstXMap(const M &map) : _map(map) {}
586 Value operator[](Key k) const {return _map[k].x;}
589 ///Returns a \ref ConstXMap class
591 ///This function just returns a \ref ConstXMap class.
594 ///\relates ConstXMap
596 inline ConstXMap<M> xMap(const M &m)
598 return ConstXMap<M>(m);
601 ///Map of y-coordinates of a \ref Point "Point"-map
604 ///Map of y-coordinates of a \ref Point "Point"-map.
612 typedef typename M::Value::Value Value;
613 typedef typename M::Key Key;
615 YMap(M& map) : _map(map) {}
616 Value operator[](Key k) const {return _map[k].y;}
617 void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
620 ///Returns a \ref YMap class
622 ///This function just returns a \ref YMap class.
627 inline YMap<M> yMap(M &m)
633 inline YMap<M> yMap(const M &m)
638 ///Constant (read only) version of \ref YMap
641 ///Constant (read only) version of \ref YMap
649 typedef typename M::Value::Value Value;
650 typedef typename M::Key Key;
652 ConstYMap(const M &map) : _map(map) {}
653 Value operator[](Key k) const {return _map[k].y;}
656 ///Returns a \ref ConstYMap class
658 ///This function just returns a \ref ConstYMap class.
661 ///\relates ConstYMap
663 inline ConstYMap<M> yMap(const M &m)
665 return ConstYMap<M>(m);
669 ///\brief Map of the \ref Point::normSquare() "normSquare()"
670 ///of a \ref Point "Point"-map
672 ///Map of the \ref Point::normSquare() "normSquare()"
673 ///of a \ref Point "Point"-map.
681 typedef typename M::Value::Value Value;
682 typedef typename M::Key Key;
684 NormSquareMap(const M &map) : _map(map) {}
685 Value operator[](Key k) const {return _map[k].normSquare();}
688 ///Returns a \ref NormSquareMap class
690 ///This function just returns a \ref NormSquareMap class.
693 ///\relates NormSquareMap
695 inline NormSquareMap<M> normSquareMap(const M &m)
697 return NormSquareMap<M>(m);
706 #endif //LEMON_DIM2_H