1 /* Generator 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_Generator_defs_hh 25 #define PPL_Generator_defs_hh 1 26 27 #include "Generator_types.hh" 28 #include "Scalar_Products_types.hh" 29 #include "Variables_Set_types.hh" 30 #include "Constraint_System_types.hh" 31 #include "Generator_System_types.hh" 32 #include "Congruence_System_types.hh" 33 #include "Polyhedron_types.hh" 34 #include "Grid_Generator_types.hh" 35 #include "Grid_Generator_System_types.hh" 36 #include "MIP_Problem_types.hh" 37 #include "Grid_types.hh" 38 39 #include "Variable_defs.hh" 40 #include "Linear_Expression_defs.hh" 41 #include "Checked_Number_defs.hh" 42 #include "distances_defs.hh" 43 #include "Topology_types.hh" 44 #include "Expression_Hide_Last_defs.hh" 45 #include "Expression_Hide_Inhomo_defs.hh" 46 47 #include <iosfwd> 48 49 namespace Parma_Polyhedra_Library { 50 51 // Put them in the namespace here to declare them friend later. 52 53 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 54 //! The basic comparison function. 55 /*! \relates Generator 56 \return 57 The returned absolute value can be \f$0\f$, \f$1\f$ or \f$2\f$. 58 59 \param x 60 A row of coefficients; 61 62 \param y 63 Another row. 64 65 Compares \p x and \p y, where \p x and \p y may be of different size, 66 in which case the "missing" coefficients are assumed to be zero. 67 The comparison is such that: 68 -# equalities are smaller than inequalities; 69 -# lines are smaller than points and rays; 70 -# the ordering is lexicographic; 71 -# the positions compared are, in decreasing order of significance, 72 1, 2, ..., \p size(), 0; 73 -# the result is negative, zero, or positive if x is smaller than, 74 equal to, or greater than y, respectively; 75 -# when \p x and \p y are different, the absolute value of the 76 result is 1 if the difference is due to the coefficient in 77 position 0; it is 2 otherwise. 78 79 When \p x and \p y represent the hyper-planes associated 80 to two equality or inequality constraints, the coefficient 81 at 0 is the known term. 82 In this case, the return value can be characterized as follows: 83 - -2, if \p x is smaller than \p y and they are \e not parallel; 84 - -1, if \p x is smaller than \p y and they \e are parallel; 85 - 0, if \p x and y are equal; 86 - +1, if \p y is smaller than \p x and they \e are parallel; 87 - +2, if \p y is smaller than \p x and they are \e not parallel. 88 */ 89 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 90 int compare(const Generator& x, const Generator& y); 91 92 namespace IO_Operators { 93 94 //! Output operator. 95 /*! \relates Parma_Polyhedra_Library::Generator */ 96 std::ostream& operator<<(std::ostream& s, const Generator& g); 97 98 } // namespace IO_Operators 99 100 //! Swaps \p x with \p y. 101 /*! \relates Generator */ 102 void swap(Generator& x, Generator& y); 103 104 } // namespace Parma_Polyhedra_Library 105 106 107 //! A line, ray, point or closure point. 108 /*! \ingroup PPL_CXX_interface 109 An object of the class Generator is one of the following: 110 111 - a line \f$\vect{l} = (a_0, \ldots, a_{n-1})^\transpose\f$; 112 113 - a ray \f$\vect{r} = (a_0, \ldots, a_{n-1})^\transpose\f$; 114 115 - a point 116 \f$\vect{p} = (\frac{a_0}{d}, \ldots, \frac{a_{n-1}}{d})^\transpose\f$; 117 118 - a closure point 119 \f$\vect{c} = (\frac{a_0}{d}, \ldots, \frac{a_{n-1}}{d})^\transpose\f$; 120 121 where \f$n\f$ is the dimension of the space 122 and, for points and closure points, \f$d > 0\f$ is the divisor. 123 124 \par A note on terminology. 125 As observed in Section \ref representation, there are cases when, 126 in order to represent a polyhedron \f$\cP\f$ using the generator system 127 \f$\cG = (L, R, P, C)\f$, we need to include in the finite set 128 \f$P\f$ even points of \f$\cP\f$ that are <EM>not</EM> vertices 129 of \f$\cP\f$. 130 This situation is even more frequent when working with NNC polyhedra 131 and it is the reason why we prefer to use the word `point' 132 where other libraries use the word `vertex'. 133 134 \par How to build a generator. 135 Each type of generator is built by applying the corresponding 136 function (<CODE>line</CODE>, <CODE>ray</CODE>, <CODE>point</CODE> 137 or <CODE>closure_point</CODE>) to a linear expression, 138 representing a direction in the space; 139 the space dimension of the generator is defined as the space dimension 140 of the corresponding linear expression. 141 Linear expressions used to define a generator should be homogeneous 142 (any constant term will be simply ignored). 143 When defining points and closure points, an optional Coefficient argument 144 can be used as a common <EM>divisor</EM> for all the coefficients 145 occurring in the provided linear expression; 146 the default value for this argument is 1. 147 148 \par 149 In all the following examples it is assumed that variables 150 <CODE>x</CODE>, <CODE>y</CODE> and <CODE>z</CODE> 151 are defined as follows: 152 \code 153 Variable x(0); 154 Variable y(1); 155 Variable z(2); 156 \endcode 157 158 \par Example 1 159 The following code builds a line with direction \f$x-y-z\f$ 160 and having space dimension \f$3\f$: 161 \code 162 Generator l = line(x - y - z); 163 \endcode 164 As mentioned above, the constant term of the linear expression 165 is not relevant. Thus, the following code has the same effect: 166 \code 167 Generator l = line(x - y - z + 15); 168 \endcode 169 By definition, the origin of the space is not a line, so that 170 the following code throws an exception: 171 \code 172 Generator l = line(0*x); 173 \endcode 174 175 \par Example 2 176 The following code builds a ray with the same direction as the 177 line in Example 1: 178 \code 179 Generator r = ray(x - y - z); 180 \endcode 181 As is the case for lines, when specifying a ray the constant term 182 of the linear expression is not relevant; also, an exception is thrown 183 when trying to build a ray from the origin of the space. 184 185 \par Example 3 186 The following code builds the point 187 \f$\vect{p} = (1, 0, 2)^\transpose \in \Rset^3\f$: 188 \code 189 Generator p = point(1*x + 0*y + 2*z); 190 \endcode 191 The same effect can be obtained by using the following code: 192 \code 193 Generator p = point(x + 2*z); 194 \endcode 195 Similarly, the origin \f$\vect{0} \in \Rset^3\f$ can be defined 196 using either one of the following lines of code: 197 \code 198 Generator origin3 = point(0*x + 0*y + 0*z); 199 Generator origin3_alt = point(0*z); 200 \endcode 201 Note however that the following code would have defined 202 a different point, namely \f$\vect{0} \in \Rset^2\f$: 203 \code 204 Generator origin2 = point(0*y); 205 \endcode 206 The following two lines of code both define the only point 207 having space dimension zero, namely \f$\vect{0} \in \Rset^0\f$. 208 In the second case we exploit the fact that the first argument 209 of the function <CODE>point</CODE> is optional. 210 \code 211 Generator origin0 = Generator::zero_dim_point(); 212 Generator origin0_alt = point(); 213 \endcode 214 215 \par Example 4 216 The point \f$\vect{p}\f$ specified in Example 3 above 217 can also be obtained with the following code, 218 where we provide a non-default value for the second argument 219 of the function <CODE>point</CODE> (the divisor): 220 \code 221 Generator p = point(2*x + 0*y + 4*z, 2); 222 \endcode 223 Obviously, the divisor can be usefully exploited to specify 224 points having some non-integer (but rational) coordinates. 225 For instance, the point 226 \f$\vect{q} = (-1.5, 3.2, 2.1)^\transpose \in \Rset^3\f$ 227 can be specified by the following code: 228 \code 229 Generator q = point(-15*x + 32*y + 21*z, 10); 230 \endcode 231 If a zero divisor is provided, an exception is thrown. 232 233 \par Example 5 234 Closure points are specified in the same way we defined points, 235 but invoking their specific constructor function. 236 For instance, the closure point 237 \f$\vect{c} = (1, 0, 2)^\transpose \in \Rset^3\f$ is defined by 238 \code 239 Generator c = closure_point(1*x + 0*y + 2*z); 240 \endcode 241 For the particular case of the (only) closure point 242 having space dimension zero, we can use any of the following: 243 \code 244 Generator closure_origin0 = Generator::zero_dim_closure_point(); 245 Generator closure_origin0_alt = closure_point(); 246 \endcode 247 248 \par How to inspect a generator 249 Several methods are provided to examine a generator and extract 250 all the encoded information: its space dimension, its type and 251 the value of its integer coefficients. 252 253 \par Example 6 254 The following code shows how it is possible to access each single 255 coefficient of a generator. 256 If <CODE>g1</CODE> is a point having coordinates 257 \f$(a_0, \ldots, a_{n-1})^\transpose\f$, 258 we construct the closure point <CODE>g2</CODE> having coordinates 259 \f$(a_0, 2 a_1, \ldots, (i+1)a_i, \ldots, n a_{n-1})^\transpose\f$. 260 \code 261 if (g1.is_point()) { 262 cout << "Point g1: " << g1 << endl; 263 Linear_Expression e; 264 for (dimension_type i = g1.space_dimension(); i-- > 0; ) 265 e += (i + 1) * g1.coefficient(Variable(i)) * Variable(i); 266 Generator g2 = closure_point(e, g1.divisor()); 267 cout << "Closure point g2: " << g2 << endl; 268 } 269 else 270 cout << "Generator g1 is not a point." << endl; 271 \endcode 272 Therefore, for the point 273 \code 274 Generator g1 = point(2*x - y + 3*z, 2); 275 \endcode 276 we would obtain the following output: 277 \code 278 Point g1: p((2*A - B + 3*C)/2) 279 Closure point g2: cp((2*A - 2*B + 9*C)/2) 280 \endcode 281 When working with (closure) points, be careful not to confuse 282 the notion of <EM>coefficient</EM> with the notion of <EM>coordinate</EM>: 283 these are equivalent only when the divisor of the (closure) point is 1. 284 */ 285 class Parma_Polyhedra_Library::Generator { 286 public: 287 288 //! The representation used for new Generators. 289 /*! 290 \note The copy constructor and the copy constructor with specified size 291 use the representation of the original object, so that it is 292 indistinguishable from the original object. 293 */ 294 static const Representation default_representation = SPARSE; 295 296 //! Returns the line of direction \p e. 297 /*! 298 \exception std::invalid_argument 299 Thrown if the homogeneous part of \p e represents the origin of 300 the vector space. 301 */ 302 static Generator line(const Linear_Expression& e, 303 Representation r = default_representation); 304 305 //! Returns the ray of direction \p e. 306 /*! 307 \exception std::invalid_argument 308 Thrown if the homogeneous part of \p e represents the origin of 309 the vector space. 310 */ 311 static Generator ray(const Linear_Expression& e, 312 Representation r = default_representation); 313 314 //! Returns the point at \p e / \p d. 315 /*! 316 Both \p e and \p d are optional arguments, with default values 317 Linear_Expression::zero() and Coefficient_one(), respectively. 318 319 \exception std::invalid_argument 320 Thrown if \p d is zero. 321 */ 322 static Generator point(const Linear_Expression& e 323 = Linear_Expression::zero(), 324 Coefficient_traits::const_reference d 325 = Coefficient_one(), 326 Representation r = default_representation); 327 328 //! Returns the origin. 329 static Generator point(Representation r); 330 331 //! Returns the point at \p e. 332 static Generator point(const Linear_Expression& e, 333 Representation r); 334 335 //! Constructs the point at the origin. 336 explicit Generator(Representation r = default_representation); 337 338 //! Returns the closure point at \p e / \p d. 339 /*! 340 Both \p e and \p d are optional arguments, with default values 341 Linear_Expression::zero() and Coefficient_one(), respectively. 342 343 \exception std::invalid_argument 344 Thrown if \p d is zero. 345 */ 346 static Generator 347 closure_point(const Linear_Expression& e = Linear_Expression::zero(), 348 Coefficient_traits::const_reference d = Coefficient_one(), 349 Representation r = default_representation); 350 351 //! Returns the closure point at the origin. 352 static Generator 353 closure_point(Representation r); 354 355 //! Returns the closure point at \p e. 356 static Generator 357 closure_point(const Linear_Expression& e, Representation r); 358 359 //! Ordinary copy constructor. 360 //! The representation of the new Generator will be the same as g. 361 Generator(const Generator& g); 362 363 //! Copy constructor with given representation. 364 Generator(const Generator& g, Representation r); 365 366 //! Copy constructor with given space dimension. 367 //! The representation of the new Generator will be the same as g. 368 Generator(const Generator& g, dimension_type space_dim); 369 370 //! Copy constructor with given representation and space dimension. 371 Generator(const Generator& g, dimension_type space_dim, Representation r); 372 373 //! Destructor. 374 ~Generator(); 375 376 //! Assignment operator. 377 Generator& operator=(const Generator& g); 378 379 //! Returns the current representation of *this. 380 Representation representation() const; 381 382 //! Converts *this to the specified representation. 383 void set_representation(Representation r); 384 385 //! Returns the maximum space dimension a Generator can handle. 386 static dimension_type max_space_dimension(); 387 388 //! Returns the dimension of the vector space enclosing \p *this. 389 dimension_type space_dimension() const; 390 391 //! Sets the dimension of the vector space enclosing \p *this to 392 //! \p space_dim . 393 void set_space_dimension(dimension_type space_dim); 394 395 //! Swaps the coefficients of the variables \p v1 and \p v2 . 396 void swap_space_dimensions(Variable v1, Variable v2); 397 398 //! Removes all the specified dimensions from the generator. 399 /*! 400 The space dimension of the variable with the highest space 401 dimension in \p vars must be at most the space dimension 402 of \p this. 403 404 If all dimensions with nonzero coefficients are removed from a ray or a 405 line, it is changed into a point and this method returns \p false . 406 Otherwise, it returns \p true . 407 */ 408 bool remove_space_dimensions(const Variables_Set& vars); 409 410 //! Permutes the space dimensions of the generator. 411 /*! 412 \param cycle 413 A vector representing a cycle of the permutation according to which the 414 space dimensions must be rearranged. 415 416 The \p cycle vector represents a cycle of a permutation of space 417 dimensions. 418 For example, the permutation 419 \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be 420 represented by the vector containing \f$ x_1, x_2, x_3 \f$. 421 */ 422 void permute_space_dimensions(const std::vector<Variable>& cycle); 423 424 //! Shift by \p n positions the coefficients of variables, starting from 425 //! the coefficient of \p v. This increases the space dimension by \p n. 426 void shift_space_dimensions(Variable v, dimension_type n); 427 428 //! The generator type. 429 enum Type { 430 /*! The generator is a line. */ 431 LINE, 432 /*! The generator is a ray. */ 433 RAY, 434 /*! The generator is a point. */ 435 POINT, 436 /*! The generator is a closure point. */ 437 CLOSURE_POINT 438 }; 439 440 //! Returns the generator type of \p *this. 441 Type type() const; 442 443 //! Returns <CODE>true</CODE> if and only if \p *this is a line. 444 bool is_line() const; 445 446 //! Returns <CODE>true</CODE> if and only if \p *this is a ray. 447 bool is_ray() const; 448 449 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS 450 //! Returns <CODE>true</CODE> if and only if \p *this is a line or a ray. 451 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS) 452 bool is_line_or_ray() const; 453 454 //! Returns <CODE>true</CODE> if and only if \p *this is a point. 455 bool is_point() const; 456 457 //! Returns <CODE>true</CODE> if and only if \p *this is a closure point. 458 bool is_closure_point() const; 459 460 //! Returns the coefficient of \p v in \p *this. 461 /*! 462 \exception std::invalid_argument 463 Thrown if the index of \p v is greater than or equal to the 464 space dimension of \p *this. 465 */ 466 Coefficient_traits::const_reference coefficient(Variable v) const; 467 468 //! If \p *this is either a point or a closure point, returns its divisor. 469 /*! 470 \exception std::invalid_argument 471 Thrown if \p *this is neither a point nor a closure point. 472 */ 473 Coefficient_traits::const_reference divisor() const; 474 475 //! Initializes the class. 476 static void initialize(); 477 478 //! Finalizes the class. 479 static void finalize(); 480 481 //! Returns the origin of the zero-dimensional space \f$\Rset^0\f$. 482 static const Generator& zero_dim_point(); 483 484 /*! \brief 485 Returns, as a closure point, 486 the origin of the zero-dimensional space \f$\Rset^0\f$. 487 */ 488 static const Generator& zero_dim_closure_point(); 489 490 /*! \brief 491 Returns a lower bound to the total size in bytes of the memory 492 occupied by \p *this. 493 */ 494 memory_size_type total_memory_in_bytes() const; 495 496 //! Returns the size in bytes of the memory managed by \p *this. 497 memory_size_type external_memory_in_bytes() const; 498 499 /*! \brief 500 Returns <CODE>true</CODE> if and only if \p *this and \p y 501 are equivalent generators. 502 503 Generators having different space dimensions are not equivalent. 504 */ 505 bool is_equivalent_to(const Generator& y) const; 506 507 //! Returns <CODE>true</CODE> if \p *this is identical to \p y. 508 /*! 509 This is faster than is_equivalent_to(), but it may return `false' even 510 for equivalent generators. 511 */ 512 bool is_equal_to(const Generator& y) const; 513 514 //! Checks if all the invariants are satisfied. 515 bool OK() const; 516 517 PPL_OUTPUT_DECLARATIONS 518 519 /*! \brief 520 Loads from \p s an ASCII representation (as produced by 521 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 522 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 523 */ 524 bool ascii_load(std::istream& s); 525 526 //! Swaps \p *this with \p y. 527 void m_swap(Generator& y); 528 529 //! The type of the (adapted) internal expression. 530 typedef Expression_Hide_Last<Expression_Hide_Inhomo<Linear_Expression> > 531 expr_type; 532 //! Partial read access to the (adapted) internal expression. 533 expr_type expression() const; 534 535 private: 536 //! The possible kinds of Generator objects. 537 enum Kind { 538 LINE_OR_EQUALITY = 0, 539 RAY_OR_POINT_OR_INEQUALITY = 1 540 }; 541 542 //! The linear expression encoding \p *this. 543 Linear_Expression expr; 544 545 //! The kind of \p *this. 546 Kind kind_; 547 548 //! The topology of \p *this. 549 Topology topology_; 550 551 /*! \brief 552 Holds (between class initialization and finalization) a pointer to 553 the origin of the zero-dimensional space \f$\Rset^0\f$. 554 */ 555 static const Generator* zero_dim_point_p; 556 557 /*! \brief 558 Holds (between class initialization and finalization) a pointer to 559 the origin of the zero-dimensional space \f$\Rset^0\f$, as a closure point. 560 */ 561 static const Generator* zero_dim_closure_point_p; 562 563 /*! \brief 564 Builds a generator of type \p type and topology \p topology, 565 stealing the coefficients from \p e. 566 567 If the topology is NNC, the last dimension of \p e is used as the epsilon 568 coefficient. 569 */ 570 Generator(Linear_Expression& e, Type type, Topology topology); 571 572 Generator(Linear_Expression& e, Kind kind, Topology topology); 573 574 Generator(dimension_type space_dim, Kind kind, Topology topology, 575 Representation r = default_representation); 576 577 /*! \brief 578 Returns <CODE>true</CODE> if and only if \p *this row 579 represents a line or an equality. 580 */ 581 bool is_line_or_equality() const; 582 583 /*! \brief 584 Returns <CODE>true</CODE> if and only if \p *this row 585 represents a ray, a point or an inequality. 586 */ 587 bool is_ray_or_point_or_inequality() const; 588 589 //! Sets to \p LINE_OR_EQUALITY the kind of \p *this row. 590 void set_is_line_or_equality(); 591 592 //! Sets to \p RAY_OR_POINT_OR_INEQUALITY the kind of \p *this row. 593 void set_is_ray_or_point_or_inequality(); 594 595 //! \name Flags inspection methods 596 //@{ 597 //! Returns the topological kind of \p *this. 598 Topology topology() const; 599 600 /*! \brief 601 Returns <CODE>true</CODE> if and only if the topology 602 of \p *this row is not necessarily closed. 603 */ 604 bool is_not_necessarily_closed() const; 605 606 /*! \brief 607 Returns <CODE>true</CODE> if and only if the topology 608 of \p *this row is necessarily closed. 609 */ 610 bool is_necessarily_closed() const; 611 //@} // Flags inspection methods 612 613 //! \name Flags coercion methods 614 //@{ 615 616 //! Sets to \p x the topological kind of \p *this row. 617 void set_topology(Topology x); 618 619 //! Sets to \p NECESSARILY_CLOSED the topological kind of \p *this row. 620 void set_necessarily_closed(); 621 622 //! Sets to \p NOT_NECESSARILY_CLOSED the topological kind of \p *this row. 623 void set_not_necessarily_closed(); 624 //@} // Flags coercion methods 625 626 //! Marks the epsilon dimension as a standard dimension. 627 /*! 628 The row topology is changed to <CODE>NECESSARILY_CLOSED</CODE>, and 629 the number of space dimensions is increased by 1. 630 */ 631 void mark_as_necessarily_closed(); 632 633 //! Marks the last dimension as the epsilon dimension. 634 /*! 635 The row topology is changed to <CODE>NOT_NECESSARILY_CLOSED</CODE>, and 636 the number of space dimensions is decreased by 1. 637 */ 638 void mark_as_not_necessarily_closed(); 639 640 //! Linearly combines \p *this with \p y so that i-th coefficient is 0. 641 /*! 642 \param y 643 The Generator that will be combined with \p *this object; 644 645 \param i 646 The index of the coefficient that has to become \f$0\f$. 647 648 Computes a linear combination of \p *this and \p y having 649 the i-th coefficient equal to \f$0\f$. Then it assigns 650 the resulting Generator to \p *this and normalizes it. 651 */ 652 void linear_combine(const Generator& y, dimension_type i); 653 654 //! Sets the dimension of the vector space enclosing \p *this to 655 //! \p space_dim . 656 //! Sets the space dimension of the rows in the system to \p space_dim . 657 /*! 658 This method is for internal use, it does *not* assert OK() at the end, 659 so it can be used for invalid objects. 660 */ 661 void set_space_dimension_no_ok(dimension_type space_dim); 662 663 /*! \brief 664 Throw a <CODE>std::invalid_argument</CODE> exception 665 containing the appropriate error message. 666 */ 667 void 668 throw_dimension_incompatible(const char* method, 669 const char* v_name, 670 Variable v) const; 671 672 /*! \brief 673 Throw a <CODE>std::invalid_argument</CODE> exception 674 containing the appropriate error message. 675 */ 676 void 677 throw_invalid_argument(const char* method, const char* reason) const; 678 679 //! Returns <CODE>true</CODE> if and only if \p *this is not a line. 680 bool is_ray_or_point() const; 681 682 //! Sets the Generator kind to <CODE>LINE_OR_EQUALITY</CODE>. 683 void set_is_line(); 684 685 //! Sets the Generator kind to <CODE>RAY_OR_POINT_OR_INEQUALITY</CODE>. 686 void set_is_ray_or_point(); 687 688 /*! \brief 689 Returns <CODE>true</CODE> if and only if the closure point 690 \p *this has the same \e coordinates of the point \p p. 691 692 It is \e assumed that \p *this is a closure point, \p p is a point 693 and both topologies and space dimensions agree. 694 */ 695 bool is_matching_closure_point(const Generator& p) const; 696 697 //! Returns the epsilon coefficient. The generator must be NNC. 698 Coefficient_traits::const_reference epsilon_coefficient() const; 699 700 //! Sets the epsilon coefficient to \p n. The generator must be NNC. 701 void set_epsilon_coefficient(Coefficient_traits::const_reference n); 702 703 /*! \brief 704 Normalizes the sign of the coefficients so that the first non-zero 705 (homogeneous) coefficient of a line-or-equality is positive. 706 */ 707 void sign_normalize(); 708 709 /*! \brief 710 Strong normalization: ensures that different Generator objects 711 represent different hyperplanes or hyperspaces. 712 713 Applies both Generator::normalize() and Generator::sign_normalize(). 714 */ 715 void strong_normalize(); 716 717 /*! \brief 718 Returns <CODE>true</CODE> if and only if the coefficients are 719 strongly normalized. 720 */ 721 bool check_strong_normalized() const; 722 723 /*! \brief 724 A print function, with fancy, more human-friendly output. 725 726 This is used by operator<<(). 727 */ 728 void fancy_print(std::ostream& s) const; 729 730 friend class Expression_Adapter<Generator>; 731 friend class Linear_System<Generator>; 732 friend class Parma_Polyhedra_Library::Scalar_Products; 733 friend class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign; 734 friend class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Assign; 735 friend class Parma_Polyhedra_Library::Generator_System; 736 friend class Parma_Polyhedra_Library::Generator_System_const_iterator; 737 // FIXME: the following friend declaration should be avoided. 738 friend class Parma_Polyhedra_Library::Polyhedron; 739 // This is for access to Linear_Expression in `insert'. 740 friend class Parma_Polyhedra_Library::Grid_Generator_System; 741 friend class Parma_Polyhedra_Library::MIP_Problem; 742 friend class Parma_Polyhedra_Library::Grid; 743 744 friend std::ostream& 745 Parma_Polyhedra_Library::IO_Operators::operator<<(std::ostream& s, 746 const Generator& g); 747 748 friend int 749 compare(const Generator& x, const Generator& y); 750 }; 751 752 753 namespace Parma_Polyhedra_Library { 754 755 //! Shorthand for Generator::line(const Linear_Expression& e, Representation r). 756 /*! \relates Generator */ 757 Generator line(const Linear_Expression& e, 758 Representation r = Generator::default_representation); 759 760 //! Shorthand for Generator::ray(const Linear_Expression& e, Representation r). 761 /*! \relates Generator */ 762 Generator ray(const Linear_Expression& e, 763 Representation r = Generator::default_representation); 764 765 /*! \brief 766 Shorthand for 767 Generator::point(const Linear_Expression& e, Coefficient_traits::const_reference d, Representation r). 768 769 \relates Generator 770 */ 771 Generator 772 point(const Linear_Expression& e = Linear_Expression::zero(), 773 Coefficient_traits::const_reference d = Coefficient_one(), 774 Representation r = Generator::default_representation); 775 776 //! Shorthand for Generator::point(Representation r). 777 /*! \relates Generator */ 778 Generator 779 point(Representation r); 780 781 /*! \brief 782 Shorthand for 783 Generator::point(const Linear_Expression& e, Representation r). 784 785 \relates Generator 786 */ 787 Generator 788 point(const Linear_Expression& e, Representation r); 789 790 /*! \brief 791 Shorthand for 792 Generator::closure_point(const Linear_Expression& e, Coefficient_traits::const_reference d, Representation r). 793 794 \relates Generator 795 */ 796 Generator 797 closure_point(const Linear_Expression& e = Linear_Expression::zero(), 798 Coefficient_traits::const_reference d = Coefficient_one(), 799 Representation r = Generator::default_representation); 800 801 //! Shorthand for Generator::closure_point(Representation r). 802 /*! \relates Generator */ 803 Generator 804 closure_point(Representation r); 805 806 /*! \brief 807 Shorthand for 808 Generator::closure_point(const Linear_Expression& e, Representation r). 809 810 \relates Generator 811 */ 812 Generator 813 closure_point(const Linear_Expression& e, Representation r); 814 815 //! Returns <CODE>true</CODE> if and only if \p x is equivalent to \p y. 816 /*! \relates Generator */ 817 bool operator==(const Generator& x, const Generator& y); 818 819 //! Returns <CODE>true</CODE> if and only if \p x is not equivalent to \p y. 820 /*! \relates Generator */ 821 bool operator!=(const Generator& x, const Generator& y); 822 823 //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. 824 /*! \relates Generator 825 If the rectilinear distance between \p x and \p y is defined, 826 stores an approximation of it into \p r and returns <CODE>true</CODE>; 827 returns <CODE>false</CODE> otherwise. 828 829 The direction of the approximation is specified by \p dir. 830 831 All computations are performed using variables of type 832 <CODE>Checked_Number\<To, Extended_Number_Policy\></CODE>. 833 834 \note 835 Distances are \e only defined between generators that are points and/or 836 closure points; for rays or lines, \c false is returned. 837 */ 838 template <typename To> 839 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 840 const Generator& x, 841 const Generator& y, 842 Rounding_Dir dir); 843 844 //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. 845 /*! \relates Generator 846 If the rectilinear distance between \p x and \p y is defined, 847 stores an approximation of it into \p r and returns <CODE>true</CODE>; 848 returns <CODE>false</CODE> otherwise. 849 850 The direction of the approximation is specified by \p dir. 851 852 All computations are performed using variables of type 853 <CODE>Checked_Number\<Temp, Extended_Number_Policy\></CODE>. 854 855 \note 856 Distances are \e only defined between generators that are points and/or 857 closure points; for rays or lines, \c false is returned. 858 */ 859 template <typename Temp, typename To> 860 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 861 const Generator& x, 862 const Generator& y, 863 Rounding_Dir dir); 864 865 //! Computes the rectilinear (or Manhattan) distance between \p x and \p y. 866 /*! \relates Generator 867 If the rectilinear distance between \p x and \p y is defined, 868 stores an approximation of it into \p r and returns <CODE>true</CODE>; 869 returns <CODE>false</CODE> otherwise. 870 871 The direction of the approximation is specified by \p dir. 872 873 All computations are performed using the temporary variables 874 \p tmp0, \p tmp1 and \p tmp2. 875 876 \note 877 Distances are \e only defined between generators that are points and/or 878 closure points; for rays or lines, \c false is returned. 879 */ 880 template <typename Temp, typename To> 881 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 882 const Generator& x, 883 const Generator& y, 884 Rounding_Dir dir, 885 Temp& tmp0, 886 Temp& tmp1, 887 Temp& tmp2); 888 889 //! Computes the euclidean distance between \p x and \p y. 890 /*! \relates Generator 891 If the euclidean distance between \p x and \p y is defined, 892 stores an approximation of it into \p r and returns <CODE>true</CODE>; 893 returns <CODE>false</CODE> otherwise. 894 895 The direction of the approximation is specified by \p dir. 896 897 All computations are performed using variables of type 898 <CODE>Checked_Number\<To, Extended_Number_Policy\></CODE>. 899 900 \note 901 Distances are \e only defined between generators that are points and/or 902 closure points; for rays or lines, \c false is returned. 903 */ 904 template <typename To> 905 bool euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 906 const Generator& x, 907 const Generator& y, 908 Rounding_Dir dir); 909 910 //! Computes the euclidean distance between \p x and \p y. 911 /*! \relates Generator 912 If the euclidean distance between \p x and \p y is defined, 913 stores an approximation of it into \p r and returns <CODE>true</CODE>; 914 returns <CODE>false</CODE> otherwise. 915 916 The direction of the approximation is specified by \p dir. 917 918 All computations are performed using variables of type 919 <CODE>Checked_Number\<Temp, Extended_Number_Policy\></CODE>. 920 921 \note 922 Distances are \e only defined between generators that are points and/or 923 closure points; for rays or lines, \c false is returned. 924 */ 925 template <typename Temp, typename To> 926 bool rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 927 const Generator& x, 928 const Generator& y, 929 Rounding_Dir dir); 930 931 //! Computes the euclidean distance between \p x and \p y. 932 /*! \relates Generator 933 If the euclidean distance between \p x and \p y is defined, 934 stores an approximation of it into \p r and returns <CODE>true</CODE>; 935 returns <CODE>false</CODE> otherwise. 936 937 The direction of the approximation is specified by \p dir. 938 939 All computations are performed using the temporary variables 940 \p tmp0, \p tmp1 and \p tmp2. 941 942 \note 943 Distances are \e only defined between generators that are points and/or 944 closure points; for rays or lines, \c false is returned. 945 */ 946 template <typename Temp, typename To> 947 bool euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 948 const Generator& x, 949 const Generator& y, 950 Rounding_Dir dir, 951 Temp& tmp0, 952 Temp& tmp1, 953 Temp& tmp2); 954 955 //! Computes the \f$L_\infty\f$ distance between \p x and \p y. 956 /*! \relates Generator 957 If the \f$L_\infty\f$ distance between \p x and \p y is defined, 958 stores an approximation of it into \p r and returns <CODE>true</CODE>; 959 returns <CODE>false</CODE> otherwise. 960 961 The direction of the approximation is specified by \p dir. 962 963 All computations are performed using variables of type 964 <CODE>Checked_Number\<To, Extended_Number_Policy\></CODE>. 965 966 \note 967 Distances are \e only defined between generators that are points and/or 968 closure points; for rays or lines, \c false is returned. 969 */ 970 template <typename To> 971 bool l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 972 const Generator& x, 973 const Generator& y, 974 Rounding_Dir dir); 975 976 //! Computes the \f$L_\infty\f$ distance between \p x and \p y. 977 /*! \relates Generator 978 If the \f$L_\infty\f$ distance between \p x and \p y is defined, 979 stores an approximation of it into \p r and returns <CODE>true</CODE>; 980 returns <CODE>false</CODE> otherwise. 981 982 The direction of the approximation is specified by \p dir. 983 984 All computations are performed using variables of type 985 <CODE>Checked_Number\<Temp, Extended_Number_Policy\></CODE>. 986 987 \note 988 Distances are \e only defined between generators that are points and/or 989 closure points; for rays or lines, \c false is returned. 990 */ 991 template <typename Temp, typename To> 992 bool l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 993 const Generator& x, 994 const Generator& y, 995 Rounding_Dir dir); 996 997 //! Computes the \f$L_\infty\f$ distance between \p x and \p y. 998 /*! \relates Generator 999 If the \f$L_\infty\f$ distance between \p x and \p y is defined, 1000 stores an approximation of it into \p r and returns <CODE>true</CODE>; 1001 returns <CODE>false</CODE> otherwise. 1002 1003 The direction of the approximation is specified by \p dir. 1004 1005 All computations are performed using the temporary variables 1006 \p tmp0, \p tmp1 and \p tmp2. 1007 1008 \note 1009 Distances are \e only defined between generators that are points and/or 1010 closure points; for rays or lines, \c false is returned. 1011 */ 1012 template <typename Temp, typename To> 1013 bool l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r, 1014 const Generator& x, 1015 const Generator& y, 1016 Rounding_Dir dir, 1017 Temp& tmp0, 1018 Temp& tmp1, 1019 Temp& tmp2); 1020 1021 namespace IO_Operators { 1022 1023 //! Output operator. 1024 /*! \relates Parma_Polyhedra_Library::Generator */ 1025 std::ostream& operator<<(std::ostream& s, const Generator::Type& t); 1026 1027 } // namespace IO_Operators 1028 1029 } // namespace Parma_Polyhedra_Library 1030 1031 #include "Generator_inlines.hh" 1032 1033 #endif // !defined(PPL_Generator_defs_hh) 1034