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