Parma_Polyhedra_Library::Grid_Generator_System Class Reference
[C++ Language Interface]

A system of grid generators. More...

#include <Grid_Generator_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Grid_Generator_System:

Inheritance graph
[legend]
Collaboration diagram for Parma_Polyhedra_Library::Grid_Generator_System:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Grid_Generator_System ()
 Default constructor: builds an empty system of generators.
 Grid_Generator_System (const Grid_Generator_System &gs)
 Ordinary copy-constructor.
 Grid_Generator_System (dimension_type dim)
 Builds an empty system of generators of dimension dim.
 Grid_Generator_System (const Grid_Generator &g)
 Builds the singleton system containing only generator g.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
void clear ()
 Removes all the generators from the generator system and sets its space dimension to 0.
void insert (const Grid_Generator &g)
 Inserts into *this a copy of the generator g, increasing the number of space dimensions if needed.
void recycling_insert (Grid_Generator &g)
 Inserts into *this the generator g, increasing the number of space dimensions if needed.
void recycling_insert (Grid_Generator_System &gs)
 Inserts into *this the generators in gs, increasing the number of space dimensions if needed.
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.
const_iterator end () const
 Returns the past-the-end const_iterator.
void swap (Grid_Generator_System &y)
 Swaps *this with y.
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
void affine_image (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
 Assigns to a given variable an affine expression.
dimension_type num_generators () const
 Returns the number of generators in the system.
dimension_type num_parameters () const
 Returns the number of parameters in the system.
dimension_type num_lines () const
 Returns the number of lines in the system.
bool has_points () const
 Returns true if and only if *this contains one or more points.
bool is_equal_to (const Grid_Generator_System y) const
 Returns true if *this is identical to y.
Grid_Generatoroperator[] (dimension_type k)
 Returns the k- th generator of the system.
const Grid_Generatoroperator[] (dimension_type k) const
 Returns a constant reference to the k- th generator of the system.
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
void print () const
 Prints *this to std::cerr using operator<<.
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump) and sets *this accordingly. Returns true if successful, false otherwise.
bool OK () const
 Checks if all the invariants are satisfied.
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.
void remove_space_dimensions (const Variables_Set &to_be_removed)
 Removes all the specified dimensions from the generator system.
void remove_higher_space_dimensions (dimension_type new_dimension)
 Removes the higher dimensions of the system so that the resulting system will have dimension new_dimension.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Grid_Generator_System can handle.

Private Member Functions

void set_sorted (bool b)
 Sets the sortedness flag of the system to b.
void unset_pending_rows ()
 Sets the index to indicate that the system has no pending rows.
void set_index_first_pending_row (dimension_type i)
 Sets the index of the first pending row to i.
void resize_no_copy (dimension_type new_n_rows, dimension_type new_n_columns)
 Resizes the system without worrying about the old contents.
dimension_type num_columns () const
 Returns the number of columns of the matrix (i.e., the size of the rows).
void erase_to_end (dimension_type first_to_erase)
 Erases from the matrix all the rows but those having an index less than first_to_erase.
void permute_columns (const std::vector< dimension_type > &cycles)
 Permutes the columns of the matrix.

Friends

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

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &s, const Grid_Generator_System &gs)
 Output operator.
void swap (Parma_Polyhedra_Library::Grid_Generator_System &x, Parma_Polyhedra_Library::Grid_Generator_System &y)
 Specializes std::swap.

Classes

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


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 $x$ 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 $x$ 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 $x$ 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 $x$ 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 $x + y = 2$ 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 177 of file Grid_Generator_System.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System (  )  [inline]

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System ( const Grid_Generator_System gs  )  [inline]

Ordinary copy-constructor.

Definition at line 39 of file Grid_Generator_System.inlines.hh.

00040   : Generator_System(gs) {
00041 }

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System ( dimension_type  dim  )  [inline, explicit]

Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System ( const Grid_Generator g  )  [inline, explicit]

Builds the singleton system containing only generator g.

Definition at line 51 of file Grid_Generator_System.inlines.hh.

References set_sorted().

00052   : Generator_System(g) {
00053   set_sorted(false);
00054 }


Member Function Documentation

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::max_space_dimension (  )  [inline, static]

Returns the maximum space dimension a Grid_Generator_System can handle.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 57 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::max_space_dimension().

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

00057                                            {
00058   // Grid generators use an extra column for the parameter divisor.
00059   return Generator_System::max_space_dimension() - 1;
00060 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::space_dimension (  )  const [inline]

void Parma_Polyhedra_Library::Grid_Generator_System::clear (  )  [inline]

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 70 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Generator_System::clear(), set_sorted(), and unset_pending_rows().

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

00070                              {
00071   Generator_System::clear();
00072   // For grid generators, two extra columns are needed.
00073   add_zero_columns(2);
00074   set_sorted(false);
00075   unset_pending_rows();
00076 }

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 85 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Matrix::add_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Grid_Generator::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Grid_Generator::is_parameter(), num_columns(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Matrix::row_capacity, set_index_first_pending_row(), set_sorted(), Parma_Polyhedra_Library::Grid_Generator::size(), space_dimension(), Parma_Polyhedra_Library::Grid_Generator::space_dimension(), Parma_Polyhedra_Library::Matrix::swap_columns(), and Parma_Polyhedra_Library::Linear_System::topology().

Referenced by Parma_Polyhedra_Library::Grid::add_generator(), Parma_Polyhedra_Library::Grid::add_recycled_generators(), Parma_Polyhedra_Library::Grid::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project(), 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(), and Parma_Polyhedra_Library::Grid::set_zero_dim_univ().

00085                                                         {
00086   dimension_type g_space_dim = g.space_dimension();
00087 
00088   if (g.is_parameter())
00089     if (g.all_homogeneous_terms_are_zero()) {
00090       dimension_type initial_space_dim = space_dimension();
00091       if (initial_space_dim < g_space_dim) {
00092         // Adjust the space dimension.
00093         add_zero_columns(g_space_dim - initial_space_dim);
00094         // Swap the parameter divisor column into the new last column.
00095         swap_columns(g_space_dim + 1, initial_space_dim + 1);
00096         assert(OK());
00097       }
00098       return;
00099     }
00100 
00101   {
00102     // This block is a substitute for Generator_System::insert, in
00103     // which the single call to Linear_System::insert has been
00104     // inlined.
00105 
00106     // We are sure that the matrix has no pending rows
00107     // and that the new row is not a pending generator.
00108     assert(num_pending_rows() == 0);
00109 
00110     // TODO: Consider whether, if possible, it would be better to wrap
00111     //       an NNC Generator, storing the generator divisor in the
00112     //       epsilon column.
00113 
00114     // This is a modified copy of Linear_System::insert.  It is here
00115     // to force Grid_Generator::OK to be used (to work around the
00116     // normalization assertions in Linear_System::OK) and so that the
00117     // parameter divisor column can be moved during the insert.
00118 
00119     // The added row must be strongly normalized and have the same
00120     // topology as the system.
00121     assert(topology() == g.topology());
00122     // This method is only used when the system has no pending rows.
00123     assert(num_pending_rows() == 0);
00124 
00125     const dimension_type old_num_rows = num_rows();
00126     const dimension_type old_num_columns = num_columns();
00127     const dimension_type g_size = g.size();
00128 
00129     // Resize the system, if necessary.
00130     assert(is_necessarily_closed());
00131     if (g_size > old_num_columns) {
00132       add_zero_columns(g_size - old_num_columns);
00133       if (old_num_rows > 0)
00134         // Swap the existing parameter divisor column into the new
00135         // last column.
00136         swap_columns(old_num_columns - 1, g_size - 1);
00137       Matrix::add_row(g);
00138     }
00139     else if (g_size < old_num_columns)
00140       if (old_num_rows == 0)
00141         Matrix::add_row(Linear_Row(g, old_num_columns, row_capacity));
00142       else {
00143         // Create a resized copy of the row (and move the parameter
00144         // divisor coefficient to its last position).
00145         Linear_Row tmp_row(g, old_num_columns, row_capacity);
00146         std::swap(tmp_row[g_size - 1], tmp_row[old_num_columns - 1]);
00147         Matrix::add_row(tmp_row);
00148       }
00149     else
00150       // Here r_size == old_num_columns.
00151       Matrix::add_row(g);
00152 
00153   } // Generator_System::insert(g) substitute.
00154 
00155   set_index_first_pending_row(num_rows());
00156   set_sorted(false);
00157 
00158   assert(OK());
00159 }

void Parma_Polyhedra_Library::Grid_Generator_System::recycling_insert ( Grid_Generator g  ) 

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

Definition at line 61 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Grid_Generator::coefficient_swap(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), operator[](), Parma_Polyhedra_Library::Linear_Row::RAY_OR_POINT_OR_INEQUALITY, set_index_first_pending_row(), Parma_Polyhedra_Library::Grid_Generator::size(), and Parma_Polyhedra_Library::Matrix::swap_columns().

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_generators(), Parma_Polyhedra_Library::Grid::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Grid::generalized_affine_image(), Parma_Polyhedra_Library::Grid::generalized_affine_preimage(), Parma_Polyhedra_Library::Grid::join_assign(), and Parma_Polyhedra_Library::Grid::time_elapse_assign().

00061                                                             {
00062   dimension_type old_num_rows = num_rows();
00063   const dimension_type old_num_cols = num_columns();
00064   const dimension_type g_num_cols = g.size();
00065   if (old_num_cols >= g_num_cols)
00066     add_zero_rows(1,
00067                   Linear_Row::Flags(NECESSARILY_CLOSED,
00068                                     Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00069   else {
00070     add_zero_rows_and_columns(1,
00071                               g_num_cols - old_num_cols,
00072                               Linear_Row::Flags(NECESSARILY_CLOSED,
00073                                                 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00074     // Swap the parameter divisor column into the new last column.
00075     swap_columns(old_num_cols - 1, num_columns() - 1);
00076   }
00077   set_index_first_pending_row(old_num_rows + 1);
00078   // Swap one coefficient at a time into the newly added rows, instead
00079   // of swapping each entire row.  This ensures that the added rows
00080   // have the same capacities as the existing rows.
00081   operator[](old_num_rows).coefficient_swap(g);
00082 }

void Parma_Polyhedra_Library::Grid_Generator_System::recycling_insert ( Grid_Generator_System gs  ) 

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

Definition at line 35 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Linear_Row::RAY_OR_POINT_OR_INEQUALITY, set_index_first_pending_row(), and Parma_Polyhedra_Library::Matrix::swap_columns().

00035                                                                     {
00036   const dimension_type old_num_rows = num_rows();
00037   const dimension_type gs_num_rows = gs.num_rows();
00038   const dimension_type old_num_cols = num_columns();
00039   const dimension_type gs_num_cols = gs.num_columns();
00040   if (old_num_cols >= gs_num_cols)
00041     add_zero_rows(gs_num_rows,
00042                   Linear_Row::Flags(NECESSARILY_CLOSED,
00043                                     Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00044   else {
00045     add_zero_rows_and_columns(gs_num_rows,
00046                               gs_num_cols - old_num_cols,
00047                               Linear_Row::Flags(NECESSARILY_CLOSED,
00048                                                 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00049     // Swap the parameter divisor column into the new last column.
00050     swap_columns(old_num_cols - 1, num_columns() - 1);
00051   }
00052   set_index_first_pending_row(old_num_rows + gs_num_rows);
00053   // Swap one coefficient at a time into the newly added rows, instead
00054   // of swapping each entire row.  This ensures that the added rows
00055   // have the same capacities as the existing rows.
00056   for (dimension_type i = gs_num_rows; i-- > 0; )
00057     operator[](old_num_rows + i).coefficient_swap(gs[i]);
00058 }

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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 167 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::begin().

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

00167                                    {
00168   return static_cast<Grid_Generator_System::const_iterator>
00169     (Generator_System::begin());
00170 }

Grid_Generator_System::const_iterator Parma_Polyhedra_Library::Grid_Generator_System::end (  )  const [inline]

void Parma_Polyhedra_Library::Grid_Generator_System::swap ( Grid_Generator_System y  )  [inline]

Swaps *this with y.

Definition at line 79 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::swap().

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

00079                                                     {
00080   Generator_System::swap(y);
00081 }

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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 84 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().

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

00084                                                       {
00085   return Generator_System::external_memory_in_bytes();
00086 }

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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 89 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().

00089                                                    {
00090   return Generator_System::total_memory_in_bytes();
00091 }

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

Assigns to a given variable an affine expression.

Parameters:
v Index of the column 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 each element of v -th 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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 163 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Scalar_Products::assign(), num_columns(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), and TEMP_INTEGER.

Referenced by Parma_Polyhedra_Library::Grid::affine_image(), and Parma_Polyhedra_Library::Grid::affine_preimage().

00165                                                               {
00166   // This is mostly a copy of Generator_System::affine_image.
00167 
00168   Grid_Generator_System& x = *this;
00169   // `v' is the index of a column corresponding to a "user" variable
00170   // (i.e., it cannot be the inhomogeneous term).
00171   assert(v > 0 && v <= x.space_dimension());
00172   assert(expr.space_dimension() <= x.space_dimension());
00173   assert(denominator > 0);
00174 
00175   const dimension_type n_columns = x.num_columns();
00176   const dimension_type n_rows = x.num_rows();
00177 
00178   // Compute the numerator of the affine transformation and assign it
00179   // to the column of `*this' indexed by `v'.
00180   TEMP_INTEGER(numerator);
00181   for (dimension_type i = n_rows; i-- > 0; ) {
00182     Grid_Generator& row = x[i];
00183     Scalar_Products::assign(numerator, expr, row);
00184     std::swap(numerator, row[v]);
00185   }
00186 
00187   if (denominator != 1)
00188     // Since we want integer elements in the matrix,
00189     // we multiply by `denominator' all the columns of `*this'
00190     // having an index different from `v'.
00191     for (dimension_type i = n_rows; i-- > 0; ) {
00192       Grid_Generator& row = x[i];
00193       for (dimension_type j = n_columns; j-- > 0; )
00194         if (j != v)
00195           row[j] *= denominator;
00196     }
00197 
00198   // If the mapping is not invertible we may have transformed valid
00199   // lines and rays into the origin of the space.
00200   const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0);
00201   if (not_invertible)
00202     x.remove_invalid_lines_and_rays();
00203 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_generators (  )  const [inline]

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_parameters (  )  const [inline]

Returns the number of parameters in the system.

Definition at line 99 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::num_rays().

Referenced by Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate().

00099                                             {
00100   return Generator_System::num_rays();
00101 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_lines (  )  const [inline]

Returns the number of lines in the system.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 104 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::num_lines().

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

00104                                        {
00105   return Generator_System::num_lines();
00106 }

bool Parma_Polyhedra_Library::Grid_Generator_System::has_points (  )  const [inline]

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 242 of file Grid_Generator_System.inlines.hh.

References operator==.

00242                                                                       {
00243   return operator==(static_cast<const Generator_System&>(*this),
00244                     static_cast<const Generator_System&>(y));
00245 }

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

Returns the k- th generator of the system.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 190 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::operator[]().

Referenced by recycling_insert().

00190                                                         {
00191   return static_cast<Grid_Generator&>(Generator_System::operator[](k));
00192 }

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

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 195 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::operator[]().

00195                                                               {
00196   return static_cast<const Grid_Generator&>(Generator_System::operator[](k));
00197 }

void Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump (  )  const

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 200 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Generator_System::ascii_dump().

00200                                                      {
00201   return Generator_System::ascii_dump(s);
00202 }

void Parma_Polyhedra_Library::Grid_Generator_System::print (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

Loads from s an ASCII representation (as produced by ascii_dump) 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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 208 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Grid_Generator::LINE, num_columns(), OK(), Parma_Polyhedra_Library::Grid_Generator::PARAMETER, Parma_Polyhedra_Library::Grid_Generator::POINT, resize_no_copy(), set_index_first_pending_row(), Parma_Polyhedra_Library::Linear_System::set_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), and set_sorted().

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

00208                                                   {
00209   // This is a copy of Generator_System::ascii_load, to force
00210   // Grid_Generator_System::OK to be called, in order to work around
00211   // the assertions in Linear_System::OK.
00212 
00213   // FIXME: Gridify this.  Add an ascii_dump to match.
00214 
00215   std::string str;
00216   if (!(s >> str) || str != "topology")
00217     return false;
00218   if (!(s >> str))
00219     return false;
00220   if (str == "NECESSARILY_CLOSED")
00221     set_necessarily_closed();
00222   else {
00223     if (str != "NOT_NECESSARILY_CLOSED")
00224       return false;
00225     set_not_necessarily_closed();
00226   }
00227 
00228   dimension_type nrows;
00229   dimension_type ncols;
00230   if (!(s >> nrows))
00231     return false;
00232   if (!(s >> str))
00233     return false;
00234   if (!(s >> ncols))
00235       return false;
00236   resize_no_copy(nrows, ncols);
00237 
00238   if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00239     return false;
00240   set_sorted(str == "(sorted)");
00241   dimension_type index;
00242   if (!(s >> str) || str != "index_first_pending")
00243     return false;
00244   if (!(s >> index))
00245     return false;
00246   set_index_first_pending_row(index);
00247 
00248   Grid_Generator_System& x = *this;
00249   for (dimension_type i = 0; i < x.num_rows(); ++i) {
00250     for (dimension_type j = 0; j < x.num_columns(); ++j)
00251       if (!(s >> const_cast<Coefficient&>(x[i][j])))
00252         return false;
00253 
00254     if (!(s >> str))
00255       return false;
00256     if (str == "L")
00257       x[i].set_is_line();
00258     else
00259       x[i].set_is_ray_or_point();
00260 
00261     // Checking for equality of actual and declared types.
00262     switch (x[i].type()) {
00263     case Grid_Generator::LINE:
00264       if (str == "L")
00265         continue;
00266       break;
00267     case Grid_Generator::PARAMETER:
00268       if (str == "R")
00269         continue;
00270       break;
00271     case Grid_Generator::POINT:
00272       if (str == "P")
00273         continue;
00274       break;
00275     }
00276     // Reaching this point means that the input was illegal.
00277     return false;
00278   }
00279 
00280   // Checking for well-formedness.
00281 
00282   assert(OK());
00283   return true;
00284 }

bool Parma_Polyhedra_Library::Grid_Generator_System::OK (  )  const

Checks if all the invariants are satisfied.

Returns true if and only if *this is a valid Linear_System and each row in the system is a valid Grid_Generator.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 287 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), and Parma_Polyhedra_Library::Linear_System::topology().

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

00287                                    {
00288   if (topology() == NOT_NECESSARILY_CLOSED) {
00289 #ifndef NDEBUG
00290     std::cerr << "Grid_Generator_System is NOT_NECESSARILY_CLOSED"
00291               << std::endl;
00292 #endif
00293     return false;
00294   }
00295 
00296   if (is_sorted()) {
00297 #ifndef NDEBUG
00298     std::cerr << "Grid_Generator_System is marked as sorted."
00299               << std::endl;
00300 #endif
00301     return false;
00302   }
00303 
00304   // A Generator_System and hence a Grid_Generator_System must be a
00305   // valid Linear_System; do not check for strong normalization, since
00306   // this will be done when checking each individual generator.
00307   if (!Linear_System::OK(false))
00308     return false;
00309 
00310   // Checking each generator in the system.
00311   const Grid_Generator_System& x = *this;
00312   for (dimension_type i = num_rows(); i-- > 0; )
00313     if (!x[i].OK())
00314       return false;
00315 
00316   // All checks passed.
00317   return true;
00318 }

void Parma_Polyhedra_Library::Grid_Generator_System::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.

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({A \atop 0}{0 \atop B}\bigr)$ where $B$ is the $dims \times dims$ unit matrix of the form $\bigl({1 \atop 0}{0 \atop 1}\bigr)$. The matrix is expanded avoiding reallocation whenever possible.

Definition at line 338 of file Grid_Generator_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Linear_Row::LINE_OR_EQUALITY, Parma_Polyhedra_Library::NECESSARILY_CLOSED, num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::rows, Parma_Polyhedra_Library::Matrix::swap_columns(), and unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions(), and Parma_Polyhedra_Library::Grid::add_space_dimensions_and_embed().

00338                                                    {
00339   assert(num_columns() > 0);
00340   dimension_type col = num_columns() - 1;
00341   add_zero_rows_and_columns(dims, dims,
00342                             Linear_Row::Flags(NECESSARILY_CLOSED,
00343                                               Linear_Row::LINE_OR_EQUALITY));
00344   unset_pending_rows();
00345   // Swap the parameter divisor column into the new last column.
00346   swap_columns(col, col + dims);
00347   // Set the diagonal element of each added rows.
00348   dimension_type rows = num_rows();
00349   for (dimension_type row = rows - dims; row < rows; ++row, ++col)
00350     const_cast<Coefficient&>(operator[](row)[col]) = 1;
00351 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions ( const Variables_Set to_be_removed  ) 

Removes all the specified dimensions from the generator system.

Exceptions:
std::invalid_argument Thrown if the highest space dimension of the variables in to_be_removed is higher than the space dimension of *this.

Definition at line 355 of file Grid_Generator_System.cc.

References num_columns(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Matrix::remove_trailing_columns(), space_dimension(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00355                                                             {
00356   // The removal of no dimensions from any system is a no-op.  This
00357   // case also captures the only legal removal of dimensions from a
00358   // 0-dim system.
00359   if (to_be_removed.empty())
00360     return;
00361 
00362   // Dimension-compatibility check: the variable having maximum space
00363   // dimension is the one occurring last in the set.
00364   const dimension_type
00365     min_space_dim = to_be_removed.rbegin()->space_dimension();
00366   if (space_dimension() < min_space_dim) {
00367     std::ostringstream s;
00368     s << "PPL::Grid_Generator_System::remove_space_dimensions(vs):\n"
00369       << "this->space_dimension() == " << space_dimension()
00370       << ", required space dimension == " << min_space_dim << ".";
00371     throw std::invalid_argument(s.str());
00372   }
00373 
00374   // For each variable to be removed, replace the corresponding column
00375   // by shifting left the columns to the right that will be kept.
00376   Variables_Set::const_iterator tbr = to_be_removed.begin();
00377   Variables_Set::const_iterator tbr_end = to_be_removed.end();
00378   dimension_type dst_col = tbr->space_dimension();
00379   dimension_type src_col = dst_col + 1;
00380   for (++tbr; tbr != tbr_end; ++tbr) {
00381     dimension_type tbr_col = tbr->space_dimension();
00382     // Move all columns in between to the left.
00383     while (src_col < tbr_col)
00384       // FIXME: consider whether Linear_System must have a swap_columns()
00385       // method.  If the answer is "no", remove this Matrix:: qualification.
00386       Matrix::swap_columns(dst_col++, src_col++);
00387     ++src_col;
00388   }
00389   // Move any remaining columns.
00390   const dimension_type num_cols = num_columns();
00391   while (src_col < num_cols)
00392     // FIXME: consider whether Linear_System must have a swap_columns()
00393     // method.  If the answer is "no", remove this Matrix:: qualification.
00394     Matrix::swap_columns(dst_col++, src_col++);
00395 
00396   // The number of remaining columns is `dst_col'.
00397   Matrix::remove_trailing_columns(num_cols - dst_col);
00398 
00399 
00400 
00401   remove_invalid_lines_and_rays();
00402 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_higher_space_dimensions ( dimension_type  new_dimension  ) 

Removes the higher dimensions of the system so that the resulting system will have dimension new_dimension.

Exceptions:
std::invalid_argument Thrown if the new_dimension is higher than the space dimension of *this.

Definition at line 406 of file Grid_Generator_System.cc.

References OK(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Matrix::remove_trailing_columns(), space_dimension(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00406                                                              {
00407   dimension_type space_dim = space_dimension();
00408   // Dimension-compatibility check.
00409   if (new_dimension > space_dim) {
00410     std::ostringstream s;
00411     s << "PPL::Grid_Generator_System::remove_higher_space_dimensions(n):\n"
00412       << "this->space_dimension() == " << space_dim
00413       << ", required space dimension == " << new_dimension << ".";
00414     throw std::invalid_argument(s.str());
00415   }
00416 
00417   // The removal of no dimensions from any system is a no-op.  Note
00418   // that this case also captures the only legal removal of dimensions
00419   // from a system in a 0-dim space.
00420   if (new_dimension == space_dim)
00421     return;
00422 
00423   // Swap the parameter divisor column into the column that will
00424   // become the last column.
00425   swap_columns(new_dimension + 1, space_dim + 1);
00426   Matrix::remove_trailing_columns(space_dim - new_dimension);
00427   remove_invalid_lines_and_rays();
00428   assert(OK());
00429 }

void Parma_Polyhedra_Library::Grid_Generator_System::set_sorted ( bool  b  )  [inline, private]

void Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows (  )  [inline, private]

void Parma_Polyhedra_Library::Grid_Generator_System::set_index_first_pending_row ( dimension_type  i  )  [inline, private]

void Parma_Polyhedra_Library::Grid_Generator_System::resize_no_copy ( dimension_type  new_n_rows,
dimension_type  new_n_columns 
) [inline, private]

Resizes the system without worrying about the old contents.

Parameters:
new_n_rows The number of rows of the resized system;
new_n_columns The number of columns of the resized system.
The system is expanded to the specified dimensions avoiding reallocation whenever possible. The contents of the original system is lost.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 220 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::resize_no_copy().

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

00221                                                                           {
00222   Generator_System::resize_no_copy(new_n_rows, new_n_columns);
00223 }

dimension_type Parma_Polyhedra_Library::Grid_Generator_System::num_columns (  )  const [inline, private]

void Parma_Polyhedra_Library::Grid_Generator_System::erase_to_end ( dimension_type  first_to_erase  )  [inline, private]

Erases from the matrix all the rows but those having an index less than first_to_erase.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 231 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::erase_to_end().

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

00231                                                                  {
00232   return Generator_System::erase_to_end(first_to_erase);
00233 }

void Parma_Polyhedra_Library::Grid_Generator_System::permute_columns ( const std::vector< dimension_type > &  cycles  )  [inline, private]

Permutes the columns of the matrix.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 237 of file Grid_Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::permute_columns().

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

00237                                                          {
00238   return Generator_System::permute_columns(cycles);
00239 }


Friends And Related Function Documentation

friend class Grid [friend]

Definition at line 438 of file Grid_Generator_System.defs.hh.

bool operator== ( const Grid_Generator_System x,
const Grid_Generator_System y 
) [friend]

Returns true if and only if x and y are identical.

Definition at line 249 of file Grid_Generator_System.inlines.hh.

Referenced by is_equal_to().

00250                                            {
00251   return x.is_equal_to(y);
00252 }

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

Output operator.

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

Definition at line 322 of file Grid_Generator_System.cc.

References begin(), and end().

00323                                                                {
00324   Grid_Generator_System::const_iterator i = gs.begin();
00325   const Grid_Generator_System::const_iterator gs_end = gs.end();
00326   if (i == gs_end)
00327     return s << "false";
00328   while (true) {
00329     s << *i++;
00330     if (i == gs_end)
00331       return s;
00332     s << ", ";
00333   }
00334 }

Specializes std::swap.

Definition at line 261 of file Grid_Generator_System.inlines.hh.

References swap().

00262                                                       {
00263   x.swap(y);
00264 }


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

Generated on Wed Jul 16 22:55:48 2008 for PPL by  doxygen 1.5.6