#include <Grid_Generator_System.defs.hh>
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_Generator & | operator[] (dimension_type k) |
Returns the k- th generator of the system. | |
const Grid_Generator & | operator[] (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... |
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.
x
and y
are defined as follows: Variable x(0); Variable y(1);
Grid_Generator_System gs; gs.insert(grid_line(x + 0*y));
gs.insert(grid_point(0*x + 0*y));
gs.insert(grid_point(0*x));
gs.insert(grid_point(0*x + 1*y));
Grid_Generator_System gs; gs.insert(parameter(x + 0*y)); gs.insert(grid_point(0*x + 0*y));
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));
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));
Grid_Generator_System gs; gs.insert(grid_point(1*x + 1*y)); gs.insert(parameter(1*x - 1*y));
Definition at line 177 of file Grid_Generator_System.defs.hh.
Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System | ( | ) | [inline] |
Default constructor: builds an empty system of generators.
Definition at line 32 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, and set_sorted().
00033 : Generator_System(NECESSARILY_CLOSED) { 00034 adjust_topology_and_space_dimension(NECESSARILY_CLOSED, 1); 00035 set_sorted(false); 00036 }
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] |
Builds an empty system of generators of dimension dim
.
Definition at line 44 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, and set_sorted().
00045 : Generator_System(NECESSARILY_CLOSED) { 00046 adjust_topology_and_space_dimension(NECESSARILY_CLOSED, dim + 1); 00047 set_sorted(false); 00048 }
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 }
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] |
Returns the dimension of the vector space enclosing *this
.
Reimplemented from Parma_Polyhedra_Library::Generator_System.
Definition at line 63 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator_System::space_dimension().
Referenced by 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_embed(), Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project(), affine_image(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), Parma_Polyhedra_Library::Grid::generators(), Parma_Polyhedra_Library::Grid::Grid(), insert(), Parma_Polyhedra_Library::Grid::minimized_generators(), Parma_Polyhedra_Library::Grid::normalize_divisors(), Parma_Polyhedra_Library::Grid::OK(), remove_higher_space_dimensions(), remove_space_dimensions(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), Parma_Polyhedra_Library::Grid::update_congruences(), and Parma_Polyhedra_Library::Grid::upper_triangular().
00063 { 00064 assert(Generator_System::space_dimension() > 0); 00065 // Grid generators use an extra column for the parameter divisor. 00066 return Generator_System::space_dimension() - 1; 00067 }
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] |
Returns the past-the-end const_iterator.
Reimplemented from Parma_Polyhedra_Library::Generator_System.
Definition at line 173 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator_System::end().
Referenced by Parma_Polyhedra_Library::Grid::map_space_dimensions(), operator<<(), and Parma_Polyhedra_Library::Grid::relation_with().
00173 { 00174 return static_cast<Grid_Generator_System::const_iterator> 00175 (Generator_System::end()); 00176 }
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.
v | Index of the column to which the affine transformation is assigned; | |
expr | The numerator of the affine transformation: ![]() | |
denominator | The denominator of the affine transformation; |
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:
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] |
Returns the number of generators in the system.
Definition at line 94 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Grid::add_recycled_generators(), Parma_Polyhedra_Library::Grid::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Grid::bounds(), Parma_Polyhedra_Library::Grid::generators(), Parma_Polyhedra_Library::Grid::get_covering_box(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), Parma_Polyhedra_Library::Grid::is_bounded(), Parma_Polyhedra_Library::Grid::is_discrete(), Parma_Polyhedra_Library::Grid::is_topologically_closed(), Parma_Polyhedra_Library::Grid::map_space_dimensions(), Parma_Polyhedra_Library::Grid::minimized_generators(), Parma_Polyhedra_Library::Grid::normalize_divisors(), Parma_Polyhedra_Library::Grid::OK(), Parma_Polyhedra_Library::Grid::quick_equivalence_test(), Parma_Polyhedra_Library::Grid::reduce_parameter_with_line(), Parma_Polyhedra_Library::Grid::shrink_bounding_box(), Parma_Polyhedra_Library::Grid::simplify(), Parma_Polyhedra_Library::Grid::time_elapse_assign(), Parma_Polyhedra_Library::Grid::update_congruences(), and Parma_Polyhedra_Library::Grid::upper_triangular().
00094 { 00095 return Generator_System::num_rows(); 00096 }
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] |
Returns true
if and only if *this
contains one or more points.
Reimplemented from Parma_Polyhedra_Library::Generator_System.
Definition at line 185 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator_System::has_points().
Referenced by Parma_Polyhedra_Library::Grid::add_recycled_generators(), Parma_Polyhedra_Library::Grid::add_recycled_generators_and_minimize(), and Parma_Polyhedra_Library::Grid::OK().
00185 { 00186 return Generator_System::has_points(); 00187 }
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 |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Generator_System.
Referenced by Parma_Polyhedra_Library::Grid::ascii_dump(), Parma_Polyhedra_Library::Grid::conversion(), Parma_Polyhedra_Library::Grid::OK(), and Parma_Polyhedra_Library::Grid::simplify().
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.
dims | The number of rows and columns to be added: must be strictly positive. |
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.
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
.
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] |
Sets the sortedness flag of the system to b
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 205 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::set_sorted().
Referenced by ascii_load(), clear(), Parma_Polyhedra_Library::Grid::Grid(), Grid_Generator_System(), insert(), and Parma_Polyhedra_Library::Grid::map_space_dimensions().
00205 { 00206 Generator_System::set_sorted(b); 00207 }
void Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows | ( | ) | [inline, private] |
Sets the index to indicate that the system has no pending rows.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 210 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::unset_pending_rows().
Referenced by add_universe_rows_and_columns(), clear(), Parma_Polyhedra_Library::Grid::Grid(), and Parma_Polyhedra_Library::Grid::simplify().
00210 { 00211 Generator_System::unset_pending_rows(); 00212 }
void Parma_Polyhedra_Library::Grid_Generator_System::set_index_first_pending_row | ( | dimension_type | i | ) | [inline, private] |
Sets the index of the first pending row to i
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 215 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row().
Referenced by ascii_load(), Parma_Polyhedra_Library::Grid::conversion(), insert(), and recycling_insert().
00215 { 00216 Generator_System::set_index_first_pending_row(i); 00217 }
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.
new_n_rows | The number of rows of the resized system; | |
new_n_columns | The number of columns of the resized system. |
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] |
Returns the number of columns of the matrix (i.e., the size of the rows).
Reimplemented from Parma_Polyhedra_Library::Matrix.
Definition at line 226 of file Grid_Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::num_columns().
Referenced by add_universe_rows_and_columns(), affine_image(), ascii_load(), Parma_Polyhedra_Library::Grid::get_covering_box(), insert(), recycling_insert(), Parma_Polyhedra_Library::Grid::reduce_parameter_with_line(), remove_space_dimensions(), Parma_Polyhedra_Library::Grid::shrink_bounding_box(), and Parma_Polyhedra_Library::Grid::simplify().
00226 { 00227 return Generator_System::num_columns(); 00228 }
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 }
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().
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 }
void swap | ( | Parma_Polyhedra_Library::Grid_Generator_System & | x, | |
Parma_Polyhedra_Library::Grid_Generator_System & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 261 of file Grid_Generator_System.inlines.hh.
References swap().
00262 { 00263 x.swap(y); 00264 }