A system of grid generators. More...

#include <Grid_Generator_System_defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::Grid_Generator_System:

[legend]

Classes
class	const_iterator
	An iterator over a system of grid generators. More...

Public Types
typedef Grid_Generator	row_type

Public Member Functions
	Grid_Generator_System (Representation r=default_representation)
	Default constructor: builds an empty system of generators. More...

	Grid_Generator_System (const Grid_Generator &g, Representation r=default_representation)
	Builds the singleton system containing only generator `g`. More...

	Grid_Generator_System (dimension_type dim, Representation r=default_representation)
	Builds an empty system of generators of dimension `dim`. More...

	Grid_Generator_System (const Grid_Generator_System &gs)

	Grid_Generator_System (const Grid_Generator_System &gs, Representation r)
	Copy constructor with specified representation. More...

	~Grid_Generator_System ()
	Destructor. More...

Grid_Generator_System &	operator= (const Grid_Generator_System &y)
	Assignment operator. More...

Representation	representation () const
	Returns the current representation of *this. More...

void	set_representation (Representation r)
	Converts *this to the specified representation. More...

dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`. More...

void	clear ()
	Removes all the generators from the generator system and sets its space dimension to 0. More...

void	insert (const Grid_Generator &g)
	Inserts into `*this` a copy of the generator `g`, increasing the number of space dimensions if needed. More...

void	insert (Grid_Generator &g, Recycle_Input)
	Inserts into `*this` the generator `g`, increasing the number of space dimensions if needed. More...

void	insert (Grid_Generator_System &gs, Recycle_Input)
	Inserts into `*this` the generators in `gs`, increasing the number of space dimensions if needed. More...

bool	empty () const
	Returns `true` if and only if `*this` has no generators. More...

const_iterator	begin () const
	Returns the const_iterator pointing to the first generator, if `this` is not empty; otherwise, returns the past-the-end const_iterator. More...

const_iterator	end () const
	Returns the past-the-end const_iterator. More...

dimension_type	num_rows () const
	Returns the number of rows (generators) in the system. More...

dimension_type	num_parameters () const
	Returns the number of parameters in the system. More...

dimension_type	num_lines () const
	Returns the number of lines in the system. More...

bool	has_points () const
	Returns `true` if and only if `*this` contains one or more points. More...

bool	is_equal_to (const Grid_Generator_System &y) const
	Returns `true` if `*this` is identical to `y`. More...

bool	OK () const
	Checks if all the invariants are satisfied. More...

void	ascii_dump () const
	Writes to `std::cerr` an ASCII representation of `*this`. More...

void	ascii_dump (std::ostream &s) const
	Writes to `s` an ASCII representation of `*this`. More...

void	print () const
	Prints `*this` to `std::cerr` using `operator<<`. More...

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise. More...

memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by `*this`. More...

memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`. More...

void	m_swap (Grid_Generator_System &y)
	Swaps `*this` with `y`. More...

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension a Grid_Generator_System can handle. More...

static void	initialize ()
	Initializes the class. More...

static void	finalize ()
	Finalizes the class. More...

static const Grid_Generator_System &	zero_dim_univ ()
	Returns the singleton system containing only Grid_Generator::zero_dim_point(). More...

Static Public Attributes
static const Representation	default_representation = SPARSE

Private Member Functions
const Grid_Generator &	operator[] (dimension_type k) const
	Returns a constant reference to the `k-` th generator of the system. More...

void	affine_image (Variable v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
	Assigns to a given variable an affine expression. More...

void	set_sorted (bool b)
	Sets the sortedness flag of the system to `b`. More...

void	add_universe_rows_and_columns (dimension_type dims)
	Adds `dims` rows and `dims` columns of zeroes to the matrix, initializing the added rows as in the universe system. More...

void	set_space_dimension (dimension_type space_dim)
	Resizes the system to the specified space dimension. More...

void	remove_space_dimensions (const Variables_Set &vars)
	Removes all the specified dimensions from the generator system. More...

void	shift_space_dimensions (Variable v, dimension_type n)

void	unset_pending_rows ()
	Sets the index to indicate that the system has no pending rows. More...

void	permute_space_dimensions (const std::vector< Variable > &cycle)
	Permutes the space dimensions of the matrix. More...

bool	has_no_rows () const

void	remove_trailing_rows (dimension_type n)
	Makes the system shrink by removing its `n` trailing rows. More...

void	insert_verbatim (const Grid_Generator &g)

Topology	topology () const
	Returns the system topology. More...

dimension_type	first_pending_row () const
	Returns the index of the first pending row. More...

void	set_index_first_pending_row (dimension_type i)
	Sets the index of the first pending row to `i`. More...

void	remove_invalid_lines_and_parameters ()
	Removes all the invalid lines and parameters. More...

Private Attributes
Linear_System< Grid_Generator >	sys

Static Private Attributes
static const Grid_Generator_System *	zero_dim_univ_p = 0
	Holds (between class initialization and finalization) a pointer to the singleton system containing only Grid_Generator::zero_dim_point(). More...

Friends
class	Polyhedron

class	Grid

bool	operator== (const Grid_Generator_System &x, const Grid_Generator_System &y)

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const Grid_Generator_System &gs)

std::ostream &	operator<< (std::ostream &s, const Grid_Generator_System &gs)
	Output operator. More...

void	swap (Grid_Generator_System &x, Grid_Generator_System &y)
	Swaps `x` with `y`. More...

bool	operator== (const Grid_Generator_System &x, const Grid_Generator_System &y)
	Returns `true` if and only if `x` and `y` are identical. More...

bool	operator== (const Grid_Generator_System &x, const Grid_Generator_System &y)

void	swap (Grid_Generator_System &x, Grid_Generator_System &y)

Detailed Description

A system of grid generators.

An object of the class Grid_Generator_System is a system of grid generators, i.e., a multiset of objects of the class Grid_Generator (lines, parameters and points). When inserting generators in a system, space dimensions are automatically adjusted so that all the generators in the system are defined on the same vector space. A system of grid generators which is meant to define a non-empty grid must include at least one point: the reason is that lines and parameters need a supporting point (lines only specify directions while parameters only specify direction and distance.

: In all the examples it is assumed that variables x and y are defined as follows:
Variable x(0);

Variable y(1);

Example 1: The following code defines the line having the same direction as the axis (i.e., the first Cartesian axis) in $\Rset^2$ :
Grid_Generator_System gs;

gs.insert(grid_line(x + 0*y));

As said above, this system of generators corresponds to an empty grid, because the line has no supporting point. To define a system of generators that does correspond to the axis, we can add the following code which inserts the origin of the space as a point:
gs.insert(grid_point(0*x + 0*y));

Since space dimensions are automatically adjusted, the following code obtains the same effect:
gs.insert(grid_point(0*x));

In contrast, if we had added the following code, we would have defined a line parallel to the axis through the point $(0, 1)^\transpose \in \Rset^2$ .
gs.insert(grid_point(0*x + 1*y));

Example 2: The following code builds a system of generators corresponding to the grid consisting of all the integral points on the axes; that is, all points satisfying the congruence relation
$\bigl\{\, (x, 0)^\transpose \in \Rset^2 \bigm| x \pmod{1}\ 0 \,\bigr\},$

Grid_Generator_System gs;

gs.insert(parameter(x + 0*y));

gs.insert(grid_point(0*x + 0*y));

Example 3: The following code builds a system of generators having three points corresponding to a non-relational grid consisting of all points whose coordinates are integer multiple of 3.
Grid_Generator_System gs;

gs.insert(grid_point(0*x + 0*y));

gs.insert(grid_point(0*x + 3*y));

gs.insert(grid_point(3*x + 0*y));

Example 4: By using parameters instead of two of the points we can define the same grid as that defined in the previous example. Note that there has to be at least one point and, for this purpose, any point in the grid could be considered. Thus the following code builds two identical grids from the grid generator systems gs and gs1.
Grid_Generator_System gs;

gs.insert(grid_point(0*x + 0*y));

gs.insert(parameter(0*x + 3*y));

gs.insert(parameter(3*x + 0*y));

Grid_Generator_System gs1;

gs1.insert(grid_point(3*x + 3*y));

gs1.insert(parameter(0*x + 3*y));

gs1.insert(parameter(3*x + 0*y));

Example 5: The following code builds a system of generators having one point and a parameter corresponding to all the integral points that lie on in $\Rset^2$
Grid_Generator_System gs;

gs.insert(grid_point(1*x + 1*y));

gs.insert(parameter(1*x - 1*y));

Note: After inserting a multiset of generators in a grid generator system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent grid generator system will be available, where original generators may have been reordered, removed (if they are duplicate or redundant), etc.

Definition at line 175 of file Grid_Generator_System_defs.hh.

Member Typedef Documentation

typedef Grid_Generator Parma_Polyhedra_Library::Grid_Generator_System::row_type

Definition at line 177 of file Grid_Generator_System_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System ( Representation r = default_representation )

inlineexplicit

Default constructor: builds an empty system of generators.

Definition at line 58 of file Grid_Generator_System_inlines.hh.

References space_dimension(), and sys.

   : sys(NECESSARILY_CLOSED, r) {
   sys.set_sorted(false);
   PPL_ASSERT(space_dimension() == 0);
 }

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System	(	const Grid_Generator &	g,
		Representation	r = `default_representation`
	)

inlineexplicit

Builds the singleton system containing only generator g.

Definition at line 85 of file Grid_Generator_System_inlines.hh.

References sys.

   : sys(NECESSARILY_CLOSED, r) {
   sys.insert(g);
   sys.set_sorted(false);
 }

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System	(	dimension_type	dim,
		Representation	r = `default_representation`
	)

inlineexplicit

Builds an empty system of generators of dimension dim.

Definition at line 76 of file Grid_Generator_System_inlines.hh.

References space_dimension(), and sys.

   : sys(NECESSARILY_CLOSED, r) {
   sys.set_space_dimension(dim);
   sys.set_sorted(false);
   PPL_ASSERT(space_dimension() == dim);
 }

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System ( const Grid_Generator_System & gs )

inline

Ordinary copy constructor. The new Grid_Generator_System will have the same representation as `gs'.

Definition at line 65 of file Grid_Generator_System_inlines.hh.

66 : sys(gs.sys) {

67 }

Parma_Polyhedra_Library::Grid_Generator_System::sys

Linear_System< Grid_Generator > sys

Definition: Grid_Generator_System_defs.hh:488

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System	(	const Grid_Generator_System &	gs,
		Representation	r
	)

inline

Copy constructor with specified representation.

Definition at line 70 of file Grid_Generator_System_inlines.hh.

72 : sys(gs.sys, r) {

73 }

Parma_Polyhedra_Library::Grid_Generator_System::sys

Linear_System< Grid_Generator > sys

Definition: Grid_Generator_System_defs.hh:488

Parma_Polyhedra_Library::Grid_Generator_System::~Grid_Generator_System ( )

inline

Destructor.

Definition at line 93 of file Grid_Generator_System_inlines.hh.

93 {

94 }

Member Function Documentation

void Parma_Polyhedra_Library::Grid_Generator_System::add_universe_rows_and_columns ( dimension_type dims )

private

Adds dims rows and dims columns of zeroes to the matrix, initializing the added rows as in the universe system.

Parameters

dims	The number of rows and columns to be added: must be strictly positive.

Turns the $r \times c$ matrix $A$ into the $(r+dims) \times (c+dims)$ matrix $\bigl(\genfrac{}{}{0pt}{}{A}{0} \genfrac{}{}{0pt}{}{0}{B}\bigr)$ where $B$ is the $dims \times dims$ unit matrix of the form $\bigl(\genfrac{}{}{0pt}{}{1}{0} \genfrac{}{}{0pt}{}{0}{1}\bigr)$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 199 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Grid_Generator::expr, Parma_Polyhedra_Library::Grid_Generator::LINE_OR_EQUALITY, Parma_Polyhedra_Library::NECESSARILY_CLOSED, and Parma_Polyhedra_Library::Grid_Generator::OK().

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions().

                                                    {
   dimension_type col = sys.space_dimension();
 
   set_space_dimension(space_dimension() + dims);
 
   // Add the new rows and set their diagonal element.
   for (dimension_type i = 0; i < dims; ++i) {
     Grid_Generator tmp(space_dimension(), Grid_Generator::LINE_OR_EQUALITY,
                        NECESSARILY_CLOSED, representation());
     tmp.expr += Variable(col);
     PPL_ASSERT(tmp.OK());
     ++col;
     sys.insert(tmp, Recycle_Input());
   }
 }

void Parma_Polyhedra_Library::Grid_Generator_System::affine_image	(	Variable	v,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator
	)

private

Assigns to a given variable an affine expression.

Parameters

v	The variable to which the affine transformation is assigned;
expr	The numerator of the affine transformation: $\sum_{i = 0}^{n - 1} a_i x_i + b$ ;
denominator	The denominator of the affine transformation;

We allow affine transformations (see the Section Operations on Rational Grids)to have rational coefficients. Since the coefficients of linear expressions are integers we also provide an integer denominator that will be used as denominator of the affine transformation. The denominator is required to be a positive integer and its default value is 1.

The affine transformation assigns to every variable v, in every column, the follow expression:

$\frac{\sum_{i = 0}^{n - 1} a_i x_i + b} {\mathrm{denominator}}.$

expr is a constant parameter and unaltered by this computation.

Definition at line 80 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Linear_Expression::coefficient(), Parma_Polyhedra_Library::Grid_Generator::expr, num_rows(), Parma_Polyhedra_Library::Grid_Generator::OK(), PPL_DIRTY_TEMP_COEFFICIENT, remove_invalid_lines_and_parameters(), Parma_Polyhedra_Library::Linear_Expression::set_coefficient(), Parma_Polyhedra_Library::Variable::space_dimension(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), and sys.

                                                               {
   // This is mostly a copy of Generator_System::affine_image.
 
   Grid_Generator_System& x = *this;
   PPL_ASSERT(v.space_dimension() <= x.sys.space_dimension());
   PPL_ASSERT(expr.space_dimension() <= x.sys.space_dimension());
   PPL_ASSERT(denominator > 0);
 
   const dimension_type num_rows = x.num_rows();
 
   // Compute the numerator of the affine transformation and assign it
   // to the column of `*this' indexed by `v'.
   PPL_DIRTY_TEMP_COEFFICIENT(numerator);
 
   for (dimension_type i = num_rows; i-- > 0; ) {
     Grid_Generator& row = sys.rows[i];
     Scalar_Products::assign(numerator, expr, row.expr);
     if (denominator != 1) {
       // Since we want integer elements in the matrix,
       // we multiply by `denominator' all the columns of `*this'
       // having an index different from `v'.
       // Note that this operation also modifies the coefficient of v, but
       // it will be overwritten by the set_coefficient() below.
       row.expr *= denominator;
     }
     row.expr.set_coefficient(v, numerator);
     // Check that the row is stll OK after fiddling with its internal data.
     PPL_ASSERT(row.OK());
   }
 
   PPL_ASSERT(sys.OK());
 
   // If the mapping is not invertible we may have transformed valid
   // lines and rays into the origin of the space.
   const bool not_invertible = (v.space_dimension() >= expr.space_dimension()
                                || expr.coefficient(v) == 0);
   if (not_invertible) {
     x.remove_invalid_lines_and_parameters();
   }
 }

void Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump ( std::ostream & s ) const

Writes to s an ASCII representation of *this.

Definition at line 126 of file Grid_Generator_System.cc.

                                                         {
   sys.ascii_dump(s);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump ( ) const

Writes to std::cerr an ASCII representation of *this.

Referenced by Parma_Polyhedra_Library::Grid::OK().

bool Parma_Polyhedra_Library::Grid_Generator_System::ascii_load ( std::istream & s )

Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.

Resizes the matrix of generators using the numbers of rows and columns read from s, then initializes the coordinates of each generator and its type reading the contents from s.

Definition at line 131 of file Grid_Generator_System.cc.

                                                   {
   if (!sys.ascii_load(s)) {
     return false;
   }
 
   PPL_ASSERT(OK());
   return true;
 }

Grid_Generator_System::const_iterator Parma_Polyhedra_Library::Grid_Generator_System::begin ( ) const

inline

Returns the const_iterator pointing to the first generator, if this is not empty; otherwise, returns the past-the-end const_iterator.

Definition at line 225 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::map_space_dimensions(), operator<<(), and Parma_Polyhedra_Library::Grid::simplify_using_context_assign().

                                    {
   return static_cast<Grid_Generator_System::const_iterator>(sys.begin());
 }

void Parma_Polyhedra_Library::Grid_Generator_System::clear ( )

inline

Removes all the generators from the generator system and sets its space dimension to 0.

Definition at line 131 of file Grid_Generator_System_inlines.hh.

References space_dimension(), and sys.

Referenced by Parma_Polyhedra_Library::Grid::conversion(), and insert().

                              {
   sys.clear();
   sys.set_sorted(false);
   sys.unset_pending_rows();
   PPL_ASSERT(space_dimension() == 0);
 }

bool Parma_Polyhedra_Library::Grid_Generator_System::empty ( ) const

inline

Returns true if and only if *this has no generators.

Definition at line 214 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Box< ITV >::Box(), and Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate().

                                    {
   return sys.has_no_rows();
 }

Grid_Generator_System::const_iterator Parma_Polyhedra_Library::Grid_Generator_System::end ( ) const

inline

Returns the past-the-end const_iterator.

Definition at line 230 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::map_space_dimensions(), operator<<(), and Parma_Polyhedra_Library::Grid::simplify_using_context_assign().

                                  {
   return static_cast<Grid_Generator_System::const_iterator>(sys.end());
 }

memory_size_type Parma_Polyhedra_Library::Grid_Generator_System::external_memory_in_bytes ( ) const

inline

Returns the size in bytes of the memory managed by *this.

Definition at line 144 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by total_memory_in_bytes().

                                                       {
   return sys.external_memory_in_bytes();
 }

void Parma_Polyhedra_Library::Grid_Generator_System::finalize ( )

static

Finalizes the class.

Definition at line 151 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Init::~Init().

                                    {
   PPL_ASSERT(zero_dim_univ_p != 0);
   delete zero_dim_univ_p;
   zero_dim_univ_p = 0;
 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::first_pending_row ( ) const

inlineprivate

Returns the index of the first pending row.

Definition at line 260 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::conversion().

                                                {
   return sys.first_pending_row();
 }

bool Parma_Polyhedra_Library::Grid_Generator_System::has_no_rows ( ) const

inlineprivate

Definition at line 240 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_grid_generators(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::generator_widening_assign(), Parma_Polyhedra_Library::Grid::map_space_dimensions(), Parma_Polyhedra_Library::Grid::OK(), and Parma_Polyhedra_Library::Grid::simplify().

                                          {
   return sys.has_no_rows();
 }

bool Parma_Polyhedra_Library::Grid_Generator_System::has_points ( ) const

Returns true if and only if *this contains one or more points.

Definition at line 255 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_grid_generators(), and Parma_Polyhedra_Library::Grid::construct().

                                            {
   const Grid_Generator_System& ggs = *this;
   for (dimension_type i = num_rows(); i-- > 0; ) {
     if (!ggs[i].is_line_or_parameter()) {
       return true;
     }
   }
   return false;
 }

void Parma_Polyhedra_Library::Grid_Generator_System::initialize ( )

static

Initializes the class.

Definition at line 144 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Grid_Generator::zero_dim_point().

Referenced by Parma_Polyhedra_Library::Init::Init().

                                      {
   PPL_ASSERT(zero_dim_univ_p == 0);
   zero_dim_univ_p
     = new Grid_Generator_System(Grid_Generator::zero_dim_point());
 }

void Parma_Polyhedra_Library::Grid_Generator_System::insert ( const Grid_Generator & g )

Inserts into *this a copy of the generator g, increasing the number of space dimensions if needed.

If g is an all-zero parameter then the only action is to ensure that the space dimension of *this is at least the space dimension of g.

Definition at line 56 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Affine_Space::Affine_Space(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::generalized_affine_image(), Parma_Polyhedra_Library::Grid::generalized_affine_preimage(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Grid::map_space_dimensions(), Parma_Polyhedra_Library::Grid::select_wider_generators(), and Parma_Polyhedra_Library::Grid::upper_bound_assign().

                                                         {
   Grid_Generator tmp(g, representation());
   insert(tmp, Recycle_Input());
 }

void Parma_Polyhedra_Library::Grid_Generator_System::insert	(	Grid_Generator &	g,
		Recycle_Input
	)

Inserts into *this the generator g, increasing the number of space dimensions if needed.

Definition at line 62 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Grid_Generator::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::Grid_Generator::is_parameter(), and Parma_Polyhedra_Library::Grid_Generator::space_dimension().

                                                                  {
   if (g.is_parameter() && g.all_homogeneous_terms_are_zero()) {
     // There is no need to add the origin as a parameter,
     // as it will be immediately flagged as redundant.
     // However, we still have to adjust space dimension.
     if (space_dimension() < g.space_dimension()) {
       set_space_dimension(g.space_dimension());
     }
     return;
   }
 
   sys.insert(g, Recycle_Input());
 
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Grid_Generator_System::insert	(	Grid_Generator_System &	gs,
		Recycle_Input
	)

Inserts into *this the generators in gs, increasing the number of space dimensions if needed.

Definition at line 36 of file Grid_Generator_System.cc.

References clear(), num_rows(), set_space_dimension(), space_dimension(), sys, and unset_pending_rows().

                                                                          {
   const dimension_type gs_num_rows = gs.num_rows();
 
   if (space_dimension() < gs.space_dimension()) {
     set_space_dimension(gs.space_dimension());
   }
   else {
     gs.set_space_dimension(space_dimension());
   }
 
   for (dimension_type i = 0; i < gs_num_rows; ++i) {
     sys.insert(gs.sys.rows[i], Recycle_Input());
   }
 
   gs.clear();
 
   unset_pending_rows();
 }

void Parma_Polyhedra_Library::Grid_Generator_System::insert_verbatim ( const Grid_Generator & g )

inlineprivate

Definition at line 250 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::conversion().

                                                               {
   sys.insert(g);
 }

bool Parma_Polyhedra_Library::Grid_Generator_System::is_equal_to ( const Grid_Generator_System & y ) const

inline

Returns true if *this is identical to y.

Definition at line 53 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by operator==().

                                                                        {
   return (sys == y.sys);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::m_swap ( Grid_Generator_System & y )

inline

Swaps *this with y.

Definition at line 139 of file Grid_Generator_System_inlines.hh.

References swap(), and sys.

Referenced by Parma_Polyhedra_Library::Grid::OK(), and swap().

                                                       {
   swap(sys, y.sys);
 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a Grid_Generator_System can handle.

Definition at line 114 of file Grid_Generator_System_inlines.hh.

References Parma_Polyhedra_Library::Linear_System< Row >::max_space_dimension().

Referenced by Parma_Polyhedra_Library::Grid::max_space_dimension().

                                            {
   // Grid generators use an extra column for the parameter divisor.
   return Linear_System<Grid_Generator>::max_space_dimension() - 1;
 }

PPL::dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_lines ( ) const

Returns the number of lines in the system.

Definition at line 266 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Grid::generator_widening_assign(), and Parma_Polyhedra_Library::Grid::quick_equivalence_test().

                                           {
   // We are sure that this method is applied only to a matrix
   // that does not contain pending rows.
   PPL_ASSERT(sys.num_pending_rows() == 0);
   const Grid_Generator_System& ggs = *this;
   dimension_type n = 0;
   // If the Linear_System happens to be sorted, take advantage of the fact
   // that lines are at the top of the system.
   if (sys.is_sorted()) {
     const dimension_type nrows = num_rows();
     for (dimension_type i = 0; i < nrows && ggs[i].is_line(); ++i) {
       ++n;
     }
   }
   else {
     for (dimension_type i = num_rows(); i-- > 0 ; ) {
       if (ggs[i].is_line()) {
         ++n;
       }
     }
   }
   return n;
 }

PPL::dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_parameters ( ) const

Returns the number of parameters in the system.

Definition at line 291 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Grid::generator_widening_assign(), and Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate().

                                                {
   // We are sure that this method is applied only to a matrix
   // that does not contain pending rows.
   PPL_ASSERT(sys.num_pending_rows() == 0);
   const Grid_Generator_System& ggs = *this;
   dimension_type n = 0;
   // If the Linear_System happens to be sorted, take advantage of the fact
   // that rays and points are at the bottom of the system and
   // rays have the inhomogeneous term equal to zero.
   if (sys.is_sorted()) {
     for (dimension_type i = num_rows();
          i != 0 && ggs[--i].is_parameter_or_point(); ) {
       if (ggs[i].is_line_or_parameter()) {
         ++n;
       }
     }
   }
   else {
     for (dimension_type i = num_rows(); i-- > 0 ; ) {
       if (ggs[i].is_parameter()) {
         ++n;
       }
     }
   }
   return n;
 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_rows ( ) const

inline

Returns the number of rows (generators) in the system.

Definition at line 154 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by affine_image(), Parma_Polyhedra_Library::Grid::conversion(), Parma_Polyhedra_Library::Grid::generator_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), insert(), Parma_Polyhedra_Library::Grid::normalize_divisors(), Parma_Polyhedra_Library::Grid::quick_equivalence_test(), Parma_Polyhedra_Library::Grid::simplify(), Parma_Polyhedra_Library::Grid::time_elapse_assign(), and Parma_Polyhedra_Library::Grid::upper_triangular().

                                       {
   return sys.num_rows();
 }

bool Parma_Polyhedra_Library::Grid_Generator_System::OK ( ) const

Checks if all the invariants are satisfied.

Definition at line 158 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED.

                                    {
   if (sys.topology() == NOT_NECESSARILY_CLOSED) {
 #ifndef NDEBUG
     std::cerr << "Grid_Generator_System is NOT_NECESSARILY_CLOSED"
               << std::endl;
 #endif
     return false;
   }
 
   if (sys.is_sorted()) {
 #ifndef NDEBUG
     std::cerr << "Grid_Generator_System is marked as sorted."
               << std::endl;
 #endif
     return false;
   }
 
   return sys.OK();
 }

Grid_Generator_System & Parma_Polyhedra_Library::Grid_Generator_System::operator= ( const Grid_Generator_System & y )

inline

Assignment operator.

Definition at line 97 of file Grid_Generator_System_inlines.hh.

References swap().

                                                                {
   Grid_Generator_System tmp = y;
   swap(*this, tmp);
   return *this;
 }

const Grid_Generator & Parma_Polyhedra_Library::Grid_Generator_System::operator[] ( dimension_type k ) const

inlineprivate

Returns a constant reference to the k- th generator of the system.

Definition at line 235 of file Grid_Generator_System_inlines.hh.

References sys.

                                                               {
   return sys[k];
 }

void Parma_Polyhedra_Library::Grid_Generator_System::permute_space_dimensions ( const std::vector< Variable > & cycle )

inlineprivate

Permutes the space dimensions of the matrix.

Definition at line 48 of file Grid_Generator_System_inlines.hh.

Referenced by Parma_Polyhedra_Library::Grid::map_space_dimensions().

                                                            {
   return sys.permute_space_dimensions(cycle);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::print ( ) const

Prints *this to std::cerr using operator<<.

void Parma_Polyhedra_Library::Grid_Generator_System::remove_invalid_lines_and_parameters ( )

private

Removes all the invalid lines and parameters.

The invalid lines and parameters are those with all the homogeneous terms set to zero.

Definition at line 235 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Grid_Generator::all_homogeneous_terms_are_zero(), and Parma_Polyhedra_Library::Grid_Generator::is_line_or_parameter().

Referenced by affine_image().

                                                               {
   // The origin of the vector space cannot be a valid line/parameter.
   // NOTE: the following swaps will mix grid generators without even trying
   // to preserve sortedness: as a matter of fact, it will almost always
   // be the case that the input generator system is NOT sorted.
 
   // Note that the num_rows() value is *not* constant because remove_row()
   // decreases it.
   for (dimension_type i = 0; i < num_rows(); ) {
     const Grid_Generator& g = (*this)[i];
     if (g.is_line_or_parameter() && g.all_homogeneous_terms_are_zero()) {
       sys.remove_row(i, false);
     }
     else {
       ++i;
     }
   }
 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions ( const Variables_Set & vars )

private

Removes all the specified dimensions from the generator system.

The space dimension of the variable with the highest space dimension in vars must be at most the space dimension of this.

Definition at line 217 of file Grid_Generator_System.cc.

                                                    {
   sys.remove_space_dimensions(vars);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_trailing_rows ( dimension_type n )

inlineprivate

Makes the system shrink by removing its n trailing rows.

Definition at line 245 of file Grid_Generator_System_inlines.hh.

References sys.

                                                             {
   sys.remove_trailing_rows(n);
 }

Representation Parma_Polyhedra_Library::Grid_Generator_System::representation ( ) const

inline

Returns the current representation of *this.

Definition at line 104 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::conversion().

                                             {
   return sys.representation();
 }

void Parma_Polyhedra_Library::Grid_Generator_System::set_index_first_pending_row ( dimension_type i )

inlineprivate

Sets the index of the first pending row to i.

Definition at line 42 of file Grid_Generator_System_inlines.hh.

References sys.

                                                                          {
   sys.set_index_first_pending_row(i);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::set_representation ( Representation r )

inline

Converts *this to the specified representation.

Definition at line 109 of file Grid_Generator_System_inlines.hh.

References sys.

                                                           {
   sys.set_representation(r);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::set_sorted ( bool b )

inlineprivate

Sets the sortedness flag of the system to b.

Definition at line 32 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::map_space_dimensions().

                                         {
   sys.set_sorted(b);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::set_space_dimension ( dimension_type space_dim )

private

Resizes the system to the specified space dimension.

Definition at line 229 of file Grid_Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_grid_generators(), Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), Parma_Polyhedra_Library::Grid::generalized_affine_image(), Parma_Polyhedra_Library::Grid::generalized_affine_preimage(), Parma_Polyhedra_Library::Grid::Grid(), and insert().

                                                         {
   sys.set_space_dimension(new_dimension);
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Grid_Generator_System::shift_space_dimensions	(	Variable	v,
		dimension_type	n
	)

private

Shift by n positions the coefficients of variables, starting from the coefficient of v. This increases the space dimension by n.

Definition at line 223 of file Grid_Generator_System.cc.

                                                      {
   sys.shift_space_dimensions(v, n);
 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::space_dimension ( ) const

inline

Returns the dimension of the vector space enclosing *this.

Definition at line 120 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_grid_generators(), Parma_Polyhedra_Library::Grid::add_space_dimensions(), clear(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), Grid_Generator_System(), insert(), Parma_Polyhedra_Library::Grid::normalize_divisors(), Parma_Polyhedra_Library::Grid::simplify(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), and Parma_Polyhedra_Library::Grid::upper_triangular().

                                              {
   return sys.space_dimension();
 }

Topology Parma_Polyhedra_Library::Grid_Generator_System::topology ( ) const

inlineprivate

Returns the system topology.

Definition at line 255 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by Parma_Polyhedra_Library::Grid::conversion().

                                       {
   return sys.topology();
 }

memory_size_type Parma_Polyhedra_Library::Grid_Generator_System::total_memory_in_bytes ( ) const

inline

Returns the total size in bytes of the memory occupied by *this.

Definition at line 149 of file Grid_Generator_System_inlines.hh.

References external_memory_in_bytes().

                                                    {
   return external_memory_in_bytes() + sizeof(*this);
 }

void Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows ( )

inlineprivate

Sets the index to indicate that the system has no pending rows.

Definition at line 37 of file Grid_Generator_System_inlines.hh.

References sys.

Referenced by insert(), and Parma_Polyhedra_Library::Grid::simplify().

                                           {
   sys.unset_pending_rows();
 }

const Grid_Generator_System & Parma_Polyhedra_Library::Grid_Generator_System::zero_dim_univ ( )

inlinestatic

Returns the singleton system containing only Grid_Generator::zero_dim_point().

Definition at line 125 of file Grid_Generator_System_inlines.hh.

References zero_dim_univ_p.

                                      {
   PPL_ASSERT(zero_dim_univ_p != 0);
   return *zero_dim_univ_p;
 }

Friends And Related Function Documentation

friend class Grid

friend

Definition at line 510 of file Grid_Generator_System_defs.hh.

std::ostream & operator<<	(	std::ostream &	s,
		const Grid_Generator_System &	gs
	)

Writes false if gs is empty. Otherwise, writes on s the generators of gs, all in one row and separated by ", ".

std::ostream & operator<<	(	std::ostream &	s,
		const Grid_Generator_System &	gs
	)

References begin(), and end().

                                                                {
   Grid_Generator_System::const_iterator i = gs.begin();
   const Grid_Generator_System::const_iterator gs_end = gs.end();
   if (i == gs_end) {
     return s << "false";
   }
   while (true) {
     s << *i;
     ++i;
     if (i == gs_end) {
       return s;
     }
     s << ", ";
   }
 }

bool operator==	(	const Grid_Generator_System &	x,
		const Grid_Generator_System &	y
	)

bool operator==	(	const Grid_Generator_System &	x,
		const Grid_Generator_System &	y
	)

References is_equal_to().

                                            {
   return x.is_equal_to(y);
 }

bool operator==	(	const Grid_Generator_System &	x,
		const Grid_Generator_System &	y
	)

friend

friend class Polyhedron

friend

Definition at line 509 of file Grid_Generator_System_defs.hh.

void swap	(	Grid_Generator_System &	x,
		Grid_Generator_System &	y
	)

Referenced by m_swap(), and operator=().

void swap	(	Grid_Generator_System &	x,
		Grid_Generator_System &	y
	)

References m_swap().

                                                          {
   x.m_swap(y);
 }

Member Data Documentation

const Representation Parma_Polyhedra_Library::Grid_Generator_System::default_representation = SPARSE

static

Definition at line 179 of file Grid_Generator_System_defs.hh.

Linear_System<Grid_Generator> Parma_Polyhedra_Library::Grid_Generator_System::sys

private

const PPL::Grid_Generator_System * Parma_Polyhedra_Library::Grid_Generator_System::zero_dim_univ_p = 0

staticprivate

Holds (between class initialization and finalization) a pointer to the singleton system containing only Grid_Generator::zero_dim_point().

Definition at line 494 of file Grid_Generator_System_defs.hh.

Referenced by zero_dim_univ().

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation