1 /* Linear_Expression_Interface 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_Interface_defs_hh 25 #define PPL_Linear_Expression_Interface_defs_hh 1 26 27 #include "Linear_Expression_Interface_types.hh" 28 #include "Coefficient_defs.hh" 29 #include "Variable_types.hh" 30 #include "Variables_Set_types.hh" 31 #include "Dense_Row_types.hh" 32 #include "Sparse_Row_types.hh" 33 #include <vector> 34 #include <set> 35 #include <cstddef> 36 37 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 38 //! A linear expression. 39 /*! \ingroup PPL_CXX_interface 40 An object of a class implementing Linear_Expression_Interface 41 represents a linear expression 42 \f[ 43 \sum_{i=0}^{n-1} a_i x_i + b 44 \f] 45 where \f$n\f$ is the dimension of the vector space, 46 each \f$a_i\f$ is the integer coefficient 47 of the \f$i\f$-th variable \f$x_i\f$ 48 and \f$b\f$ is the integer for the inhomogeneous term. 49 */ 50 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 51 class Parma_Polyhedra_Library::Linear_Expression_Interface { 52 public: 53 virtual ~Linear_Expression_Interface(); 54 55 virtual bool OK() const = 0; 56 57 //! Returns the current representation of this linear expression. 58 virtual Representation representation() const = 0; 59 60 //! An interface for const iterators on the expression (homogeneous) 61 //! coefficients that are nonzero. 62 /*! 63 These iterators are invalidated by operations that modify the expression. 64 */ 65 class const_iterator_interface { 66 public: 67 typedef std::bidirectional_iterator_tag iterator_category; 68 typedef const Coefficient value_type; 69 typedef std::ptrdiff_t difference_type; 70 typedef value_type* pointer; 71 typedef Coefficient_traits::const_reference reference; 72 73 //! Returns a copy of *this. 74 //! This returns a pointer to dynamic-allocated memory. The caller has the 75 //! duty to free the memory when it's not needed anymore. 76 virtual const_iterator_interface* clone() const = 0; 77 78 virtual ~const_iterator_interface(); 79 80 //! Navigates to the next nonzero coefficient. 81 //! Note that this method does *not* return a reference, to increase 82 //! efficiency since it's virtual. 83 virtual void operator++() = 0; 84 85 //! Navigates to the previous nonzero coefficient. 86 //! Note that this method does *not* return a reference, to increase 87 //! efficiency since it's virtual. 88 virtual void operator--() = 0; 89 90 //! Returns the current element. 91 virtual reference operator*() const = 0; 92 93 //! Returns the variable of the coefficient pointed to by \c *this. 94 /*! 95 \returns the variable of the coefficient pointed to by \c *this. 96 */ 97 virtual Variable variable() const = 0; 98 99 //! Compares \p *this with x . 100 /*! 101 \param x 102 The %iterator that will be compared with *this. 103 */ 104 virtual bool operator==(const const_iterator_interface& x) const = 0; 105 }; 106 107 //! This returns a pointer to dynamic-allocated memory. The caller has the 108 //! duty to free the memory when it's not needed anymore. 109 virtual const_iterator_interface* begin() const = 0; 110 111 //! This returns a pointer to dynamic-allocated memory. The caller has the 112 //! duty to free the memory when it's not needed anymore. 113 virtual const_iterator_interface* end() const = 0; 114 115 //! This returns a pointer to dynamic-allocated memory. The caller has the 116 //! duty to free the memory when it's not needed anymore. 117 //! Returns (a pointer to) an iterator that points to the first nonzero 118 //! coefficient of a variable greater than or equal to v, or at end if no 119 //! such coefficient exists. 120 virtual const_iterator_interface* lower_bound(Variable v) const = 0; 121 122 //! Returns the dimension of the vector space enclosing \p *this. 123 virtual dimension_type space_dimension() const = 0; 124 125 //! Sets the dimension of the vector space enclosing \p *this to \p n . 126 virtual void set_space_dimension(dimension_type n) = 0; 127 128 //! Returns the coefficient of \p v in \p *this. 129 virtual Coefficient_traits::const_reference 130 coefficient(Variable v) const = 0; 131 132 //! Sets the coefficient of \p v in \p *this to \p n. 133 virtual void 134 set_coefficient(Variable v, Coefficient_traits::const_reference n) = 0; 135 136 //! Returns the inhomogeneous term of \p *this. 137 virtual Coefficient_traits::const_reference inhomogeneous_term() const = 0; 138 139 //! Sets the inhomogeneous term of \p *this to \p n. 140 virtual void 141 set_inhomogeneous_term(Coefficient_traits::const_reference n) = 0; 142 143 //! Linearly combines \p *this with \p y so that the coefficient of \p v 144 //! is 0. 145 /*! 146 \param y 147 The expression that will be combined with \p *this object; 148 149 \param v 150 The variable whose coefficient has to become \f$0\f$. 151 152 Computes a linear combination of \p *this and \p y having 153 the coefficient of variable \p v equal to \f$0\f$. Then it assigns 154 the resulting expression to \p *this. 155 156 \p *this and \p y must have the same space dimension. 157 */ 158 virtual void 159 linear_combine(const Linear_Expression_Interface& y, Variable v) = 0; 160 161 //! Equivalent to <CODE>*this = *this * c1 + y * c2</CODE>, but assumes that 162 //! \p *this and \p y have the same space dimension. 163 virtual void linear_combine(const Linear_Expression_Interface& y, 164 Coefficient_traits::const_reference c1, 165 Coefficient_traits::const_reference c2) = 0; 166 167 //! Equivalent to <CODE>*this = *this * c1 + y * c2</CODE>. 168 //! c1 and c2 may be 0. 169 virtual void linear_combine_lax(const Linear_Expression_Interface& y, 170 Coefficient_traits::const_reference c1, 171 Coefficient_traits::const_reference c2) = 0; 172 173 //! Swaps the coefficients of the variables \p v1 and \p v2 . 174 virtual void swap_space_dimensions(Variable v1, Variable v2) = 0; 175 176 //! Removes all the specified dimensions from the expression. 177 /*! 178 The space dimension of the variable with the highest space 179 dimension in \p vars must be at most the space dimension 180 of \p this. 181 */ 182 virtual void remove_space_dimensions(const Variables_Set& vars) = 0; 183 184 //! Shift by \p n positions the coefficients of variables, starting from 185 //! the coefficient of \p v. This increases the space dimension by \p n. 186 virtual void shift_space_dimensions(Variable v, dimension_type n) = 0; 187 188 //! Permutes the space dimensions of the expression. 189 /*! 190 \param cycle 191 A vector representing a cycle of the permutation according to which the 192 space dimensions must be rearranged. 193 194 The \p cycle vector represents a cycle of a permutation of space 195 dimensions. 196 For example, the permutation 197 \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be 198 represented by the vector containing \f$ x_1, x_2, x_3 \f$. 199 */ 200 virtual void 201 permute_space_dimensions(const std::vector<Variable>& cycle) = 0; 202 203 //! Returns <CODE>true</CODE> if and only if \p *this is \f$0\f$. 204 virtual bool is_zero() const = 0; 205 206 /*! \brief 207 Returns <CODE>true</CODE> if and only if all the homogeneous 208 terms of \p *this are \f$0\f$. 209 */ 210 virtual bool all_homogeneous_terms_are_zero() const = 0; 211 212 /*! \brief 213 Returns a lower bound to the total size in bytes of the memory 214 occupied by \p *this. 215 */ 216 virtual memory_size_type total_memory_in_bytes() const = 0; 217 218 //! Returns the size in bytes of the memory managed by \p *this. 219 virtual memory_size_type external_memory_in_bytes() const = 0; 220 221 //! Writes to \p s an ASCII representation of \p *this. 222 virtual void ascii_dump(std::ostream& s) const = 0; 223 224 /*! \brief 225 Loads from \p s an ASCII representation (as produced by 226 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 227 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 228 */ 229 virtual bool ascii_load(std::istream& s) = 0; 230 231 //! Returns \p true if *this is equal to \p x. 232 //! Note that (*this == x) has a completely different meaning. 233 virtual bool is_equal_to(const Linear_Expression_Interface& x) const = 0; 234 235 //! Normalizes the modulo of the coefficients and of the inhomogeneous term 236 //! so that they are mutually prime. 237 /*! 238 Computes the Greatest Common Divisor (GCD) among the coefficients 239 and the inhomogeneous term and normalizes them by the GCD itself. 240 */ 241 virtual void normalize() = 0; 242 243 //! Ensures that the first nonzero homogeneous coefficient is positive, 244 //! by negating the row if necessary. 245 virtual void sign_normalize() = 0; 246 247 /*! \brief 248 Negates the elements from index \p first (included) 249 to index \p last (excluded). 250 */ 251 virtual void negate(dimension_type first, dimension_type last) = 0; 252 253 virtual Linear_Expression_Interface& 254 operator+=(Coefficient_traits::const_reference n) = 0; 255 virtual Linear_Expression_Interface& 256 operator-=(Coefficient_traits::const_reference n) = 0; 257 258 //! The basic comparison function. 259 /*! \relates Linear_Expression_Interface 260 261 \returns -1 or -2 if x is less than y, 0 if they are equal and 1 or 2 is y 262 is greater. The absolute value of the result is 1 if the difference 263 is only in the inhomogeneous terms, 2 otherwise 264 265 The order is a lexicographic. It starts comparing the variables' 266 coefficient, starting from Variable(0), and at the end it compares 267 the inhomogeneous terms. 268 */ 269 virtual int compare(const Linear_Expression_Interface& y) const = 0; 270 271 virtual Linear_Expression_Interface& 272 operator+=(const Linear_Expression_Interface& e2) = 0; 273 virtual Linear_Expression_Interface& 274 operator+=(const Variable v) = 0; 275 virtual Linear_Expression_Interface& 276 operator-=(const Linear_Expression_Interface& e2) = 0; 277 virtual Linear_Expression_Interface& 278 operator-=(const Variable v) = 0; 279 virtual Linear_Expression_Interface& 280 operator*=(Coefficient_traits::const_reference n) = 0; 281 virtual Linear_Expression_Interface& 282 operator/=(Coefficient_traits::const_reference n) = 0; 283 284 virtual void negate() = 0; 285 286 virtual Linear_Expression_Interface& 287 add_mul_assign(Coefficient_traits::const_reference n, const Variable v) = 0; 288 289 virtual Linear_Expression_Interface& 290 sub_mul_assign(Coefficient_traits::const_reference n, const Variable v) = 0; 291 292 virtual void add_mul_assign(Coefficient_traits::const_reference factor, 293 const Linear_Expression_Interface& e2) = 0; 294 295 virtual void sub_mul_assign(Coefficient_traits::const_reference factor, 296 const Linear_Expression_Interface& e2) = 0; 297 298 virtual void print(std::ostream& s) const = 0; 299 300 /*! \brief 301 Returns <CODE>true</CODE> if the coefficient of each variable in 302 \p vars[i] is \f$0\f$. 303 */ 304 virtual bool all_zeroes(const Variables_Set& vars) const = 0; 305 306 //! Returns true if there is a variable in [first,last) whose coefficient 307 //! is nonzero in both *this and x. 308 virtual bool have_a_common_variable(const Linear_Expression_Interface& x, 309 Variable first, Variable last) const = 0; 310 311 // NOTE: This method is public, but it's not exposed in Linear_Expression, 312 // so that it can be used internally in the PPL, by friends of 313 // Linear_Expression. 314 //! Returns the i-th coefficient. 315 virtual Coefficient_traits::const_reference get(dimension_type i) const = 0; 316 317 // NOTE: This method is public, but it's not exposed in Linear_Expression, 318 // so that it can be used internally in the PPL, by friends of 319 // Linear_Expression. 320 //! Sets the i-th coefficient to n. 321 virtual void set(dimension_type i, Coefficient_traits::const_reference n) = 0; 322 323 // NOTE: This method is public, but it's not exposed in Linear_Expression, 324 // so that it can be used internally in the PPL, by friends of 325 // Linear_Expression. 326 /*! \brief 327 Returns <CODE>true</CODE> if (*this)[i] is \f$0\f$, for each i in 328 [start, end). 329 */ 330 virtual bool all_zeroes(dimension_type start, dimension_type end) const = 0; 331 332 // NOTE: This method is public, but it's not exposed in Linear_Expression, 333 // so that it can be used internally in the PPL, by friends of 334 // Linear_Expression. 335 /*! \brief 336 Returns the number of zero coefficient in [start, end). 337 */ 338 virtual dimension_type 339 num_zeroes(dimension_type start, dimension_type end) const = 0; 340 341 // NOTE: This method is public, but it's not exposed in Linear_Expression, 342 // so that it can be used internally in the PPL, by friends of 343 // Linear_Expression. 344 /*! \brief 345 Returns the gcd of the nonzero coefficients in [start,end). If all the 346 coefficients in this range are 0 returns 0. 347 */ 348 virtual Coefficient gcd(dimension_type start, dimension_type end) const = 0; 349 350 // NOTE: This method is public, but it's not exposed in Linear_Expression, 351 // so that it can be used internally in the PPL, by friends of 352 // Linear_Expression. 353 virtual void exact_div_assign(Coefficient_traits::const_reference c, 354 dimension_type start, dimension_type end) = 0; 355 356 // NOTE: This method is public, but it's not exposed in Linear_Expression, 357 // so that it can be used internally in the PPL, by friends of 358 // Linear_Expression. 359 //! Equivalent to <CODE>(*this)[i] *= n</CODE>, for each i in [start, end). 360 virtual void mul_assign(Coefficient_traits::const_reference n, 361 dimension_type start, dimension_type end) = 0; 362 363 // NOTE: This method is public, but it's not exposed in Linear_Expression, 364 // so that it can be used internally in the PPL, by friends of 365 // Linear_Expression. 366 //! Linearly combines \p *this with \p y so that the coefficient of \p v 367 //! is 0. 368 /*! 369 \param y 370 The expression that will be combined with \p *this object; 371 372 \param i 373 The index of the coefficient that has to become \f$0\f$. 374 375 Computes a linear combination of \p *this and \p y having 376 the i-th coefficient equal to \f$0\f$. Then it assigns 377 the resulting expression to \p *this. 378 379 \p *this and \p y must have the same space dimension. 380 */ 381 virtual void 382 linear_combine(const Linear_Expression_Interface& y, dimension_type i) = 0; 383 384 // NOTE: This method is public, but it's not exposed in Linear_Expression, 385 // so that it can be used internally in the PPL, by friends of 386 // Linear_Expression. 387 //! Equivalent to <CODE>(*this)[i] = (*this)[i] * c1 + y[i] * c2</CODE>, 388 //! for each i in [start, end). 389 virtual void linear_combine(const Linear_Expression_Interface& y, 390 Coefficient_traits::const_reference c1, 391 Coefficient_traits::const_reference c2, 392 dimension_type start, dimension_type end) = 0; 393 394 // NOTE: This method is public, but it's not exposed in Linear_Expression, 395 // so that it can be used internally in the PPL, by friends of 396 // Linear_Expression. 397 //! Equivalent to <CODE>(*this)[i] = (*this)[i] * c1 + y[i] * c2</CODE>, 398 //! for each i in [start, end). c1 and c2 may be zero. 399 virtual void linear_combine_lax(const Linear_Expression_Interface& y, 400 Coefficient_traits::const_reference c1, 401 Coefficient_traits::const_reference c2, 402 dimension_type start, dimension_type end) = 0; 403 404 // NOTE: This method is public, but it's not exposed in Linear_Expression, 405 // so that it can be used internally in the PPL, by friends of 406 // Linear_Expression. 407 //! Returns the index of the last nonzero element, or 0 if there are no 408 //! nonzero elements. 409 virtual dimension_type last_nonzero() const = 0; 410 411 // NOTE: This method is public, but it's not exposed in Linear_Expression, 412 // so that it can be used internally in the PPL, by friends of 413 // Linear_Expression. 414 //! Returns the index of the last nonzero element in [first,last), or last 415 //! if there are no nonzero elements. 416 virtual dimension_type 417 last_nonzero(dimension_type first, dimension_type last) const = 0; 418 419 //! Returns the index of the first nonzero element, or \p last if there are no 420 //! nonzero elements, considering only elements in [first,last). 421 virtual dimension_type 422 first_nonzero(dimension_type first, dimension_type last) const = 0; 423 424 // NOTE: This method is public, but it's not exposed in Linear_Expression, 425 // so that it can be used internally in the PPL, by friends of 426 // Linear_Expression. 427 /*! \brief 428 Returns <CODE>true</CODE> if each coefficient in [start,end) is *not* in 429 \f$0\f$, disregarding coefficients of variables in \p vars. 430 */ 431 virtual bool 432 all_zeroes_except(const Variables_Set& vars, 433 dimension_type start, dimension_type end) const = 0; 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 //! Sets results to the sum of (*this)[i]*y[i], for each i in [start,end). 439 virtual void 440 scalar_product_assign(Coefficient& result, 441 const Linear_Expression_Interface& y, 442 dimension_type start, dimension_type end) const = 0; 443 444 // NOTE: This method is public, but it's not exposed in Linear_Expression, 445 // so that it can be used internally in the PPL, by friends of 446 // Linear_Expression. 447 //! Computes the sign of the sum of (*this)[i]*y[i], 448 //! for each i in [start,end). 449 virtual int 450 scalar_product_sign(const Linear_Expression_Interface& y, 451 dimension_type start, dimension_type end) const = 0; 452 453 // NOTE: This method is public, but it's not exposed in Linear_Expression, 454 // so that it can be used internally in the PPL, by friends of 455 // Linear_Expression. 456 //! Removes from the set x all the indexes of nonzero elements of *this. 457 virtual void 458 has_a_free_dimension_helper(std::set<dimension_type>& x) const = 0; 459 460 // NOTE: This method is public, but it's not exposed in Linear_Expression, 461 // so that it can be used internally in the PPL, by friends of 462 // Linear_Expression. 463 //! Returns \p true if (*this)[i] is equal to x[i], for each i in [start,end). 464 virtual bool is_equal_to(const Linear_Expression_Interface& x, 465 dimension_type start, dimension_type end) const = 0; 466 467 // NOTE: This method is public, but it's not exposed in Linear_Expression, 468 // so that it can be used internally in the PPL, by friends of 469 // Linear_Expression. 470 //! Returns \p true if (*this)[i]*c1 is equal to x[i]*c2, for each i in 471 //! [start,end). 472 virtual bool is_equal_to(const Linear_Expression_Interface& x, 473 Coefficient_traits::const_reference c1, 474 Coefficient_traits::const_reference c2, 475 dimension_type start, dimension_type end) const = 0; 476 477 // NOTE: This method is public, but it is not exposed in 478 // Linear_Expression, so that it can be used internally in the PPL, 479 // by friends of Linear_Expression. 480 //! Sets \p r to a copy of the row that implements \p *this. 481 virtual void get_row(Dense_Row& r) const = 0; 482 483 // NOTE: This method is public, but it is not exposed in 484 // Linear_Expression, so that it can be used internally in the PPL, 485 // by friends of Linear_Expression. 486 //! Sets \p r to a copy of the row that implements \p *this. 487 virtual void get_row(Sparse_Row& r) const = 0; 488 }; 489 490 #endif // !defined(PPL_Linear_Expression_Interface_defs_hh) 491