diff options
Diffstat (limited to 'src/Matrix.defs.hh')
| -rw-r--r-- | src/Matrix.defs.hh | 374 |
1 files changed, 374 insertions, 0 deletions
diff --git a/src/Matrix.defs.hh b/src/Matrix.defs.hh new file mode 100644 index 000000000..df03d9c98 --- /dev/null +++ b/src/Matrix.defs.hh @@ -0,0 +1,374 @@ +/* Matrix class declaration. + Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> + 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_Matrix_defs_hh +#define PPL_Matrix_defs_hh 1 + +#include "Matrix.types.hh" +#include "Row.defs.hh" +#include "Constraint_System.types.hh" +#include "Generator_System.types.hh" +#include "Coefficient.types.hh" +#include <vector> +#include <cstddef> + +#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS +//! A 2-dimensional matrix of coefficients. +/*! \ingroup PPL_CXX_interface + A Matrix object is a sequence of Row objects and is characterized + by the matrix dimensions (the number of rows and columns). + All the rows in a matrix, besides having the same size (corresponding + to the number of columns of the matrix), are also bound to have the + same capacity. +*/ +#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) + +class Parma_Polyhedra_Library::Matrix { +public: + //! Returns the maximum number of rows of a Matrix. + static dimension_type max_num_rows(); + + //! Returns the maximum number of columns of a Matrix. + static dimension_type max_num_columns(); + + //! Builds an empty matrix. + /*! + Rows' size and capacity are initialized to \f$0\f$. + */ + Matrix(); + + //! Builds a zero matrix with specified dimensions and flags. + /*! + \param n_rows + The number of rows of the matrix that will be created; + + \param n_columns + The number of columns of the matrix that will be created. + + \param row_flags + The flags used to build the rows of the matrix; + by default, the rows will have all flags unset. + */ + Matrix(dimension_type n_rows, dimension_type n_columns, + Row::Flags row_flags = Row::Flags()); + + //! Copy constructor. + Matrix(const Matrix& y); + + //! Destructor. + ~Matrix(); + + //! Assignment operator. + Matrix& operator=(const Matrix& y); + +#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS + //! An iterator over a matrix. + /*! \ingroup PPL_CXX_interface + A const_iterator is used to provide read-only access + to each row contained in a Matrix object. + */ +#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) + class const_iterator { + private: + typedef std::vector<Row>::const_iterator Iter; + //! The const iterator on the rows' vector \p rows. + Iter i; + + public: + typedef std::forward_iterator_tag iterator_category; + typedef std::iterator_traits<Iter>::value_type value_type; + typedef std::iterator_traits<Iter>::difference_type difference_type; + typedef std::iterator_traits<Iter>::pointer pointer; + typedef std::iterator_traits<Iter>::reference reference; + + //! Default constructor. + const_iterator(); + + /*! \brief + Builds a const iterator on the matrix starting from + an iterator \p b on the elements of the vector \p rows. + */ + explicit const_iterator(const Iter& b); + + //! Ordinary copy constructor. + const_iterator(const const_iterator& y); + + //! Assignment operator. + const_iterator& operator=(const const_iterator& y); + + //! Dereference operator. + reference operator*() const; + + //! Indirect member selector. + pointer operator->() const; + + //! Prefix increment operator. + const_iterator& operator++(); + + //! Postfix increment operator. + const_iterator operator++(int); + + /*! \brief + Returns <CODE>true</CODE> if and only if + \p *this and \p y are identical. + */ + bool operator==(const const_iterator& y) const; + + /*! \brief + Returns <CODE>true</CODE> if and only if + \p *this and \p y are different. + */ + bool operator!=(const const_iterator& y) const; + }; // class const_iterator + + + //! Returns <CODE>true</CODE> if and only if \p *this has no rows. + /*! + \note + The unusual naming for this method is \em intentional: + we do not want it to be named \c empty because this would cause + an error prone name clash with the corresponding methods in derived + classes Constraint_System and Congruence_System (which have a + different semantics). + */ + bool has_no_rows() const; + + /*! \brief + Returns the const_iterator pointing to the first row, 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; + + // FIXME: the following section must become private. +protected: + //! Contains the rows of the matrix. + std::vector<Row> rows; + + //! Size of the initialized part of each row. + dimension_type row_size; + + //! Capacity allocated for each row. + dimension_type row_capacity; + +public: + //! Swaps \p *this with \p y. + void swap(Matrix& y); + + //! Adds to the matrix \p n rows of zeroes with flags set to \p row_flags. + /*! + \param n + The number of rows to be added: must be strictly positive. + + \param row_flags + Flags for the newly added rows. + + Turns the \f$r \times c\f$ matrix \f$M\f$ into + the \f$(r+n) \times c\f$ matrix \f$\genfrac{(}{)}{0pt}{}{M}{0}\f$. + The matrix is expanded avoiding reallocation whenever possible. + */ + void add_zero_rows(dimension_type n, Row::Flags row_flags); + + //! Adds \p n columns of zeroes to the matrix. + /*! + \param n + The number of columns to be added: must be strictly positive. + + Turns the \f$r \times c\f$ matrix \f$M\f$ into + the \f$r \times (c+n)\f$ matrix \f$(M \, 0)\f$. + The matrix is expanded avoiding reallocation whenever possible. + */ + void add_zero_columns(dimension_type n); + + //! Adds \p n rows and \p m columns of zeroes to the matrix. + /*! + \param n + The number of rows to be added: must be strictly positive. + + \param m + The number of columns to be added: must be strictly positive. + + \param row_flags + Flags for the newly added rows. + + Turns the \f$r \times c\f$ matrix \f$M\f$ into + the \f$(r+n) \times (c+m)\f$ matrix + \f$\bigl(\genfrac{}{}{0pt}{}{M}{0} \genfrac{}{}{0pt}{}{0}{0}\bigr)\f$. + The matrix is expanded avoiding reallocation whenever possible. + */ + void add_zero_rows_and_columns(dimension_type n, dimension_type m, + Row::Flags row_flags); + + //! Adds a copy of the row \p y to the matrix. + /*! + \param y + The row to be copied: it must have the same number of columns as + the matrix. + + Turns the \f$r \times c\f$ matrix \f$M\f$ into + the \f$(r+1) \times c\f$ matrix + \f$\genfrac{(}{)}{0pt}{}{M}{y}\f$. + The matrix is expanded avoiding reallocation whenever possible. + */ + void add_row(const Row& y); + + //! Adds the row \p y to the matrix. + /*! + \param y + The row to be added: it must have the same size and capacity as + \p *this. It is not declared <CODE>const</CODE> because its + data-structures will recycled to build the new matrix row. + + Turns the \f$r \times c\f$ matrix \f$M\f$ into + the \f$(r+1) \times c\f$ matrix + \f$\genfrac{(}{)}{0pt}{}{M}{y}\f$. + The matrix is expanded avoiding reallocation whenever possible. + */ + void add_recycled_row(Row& y); + + //! Makes the matrix shrink by removing its \p n trailing columns. + void remove_trailing_columns(dimension_type n); + + //! Resizes the matrix without worrying about the old contents. + /*! + \param new_n_rows + The number of rows of the resized matrix; + + \param new_n_columns + The number of columns of the resized matrix. + + \param row_flags + The flags of the rows eventually added to the matrix. + + The matrix is expanded to the specified dimensions avoiding + reallocation whenever possible. + The contents of the original matrix is lost. + */ + void resize_no_copy(dimension_type new_n_rows, dimension_type new_n_columns, + Row::Flags row_flags); + + //! Swaps the columns having indexes \p i and \p j. + void swap_columns(dimension_type i, dimension_type j); + + //! Permutes the columns of the matrix. + /* + \param cycles + A vector representing the non-trivial cycles of the permutation + according to which the columns must be rearranged. + + The \p cycles vector contains, one after the other, the + non-trivial cycles (i.e., the cycles of length greater than one) + of a permutation of \e non-zero column indexes. Each cycle is + terminated by zero. For example, assuming the matrix has 7 + columns, the permutation \f$ \{ 1 \mapsto 3, 2 \mapsto 4, + 3 \mapsto 6, 4 \mapsto 2, 5 \mapsto 5, 6 \mapsto 1 \}\f$ can be + represented by the non-trivial cycles \f$(1 3 6)(2 4)\f$ that, in + turn can be represented by a vector of 6 elements containing 1, 3, + 6, 0, 2, 4, 0. + + \note + The first column of the matrix, having index zero, is never involved + in a permutation. + */ + void permute_columns(const std::vector<dimension_type>& cycles); + + //! \name Accessors + //@{ + + //! Returns the number of columns of the matrix (i.e., the size of the rows). + dimension_type num_columns() const; + + //! Returns the number of rows in the matrix. + dimension_type num_rows() const; + //@} // Accessors + + //! \name Subscript operators + //@{ + //! Returns a reference to the \p k-th row of the matrix. + Row& operator[](dimension_type k); + + //! Returns a constant reference to the \p k-th row of the matrix. + const Row& operator[](dimension_type k) const; + //@} // Subscript operators + + //! Clears the matrix deallocating all its rows. + void clear(); + + 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 <CODE>true</CODE> if successful, <CODE>false</CODE> 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; + + /*! \brief + Erases from the matrix all the rows but those having + an index less than \p first_to_erase. + */ + void erase_to_end(dimension_type first_to_erase); + + //! Checks if all the invariants are satisfied. + bool OK() const; +}; + +namespace std { + +#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS + //! Specializes <CODE>std::swap</CODE>. + /*! \relates Parma_Polyhedra_Library::Matrix */ +#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) +void swap(Parma_Polyhedra_Library::Matrix& x, + Parma_Polyhedra_Library::Matrix& y); + +} // namespace std + + +namespace Parma_Polyhedra_Library { + +#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS +//! Returns <CODE>true</CODE> if and only if \p x and \p y are identical. +/*! \relates Matrix */ +#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) +bool operator==(const Matrix& x, const Matrix& y); + +#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS +//! Returns <CODE>true</CODE> if and only if \p x and \p y are different. +/*! \relates Matrix */ +#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) +bool operator!=(const Matrix& x, const Matrix& y); + +} // namespace Parma_Polyhedra_Library + +#include "Matrix.inlines.hh" + +#endif // !defined(PPL_Matrix_defs_hh) |