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 &g)
 Builds the singleton system containing only generator g.
 Grid_Generator_System (dimension_type dim)
 Builds an empty system of generators of dimension dim.
 Grid_Generator_System (const Grid_Generator_System &gs)
 Ordinary copy-constructor.
 ~Grid_Generator_System ()
 Destructor.
Grid_Generator_Systemoperator= (const Grid_Generator_System &y)
 Assignment operator.
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.
bool empty () const
 Returns true if and only if *this has no generators.
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.
dimension_type num_rows () const
 Returns the number of rows (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.
bool OK () const
 Checks if all the invariants are satisfied.
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(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
void swap (Grid_Generator_System &y)
 Swaps *this with y.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Grid_Generator_System can handle.
static void initialize ()
 Initializes the class.
static void finalize ()
 Finalizes the class.
static const
Grid_Generator_System
zero_dim_univ ()
 Returns the singleton system containing only Grid_Generator::zero_dim_point().

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.
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 affine_image (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
 Assigns to a given variable an affine expression.
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.
void resize_no_copy (dimension_type new_num_rows, dimension_type new_num_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.

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().

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 g  )  [inline, explicit]

Builds the singleton system containing only generator g.

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

References set_sorted().

00095   : Generator_System(g) {
00096   set_sorted(false);
00097 }

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_System gs  )  [inline]

Ordinary copy-constructor.

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

00083   : Generator_System(gs) {
00084 }

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

Destructor.

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

00100                                               {
00101 }


Member Function Documentation

Grid_Generator_System & Parma_Polyhedra_Library::Grid_Generator_System::operator= ( const Grid_Generator_System y  )  [inline]

Assignment operator.

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

References Parma_Polyhedra_Library::Generator_System::operator=().

00104                                                                {
00105   Generator_System::operator=(y);
00106   return *this;
00107 }

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 110 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().

00110                                            {
00111   // Grid generators use an extra column for the parameter divisor.
00112   return Generator_System::max_space_dimension() - 1;
00113 }

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 129 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().

00129                              {
00130   Generator_System::clear();
00131   // For grid generators, two extra columns are needed.
00132   add_zero_columns(2);
00133   set_sorted(false);
00134   unset_pending_rows();
00135 }

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 84 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(), 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::swap(), Parma_Polyhedra_Library::Matrix::swap_columns(), and Parma_Polyhedra_Library::Linear_System::topology().

Referenced by Parma_Polyhedra_Library::Grid::add_grid_generator(), Parma_Polyhedra_Library::Grid::add_recycled_grid_generators(), Parma_Polyhedra_Library::Grid::add_recycled_grid_generators_and_minimize(), Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project(), 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::Polyhedron::grid_generators(), Parma_Polyhedra_Library::Grid::map_space_dimensions(), Parma_Polyhedra_Library::Grid::select_wider_generators(), and Parma_Polyhedra_Library::Grid::set_zero_dim_univ().

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

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 60 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(), 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_grid_generators(), Parma_Polyhedra_Library::Grid::add_recycled_grid_generators_and_minimize(), Parma_Polyhedra_Library::Grid::generalized_affine_image(), Parma_Polyhedra_Library::Grid::generalized_affine_preimage(), Parma_Polyhedra_Library::Grid::time_elapse_assign(), Parma_Polyhedra_Library::Grid::unconstrain(), and Parma_Polyhedra_Library::Grid::upper_bound_assign().

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

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 34 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(), num_rows(), Parma_Polyhedra_Library::Linear_Row::RAY_OR_POINT_OR_INEQUALITY, set_index_first_pending_row(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

void Parma_Polyhedra_Library::Grid_Generator_System::initialize (  )  [static]

void Parma_Polyhedra_Library::Grid_Generator_System::finalize (  )  [static]

Finalizes the class.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 252 of file Grid_Generator_System.cc.

References zero_dim_univ_p.

00252                                    {
00253   assert(zero_dim_univ_p != 0);
00254   delete zero_dim_univ_p;
00255   zero_dim_univ_p = 0;
00256 }

const Grid_Generator_System & Parma_Polyhedra_Library::Grid_Generator_System::zero_dim_univ (  )  [inline, static]

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

References zero_dim_univ_p.

00123                                      {
00124   assert(zero_dim_univ_p != 0);
00125   return *zero_dim_univ_p;
00126 }

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

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

References empty.

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

00226                                    {
00227   return Generator_System::empty();
00228 }

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

References Parma_Polyhedra_Library::Generator_System::begin().

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

00237                                    {
00238   return static_cast<Grid_Generator_System::const_iterator>
00239     (Generator_System::begin());
00240 }

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

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

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

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

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

References operator==.

00069                                                                        {
00070   return operator==(static_cast<const Generator_System&>(*this),
00071                     static_cast<const Generator_System&>(y));
00072 }

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

References Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, 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().

00259                                    {
00260   if (topology() == NOT_NECESSARILY_CLOSED) {
00261 #ifndef NDEBUG
00262     std::cerr << "Grid_Generator_System is NOT_NECESSARILY_CLOSED"
00263               << std::endl;
00264 #endif
00265     return false;
00266   }
00267 
00268   if (is_sorted()) {
00269 #ifndef NDEBUG
00270     std::cerr << "Grid_Generator_System is marked as sorted."
00271               << std::endl;
00272 #endif
00273     return false;
00274   }
00275 
00276   // A Generator_System and hence a Grid_Generator_System must be a
00277   // valid Linear_System; do not check for strong normalization, since
00278   // this will be done when checking each individual generator.
00279   if (!Linear_System::OK(false))
00280     return false;
00281 
00282   // Checking each generator in the system.
00283   const Grid_Generator_System& x = *this;
00284   for (dimension_type i = num_rows(); i-- > 0; )
00285     if (!x[i].OK())
00286       return false;
00287 
00288   // All checks passed.
00289   return true;
00290 }

void Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 207 of file Grid_Generator_System.cc.

References num_columns(), and num_rows().

00207                                                         {
00208   const dimension_type num_rows = this->num_rows();
00209   s << num_rows << " x " << num_columns() << '\n';
00210   for (dimension_type i = 0; i < num_rows; ++i)
00211     operator[](i).ascii_dump(s);
00212 }

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(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.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

Definition at line 215 of file Grid_Generator_System.cc.

References num_columns(), num_rows(), OK(), resize_no_copy(), set_index_first_pending_row(), and set_sorted().

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

00215                                                   {
00216   dimension_type num_rows;
00217   dimension_type num_columns;
00218   if (!(s >> num_rows))
00219     return false;
00220   std::string str;
00221   if (!(s >> str))
00222     return false;
00223   if (!(s >> num_columns))
00224       return false;
00225   resize_no_copy(num_rows, num_columns);
00226 
00227   set_sorted(false);
00228   set_index_first_pending_row(num_rows);
00229 
00230   Grid_Generator_System& x = *this;
00231   for (dimension_type i = 0; i < num_rows; ++i)
00232     if (!x[i].ascii_load(s))
00233       return false;
00234 
00235   // Check invariants.
00236   assert(OK());
00237 
00238   return true;
00239 }

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

References Parma_Polyhedra_Library::total_memory_in_bytes().

00148                                                    {
00149   return Generator_System::total_memory_in_bytes();
00150 }

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

References Parma_Polyhedra_Library::external_memory_in_bytes().

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

00143                                                       {
00144   return Generator_System::external_memory_in_bytes();
00145 }

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

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]

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

Returns the k- th generator of the system.

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

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

Referenced by recycling_insert().

00254                                                         {
00255   return static_cast<Grid_Generator&>(Generator_System::operator[](k));
00256 }

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

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

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

00259                                                               {
00260   return static_cast<const Grid_Generator&>(Generator_System::operator[](k));
00261 }

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

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

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

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

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

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 310 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(), num_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().

00310                                                    {
00311   assert(num_columns() > 0);
00312   dimension_type col = num_columns() - 1;
00313   add_zero_rows_and_columns(dims, dims,
00314                             Linear_Row::Flags(NECESSARILY_CLOSED,
00315                                               Linear_Row::LINE_OR_EQUALITY));
00316   unset_pending_rows();
00317   // Swap the parameter divisor column into the new last column.
00318   swap_columns(col, col + dims);
00319   // Set the diagonal element of each added rows.
00320   dimension_type num_rows = this->num_rows();
00321   for (dimension_type row = num_rows - dims; row < num_rows; ++row, ++col)
00322     const_cast<Coefficient&>(operator[](row)[col]) = 1;
00323 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions ( const Variables_Set &  to_be_removed  )  [private]

Removes all the specified dimensions from the generator system.

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

Definition at line 327 of file Grid_Generator_System.cc.

References num_columns(), 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().

00327                                                             {
00328   // Dimension-compatibility assertion.
00329   assert(space_dimension() >= to_be_removed.space_dimension());
00330 
00331   // The removal of no dimensions from any system is a no-op.  This
00332   // case also captures the only legal removal of dimensions from a
00333   // 0-dim system.
00334   if (to_be_removed.empty())
00335     return;
00336 
00337   // For each variable to be removed, replace the corresponding column
00338   // by shifting left the columns to the right that will be kept.
00339   Variables_Set::const_iterator tbr = to_be_removed.begin();
00340   Variables_Set::const_iterator tbr_end = to_be_removed.end();
00341   dimension_type dst_col = *tbr+1;
00342   dimension_type src_col = dst_col + 1;
00343   for (++tbr; tbr != tbr_end; ++tbr) {
00344     const dimension_type tbr_col = *tbr+1;
00345     // Move all columns in between to the left.
00346     while (src_col < tbr_col)
00347       Matrix::swap_columns(dst_col++, src_col++);
00348     ++src_col;
00349   }
00350   // Move any remaining columns.
00351   const dimension_type num_columns = this->num_columns();
00352   while (src_col < num_columns)
00353     Matrix::swap_columns(dst_col++, src_col++);
00354 
00355   // The number of remaining columns is `dst_col'.
00356   Matrix::remove_trailing_columns(num_columns - dst_col);
00357 }

void Parma_Polyhedra_Library::Grid_Generator_System::remove_higher_space_dimensions ( dimension_type  new_dimension  )  [private]

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

The value of new_dimension must be at most the space dimension of *this.

Definition at line 361 of file Grid_Generator_System.cc.

References OK(), 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().

00361                                                                    {
00362   dimension_type space_dim = space_dimension();
00363 
00364   assert(new_dimension <= space_dim);
00365 
00366   // The removal of no dimensions from any system is a no-op.  Note
00367   // that this case also captures the only legal removal of dimensions
00368   // from a system in a 0-dim space.
00369   if (new_dimension == space_dim)
00370     return;
00371 
00372   // Swap the parameter divisor column into the column that will
00373   // become the last column.
00374   swap_columns(new_dimension + 1, space_dim + 1);
00375   Matrix::remove_trailing_columns(space_dim - new_dimension);
00376   assert(OK());
00377 }

void Parma_Polyhedra_Library::Grid_Generator_System::resize_no_copy ( dimension_type  new_num_rows,
dimension_type  new_num_columns 
) [inline, private]

Resizes the system without worrying about the old contents.

Parameters:
new_num_rows The number of rows of the resized system;
new_num_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 47 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().

00048                                                                             {
00049   Generator_System::resize_no_copy(new_num_rows, new_num_columns);
00050 }

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 58 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().

00058                                                                  {
00059   return Generator_System::erase_to_end(first_to_erase);
00060 }

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

References Parma_Polyhedra_Library::Linear_System::permute_columns().

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

00064                                                          {
00065   return Generator_System::permute_columns(cycles);
00066 }


Friends And Related Function Documentation

friend class Grid [friend]

Definition at line 385 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 265 of file Grid_Generator_System.inlines.hh.

Referenced by is_equal_to().

00266                                            {
00267   return x.is_equal_to(y);
00268 }

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

References begin(), and end().

00295                                                                {
00296   Grid_Generator_System::const_iterator i = gs.begin();
00297   const Grid_Generator_System::const_iterator gs_end = gs.end();
00298   if (i == gs_end)
00299     return s << "false";
00300   while (true) {
00301     s << *i++;
00302     if (i == gs_end)
00303       return s;
00304     s << ", ";
00305   }
00306 }

Specializes std::swap.

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

References swap().

00278                                                       {
00279   x.swap(y);
00280 }


Member Data Documentation

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

Reimplemented from Parma_Polyhedra_Library::Generator_System.

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

Referenced by finalize(), initialize(), and zero_dim_univ().


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

Generated on Sat Oct 11 10:41:09 2008 for PPL by  doxygen 1.5.6