1 /* 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_Matrix_defs_hh 25 #define PPL_Matrix_defs_hh 1 26 27 #include "Matrix_types.hh" 28 #include "globals_defs.hh" 29 #include "Coefficient_defs.hh" 30 #include "Swapping_Vector_defs.hh" 31 #include <ostream> 32 33 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 34 //! A sparse matrix of Coefficient. 35 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 36 template <typename Row> 37 class Parma_Polyhedra_Library::Matrix { 38 39 public: 40 typedef typename Swapping_Vector<Row>::iterator iterator; 41 typedef typename Swapping_Vector<Row>::const_iterator const_iterator; 42 43 //! Returns the maximum number of rows of a Sparse_Matrix. 44 static dimension_type max_num_rows(); 45 46 //! Returns the maximum number of columns of a Sparse_Matrix. 47 static dimension_type max_num_columns(); 48 49 /*! 50 \brief Constructs a square matrix with the given size, filled with 51 unstored zeroes. 52 53 \param n 54 The size of the new square matrix. 55 56 This method takes \f$O(n)\f$ time. 57 */ 58 explicit Matrix(dimension_type n = 0); 59 60 /*! 61 \brief Constructs a matrix with the given dimensions, filled with unstored 62 zeroes. 63 64 \param num_rows 65 The number of rows in the new matrix. 66 67 \param num_columns 68 The number of columns in the new matrix. 69 70 This method takes \f$O(n)\f$ time, where n is \p num_rows. 71 */ 72 Matrix(dimension_type num_rows, dimension_type num_columns); 73 74 //! Swaps (*this) with x. 75 /*! 76 77 \param x 78 The matrix that will be swapped with *this. 79 80 This method takes \f$O(1)\f$ time. 81 */ 82 void m_swap(Matrix& x); 83 84 //! Returns the number of rows in the matrix. 85 /*! 86 This method takes \f$O(1)\f$ time. 87 */ 88 dimension_type num_rows() const; 89 90 //! Returns the number of columns in the matrix. 91 /*! 92 This method takes \f$O(1)\f$ time. 93 */ 94 dimension_type num_columns() const; 95 96 // TODO: Check if this can be removed. 97 //! Returns the capacity of the row vector. 98 dimension_type capacity() const; 99 100 //! Returns <CODE>true</CODE> if and only if \p *this has no rows. 101 /*! 102 \note 103 The unusual naming for this method is \em intentional: 104 we do not want it to be named \c empty because this would cause 105 an error prone name clash with the corresponding methods in derived 106 classes Constraint_System and Congruence_System (which have a 107 different semantics). 108 */ 109 bool has_no_rows() const; 110 111 //! Equivalent to resize(n, n). 112 void resize(dimension_type n); 113 114 // TODO: Check if this can become private. 115 //! Reserves space for at least \p n rows. 116 void reserve_rows(dimension_type n); 117 118 //! Resizes this matrix to the specified dimensions. 119 /*! 120 121 \param num_rows 122 The desired numer of rows. 123 124 \param num_columns 125 The desired numer of columns. 126 127 New rows and columns will contain non-stored zeroes. 128 129 This operation invalidates existing iterators. 130 131 Adding n rows takes \f$O(n)\f$ amortized time. 132 133 Adding n columns takes \f$O(r)\f$ time, where r is \p num_rows. 134 135 Removing n rows takes \f$O(n+k)\f$ amortized time, where k is the total 136 number of elements stored in the removed rows. 137 138 Removing n columns takes \f$O(\sum_{j=1}^{r} (k_j*\log^2 n_j))\f$ time, 139 where r is the number of rows, \f$k_j\f$ is the number of elements stored 140 in the columns of the j-th row that must be removed and \f$n_j\f$ is the 141 total number of elements stored in the j-th row. 142 A weaker (but simpler) bound is \f$O(r+k*\log^2 c)\f$, where r is the 143 number of rows, k is the number of elements that have to be removed and c 144 is the number of columns. 145 */ 146 void resize(dimension_type num_rows, dimension_type num_columns); 147 148 //! Adds \p n rows and \p m columns of zeroes to the matrix. 149 /*! 150 \param n 151 The number of rows to be added: must be strictly positive. 152 153 \param m 154 The number of columns to be added: must be strictly positive. 155 156 Turns the \f$r \times c\f$ matrix \f$M\f$ into 157 the \f$(r+n) \times (c+m)\f$ matrix 158 \f$\bigl(\genfrac{}{}{0pt}{}{M}{0} \genfrac{}{}{0pt}{}{0}{0}\bigr)\f$. 159 The matrix is expanded avoiding reallocation whenever possible. 160 161 This method takes \f$O(r)\f$ time, where r is the number of the matrix's 162 rows after the operation. 163 */ 164 void add_zero_rows_and_columns(dimension_type n, dimension_type m); 165 166 //! Adds to the matrix \p n rows of zeroes. 167 /*! 168 \param n 169 The number of rows to be added: must be strictly positive. 170 171 Turns the \f$r \times c\f$ matrix \f$M\f$ into 172 the \f$(r+n) \times c\f$ matrix \f$\genfrac{(}{)}{0pt}{}{M}{0}\f$. 173 The matrix is expanded avoiding reallocation whenever possible. 174 175 This method takes \f$O(k)\f$ amortized time, where k is the number of the 176 new rows. 177 */ 178 void add_zero_rows(dimension_type n); 179 180 //! Adds a copy of the row \p x at the end of the matrix. 181 /*! 182 183 \param x 184 The row that will be appended to the matrix. 185 186 This operation invalidates existing iterators. 187 188 This method takes \f$O(n)\f$ amortized time, where n is the numer of 189 elements stored in \p x. 190 */ 191 void add_row(const Row& x); 192 193 //! Adds the row \p y to the matrix. 194 /*! 195 \param y 196 The row to be added: it must have the same size and capacity as 197 \p *this. It is not declared <CODE>const</CODE> because its 198 data-structures will recycled to build the new matrix row. 199 200 Turns the \f$r \times c\f$ matrix \f$M\f$ into 201 the \f$(r+1) \times c\f$ matrix 202 \f$\genfrac{(}{)}{0pt}{}{M}{y}\f$. 203 The matrix is expanded avoiding reallocation whenever possible. 204 */ 205 void add_recycled_row(Row& y); 206 207 /*! \brief 208 Removes from the matrix the last \p n rows. 209 210 \param n 211 The number of row that will be removed. 212 213 It is equivalent to num_rows() - n, num_columns()). 214 215 This method takes \f$O(n+k)\f$ amortized time, where k is the total number 216 of elements stored in the removed rows and n is the number of removed 217 rows. 218 */ 219 void remove_trailing_rows(dimension_type n); 220 221 void remove_rows(iterator first, iterator last); 222 223 //! Permutes the columns of the matrix. 224 /*! 225 This method may be slow for some Row types, and should be avoided if 226 possible. 227 228 \param cycles 229 A vector representing the non-trivial cycles of the permutation 230 according to which the columns must be rearranged. 231 232 The \p cycles vector contains, one after the other, the 233 non-trivial cycles (i.e., the cycles of length greater than one) 234 of a permutation of \e non-zero column indexes. Each cycle is 235 terminated by zero. For example, assuming the matrix has 7 236 columns, the permutation \f$ \{ 1 \mapsto 3, 2 \mapsto 4, 237 3 \mapsto 6, 4 \mapsto 2, 5 \mapsto 5, 6 \mapsto 1 \}\f$ can be 238 represented by the non-trivial cycles \f$(1 3 6)(2 4)\f$ that, in 239 turn can be represented by a vector of 6 elements containing 1, 3, 240 6, 0, 2, 4, 0. 241 242 This method takes \f$O(k*\sum_{j=1}^{r} \log^2 n_j)\f$ expected time, 243 where k is the size of the \p cycles vector, r the number of rows and 244 \f$n_j\f$ the number of elements stored in row j. 245 A weaker (but simpler) bound is \f$O(k*r*\log^2 c)\f$, where k is the size 246 of the \p cycles vector, r is the number of rows and c is the number of 247 columns. 248 249 \note 250 The first column of the matrix, having index zero, is never involved 251 in a permutation. 252 */ 253 void permute_columns(const std::vector<dimension_type>& cycles); 254 255 //! Swaps the columns having indexes \p i and \p j. 256 void swap_columns(dimension_type i, dimension_type j); 257 258 //! Adds \p n columns of zeroes to the matrix. 259 /*! 260 \param n 261 The number of columns to be added: must be strictly positive. 262 263 Turns the \f$r \times c\f$ matrix \f$M\f$ into 264 the \f$r \times (c+n)\f$ matrix \f$(M \, 0)\f$. 265 266 This method takes \f$O(r)\f$ amortized time, where r is the numer of the 267 matrix's rows. 268 */ 269 void add_zero_columns(dimension_type n); 270 271 //! Adds \p n columns of non-stored zeroes to the matrix before column i. 272 /*! 273 274 \param n 275 The numer of columns that will be added. 276 277 \param i 278 The index of the column before which the new columns will be added. 279 280 This operation invalidates existing iterators. 281 282 This method takes \f$O(\sum_{j=1}^{r} (k_j+\log n_j))\f$ time, where r is 283 the number of rows, \f$k_j\f$ is the number of elements stored in the 284 columns of the j-th row that must be shifted and \f$n_j\f$ is the number 285 of elements stored in the j-th row. 286 A weaker (but simpler) bound is \f$O(k+r*\log c)\f$ time, where k is the 287 number of elements that must be shifted, r is the number of the rows and c 288 is the number of the columns. 289 */ 290 void add_zero_columns(dimension_type n, dimension_type i); 291 292 //! Removes the i-th from the matrix, shifting other columns to the left. 293 /*! 294 295 \param i 296 The index of the column that will be removed. 297 298 This operation invalidates existing iterators on rows' elements. 299 300 This method takes \f$O(k + \sum_{j=1}^{r} (\log^2 n_j))\f$ amortized time, 301 where k is the number of elements stored with column index greater than i, 302 r the number of rows in this matrix and \f$n_j\f$ the number of elements 303 stored in row j. 304 A weaker (but simpler) bound is \f$O(r*(c-i+\log^2 c))\f$, where r is the 305 number of rows, c is the number of columns and i is the parameter passed 306 to this method. 307 */ 308 void remove_column(dimension_type i); 309 310 //! Shrinks the matrix by removing its \p n trailing columns. 311 /*! 312 313 \param n 314 The number of trailing columns that will be removed. 315 316 This operation invalidates existing iterators. 317 318 This method takes \f$O(\sum_{j=1}^r (k_j*\log n_j))\f$ amortized time, 319 where r is the number of rows, \f$k_j\f$ is the number of elements that 320 have to be removed from row j and \f$n_j\f$ is the total number of 321 elements stored in row j. 322 A weaker (but simpler) bound is \f$O(r*n*\log c)\f$, where r is the number 323 of rows, c the number of columns and n the parameter passed to this 324 method. 325 */ 326 void remove_trailing_columns(dimension_type n); 327 328 //! Equivalent to resize(0,0). 329 void clear(); 330 331 //! Returns an %iterator pointing to the first row. 332 /*! 333 This method takes \f$O(1)\f$ time. 334 */ 335 iterator begin(); 336 337 //! Returns an %iterator pointing after the last row. 338 /*! 339 This method takes \f$O(1)\f$ time. 340 */ 341 iterator end(); 342 343 //! Returns an %iterator pointing to the first row. 344 /*! 345 This method takes \f$O(1)\f$ time. 346 */ 347 const_iterator begin() const; 348 349 //! Returns an %iterator pointing after the last row. 350 /*! 351 This method takes \f$O(1)\f$ time. 352 */ 353 const_iterator end() const; 354 355 //! Returns a reference to the i-th row. 356 /*! 357 \param i 358 The index of the desired row. 359 360 This method takes \f$O(1)\f$ time. 361 */ 362 Row& operator[](dimension_type i); 363 364 //! Returns a const reference to the i-th row. 365 /*! 366 \param i 367 The index of the desired row. 368 369 This method takes \f$O(1)\f$ time. 370 */ 371 const Row& operator[](dimension_type i) const; 372 373 //! Loads the row from an ASCII representation generated using ascii_dump(). 374 /*! 375 \param s 376 The stream from which read the ASCII representation. 377 378 This method takes \f$O(n*\log n)\f$ time. 379 */ 380 bool ascii_load(std::istream& s); 381 382 PPL_OUTPUT_DECLARATIONS 383 384 //! Returns the total size in bytes of the memory occupied by \p *this. 385 /*! 386 This method is \f$O(r+k)\f$, where r is the number of rows and k is the 387 number of elements stored in the matrix. 388 */ 389 memory_size_type total_memory_in_bytes() const; 390 391 //! Returns the size in bytes of the memory managed by \p *this. 392 /*! 393 This method is \f$O(r+k)\f$, where r is the number of rows and k is the 394 number of elements stored in the matrix. 395 */ 396 memory_size_type external_memory_in_bytes() const; 397 398 //! Checks if all the invariants are satisfied. 399 bool OK() const; 400 401 private: 402 //! The vector that stores the matrix's elements. 403 Swapping_Vector<Row> rows; 404 405 //! The number of columns in this matrix. 406 dimension_type num_columns_; 407 }; 408 409 namespace Parma_Polyhedra_Library { 410 411 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 412 /*! \relates Matrix */ 413 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 414 template <typename Row> 415 void swap(Matrix<Row>& x, Matrix<Row>& y); 416 417 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 418 //! Returns <CODE>true</CODE> if and only if \p x and \p y are identical. 419 /*! \relates Matrix */ 420 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 421 template <typename Row> 422 bool operator==(const Matrix<Row>& x, const Matrix<Row>& y); 423 424 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 425 //! Returns <CODE>true</CODE> if and only if \p x and \p y are different. 426 /*! \relates Matrix */ 427 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 428 template <typename Row> 429 bool operator!=(const Matrix<Row>& x, const Matrix<Row>& y); 430 431 } // namespace Parma_Polyhedra_Library 432 433 434 #include "Matrix_inlines.hh" 435 #include "Matrix_templates.hh" 436 437 #endif // !defined(PPL_Matrix_defs_hh) 438