1 /* Dense_Row 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_Dense_Row_defs_hh 25 #define PPL_Dense_Row_defs_hh 1 26 27 #include "Dense_Row_types.hh" 28 29 #include "globals_defs.hh" 30 31 #include "Sparse_Row_types.hh" 32 #include "Coefficient_defs.hh" 33 #include <memory> 34 #include <vector> 35 #include <limits> 36 #include <cstddef> 37 38 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 39 //! A finite sequence of coefficients. 40 /*! \ingroup PPL_CXX_interface */ 41 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 42 class Parma_Polyhedra_Library::Dense_Row { 43 public: 44 class iterator; 45 class const_iterator; 46 47 //! Constructs an empty row. 48 Dense_Row(); 49 50 explicit Dense_Row(const Sparse_Row& row); 51 52 //! Tight constructor: resizing may require reallocation. 53 /*! 54 Constructs a row with size and capacity \p sz. 55 */ 56 Dense_Row(dimension_type sz); 57 58 //! Sizing constructor with capacity. 59 /*! 60 \param sz 61 The size of the row that will be constructed; 62 63 \param capacity 64 The capacity of the row that will be constructed; 65 66 The row that is constructed has storage for \p capacity elements, 67 \p sz of which are default-constructed now. 68 */ 69 Dense_Row(dimension_type sz, dimension_type capacity); 70 71 //! Ordinary copy constructor. 72 Dense_Row(const Dense_Row& y); 73 74 //! Copy constructor with specified capacity. 75 /*! 76 It is assumed that \p capacity is greater than or equal to 77 the size of \p y. 78 */ 79 Dense_Row(const Dense_Row& y, dimension_type capacity); 80 81 //! Copy constructor with specified size and capacity. 82 /*! 83 It is assumed that \p sz is less than or equal to \p capacity. 84 */ 85 Dense_Row(const Dense_Row& y, dimension_type sz, dimension_type capacity); 86 87 //! Copy constructor with specified size and capacity from a Sparse_Row. 88 /*! 89 It is assumed that \p sz is less than or equal to \p capacity. 90 */ 91 Dense_Row(const Sparse_Row& y, dimension_type sz, dimension_type capacity); 92 93 //! Destructor. 94 ~Dense_Row(); 95 96 //! Assignment operator. 97 Dense_Row& operator=(const Dense_Row& y); 98 99 //! Assignment operator. 100 Dense_Row& operator=(const Sparse_Row& y); 101 102 //! Swaps \p *this with \p y. 103 void m_swap(Dense_Row& y); 104 105 //! Resizes the row to \p sz. 106 void resize(dimension_type sz); 107 108 //! Resizes the row to \p sz, with capacity \p capacity. 109 void resize(dimension_type sz, dimension_type capacity); 110 111 //! Resets all the elements of this row. 112 void clear(); 113 114 //! Adds \p n zeroes before index \p i. 115 /*! 116 \param n 117 The number of zeroes that will be added to the row. 118 119 \param i 120 The index of the element before which the zeroes will be added. 121 122 Existing elements with index greater than or equal to \p i are shifted 123 to the right by \p n positions. The size is increased by \p n. 124 125 Existing iterators are invalidated. 126 */ 127 void add_zeroes_and_shift(dimension_type n, dimension_type i); 128 129 //! Expands the row to size \p new_size. 130 /*! 131 Adds new positions to the implementation of the row 132 obtaining a new row with size \p new_size. 133 It is assumed that \p new_size is between the current size 134 and capacity of the row. 135 */ 136 void expand_within_capacity(dimension_type new_size); 137 138 //! Shrinks the row by erasing elements at the end. 139 /*! 140 Destroys elements of the row implementation 141 from position \p new_size to the end. 142 It is assumed that \p new_size is not greater than the current size. 143 */ 144 void shrink(dimension_type new_size); 145 146 //! Returns the size() of the largest possible Dense_Row. 147 static dimension_type max_size(); 148 149 //! Gives the number of coefficients currently in use. 150 dimension_type size() const; 151 152 //! \name Subscript operators 153 //@{ 154 //! Returns a reference to the element of the row indexed by \p k. 155 Coefficient& operator[](dimension_type k); 156 157 //! Returns a constant reference to the element of the row indexed by \p k. 158 Coefficient_traits::const_reference operator[](dimension_type k) const; 159 //@} // Subscript operators 160 161 //! Normalizes the modulo of coefficients so that they are mutually prime. 162 /*! 163 Computes the Greatest Common Divisor (GCD) among the elements of 164 the row and normalizes them by the GCD itself. 165 */ 166 void normalize(); 167 168 //! Swaps the i-th element with the j-th element. 169 //! Provided for compatibility with Sparse_Row 170 void swap_coefficients(dimension_type i, dimension_type j); 171 172 //! Swaps the element pointed to by i with the element pointed to by j. 173 //! Provided for compatibility with Sparse_Row 174 void swap_coefficients(iterator i, iterator j); 175 176 iterator begin(); 177 const_iterator begin() const; 178 179 iterator end(); 180 const_iterator end() const; 181 182 //! Resets the i-th element to 0. 183 //! Provided for compatibility with Sparse_Row 184 void reset(dimension_type i); 185 186 //! Resets the elements [first,last) to 0. 187 //! Provided for compatibility with Sparse_Row 188 void reset(dimension_type first, dimension_type last); 189 190 //! Resets the element pointed to by itr to 0. 191 //! Provided for compatibility with Sparse_Row. 192 iterator reset(iterator itr); 193 194 //! Gets the i-th element. 195 //! Provided for compatibility with Sparse_Row. 196 Coefficient_traits::const_reference get(dimension_type i) const; 197 198 //! Provided for compatibility with Sparse_Row. 199 iterator find(dimension_type i); 200 201 //! Provided for compatibility with Sparse_Row. 202 const_iterator find(dimension_type i) const; 203 204 //! Provided for compatibility with Sparse_Row. 205 iterator find(iterator itr, dimension_type i); 206 207 //! Provided for compatibility with Sparse_Row. 208 const_iterator find(const_iterator itr, dimension_type i) const; 209 210 //! Provided for compatibility with Sparse_Row. 211 iterator lower_bound(dimension_type i); 212 213 //! Provided for compatibility with Sparse_Row. 214 const_iterator lower_bound(dimension_type i) const; 215 216 //! Provided for compatibility with Sparse_Row. 217 iterator lower_bound(iterator itr, dimension_type i); 218 219 //! Provided for compatibility with Sparse_Row. 220 const_iterator lower_bound(const_iterator itr, dimension_type i) const; 221 222 //! Provided for compatibility with Sparse_Row. 223 iterator insert(dimension_type i, Coefficient_traits::const_reference x); 224 225 //! Provided for compatibility with Sparse_Row. 226 iterator insert(dimension_type i); 227 228 //! Provided for compatibility with Sparse_Row. 229 iterator insert(iterator itr, dimension_type i, 230 Coefficient_traits::const_reference x); 231 232 //! Provided for compatibility with Sparse_Row. 233 iterator insert(iterator itr, dimension_type i); 234 235 //! Calls g(x[i],y[i]), for each i. 236 /*! 237 \param y 238 The row that will be combined with *this. 239 240 \param f 241 A functor that should take a Coefficient&. 242 f(c1) must be equivalent to g(c1, 0). 243 244 \param g 245 A functor that should take a Coefficient& and a 246 Coefficient_traits::const_reference. 247 g(c1, c2) must do nothing when c1 is zero. 248 249 This method takes \f$O(n)\f$ time. 250 251 \note 252 The functors will only be called when necessary, assuming the requested 253 properties hold. 254 255 \see combine_needs_second 256 \see combine 257 */ 258 template <typename Func1, typename Func2> 259 void combine_needs_first(const Dense_Row& y, 260 const Func1& f, const Func2& g); 261 262 //! Calls g(x[i],y[i]), for each i. 263 /*! 264 \param y 265 The row that will be combined with *this. 266 267 \param g 268 A functor that should take a Coefficient& and a 269 Coefficient_traits::const_reference. 270 g(c1, 0) must do nothing, for every c1. 271 272 \param h 273 A functor that should take a Coefficient& and a 274 Coefficient_traits::const_reference. 275 h(c1, c2) must be equivalent to g(c1, c2) when c1 is zero. 276 277 This method takes \f$O(n)\f$ time. 278 279 \note 280 The functors will only be called when necessary, assuming the requested 281 properties hold. 282 283 \see combine_needs_first 284 \see combine 285 */ 286 template <typename Func1, typename Func2> 287 void combine_needs_second(const Dense_Row& y, 288 const Func1& g, const Func2& h); 289 290 //! Calls g(x[i],y[i]), for each i. 291 /*! 292 \param y 293 The row that will be combined with *this. 294 295 \param f 296 A functor that should take a Coefficient&. 297 f(c1) must be equivalent to g(c1, 0). 298 299 \param g 300 A functor that should take a Coefficient& and a 301 Coefficient_traits::const_reference. 302 g(c1, c2) must do nothing when both c1 and c2 are zero. 303 304 \param h 305 A functor that should take a Coefficient& and a 306 Coefficient_traits::const_reference. 307 h(c1, c2) must be equivalent to g(c1, c2) when c1 is zero. 308 309 This method takes \f$O(n)\f$ time. 310 311 \note 312 The functors will only be called when necessary, assuming the requested 313 properties hold. 314 315 \see combine_needs_first 316 \see combine_needs_second 317 */ 318 template <typename Func1, typename Func2, typename Func3> 319 void combine(const Dense_Row& y, 320 const Func1& f, const Func2& g, const Func3& h); 321 322 //! Executes <CODE>(*this)[i] = (*this)[i]*coeff1 + y[i]*coeff2</CODE>, for 323 //! each i. 324 /*! 325 \param y 326 The row that will be combined with *this. 327 328 \param coeff1 329 The coefficient used for elements of *this. 330 It must not be 0. 331 332 \param coeff2 333 The coefficient used for elements of y. 334 It must not be 0. 335 336 This method takes \f$O(n)\f$ time. 337 338 \see combine_needs_first 339 \see combine_needs_second 340 \see combine 341 */ 342 void linear_combine(const Dense_Row& y, 343 Coefficient_traits::const_reference coeff1, 344 Coefficient_traits::const_reference coeff2); 345 346 //! Equivalent to <CODE>(*this)[i] = (*this)[i] * c1 + y[i] * c2</CODE>, 347 //! for each i in [start, end). 348 /*! 349 This method detects when coeff1==1 and/or coeff2==1 or coeff2==-1 in 350 order to save some work. 351 352 coeff1 and coeff2 must not be 0. 353 */ 354 void linear_combine(const Dense_Row& y, 355 Coefficient_traits::const_reference c1, 356 Coefficient_traits::const_reference c2, 357 dimension_type start, dimension_type end); 358 359 PPL_OUTPUT_DECLARATIONS 360 361 /*! \brief 362 Loads from \p s an ASCII representation (as produced by 363 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 364 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 365 */ 366 bool ascii_load(std::istream& s); 367 368 /*! \brief 369 Returns a lower bound to the total size in bytes of the memory 370 occupied by \p *this. 371 */ 372 memory_size_type total_memory_in_bytes() const; 373 374 /*! \brief 375 Returns a lower bound to the size in bytes of the memory 376 managed by \p *this. 377 */ 378 memory_size_type external_memory_in_bytes() const; 379 380 /*! \brief 381 Returns the total size in bytes of the memory occupied by \p *this, 382 provided the capacity of \p *this is given by \p capacity. 383 */ 384 memory_size_type total_memory_in_bytes(dimension_type capacity) const; 385 386 /*! \brief 387 Returns the size in bytes of the memory managed by \p *this, 388 provided the capacity of \p *this is given by \p capacity. 389 */ 390 memory_size_type external_memory_in_bytes(dimension_type capacity) const; 391 392 //! Checks if all the invariants are satisfied. 393 bool OK() const; 394 395 /*! \brief 396 Checks if all the invariants are satisfied and that the actual 397 size matches the value provided as argument. 398 */ 399 bool OK(dimension_type row_size) const; 400 401 private: 402 void init(const Sparse_Row& row); 403 404 void destroy(); 405 406 struct Impl { 407 408 Impl(); 409 410 ~Impl(); 411 412 //! The number of coefficients in the row. 413 dimension_type size; 414 415 //! The capacity of the row. 416 dimension_type capacity; 417 418 //! The allocator used to allocate/deallocate vec. 419 std::allocator<Coefficient> coeff_allocator; 420 421 //! The vector of coefficients. 422 //! An empty vector may be stored as NULL instead of using a valid pointer. 423 Coefficient* vec; 424 }; 425 426 Impl impl; 427 428 //! Returns the capacity of the row. 429 dimension_type capacity() const; 430 }; 431 432 class Parma_Polyhedra_Library::Dense_Row::iterator { 433 public: 434 435 typedef std::bidirectional_iterator_tag iterator_category; 436 typedef Coefficient value_type; 437 typedef std::ptrdiff_t difference_type; 438 typedef value_type* pointer; 439 typedef value_type& reference; 440 441 iterator(); 442 iterator(Dense_Row& r, dimension_type i); 443 444 Coefficient& operator*(); 445 Coefficient_traits::const_reference operator*() const; 446 447 //! Returns the index of the element pointed to by \c *this. 448 /*! 449 If itr is a valid iterator for row, <CODE>row[itr.index()]</CODE> is 450 equivalent to *itr. 451 452 \returns the index of the element pointed to by \c *this. 453 */ 454 dimension_type index() const; 455 456 iterator& operator++(); 457 iterator operator++(int); 458 459 iterator& operator--(); 460 iterator operator--(int); 461 462 bool operator==(const iterator& x) const; 463 bool operator!=(const iterator& x) const; 464 465 operator const_iterator() const; 466 467 bool OK() const; 468 469 private: 470 Dense_Row* row; 471 dimension_type idx; 472 }; 473 474 class Parma_Polyhedra_Library::Dense_Row::const_iterator { 475 public: 476 477 typedef const Coefficient value_type; 478 typedef std::ptrdiff_t difference_type; 479 typedef value_type* pointer; 480 typedef Coefficient_traits::const_reference reference; 481 482 const_iterator(); 483 const_iterator(const Dense_Row& r, dimension_type i); 484 485 Coefficient_traits::const_reference operator*() const; 486 487 //! Returns the index of the element pointed to by \c *this. 488 /*! 489 If itr is a valid iterator for row, <CODE>row[itr.index()]</CODE> is 490 equivalent to *itr. 491 492 \returns the index of the element pointed to by \c *this. 493 */ 494 dimension_type index() const; 495 496 const_iterator& operator++(); 497 const_iterator operator++(int); 498 499 const_iterator& operator--(); 500 const_iterator operator--(int); 501 502 bool operator==(const const_iterator& x) const; 503 bool operator!=(const const_iterator& x) const; 504 505 bool OK() const; 506 507 private: 508 const Dense_Row* row; 509 dimension_type idx; 510 }; 511 512 513 namespace Parma_Polyhedra_Library { 514 515 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 516 //! Swaps \p x with \p y. 517 /*! \relates Dense_Row */ 518 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 519 void swap(Dense_Row& x, Dense_Row& y); 520 521 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 522 //! Swaps objects referred by \p x and \p y. 523 /*! \relates Dense_Row */ 524 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 525 void iter_swap(std::vector<Dense_Row>::iterator x, 526 std::vector<Dense_Row>::iterator y); 527 528 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 529 //! Returns <CODE>true</CODE> if and only if \p x and \p y are equal. 530 /*! \relates Dense_Row */ 531 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 532 bool operator==(const Dense_Row& x, const Dense_Row& y); 533 534 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 535 //! Returns <CODE>true</CODE> if and only if \p x and \p y are different. 536 /*! \relates Dense_Row */ 537 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 538 bool operator!=(const Dense_Row& x, const Dense_Row& y); 539 540 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 541 /*! \relates Dense_Row */ 542 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 543 void linear_combine(Dense_Row& x, const Dense_Row& y, 544 Coefficient_traits::const_reference coeff1, 545 Coefficient_traits::const_reference coeff2); 546 547 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 548 //! Equivalent to <CODE>x[i] = x[i] * c1 + y[i] * c2</CODE>, 549 //! for each i in [start, end). 550 /*! \relates Dense_Row */ 551 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 552 void linear_combine(Dense_Row& x, const Dense_Row& y, 553 Coefficient_traits::const_reference c1, 554 Coefficient_traits::const_reference c2, 555 dimension_type start, dimension_type end); 556 557 } // namespace Parma_Polyhedra_Library 558 559 #include "Dense_Row_inlines.hh" 560 #include "Dense_Row_templates.hh" 561 562 #endif // !defined(PPL_Dense_Row_defs_hh) 563