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


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.

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

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

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

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.

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


Friends And Related Function Documentation

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.

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 }

Specializes std::swap.

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

References swap().

00206                                                  {
00207   x.swap(y);
00208 }


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

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