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

A system of generators. More...

#include <Generator_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Generator_System:

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

Collaboration graph
[legend]

List of all members.

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_Systemoperator= (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.
bool empty () const
 Returns true if and only if *this has no generators.
const_iterator begin () const
 Returns the const_iterator pointing to the first generator, if *this is not empty; otherwise, returns the past-the-end const_iterator.
const_iterator end () const
 Returns the past-the-end const_iterator.
bool OK () const
 Checks if all the invariants are satisfied.
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
void print () const
 Prints *this to std::cerr using operator<<.
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
void swap (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 void initialize ()
 Initializes the class.
static void finalize ()
 Finalizes the class.
static const Generator_Systemzero_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 $\epsilon$ dimension, if 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.
Generatoroperator[] (dimension_type k)
 Returns the k- th generator of the system.
const Generatoroperator[] (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 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.

Static Private Attributes

static const Generator_Systemzero_dim_univ_p = 0
 Holds (between class initialization and finalization) a pointer to the singleton system containing only Generator::zero_dim_point().

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


Detailed Description

A system of generators.

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

In all the examples it is assumed that variables x and y are defined as follows:
  Variable x(0);
  Variable y(1);
Example 1
The following code defines the line having the same direction as the $x$ axis (i.e., the first Cartesian axis) in $\Rset^2$:
  Generator_System gs;
  gs.insert(line(x + 0*y));
As said above, this system of generators corresponds to an empty polyhedron, because the line has no supporting point. To define a system of generators that does correspond to the $x$ axis, we can add the following code which inserts the origin of the space as a point:
  gs.insert(point(0*x + 0*y));
Since space dimensions are automatically adjusted, the following code obtains the same effect:
  gs.insert(point(0*x));
In contrast, if we had added the following code, we would have defined a line parallel to the $x$ axis through the point $(0, 1)^\transpose \in \Rset^2$.
  gs.insert(point(0*x + 1*y));
Example 2
The following code builds a ray having the same direction as the positive part of the $x$ axis in $\Rset^2$:
  Generator_System gs;
  gs.insert(ray(x + 0*y));
To define a system of generators indeed corresponding to the set

\[ \bigl\{\, (x, 0)^\transpose \in \Rset^2 \bigm| x \geq 0 \,\bigr\}, \]

one just has to add the origin:

  gs.insert(point(0*x + 0*y));
Example 3
The following code builds a system of generators having four points and corresponding to a square in $\Rset^2$ (the same as Example 1 for the system of constraints):
  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));
Example 4
By using closure points, we can define the kernel (i.e., the largest open set included in a given set) of the square defined in the previous example. Note that a supporting point is needed and, for that purpose, any inner point could be considered.
  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));
Example 5
The following code builds a system of generators having two points and a ray, corresponding to a half-strip in $\Rset^2$ (the same as Example 2 for the system of constraints):
  Generator_System gs;
  gs.insert(point(0*x + 0*y));
  gs.insert(point(0*x + 1*y));
  gs.insert(ray(x - y));
Note:
After inserting a multiset of generators in a generator system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent generator system will be available, where original generators may have been reordered, removed (if they are duplicate or redundant), etc.

Definition at line 183 of file Generator_System.defs.hh.


Constructor & Destructor Documentation

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.

Referenced by initialize().

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]

Destructor.

Definition at line 59 of file Generator_System.inlines.hh.

00059                                     {
00060 }

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 $\epsilon$ 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 }


Member Function Documentation

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

Referenced by Parma_Polyhedra_Library::Grid_Generator_System::operator=().

00063                                                      {
00064   Linear_System::operator=(y);
00065   return *this;
00066 }

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

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

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

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 282 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(), and Parma_Polyhedra_Library::Polyhedron::unconstrain().

00282                                               {
00283   // We are sure that the matrix has no pending rows
00284   // and that the new row is not a pending generator.
00285   assert(num_pending_rows() == 0);
00286   if (topology() == g.topology())
00287     Linear_System::insert(g);
00288   else
00289     // `*this' and `g' have different topologies.
00290     if (is_necessarily_closed()) {
00291       // Padding the matrix with the column
00292       // corresponding to the epsilon coefficients:
00293       // all points must have epsilon coordinate equal to 1
00294       // (i.e., the epsilon coefficient is equal to the divisor);
00295       // rays and lines must have epsilon coefficient equal to 0.
00296       // Note: normalization is preserved.
00297       const dimension_type eps_index = num_columns();
00298       add_zero_columns(1);
00299       Generator_System& gs = *this;
00300       for (dimension_type i = num_rows(); i-- > 0; ) {
00301         Generator& gen = gs[i];
00302         if (!gen.is_line_or_ray())
00303           gen[eps_index] = gen[0];
00304       }
00305       set_not_necessarily_closed();
00306       // Inserting the new generator.
00307       Linear_System::insert(g);
00308     }
00309     else {
00310       // The generator system is NOT necessarily closed:
00311       // copy the generator, adding the missing dimensions
00312       // and the epsilon coefficient.
00313       const dimension_type new_size = 2 + std::max(g.space_dimension(),
00314                                                    space_dimension());
00315       Generator tmp_g(g, new_size);
00316       // If it was a point, set the epsilon coordinate to 1
00317       // (i.e., set the coefficient equal to the divisor).
00318       // Note: normalization is preserved.
00319       if (!tmp_g.is_line_or_ray())
00320         tmp_g[new_size - 1] = tmp_g[0];
00321       tmp_g.set_not_necessarily_closed();
00322       // Inserting the new generator.
00323       Linear_System::insert(tmp_g);
00324     }
00325   assert(OK());
00326 }

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

Initializes the class.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 1007 of file Generator_System.cc.

References Generator_System(), Parma_Polyhedra_Library::Generator::zero_dim_point(), and zero_dim_univ_p.

01007                                 {
01008   assert(zero_dim_univ_p == 0);
01009   zero_dim_univ_p
01010     = new Generator_System(Generator::zero_dim_point());
01011 }

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

Finalizes the class.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 1014 of file Generator_System.cc.

References zero_dim_univ_p.

01014                               {
01015   assert(zero_dim_univ_p != 0);
01016   delete zero_dim_univ_p;
01017   zero_dim_univ_p = 0;
01018 }

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

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

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 177 of file Generator_System.inlines.hh.

References zero_dim_univ_p.

00177                                 {
00178   assert(zero_dim_univ_p != 0);
00179   return *zero_dim_univ_p;
00180 }

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

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

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 158 of file Generator_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::has_no_rows().

00158                               {
00159   return Linear_System::has_no_rows();
00160 }

Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::begin (  )  const [inline]

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

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

01021                               {
01022   // A Generator_System must be a valid Linear_System; do not check for
01023   // strong normalization, since this will be done when
01024   // checking each individual generator.
01025   if (!Linear_System::OK(false))
01026     return false;
01027 
01028   // Checking each generator in the system.
01029   const Generator_System& x = *this;
01030   for (dimension_type i = num_rows(); i-- > 0; )
01031     if (!x[i].OK())
01032       return false;
01033 
01034   // All checks passed.
01035   return true;
01036 }

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

00833                                                    {
00834   const Generator_System& x = *this;
00835   const dimension_type x_num_rows = x.num_rows();
00836   const dimension_type x_num_columns = x.num_columns();
00837   s << "topology " << (is_necessarily_closed()
00838                        ? "NECESSARILY_CLOSED"
00839                        : "NOT_NECESSARILY_CLOSED")
00840     << "\n"
00841     << x_num_rows << " x " << x_num_columns << ' '
00842     << (x.is_sorted() ? "(sorted)" : "(not_sorted)")
00843     << "\n"
00844     << "index_first_pending " << x.first_pending_row()
00845     << "\n";
00846   for (dimension_type i = 0; i < x_num_rows; ++i) {
00847     const Generator& g = x[i];
00848     for (dimension_type j = 0; j < x_num_columns; ++j)
00849       s << g[j] << ' ';
00850     switch (g.type()) {
00851     case Generator::LINE:
00852       s << "L";
00853       break;
00854     case Generator::RAY:
00855       s << "R";
00856       break;
00857     case Generator::POINT:
00858       s << "P";
00859       break;
00860     case Generator::CLOSURE_POINT:
00861       s << "C";
00862       break;
00863     }
00864     s << "\n";
00865   }
00866 }

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(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.

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

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 871 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().

00871                                              {
00872   std::string str;
00873   if (!(s >> str) || str != "topology")
00874     return false;
00875   if (!(s >> str))
00876     return false;
00877   if (str == "NECESSARILY_CLOSED")
00878     set_necessarily_closed();
00879   else {
00880     if (str != "NOT_NECESSARILY_CLOSED")
00881       return false;
00882     set_not_necessarily_closed();
00883   }
00884 
00885   dimension_type nrows;
00886   dimension_type ncols;
00887   if (!(s >> nrows))
00888     return false;
00889   if (!(s >> str))
00890     return false;
00891   if (!(s >> ncols))
00892       return false;
00893   resize_no_copy(nrows, ncols);
00894 
00895   if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00896     return false;
00897   set_sorted(str == "(sorted)");
00898   dimension_type index;
00899   if (!(s >> str) || str != "index_first_pending")
00900     return false;
00901   if (!(s >> index))
00902     return false;
00903   set_index_first_pending_row(index);
00904 
00905   Generator_System& x = *this;
00906   for (dimension_type i = 0; i < x.num_rows(); ++i) {
00907     for (dimension_type j = 0; j < x.num_columns(); ++j)
00908       if (!(s >> x[i][j]))
00909         return false;
00910 
00911     if (!(s >> str))
00912       return false;
00913     if (str == "L")
00914       x[i].set_is_line();
00915     else
00916       x[i].set_is_ray_or_point();
00917 
00918     // Checking for equality of actual and declared types.
00919     switch (x[i].type()) {
00920     case Generator::LINE:
00921       if (str == "L")
00922         continue;
00923       break;
00924     case Generator::RAY:
00925       if (str == "R")
00926         continue;
00927       break;
00928     case Generator::POINT:
00929       if (str == "P")
00930         continue;
00931       break;
00932     case Generator::CLOSURE_POINT:
00933       if (str == "C")
00934         continue;
00935       break;
00936     }
00937     // Reaching this point means that the input was illegal.
00938     return false;
00939   }
00940 
00941   // Check invariants.
00942   assert(OK());
00943   return true;
00944 }

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 193 of file Generator_System.inlines.hh.

References Parma_Polyhedra_Library::total_memory_in_bytes().

00193                                               {
00194   return Linear_System::total_memory_in_bytes();
00195 }

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 188 of file Generator_System.inlines.hh.

References Parma_Polyhedra_Library::external_memory_in_bytes().

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

00188                                                  {
00189   return Linear_System::external_memory_in_bytes();
00190 }

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

Swaps *this with y.

Definition at line 183 of file Generator_System.inlines.hh.

References Parma_Polyhedra_Library::swap().

Referenced by swap().

00183                                           {
00184   Linear_System::swap(y);
00185 }

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::Matrix::has_no_rows(), 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::swap(), 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 generator systems first.
00048   if (has_no_rows()) {
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 the generator systen is not empty.
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     }
00176   // We successfully adjusted dimensions and topology.
00177   assert(OK());
00178   return true;
00179 }

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

00213                                               {
00214   assert(!is_necessarily_closed());
00215   // NOTE: we always add (pending) rows at the end of the generator system.
00216   // Updating `index_first_pending', if needed, is done by the caller.
00217   Generator_System& gs = *this;
00218   const dimension_type n_rows = gs.num_rows();
00219   const dimension_type eps_index = gs.num_columns() - 1;
00220   for (dimension_type i = 0; i < n_rows; i++) {
00221     const Generator& g = gs[i];
00222     if (!g.is_line_or_ray() && g[eps_index] == 0) {
00223       // `g' is a closure point: adding the point.
00224       // Note: normalization is preserved.
00225       Generator p = g;
00226       p[eps_index] = p[0];
00227       gs.add_pending_row(p);
00228     }
00229   }
00230   assert(OK());
00231 }

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

00246                                       {
00247   const Generator_System& gs = *this;
00248   // Avoiding the repeated tests on topology.
00249   if (is_necessarily_closed())
00250     for (dimension_type i = num_rows(); i-- > 0; ) {
00251       if (!gs[i].is_line_or_ray())
00252         return true;
00253     }
00254   else {
00255     // !is_necessarily_closed()
00256     const dimension_type eps_index = gs.num_columns() - 1;
00257     for (dimension_type i = num_rows(); i-- > 0; )
00258     if (gs[i][eps_index] != 0)
00259       return true;
00260   }
00261   return false;
00262 }

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

00186                                                       {
00187   assert(!is_necessarily_closed());
00188   // NOTE: we always add (pending) rows at the end of the generator system.
00189   // Updating `index_first_pending', if needed, is done by the caller.
00190   Generator_System& gs = *this;
00191   const dimension_type n_rows = gs.num_rows();
00192   const dimension_type eps_index = gs.num_columns() - 1;
00193   for (dimension_type i = n_rows; i-- > 0; ) {
00194     const Generator& g = gs[i];
00195     if (g[eps_index] > 0) {
00196       // `g' is a point: adding the closure point.
00197       Generator cp = g;
00198       cp[eps_index] = 0;
00199       // Enforcing normalization.
00200       cp.normalize();
00201       gs.add_pending_row(cp);
00202     }
00203   }
00204   assert(OK());
00205 }

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

00234                                               {
00235   if (is_necessarily_closed())
00236     return false;
00237   // Adopt the point of view of the user.
00238   for (Generator_System::const_iterator i = begin(),
00239          this_end = end(); i != this_end; ++i)
00240     if (i->is_closure_point())
00241       return true;
00242   return false;
00243 }

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

00416                                                             {
00417   // Note: this method is not public and it is the responsibility
00418   // of the caller to actually test for dimension compatibility.
00419   // We simply assert it.
00420   assert(space_dimension() >= c.space_dimension());
00421   // Number of generators: the case of an empty polyhedron
00422   // has already been filtered out by the caller.
00423   const dimension_type n_rows = num_rows();
00424   assert(n_rows > 0);
00425   const Generator_System& gs = *this;
00426 
00427   // `result' will keep the relation holding between the generators
00428   // we have seen so far and the constraint `c'.
00429   Poly_Con_Relation result = Poly_Con_Relation::saturates();
00430 
00431   switch (c.type()) {
00432 
00433   case Constraint::EQUALITY:
00434     {
00435       // The hyperplane defined by the equality `c' is included
00436       // in the set of points satisfying `c' (it is the same set!).
00437       result = result && Poly_Con_Relation::is_included();
00438       // The following integer variable will hold the scalar product sign
00439       // of either the first point or the first non-saturating ray we find.
00440       // If it is equal to 2, then it means that we haven't found such
00441       // a generator yet.
00442       int first_point_or_nonsaturating_ray_sign = 2;
00443 
00444       for (dimension_type i = n_rows; i-- > 0; ) {
00445         const Generator& g = gs[i];
00446         const int sp_sign = Scalar_Products::sign(c, g);
00447         // Checking whether the generator saturates the equality.
00448         // If that is the case, then we have to do something only if
00449         // the generator is a point.
00450         if (sp_sign == 0) {
00451           if (g.is_point()) {
00452             if (first_point_or_nonsaturating_ray_sign == 2)
00453               // It is the first time that we find a point and
00454               // we have not found a non-saturating ray yet.
00455               first_point_or_nonsaturating_ray_sign = 0;
00456             else
00457               // We already found a point or a non-saturating ray.
00458               if (first_point_or_nonsaturating_ray_sign != 0)
00459                 return Poly_Con_Relation::strictly_intersects();
00460           }
00461         }
00462         else
00463           // Here we know that sp_sign != 0.
00464           switch (g.type()) {
00465 
00466           case Generator::LINE:
00467             // If a line does not saturate `c', then there is a strict
00468             // intersection between the points satisfying `c'
00469             // and the points generated by `gs'.
00470             return Poly_Con_Relation::strictly_intersects();
00471 
00472           case Generator::RAY:
00473             if (first_point_or_nonsaturating_ray_sign == 2) {
00474               // It is the first time that we have a non-saturating ray
00475               // and we have not found any point yet.
00476               first_point_or_nonsaturating_ray_sign = sp_sign;
00477               result = Poly_Con_Relation::is_disjoint();
00478             }
00479             else
00480               // We already found a point or a non-saturating ray.
00481               if (sp_sign != first_point_or_nonsaturating_ray_sign)
00482                 return Poly_Con_Relation::strictly_intersects();
00483             break;
00484 
00485           case Generator::POINT:
00486           case Generator::CLOSURE_POINT:
00487             // NOTE: a non-saturating closure point is treated as
00488             // a normal point.
00489             if (first_point_or_nonsaturating_ray_sign == 2) {
00490               // It is the first time that we find a point and
00491               // we have not found a non-saturating ray yet.
00492               first_point_or_nonsaturating_ray_sign = sp_sign;
00493               result = Poly_Con_Relation::is_disjoint();
00494             }
00495             else
00496               // We already found a point or a non-saturating ray.
00497               if (sp_sign != first_point_or_nonsaturating_ray_sign)
00498                 return Poly_Con_Relation::strictly_intersects();
00499             break;
00500           }
00501       }
00502     }
00503     break;
00504 
00505   case Constraint::NONSTRICT_INEQUALITY:
00506     {
00507       // The hyperplane implicitly defined by the non-strict inequality `c'
00508       // is included in the set of points satisfying `c'.
00509       result = result && Poly_Con_Relation::is_included();
00510       // The following Boolean variable will be set to `false'
00511       // as soon as either we find (any) point or we find a
00512       // non-saturating ray.
00513       bool first_point_or_nonsaturating_ray = true;
00514 
00515       for (dimension_type i = n_rows; i-- > 0; ) {
00516         const Generator& g = gs[i];
00517         const int sp_sign = Scalar_Products::sign(c, g);
00518         // Checking whether the generator saturates the non-strict
00519         // inequality. If that is the case, then we have to do something
00520         // only if the generator is a point.
00521         if (sp_sign == 0) {
00522           if (g.is_point()) {
00523             if (first_point_or_nonsaturating_ray)
00524               // It is the first time that we have a point and
00525               // we have not found a non-saturating ray yet.
00526               first_point_or_nonsaturating_ray = false;
00527             else
00528               // We already found a point or a non-saturating ray before.
00529               if (result == Poly_Con_Relation::is_disjoint())
00530                 // Since g saturates c, we have a strict intersection if
00531                 // none of the generators seen so far are included in `c'.
00532                 return Poly_Con_Relation::strictly_intersects();
00533           }
00534         }
00535         else
00536           // Here we know that sp_sign != 0.
00537           switch (g.type()) {
00538 
00539           case Generator::LINE:
00540             // If a line does not saturate `c', then there is a strict
00541             // intersection between the points satisfying `c' and
00542             // the points generated by `gs'.
00543             return Poly_Con_Relation::strictly_intersects();
00544 
00545           case Generator::RAY:
00546             if (first_point_or_nonsaturating_ray) {
00547               // It is the first time that we have a non-saturating ray
00548               // and we have not found any point yet.
00549               first_point_or_nonsaturating_ray = false;
00550               result = (sp_sign > 0)
00551                 ? Poly_Con_Relation::is_included()
00552                 : Poly_Con_Relation::is_disjoint();
00553             }
00554             else {
00555               // We already found a point or a non-saturating ray.
00556               if ((sp_sign > 0
00557                    && result == Poly_Con_Relation::is_disjoint())
00558                   || (sp_sign < 0
00559                       && result.implies(Poly_Con_Relation::is_included())))
00560                 // We have a strict intersection if either:
00561                 // - `g' satisfies `c' but none of the generators seen
00562                 //    so far are included in `c'; or
00563                 // - `g' does not satisfy `c' and all the generators
00564                 //    seen so far are included in `c'.
00565                 return Poly_Con_Relation::strictly_intersects();
00566               if (sp_sign > 0)
00567                 // Here all the generators seen so far either saturate
00568                 // or are included in `c'.
00569                 // Since `g' does not saturate `c' ...
00570                 result = Poly_Con_Relation::is_included();
00571             }
00572             break;
00573 
00574           case Generator::POINT:
00575           case Generator::CLOSURE_POINT:
00576             // NOTE: a non-saturating closure point is treated as
00577             // a normal point.
00578             if (first_point_or_nonsaturating_ray) {
00579               // It is the first time that we have a point and
00580               // we have not found a non-saturating ray yet.
00581               // - If point `g' saturates `c', then all the generators
00582               //   seen so far saturate `c'.
00583               // - If point `g' is included (but does not saturate) `c',
00584               //   then all the generators seen so far are included in `c'.
00585               // - If point `g' does not satisfy `c', then all the
00586               //   generators seen so far are disjoint from `c'.
00587               first_point_or_nonsaturating_ray = false;
00588               if (sp_sign > 0)
00589                 result = Poly_Con_Relation::is_included();
00590               else if (sp_sign < 0)
00591                 result = Poly_Con_Relation::is_disjoint();
00592             }
00593             else {
00594               // We already found a point or a non-saturating ray before.
00595               if ((sp_sign > 0
00596                    && result == Poly_Con_Relation::is_disjoint())
00597                   || (sp_sign < 0
00598                       && result.implies(Poly_Con_Relation::is_included())))
00599                 // We have a strict intersection if either:
00600                 // - `g' satisfies or saturates `c' but none of the
00601                 //    generators seen so far are included in `c'; or
00602                 // - `g' does not satisfy `c' and all the generators
00603                 //    seen so far are included in `c'.
00604                 return Poly_Con_Relation::strictly_intersects();
00605               if (sp_sign > 0)
00606                 // Here all the generators seen so far either saturate
00607                 // or are included in `c'.
00608                 // Since `g' does not saturate `c' ...
00609                 result = Poly_Con_Relation::is_included();
00610             }
00611             break;
00612           }
00613       }
00614     }
00615     break;
00616 
00617   case Constraint::STRICT_INEQUALITY:
00618     {
00619       // The hyperplane implicitly defined by the strict inequality `c'
00620       // is disjoint from the set of points satisfying `c'.
00621       result = result && Poly_Con_Relation::is_disjoint();
00622       // The following Boolean variable will be set to `false'
00623       // as soon as either we find (any) point or we find a
00624       // non-saturating ray.
00625       bool first_point_or_nonsaturating_ray = true;
00626       for (dimension_type i = n_rows; i-- > 0; ) {
00627         const Generator& g = gs[i];
00628         // Using the reduced scalar product operator to avoid
00629         // both topology and num_columns mismatches.
00630         const int sp_sign = Scalar_Products::reduced_sign(c, g);
00631         // Checking whether the generator saturates the strict inequality.
00632         // If that is the case, then we have to do something
00633         // only if the generator is a point.
00634         if (sp_sign == 0) {
00635           if (g.is_point()) {
00636             if (first_point_or_nonsaturating_ray)
00637               // It is the first time that we have a point and
00638               // we have not found a non-saturating ray yet.
00639               first_point_or_nonsaturating_ray = false;
00640             else
00641               // We already found a point or a non-saturating ray before.
00642               if (result == Poly_Con_Relation::is_included())
00643                 return Poly_Con_Relation::strictly_intersects();
00644           }
00645         }
00646         else
00647           // Here we know that sp_sign != 0.
00648           switch (g.type()) {
00649 
00650           case Generator::LINE:
00651             // If a line does not saturate `c', then there is a strict
00652             // intersection between the points satisfying `c' and the points
00653             // generated by `gs'.
00654             return Poly_Con_Relation::strictly_intersects();
00655 
00656           case Generator::RAY:
00657             if (first_point_or_nonsaturating_ray) {
00658               // It is the first time that we have a non-saturating ray
00659               // and we have not found any point yet.
00660               first_point_or_nonsaturating_ray = false;
00661               result = (sp_sign > 0)
00662                 ? Poly_Con_Relation::is_included()
00663                 : Poly_Con_Relation::is_disjoint();
00664             }
00665             else {
00666               // We already found a point or a non-saturating ray before.
00667               if ((sp_sign > 0
00668                    && result.implies(Poly_Con_Relation::is_disjoint()))
00669                   ||
00670                   (sp_sign <= 0
00671                    && result == Poly_Con_Relation::is_included()))
00672                 return Poly_Con_Relation::strictly_intersects();
00673               if (sp_sign < 0)
00674                 // Here all the generators seen so far either saturate
00675                 // or are disjoint from `c'.
00676                 // Since `g' does not saturate `c' ...
00677                 result = Poly_Con_Relation::is_disjoint();
00678             }
00679             break;
00680 
00681           case Generator::POINT:
00682           case Generator::CLOSURE_POINT:
00683             if (first_point_or_nonsaturating_ray) {
00684               // It is the first time that we have a point and
00685               // we have not found a non-saturating ray yet.
00686               // - If point `g' saturates `c', then all the generators
00687               //   seen so far saturate `c'.
00688               // - If point `g' is included in (but does not saturate) `c',
00689               //   then all the generators seen so far are included in `c'.
00690               // - If point `g' strictly violates `c', then all the
00691               //   generators seen so far are disjoint from `c'.
00692               first_point_or_nonsaturating_ray = false;
00693               if (sp_sign > 0)
00694                 result = Poly_Con_Relation::is_included();
00695               else if (sp_sign < 0)
00696                 result = Poly_Con_Relation::is_disjoint();
00697             }
00698             else {
00699               // We already found a point or a non-saturating ray before.
00700               if ((sp_sign > 0
00701                    && result.implies(Poly_Con_Relation::is_disjoint()))
00702                   ||
00703                   (sp_sign <= 0
00704                    && result == Poly_Con_Relation::is_included()))
00705                 return Poly_Con_Relation::strictly_intersects();
00706               if (sp_sign < 0)
00707                 // Here all the generators seen so far either saturate
00708                 // or are disjoint from `c'.
00709                 // Since `g' does not saturate `c' ...
00710                 result = Poly_Con_Relation::is_disjoint();
00711             }
00712             break;
00713           }
00714       }
00715     }
00716     break;
00717   }
00718   // We have seen all generators.
00719   return result;
00720 }

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 724 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(), Parma_Polyhedra_Library::Polyhedron::select_CH78_constraints(), and Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().

00724                                                                           {
00725   assert(c.space_dimension() <= space_dimension());
00726 
00727   // Setting `sps' to the appropriate scalar product sign operator.
00728   // This also avoids problems when having _legal_ topology mismatches
00729   // (which could also cause a mismatch in the number of columns).
00730   Topology_Adjusted_Scalar_Product_Sign sps(c);
00731 
00732   const Generator_System& gs = *this;
00733   switch (c.type()) {
00734   case Constraint::EQUALITY:
00735     // Equalities must be saturated by all generators.
00736     for (dimension_type i = gs.num_rows(); i-- > 0; )
00737       if (sps(c, gs[i]) != 0)
00738         return false;
00739     break;
00740   case Constraint::NONSTRICT_INEQUALITY:
00741     // Non-strict inequalities must be saturated by lines and
00742     // satisfied by all the other generators.
00743     for (dimension_type i = gs.num_rows(); i-- > 0; ) {
00744       const Generator& g = gs[i];
00745       const int sp_sign = sps(c, g);
00746       if (g.is_line()) {
00747         if (sp_sign != 0)
00748           return false;
00749       }
00750       else
00751         // `g' is a ray, point or closure point.
00752         if (sp_sign < 0)
00753           return false;
00754     }
00755     break;
00756   case Constraint::STRICT_INEQUALITY:
00757     // Strict inequalities must be saturated by lines,
00758     // satisfied by all generators, and must not be saturated by points.
00759     for (dimension_type i = gs.num_rows(); i-- > 0; ) {
00760       const Generator& g = gs[i];
00761       const int sp_sign = sps(c, g);
00762       switch (g.type()) {
00763       case Generator::POINT:
00764         if (sp_sign <= 0)
00765           return false;
00766         break;
00767       case Generator::LINE:
00768         if (sp_sign != 0)
00769           return false;
00770         break;
00771       default:
00772         // `g' is a ray or closure point.
00773         if (sp_sign < 0)
00774           return false;
00775         break;
00776       }
00777     }
00778     break;
00779   }
00780   // If we reach this point, `c' is satisfied by all generators.
00781   return true;
00782 }

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.

Parameters:
v Index of the column to which the affine transformation is assigned;
expr The numerator of the affine transformation: $\sum_{i = 0}^{n - 1} a_i x_i + b$;
denominator The denominator of the affine transformation.
We want to allow affine transformations (see the Introduction) having any rational coefficients. Since the coefficients of the constraints are integers we must also provide an integer 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:

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

expr is a constant parameter and unaltered by this computation.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 787 of file Generator_System.cc.

References 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(), Parma_Polyhedra_Library::swap(), and TEMP_INTEGER.

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

00789                                                               {
00790   Generator_System& x = *this;
00791   // `v' is the index of a column corresponding to
00792   // a "user" variable (i.e., it cannot be the inhomogeneous term,
00793   // nor the epsilon dimension of NNC polyhedra).
00794   assert(v > 0 && v <= x.space_dimension());
00795   assert(expr.space_dimension() <= x.space_dimension());
00796   assert(denominator > 0);
00797 
00798   const dimension_type n_columns = x.num_columns();
00799   const dimension_type n_rows = x.num_rows();
00800 
00801   // Compute the numerator of the affine transformation and assign it
00802   // to the column of `*this' indexed by `v'.
00803   TEMP_INTEGER(numerator);
00804   for (dimension_type i = n_rows; i-- > 0; ) {
00805     Generator& row = x[i];
00806     Scalar_Products::assign(numerator, expr, row);
00807     std::swap(numerator, row[v]);
00808   }
00809 
00810   if (denominator != 1) {
00811     // Since we want integer elements in the matrix,
00812     // we multiply by `denominator' all the columns of `*this'
00813     // having an index different from `v'.
00814     for (dimension_type i = n_rows; i-- > 0; ) {
00815       Generator& row = x[i];
00816       for (dimension_type j = n_columns; j-- > 0; )
00817         if (j != v)
00818           row[j] *= denominator;
00819     }
00820   }
00821 
00822   // If the mapping is not invertible we may have transformed
00823   // valid lines and rays into the origin of the space.
00824   const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0);
00825   if (not_invertible)
00826     x.remove_invalid_lines_and_rays();
00827 
00828   // Strong normalization also resets the sortedness flag.
00829   x.strong_normalize();
00830 }

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

00373                                      {
00374   // We are sure that this method is applied only to a matrix
00375   // that does not contain pending rows.
00376   assert(num_pending_rows() == 0);
00377   const Generator_System& gs = *this;
00378   dimension_type n = 0;
00379   // If the Linear_System happens to be sorted, take advantage of the fact
00380   // that lines are at the top of the system.
00381   if (is_sorted()) {
00382     dimension_type nrows = num_rows();
00383     for (dimension_type i = 0; i < nrows && gs[i].is_line(); ++i)
00384       ++n;
00385   }
00386   else
00387     for (dimension_type i = num_rows(); i-- > 0 ; )
00388       if (gs[i].is_line())
00389         ++n;
00390   return n;
00391 }

PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_rays (  )  const [private]

Returns the number of rays of the system.

Definition at line 394 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().

00394                                     {
00395   // We are sure that this method is applied only to a matrix
00396   // that does not contain pending rows.
00397   assert(num_pending_rows() == 0);
00398   const Generator_System& gs = *this;
00399   dimension_type n = 0;
00400   // If the Linear_System happens to be sorted, take advantage of the fact
00401   // that rays and points are at the bottom of the system and
00402   // rays have the inhomogeneous term equal to zero.
00403   if (is_sorted()) {
00404     for (dimension_type i = num_rows(); i != 0 && gs[--i].is_ray_or_point(); )
00405       if (gs[i].is_line_or_ray())
00406         ++n;
00407   }
00408   else
00409     for (dimension_type i = num_rows(); i-- > 0 ; )
00410       if (gs[i].is_ray())
00411         ++n;
00412   return n;
00413 }

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 947 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(), Parma_Polyhedra_Library::Linear_System::set_sorted(), and Parma_Polyhedra_Library::swap().

Referenced by affine_image(), Parma_Polyhedra_Library::Polyhedron::remove_higher_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::remove_space_dimensions(), and simplify().

00947                                                    {
00948   // The origin of the vector space cannot be a valid line/ray.
00949   // NOTE: the following swaps will mix generators without even trying
00950   // to preserve sortedness: as a matter of fact, it will almost always
00951   // be the case that the input generator system is NOT sorted.
00952   Generator_System& gs = *this;
00953   dimension_type n_rows = gs.num_rows();
00954   if (num_pending_rows() == 0) {
00955     for (dimension_type i = n_rows; i-- > 0; ) {
00956       Generator& g = gs[i];
00957       if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00958         // An invalid line/ray has been found.
00959         --n_rows;
00960         std::swap(g, gs[n_rows]);
00961         gs.set_sorted(false);
00962       }
00963     }
00964     set_index_first_pending_row(n_rows);
00965   }
00966   else {
00967     // If the matrix has some pending rows, we can not
00968     // swap the "normal" rows with the pending rows. So
00969     // we must put at the end of the "normal" rows
00970     // the invalid "normal" rows, put them at the end
00971     // of the matrix, find the invalid rows in the pending
00972     // part and then erase the invalid rows that now
00973     // are in the bottom part of the matrix.
00974     assert(num_pending_rows() > 0);
00975     dimension_type first_pending = first_pending_row();
00976     for (dimension_type i = first_pending; i-- > 0; ) {
00977       Generator& g = gs[i];
00978       if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00979         // An invalid line/ray has been found.
00980         --first_pending;
00981         std::swap(g, gs[first_pending]);
00982         gs.set_sorted(false);
00983       }
00984     }
00985     const dimension_type num_invalid_rows
00986       = first_pending_row() - first_pending;
00987     set_index_first_pending_row(first_pending);
00988     for (dimension_type i = 0; i < num_invalid_rows; ++i)
00989       std::swap(gs[n_rows - i], gs[first_pending + i]);
00990     n_rows -= num_invalid_rows;
00991     for (dimension_type i = n_rows; i-- > first_pending; ) {
00992       Generator& g = gs[i];
00993       if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00994         // An invalid line/ray has been found.
00995         --n_rows;
00996         std::swap(g, gs[n_rows]);
00997         gs.set_sorted(false);
00998       }
00999     }
01000   }
01001   gs.erase_to_end(n_rows);
01002 }

void Parma_Polyhedra_Library::Generator_System::simplify (  )  [inline, private]

Applies Gaussian 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 198 of file Generator_System.inlines.hh.

References remove_invalid_lines_and_rays(), and Parma_Polyhedra_Library::Linear_System::simplify().

00198                            {
00199   Linear_System::simplify();
00200   remove_invalid_lines_and_rays();
00201 }

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 329 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(), and Parma_Polyhedra_Library::Polyhedron::unconstrain().

00329                                                       {
00330   if (topology() == g.topology())
00331     Linear_System::insert_pending(g);
00332   else
00333     // `*this' and `g' have different topologies.
00334     if (is_necessarily_closed()) {
00335       // Padding the matrix with the column
00336       // corresponding to the epsilon coefficients:
00337       // all points must have epsilon coordinate equal to 1
00338       // (i.e., the epsilon coefficient is equal to the divisor);
00339       // rays and lines must have epsilon coefficient equal to 0.
00340       // Note: normalization is preserved.
00341       const dimension_type eps_index = num_columns();
00342       add_zero_columns(1);
00343       Generator_System& gs = *this;
00344       for (dimension_type i = num_rows(); i-- > 0; ) {
00345         Generator& gen = gs[i];
00346         if (!gen.is_line_or_ray())
00347           gen[eps_index] = gen[0];
00348       }
00349       set_not_necessarily_closed();
00350       // Inserting the new generator.
00351       Linear_System::insert_pending(g);
00352     }
00353     else {
00354       // The generator system is NOT necessarily closed:
00355       // copy the generator, adding the missing dimensions
00356       // and the epsilon coefficient.
00357       const dimension_type new_size = 2 + std::max(g.space_dimension(),
00358                                                    space_dimension());
00359       Generator tmp_g(g, new_size);
00360       // If it was a point, set the epsilon coordinate to 1
00361       // (i.e., set the coefficient equal to the divisor).
00362       // Note: normalization is preserved.
00363       if (!tmp_g.is_line_or_ray())
00364         tmp_g[new_size - 1] = tmp_g[0];
00365       tmp_g.set_not_necessarily_closed();
00366       // Inserting the new generator.
00367       Linear_System::insert_pending(tmp_g);
00368     }
00369   assert(OK());
00370 }


Friends And Related Function Documentation

friend class const_iterator [friend]

Definition at line 364 of file Generator_System.defs.hh.

friend class Parma_Polyhedra_Library::Polyhedron [friend]

Definition at line 365 of file Generator_System.defs.hh.

Definition at line 366 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 1040 of file Generator_System.cc.

References begin(), and end().

01040                                                                      {
01041   Generator_System::const_iterator i = gs.begin();
01042   const Generator_System::const_iterator gs_end = gs.end();
01043   if (i == gs_end)
01044     return s << "false";
01045   while (true) {
01046     s << *i++;
01047     if (i == gs_end)
01048       return s;
01049     s << ", ";
01050   }
01051 }

Specializes std::swap.

Definition at line 210 of file Generator_System.inlines.hh.

References swap().

00211                                                  {
00212   x.swap(y);
00213 }


Member Data Documentation

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

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 362 of file Generator_System.defs.hh.

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


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

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