Minor doc fixes.
Replaced \c by \ref and \ref by \c to work properly and to be uniform.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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/bits/utility.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
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.
40 ///Tools for handling two dimensional coordinates
42 ///This namespace is a storage of several
43 ///tools for handling two dimensional coordinates
49 /// A simple two dimensional vector (plainvector) implementation
51 /// A simple two dimensional vector (plainvector) implementation
52 ///with the usual vector
67 ///Default constructor
70 ///Construct an instance from coordinates
71 Point(T a, T b) : x(a), y(b) { }
73 ///The dimension of the vector.
75 ///The dimension of the vector.
76 ///This function always returns 2.
77 int size() const { return 2; }
79 ///Subscripting operator
81 ///\c p[0] is \c p.x and \c p[1] is \c p.y
83 T& operator[](int idx) { return idx == 0 ? x : y; }
85 ///Const subscripting operator
87 ///\c p[0] is \c p.x and \c p[1] is \c p.y
89 const T& operator[](int idx) const { return idx == 0 ? x : y; }
91 ///Conversion constructor
92 template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
94 ///Give back the square of the norm of the vector
95 T normSquare() const {
99 ///Increment the left hand side by u
100 Point<T>& operator +=(const Point<T>& u) {
106 ///Decrement the left hand side by u
107 Point<T>& operator -=(const Point<T>& u) {
113 ///Multiply the left hand side with a scalar
114 Point<T>& operator *=(const T &u) {
120 ///Divide the left hand side by a scalar
121 Point<T>& operator /=(const T &u) {
127 ///Return the scalar product of two vectors
128 T operator *(const Point<T>& u) const {
132 ///Return the sum of two vectors
133 Point<T> operator+(const Point<T> &u) const {
138 ///Return the negative of the vector
139 Point<T> operator-() const {
145 ///Return the difference of two vectors
146 Point<T> operator-(const Point<T> &u) const {
151 ///Return a vector multiplied by a scalar
152 Point<T> operator*(const T &u) const {
157 ///Return a vector divided by a scalar
158 Point<T> operator/(const T &u) const {
164 bool operator==(const Point<T> &u) const {
165 return (x==u.x) && (y==u.y);
169 bool operator!=(Point u) const {
170 return (x!=u.x) || (y!=u.y);
179 template <typename T>
180 inline Point<T> makePoint(const T& x, const T& y) {
181 return Point<T>(x, y);
184 ///Return a vector multiplied by a scalar
186 ///Return a vector multiplied by a scalar.
188 template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
192 ///Read a plainvector from a stream
194 ///Read a plainvector from a stream.
198 inline std::istream& operator>>(std::istream &is, Point<T> &z) {
201 if (c != '(') is.putback(c);
205 if (!(is >> z.x)) return is;
207 if (c != ',') is.putback(c);
211 if (!(is >> z.y)) return is;
213 if (c != ')') is.putback(c);
220 ///Write a plainvector to a stream
222 ///Write a plainvector to a stream.
226 inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
228 os << "(" << z.x << ", " << z.y << ")";
232 ///Rotate by 90 degrees
234 ///Returns the parameter rotated by 90 degrees in positive direction.
238 inline Point<T> rot90(const Point<T> &z)
240 return Point<T>(-z.y,z.x);
243 ///Rotate by 180 degrees
245 ///Returns the parameter rotated by 180 degrees.
249 inline Point<T> rot180(const Point<T> &z)
251 return Point<T>(-z.x,-z.y);
254 ///Rotate by 270 degrees
256 ///Returns the parameter rotated by 90 degrees in negative direction.
260 inline Point<T> rot270(const Point<T> &z)
262 return Point<T>(z.y,-z.x);
267 /// A class to calculate or store the bounding box of plainvectors.
269 /// A class to calculate or store the bounding box of plainvectors.
273 Point<T> bottom_left, top_right;
277 ///Default constructor: creates an empty bounding box
278 BoundingBox() { _empty = true; }
280 ///Construct an instance from one point
281 BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
283 ///Construct an instance from two points
285 ///Construct an instance from two points.
286 ///\param a The bottom left corner.
287 ///\param b The top right corner.
288 ///\warning The coordinates of the bottom left corner must be no more
289 ///than those of the top right one.
290 BoundingBox(Point<T> a,Point<T> b)
297 ///Construct an instance from four numbers
299 ///Construct an instance from four numbers.
300 ///\param l The left side of the box.
301 ///\param b The bottom of the box.
302 ///\param r The right side of the box.
303 ///\param t The top of the box.
304 ///\warning The left side must be no more than the right side and
305 ///bottom must be no more than the top.
306 BoundingBox(T l,T b,T r,T t)
308 bottom_left=Point<T>(l,b);
309 top_right=Point<T>(r,t);
313 ///Return \c true if the bounding box is empty.
315 ///Return \c true if the bounding box is empty (i.e. return \c false
316 ///if at least one point was added to the box or the coordinates of
317 ///the box were set).
318 ///The coordinates of an empty bounding box are not defined.
323 ///Make the BoundingBox empty
328 ///Give back the bottom left corner
330 ///Give back the bottom left corner.
331 ///If the bounding box is empty, then the return value is not defined.
332 Point<T> bottomLeft() const {
336 ///Set the bottom left corner
338 ///Set the bottom left corner.
339 ///It should only be used for non-empty box.
340 void bottomLeft(Point<T> p) {
344 ///Give back the top right corner
346 ///Give back the top right corner.
347 ///If the bounding box is empty, then the return value is not defined.
348 Point<T> topRight() const {
352 ///Set the top right corner
354 ///Set the top right corner.
355 ///It should only be used for non-empty box.
356 void topRight(Point<T> p) {
360 ///Give back the bottom right corner
362 ///Give back the bottom right corner.
363 ///If the bounding box is empty, then the return value is not defined.
364 Point<T> bottomRight() const {
365 return Point<T>(top_right.x,bottom_left.y);
368 ///Set the bottom right corner
370 ///Set the bottom right corner.
371 ///It should only be used for non-empty box.
372 void bottomRight(Point<T> p) {
377 ///Give back the top left corner
379 ///Give back the top left corner.
380 ///If the bounding box is empty, then the return value is not defined.
381 Point<T> topLeft() const {
382 return Point<T>(bottom_left.x,top_right.y);
385 ///Set the top left corner
387 ///Set the top left corner.
388 ///It should only be used for non-empty box.
389 void topLeft(Point<T> p) {
394 ///Give back the bottom of the box
396 ///Give back the bottom of the box.
397 ///If the bounding box is empty, then the return value is not defined.
399 return bottom_left.y;
402 ///Set the bottom of the box
404 ///Set the bottom of the box.
405 ///It should only be used for non-empty box.
410 ///Give back the top of the box
412 ///Give back the top of the box.
413 ///If the bounding box is empty, then the return value is not defined.
418 ///Set the top of the box
420 ///Set the top of the box.
421 ///It should only be used for non-empty box.
426 ///Give back the left side of the box
428 ///Give back the left side of the box.
429 ///If the bounding box is empty, then the return value is not defined.
431 return bottom_left.x;
434 ///Set the left side of the box
436 ///Set the left side of the box.
437 ///It should only be used for non-empty box.
442 /// Give back the right side of the box
444 /// Give back the right side of the box.
445 ///If the bounding box is empty, then the return value is not defined.
450 ///Set the right side of the box
452 ///Set the right side of the box.
453 ///It should only be used for non-empty box.
458 ///Give back the height of the box
460 ///Give back the height of the box.
461 ///If the bounding box is empty, then the return value is not defined.
463 return top_right.y-bottom_left.y;
466 ///Give back the width of the box
468 ///Give back the width of the box.
469 ///If the bounding box is empty, then the return value is not defined.
471 return top_right.x-bottom_left.x;
474 ///Checks whether a point is inside a bounding box
475 bool inside(const Point<T>& u) const {
479 return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
480 (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
484 ///Increments a bounding box with a point
486 ///Increments a bounding box with a point.
488 BoundingBox& add(const Point<T>& u){
490 bottom_left=top_right=u;
494 if (bottom_left.x > u.x) bottom_left.x = u.x;
495 if (bottom_left.y > u.y) bottom_left.y = u.y;
496 if (top_right.x < u.x) top_right.x = u.x;
497 if (top_right.y < u.y) top_right.y = u.y;
502 ///Increments a bounding box to contain another bounding box
504 ///Increments a bounding box to contain another bounding box.
506 BoundingBox& add(const BoundingBox &u){
508 this->add(u.bottomLeft());
509 this->add(u.topRight());
514 ///Intersection of two bounding boxes
516 ///Intersection of two bounding boxes.
518 BoundingBox operator&(const BoundingBox& u) const {
520 if (this->_empty || u._empty) {
523 b.bottom_left.x = std::max(this->bottom_left.x,u.bottom_left.x);
524 b.bottom_left.y = std::max(this->bottom_left.y,u.bottom_left.y);
525 b.top_right.x = std::min(this->top_right.x,u.top_right.x);
526 b.top_right.y = std::min(this->top_right.y,u.top_right.y);
527 b._empty = b.bottom_left.x > b.top_right.x ||
528 b.bottom_left.y > b.top_right.y;
533 };//class Boundingbox
536 ///Map of x-coordinates of a \ref Point "Point"-map
539 ///Map of x-coordinates of a \ref Point "Point"-map.
547 typedef typename M::Value::Value Value;
548 typedef typename M::Key Key;
550 XMap(M& map) : _map(map) {}
551 Value operator[](Key k) const {return _map[k].x;}
552 void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
555 ///Returns an \ref XMap class
557 ///This function just returns an \ref XMap class.
562 inline XMap<M> xMap(M &m)
568 inline XMap<M> xMap(const M &m)
573 ///Constant (read only) version of \ref XMap
576 ///Constant (read only) version of \ref XMap
584 typedef typename M::Value::Value Value;
585 typedef typename M::Key Key;
587 ConstXMap(const M &map) : _map(map) {}
588 Value operator[](Key k) const {return _map[k].x;}
591 ///Returns a \ref ConstXMap class
593 ///This function just returns a \ref ConstXMap class.
596 ///\relates ConstXMap
598 inline ConstXMap<M> xMap(const M &m)
600 return ConstXMap<M>(m);
603 ///Map of y-coordinates of a \ref Point "Point"-map
606 ///Map of y-coordinates of a \ref Point "Point"-map.
614 typedef typename M::Value::Value Value;
615 typedef typename M::Key Key;
617 YMap(M& map) : _map(map) {}
618 Value operator[](Key k) const {return _map[k].y;}
619 void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
622 ///Returns a \ref YMap class
624 ///This function just returns a \ref YMap class.
629 inline YMap<M> yMap(M &m)
635 inline YMap<M> yMap(const M &m)
640 ///Constant (read only) version of \ref YMap
643 ///Constant (read only) version of \ref YMap
651 typedef typename M::Value::Value Value;
652 typedef typename M::Key Key;
654 ConstYMap(const M &map) : _map(map) {}
655 Value operator[](Key k) const {return _map[k].y;}
658 ///Returns a \ref ConstYMap class
660 ///This function just returns a \ref ConstYMap class.
663 ///\relates ConstYMap
665 inline ConstYMap<M> yMap(const M &m)
667 return ConstYMap<M>(m);
671 ///\brief Map of the \ref Point::normSquare() "normSquare()"
672 ///of a \ref Point "Point"-map
674 ///Map of the \ref Point::normSquare() "normSquare()"
675 ///of a \ref Point "Point"-map.
684 typedef typename M::Value::Value Value;
685 typedef typename M::Key Key;
687 NormSquareMap(const M &map) : _map(map) {}
688 Value operator[](Key k) const {return _map[k].normSquare();}
691 ///Returns a \ref NormSquareMap class
693 ///This function just returns a \ref NormSquareMap class.
696 ///\relates NormSquareMap
698 inline NormSquareMap<M> normSquareMap(const M &m)
700 return NormSquareMap<M>(m);
709 #endif //LEMON_DIM2_H