1 /* Grid_Generator_System 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_Grid_Generator_System_defs_hh 25 #define PPL_Grid_Generator_System_defs_hh 1 26 27 #include "Grid_Generator_System_types.hh" 28 29 #include "Linear_System_defs.hh" 30 #include "Grid_Generator_defs.hh" 31 #include "Variables_Set_types.hh" 32 #include "Polyhedron_types.hh" 33 #include <iosfwd> 34 #include <cstddef> 35 36 namespace Parma_Polyhedra_Library { 37 38 namespace IO_Operators { 39 40 //! Output operator. 41 /*! 42 \relates Parma_Polyhedra_Library::Grid_Generator_System 43 Writes <CODE>false</CODE> if \p gs is empty. Otherwise, writes on 44 \p s the generators of \p gs, all in one row and separated by ", ". 45 */ 46 std::ostream& operator<<(std::ostream& s, const Grid_Generator_System& gs); 47 48 } // namespace IO_Operators 49 50 //! Swaps \p x with \p y. 51 /*! \relates Grid_Generator_System */ 52 void swap(Grid_Generator_System& x, Grid_Generator_System& y); 53 54 //! Returns <CODE>true</CODE> if and only if \p x and \p y are identical. 55 /*! \relates Grid_Generator_System */ 56 bool operator==(const Grid_Generator_System& x, 57 const Grid_Generator_System& y); 58 59 } // namespace Parma_Polyhedra_Library 60 61 //! A system of grid generators. 62 /*! \ingroup PPL_CXX_interface 63 An object of the class Grid_Generator_System is a system of 64 grid generators, i.e., a multiset of objects of the class 65 Grid_Generator (lines, parameters and points). 66 When inserting generators in a system, space dimensions are 67 automatically adjusted so that all the generators in the system 68 are defined on the same vector space. 69 A system of grid generators which is meant to define a non-empty 70 grid must include at least one point: the reason is that 71 lines and parameters need a supporting point 72 (lines only specify directions while parameters only 73 specify direction and distance. 74 75 \par 76 In all the examples it is assumed that variables 77 <CODE>x</CODE> and <CODE>y</CODE> are defined as follows: 78 \code 79 Variable x(0); 80 Variable y(1); 81 \endcode 82 83 \par Example 1 84 The following code defines the line having the same direction 85 as the \f$x\f$ axis (i.e., the first Cartesian axis) 86 in \f$\Rset^2\f$: 87 \code 88 Grid_Generator_System gs; 89 gs.insert(grid_line(x + 0*y)); 90 \endcode 91 As said above, this system of generators corresponds to 92 an empty grid, because the line has no supporting point. 93 To define a system of generators that does correspond to 94 the \f$x\f$ axis, we can add the following code which 95 inserts the origin of the space as a point: 96 \code 97 gs.insert(grid_point(0*x + 0*y)); 98 \endcode 99 Since space dimensions are automatically adjusted, the following 100 code obtains the same effect: 101 \code 102 gs.insert(grid_point(0*x)); 103 \endcode 104 In contrast, if we had added the following code, we would have 105 defined a line parallel to the \f$x\f$ axis through 106 the point \f$(0, 1)^\transpose \in \Rset^2\f$. 107 \code 108 gs.insert(grid_point(0*x + 1*y)); 109 \endcode 110 111 \par Example 2 112 The following code builds a system of generators corresponding 113 to the grid consisting of all the integral points on the \f$x\f$ axes; 114 that is, all points satisfying the congruence relation 115 \f[ 116 \bigl\{\, 117 (x, 0)^\transpose \in \Rset^2 118 \bigm| 119 x \pmod{1}\ 0 120 \,\bigr\}, 121 \f] 122 \code 123 Grid_Generator_System gs; 124 gs.insert(parameter(x + 0*y)); 125 gs.insert(grid_point(0*x + 0*y)); 126 \endcode 127 128 \par Example 3 129 The following code builds a system of generators having three points 130 corresponding to a non-relational grid consisting of all points 131 whose coordinates are integer multiple of 3. 132 \code 133 Grid_Generator_System gs; 134 gs.insert(grid_point(0*x + 0*y)); 135 gs.insert(grid_point(0*x + 3*y)); 136 gs.insert(grid_point(3*x + 0*y)); 137 \endcode 138 139 \par Example 4 140 By using parameters instead of two of the points we 141 can define the same grid as that defined in the previous example. 142 Note that there has to be at least one point and, for this purpose, 143 any point in the grid could be considered. 144 Thus the following code builds two identical grids from the 145 grid generator systems \p gs and \p gs1. 146 \code 147 Grid_Generator_System gs; 148 gs.insert(grid_point(0*x + 0*y)); 149 gs.insert(parameter(0*x + 3*y)); 150 gs.insert(parameter(3*x + 0*y)); 151 Grid_Generator_System gs1; 152 gs1.insert(grid_point(3*x + 3*y)); 153 gs1.insert(parameter(0*x + 3*y)); 154 gs1.insert(parameter(3*x + 0*y)); 155 \endcode 156 157 \par Example 5 158 The following code builds a system of generators having one point and 159 a parameter corresponding to all the integral points that 160 lie on \f$x + y = 2\f$ in \f$\Rset^2\f$ 161 \code 162 Grid_Generator_System gs; 163 gs.insert(grid_point(1*x + 1*y)); 164 gs.insert(parameter(1*x - 1*y)); 165 \endcode 166 167 \note 168 After inserting a multiset of generators in a grid generator system, 169 there are no guarantees that an <EM>exact</EM> copy of them 170 can be retrieved: 171 in general, only an <EM>equivalent</EM> grid generator system 172 will be available, where original generators may have been 173 reordered, removed (if they are duplicate or redundant), etc. 174 */ 175 class Parma_Polyhedra_Library::Grid_Generator_System { 176 public: 177 typedef Grid_Generator row_type; 178 179 static const Representation default_representation = SPARSE; 180 181 //! Default constructor: builds an empty system of generators. 182 explicit Grid_Generator_System(Representation r = default_representation); 183 184 //! Builds the singleton system containing only generator \p g. 185 explicit Grid_Generator_System(const Grid_Generator& g, 186 Representation r = default_representation); 187 188 //! Builds an empty system of generators of dimension \p dim. 189 explicit Grid_Generator_System(dimension_type dim, 190 Representation r = default_representation); 191 192 //! Ordinary copy constructor. 193 //! The new Grid_Generator_System will have the same representation as `gs'. 194 Grid_Generator_System(const Grid_Generator_System& gs); 195 196 //! Copy constructor with specified representation. 197 Grid_Generator_System(const Grid_Generator_System& gs, Representation r); 198 199 //! Destructor. 200 ~Grid_Generator_System(); 201 202 //! Assignment operator. 203 Grid_Generator_System& operator=(const Grid_Generator_System& y); 204 205 //! Returns the current representation of *this. 206 Representation representation() const; 207 208 //! Converts *this to the specified representation. 209 void set_representation(Representation r); 210 211 //! Returns the maximum space dimension a Grid_Generator_System can handle. 212 static dimension_type max_space_dimension(); 213 214 //! Returns the dimension of the vector space enclosing \p *this. 215 dimension_type space_dimension() const; 216 217 /*! \brief 218 Removes all the generators from the generator system and sets its 219 space dimension to 0. 220 */ 221 void clear(); 222 223 /*! \brief 224 Inserts into \p *this a copy of the generator \p g, increasing the 225 number of space dimensions if needed. 226 227 If \p g is an all-zero parameter then the only action is to ensure 228 that the space dimension of \p *this is at least the space 229 dimension of \p g. 230 */ 231 void insert(const Grid_Generator& g); 232 233 /*! \brief 234 Inserts into \p *this the generator \p g, increasing the number of 235 space dimensions if needed. 236 */ 237 void insert(Grid_Generator& g, Recycle_Input); 238 239 /*! \brief 240 Inserts into \p *this the generators in \p gs, increasing the 241 number of space dimensions if needed. 242 */ 243 void insert(Grid_Generator_System& gs, Recycle_Input); 244 245 //! Initializes the class. 246 static void initialize(); 247 248 //! Finalizes the class. 249 static void finalize(); 250 251 /*! \brief 252 Returns the singleton system containing only 253 Grid_Generator::zero_dim_point(). 254 */ 255 static const Grid_Generator_System& zero_dim_univ(); 256 257 //! An iterator over a system of grid generators 258 /*! \ingroup PPL_CXX_interface 259 A const_iterator is used to provide read-only access 260 to each generator contained in an object of Grid_Generator_System. 261 262 \par Example 263 The following code prints the system of generators 264 of the grid <CODE>gr</CODE>: 265 \code 266 const Grid_Generator_System& ggs = gr.generators(); 267 for (Grid_Generator_System::const_iterator i = ggs.begin(), 268 ggs_end = ggs.end(); i != ggs_end; ++i) 269 cout << *i << endl; 270 \endcode 271 The same effect can be obtained more concisely by using 272 more features of the STL: 273 \code 274 const Grid_Generator_System& ggs = gr.generators(); 275 copy(ggs.begin(), ggs.end(), ostream_iterator<Grid_Generator>(cout, "\n")); 276 \endcode 277 */ 278 class const_iterator 279 : public std::iterator<std::forward_iterator_tag, 280 Grid_Generator, 281 std::ptrdiff_t, 282 const Grid_Generator*, 283 const Grid_Generator&> { 284 public: 285 //! Default constructor. 286 const_iterator(); 287 288 //! Ordinary copy constructor. 289 const_iterator(const const_iterator& y); 290 291 //! Destructor. 292 ~const_iterator(); 293 294 //! Assignment operator. 295 const_iterator& operator=(const const_iterator& y); 296 297 //! Dereference operator. 298 const Grid_Generator& operator*() const; 299 300 //! Indirect member selector. 301 const Grid_Generator* operator->() const; 302 303 //! Prefix increment operator. 304 const_iterator& operator++(); 305 306 //! Postfix increment operator. 307 const_iterator operator++(int); 308 309 /*! \brief 310 Returns <CODE>true</CODE> if and only if \p *this and \p y are 311 identical. 312 */ 313 bool operator==(const const_iterator& y) const; 314 315 /*! \brief 316 Returns <CODE>true</CODE> if and only if \p *this and \p y are 317 different. 318 */ 319 bool operator!=(const const_iterator& y) const; 320 321 private: 322 friend class Grid_Generator_System; 323 324 Linear_System<Grid_Generator>::const_iterator i; 325 326 //! Copy constructor from Linear_System< Grid_Generator>::const_iterator. 327 const_iterator(const Linear_System<Grid_Generator>::const_iterator& y); 328 }; 329 330 //! Returns <CODE>true</CODE> if and only if \p *this has no generators. 331 bool empty() const; 332 333 /*! \brief 334 Returns the const_iterator pointing to the first generator, if \p 335 *this is not empty; otherwise, returns the past-the-end 336 const_iterator. 337 */ 338 const_iterator begin() const; 339 340 //! Returns the past-the-end const_iterator. 341 const_iterator end() const; 342 343 //! Returns the number of rows (generators) in the system. 344 dimension_type num_rows() const; 345 346 //! Returns the number of parameters in the system. 347 dimension_type num_parameters() const; 348 349 //! Returns the number of lines in the system. 350 dimension_type num_lines() const; 351 352 /*! \brief 353 Returns <CODE>true</CODE> if and only if \p *this contains one or 354 more points. 355 */ 356 bool has_points() const; 357 358 //! Returns <CODE>true</CODE> if \p *this is identical to \p y. 359 bool is_equal_to(const Grid_Generator_System& y) const; 360 361 //! Checks if all the invariants are satisfied. 362 bool OK() const; 363 364 PPL_OUTPUT_DECLARATIONS 365 366 /*! \brief 367 Loads from \p s an ASCII representation (as produced by 368 ascii_dump(std::ostream&) const) and sets \p *this accordingly. 369 Returns <CODE>true</CODE> if successful, <CODE>false</CODE> otherwise. 370 371 Resizes the matrix of generators using the numbers of rows and columns 372 read from \p s, then initializes the coordinates of each generator 373 and its type reading the contents from \p s. 374 */ 375 bool ascii_load(std::istream& s); 376 377 //! Returns the total size in bytes of the memory occupied by \p *this. 378 memory_size_type total_memory_in_bytes() const; 379 380 //! Returns the size in bytes of the memory managed by \p *this. 381 memory_size_type external_memory_in_bytes() const; 382 383 //! Swaps \p *this with \p y. 384 void m_swap(Grid_Generator_System& y); 385 386 private: 387 //! Returns a constant reference to the \p k- th generator of the system. 388 const Grid_Generator& operator[](dimension_type k) const; 389 390 //! Assigns to a given variable an affine expression. 391 /*! 392 \param v 393 The variable to which the affine transformation is assigned; 394 395 \param expr 396 The numerator of the affine transformation: 397 \f$\sum_{i = 0}^{n - 1} a_i x_i + b\f$; 398 399 \param denominator 400 The denominator of the affine transformation; 401 402 We allow affine transformations (see the Section \ref 403 rational_grid_operations)to have rational 404 coefficients. Since the coefficients of linear expressions are 405 integers we also provide an integer \p denominator that will 406 be used as denominator of the affine transformation. The 407 denominator is required to be a positive integer and its 408 default value is 1. 409 410 The affine transformation assigns to every variable \p v, in every 411 column, the follow expression: 412 \f[ 413 \frac{\sum_{i = 0}^{n - 1} a_i x_i + b} 414 {\mathrm{denominator}}. 415 \f] 416 417 \p expr is a constant parameter and unaltered by this computation. 418 */ 419 void affine_image(Variable v, 420 const Linear_Expression& expr, 421 Coefficient_traits::const_reference denominator); 422 423 //! Sets the sortedness flag of the system to \p b. 424 void set_sorted(bool b); 425 426 /*! \brief 427 Adds \p dims rows and \p dims columns of zeroes to the matrix, 428 initializing the added rows as in the universe system. 429 430 \param dims 431 The number of rows and columns to be added: must be strictly 432 positive. 433 434 Turns the \f$r \times c\f$ matrix \f$A\f$ into the \f$(r+dims) 435 \times (c+dims)\f$ matrix 436 \f$\bigl(\genfrac{}{}{0pt}{}{A}{0} \genfrac{}{}{0pt}{}{0}{B}\bigr)\f$ 437 where \f$B\f$ is the \f$dims \times dims\f$ unit matrix of the form 438 \f$\bigl(\genfrac{}{}{0pt}{}{1}{0} \genfrac{}{}{0pt}{}{0}{1}\bigr)\f$. 439 The matrix is expanded avoiding reallocation whenever possible. 440 */ 441 void add_universe_rows_and_columns(dimension_type dims); 442 443 //! Resizes the system to the specified space dimension. 444 void set_space_dimension(dimension_type space_dim); 445 446 //! Removes all the specified dimensions from the generator system. 447 /*! 448 The space dimension of the variable with the highest space 449 dimension in \p vars must be at most the space dimension 450 of \p this. 451 */ 452 void remove_space_dimensions(const Variables_Set& vars); 453 454 //! Shift by \p n positions the coefficients of variables, starting from 455 //! the coefficient of \p v. This increases the space dimension by \p n. 456 void shift_space_dimensions(Variable v, dimension_type n); 457 458 //! Sets the index to indicate that the system has no pending rows. 459 void unset_pending_rows(); 460 461 //! Permutes the space dimensions of the matrix. 462 /* 463 \param cycle 464 A vector representing a cycle of the permutation according to which the 465 columns must be rearranged. 466 467 The \p cycle vector represents a cycle of a permutation of space 468 dimensions. 469 For example, the permutation 470 \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be 471 represented by the vector containing \f$ x_1, x_2, x_3 \f$. 472 */ 473 void permute_space_dimensions(const std::vector<Variable>& cycle); 474 475 bool has_no_rows() const; 476 477 //! Makes the system shrink by removing its \p n trailing rows. 478 void remove_trailing_rows(dimension_type n); 479 480 void insert_verbatim(const Grid_Generator& g); 481 482 //! Returns the system topology. 483 Topology topology() const; 484 485 //! Returns the index of the first pending row. 486 dimension_type first_pending_row() const; 487 488 Linear_System<Grid_Generator> sys; 489 490 /*! \brief 491 Holds (between class initialization and finalization) a pointer to 492 the singleton system containing only Grid_Generator::zero_dim_point(). 493 */ 494 static const Grid_Generator_System* zero_dim_univ_p; 495 496 friend bool 497 operator==(const Grid_Generator_System& x, const Grid_Generator_System& y); 498 499 //! Sets the index of the first pending row to \p i. 500 void set_index_first_pending_row(dimension_type i); 501 502 //! Removes all the invalid lines and parameters. 503 /*! 504 The invalid lines and parameters are those with all 505 the homogeneous terms set to zero. 506 */ 507 void remove_invalid_lines_and_parameters(); 508 509 friend class Polyhedron; 510 friend class Grid; 511 }; 512 513 // Grid_Generator_System_inlines.hh is not included here on purpose. 514 515 #endif // !defined(PPL_Grid_Generator_System_defs_hh) 516