/* Generator class declaration. Copyright (C) 2001-2010 Roberto Bagnara Copyright (C) 2010-2011 BUGSENG srl (http://bugseng.com) This file is part of the Parma Polyhedra Library (PPL). The PPL is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. The PPL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. For the most up-to-date information see the Parma Polyhedra Library site: http://www.cs.unipr.it/ppl/ . */ #ifndef PPL_Generator_defs_hh #define PPL_Generator_defs_hh 1 #include "Generator.types.hh" #include "Scalar_Products.types.hh" #include "Row.defs.hh" #include "Variable.defs.hh" #include "Constraint_System.types.hh" #include "Generator_System.defs.hh" #include "Congruence_System.types.hh" #include "Linear_Expression.defs.hh" #include "Polyhedron.types.hh" #include "Grid_Generator.types.hh" #include "Grid_Generator_System.types.hh" #include "Checked_Number.defs.hh" #include "distances.defs.hh" #include namespace Parma_Polyhedra_Library { // Put them in the namespace here to declare them friend later. namespace IO_Operators { //! Output operator. /*! \relates Parma_Polyhedra_Library::Generator */ std::ostream& operator<<(std::ostream& s, const Generator& g); } // namespace IO_Operators } // namespace Parma_Polyhedra_Library namespace std { //! Specializes std::swap. /*! \relates Parma_Polyhedra_Library::Generator */ void swap(Parma_Polyhedra_Library::Generator& x, Parma_Polyhedra_Library::Generator& y); } // namespace std //! A line, ray, point or closure point. /*! \ingroup PPL_CXX_interface An object of the class Generator is one of the following: - a line \f$\vect{l} = (a_0, \ldots, a_{n-1})^\transpose\f$; - a ray \f$\vect{r} = (a_0, \ldots, a_{n-1})^\transpose\f$; - a point \f$\vect{p} = (\frac{a_0}{d}, \ldots, \frac{a_{n-1}}{d})^\transpose\f$; - a closure point \f$\vect{c} = (\frac{a_0}{d}, \ldots, \frac{a_{n-1}}{d})^\transpose\f$; where \f$n\f$ is the dimension of the space and, for points and closure points, \f$d > 0\f$ is the divisor. \par A note on terminology. As observed in Section \ref representation, there are cases when, in order to represent a polyhedron \f$\cP\f$ using the generator system \f$\cG = (L, R, P, C)\f$, we need to include in the finite set \f$P\f$ even points of \f$\cP\f$ that are not vertices of \f$\cP\f$. This situation is even more frequent when working with NNC polyhedra and it is the reason why we prefer to use the word `point' where other libraries use the word `vertex'. \par How to build a generator. Each type of generator is built by applying the corresponding function (line, ray, point or closure_point) to a linear expression, representing a direction in the space; the space dimension of the generator is defined as the space dimension of the corresponding linear expression. Linear expressions used to define a generator should be homogeneous (any constant term will be simply ignored). When defining points and closure points, an optional Coefficient argument can be used as a common divisor for all the coefficients occurring in the provided linear expression; the default value for this argument is 1. \par In all the following examples it is assumed that variables x, y and z are defined as follows: \code Variable x(0); Variable y(1); Variable z(2); \endcode \par Example 1 The following code builds a line with direction \f$x-y-z\f$ and having space dimension \f$3\f$: \code Generator l = line(x - y - z); \endcode As mentioned above, the constant term of the linear expression is not relevant. Thus, the following code has the same effect: \code Generator l = line(x - y - z + 15); \endcode By definition, the origin of the space is not a line, so that the following code throws an exception: \code Generator l = line(0*x); \endcode \par Example 2 The following code builds a ray with the same direction as the line in Example 1: \code Generator r = ray(x - y - z); \endcode As is the case for lines, when specifying a ray the constant term of the linear expression is not relevant; also, an exception is thrown when trying to build a ray from the origin of the space. \par Example 3 The following code builds the point \f$\vect{p} = (1, 0, 2)^\transpose \in \Rset^3\f$: \code Generator p = point(1*x + 0*y + 2*z); \endcode The same effect can be obtained by using the following code: \code Generator p = point(x + 2*z); \endcode Similarly, the origin \f$\vect{0} \in \Rset^3\f$ can be defined using either one of the following lines of code: \code Generator origin3 = point(0*x + 0*y + 0*z); Generator origin3_alt = point(0*z); \endcode Note however that the following code would have defined a different point, namely \f$\vect{0} \in \Rset^2\f$: \code Generator origin2 = point(0*y); \endcode The following two lines of code both define the only point having space dimension zero, namely \f$\vect{0} \in \Rset^0\f$. In the second case we exploit the fact that the first argument of the function point is optional. \code Generator origin0 = Generator::zero_dim_point(); Generator origin0_alt = point(); \endcode \par Example 4 The point \f$\vect{p}\f$ specified in Example 3 above can also be obtained with the following code, where we provide a non-default value for the second argument of the function point (the divisor): \code Generator p = point(2*x + 0*y + 4*z, 2); \endcode Obviously, the divisor can be usefully exploited to specify points having some non-integer (but rational) coordinates. For instance, the point \f$\vect{q} = (-1.5, 3.2, 2.1)^\transpose \in \Rset^3\f$ can be specified by the following code: \code Generator q = point(-15*x + 32*y + 21*z, 10); \endcode If a zero divisor is provided, an exception is thrown. \par Example 5 Closure points are specified in the same way we defined points, but invoking their specific constructor function. For instance, the closure point \f$\vect{c} = (1, 0, 2)^\transpose \in \Rset^3\f$ is defined by \code Generator c = closure_point(1*x + 0*y + 2*z); \endcode For the particular case of the (only) closure point having space dimension zero, we can use any of the following: \code Generator closure_origin0 = Generator::zero_dim_closure_point(); Generator closure_origin0_alt = closure_point(); \endcode \par How to inspect a generator Several methods are provided to examine a generator and extract all the encoded information: its space dimension, its type and the value of its integer coefficients. \par Example 6 The following code shows how it is possible to access each single coefficient of a generator. If g1 is a point having coordinates \f$(a_0, \ldots, a_{n-1})^\transpose\f$, we construct the closure point g2 having coordinates \f$(a_0, 2 a_1, \ldots, (i+1)a_i, \ldots, n a_{n-1})^\transpose\f$. \code if (g1.is_point()) { cout << "Point g1: " << g1 << endl; Linear_Expression e; for (dimension_type i = g1.space_dimension(); i-- > 0; ) e += (i + 1) * g1.coefficient(Variable(i)) * Variable(i); Generator g2 = closure_point(e, g1.divisor()); cout << "Closure point g2: " << g2 << endl; } else cout << "Generator g1 is not a point." << endl; \endcode Therefore, for the point \code Generator g1 = point(2*x - y + 3*z, 2); \endcode we would obtain the following output: \code Point g1: p((2*A - B + 3*C)/2) Closure point g2: cp((2*A - 2*B + 9*C)/2) \endcode When working with (closure) points, be careful not to confuse the notion of coefficient with the notion of coordinate: these are equivalent only when the divisor of the (closure) point is 1. */ class Parma_Polyhedra_Library::Generator : private Linear_Row { public: //! Returns the line of direction \p e. /*! \exception std::invalid_argument Thrown if the homogeneous part of \p e represents the origin of the vector space. */ static Generator line(const Linear_Expression& e); //! Returns the ray of direction \p e. /*! \exception std::invalid_argument Thrown if the homogeneous part of \p e represents the origin of the vector space. */ static Generator ray(const Linear_Expression& e); //! Returns the point at \p e / \p d. /*! Both \p e and \p d are optional arguments, with default values Linear_Expression::zero() and Coefficient_one(), respectively. \exception std::invalid_argument Thrown if \p d is zero. */ static Generator point(const Linear_Expression& e = Linear_Expression::zero(), Coefficient_traits::const_reference d = Coefficient_one()); //! Returns the closure point at \p e / \p d. /*! Both \p e and \p d are optional arguments, with default values Linear_Expression::zero() and Coefficient_one(), respectively. \exception std::invalid_argument Thrown if \p d is zero. */ static Generator closure_point(const Linear_Expression& e = Linear_Expression::zero(), Coefficient_traits::const_reference d = Coefficient_one()); //! Ordinary copy constructor. Generator(const Generator& g); //! Destructor. ~Generator(); //! Assignment operator. Generator& operator=(const Generator& g); //! Returns the maximum space dimension a Generator can handle. static dimension_type max_space_dimension(); //! Returns the dimension of the vector space enclosing \p *this. dimension_type space_dimension() const; //! The generator type. enum Type { /*! The generator is a line. */ LINE, /*! The generator is a ray. */ RAY, /*! The generator is a point. */ POINT, /*! The generator is a closure point. */ CLOSURE_POINT }; //! Returns the generator type of \p *this. Type type() const; //! Returns true if and only if \p *this is a line. bool is_line() const; //! Returns true if and only if \p *this is a ray. bool is_ray() const; #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS //! Returns true if and only if \p *this is a line or a ray. #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) bool is_line_or_ray() const; //! Returns true if and only if \p *this is a point. bool is_point() const; //! Returns true if and only if \p *this is a closure point. bool is_closure_point() const; //! Returns the coefficient of \p v in \p *this. /*! \exception std::invalid_argument Thrown if the index of \p v is greater than or equal to the space dimension of \p *this. */ Coefficient_traits::const_reference coefficient(Variable v) const; //! If \p *this is either a point or a closure point, returns its divisor. /*! \exception std::invalid_argument Thrown if \p *this is neither a point nor a closure point. */ Coefficient_traits::const_reference divisor() const; //! Initializes the class. static void initialize(); //! Finalizes the class. static void finalize(); //! Returns the origin of the zero-dimensional space \f$\Rset^0\f$. static const Generator& zero_dim_point(); /*! \brief Returns, as a closure point, the origin of the zero-dimensional space \f$\Rset^0\f$. */ static const Generator& zero_dim_closure_point(); /*! \brief Returns a lower bound to the total size in bytes of the memory occupied by \p *this. */ memory_size_type total_memory_in_bytes() const; //! Returns the size in bytes of the memory managed by \p *this. memory_size_type external_memory_in_bytes() const; /*! \brief Returns true if and only if \p *this and \p y are equivalent generators. Generators having different space dimensions are not equivalent. */ bool is_equivalent_to(const Generator& y) const; PPL_OUTPUT_DECLARATIONS /*! \brief Loads from \p s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets \p *this accordingly. Returns true if successful, false otherwise. */ bool ascii_load(std::istream& s); //! Checks if all the invariants are satisfied. bool OK() const; //! Swaps \p *this with \p y. void swap(Generator& y); private: /*! \brief Holds (between class initialization and finalization) a pointer to the origin of the zero-dimensional space \f$\Rset^0\f$. */ static const Generator* zero_dim_point_p; /*! \brief Holds (between class initialization and finalization) a pointer to the origin of the zero-dimensional space \f$\Rset^0\f$, as a closure point. */ static const Generator* zero_dim_closure_point_p; /*! \brief Builds a generator of type \p type and topology \p topology, stealing the coefficients from \p e. */ Generator(Linear_Expression& e, Type type, Topology topology); /*! \brief Throw a std::invalid_argument exception containing the appropriate error message. */ void throw_dimension_incompatible(const char* method, const char* name_var, Variable v) const; /*! \brief Throw a std::invalid_argument exception containing the appropriate error message. */ void throw_invalid_argument(const char* method, const char* reason) const; friend class Parma_Polyhedra_Library::Scalar_Products; friend class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign; friend class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Assign; friend class Parma_Polyhedra_Library::Generator_System; friend class Parma_Polyhedra_Library::Generator_System::const_iterator; // FIXME: the following friend declaration should be avoided. friend class Parma_Polyhedra_Library::Polyhedron; friend class Parma_Polyhedra_Library::Grid_Generator; // This is for access to Row and Linear_Row in `insert'. friend class Parma_Polyhedra_Library::Grid_Generator_System; friend Parma_Polyhedra_Library ::Linear_Expression::Linear_Expression(const Generator& g); friend std::ostream& Parma_Polyhedra_Library::IO_Operators::operator<<(std::ostream& s, const Generator& g); //! Copy constructor with given space dimension. Generator(const Generator& g, dimension_type dimension); //! Returns true if and only if \p *this is not a line. bool is_ray_or_point() const; //! Sets the Linear_Row kind to LINE_OR_EQUALITY. void set_is_line(); //! Sets the Linear_Row kind to RAY_OR_POINT_OR_INEQUALITY. void set_is_ray_or_point(); /*! \brief Returns true if and only if the closure point \p *this has the same \e coordinates of the point \p p. It is \e assumed that \p *this is a closure point, \p p is a point and both topologies and space dimensions agree. */ bool is_matching_closure_point(const Generator& p) const; //! Default constructor: private and not implemented. Generator(); }; namespace Parma_Polyhedra_Library { //! Shorthand for Generator Generator::line(const Linear_Expression& e). /*! \relates Generator */ Generator line(const Linear_Expression& e); //! Shorthand for Generator Generator::ray(const Linear_Expression& e). /*! \relates Generator */ Generator ray(const Linear_Expression& e); /*! \brief Shorthand for Generator Generator::point(const Linear_Expression& e, Coefficient_traits::const_reference d). \relates Generator */ Generator point(const Linear_Expression& e = Linear_Expression::zero(), Coefficient_traits::const_reference d = Coefficient_one()); /*! \brief Shorthand for Generator Generator::closure_point(const Linear_Expression& e, Coefficient_traits::const_reference d). \relates Generator */ Generator closure_point(const Linear_Expression& e = Linear_Expression::zero(), Coefficient_traits::const_reference d = Coefficient_one()); //! Returns true if and only if \p x is equivalent to \p y. /*! \relates Generator */ bool operator==(const Generator& x, const Generator& y); //! Returns true if and only if \p x is not equivalent to \p y. /*! \relates Generator */ bool operator!=(const Generator& x, const Generator& y); //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. /*! \relates Generator If the rectilinear distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool rectilinear_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. /*! \relates Generator If the rectilinear distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool rectilinear_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. /*! \relates Generator If the rectilinear distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using the temporary variables \p tmp0, \p tmp1 and \p tmp2. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool rectilinear_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir, Temp& tmp0, Temp& tmp1, Temp& tmp2); //! Computes the euclidean distance between \p x and \p y. /*! \relates Generator If the euclidean distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool euclidean_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the euclidean distance between \p x and \p y. /*! \relates Generator If the euclidean distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool rectilinear_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the euclidean distance between \p x and \p y. /*! \relates Generator If the euclidean distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using the temporary variables \p tmp0, \p tmp1 and \p tmp2. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool euclidean_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir, Temp& tmp0, Temp& tmp1, Temp& tmp2); //! Computes the \f$L_\infty\f$ distance between \p x and \p y. /*! \relates Generator If the \f$L_\infty\f$ distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool l_infinity_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the \f$L_\infty\f$ distance between \p x and \p y. /*! \relates Generator If the \f$L_\infty\f$ distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using variables of type Checked_Number. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool l_infinity_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir); //! Computes the \f$L_\infty\f$ distance between \p x and \p y. /*! \relates Generator If the \f$L_\infty\f$ distance between \p x and \p y is defined, stores an approximation of it into \p r and returns true; returns false otherwise. The direction of the approximation is specified by \p dir. All computations are performed using the temporary variables \p tmp0, \p tmp1 and \p tmp2. \note Distances are \e only defined between generators that are points and/or closure points; for rays or lines, \c false is returned. */ template bool l_infinity_distance_assign(Checked_Number& r, const Generator& x, const Generator& y, Rounding_Dir dir, Temp& tmp0, Temp& tmp1, Temp& tmp2); namespace IO_Operators { //! Output operator. /*! \relates Parma_Polyhedra_Library::Generator */ std::ostream& operator<<(std::ostream& s, const Generator::Type& t); } // namespace IO_Operators } // namespace Parma_Polyhedra_Library #include "Generator.inlines.hh" #endif // !defined(PPL_Generator_defs_hh)