1 /* Bit_Matrix class declaration. 2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it> 3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com) 4 5 This file is part of the Parma Polyhedra Library (PPL). 6 7 The PPL is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by the 9 Free Software Foundation; either version 3 of the License, or (at your 10 option) any later version. 11 12 The PPL is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software Foundation, 19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 20 21 For the most up-to-date information see the Parma Polyhedra Library 22 site: http://bugseng.com/products/ppl/ . */ 23 24 #ifndef PPL_Bit_Matrix_defs_hh 25 #define PPL_Bit_Matrix_defs_hh 1 26 27 #include "Bit_Matrix_types.hh" 28 #include "Linear_System_types.hh" 29 #include "Bit_Row_defs.hh" 30 #include <vector> 31 #include <iosfwd> 32 33 namespace Parma_Polyhedra_Library { 34 35 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 36 //! Swaps \p x with \p y. 37 /*! \relates Bit_Matrix */ 38 void swap(Bit_Matrix& x, Bit_Matrix& y); 39 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 40 41 } // namespace Parma_Polyhedra_Library 42 43 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 44 //! A matrix of bits. 45 /*! \ingroup PPL_CXX_interface */ 46 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 47 class Parma_Polyhedra_Library::Bit_Matrix { 48 public: 49 //! Default constructor. 50 Bit_Matrix(); 51 52 //! Construct a bit matrix with \p n_rows rows and \p n_columns columns. 53 Bit_Matrix(dimension_type n_rows, dimension_type n_columns); 54 55 //! Copy constructor. 56 Bit_Matrix(const Bit_Matrix& y); 57 58 //! Destructor. 59 ~Bit_Matrix(); 60 61 //! Assignment operator. 62 Bit_Matrix& operator=(const Bit_Matrix& y); 63 64 //! Swaps \p *this with \p y. 65 void m_swap(Bit_Matrix& y); 66 67 //! Subscript operator. 68 Bit_Row& operator[](dimension_type k); 69 70 //! Constant subscript operator. 71 const Bit_Row& operator[](dimension_type k) const; 72 73 //! Clears the matrix deallocating all its rows. 74 void clear(); 75 76 //! Transposes the matrix. 77 void transpose(); 78 79 //! Makes \p *this a transposed copy of \p y. 80 void transpose_assign(const Bit_Matrix& y); 81 82 //! Returns the maximum number of rows of a Bit_Matrix. 83 static dimension_type max_num_rows(); 84 85 //! Returns the number of columns of \p *this. 86 dimension_type num_columns() const; 87 88 //! Returns the number of rows of \p *this. 89 dimension_type num_rows() const; 90 91 //! Sorts the rows and removes duplicates. 92 void sort_rows(); 93 94 //! Looks for \p row in \p *this, which is assumed to be sorted. 95 /*! 96 \return 97 <CODE>true</CODE> if \p row belongs to \p *this, false otherwise. 98 99 \param row 100 The row that will be searched for in the matrix. 101 102 Given a sorted bit matrix (this ensures better efficiency), 103 tells whether it contains the given row. 104 */ 105 bool sorted_contains(const Bit_Row& row) const; 106 107 //! Adds \p row to \p *this. 108 /*! 109 \param row 110 The row whose implementation will be recycled. 111 112 The only thing that can be done with \p row upon return is destruction. 113 */ 114 void add_recycled_row(Bit_Row& row); 115 116 //! Removes the last \p n rows. 117 void remove_trailing_rows(dimension_type n); 118 119 //! Removes the last \p n columns. 120 /*! 121 The last \p n columns of the matrix are all made of zeros. 122 If such an assumption is not met, the behavior is undefined. 123 */ 124 void remove_trailing_columns(dimension_type n); 125 126 //! Resizes the matrix copying the old contents. 127 void resize(dimension_type new_n_rows, dimension_type new_n_columns); 128 129 //! Checks if all the invariants are satisfied. 130 bool OK() const; 131 132 PPL_OUTPUT_DECLARATIONS 133 134 /*! \brief 135 Loads from \p s an ASCII representation (as produced by 136 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 137 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 138 */ 139 bool ascii_load(std::istream& s); 140 141 //! Returns the total size in bytes of the memory occupied by \p *this. 142 memory_size_type total_memory_in_bytes() const; 143 144 //! Returns the size in bytes of the memory managed by \p *this. 145 memory_size_type external_memory_in_bytes() const; 146 147 #ifndef NDEBUG 148 //! Checks whether \p *this is sorted. It does NOT check for duplicates. 149 bool check_sorted() const; 150 #endif 151 152 private: 153 //! Contains the rows of the matrix. 154 std::vector<Bit_Row> rows; 155 156 //! Size of the initialized part of each row. 157 dimension_type row_size; 158 159 //! Ordering predicate (used when implementing the sort algorithm). 160 /*! \ingroup PPL_CXX_interface */ 161 struct Bit_Row_Less_Than { 162 bool operator()(const Bit_Row& x, const Bit_Row& y) const; 163 }; 164 165 template <typename Row> 166 friend class Parma_Polyhedra_Library::Linear_System; 167 }; 168 169 namespace Parma_Polyhedra_Library { 170 171 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 172 //! Returns <CODE>true</CODE> if and only if \p x and \p y are equal. 173 /*! \relates Bit_Matrix */ 174 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 175 bool operator==(const Bit_Matrix& x, const Bit_Matrix& y); 176 177 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 178 //! Returns <CODE>true</CODE> if and only if \p x and \p y are not equal. 179 /*! \relates Bit_Matrix */ 180 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 181 bool operator!=(const Bit_Matrix& x, const Bit_Matrix& y); 182 183 } // namespace Parma_Polyhedra_Library 184 185 #include "Bit_Matrix_inlines.hh" 186 187 #endif // !defined(PPL_Bit_Matrix_defs_hh) 188