# HG changeset patch # User Alpar Juttner # Date 2007-12-20 17:11:56 # Node ID a1b1d672f37ab7fae62c884061fffeed9ad245bd # Parent 4d461e9867da55e340da4353b59a73b1a1875451 Port dim2.h from svn -r3422 diff --git a/lemon/Makefile.am b/lemon/Makefile.am --- a/lemon/Makefile.am +++ b/lemon/Makefile.am @@ -13,6 +13,7 @@ lemon_libemon_la_LDFLAGS = $(GLPK_LIBS) $(CPLEX_LIBS) $(SOPLEX_LIBS) lemon_HEADERS += \ + lemon/dim2.h \ lemon/list_graph.h \ lemon/tolerance.h diff --git a/lemon/dim2.h b/lemon/dim2.h new file mode 100644 --- /dev/null +++ b/lemon/dim2.h @@ -0,0 +1,689 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_DIM2_H +#define LEMON_DIM2_H + +#include +#include + +///\ingroup misc +///\file +///\brief A simple two dimensional vector and a bounding box implementation +/// +/// The class \ref lemon::dim2::Point "dim2::Point" implements +///a two dimensional vector with the usual +/// operations. +/// +/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" +/// can be used to determine +/// the rectangular bounding box of a set of +/// \ref lemon::dim2::Point "dim2::Point"'s. +/// +///\author Attila Bernath + + +namespace lemon { + + ///Tools for handling two dimensional coordinates + + ///This namespace is a storage of several + ///tools for handling two dimensional coordinates + namespace dim2 { + + /// \addtogroup misc + /// @{ + + /// A simple two dimensional vector (plainvector) implementation + + /// A simple two dimensional vector (plainvector) implementation + ///with the usual vector + /// operators. + /// + template + class Point { + + public: + + typedef T Value; + + ///First co-ordinate + T x; + ///Second co-ordinate + T y; + + ///Default constructor + Point() {} + + ///Construct an instance from coordinates + Point(T a, T b) : x(a), y(b) { } + + ///The dimension of the vector. + + ///This class give back always 2. + /// + int size() const { return 2; } + + ///Subscripting operator + + ///\c p[0] is \c p.x and \c p[1] is \c p.y + /// + T& operator[](int idx) { return idx == 0 ? x : y; } + + ///Const subscripting operator + + ///\c p[0] is \c p.x and \c p[1] is \c p.y + /// + const T& operator[](int idx) const { return idx == 0 ? x : y; } + + ///Conversion constructor + template Point(const Point &p) : x(p.x), y(p.y) {} + + ///Give back the square of the norm of the vector + T normSquare() const { + return x*x+y*y; + } + + ///Increment the left hand side by u + Point& operator +=(const Point& u) { + x += u.x; + y += u.y; + return *this; + } + + ///Decrement the left hand side by u + Point& operator -=(const Point& u) { + x -= u.x; + y -= u.y; + return *this; + } + + ///Multiply the left hand side with a scalar + Point& operator *=(const T &u) { + x *= u; + y *= u; + return *this; + } + + ///Divide the left hand side by a scalar + Point& operator /=(const T &u) { + x /= u; + y /= u; + return *this; + } + + ///Return the scalar product of two vectors + T operator *(const Point& u) const { + return x*u.x+y*u.y; + } + + ///Return the sum of two vectors + Point operator+(const Point &u) const { + Point b=*this; + return b+=u; + } + + ///Return the neg of the vectors + Point operator-() const { + Point b=*this; + b.x=-b.x; b.y=-b.y; + return b; + } + + ///Return the difference of two vectors + Point operator-(const Point &u) const { + Point b=*this; + return b-=u; + } + + ///Return a vector multiplied by a scalar + Point operator*(const T &u) const { + Point b=*this; + return b*=u; + } + + ///Return a vector divided by a scalar + Point operator/(const T &u) const { + Point b=*this; + return b/=u; + } + + ///Test equality + bool operator==(const Point &u) const { + return (x==u.x) && (y==u.y); + } + + ///Test inequality + bool operator!=(Point u) const { + return (x!=u.x) || (y!=u.y); + } + + }; + + ///Return an Point + + ///Return an Point + ///\relates Point + template + inline Point makePoint(const T& x, const T& y) { + return Point(x, y); + } + + ///Return a vector multiplied by a scalar + + ///Return a vector multiplied by a scalar + ///\relates Point + template Point operator*(const T &u,const Point &x) { + return x*u; + } + + ///Read a plainvector from a stream + + ///Read a plainvector from a stream + ///\relates Point + /// + template + inline std::istream& operator>>(std::istream &is, Point &z) { + char c; + if (is >> c) { + if (c != '(') is.putback(c); + } else { + is.clear(); + } + if (!(is >> z.x)) return is; + if (is >> c) { + if (c != ',') is.putback(c); + } else { + is.clear(); + } + if (!(is >> z.y)) return is; + if (is >> c) { + if (c != ')') is.putback(c); + } else { + is.clear(); + } + return is; + } + + ///Write a plainvector to a stream + + ///Write a plainvector to a stream + ///\relates Point + /// + template + inline std::ostream& operator<<(std::ostream &os, const Point& z) + { + os << "(" << z.x << ", " << z.y << ")"; + return os; + } + + ///Rotate by 90 degrees + + ///Returns its parameter rotated by 90 degrees in positive direction. + ///\relates Point + /// + template + inline Point rot90(const Point &z) + { + return Point(-z.y,z.x); + } + + ///Rotate by 180 degrees + + ///Returns its parameter rotated by 180 degrees. + ///\relates Point + /// + template + inline Point rot180(const Point &z) + { + return Point(-z.x,-z.y); + } + + ///Rotate by 270 degrees + + ///Returns its parameter rotated by 90 degrees in negative direction. + ///\relates Point + /// + template + inline Point rot270(const Point &z) + { + return Point(z.y,-z.x); + } + + + + /// A class to calculate or store the bounding box of plainvectors. + + /// A class to calculate or store the bounding box of plainvectors. + /// + ///\author Attila Bernath + template + class BoundingBox { + Point bottom_left, top_right; + bool _empty; + public: + + ///Default constructor: creates an empty bounding box + BoundingBox() { _empty = true; } + + ///Construct an instance from one point + BoundingBox(Point a) { bottom_left=top_right=a; _empty = false; } + + ///Construct an instance from two points + + ///Construct an instance from two points + ///\warning The coordinates of the bottom-left corner must be no more + ///than those of the top-right one + BoundingBox(Point a,Point b) + { + bottom_left=a; + top_right=b; + _empty = false; + } + + ///Construct an instance from four numbers + + ///Construct an instance from four numbers + ///\warning The coordinates of the bottom-left corner must be no more + ///than those of the top-right one + BoundingBox(T l,T b,T r,T t) + { + bottom_left=Point(l,b); + top_right=Point(r,t); + _empty = false; + } + + ///Were any points added? + bool empty() const { + return _empty; + } + + ///Make the BoundingBox empty + void clear() { + _empty=1; + } + + ///Give back the bottom left corner + + ///Give back the bottom left corner. + ///If the bounding box is empty, then the return value is not defined. + Point bottomLeft() const { + return bottom_left; + } + + ///Set the bottom left corner + + ///Set the bottom left corner. + ///It should only bee used for non-empty box. + void bottomLeft(Point p) { + bottom_left = p; + } + + ///Give back the top right corner + + ///Give back the top right corner. + ///If the bounding box is empty, then the return value is not defined. + Point topRight() const { + return top_right; + } + + ///Set the top right corner + + ///Set the top right corner. + ///It should only bee used for non-empty box. + void topRight(Point p) { + top_right = p; + } + + ///Give back the bottom right corner + + ///Give back the bottom right corner. + ///If the bounding box is empty, then the return value is not defined. + Point bottomRight() const { + return Point(top_right.x,bottom_left.y); + } + + ///Set the bottom right corner + + ///Set the bottom right corner. + ///It should only bee used for non-empty box. + void bottomRight(Point p) { + top_right.x = p.x; + bottom_left.y = p.y; + } + + ///Give back the top left corner + + ///Give back the top left corner. + ///If the bounding box is empty, then the return value is not defined. + Point topLeft() const { + return Point(bottom_left.x,top_right.y); + } + + ///Set the top left corner + + ///Set the top left corner. + ///It should only bee used for non-empty box. + void topLeft(Point p) { + top_right.y = p.y; + bottom_left.x = p.x; + } + + ///Give back the bottom of the box + + ///Give back the bottom of the box. + ///If the bounding box is empty, then the return value is not defined. + T bottom() const { + return bottom_left.y; + } + + ///Set the bottom of the box + + ///Set the bottom of the box. + ///It should only bee used for non-empty box. + void bottom(T t) { + bottom_left.y = t; + } + + ///Give back the top of the box + + ///Give back the top of the box. + ///If the bounding box is empty, then the return value is not defined. + T top() const { + return top_right.y; + } + + ///Set the top of the box + + ///Set the top of the box. + ///It should only bee used for non-empty box. + void top(T t) { + top_right.y = t; + } + + ///Give back the left side of the box + + ///Give back the left side of the box. + ///If the bounding box is empty, then the return value is not defined. + T left() const { + return bottom_left.x; + } + + ///Set the left side of the box + + ///Set the left side of the box. + ///It should only bee used for non-empty box + void left(T t) { + bottom_left.x = t; + } + + /// Give back the right side of the box + + /// Give back the right side of the box. + ///If the bounding box is empty, then the return value is not defined. + T right() const { + return top_right.x; + } + + ///Set the right side of the box + + ///Set the right side of the box. + ///It should only bee used for non-empty box + void right(T t) { + top_right.x = t; + } + + ///Give back the height of the box + + ///Give back the height of the box. + ///If the bounding box is empty, then the return value is not defined. + T height() const { + return top_right.y-bottom_left.y; + } + + ///Give back the width of the box + + ///Give back the width of the box. + ///If the bounding box is empty, then the return value is not defined. + T width() const { + return top_right.x-bottom_left.x; + } + + ///Checks whether a point is inside a bounding box + bool inside(const Point& u){ + if (_empty) + return false; + else{ + return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 && + (u.y-bottom_left.y)*(top_right.y-u.y) >= 0 ); + } + } + + ///Increments a bounding box with a point + BoundingBox& add(const Point& u){ + if (_empty){ + bottom_left=top_right=u; + _empty = false; + } + else{ + if (bottom_left.x > u.x) bottom_left.x = u.x; + if (bottom_left.y > u.y) bottom_left.y = u.y; + if (top_right.x < u.x) top_right.x = u.x; + if (top_right.y < u.y) top_right.y = u.y; + } + return *this; + } + + ///Increments a bounding to contain another bounding box + BoundingBox& add(const BoundingBox &u){ + if ( !u.empty() ){ + this->add(u.bottomLeft()); + this->add(u.topRight()); + } + return *this; + } + + ///Intersection of two bounding boxes + BoundingBox operator &(const BoundingBox& u){ + BoundingBox b; + b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x); + b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y); + b.top_right.x=std::min(this->top_right.x,u.top_right.x); + b.top_right.y=std::min(this->top_right.y,u.top_right.y); + b._empty = this->_empty || u._empty || + b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y; + return b; + } + + };//class Boundingbox + + + ///Map of x-coordinates of a dim2::Point<>-map + + ///\ingroup maps + ///Map of x-coordinates of a dim2::Point<>-map + /// + template + class XMap + { + M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + XMap(M& map) : _map(map) {} + Value operator[](Key k) const {return _map[k].x;} + void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));} + }; + + ///Returns an \ref XMap class + + ///This function just returns an \ref XMap class. + /// + ///\ingroup maps + ///\relates XMap + template + inline XMap xMap(M &m) + { + return XMap(m); + } + + template + inline XMap xMap(const M &m) + { + return XMap(m); + } + + ///Constant (read only) version of \ref XMap + + ///\ingroup maps + ///Constant (read only) version of \ref XMap + /// + template + class ConstXMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + ConstXMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].x;} + }; + + ///Returns a \ref ConstXMap class + + ///This function just returns an \ref ConstXMap class. + /// + ///\ingroup maps + ///\relates ConstXMap + template + inline ConstXMap xMap(const M &m) + { + return ConstXMap(m); + } + + ///Map of y-coordinates of a dim2::Point<>-map + + ///\ingroup maps + ///Map of y-coordinates of a dim2::Point<>-map + /// + template + class YMap + { + M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + YMap(M& map) : _map(map) {} + Value operator[](Key k) const {return _map[k].y;} + void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));} + }; + + ///Returns an \ref YMap class + + ///This function just returns an \ref YMap class. + /// + ///\ingroup maps + ///\relates YMap + template + inline YMap yMap(M &m) + { + return YMap(m); + } + + template + inline YMap yMap(const M &m) + { + return YMap(m); + } + + ///Constant (read only) version of \ref YMap + + ///\ingroup maps + ///Constant (read only) version of \ref YMap + /// + template + class ConstYMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + ConstYMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].y;} + }; + + ///Returns a \ref ConstYMap class + + ///This function just returns an \ref ConstYMap class. + /// + ///\ingroup maps + ///\relates ConstYMap + template + inline ConstYMap yMap(const M &m) + { + return ConstYMap(m); + } + + + ///\brief Map of the \ref Point::normSquare() "normSquare()" + ///of an \ref Point "Point"-map + /// + ///Map of the \ref Point::normSquare() "normSquare()" + ///of an \ref Point "Point"-map + ///\ingroup maps + /// + template + class NormSquareMap + { + const M& _map; + public: + + typedef typename M::Value::Value Value; + typedef typename M::Key Key; + ///\e + NormSquareMap(const M &map) : _map(map) {} + Value operator[](Key k) const {return _map[k].normSquare();} + }; + + ///Returns a \ref NormSquareMap class + + ///This function just returns an \ref NormSquareMap class. + /// + ///\ingroup maps + ///\relates NormSquareMap + template + inline NormSquareMap normSquareMap(const M &m) + { + return NormSquareMap(m); + } + + /// @} + + } //namespce dim2 + +} //namespace lemon + +#endif //LEMON_DIM2_H diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -5,11 +5,13 @@ test/test_tools.h check_PROGRAMS += \ + test/dim_test \ test/test_tools_fail \ test/test_tools_pass TESTS += $(check_PROGRAMS) XFAIL_TESTS += test/test_tools_fail$(EXEEXT) +test_dim_test_SOURCES = test/dim_test.cc test_test_tools_fail_SOURCES = test/test_tools_fail.cc test_test_tools_pass_SOURCES = test/test_tools_pass.cc diff --git a/test/dim_test.cc b/test/dim_test.cc new file mode 100644 --- /dev/null +++ b/test/dim_test.cc @@ -0,0 +1,86 @@ +/* -*- C++ -*- + * + * This file is a part of LEMON, a generic C++ optimization library + * + * Copyright (C) 2003-2007 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include +#include "test_tools.h" + +using namespace std; +using namespace lemon; +int main() +{ + + cout << "Testing classes `dim2::Point' and `dim2::BoundingBox'." << endl; + + typedef dim2::Point Point; + + Point seged; + check(seged.size()==2, "Wrong vector addition"); + + Point a(1,2); + Point b(3,4); + + check(a[0]==1 && a[1]==2, "Wrong vector addition"); + + seged = a+b; + check(seged.x==4 && seged.y==6, "Wrong vector addition"); + + seged = a-b; + check(seged.x==-2 && seged.y==-2, "a-b"); + + check(a.normSquare()==5,"Wrong norm calculation"); + check(a*b==11, "a*b"); + + int l=2; + seged = a*l; + check(seged.x==2 && seged.y==4, "a*l"); + + seged = b/l; + check(seged.x==1 && seged.y==2, "b/l"); + + typedef dim2::BoundingBox BB; + BB doboz1; + check(doboz1.empty(), "It should be empty."); + + doboz1.add(a); + check(!doboz1.empty(), "It should not be empty."); + doboz1.add(b); + + check(doboz1.bottomLeft().x==1 && + doboz1.bottomLeft().y==2 && + doboz1.topRight().x==3 && + doboz1.topRight().y==4, + "added points to box"); + + seged.x=2;seged.y=3; + check(doboz1.inside(seged),"It should be inside."); + + seged.x=1;seged.y=3; + check(doboz1.inside(seged),"It should be inside."); + + seged.x=0;seged.y=3; + check(!doboz1.inside(seged),"It should not be inside."); + + BB doboz2(seged); + check(!doboz2.empty(), + "It should not be empty. Constructed from 1 point."); + + doboz2.add(doboz1); + check(doboz2.inside(seged), + "It should be inside. Incremented a box with another one."); +}