1 /* OR_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_OR_Matrix_defs_hh 25 #define PPL_OR_Matrix_defs_hh 1 26 27 #include "OR_Matrix_types.hh" 28 #include "globals_defs.hh" 29 #include "DB_Row_defs.hh" 30 #include "Checked_Number_defs.hh" 31 #include <cstddef> 32 #include <iosfwd> 33 34 #ifndef PPL_OR_MATRIX_EXTRA_DEBUG 35 #ifdef PPL_ABI_BREAKING_EXTRA_DEBUG 36 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 37 /*! \brief 38 When PPL_OR_MATRIX_EXTRA_DEBUG evaluates to <CODE>true</CODE>, each 39 instance of the class OR_Matrix::Pseudo_Row carries its own size; 40 this enables extra consistency checks to be performed. 41 \ingroup PPL_CXX_interface 42 */ 43 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 44 #define PPL_OR_MATRIX_EXTRA_DEBUG 1 45 #else // !defined(PPL_ABI_BREAKING_EXTRA_DEBUG) 46 #define PPL_OR_MATRIX_EXTRA_DEBUG 0 47 #endif // !defined(PPL_ABI_BREAKING_EXTRA_DEBUG) 48 #endif // !defined(PPL_OR_MATRIX_EXTRA_DEBUG) 49 50 namespace Parma_Polyhedra_Library { 51 52 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 53 //! Returns <CODE>true</CODE> if and only if \p x and \p y are identical. 54 /*! \relates OR_Matrix */ 55 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 56 template <typename T> 57 bool operator==(const OR_Matrix<T>& x, const OR_Matrix<T>& y); 58 59 namespace IO_Operators { 60 61 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 62 //! Output operator. 63 /*! \relates Parma_Polyhedra_Library::OR_Matrix */ 64 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 65 template <typename T> 66 std::ostream& 67 operator<<(std::ostream& s, const OR_Matrix<T>& m); 68 69 } // namespace IO_Operators 70 71 } // namespace Parma_Polyhedra_Library 72 73 74 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 75 //! A matrix representing octagonal constraints. 76 /*! 77 An OR_Matrix object is a DB_Row object that allows 78 the representation of a \em pseudo-triangular matrix, 79 like the following: 80 81 <PRE> 82 _ _ 83 0 |_|_| 84 1 |_|_|_ _ 85 2 |_|_|_|_| 86 3 |_|_|_|_|_ _ 87 4 |_|_|_|_|_|_| 88 5 |_|_|_|_|_|_| 89 . . . 90 _ _ _ _ _ _ _ 91 2n-2 |_|_|_|_|_|_| ... |_| 92 2n-1 |_|_|_|_|_|_| ... |_| 93 0 1 2 3 4 5 ... 2n-1 94 95 </PRE> 96 97 It is characterized by parameter n that defines the structure, 98 and such that there are 2*n rows (and 2*n columns). 99 It provides row_iterators for the access to the rows 100 and element_iterators for the access to the elements. 101 */ 102 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 103 104 template <typename T> 105 class Parma_Polyhedra_Library::OR_Matrix { 106 private: 107 /*! \brief 108 An object that behaves like a matrix's row with respect to 109 the subscript operators. 110 */ 111 template <typename U> 112 class Pseudo_Row { 113 public: 114 /*! \brief 115 Copy constructor allowing the construction of a const pseudo-row 116 from a non-const pseudo-row. 117 Ordinary copy constructor. 118 */ 119 template <typename V> 120 Pseudo_Row(const Pseudo_Row<V>& y); 121 122 //! Destructor. 123 ~Pseudo_Row(); 124 125 //! Subscript operator. 126 U& operator[](dimension_type k) const; 127 128 //! Default constructor: creates an invalid object that has to be assigned. 129 Pseudo_Row(); 130 131 //! Assignment operator. 132 Pseudo_Row& operator=(const Pseudo_Row& y); 133 134 #if !defined(__GNUC__) || __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 0) 135 private: 136 #else 137 // Work around a bug of GCC 4.0.x (and, likely, previous versions). 138 public: 139 #endif 140 141 #if PPL_OR_MATRIX_EXTRA_DEBUG 142 143 //! Private constructor for a Pseudo_Row with size \p s beginning at \p y. 144 Pseudo_Row(U& y, dimension_type s); 145 146 #else // !PPL_OR_MATRIX_EXTRA_DEBUG 147 148 //! Private constructor for a Pseudo_Row beginning at \p y. 149 explicit Pseudo_Row(U& y); 150 151 #endif // !PPL_OR_MATRIX_EXTRA_DEBUG 152 153 //! Holds a reference to the beginning of this row. 154 U* first; 155 156 #if !defined(__GNUC__) || __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ > 0) 157 #else 158 // Work around a bug of GCC 4.0.x (and, likely, previous versions). 159 private: 160 #endif 161 162 #if PPL_OR_MATRIX_EXTRA_DEBUG 163 164 //! The size of the row. 165 dimension_type size_; 166 167 //! Returns the size of the row. 168 dimension_type size() const; 169 170 #endif // PPL_OR_MATRIX_EXTRA_DEBUG 171 172 // FIXME: the EDG-based compilers (such as Comeau and Intel) 173 // are here in wild disagreement with GCC: what is a legal friend 174 // declaration for one, is illegal for the others. 175 #ifdef __EDG__ 176 template <typename V> template<typename W> 177 friend class OR_Matrix<V>::Pseudo_Row; 178 template <typename V> template<typename W> 179 friend class OR_Matrix<V>::any_row_iterator; 180 #else 181 template <typename V> friend class Pseudo_Row; 182 template <typename V> friend class any_row_iterator; 183 #endif 184 185 friend class OR_Matrix; 186 }; // class Pseudo_Row 187 188 public: 189 //! A (non const) reference to a matrix's row. 190 typedef Pseudo_Row<T> row_reference_type; 191 192 //! A const reference to a matrix's row. 193 typedef Pseudo_Row<const T> const_row_reference_type; 194 195 private: 196 /*! \brief 197 A template class to derive both OR_Matrix::iterator 198 and OR_Matrix::const_iterator. 199 */ 200 template <typename U> 201 class any_row_iterator { 202 public: 203 typedef std::random_access_iterator_tag iterator_category; 204 typedef Pseudo_Row<U> value_type; 205 typedef long difference_type; 206 typedef const Pseudo_Row<U>* pointer; 207 typedef const Pseudo_Row<U>& reference; 208 209 //! Constructor to build past-the-end objects. 210 any_row_iterator(dimension_type n_rows); 211 212 /*! \brief 213 Builds an iterator pointing at the beginning of an OR_Matrix whose 214 first element is \p base; 215 */ 216 explicit any_row_iterator(U& base); 217 218 /*! \brief 219 Copy constructor allowing the construction of a const_iterator 220 from a non-const iterator. 221 */ 222 template <typename V> 223 any_row_iterator(const any_row_iterator<V>& y); 224 225 /*! \brief 226 Assignment operator allowing the assignment of a non-const iterator 227 to a const_iterator. 228 */ 229 template <typename V> 230 any_row_iterator& operator=(const any_row_iterator<V>& y); 231 232 //! Dereference operator. 233 reference operator*() const; 234 235 //! Indirect member selector. 236 pointer operator->() const; 237 238 //! Prefix increment operator. 239 any_row_iterator& operator++(); 240 241 //! Postfix increment operator. 242 any_row_iterator operator++(int); 243 244 //! Prefix decrement operator. 245 any_row_iterator& operator--(); 246 247 //! Postfix decrement operator. 248 any_row_iterator operator--(int); 249 250 //! Subscript operator. 251 reference operator[](difference_type m) const; 252 253 //! Assignment-increment operator. 254 any_row_iterator& operator+=(difference_type m); 255 256 //! Assignment-increment operator for \p m of unsigned type. 257 template <typename Unsigned> 258 typename Enable_If<(static_cast<Unsigned>(-1) > 0), any_row_iterator&>::type 259 operator+=(Unsigned m); 260 261 //! Assignment-decrement operator. 262 any_row_iterator& operator-=(difference_type m); 263 264 //! Returns the difference between \p *this and \p y. 265 difference_type operator-(const any_row_iterator& y) const; 266 267 //! Returns the sum of \p *this and \p m. 268 any_row_iterator operator+(difference_type m) const; 269 270 //! Returns the sum of \p *this and \p m, for \p m of unsigned type. 271 template <typename Unsigned> 272 typename Enable_If<(static_cast<Unsigned>(-1) > 0), any_row_iterator>::type 273 operator+(Unsigned m) const; 274 275 //! Returns the difference of \p *this and \p m. 276 any_row_iterator operator-(difference_type m) const; 277 278 //! Returns <CODE>true</CODE> if and only if \p *this is equal to \p y. 279 bool operator==(const any_row_iterator& y) const; 280 281 /*! \brief 282 Returns <CODE>true</CODE> if and only if \p *this 283 is different from \p y. 284 */ 285 bool operator!=(const any_row_iterator& y) const; 286 287 //! Returns <CODE>true</CODE> if and only if \p *this is less than \p y. 288 bool operator<(const any_row_iterator& y) const; 289 290 /*! \brief 291 Returns <CODE>true</CODE> if and only if \p *this is less than 292 or equal to \p y. 293 */ 294 bool operator<=(const any_row_iterator& y) const; 295 296 //! Returns <CODE>true</CODE> if and only if \p *this is greater than \p y. 297 bool operator>(const any_row_iterator& y) const; 298 299 /*! \brief 300 Returns <CODE>true</CODE> if and only if \p *this is greater than 301 or equal to \p y. 302 */ 303 bool operator>=(const any_row_iterator& y) const; 304 305 dimension_type row_size() const; 306 307 dimension_type index() const; 308 309 private: 310 //! Represents the beginning of a row. 311 Pseudo_Row<U> value; 312 313 //! External index. 314 dimension_type e; 315 316 //! Internal index: <CODE>i = (e+1)*(e+1)/2</CODE>. 317 dimension_type i; 318 319 // FIXME: the EDG-based compilers (such as Comeau and Intel) 320 // are here in wild disagreement with GCC: what is a legal friend 321 // declaration for one, is illegal for the others. 322 #ifdef __EDG__ 323 template <typename V> template<typename W> 324 friend class OR_Matrix<V>::any_row_iterator; 325 #else 326 template <typename V> friend class any_row_iterator; 327 #endif 328 }; // class any_row_iterator 329 330 public: 331 //! A (non const) row iterator. 332 typedef any_row_iterator<T> row_iterator; 333 334 //! A const row iterator. 335 typedef any_row_iterator<const T> const_row_iterator; 336 337 //! A (non const) element iterator. 338 typedef typename DB_Row<T>::iterator element_iterator; 339 340 //! A const element iterator. 341 typedef typename DB_Row<T>::const_iterator const_element_iterator; 342 343 public: 344 //! Returns the maximum number of rows of a OR_Matrix. 345 static dimension_type max_num_rows(); 346 347 //! Builds a matrix with specified dimensions. 348 /*! 349 \param num_dimensions 350 The space dimension of the matrix that will be created. 351 352 This constructor creates a matrix with \p 2*num_dimensions rows. 353 Each element is initialized to plus infinity. 354 */ 355 OR_Matrix(dimension_type num_dimensions); 356 357 //! Copy constructor. 358 OR_Matrix(const OR_Matrix& y); 359 360 //! Constructs a conservative approximation of \p y. 361 template <typename U> 362 explicit OR_Matrix(const OR_Matrix<U>& y); 363 364 //! Destructor. 365 ~OR_Matrix(); 366 367 //! Assignment operator. 368 OR_Matrix& operator=(const OR_Matrix& y); 369 370 private: 371 template <typename U> friend class OR_Matrix; 372 373 //! Contains the rows of the matrix. 374 /*! 375 A DB_Row which contains the rows of the OR_Matrix 376 inserting each successive row to the end of the vec. 377 To contain all the elements of OR_Matrix the size of the DB_Row 378 is 2*n*(n+1), where the n is the characteristic parameter of 379 OR_Matrix. 380 */ 381 DB_Row<T> vec; 382 383 //! Contains the dimension of the space of the matrix. 384 dimension_type space_dim; 385 386 //! Contains the capacity of \p vec. 387 dimension_type vec_capacity; 388 389 //! Private and not implemented: default construction is not allowed. 390 OR_Matrix(); 391 392 /*! \brief 393 Returns the index into <CODE>vec</CODE> of the first element 394 of the row of index \p k. 395 */ 396 static dimension_type row_first_element_index(dimension_type k); 397 398 public: 399 //! Returns the size of the row of index \p k. 400 static dimension_type row_size(dimension_type k); 401 402 //! Swaps \p *this with \p y. 403 void m_swap(OR_Matrix& y); 404 405 //! Makes the matrix grow by adding more space dimensions. 406 /*! 407 \param new_dim 408 The new dimension of the resized matrix. 409 410 Adds new rows of right dimension to the end if 411 there is enough capacity; otherwise, creates a new matrix, 412 with the specified dimension, copying the old elements 413 in the upper part of the new matrix, which is 414 then assigned to \p *this. 415 Each new element is initialized to plus infinity. 416 */ 417 void grow(dimension_type new_dim); 418 419 //! Makes the matrix shrink by removing the last space dimensions. 420 /*! 421 \param new_dim 422 The new dimension of the resized matrix. 423 424 Erases from matrix to the end the rows with index 425 greater than 2*new_dim-1. 426 */ 427 void shrink(dimension_type new_dim); 428 429 //! Resizes the matrix without worrying about the old contents. 430 /*! 431 \param new_dim 432 The new dimension of the resized matrix. 433 434 If the new dimension is greater than the old one, it adds new rows 435 of right dimension to the end if there is enough capacity; otherwise, 436 it creates a new matrix, with the specified dimension, which is 437 then assigned to \p *this. 438 If the new dimension is less than the old one, it erase from the matrix 439 the rows having index greater than 2*new_dim-1 440 */ 441 void resize_no_copy(dimension_type new_dim); 442 443 //! Returns the space-dimension of the matrix. 444 dimension_type space_dimension() const; 445 446 //! Returns the number of rows in the matrix. 447 dimension_type num_rows() const; 448 449 //! \name Subscript operators. 450 //@{ 451 //! Returns a reference to the \p k-th row of the matrix. 452 row_reference_type operator[](dimension_type k); 453 454 //! Returns a constant reference to the \p k-th row of the matrix. 455 const_row_reference_type operator[](dimension_type k) const; 456 //@} 457 458 459 /*! \brief 460 Returns an iterator pointing to the first row, 461 if \p *this is not empty; 462 otherwise, returns the past-the-end const_iterator. 463 */ 464 row_iterator row_begin(); 465 466 //! Returns the past-the-end const_iterator. 467 row_iterator row_end(); 468 469 /*! \brief 470 Returns a const row iterator pointing to the first row, 471 if \p *this is not empty; 472 otherwise, returns the past-the-end const_iterator. 473 */ 474 const_row_iterator row_begin() const; 475 476 //! Returns the past-the-end const row iterator. 477 const_row_iterator row_end() const; 478 479 /*! \brief 480 Returns an iterator pointing to the first element, 481 if \p *this is not empty; 482 otherwise, returns the past-the-end const_iterator. 483 */ 484 element_iterator element_begin(); 485 486 //! Returns the past-the-end const_iterator. 487 element_iterator element_end(); 488 489 /*! \brief 490 Returns a const element iterator pointing to the first element, 491 if \p *this is not empty; 492 otherwise, returns the past-the-end const_iterator. 493 */ 494 const_element_iterator element_begin() const; 495 496 //! Returns the past-the-end const element iterator. 497 const_element_iterator element_end() const; 498 499 //! Clears the matrix deallocating all its rows. 500 void clear(); 501 502 PPL_OUTPUT_DECLARATIONS 503 504 /*! \brief 505 Loads from \p s an ASCII representation (as produced by 506 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 507 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 508 */ 509 bool ascii_load(std::istream& s); 510 511 //! Returns the total size in bytes of the memory occupied by \p *this. 512 memory_size_type total_memory_in_bytes() const; 513 514 //! Returns the size in bytes of the memory managed by \p *this. 515 memory_size_type external_memory_in_bytes() const; 516 517 friend bool operator==<T>(const OR_Matrix<T>& x, const OR_Matrix<T>& y); 518 519 //! Checks if all the invariants are satisfied. 520 bool OK() const; 521 }; 522 523 namespace Parma_Polyhedra_Library { 524 525 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 526 //! Swaps \p x with \p y. 527 /*! \relates OR_Matrix */ 528 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 529 template <typename T> 530 void swap(OR_Matrix<T>& x, OR_Matrix<T>& y); 531 532 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 533 //! Returns <CODE>true</CODE> if and only if \p x and \p y are different. 534 /*! \relates OR_Matrix */ 535 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 536 template <typename T> 537 bool operator!=(const OR_Matrix<T>& x, const OR_Matrix<T>& y); 538 539 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 540 //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. 541 /*! \relates OR_Matrix 542 If the rectilinear distance between \p x and \p y is defined, 543 stores an approximation of it into to \p r 544 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 545 546 The direction of the approximation is specified by \p dir. 547 548 All computations are performed using the temporary variables 549 \p tmp0, \p tmp1 and \p tmp2. 550 */ 551 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 552 template <typename Temp, typename To, typename T> 553 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 554 const OR_Matrix<T>& x, 555 const OR_Matrix<T>& y, 556 Rounding_Dir dir, 557 Temp& tmp0, 558 Temp& tmp1, 559 Temp& tmp2); 560 561 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 562 //! Computes the euclidean distance between \p x and \p y. 563 /*! \relates OR_Matrix 564 If the Euclidean distance between \p x and \p y is defined, 565 stores an approximation of it into to \p r 566 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 567 568 The direction of the approximation is specified by \p dir. 569 570 All computations are performed using the temporary variables 571 \p tmp0, \p tmp1 and \p tmp2. 572 */ 573 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 574 template <typename Temp, typename To, typename T> 575 bool euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 576 const OR_Matrix<T>& x, 577 const OR_Matrix<T>& y, 578 Rounding_Dir dir, 579 Temp& tmp0, 580 Temp& tmp1, 581 Temp& tmp2); 582 583 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 584 //! Computes the \f$L_\infty\f$ distance between \p x and \p y. 585 /*! \relates OR_Matrix 586 If the \f$L_\infty\f$ distance between \p x and \p y is defined, 587 stores an approximation of it into to \p r 588 and returns <CODE>true</CODE>; returns <CODE>false</CODE> otherwise. 589 590 The direction of the approximation is specified by \p dir. 591 592 All computations are performed using the temporary variables 593 \p tmp0, \p tmp1 and \p tmp2. 594 */ 595 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 596 template <typename Temp, typename To, typename T> 597 bool l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 598 const OR_Matrix<T>& x, 599 const OR_Matrix<T>& y, 600 Rounding_Dir dir, 601 Temp& tmp0, 602 Temp& tmp1, 603 Temp& tmp2); 604 605 } // namespace Parma_Polyhedra_Library 606 607 #include "OR_Matrix_inlines.hh" 608 #include "OR_Matrix_templates.hh" 609 610 #endif // !defined(PPL_OR_Matrix_defs_hh) 611