#include <Generator_System.defs.hh>
Public Member Functions | |
Generator_System () | |
Default constructor: builds an empty system of generators. | |
Generator_System (const Generator &g) | |
Builds the singleton system containing only generator g . | |
Generator_System (const Generator_System &gs) | |
Ordinary copy-constructor. | |
~Generator_System () | |
Destructor. | |
Generator_System & | operator= (const 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 Generator &g) |
Inserts in *this a copy of the generator g , 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. | |
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) 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 (Generator_System &y) |
Swaps *this with y . | |
Static Public Member Functions | |
static dimension_type | max_space_dimension () |
Returns the maximum space dimension a Generator_System can handle. | |
static const Generator_System & | zero_dim_univ () |
Returns the singleton system containing only Generator::zero_dim_point(). | |
Private Member Functions | |
Generator_System (Topology topol) | |
Builds an empty system of generators having the specified topology. | |
Generator_System (Topology topol, dimension_type n_rows, dimension_type n_columns) | |
Builds a system of n_rows rays/points on a n_columns - 1 dimensional space (including the ![]() topol is NOT_NECESSARILY_CLOSED ). | |
bool | adjust_topology_and_space_dimension (Topology topol, dimension_type num_dimensions) |
Adjusts *this so that it matches the topology and the number of space dimensions given as parameters (adding or removing columns if needed). Returns false if and only if topol is equal to NECESSARILY_CLOSED and *this contains closure points. | |
void | add_corresponding_points () |
For each unmatched closure point in *this , adds the corresponding point. | |
bool | has_points () const |
Returns true if and only if *this contains one or more points. | |
void | add_corresponding_closure_points () |
For each unmatched point in *this , adds the corresponding closure point. | |
bool | has_closure_points () const |
Returns true if and only if *this contains one or more closure points. | |
Generator & | operator[] (dimension_type k) |
Returns the k- th generator of the system. | |
const Generator & | operator[] (dimension_type k) const |
Returns a constant reference to the k- th generator of the system. | |
Parma_Polyhedra_Library::Poly_Con_Relation | relation_with (const Constraint &c) const |
Returns the relations holding between the generator system and the constraint c . | |
bool | satisfied_by_all_generators (const Constraint &c) const |
Returns true if all the generators satisfy c . | |
bool | satisfied_by_all_generators_C (const Constraint &c) const |
Returns true if all the generators satisfy c . | |
bool | satisfied_by_all_generators_NNC (const Constraint &c) const |
Returns true if all the generators satisfy c . | |
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_lines () const |
Returns the number of lines of the system. | |
dimension_type | num_rays () const |
Returns the number of rays of the system. | |
void | remove_invalid_lines_and_rays () |
Removes all the invalid lines and rays. | |
void | simplify () |
Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of generators. | |
void | insert_pending (const Generator &g) |
Inserts in *this a copy of the generator g , increasing the number of space dimensions if needed. It is a pending generator. | |
Friends | |
class | const_iterator |
class | Parma_Polyhedra_Library::Polyhedron |
class | Parma_Polyhedra_Library::Grid_Generator_System |
bool | operator== (const Polyhedron &x, const Polyhedron &y) |
Related Functions | |
(Note that these are not member functions.) | |
std::ostream & | operator<< (std::ostream &s, const Generator_System &gs) |
Output operator. | |
void | swap (Parma_Polyhedra_Library::Generator_System &x, Parma_Polyhedra_Library::Generator_System &y) |
Specializes std::swap . | |
Classes | |
class | const_iterator |
An iterator over a system of generators. More... |
An object of the class Generator_System is a system of generators, i.e., a multiset of objects of the class Generator (lines, rays, points and closure 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 generators which is meant to define a non-empty polyhedron must include at least one point: the reason is that lines, rays and closure points need a supporting point (lines and rays only specify directions while closure points only specify points in the topological closure of the NNC polyhedron).
x
and y
are defined as follows: Variable x(0); Variable y(1);
Generator_System gs; gs.insert(line(x + 0*y));
gs.insert(point(0*x + 0*y));
gs.insert(point(0*x));
gs.insert(point(0*x + 1*y));
Generator_System gs; gs.insert(ray(x + 0*y));
one just has to add the origin:
gs.insert(point(0*x + 0*y));
Generator_System gs; gs.insert(point(0*x + 0*y)); gs.insert(point(0*x + 3*y)); gs.insert(point(3*x + 0*y)); gs.insert(point(3*x + 3*y));
Generator_System gs; gs.insert(point(x + y)); gs.insert(closure_point(0*x + 0*y)); gs.insert(closure_point(0*x + 3*y)); gs.insert(closure_point(3*x + 0*y)); gs.insert(closure_point(3*x + 3*y));
Generator_System gs; gs.insert(point(0*x + 0*y)); gs.insert(point(0*x + 1*y)); gs.insert(ray(x - y));
Definition at line 183 of file Generator_System.defs.hh.
Parma_Polyhedra_Library::Generator_System::Generator_System | ( | ) | [inline] |
Default constructor: builds an empty system of generators.
Definition at line 31 of file Generator_System.inlines.hh.
00032 : Linear_System(NECESSARILY_CLOSED) { 00033 }
Parma_Polyhedra_Library::Generator_System::Generator_System | ( | const Generator & | g | ) | [inline, explicit] |
Builds the singleton system containing only generator g
.
Definition at line 36 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::insert().
00037 : Linear_System(g.topology()) { 00038 Linear_System::insert(g); 00039 }
Parma_Polyhedra_Library::Generator_System::Generator_System | ( | const Generator_System & | gs | ) | [inline] |
Ordinary copy-constructor.
Definition at line 42 of file Generator_System.inlines.hh.
00043 : Linear_System(gs) { 00044 }
Parma_Polyhedra_Library::Generator_System::~Generator_System | ( | ) | [inline] |
Parma_Polyhedra_Library::Generator_System::Generator_System | ( | Topology | topol | ) | [inline, explicit, private] |
Builds an empty system of generators having the specified topology.
Definition at line 47 of file Generator_System.inlines.hh.
00048 : Linear_System(topol) { 00049 }
Parma_Polyhedra_Library::Generator_System::Generator_System | ( | Topology | topol, | |
dimension_type | n_rows, | |||
dimension_type | n_columns | |||
) | [inline, private] |
Builds a system of n_rows
rays/points on a n_columns
- 1 dimensional space (including the dimension, if
topol
is NOT_NECESSARILY_CLOSED
).
Definition at line 52 of file Generator_System.inlines.hh.
00055 : Linear_System(topol, n_rows, n_columns) { 00056 }
Generator_System & Parma_Polyhedra_Library::Generator_System::operator= | ( | const Generator_System & | y | ) | [inline] |
Assignment operator.
Definition at line 63 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator=().
00063 { 00064 Linear_System::operator=(y); 00065 return *this; 00066 }
dimension_type Parma_Polyhedra_Library::Generator_System::max_space_dimension | ( | ) | [inline, static] |
Returns the maximum space dimension a Generator_System can handle.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 69 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::max_space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::max_space_dimension(), and Parma_Polyhedra_Library::Grid_Generator_System::max_space_dimension().
00069 { 00070 return Linear_System::max_space_dimension(); 00071 }
dimension_type Parma_Polyhedra_Library::Generator_System::space_dimension | ( | ) | const [inline] |
Returns the dimension of the vector space enclosing *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 74 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::space_dimension().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), adjust_topology_and_space_dimension(), affine_image(), Parma_Polyhedra_Library::Polyhedron::generators(), insert(), insert_pending(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), relation_with(), satisfied_by_all_generators(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), and Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible().
00074 { 00075 return Linear_System::space_dimension(); 00076 }
void Parma_Polyhedra_Library::Generator_System::clear | ( | ) | [inline] |
Removes all the generators from the generator system and sets its space dimension to 0.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 79 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::clear().
Referenced by Parma_Polyhedra_Library::Grid_Generator_System::clear(), Parma_Polyhedra_Library::Polyhedron::set_empty(), and Parma_Polyhedra_Library::Polyhedron::set_zero_dim_univ().
00079 { 00080 Linear_System::clear(); 00081 }
void Parma_Polyhedra_Library::Generator_System::insert | ( | const Generator & | g | ) |
Inserts in *this
a copy of the generator g
, increasing the number of space dimensions if needed.
Definition at line 281 of file Generator_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Generator::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_generator(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_evolving_rays(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_preimage(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), ppl_Generator_System_insert_Generator(), ppl_new_C_Polyhedron_from_generators(), ppl_new_NNC_Polyhedron_from_generators(), ppl_Polyhedron_add_generators(), and ppl_Polyhedron_add_generators_and_minimize().
00281 { 00282 // We are sure that the matrix has no pending rows 00283 // and that the new row is not a pending generator. 00284 assert(num_pending_rows() == 0); 00285 if (topology() == g.topology()) 00286 Linear_System::insert(g); 00287 else 00288 // `*this' and `g' have different topologies. 00289 if (is_necessarily_closed()) { 00290 // Padding the matrix with the column 00291 // corresponding to the epsilon coefficients: 00292 // all points must have epsilon coordinate equal to 1 00293 // (i.e., the epsilon coefficient is equal to the divisor); 00294 // rays and lines must have epsilon coefficient equal to 0. 00295 // Note: normalization is preserved. 00296 const dimension_type eps_index = num_columns(); 00297 add_zero_columns(1); 00298 Generator_System& gs = *this; 00299 for (dimension_type i = num_rows(); i-- > 0; ) { 00300 Generator& gen = gs[i]; 00301 if (!gen.is_line_or_ray()) 00302 gen[eps_index] = gen[0]; 00303 } 00304 set_not_necessarily_closed(); 00305 // Inserting the new generator. 00306 Linear_System::insert(g); 00307 } 00308 else { 00309 // The generator system is NOT necessarily closed: 00310 // copy the generator, adding the missing dimensions 00311 // and the epsilon coefficient. 00312 const dimension_type new_size = 2 + std::max(g.space_dimension(), 00313 space_dimension()); 00314 Generator tmp_g(g, new_size); 00315 // If it was a point, set the epsilon coordinate to 1 00316 // (i.e., set the coefficient equal to the divisor). 00317 // Note: normalization is preserved. 00318 if (!tmp_g.is_line_or_ray()) 00319 tmp_g[new_size - 1] = tmp_g[0]; 00320 tmp_g.set_not_necessarily_closed(); 00321 // Inserting the new generator. 00322 Linear_System::insert(tmp_g); 00323 } 00324 assert(OK()); 00325 }
const Generator_System & Parma_Polyhedra_Library::Generator_System::zero_dim_univ | ( | ) | [inline, static] |
Returns the singleton system containing only Generator::zero_dim_point().
Definition at line 172 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Generator::zero_dim_point().
00172 { 00173 static const Generator_System zdu(Generator::zero_dim_point()); 00174 return zdu; 00175 }
Generator_System::const_iterator Parma_Polyhedra_Library::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::Matrix.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 158 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::begin(), and Parma_Polyhedra_Library::Linear_System::is_necessarily_closed().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Grid_Generator_System::begin(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), has_closure_points(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), operator<<(), ppl_Generator_System_begin(), ppl_Polyhedron_get_generators(), ppl_Polyhedron_get_minimized_generators(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00158 { 00159 const_iterator i(Linear_System::begin(), *this); 00160 if (!is_necessarily_closed()) 00161 i.skip_forward(); 00162 return i; 00163 }
Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::end | ( | ) | const [inline] |
Returns the past-the-end const_iterator.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 166 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Matrix::end().
Referenced by Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), Parma_Polyhedra_Library::Grid_Generator_System::end(), has_closure_points(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), operator<<(), ppl_Generator_System_end(), ppl_Polyhedron_get_generators(), ppl_Polyhedron_get_minimized_generators(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().
00166 { 00167 const const_iterator i(Linear_System::end(), *this); 00168 return i; 00169 }
bool Parma_Polyhedra_Library::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 Generator.
Reimplemented from Parma_Polyhedra_Library::Matrix.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 1002 of file Generator_System.cc.
References Parma_Polyhedra_Library::Matrix::num_rows(), and Parma_Polyhedra_Library::Matrix::OK().
Referenced by add_corresponding_closure_points(), add_corresponding_points(), adjust_topology_and_space_dimension(), ascii_load(), insert(), insert_pending(), and Parma_Polyhedra_Library::Polyhedron::OK().
01002 { 01003 // A Generator_System must be a valid Linear_System; do not check for 01004 // strong normalization, since this will be done when 01005 // checking each individual generator. 01006 if (!Linear_System::OK(false)) 01007 return false; 01008 01009 // Checking each generator in the system. 01010 const Generator_System& x = *this; 01011 for (dimension_type i = num_rows(); i-- > 0; ) 01012 if (!x[i].OK()) 01013 return false; 01014 01015 // All checks passed. 01016 return true; 01017 }
void Parma_Polyhedra_Library::Generator_System::ascii_dump | ( | ) | const |
Writes to std::cerr
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Referenced by Parma_Polyhedra_Library::Polyhedron::ascii_dump(), Parma_Polyhedra_Library::Grid_Generator_System::ascii_dump(), and Parma_Polyhedra_Library::Polyhedron::OK().
void Parma_Polyhedra_Library::Generator_System::ascii_dump | ( | std::ostream & | s | ) | const |
Writes to s
an ASCII representation of *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 829 of file Generator_System.cc.
References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Linear_System::first_pending_row(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Generator::RAY, and Parma_Polyhedra_Library::Generator::type().
00829 { 00830 const Generator_System& x = *this; 00831 const dimension_type x_num_rows = x.num_rows(); 00832 const dimension_type x_num_columns = x.num_columns(); 00833 s << "topology " << (is_necessarily_closed() 00834 ? "NECESSARILY_CLOSED" 00835 : "NOT_NECESSARILY_CLOSED") 00836 << "\n" 00837 << x_num_rows << " x " << x_num_columns << ' ' 00838 << (x.is_sorted() ? "(sorted)" : "(not_sorted)") 00839 << "\n" 00840 << "index_first_pending " << x.first_pending_row() 00841 << "\n"; 00842 for (dimension_type i = 0; i < x_num_rows; ++i) { 00843 const Generator& g = x[i]; 00844 for (dimension_type j = 0; j < x_num_columns; ++j) 00845 s << g[j] << ' '; 00846 switch (g.type()) { 00847 case Generator::LINE: 00848 s << "L"; 00849 break; 00850 case Generator::RAY: 00851 s << "R"; 00852 break; 00853 case Generator::POINT: 00854 s << "P"; 00855 break; 00856 case Generator::CLOSURE_POINT: 00857 s << "C"; 00858 break; 00859 } 00860 s << "\n"; 00861 } 00862 }
void Parma_Polyhedra_Library::Generator_System::print | ( | ) | const |
Prints *this
to std::cerr
using operator<<
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
bool Parma_Polyhedra_Library::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::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 867 of file Generator_System.cc.
References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Generator::RAY, Parma_Polyhedra_Library::Linear_System::resize_no_copy(), Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row(), Parma_Polyhedra_Library::Linear_System::set_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), and Parma_Polyhedra_Library::Linear_System::set_sorted().
Referenced by Parma_Polyhedra_Library::Polyhedron::ascii_load().
00867 { 00868 std::string str; 00869 if (!(s >> str) || str != "topology") 00870 return false; 00871 if (!(s >> str)) 00872 return false; 00873 if (str == "NECESSARILY_CLOSED") 00874 set_necessarily_closed(); 00875 else { 00876 if (str != "NOT_NECESSARILY_CLOSED") 00877 return false; 00878 set_not_necessarily_closed(); 00879 } 00880 00881 dimension_type nrows; 00882 dimension_type ncols; 00883 if (!(s >> nrows)) 00884 return false; 00885 if (!(s >> str)) 00886 return false; 00887 if (!(s >> ncols)) 00888 return false; 00889 resize_no_copy(nrows, ncols); 00890 00891 if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)")) 00892 return false; 00893 set_sorted(str == "(sorted)"); 00894 dimension_type index; 00895 if (!(s >> str) || str != "index_first_pending") 00896 return false; 00897 if (!(s >> index)) 00898 return false; 00899 set_index_first_pending_row(index); 00900 00901 Generator_System& x = *this; 00902 for (dimension_type i = 0; i < x.num_rows(); ++i) { 00903 for (dimension_type j = 0; j < x.num_columns(); ++j) 00904 if (!(s >> x[i][j])) 00905 return false; 00906 00907 if (!(s >> str)) 00908 return false; 00909 if (str == "L") 00910 x[i].set_is_line(); 00911 else 00912 x[i].set_is_ray_or_point(); 00913 00914 // Checking for equality of actual and declared types. 00915 switch (x[i].type()) { 00916 case Generator::LINE: 00917 if (str == "L") 00918 continue; 00919 break; 00920 case Generator::RAY: 00921 if (str == "R") 00922 continue; 00923 break; 00924 case Generator::POINT: 00925 if (str == "P") 00926 continue; 00927 break; 00928 case Generator::CLOSURE_POINT: 00929 if (str == "C") 00930 continue; 00931 break; 00932 } 00933 // Reaching this point means that the input was illegal. 00934 return false; 00935 } 00936 00937 // Checking for well-formedness. 00938 00939 assert(OK()); 00940 return true; 00941 }
memory_size_type Parma_Polyhedra_Library::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::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 188 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().
00188 { 00189 return Linear_System::total_memory_in_bytes(); 00190 }
memory_size_type Parma_Polyhedra_Library::Generator_System::external_memory_in_bytes | ( | ) | const [inline] |
Returns the size in bytes of the memory managed by *this
.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 183 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().
Referenced by Parma_Polyhedra_Library::Polyhedron::external_memory_in_bytes().
00183 { 00184 return Linear_System::external_memory_in_bytes(); 00185 }
void Parma_Polyhedra_Library::Generator_System::swap | ( | Generator_System & | y | ) | [inline] |
Swaps *this
with y
.
Definition at line 178 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::swap().
Referenced by Parma_Polyhedra_Library::Grid_Generator_System::swap(), and swap().
00178 { 00179 Linear_System::swap(y); 00180 }
bool Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension | ( | Topology | topol, | |
dimension_type | num_dimensions | |||
) | [private] |
Adjusts *this
so that it matches the topology and the number of space dimensions given as parameters (adding or removing columns if needed). Returns false
if and only if topol
is equal to NECESSARILY_CLOSED
and *this
contains closure points.
Definition at line 39 of file Generator_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::erase_to_end(), has_closure_points(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::Linear_System::normalize(), Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Linear_System::remove_trailing_columns(), Parma_Polyhedra_Library::Linear_System::set_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Matrix::swap_columns(), and Parma_Polyhedra_Library::Linear_System::topology().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_generator(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Polyhedron::generators(), Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00040 { 00041 assert(space_dimension() <= new_space_dim); 00042 00043 const dimension_type old_space_dim = space_dimension(); 00044 const Topology old_topology = topology(); 00045 dimension_type cols_to_be_added = new_space_dim - old_space_dim; 00046 00047 // Dealing with empty constraint systems first. 00048 if (num_rows() == 0) { 00049 if (num_columns() == 0) 00050 if (new_topology == NECESSARILY_CLOSED) { 00051 add_zero_columns(cols_to_be_added + 1); 00052 set_necessarily_closed(); 00053 } 00054 else { 00055 add_zero_columns(cols_to_be_added + 2); 00056 set_not_necessarily_closed(); 00057 } 00058 else 00059 // Here `num_columns() > 0'. 00060 if (old_topology != new_topology) 00061 if (new_topology == NECESSARILY_CLOSED) { 00062 switch (cols_to_be_added) { 00063 case 0: 00064 remove_trailing_columns(1); 00065 break; 00066 case 1: 00067 // Nothing to do. 00068 break; 00069 default: 00070 add_zero_columns(cols_to_be_added - 1); 00071 } 00072 set_necessarily_closed(); 00073 } 00074 else { 00075 // Here old_topology == NECESSARILY_CLOSED 00076 // and new_topology == NOT_NECESSARILY_CLOSED. 00077 add_zero_columns(cols_to_be_added + 1); 00078 set_not_necessarily_closed(); 00079 } 00080 else 00081 // Here topologies agree. 00082 if (cols_to_be_added > 0) 00083 add_zero_columns(cols_to_be_added); 00084 assert(OK()); 00085 return true; 00086 } 00087 00088 // Here `num_rows() > 0'. 00089 if (cols_to_be_added > 0) 00090 if (old_topology != new_topology) 00091 if (new_topology == NECESSARILY_CLOSED) { 00092 // A NOT_NECESSARILY_CLOSED generator system 00093 // can be converted to a NECESSARILY_CLOSED one 00094 // only if it does not contain closure points. 00095 // This check has to be performed under the user viewpoint. 00096 if (has_closure_points()) 00097 return false; 00098 // For a correct implementation, we have to remove those 00099 // closure points that were matching a point (i.e., those 00100 // that are in the generator system, but are invisible to 00101 // the user). 00102 Generator_System& gs = *this; 00103 dimension_type num_closure_points = 0; 00104 dimension_type gs_end = gs.num_rows(); 00105 for (dimension_type i = 0; i < gs_end; ) { 00106 // All the closure points seen so far have consecutive 00107 // indices starting from `i'. 00108 if (num_closure_points > 0) 00109 // Let next generator have index `i'. 00110 std::swap(gs[i], gs[i+num_closure_points]); 00111 if (gs[i].is_closure_point()) { 00112 ++num_closure_points; 00113 --gs_end; 00114 } 00115 else 00116 ++i; 00117 } 00118 // We may have identified some closure points. 00119 if (num_closure_points > 0) { 00120 assert(num_closure_points == num_rows() - gs_end); 00121 erase_to_end(gs_end); 00122 } 00123 // Remove the epsilon column, re-normalize and, after that, 00124 // add the missing dimensions. This ensures that 00125 // non-zero epsilon coefficients will be cleared. 00126 remove_trailing_columns(1); 00127 set_necessarily_closed(); 00128 normalize(); 00129 add_zero_columns(cols_to_be_added); 00130 } 00131 else { 00132 // A NECESSARILY_CLOSED generator system is converted to 00133 // a NOT_NECESSARILY_CLOSED one by adding a further column 00134 // and setting the epsilon coordinate of all points to 1. 00135 // Note: normalization is preserved. 00136 add_zero_columns(cols_to_be_added + 1); 00137 Generator_System& gs = *this; 00138 const dimension_type eps_index = new_space_dim + 1; 00139 for (dimension_type i = num_rows(); i-- > 0; ) 00140 gs[i][eps_index] = gs[i][0]; 00141 set_not_necessarily_closed(); 00142 } 00143 else { 00144 // Topologies agree: first add the required zero columns ... 00145 add_zero_columns(cols_to_be_added); 00146 // ... and, if needed, move the epsilon coefficients 00147 // to the new last column. 00148 if (old_topology == NOT_NECESSARILY_CLOSED) 00149 swap_columns(old_space_dim + 1, new_space_dim + 1); 00150 } 00151 else 00152 // Here `cols_to_be_added == 0'. 00153 if (old_topology != new_topology) 00154 if (new_topology == NECESSARILY_CLOSED) { 00155 // A NOT_NECESSARILY_CLOSED generator system 00156 // can be converted in to a NECESSARILY_CLOSED one 00157 // only if it does not contain closure points. 00158 if (has_closure_points()) 00159 return false; 00160 // We just remove the column of the epsilon coefficients. 00161 remove_trailing_columns(1); 00162 set_necessarily_closed(); 00163 } 00164 else { 00165 // Add the column of the epsilon coefficients 00166 // and set the epsilon coordinate of all points to 1. 00167 // Note: normalization is preserved. 00168 add_zero_columns(1); 00169 Generator_System& gs = *this; 00170 const dimension_type eps_index = new_space_dim + 1; 00171 for (dimension_type i = num_rows(); i-- > 0; ) 00172 gs[i][eps_index] = gs[i][0]; 00173 set_not_necessarily_closed(); 00174 } 00175 // We successfully adjusted dimensions and topology. 00176 assert(OK()); 00177 return true; 00178 }
void Parma_Polyhedra_Library::Generator_System::add_corresponding_points | ( | ) | [private] |
For each unmatched closure point in *this
, adds the corresponding point.
It is assumed that the topology of *this
is NOT_NECESSARILY_CLOSED
.
Definition at line 212 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_System::add_pending_row(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), and OK().
Referenced by Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().
00212 { 00213 assert(!is_necessarily_closed()); 00214 // NOTE: we always add (pending) rows at the end of the generator system. 00215 // Updating `index_first_pending', if needed, is done by the caller. 00216 Generator_System& gs = *this; 00217 const dimension_type n_rows = gs.num_rows(); 00218 const dimension_type eps_index = gs.num_columns() - 1; 00219 for (dimension_type i = 0; i < n_rows; i++) { 00220 const Generator& g = gs[i]; 00221 if (!g.is_line_or_ray() && g[eps_index] == 0) { 00222 // `g' is a closure point: adding the point. 00223 // Note: normalization is preserved. 00224 Generator p = g; 00225 p[eps_index] = p[0]; 00226 gs.add_pending_row(p); 00227 } 00228 } 00229 assert(OK()); 00230 }
bool Parma_Polyhedra_Library::Generator_System::has_points | ( | ) | const [private] |
Returns true
if and only if *this
contains one or more points.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 245 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), Parma_Polyhedra_Library::Grid_Generator_System::has_points(), Parma_Polyhedra_Library::Polyhedron::OK(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00245 { 00246 const Generator_System& gs = *this; 00247 // Avoiding the repeated tests on topology. 00248 if (is_necessarily_closed()) 00249 for (dimension_type i = num_rows(); i-- > 0; ) { 00250 if (!gs[i].is_line_or_ray()) 00251 return true; 00252 } 00253 else { 00254 // !is_necessarily_closed() 00255 const dimension_type eps_index = gs.num_columns() - 1; 00256 for (dimension_type i = num_rows(); i-- > 0; ) 00257 if (gs[i][eps_index] != 0) 00258 return true; 00259 } 00260 return false; 00261 }
void Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points | ( | ) | [private] |
For each unmatched point in *this
, adds the corresponding closure point.
It is assumed that the topology of *this
is NOT_NECESSARILY_CLOSED
.
Definition at line 185 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_System::add_pending_row(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Row::normalize(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), and OK().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().
00185 { 00186 assert(!is_necessarily_closed()); 00187 // NOTE: we always add (pending) rows at the end of the generator system. 00188 // Updating `index_first_pending', if needed, is done by the caller. 00189 Generator_System& gs = *this; 00190 const dimension_type n_rows = gs.num_rows(); 00191 const dimension_type eps_index = gs.num_columns() - 1; 00192 for (dimension_type i = n_rows; i-- > 0; ) { 00193 const Generator& g = gs[i]; 00194 if (g[eps_index] > 0) { 00195 // `g' is a point: adding the closure point. 00196 Generator cp = g; 00197 cp[eps_index] = 0; 00198 // Enforcing normalization. 00199 cp.normalize(); 00200 gs.add_pending_row(cp); 00201 } 00202 } 00203 assert(OK()); 00204 }
bool Parma_Polyhedra_Library::Generator_System::has_closure_points | ( | ) | const [private] |
Returns true
if and only if *this
contains one or more closure points.
Note: the check for the presence of closure points is done under the point of view of the user. Namely, we scan the generator system using high-level iterators, so that closure points that are matching the corresponding points will be disregarded.
Definition at line 233 of file Generator_System.cc.
References begin(), end(), and Parma_Polyhedra_Library::Linear_System::is_necessarily_closed().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), and adjust_topology_and_space_dimension().
00233 { 00234 if (is_necessarily_closed()) 00235 return false; 00236 // Adopt the point of view of the user. 00237 for (Generator_System::const_iterator i = begin(), 00238 iend = end(); i != iend; ++i) 00239 if (i->is_closure_point()) 00240 return true; 00241 return false; 00242 }
Generator & Parma_Polyhedra_Library::Generator_System::operator[] | ( | dimension_type | k | ) | [inline, private] |
Returns the k-
th generator of the system.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 84 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator[]().
Referenced by Parma_Polyhedra_Library::Grid_Generator_System::operator[]().
00084 { 00085 return static_cast<Generator&>(Linear_System::operator[](k)); 00086 }
const Generator & Parma_Polyhedra_Library::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::Linear_System.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 89 of file Generator_System.inlines.hh.
References Parma_Polyhedra_Library::Linear_System::operator[]().
00089 { 00090 return static_cast<const Generator&>(Linear_System::operator[](k)); 00091 }
PPL::Poly_Con_Relation Parma_Polyhedra_Library::Generator_System::relation_with | ( | const Constraint & | c | ) | const [private] |
Returns the relations holding between the generator system and the constraint c
.
Definition at line 415 of file Generator_System.cc.
References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Poly_Con_Relation::implies(), Parma_Polyhedra_Library::Poly_Con_Relation::is_disjoint(), Parma_Polyhedra_Library::Poly_Con_Relation::is_included(), Parma_Polyhedra_Library::Generator::is_point(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Generator::RAY, Parma_Polyhedra_Library::Scalar_Products::reduced_sign(), Parma_Polyhedra_Library::Poly_Con_Relation::saturates(), Parma_Polyhedra_Library::Scalar_Products::sign(), Parma_Polyhedra_Library::Constraint::space_dimension(), space_dimension(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, Parma_Polyhedra_Library::Poly_Con_Relation::strictly_intersects(), Parma_Polyhedra_Library::Generator::type(), and Parma_Polyhedra_Library::Constraint::type().
Referenced by Parma_Polyhedra_Library::Polyhedron::relation_with().
00415 { 00416 // Note: this method is not public and it is the responsibility 00417 // of the caller to actually test for dimension compatibility. 00418 // We simply assert it. 00419 assert(space_dimension() >= c.space_dimension()); 00420 // Number of generators: the case of an empty polyhedron 00421 // has already been filtered out by the caller. 00422 const dimension_type n_rows = num_rows(); 00423 assert(n_rows > 0); 00424 const Generator_System& gs = *this; 00425 00426 // `result' will keep the relation holding between the generators 00427 // we have seen so far and the constraint `c'. 00428 Poly_Con_Relation result = Poly_Con_Relation::saturates(); 00429 00430 switch (c.type()) { 00431 00432 case Constraint::EQUALITY: 00433 { 00434 // The hyperplane defined by the equality `c' is included 00435 // in the set of points satisfying `c' (it is the same set!). 00436 result = result && Poly_Con_Relation::is_included(); 00437 // The following integer variable will hold the scalar product sign 00438 // of either the first point or the first non-saturating ray we find. 00439 // If it is equal to 2, then it means that we haven't found such 00440 // a generator yet. 00441 int first_point_or_nonsaturating_ray_sign = 2; 00442 00443 for (dimension_type i = n_rows; i-- > 0; ) { 00444 const Generator& g = gs[i]; 00445 const int sp_sign = Scalar_Products::sign(c, g); 00446 // Checking whether the generator saturates the equality. 00447 // If that is the case, then we have to do something only if 00448 // the generator is a point. 00449 if (sp_sign == 0) { 00450 if (g.is_point()) 00451 if (first_point_or_nonsaturating_ray_sign == 2) 00452 // It is the first time that we find a point and 00453 // we have not found a non-saturating ray yet. 00454 first_point_or_nonsaturating_ray_sign = 0; 00455 else 00456 // We already found a point or a non-saturating ray. 00457 if (first_point_or_nonsaturating_ray_sign != 0) 00458 return Poly_Con_Relation::strictly_intersects(); 00459 } 00460 else 00461 // Here we know that sp_sign != 0. 00462 switch (g.type()) { 00463 00464 case Generator::LINE: 00465 // If a line does not saturate `c', then there is a strict 00466 // intersection between the points satisfying `c' 00467 // and the points generated by `gs'. 00468 return Poly_Con_Relation::strictly_intersects(); 00469 00470 case Generator::RAY: 00471 if (first_point_or_nonsaturating_ray_sign == 2) { 00472 // It is the first time that we have a non-saturating ray 00473 // and we have not found any point yet. 00474 first_point_or_nonsaturating_ray_sign = sp_sign; 00475 result = Poly_Con_Relation::is_disjoint(); 00476 } 00477 else 00478 // We already found a point or a non-saturating ray. 00479 if (sp_sign != first_point_or_nonsaturating_ray_sign) 00480 return Poly_Con_Relation::strictly_intersects(); 00481 break; 00482 00483 case Generator::POINT: 00484 case Generator::CLOSURE_POINT: 00485 // NOTE: a non-saturating closure point is treated as 00486 // a normal point. 00487 if (first_point_or_nonsaturating_ray_sign == 2) { 00488 // It is the first time that we find a point and 00489 // we have not found a non-saturating ray yet. 00490 first_point_or_nonsaturating_ray_sign = sp_sign; 00491 result = Poly_Con_Relation::is_disjoint(); 00492 } 00493 else 00494 // We already found a point or a non-saturating ray. 00495 if (sp_sign != first_point_or_nonsaturating_ray_sign) 00496 return Poly_Con_Relation::strictly_intersects(); 00497 break; 00498 } 00499 } 00500 } 00501 break; 00502 00503 case Constraint::NONSTRICT_INEQUALITY: 00504 { 00505 // The hyperplane implicitly defined by the non-strict inequality `c' 00506 // is included in the set of points satisfying `c'. 00507 result = result && Poly_Con_Relation::is_included(); 00508 // The following boolean variable will be set to `false' 00509 // as soon as either we find (any) point or we find a 00510 // non-saturating ray. 00511 bool first_point_or_nonsaturating_ray = true; 00512 00513 for (dimension_type i = n_rows; i-- > 0; ) { 00514 const Generator& g = gs[i]; 00515 const int sp_sign = Scalar_Products::sign(c, g); 00516 // Checking whether the generator saturates the non-strict 00517 // inequality. If that is the case, then we have to do something 00518 // only if the generator is a point. 00519 if (sp_sign == 0) { 00520 if (g.is_point()) 00521 if (first_point_or_nonsaturating_ray) 00522 // It is the first time that we have a point and 00523 // we have not found a non-saturating ray yet. 00524 first_point_or_nonsaturating_ray = false; 00525 else 00526 // We already found a point or a non-saturating ray before. 00527 if (result == Poly_Con_Relation::is_disjoint()) 00528 // Since g saturates c, we have a strict intersection if 00529 // none of the generators seen so far are included in `c'. 00530 return Poly_Con_Relation::strictly_intersects(); 00531 } 00532 else 00533 // Here we know that sp_sign != 0. 00534 switch (g.type()) { 00535 00536 case Generator::LINE: 00537 // If a line does not saturate `c', then there is a strict 00538 // intersection between the points satisfying `c' and 00539 // the points generated by `gs'. 00540 return Poly_Con_Relation::strictly_intersects(); 00541 00542 case Generator::RAY: 00543 if (first_point_or_nonsaturating_ray) { 00544 // It is the first time that we have a non-saturating ray 00545 // and we have not found any point yet. 00546 first_point_or_nonsaturating_ray = false; 00547 result = (sp_sign > 0) 00548 ? Poly_Con_Relation::is_included() 00549 : Poly_Con_Relation::is_disjoint(); 00550 } 00551 else { 00552 // We already found a point or a non-saturating ray. 00553 if ((sp_sign > 0 00554 && result == Poly_Con_Relation::is_disjoint()) 00555 || (sp_sign < 0 00556 && result.implies(Poly_Con_Relation::is_included()))) 00557 // We have a strict intersection if either: 00558 // - `g' satisfies `c' but none of the generators seen 00559 // so far are included in `c'; or 00560 // - `g' does not satisfy `c' and all the generators 00561 // seen so far are included in `c'. 00562 return Poly_Con_Relation::strictly_intersects(); 00563 if (sp_sign > 0) 00564 // Here all the generators seen so far either saturate 00565 // or are included in `c'. 00566 // Since `g' does not saturate `c' ... 00567 result = Poly_Con_Relation::is_included(); 00568 } 00569 break; 00570 00571 case Generator::POINT: 00572 case Generator::CLOSURE_POINT: 00573 // NOTE: a non-saturating closure point is treated as 00574 // a normal point. 00575 if (first_point_or_nonsaturating_ray) { 00576 // It is the first time that we have a point and 00577 // we have not found a non-saturating ray yet. 00578 // - If point `g' saturates `c', then all the generators 00579 // seen so far saturate `c'. 00580 // - If point `g' is included (but does not saturate) `c', 00581 // then all the generators seen so far are included in `c'. 00582 // - If point `g' does not satisfy `c', then all the 00583 // generators seen so far are disjoint from `c'. 00584 first_point_or_nonsaturating_ray = false; 00585 if (sp_sign > 0) 00586 result = Poly_Con_Relation::is_included(); 00587 else if (sp_sign < 0) 00588 result = Poly_Con_Relation::is_disjoint(); 00589 } 00590 else { 00591 // We already found a point or a non-saturating ray before. 00592 if ((sp_sign > 0 00593 && result == Poly_Con_Relation::is_disjoint()) 00594 || (sp_sign < 0 00595 && result.implies(Poly_Con_Relation::is_included()))) 00596 // We have a strict intersection if either: 00597 // - `g' satisfies or saturates `c' but none of the 00598 // generators seen so far are included in `c'; or 00599 // - `g' does not satisfy `c' and all the generators 00600 // seen so far are included in `c'. 00601 return Poly_Con_Relation::strictly_intersects(); 00602 if (sp_sign > 0) 00603 // Here all the generators seen so far either saturate 00604 // or are included in `c'. 00605 // Since `g' does not saturate `c' ... 00606 result = Poly_Con_Relation::is_included(); 00607 } 00608 break; 00609 } 00610 } 00611 } 00612 break; 00613 00614 case Constraint::STRICT_INEQUALITY: 00615 { 00616 // The hyperplane implicitly defined by the strict inequality `c' 00617 // is disjoint from the set of points satisfying `c'. 00618 result = result && Poly_Con_Relation::is_disjoint(); 00619 // The following boolean variable will be set to `false' 00620 // as soon as either we find (any) point or we find a 00621 // non-saturating ray. 00622 bool first_point_or_nonsaturating_ray = true; 00623 for (dimension_type i = n_rows; i-- > 0; ) { 00624 const Generator& g = gs[i]; 00625 // Using the reduced scalar product operator to avoid 00626 // both topology and num_columns mismatches. 00627 const int sp_sign = Scalar_Products::reduced_sign(c, g); 00628 // Checking whether the generator saturates the strict inequality. 00629 // If that is the case, then we have to do something 00630 // only if the generator is a point. 00631 if (sp_sign == 0) { 00632 if (g.is_point()) 00633 if (first_point_or_nonsaturating_ray) 00634 // It is the first time that we have a point and 00635 // we have not found a non-saturating ray yet. 00636 first_point_or_nonsaturating_ray = false; 00637 else 00638 // We already found a point or a non-saturating ray before. 00639 if (result == Poly_Con_Relation::is_included()) 00640 return Poly_Con_Relation::strictly_intersects(); 00641 } 00642 else 00643 // Here we know that sp_sign != 0. 00644 switch (g.type()) { 00645 00646 case Generator::LINE: 00647 // If a line does not saturate `c', then there is a strict 00648 // intersection between the points satisfying `c' and the points 00649 // generated by `gs'. 00650 return Poly_Con_Relation::strictly_intersects(); 00651 00652 case Generator::RAY: 00653 if (first_point_or_nonsaturating_ray) { 00654 // It is the first time that we have a non-saturating ray 00655 // and we have not found any point yet. 00656 first_point_or_nonsaturating_ray = false; 00657 result = (sp_sign > 0) 00658 ? Poly_Con_Relation::is_included() 00659 : Poly_Con_Relation::is_disjoint(); 00660 } 00661 else { 00662 // We already found a point or a non-saturating ray before. 00663 if ((sp_sign > 0 00664 && result.implies(Poly_Con_Relation::is_disjoint())) 00665 || 00666 (sp_sign <= 0 00667 && result == Poly_Con_Relation::is_included())) 00668 return Poly_Con_Relation::strictly_intersects(); 00669 if (sp_sign < 0) 00670 // Here all the generators seen so far either saturate 00671 // or are disjoint from `c'. 00672 // Since `g' does not saturate `c' ... 00673 result = Poly_Con_Relation::is_disjoint(); 00674 } 00675 break; 00676 00677 case Generator::POINT: 00678 case Generator::CLOSURE_POINT: 00679 if (first_point_or_nonsaturating_ray) { 00680 // It is the first time that we have a point and 00681 // we have not found a non-saturating ray yet. 00682 // - If point `g' saturates `c', then all the generators 00683 // seen so far saturate `c'. 00684 // - If point `g' is included in (but does not saturate) `c', 00685 // then all the generators seen so far are included in `c'. 00686 // - If point `g' strictly violates `c', then all the 00687 // generators seen so far are disjoint from `c'. 00688 first_point_or_nonsaturating_ray = false; 00689 if (sp_sign > 0) 00690 result = Poly_Con_Relation::is_included(); 00691 else if (sp_sign < 0) 00692 result = Poly_Con_Relation::is_disjoint(); 00693 } 00694 else { 00695 // We already found a point or a non-saturating ray before. 00696 if ((sp_sign > 0 00697 && result.implies(Poly_Con_Relation::is_disjoint())) 00698 || 00699 (sp_sign <= 0 00700 && result == Poly_Con_Relation::is_included())) 00701 return Poly_Con_Relation::strictly_intersects(); 00702 if (sp_sign < 0) 00703 // Here all the generators seen so far either saturate 00704 // or are disjoint from `c'. 00705 // Since `g' does not saturate `c' ... 00706 result = Poly_Con_Relation::is_disjoint(); 00707 } 00708 break; 00709 } 00710 } 00711 } 00712 break; 00713 } 00714 // We have seen all generators. 00715 return result; 00716 }
bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators | ( | const Constraint & | c | ) | const [private] |
Returns true
if all the generators satisfy c
.
Definition at line 720 of file Generator_System.cc.
References Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Generator::is_line(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, space_dimension(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, Parma_Polyhedra_Library::Generator::type(), and Parma_Polyhedra_Library::Constraint::type().
Referenced by Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), and Parma_Polyhedra_Library::Polyhedron::select_CH78_constraints().
00720 { 00721 assert(c.space_dimension() <= space_dimension()); 00722 00723 // Setting `sps' to the appropriate scalar product sign operator. 00724 // This also avoids problems when having _legal_ topology mismatches 00725 // (which could also cause a mismatch in the number of columns). 00726 Topology_Adjusted_Scalar_Product_Sign sps(c); 00727 00728 const Generator_System& gs = *this; 00729 switch (c.type()) { 00730 case Constraint::EQUALITY: 00731 // Equalities must be saturated by all generators. 00732 for (dimension_type i = gs.num_rows(); i-- > 0; ) 00733 if (sps(c, gs[i]) != 0) 00734 return false; 00735 break; 00736 case Constraint::NONSTRICT_INEQUALITY: 00737 // Non-strict inequalities must be saturated by lines and 00738 // satisfied by all the other generators. 00739 for (dimension_type i = gs.num_rows(); i-- > 0; ) { 00740 const Generator& g = gs[i]; 00741 const int sp_sign = sps(c, g); 00742 if (g.is_line()) { 00743 if (sp_sign != 0) 00744 return false; 00745 } 00746 else 00747 // `g' is a ray, point or closure point. 00748 if (sp_sign < 0) 00749 return false; 00750 } 00751 break; 00752 case Constraint::STRICT_INEQUALITY: 00753 // Strict inequalities must be saturated by lines, 00754 // satisfied by all generators, and must not be saturated by points. 00755 for (dimension_type i = gs.num_rows(); i-- > 0; ) { 00756 const Generator& g = gs[i]; 00757 const int sp_sign = sps(c, g); 00758 switch (g.type()) { 00759 case Generator::POINT: 00760 if (sp_sign <= 0) 00761 return false; 00762 break; 00763 case Generator::LINE: 00764 if (sp_sign != 0) 00765 return false; 00766 break; 00767 default: 00768 // `g' is a ray or closure point. 00769 if (sp_sign < 0) 00770 return false; 00771 break; 00772 } 00773 } 00774 break; 00775 } 00776 // If we reach this point, `c' is satisfied by all generators. 00777 return true; 00778 }
bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators_C | ( | const Constraint & | c | ) | const [private] |
Returns true
if all the generators satisfy c
.
It is assumed that c.is_necessarily_closed()
holds.
bool Parma_Polyhedra_Library::Generator_System::satisfied_by_all_generators_NNC | ( | const Constraint & | c | ) | const [private] |
Returns true
if all the generators satisfy c
.
It is assumed that c.is_necessarily_closed()
does not hold.
void Parma_Polyhedra_Library::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.
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.
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 in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 783 of file Generator_System.cc.
References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), Parma_Polyhedra_Library::Linear_System::strong_normalize(), and TEMP_INTEGER.
Referenced by Parma_Polyhedra_Library::Polyhedron::affine_image(), and Parma_Polyhedra_Library::Polyhedron::affine_preimage().
00785 { 00786 Generator_System& x = *this; 00787 // `v' is the index of a column corresponding to 00788 // a "user" variable (i.e., it cannot be the inhomogeneous term, 00789 // nor the epsilon dimension of NNC polyhedra). 00790 assert(v > 0 && v <= x.space_dimension()); 00791 assert(expr.space_dimension() <= x.space_dimension()); 00792 assert(denominator > 0); 00793 00794 const dimension_type n_columns = x.num_columns(); 00795 const dimension_type n_rows = x.num_rows(); 00796 00797 // Compute the numerator of the affine transformation and assign it 00798 // to the column of `*this' indexed by `v'. 00799 TEMP_INTEGER(numerator); 00800 for (dimension_type i = n_rows; i-- > 0; ) { 00801 Generator& row = x[i]; 00802 Scalar_Products::assign(numerator, expr, row); 00803 std::swap(numerator, row[v]); 00804 } 00805 00806 if (denominator != 1) { 00807 // Since we want integer elements in the matrix, 00808 // we multiply by `denominator' all the columns of `*this' 00809 // having an index different from `v'. 00810 for (dimension_type i = n_rows; i-- > 0; ) { 00811 Generator& row = x[i]; 00812 for (dimension_type j = n_columns; j-- > 0; ) 00813 if (j != v) 00814 row[j] *= denominator; 00815 } 00816 } 00817 00818 // If the mapping is not invertible we may have transformed 00819 // valid lines and rays into the origin of the space. 00820 const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0); 00821 if (not_invertible) 00822 x.remove_invalid_lines_and_rays(); 00823 00824 // Strong normalization also resets the sortedness flag. 00825 x.strong_normalize(); 00826 }
PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_lines | ( | ) | const [private] |
Returns the number of lines of the system.
Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.
Definition at line 372 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Polyhedron::is_topologically_closed(), Parma_Polyhedra_Library::Grid_Generator_System::num_lines(), Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::Polyhedron::quick_equivalence_test(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().
00372 { 00373 // We are sure that this method is applied only to a matrix 00374 // that does not contain pending rows. 00375 assert(num_pending_rows() == 0); 00376 const Generator_System& gs = *this; 00377 dimension_type n = 0; 00378 // If the Linear_System happens to be sorted, take advantage of the fact 00379 // that lines are at the top of the system. 00380 if (is_sorted()) { 00381 dimension_type nrows = num_rows(); 00382 for (dimension_type i = 0; i < nrows && gs[i].is_line(); ++i) 00383 ++n; 00384 } 00385 else 00386 for (dimension_type i = num_rows(); i-- > 0 ; ) 00387 if (gs[i].is_line()) 00388 ++n; 00389 return n; 00390 }
PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_rays | ( | ) | const [private] |
Returns the number of rays of the system.
Definition at line 393 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().
Referenced by Parma_Polyhedra_Library::Grid_Generator_System::num_parameters(), and Parma_Polyhedra_Library::Polyhedron::OK().
00393 { 00394 // We are sure that this method is applied only to a matrix 00395 // that does not contain pending rows. 00396 assert(num_pending_rows() == 0); 00397 const Generator_System& gs = *this; 00398 dimension_type n = 0; 00399 // If the Linear_System happens to be sorted, take advantage of the fact 00400 // that rays and points are at the bottom of the system and 00401 // rays have the inhomogeneous term equal to zero. 00402 if (is_sorted()) { 00403 for (dimension_type i = num_rows(); i != 0 && gs[--i].is_ray_or_point(); ) 00404 if (gs[i].is_line_or_ray()) 00405 ++n; 00406 } 00407 else 00408 for (dimension_type i = num_rows(); i-- > 0 ; ) 00409 if (gs[i].is_ray()) 00410 ++n; 00411 return n; 00412 }
void Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays | ( | ) | [private] |
Removes all the invalid lines and rays.
The invalid lines and rays are those with all the homogeneous terms set to zero.
Definition at line 944 of file Generator_System.cc.
References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::Matrix::erase_to_end(), Parma_Polyhedra_Library::Linear_System::first_pending_row(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row(), and Parma_Polyhedra_Library::Linear_System::set_sorted().
Referenced by affine_image(), Parma_Polyhedra_Library::Polyhedron::remove_higher_space_dimensions(), Parma_Polyhedra_Library::Grid_Generator_System::remove_higher_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::remove_space_dimensions(), Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions(), and simplify().
00944 { 00945 // The origin of the vector space cannot be a valid line/ray. 00946 // NOTE: the following swaps will mix generators without even trying 00947 // to preserve sortedness: as a matter of fact, it will almost always 00948 // be the case that the input generator system is NOT sorted. 00949 Generator_System& gs = *this; 00950 dimension_type n_rows = gs.num_rows(); 00951 if (num_pending_rows() == 0) { 00952 for (dimension_type i = n_rows; i-- > 0; ) { 00953 Generator& g = gs[i]; 00954 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) { 00955 // An invalid line/ray has been found. 00956 --n_rows; 00957 std::swap(g, gs[n_rows]); 00958 gs.set_sorted(false); 00959 } 00960 } 00961 set_index_first_pending_row(n_rows); 00962 } 00963 else { 00964 // If the matrix has some pending rows, we can not 00965 // swap the "normal" rows with the pending rows. So 00966 // we must put at the end of the "normal" rows 00967 // the invalid "normal" rows, put them at the end 00968 // of the matrix, find the invalid rows in the pending 00969 // part and then erase the invalid rows that now 00970 // are in the bottom part of the matrix. 00971 assert(num_pending_rows() > 0); 00972 dimension_type first_pending = first_pending_row(); 00973 for (dimension_type i = first_pending; i-- > 0; ) { 00974 Generator& g = gs[i]; 00975 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) { 00976 // An invalid line/ray has been found. 00977 --first_pending; 00978 std::swap(g, gs[first_pending]); 00979 gs.set_sorted(false); 00980 } 00981 } 00982 const dimension_type num_invalid_rows 00983 = first_pending_row() - first_pending; 00984 set_index_first_pending_row(first_pending); 00985 for (dimension_type i = 0; i < num_invalid_rows; ++i) 00986 std::swap(gs[n_rows - i], gs[first_pending + i]); 00987 n_rows -= num_invalid_rows; 00988 for (dimension_type i = n_rows; i-- > first_pending; ) { 00989 Generator& g = gs[i]; 00990 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) { 00991 // An invalid line/ray has been found. 00992 --n_rows; 00993 std::swap(g, gs[n_rows]); 00994 gs.set_sorted(false); 00995 } 00996 } 00997 } 00998 gs.erase_to_end(n_rows); 00999 }
void Parma_Polyhedra_Library::Generator_System::simplify | ( | ) | [inline, private] |
Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of generators.
It is assumed that the system has no pending generators.
Reimplemented from Parma_Polyhedra_Library::Linear_System.
Definition at line 193 of file Generator_System.inlines.hh.
References remove_invalid_lines_and_rays(), and Parma_Polyhedra_Library::Linear_System::simplify().
00193 { 00194 Linear_System::simplify(); 00195 remove_invalid_lines_and_rays(); 00196 }
void Parma_Polyhedra_Library::Generator_System::insert_pending | ( | const Generator & | g | ) | [private] |
Inserts in *this
a copy of the generator g
, increasing the number of space dimensions if needed. It is a pending generator.
Definition at line 328 of file Generator_System.cc.
References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert_pending(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Generator::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_generator().
00328 { 00329 if (topology() == g.topology()) 00330 Linear_System::insert_pending(g); 00331 else 00332 // `*this' and `g' have different topologies. 00333 if (is_necessarily_closed()) { 00334 // Padding the matrix with the column 00335 // corresponding to the epsilon coefficients: 00336 // all points must have epsilon coordinate equal to 1 00337 // (i.e., the epsilon coefficient is equal to the divisor); 00338 // rays and lines must have epsilon coefficient equal to 0. 00339 // Note: normalization is preserved. 00340 const dimension_type eps_index = num_columns(); 00341 add_zero_columns(1); 00342 Generator_System& gs = *this; 00343 for (dimension_type i = num_rows(); i-- > 0; ) { 00344 Generator& gen = gs[i]; 00345 if (!gen.is_line_or_ray()) 00346 gen[eps_index] = gen[0]; 00347 } 00348 set_not_necessarily_closed(); 00349 // Inserting the new generator. 00350 Linear_System::insert_pending(g); 00351 } 00352 else { 00353 // The generator system is NOT necessarily closed: 00354 // copy the generator, adding the missing dimensions 00355 // and the epsilon coefficient. 00356 const dimension_type new_size = 2 + std::max(g.space_dimension(), 00357 space_dimension()); 00358 Generator tmp_g(g, new_size); 00359 // If it was a point, set the epsilon coordinate to 1 00360 // (i.e., set the coefficient equal to the divisor). 00361 // Note: normalization is preserved. 00362 if (!tmp_g.is_line_or_ray()) 00363 tmp_g[new_size - 1] = tmp_g[0]; 00364 tmp_g.set_not_necessarily_closed(); 00365 // Inserting the new generator. 00366 Linear_System::insert_pending(tmp_g); 00367 } 00368 assert(OK()); 00369 }
friend class const_iterator [friend] |
Definition at line 350 of file Generator_System.defs.hh.
friend class Parma_Polyhedra_Library::Polyhedron [friend] |
Definition at line 351 of file Generator_System.defs.hh.
friend class Parma_Polyhedra_Library::Grid_Generator_System [friend] |
Definition at line 352 of file Generator_System.defs.hh.
bool operator== | ( | const Polyhedron & | x, | |
const Polyhedron & | y | |||
) | [friend] |
std::ostream & operator<< | ( | std::ostream & | s, | |
const 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 1021 of file Generator_System.cc.
References begin(), and end().
01021 { 01022 Generator_System::const_iterator i = gs.begin(); 01023 const Generator_System::const_iterator gs_end = gs.end(); 01024 if (i == gs_end) 01025 return s << "false"; 01026 while (true) { 01027 s << *i++; 01028 if (i == gs_end) 01029 return s; 01030 s << ", "; 01031 } 01032 }
void swap | ( | Parma_Polyhedra_Library::Generator_System & | x, | |
Parma_Polyhedra_Library::Generator_System & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 205 of file Generator_System.inlines.hh.
References swap().
00206 { 00207 x.swap(y); 00208 }