1 /* Linear_Expression 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_Linear_Expression_defs_hh 25 #define PPL_Linear_Expression_defs_hh 1 26 27 #include "Linear_Expression_types.hh" 28 29 #include "Constraint_types.hh" 30 #include "Generator_types.hh" 31 #include "Congruence_types.hh" 32 #include "Grid_Generator_types.hh" 33 #include "Linear_System_types.hh" 34 #include "Constraint_System_types.hh" 35 #include "Congruence_System_types.hh" 36 #include "Coefficient_types.hh" 37 #include "Polyhedron_types.hh" 38 #include "Grid_types.hh" 39 #include "PIP_Problem_types.hh" 40 #include "BHRZ03_Certificate_types.hh" 41 #include "Scalar_Products_types.hh" 42 #include "MIP_Problem_types.hh" 43 #include "Box_types.hh" 44 #include "BD_Shape_types.hh" 45 #include "Octagonal_Shape_types.hh" 46 #include "termination_types.hh" 47 48 #include "Expression_Adapter_defs.hh" 49 #include "Expression_Hide_Inhomo_types.hh" 50 #include "Expression_Hide_Last_types.hh" 51 52 #include "Linear_Expression_Interface_defs.hh" 53 #include "Variable_defs.hh" 54 #include <cstddef> 55 56 namespace Parma_Polyhedra_Library { 57 58 // Put them in the namespace here to declare them friend later. 59 60 //! Returns the linear expression \p e1 + \p e2. 61 /*! \relates Linear_Expression */ 62 Linear_Expression 63 operator+(const Linear_Expression& e1, const Linear_Expression& e2); 64 65 //! Returns the linear expression \p v + \p w. 66 /*! \relates Linear_Expression */ 67 Linear_Expression 68 operator+(Variable v, Variable w); 69 70 //! Returns the linear expression \p v + \p e. 71 /*! \relates Linear_Expression */ 72 Linear_Expression 73 operator+(Variable v, const Linear_Expression& e); 74 75 //! Returns the linear expression \p e + \p v. 76 /*! \relates Linear_Expression */ 77 Linear_Expression 78 operator+(const Linear_Expression& e, Variable v); 79 80 //! Returns the linear expression \p n + \p e. 81 /*! \relates Linear_Expression */ 82 Linear_Expression 83 operator+(Coefficient_traits::const_reference n, const Linear_Expression& e); 84 85 //! Returns the linear expression \p e + \p n. 86 /*! \relates Linear_Expression */ 87 Linear_Expression 88 operator+(const Linear_Expression& e, Coefficient_traits::const_reference n); 89 90 //! Returns the linear expression \p e. 91 /*! \relates Linear_Expression */ 92 Linear_Expression 93 operator+(const Linear_Expression& e); 94 95 //! Returns the linear expression - \p e. 96 /*! \relates Linear_Expression */ 97 Linear_Expression 98 operator-(const Linear_Expression& e); 99 100 //! Returns the linear expression \p e1 - \p e2. 101 /*! \relates Linear_Expression */ 102 Linear_Expression 103 operator-(const Linear_Expression& e1, const Linear_Expression& e2); 104 105 //! Returns the linear expression \p v - \p w. 106 /*! \relates Linear_Expression */ 107 Linear_Expression 108 operator-(Variable v, Variable w); 109 110 //! Returns the linear expression \p v - \p e. 111 /*! \relates Linear_Expression */ 112 Linear_Expression 113 operator-(Variable v, const Linear_Expression& e); 114 115 //! Returns the linear expression \p e - \p v. 116 /*! \relates Linear_Expression */ 117 Linear_Expression 118 operator-(const Linear_Expression& e, Variable v); 119 120 //! Returns the linear expression \p n - \p e. 121 /*! \relates Linear_Expression */ 122 Linear_Expression 123 operator-(Coefficient_traits::const_reference n, const Linear_Expression& e); 124 125 //! Returns the linear expression \p e - \p n. 126 /*! \relates Linear_Expression */ 127 Linear_Expression 128 operator-(const Linear_Expression& e, Coefficient_traits::const_reference n); 129 130 //! Returns the linear expression \p n * \p e. 131 /*! \relates Linear_Expression */ 132 Linear_Expression 133 operator*(Coefficient_traits::const_reference n, const Linear_Expression& e); 134 135 //! Returns the linear expression \p e * \p n. 136 /*! \relates Linear_Expression */ 137 Linear_Expression 138 operator*(const Linear_Expression& e, Coefficient_traits::const_reference n); 139 140 //! Returns the linear expression \p e1 + \p e2 and assigns it to \p e1. 141 /*! \relates Linear_Expression */ 142 Linear_Expression& 143 operator+=(Linear_Expression& e1, const Linear_Expression& e2); 144 145 //! Returns the linear expression \p e + \p v and assigns it to \p e. 146 /*! \relates Linear_Expression 147 \exception std::length_error 148 Thrown if the space dimension of \p v exceeds 149 <CODE>Linear_Expression::max_space_dimension()</CODE>. 150 */ 151 Linear_Expression& 152 operator+=(Linear_Expression& e, Variable v); 153 154 //! Returns the linear expression \p e + \p n and assigns it to \p e. 155 /*! \relates Linear_Expression */ 156 Linear_Expression& 157 operator+=(Linear_Expression& e, Coefficient_traits::const_reference n); 158 159 //! Returns the linear expression \p e1 - \p e2 and assigns it to \p e1. 160 /*! \relates Linear_Expression */ 161 Linear_Expression& 162 operator-=(Linear_Expression& e1, const Linear_Expression& e2); 163 164 //! Returns the linear expression \p e - \p v and assigns it to \p e. 165 /*! \relates Linear_Expression 166 \exception std::length_error 167 Thrown if the space dimension of \p v exceeds 168 <CODE>Linear_Expression::max_space_dimension()</CODE>. 169 */ 170 Linear_Expression& 171 operator-=(Linear_Expression& e, Variable v); 172 173 //! Returns the linear expression \p e - \p n and assigns it to \p e. 174 /*! \relates Linear_Expression */ 175 Linear_Expression& 176 operator-=(Linear_Expression& e, Coefficient_traits::const_reference n); 177 178 //! Returns the linear expression \p n * \p e and assigns it to \p e. 179 /*! \relates Linear_Expression */ 180 Linear_Expression& 181 operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); 182 183 //! Returns the linear expression \p n / \p e and assigns it to \p e. 184 /*! \relates Linear_Expression */ 185 Linear_Expression& 186 operator/=(Linear_Expression& e, Coefficient_traits::const_reference n); 187 188 //! Assigns to \p e its own negation. 189 /*! \relates Linear_Expression */ 190 void 191 neg_assign(Linear_Expression& e); 192 193 //! Returns the linear expression \p e + \p n * \p v and assigns it to \p e. 194 /*! \relates Linear_Expression */ 195 Linear_Expression& 196 add_mul_assign(Linear_Expression& e, 197 Coefficient_traits::const_reference n, Variable v); 198 199 //! Sums \p e2 multiplied by \p factor into \p e1. 200 /*! \relates Linear_Expression */ 201 void add_mul_assign(Linear_Expression& e1, 202 Coefficient_traits::const_reference factor, 203 const Linear_Expression& e2); 204 205 //! Subtracts \p e2 multiplied by \p factor from \p e1. 206 /*! \relates Linear_Expression */ 207 void sub_mul_assign(Linear_Expression& e1, 208 Coefficient_traits::const_reference factor, 209 const Linear_Expression& e2); 210 211 //! Returns the linear expression \p e - \p n * \p v and assigns it to \p e. 212 /*! \relates Linear_Expression */ 213 Linear_Expression& 214 sub_mul_assign(Linear_Expression& e, 215 Coefficient_traits::const_reference n, Variable v); 216 217 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 218 //! The basic comparison function. 219 /*! \relates Linear_Expression 220 221 \returns -1 or -2 if x is less than y, 0 if they are equal and 1 or 2 is y 222 is greater. The absolute value of the result is 1 if the difference 223 is only in the inhomogeneous terms, 2 otherwise 224 225 The order is a lexicographic. It starts comparing the variables' coefficient, 226 starting from Variable(0), and at the end it compares the inhomogeneous 227 terms. 228 */ 229 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 230 int compare(const Linear_Expression& x, const Linear_Expression& y); 231 232 namespace IO_Operators { 233 234 //! Output operator. 235 /*! \relates Parma_Polyhedra_Library::Linear_Expression */ 236 std::ostream& operator<<(std::ostream& s, const Linear_Expression& e); 237 238 } // namespace IO_Operators 239 240 } // namespace Parma_Polyhedra_Library 241 242 //! A linear expression. 243 /*! \ingroup PPL_CXX_interface 244 An object of the class Linear_Expression represents the linear expression 245 \f[ 246 \sum_{i=0}^{n-1} a_i x_i + b 247 \f] 248 where \f$n\f$ is the dimension of the vector space, 249 each \f$a_i\f$ is the integer coefficient 250 of the \f$i\f$-th variable \f$x_i\f$ 251 and \f$b\f$ is the integer for the inhomogeneous term. 252 253 \par How to build a linear expression. 254 255 Linear expressions are the basic blocks for defining 256 both constraints (i.e., linear equalities or inequalities) 257 and generators (i.e., lines, rays, points and closure points). 258 A full set of functions is defined to provide a convenient interface 259 for building complex linear expressions starting from simpler ones 260 and from objects of the classes Variable and Coefficient: 261 available operators include unary negation, 262 binary addition and subtraction, 263 as well as multiplication by a Coefficient. 264 The space dimension of a linear expression is defined as the maximum 265 space dimension of the arguments used to build it: 266 in particular, the space dimension of a Variable <CODE>x</CODE> 267 is defined as <CODE>x.id()+1</CODE>, 268 whereas all the objects of the class Coefficient have space dimension zero. 269 270 \par Example 271 The following code builds the linear expression \f$4x - 2y - z + 14\f$, 272 having space dimension \f$3\f$: 273 \code 274 Linear_Expression e = 4*x - 2*y - z + 14; 275 \endcode 276 Another way to build the same linear expression is: 277 \code 278 Linear_Expression e1 = 4*x; 279 Linear_Expression e2 = 2*y; 280 Linear_Expression e3 = z; 281 Linear_Expression e = Linear_Expression(14); 282 e += e1 - e2 - e3; 283 \endcode 284 Note that \p e1, \p e2 and \p e3 have space dimension 1, 2 and 3, 285 respectively; also, in the fourth line of code, \p e is created 286 with space dimension zero and then extended to space dimension 3 287 in the fifth line. 288 */ 289 class Parma_Polyhedra_Library::Linear_Expression { 290 public: 291 static const Representation default_representation = SPARSE; 292 293 //! Default constructor: returns a copy of Linear_Expression::zero(). 294 explicit Linear_Expression(Representation r = default_representation); 295 296 /*! \brief Ordinary copy constructor. 297 \note 298 The new expression will have the same representation as \p e 299 (not necessarily the default_representation). 300 */ 301 Linear_Expression(const Linear_Expression& e); 302 303 //! Copy constructor that takes also a Representation. 304 Linear_Expression(const Linear_Expression& e, Representation r); 305 306 // Queried by expression adapters. 307 typedef const Linear_Expression& const_reference; 308 typedef Linear_Expression raw_type; 309 310 /*! \brief Copy constructor from a linear expression adapter. 311 \note 312 The new expression will have the same representation as \p e 313 (not necessarily the default_representation). 314 */ 315 template <typename LE_Adapter> 316 explicit 317 Linear_Expression(const LE_Adapter& e, 318 typename 319 Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base, 320 LE_Adapter>::value, 321 void*>::type = 0); 322 323 /*! \brief Copy constructor from a linear expression adapter that takes a 324 Representation. 325 */ 326 template <typename LE_Adapter> 327 Linear_Expression(const LE_Adapter& e, 328 Representation r, 329 typename 330 Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base, 331 LE_Adapter>::value, 332 void*>::type = 0); 333 334 /*! \brief 335 Copy constructor from a linear expression adapter that takes a 336 space dimension. 337 \note 338 The new expression will have the same representation as \p e 339 (not necessarily default_representation). 340 */ 341 template <typename LE_Adapter> 342 explicit 343 Linear_Expression(const LE_Adapter& e, 344 dimension_type space_dim, 345 typename 346 Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base, 347 LE_Adapter>::value, 348 void*>::type = 0); 349 350 /*! \brief 351 Copy constructor from a linear expression adapter that takes a 352 space dimension and a Representation. 353 */ 354 template <typename LE_Adapter> 355 Linear_Expression(const LE_Adapter& e, 356 dimension_type space_dim, 357 Representation r, 358 typename 359 Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base, 360 LE_Adapter>::value, 361 void*>::type = 0); 362 363 //! Assignment operator. 364 Linear_Expression& operator=(const Linear_Expression& e); 365 366 //! Destructor. 367 ~Linear_Expression(); 368 369 /*! \brief 370 Builds the linear expression corresponding 371 to the inhomogeneous term \p n. 372 */ 373 explicit Linear_Expression(Coefficient_traits::const_reference n, 374 Representation r = default_representation); 375 376 //! Builds the linear expression corresponding to the variable \p v. 377 /*! 378 \exception std::length_error 379 Thrown if the space dimension of \p v exceeds 380 <CODE>Linear_Expression::max_space_dimension()</CODE>. 381 */ 382 Linear_Expression(Variable v, Representation r = default_representation); 383 384 //! Returns the current representation of *this. 385 Representation representation() const; 386 387 //! Converts *this to the specified representation. 388 void set_representation(Representation r); 389 390 //! A const %iterator on the expression (homogeneous) coefficient that are 391 //! nonzero. 392 /*! 393 These iterators are invalidated by operations that modify the expression. 394 */ 395 class const_iterator { 396 private: 397 public: 398 typedef std::bidirectional_iterator_tag iterator_category; 399 typedef const Coefficient value_type; 400 typedef std::ptrdiff_t difference_type; 401 typedef value_type* pointer; 402 typedef Coefficient_traits::const_reference reference; 403 404 //! Constructs an invalid const_iterator. 405 /*! 406 This constructor takes \f$O(1)\f$ time. 407 */ 408 explicit const_iterator(); 409 410 //! The copy constructor. 411 /*! 412 \param i 413 The %iterator that will be copied. 414 415 This constructor takes \f$O(1)\f$ time. 416 */ 417 const_iterator(const const_iterator& i); 418 419 ~const_iterator(); 420 421 //! Swaps \p i with \p *this. 422 /*! 423 \param i 424 The %iterator that will be swapped with \p *this. 425 426 This method takes \f$O(1)\f$ time. 427 */ 428 void m_swap(const_iterator& i); 429 430 //! Assigns \p i to *this . 431 /*! 432 \param i 433 The %iterator that will be assigned into *this. 434 435 This method takes \f$O(1)\f$ time. 436 */ 437 const_iterator& operator=(const const_iterator& i); 438 439 //! Navigates to the next nonzero coefficient. 440 /*! 441 This method takes \f$O(n)\f$ time for dense expressions, and 442 \f$O(1)\f$ time for sparse expressions. 443 */ 444 const_iterator& operator++(); 445 446 //! Navigates to the previous nonzero coefficient. 447 /*! 448 This method takes \f$O(n)\f$ time for dense expressions, and 449 \f$O(1)\f$ time for sparse expressions. 450 */ 451 const_iterator& operator--(); 452 453 //! Returns the current element. 454 reference operator*() const; 455 456 //! Returns the variable of the coefficient pointed to by \c *this. 457 /*! 458 \returns the variable of the coefficient pointed to by \c *this. 459 */ 460 Variable variable() const; 461 462 //! Compares \p *this with \p i. 463 /*! 464 \param i 465 The %iterator that will be compared with *this. 466 */ 467 bool operator==(const const_iterator& i) const; 468 469 //! Compares \p *this with \p i . 470 /*! 471 \param i 472 The %iterator that will be compared with *this. 473 */ 474 bool operator!=(const const_iterator& i) const; 475 476 private: 477 //! Constructor from a const_iterator_interface*. 478 //! The new object takes ownership of the dynamic object. 479 const_iterator(Linear_Expression_Interface::const_iterator_interface* i); 480 481 Linear_Expression_Interface::const_iterator_interface* itr; 482 483 friend class Linear_Expression; 484 }; 485 486 //! Returns an iterator that points to the first nonzero coefficient in the 487 //! expression. 488 const_iterator begin() const; 489 490 //! Returns an iterator that points to the last nonzero coefficient in the 491 //! expression. 492 const_iterator end() const; 493 494 //! Returns an iterator that points to the first nonzero coefficient of a 495 //! variable bigger than or equal to v. 496 const_iterator lower_bound(Variable v) const; 497 498 //! Returns the maximum space dimension a Linear_Expression can handle. 499 static dimension_type max_space_dimension(); 500 501 //! Returns the dimension of the vector space enclosing \p *this. 502 dimension_type space_dimension() const; 503 504 //! Sets the dimension of the vector space enclosing \p *this to \p n . 505 void set_space_dimension(dimension_type n); 506 507 //! Returns the coefficient of \p v in \p *this. 508 Coefficient_traits::const_reference coefficient(Variable v) const; 509 510 //! Sets the coefficient of \p v in \p *this to \p n. 511 void set_coefficient(Variable v, 512 Coefficient_traits::const_reference n); 513 514 //! Returns the inhomogeneous term of \p *this. 515 Coefficient_traits::const_reference inhomogeneous_term() const; 516 517 //! Sets the inhomogeneous term of \p *this to \p n. 518 void set_inhomogeneous_term(Coefficient_traits::const_reference n); 519 520 //! Linearly combines \p *this with \p y so that the coefficient of \p v 521 //! is 0. 522 /*! 523 \param y 524 The expression that will be combined with \p *this object; 525 526 \param v 527 The variable whose coefficient has to become \f$0\f$. 528 529 Computes a linear combination of \p *this and \p y having 530 the coefficient of variable \p v equal to \f$0\f$. Then it assigns 531 the resulting expression to \p *this. 532 533 \p *this and \p y must have the same space dimension. 534 */ 535 void linear_combine(const Linear_Expression& y, Variable v); 536 537 //! Equivalent to <CODE>*this = *this * c1 + y * c2</CODE>, but assumes that 538 //! c1 and c2 are not 0. 539 void linear_combine(const Linear_Expression& y, 540 Coefficient_traits::const_reference c1, 541 Coefficient_traits::const_reference c2); 542 543 //! Equivalent to <CODE>*this = *this * c1 + y * c2</CODE>. 544 //! c1 and c2 may be 0. 545 void linear_combine_lax(const Linear_Expression& y, 546 Coefficient_traits::const_reference c1, 547 Coefficient_traits::const_reference c2); 548 549 //! Swaps the coefficients of the variables \p v1 and \p v2 . 550 void swap_space_dimensions(Variable v1, Variable v2); 551 552 //! Removes all the specified dimensions from the expression. 553 /*! 554 The space dimension of the variable with the highest space 555 dimension in \p vars must be at most the space dimension 556 of \p this. 557 */ 558 void remove_space_dimensions(const Variables_Set& vars); 559 560 //! Shift by \p n positions the coefficients of variables, starting from 561 //! the coefficient of \p v. This increases the space dimension by \p n. 562 void shift_space_dimensions(Variable v, dimension_type n); 563 564 //! Permutes the space dimensions of the expression. 565 /*! 566 \param cycle 567 A vector representing a cycle of the permutation according to which the 568 space dimensions must be rearranged. 569 570 The \p cycle vector represents a cycle of a permutation of space 571 dimensions. 572 For example, the permutation 573 \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be 574 represented by the vector containing \f$ x_1, x_2, x_3 \f$. 575 */ 576 void permute_space_dimensions(const std::vector<Variable>& cycle); 577 578 //! Returns <CODE>true</CODE> if and only if \p *this is \f$0\f$. 579 bool is_zero() const; 580 581 /*! \brief 582 Returns <CODE>true</CODE> if and only if all the homogeneous 583 terms of \p *this are \f$0\f$. 584 */ 585 bool all_homogeneous_terms_are_zero() const; 586 587 //! Initializes the class. 588 static void initialize(); 589 590 //! Finalizes the class. 591 static void finalize(); 592 593 //! Returns the (zero-dimension space) constant 0. 594 static const Linear_Expression& zero(); 595 596 /*! \brief 597 Returns a lower bound to the total size in bytes of the memory 598 occupied by \p *this. 599 */ 600 memory_size_type total_memory_in_bytes() const; 601 602 //! Returns the size in bytes of the memory managed by \p *this. 603 memory_size_type external_memory_in_bytes() const; 604 605 //! Checks if all the invariants are satisfied. 606 bool OK() const; 607 608 PPL_OUTPUT_DECLARATIONS 609 610 /*! \brief 611 Loads from \p s an ASCII representation (as produced by 612 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 613 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 614 */ 615 bool ascii_load(std::istream& s); 616 617 //! Swaps \p *this with \p y. 618 void m_swap(Linear_Expression& y); 619 620 //! Copy constructor with a specified space dimension. 621 Linear_Expression(const Linear_Expression& e, dimension_type space_dim); 622 623 //! Copy constructor with a specified space dimension and representation. 624 Linear_Expression(const Linear_Expression& e, dimension_type space_dim, 625 Representation r); 626 627 //! Returns \p true if *this is equal to \p x. 628 //! Note that (*this == x) has a completely different meaning. 629 bool is_equal_to(const Linear_Expression& x) const; 630 631 //! Normalizes the modulo of the coefficients and of the inhomogeneous term 632 //! so that they are mutually prime. 633 /*! 634 Computes the Greatest Common Divisor (GCD) among the coefficients 635 and the inhomogeneous term and normalizes them by the GCD itself. 636 */ 637 void normalize(); 638 639 //! Ensures that the first nonzero homogeneous coefficient is positive, 640 //! by negating the row if necessary. 641 void sign_normalize(); 642 643 /*! \brief 644 Returns <CODE>true</CODE> if the coefficient of each variable in 645 \p vars[i] is \f$0\f$. 646 */ 647 bool all_zeroes(const Variables_Set& vars) const; 648 649 private: 650 /*! \brief 651 Holds (between class initialization and finalization) a pointer to 652 the (zero-dimension space) constant 0. 653 */ 654 static const Linear_Expression* zero_p; 655 656 Linear_Expression_Interface* impl; 657 658 //! Implementation sizing constructor. 659 /*! 660 The bool parameter is just to avoid problems with 661 the constructor Linear_Expression(Coefficient_traits::const_reference n). 662 */ 663 Linear_Expression(dimension_type space_dim, bool, 664 Representation r = default_representation); 665 666 // NOTE: This method is public, but it's not exposed in Linear_Expression, 667 // so that it can be used internally in the PPL, by friends of 668 // Linear_Expression. 669 //! Returns the i-th coefficient. 670 Coefficient_traits::const_reference get(dimension_type i) const; 671 672 // NOTE: This method is public, but it's not exposed in Linear_Expression, 673 // so that it can be used internally in the PPL, by friends of 674 // Linear_Expression. 675 //! Sets the i-th coefficient to n. 676 void set(dimension_type i, Coefficient_traits::const_reference n); 677 678 // NOTE: This method is public, but it's not exposed in Linear_Expression, 679 // so that it can be used internally in the PPL, by friends of 680 // Linear_Expression. 681 //! Returns the coefficient of v. 682 Coefficient_traits::const_reference get(Variable v) const; 683 684 // NOTE: This method is public, but it's not exposed in Linear_Expression, 685 // so that it can be used internally in the PPL, by friends of 686 // Linear_Expression. 687 //! Sets the coefficient of v to n. 688 void set(Variable v, Coefficient_traits::const_reference n); 689 690 /*! \brief 691 Returns <CODE>true</CODE> if (*this)[i] is \f$0\f$, for each i in 692 [start, end). 693 */ 694 bool all_zeroes(dimension_type start, dimension_type end) const; 695 696 /*! \brief 697 Returns the number of zero coefficient in [start, end). 698 */ 699 dimension_type num_zeroes(dimension_type start, dimension_type end) const; 700 701 /*! \brief 702 Returns the gcd of the nonzero coefficients in [start,end). If all the 703 coefficients in this range are 0 returns 0. 704 */ 705 Coefficient gcd(dimension_type start, dimension_type end) const; 706 707 void exact_div_assign(Coefficient_traits::const_reference c, 708 dimension_type start, dimension_type end); 709 710 //! Linearly combines \p *this with \p y so that the coefficient of \p v 711 //! is 0. 712 /*! 713 \param y 714 The expression that will be combined with \p *this object; 715 716 \param i 717 The index of the coefficient that has to become \f$0\f$. 718 719 Computes a linear combination of \p *this and \p y having 720 the i-th coefficient equal to \f$0\f$. Then it assigns 721 the resulting expression to \p *this. 722 723 \p *this and \p y must have the same space dimension. 724 */ 725 void linear_combine(const Linear_Expression& y, dimension_type i); 726 727 //! Equivalent to <CODE>(*this)[i] = (*this)[i] * c1 + y[i] * c2</CODE>, 728 //! for each i in [start, end). It assumes that c1 and c2 are nonzero. 729 void linear_combine(const Linear_Expression& y, 730 Coefficient_traits::const_reference c1, 731 Coefficient_traits::const_reference c2, 732 dimension_type start, dimension_type end); 733 734 //! Equivalent to <CODE>(*this)[i] = (*this)[i] * c1 + y[i] * c2</CODE>, 735 //! for each i in [start, end). c1 and c2 may be zero. 736 void linear_combine_lax(const Linear_Expression& y, 737 Coefficient_traits::const_reference c1, 738 Coefficient_traits::const_reference c2, 739 dimension_type start, dimension_type end); 740 741 //! Equivalent to <CODE>(*this)[i] *= n</CODE>, for each i in [start, end). 742 void mul_assign(Coefficient_traits::const_reference n, 743 dimension_type start, dimension_type end); 744 745 //! Returns the index of the last nonzero element, or 0 if there are no 746 //! nonzero elements. 747 dimension_type last_nonzero() const; 748 749 //! Returns the index of the last nonzero element in [first,last), or last 750 //! if there are no nonzero elements. 751 dimension_type last_nonzero(dimension_type first, dimension_type last) const; 752 753 //! Returns the index of the first nonzero element, or \p last if there are no 754 //! nonzero elements, considering only elements in [first,last). 755 dimension_type first_nonzero(dimension_type first, dimension_type last) const; 756 757 /*! \brief 758 Returns <CODE>true</CODE> if all coefficients in [start,end), 759 except those corresponding to variables in \p vars, are zero. 760 */ 761 bool all_zeroes_except(const Variables_Set& vars, 762 dimension_type start, dimension_type end) const; 763 764 //! Sets results to the sum of (*this)[i]*y[i], for each i. 765 void scalar_product_assign(Coefficient& result, 766 const Linear_Expression& y) const; 767 768 //! Sets results to the sum of (*this)[i]*y[i], for each i in [start,end). 769 void scalar_product_assign(Coefficient& result, const Linear_Expression& y, 770 dimension_type start, dimension_type end) const; 771 772 //! Computes the sign of the sum of (*this)[i]*y[i], for each i. 773 int scalar_product_sign(const Linear_Expression& y) const; 774 775 //! Computes the sign of the sum of (*this)[i]*y[i], 776 //! for each i in [start,end). 777 int scalar_product_sign(const Linear_Expression& y, 778 dimension_type start, dimension_type end) const; 779 780 //! Removes from the set x all the indexes of nonzero elements of *this. 781 void has_a_free_dimension_helper(std::set<dimension_type>& x) const; 782 783 //! Returns \p true if (*this)[i] is equal to x[i], for each i in [start,end). 784 bool is_equal_to(const Linear_Expression& x, 785 dimension_type start, dimension_type end) const; 786 787 //! Returns \p true if (*this)[i]*c1 is equal to x[i]*c2, for each i in 788 //! [start,end). 789 bool is_equal_to(const Linear_Expression& x, 790 Coefficient_traits::const_reference c1, 791 Coefficient_traits::const_reference c2, 792 dimension_type start, dimension_type end) const; 793 794 //! Sets \p r to a copy of the row that implements \p *this. 795 void get_row(Dense_Row& r) const; 796 797 //! Sets \p r to a copy of the row that implements \p *this. 798 void get_row(Sparse_Row& r) const; 799 800 /*! \brief 801 Returns \p true if there is a variable from index \p first (included) 802 to index \p last (excluded) whose coefficient is nonzero in both 803 \p *this and \p x. 804 */ 805 bool have_a_common_variable(const Linear_Expression& x, 806 Variable first, Variable last) const; 807 808 /*! \brief 809 Negates the elements from index \p first (included) 810 to index \p last (excluded). 811 */ 812 void negate(dimension_type first, dimension_type last); 813 814 template <typename Row> 815 friend class Linear_Expression_Impl; 816 817 // NOTE: The following classes are friends of Linear_Expression in order 818 // to access its private methods. 819 // Since they are *not* friend of Linear_Expression_Impl, they can only 820 // access its public methods so they cannot break the class invariant of 821 // Linear_Expression_Impl. 822 friend class Grid; 823 friend class Congruence; 824 friend class Polyhedron; 825 friend class PIP_Tree_Node; 826 friend class Grid_Generator; 827 friend class Generator; 828 friend class Constraint; 829 friend class Constraint_System; 830 friend class PIP_Problem; 831 friend class BHRZ03_Certificate; 832 friend class Scalar_Products; 833 friend class MIP_Problem; 834 friend class Box_Helpers; 835 friend class Congruence_System; 836 friend class BD_Shape_Helpers; 837 friend class Octagonal_Shape_Helper; 838 friend class Termination_Helpers; 839 template <typename T> 840 friend class BD_Shape; 841 template <typename T> 842 friend class Octagonal_Shape; 843 template <typename T> 844 friend class Linear_System; 845 template <typename T> 846 friend class Box; 847 template <typename T> 848 friend class Expression_Adapter; 849 template <typename T> 850 friend class Expression_Hide_Inhomo; 851 template <typename T> 852 friend class Expression_Hide_Last; 853 854 friend Linear_Expression 855 operator+(const Linear_Expression& e1, const Linear_Expression& e2); 856 friend Linear_Expression 857 operator+(Coefficient_traits::const_reference n, const Linear_Expression& e); 858 friend Linear_Expression 859 operator+(const Linear_Expression& e, Coefficient_traits::const_reference n); 860 friend Linear_Expression 861 operator+(Variable v, const Linear_Expression& e); 862 friend Linear_Expression 863 operator+(Variable v, Variable w); 864 865 friend Linear_Expression 866 operator-(const Linear_Expression& e); 867 868 friend Linear_Expression 869 operator-(const Linear_Expression& e1, const Linear_Expression& e2); 870 friend Linear_Expression 871 operator-(Variable v, Variable w); 872 friend Linear_Expression 873 operator-(Coefficient_traits::const_reference n, const Linear_Expression& e); 874 friend Linear_Expression 875 operator-(const Linear_Expression& e, Coefficient_traits::const_reference n); 876 friend Linear_Expression 877 operator-(Variable v, const Linear_Expression& e); 878 friend Linear_Expression 879 operator-(const Linear_Expression& e, Variable v); 880 881 friend Linear_Expression 882 operator*(Coefficient_traits::const_reference n, const Linear_Expression& e); 883 friend Linear_Expression 884 operator*(const Linear_Expression& e, Coefficient_traits::const_reference n); 885 886 friend Linear_Expression& 887 operator+=(Linear_Expression& e1, const Linear_Expression& e2); 888 friend Linear_Expression& 889 operator+=(Linear_Expression& e, Variable v); 890 friend Linear_Expression& 891 operator+=(Linear_Expression& e, Coefficient_traits::const_reference n); 892 893 friend Linear_Expression& 894 operator-=(Linear_Expression& e1, const Linear_Expression& e2); 895 friend Linear_Expression& 896 operator-=(Linear_Expression& e, Variable v); 897 friend Linear_Expression& 898 operator-=(Linear_Expression& e, Coefficient_traits::const_reference n); 899 900 friend Linear_Expression& 901 operator*=(Linear_Expression& e, Coefficient_traits::const_reference n); 902 friend Linear_Expression& 903 operator/=(Linear_Expression& e, Coefficient_traits::const_reference n); 904 905 friend void 906 neg_assign(Linear_Expression& e); 907 908 friend Linear_Expression& 909 add_mul_assign(Linear_Expression& e, 910 Coefficient_traits::const_reference n, Variable v); 911 friend Linear_Expression& 912 sub_mul_assign(Linear_Expression& e, 913 Coefficient_traits::const_reference n, Variable v); 914 915 friend void 916 add_mul_assign(Linear_Expression& e1, 917 Coefficient_traits::const_reference factor, 918 const Linear_Expression& e2); 919 friend void 920 sub_mul_assign(Linear_Expression& e1, 921 Coefficient_traits::const_reference factor, 922 const Linear_Expression& e2); 923 924 friend int 925 compare(const Linear_Expression& x, const Linear_Expression& y); 926 927 friend std::ostream& 928 Parma_Polyhedra_Library::IO_Operators 929 ::operator<<(std::ostream& s, const Linear_Expression& e); 930 }; 931 932 namespace Parma_Polyhedra_Library { 933 934 //! Swaps \p x with \p y. 935 /*! \relates Linear_Expression */ 936 void swap(Linear_Expression& x, Linear_Expression& y); 937 938 //! Swaps \p x with \p y. 939 /*! \relates Linear_Expression::const_iterator */ 940 void swap(Linear_Expression::const_iterator& x, 941 Linear_Expression::const_iterator& y); 942 943 } // namespace Parma_Polyhedra_Library 944 945 #include "Linear_Expression_inlines.hh" 946 947 #endif // !defined(PPL_Linear_Expression_defs_hh) 948