/* Constraint_System class declaration. Copyright (C) 2001-2010 Roberto Bagnara Copyright (C) 2010-2012 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://bugseng.com/products/ppl/ . */ #ifndef PPL_Constraint_System_defs_hh #define PPL_Constraint_System_defs_hh 1 #include "Constraint_System_types.hh" #include "Linear_System_defs.hh" #include "Constraint_defs.hh" #include "Linear_Expression_types.hh" #include "Generator_types.hh" #include "Constraint_types.hh" #include "Congruence_System_types.hh" #include "Polyhedron_types.hh" #include "termination_types.hh" #include #include namespace Parma_Polyhedra_Library { namespace IO_Operators { //! Output operator. /*! \relates Parma_Polyhedra_Library::Constraint_System Writes true if \p cs is empty. Otherwise, writes on \p s the constraints of \p cs, all in one row and separated by ", ". */ std::ostream& operator<<(std::ostream& s, const Constraint_System& cs); } // namespace IO_Operators // TODO: Consider removing this. #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS //! Returns true if and only if \p x and \p y are identical. /*! \relates Constraint_System */ #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) bool operator==(const Constraint_System& x, const Constraint_System& y); // TODO: Consider removing this. #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS //! Returns true if and only if \p x and \p y are different. /*! \relates Constraint_System */ #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) bool operator!=(const Constraint_System& x, const Constraint_System& y); /*! \relates Constraint_System */ void swap(Constraint_System& x, Constraint_System& y); } // namespace Parma_Polyhedra_Library //! A system of constraints. /*! \ingroup PPL_CXX_interface An object of the class Constraint_System is a system of constraints, i.e., a multiset of objects of the class Constraint. When inserting constraints in a system, space dimensions are automatically adjusted so that all the constraints in the system are defined on the same vector space. \par In all the examples it is assumed that variables x and y are defined as follows: \code Variable x(0); Variable y(1); \endcode \par Example 1 The following code builds a system of constraints corresponding to a square in \f$\Rset^2\f$: \code Constraint_System cs; cs.insert(x >= 0); cs.insert(x <= 3); cs.insert(y >= 0); cs.insert(y <= 3); \endcode Note that: the constraint system is created with space dimension zero; the first and third constraint insertions increase the space dimension to \f$1\f$ and \f$2\f$, respectively. \par Example 2 By adding four strict inequalities to the constraint system of the previous example, we can remove just the four vertices from the square defined above. \code cs.insert(x + y > 0); cs.insert(x + y < 6); cs.insert(x - y < 3); cs.insert(y - x < 3); \endcode \par Example 3 The following code builds a system of constraints corresponding to a half-strip in \f$\Rset^2\f$: \code Constraint_System cs; cs.insert(x >= 0); cs.insert(x - y <= 0); cs.insert(x - y + 1 >= 0); \endcode \note After inserting a multiset of constraints in a constraint system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent constraint system will be available, where original constraints may have been reordered, removed (if they are trivial, duplicate or implied by other constraints), linearly combined, etc. */ class Parma_Polyhedra_Library::Constraint_System { public: typedef Constraint row_type; static const Representation default_representation = SPARSE; //! Default constructor: builds an empty system of constraints. explicit Constraint_System(Representation r = default_representation); //! Builds the singleton system containing only constraint \p c. explicit Constraint_System(const Constraint& c, Representation r = default_representation); //! Builds a system containing copies of any equalities in \p cgs. explicit Constraint_System(const Congruence_System& cgs, Representation r = default_representation); //! Ordinary copy constructor. /*! \note The copy will have the same representation as `cs', to make it indistinguishable from `cs'. */ Constraint_System(const Constraint_System& cs); //! Copy constructor with specified representation. Constraint_System(const Constraint_System& cs, Representation r); //! Destructor. ~Constraint_System(); //! Assignment operator. Constraint_System& operator=(const Constraint_System& y); //! Returns the current representation of *this. Representation representation() const; //! Converts *this to the specified representation. void set_representation(Representation r); //! Returns the maximum space dimension a Constraint_System can handle. static dimension_type max_space_dimension(); //! Returns the dimension of the vector space enclosing \p *this. dimension_type space_dimension() const; //! Sets the space dimension of the rows in the system to \p space_dim . void set_space_dimension(dimension_type space_dim); /*! \brief Returns true if and only if \p *this contains one or more equality constraints. */ bool has_equalities() const; /*! \brief Returns true if and only if \p *this contains one or more strict inequality constraints. */ bool has_strict_inequalities() const; /*! \brief Inserts in \p *this a copy of the constraint \p c, increasing the number of space dimensions if needed. */ void insert(const Constraint& c); //! Initializes the class. static void initialize(); //! Finalizes the class. static void finalize(); /*! \brief Returns the singleton system containing only Constraint::zero_dim_false(). */ static const Constraint_System& zero_dim_empty(); typedef Constraint_System_const_iterator const_iterator; //! Returns true if and only if \p *this has no constraints. bool empty() const; /*! \brief Removes all the constraints from the constraint system and sets its space dimension to 0. */ void clear(); /*! \brief Returns the const_iterator pointing to the first constraint, if \p *this is not empty; otherwise, returns the past-the-end const_iterator. */ const_iterator begin() const; //! Returns the past-the-end const_iterator. const_iterator end() const; //! Checks if all the invariants are satisfied. bool OK() 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); //! Returns 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; //! Swaps \p *this with \p y. void m_swap(Constraint_System& y); private: Linear_System sys; /*! \brief Holds (between class initialization and finalization) a pointer to the singleton system containing only Constraint::zero_dim_false(). */ static const Constraint_System* zero_dim_empty_p; friend class Constraint_System_const_iterator; friend bool operator==(const Constraint_System& x, const Constraint_System& y); //! Builds an empty system of constraints having the specified topology. explicit Constraint_System(Topology topol, Representation r = default_representation); /*! \brief Builds a system of constraints on a \p space_dim dimensional space. If \p topol is NOT_NECESSARILY_CLOSED the \f$\epsilon\f$ dimension is added. */ Constraint_System(Topology topol, dimension_type space_dim, Representation r = default_representation); //! Returns the number of equality constraints. dimension_type num_equalities() const; //! Returns the number of inequality constraints. dimension_type num_inequalities() const; /*! \brief Applies Gaussian elimination and back-substitution so as to provide a partial simplification of the system of constraints. It is assumed that the system has no pending constraints. */ void simplify(); /*! \brief Adjusts \p *this so that it matches \p new_topology and \p new_space_dim (adding or removing columns if needed). Returns false if and only if \p topol is equal to NECESSARILY_CLOSED and \p *this contains strict inequalities. */ bool adjust_topology_and_space_dimension(Topology new_topology, dimension_type new_space_dim); //! Returns a constant reference to the \p k- th constraint of the system. const Constraint& operator[](dimension_type k) const; //! Returns true if \p g satisfies all the constraints. bool satisfies_all_constraints(const Generator& g) const; //! Substitutes a given column of coefficients by a given affine expression. /*! \param v The variable to which the affine transformation is substituted. \param expr The numerator of the affine transformation: \f$\sum_{i = 0}^{n - 1} a_i x_i + b\f$; \param denominator The denominator of the affine transformation. We want to allow affine transformations (see Section \ref Images_and_Preimages_of_Affine_Transfer_Relations) having any rational coefficients. Since the coefficients of the constraints are integers we must also provide an integer \p denominator that will be used as denominator of the affine transformation. The denominator is required to be a positive integer. The affine transformation substitutes the matrix of constraints by a new matrix whose elements \f${a'}_{ij}\f$ are built from the old one \f$a_{ij}\f$ as follows: \f[ {a'}_{ij} = \begin{cases} a_{ij} * \mathrm{denominator} + a_{iv} * \mathrm{expr}[j] \quad \text{for } j \neq v; \\ \mathrm{expr}[v] * a_{iv} \quad \text{for } j = v. \end{cases} \f] \p expr is a constant parameter and unaltered by this computation. */ void affine_preimage(Variable v, const Linear_Expression& expr, Coefficient_traits::const_reference denominator); /*! \brief Inserts in \p *this a copy of the constraint \p c, increasing the number of space dimensions if needed. It is a pending constraint. */ void insert_pending(const Constraint& c); //! Adds low-level constraints to the constraint system. void add_low_level_constraints(); //! Returns the system topology. Topology topology() const; dimension_type num_rows() const; /*! \brief Returns true if and only if the system topology is NECESSARILY_CLOSED. */ bool is_necessarily_closed() const; //! Returns the number of rows that are in the pending part of the system. dimension_type num_pending_rows() const; //! Returns the index of the first pending row. dimension_type first_pending_row() const; //! Returns the value of the sortedness flag. bool is_sorted() const; //! Sets the index to indicate that the system has no pending rows. void unset_pending_rows(); //! Sets the index of the first pending row to \p i. void set_index_first_pending_row(dimension_type i); //! Sets the sortedness flag of the system to \p b. void set_sorted(bool b); //! Makes the system shrink by removing its i-th row. /*! When \p keep_sorted is \p true and the system is sorted, sortedness will be preserved, but this method costs O(n). Otherwise, this method just swaps the i-th row with the last and then removes it, so it costs O(1). */ void remove_row(dimension_type i, bool keep_sorted = false); //! Removes the specified rows. The row ordering of remaining rows is //! preserved. /*! \param indexes specifies a list of row indexes. It must be sorted. */ void remove_rows(const std::vector& indexes); //! Makes the system shrink by removing the rows in [first,last). /*! When \p keep_sorted is \p true and the system is sorted, sortedness will be preserved, but this method costs O(num_rows()). Otherwise, this method just swaps the rows with the last ones and then removes them, so it costs O(last - first). */ void remove_rows(dimension_type first, dimension_type last, bool keep_sorted = false); //! Makes the system shrink by removing its \p n trailing rows. void remove_trailing_rows(dimension_type n); //! Removes all the specified dimensions from the constraint system. /*! The space dimension of the variable with the highest space dimension in \p vars must be at most the space dimension of \p this. */ void remove_space_dimensions(const Variables_Set& vars); //! Shift by \p n positions the coefficients of variables, starting from //! the coefficient of \p v. This increases the space dimension by \p n. void shift_space_dimensions(Variable v, dimension_type n); //! Permutes the space dimensions of the matrix. /* \param cycle A vector representing a cycle of the permutation according to which the columns must be rearranged. The \p cycle vector represents a cycle of a permutation of space dimensions. For example, the permutation \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be represented by the vector containing \f$ x_1, x_2, x_3 \f$. */ void permute_space_dimensions(const std::vector& cycle); //! Swaps the coefficients of the variables \p v1 and \p v2 . void swap_space_dimensions(Variable v1, Variable v2); bool has_no_rows() const; //! Strongly normalizes the system. void strong_normalize(); /*! \brief Sorts the non-pending rows (in growing order) and eliminates duplicated ones. */ void sort_rows(); /*! \brief Adds the given row to the pending part of the system, stealing its contents and automatically resizing the system or the row, if needed. */ void insert_pending(Constraint& r, Recycle_Input); //! Adds the rows of `y' to the pending part of `*this', stealing them from //! `y'. void insert_pending(Constraint_System& r, Recycle_Input); /*! \brief Adds \p r to the system, stealing its contents and automatically resizing the system or the row, if needed. */ void insert(Constraint& r, Recycle_Input); //! Adds to \p *this a the rows of `y', stealing them from `y'. /*! It is assumed that \p *this has no pending rows. */ void insert(Constraint_System& r, Recycle_Input); //! Adds a copy of the rows of `y' to the pending part of `*this'. void insert_pending(const Constraint_System& r); /*! \brief Assigns to \p *this the result of merging its rows with those of \p y, obtaining a sorted system. Duplicated rows will occur only once in the result. On entry, both systems are assumed to be sorted and have no pending rows. */ void merge_rows_assign(const Constraint_System& y); //! Adds to \p *this a copy of the rows of \p y. /*! It is assumed that \p *this has no pending rows. */ void insert(const Constraint_System& y); //! Marks the epsilon dimension as a standard dimension. /*! The system topology is changed to NOT_NECESSARILY_CLOSED, and the number of space dimensions is increased by 1. */ void mark_as_necessarily_closed(); //! Marks the last dimension as the epsilon dimension. /*! The system topology is changed to NECESSARILY_CLOSED, and the number of space dimensions is decreased by 1. */ void mark_as_not_necessarily_closed(); //! Minimizes the subsystem of equations contained in \p *this. /*! This method works only on the equalities of the system: the system is required to be partially sorted, so that all the equalities are grouped at its top; it is assumed that the number of equalities is exactly \p n_lines_or_equalities. The method finds a minimal system for the equalities and returns its rank, i.e., the number of linearly independent equalities. The result is an upper triangular subsystem of equalities: for each equality, the pivot is chosen starting from the right-most columns. */ dimension_type gauss(dimension_type n_lines_or_equalities); /*! \brief Back-substitutes the coefficients to reduce the complexity of the system. Takes an upper triangular system having \p n_lines_or_equalities rows. For each row, starting from the one having the minimum number of coefficients different from zero, computes the expression of an element as a function of the remaining ones and then substitutes this expression in all the other rows. */ void back_substitute(dimension_type n_lines_or_equalities); //! Full assignment operator: pending rows are copied as pending. void assign_with_pending(const Constraint_System& y); /*! \brief Sorts the pending rows and eliminates those that also occur in the non-pending part of the system. */ void sort_pending_and_remove_duplicates(); /*! \brief Sorts the system, removing duplicates, keeping the saturation matrix consistent. \param sat Bit matrix with rows corresponding to the rows of \p *this. */ void sort_and_remove_with_sat(Bit_Matrix& sat); /*! \brief Returns true if and only if \p *this is sorted, without checking for duplicates. */ bool check_sorted() const; /*! \brief Returns the number of rows in the system that represent either lines or equalities. */ dimension_type num_lines_or_equalities() const; //! Adds \p n rows and space dimensions to the system. /*! \param n The number of rows and space dimensions to be added: must be strictly positive. Turns the system \f$M \in \Rset^r \times \Rset^c\f$ into the system \f$N \in \Rset^{r+n} \times \Rset^{c+n}\f$ such that \f$N = \bigl(\genfrac{}{}{0pt}{}{0}{M}\genfrac{}{}{0pt}{}{J}{o}\bigr)\f$, where \f$J\f$ is the specular image of the \f$n \times n\f$ identity matrix. */ void add_universe_rows_and_space_dimensions(dimension_type n); friend class Polyhedron; friend class Termination_Helpers; }; //! An iterator over a system of constraints. /*! \ingroup PPL_CXX_interface A const_iterator is used to provide read-only access to each constraint contained in a Constraint_System object. \par Example The following code prints the system of constraints defining the polyhedron ph: \code const Constraint_System& cs = ph.constraints(); for (Constraint_System::const_iterator i = cs.begin(), cs_end = cs.end(); i != cs_end; ++i) cout << *i << endl; \endcode */ // NOTE: This is not an inner class of Constraint_System, so Constraint can // declare that this class is his friend without including this file // (the .types.hh file suffices). class Parma_Polyhedra_Library::Constraint_System_const_iterator : public std::iterator { public: //! Default constructor. Constraint_System_const_iterator(); //! Ordinary copy constructor. Constraint_System_const_iterator(const Constraint_System_const_iterator& y); //! Destructor. ~Constraint_System_const_iterator(); //! Assignment operator. Constraint_System_const_iterator& operator=(const Constraint_System_const_iterator& y); //! Dereference operator. const Constraint& operator*() const; //! Indirect member selector. const Constraint* operator->() const; //! Prefix increment operator. Constraint_System_const_iterator& operator++(); //! Postfix increment operator. Constraint_System_const_iterator operator++(int); /*! \brief Returns true if and only if \p *this and \p y are identical. */ bool operator==(const Constraint_System_const_iterator& y) const; /*! \brief Returns true if and only if \p *this and \p y are different. */ bool operator!=(const Constraint_System_const_iterator& y) const; private: friend class Constraint_System; //! The const iterator over the matrix of constraints. Linear_System::const_iterator i; //! A const pointer to the matrix of constraints. const Linear_System* csp; //! Constructor. Constraint_System_const_iterator(const Linear_System ::const_iterator& iter, const Constraint_System& cs); //! \p *this skips to the next non-trivial constraint. void skip_forward(); }; namespace Parma_Polyhedra_Library { namespace Implementation { #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS //! Helper returning number of constraints in system. #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) dimension_type num_constraints(const Constraint_System& cs); } // namespace Implementation } // namespace Parma_Polyhedra_Library // Constraint_System_inlines.hh is not included here on purpose. #endif // !defined(PPL_Constraint_System_defs_hh)