A system of generators. More...

#include <Generator_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Generator_System:

Collaboration diagram for Parma_Polyhedra_Library::Generator_System:

Classes
class	const_iterator
	An iterator over a system of generators. More...
Public Member Functions
	Generator_System ()
	Default constructor: builds an empty system of generators.
	Generator_System (const Generator &g)
	Builds the singleton system containing only generator `g`.
	Generator_System (const Generator_System &gs)
	Ordinary copy constructor.
	~Generator_System ()
	Destructor.
Generator_System &	operator= (const Generator_System &y)
	Assignment operator.
dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`.
void	clear ()
	Removes all the generators from the generator system and sets its space dimension to 0.
void	insert (const Generator &g)
	Inserts in `*this` a copy of the generator `g`, increasing the number of space dimensions if needed.
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	m_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_System &	zero_dim_univ ()
	Returns the singleton system containing only Generator::zero_dim_point().
Private Member Functions
	Generator_System (Topology topol)
	Builds an empty system of generators having the specified topology.
	Generator_System (Topology topol, dimension_type n_rows, dimension_type n_columns)
	Builds a system of `n_rows` rays/points on a `n_columns` - 1 dimensional space (including the $\epsilon$ dimension, if `topol` is `NOT_NECESSARILY_CLOSED`).
bool	adjust_topology_and_space_dimension (Topology new_topology, dimension_type new_space_dim)
	Adjusts `this` so that it matches the `new_topology` and `new_space_dim` (adding or removing columns if needed). Returns `false` if and only if `topol` is equal to `NECESSARILY_CLOSED` and `this` contains closure points.
void	add_corresponding_points ()
	For each unmatched closure point in `*this`, adds the corresponding point.
bool	has_points () const
	Returns `true` if and only if `*this` contains one or more points.
void	add_corresponding_closure_points ()
	For each unmatched point in `*this`, adds the corresponding closure point.
bool	has_closure_points () const
	Returns `true` if and only if `*this` contains one or more closure points.
Generator &	operator[] (dimension_type k)
	Returns the `k-` th generator of the system.
const Generator &	operator[] (dimension_type k) const
	Returns a constant reference to the `k-` th generator of the system.
Parma_Polyhedra_Library::Poly_Con_Relation	relation_with (const Constraint &c) const
	Returns the relations holding between the generator system and the constraint `c`.
bool	satisfied_by_all_generators (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`.
bool	satisfied_by_all_generators_C (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`.
bool	satisfied_by_all_generators_NNC (const Constraint &c) const
	Returns `true` if all the generators satisfy `c`.
void	affine_image (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
	Assigns to a given variable an affine expression.
dimension_type	num_lines () const
	Returns the number of lines of the system.
dimension_type	num_rays () const
	Returns the number of rays of the system.
void	remove_invalid_lines_and_rays ()
	Removes all the invalid lines and rays.
void	simplify ()
	Applies Gaussian 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_System *	zero_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)
std::ostream &	operator<< (std::ostream &s, const Generator_System &gs)
	Output operator.
void	swap (Generator_System &x, Generator_System &y)
	Swaps `x` with `y`.
void	swap (Generator_System &x, Generator_System &y)

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

  : Linear_System(NECESSARILY_CLOSED) {
}

Parma_Polyhedra_Library::Generator_System::Generator_System ( const Generator & g )

inlineexplicit

Builds the singleton system containing only generator g.

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

References insert().

  : Linear_System(g.topology()) {
  Linear_System::insert(g);
}

Parma_Polyhedra_Library::Generator_System::Generator_System ( const Generator_System & gs )

inline

Ordinary copy constructor.

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

  : Linear_System(gs) {
}

Parma_Polyhedra_Library::Generator_System::~Generator_System ( )

inline

Destructor.

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

{
}

Parma_Polyhedra_Library::Generator_System::Generator_System ( Topology topol )

inlineexplicitprivate

Builds an empty system of generators having the specified topology.

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

  : Linear_System(topol) {
}

Parma_Polyhedra_Library::Generator_System::Generator_System	(	Topology	topol,
		dimension_type	n_rows,
		dimension_type	n_columns
	)

inlineprivate

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

  : Linear_System(topol, n_rows, n_columns) {
}

Member Function Documentation

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

References Parma_Polyhedra_Library::Linear_System::add_pending_row(), Parma_Polyhedra_Library::Dense_Row::normalize(), Parma_Polyhedra_Library::Dense_Matrix::num_columns(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), and PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                                      {
  PPL_ASSERT(!is_necessarily_closed());
  // NOTE: we always add (pending) rows at the end of the generator system.
  // Updating `index_first_pending', if needed, is done by the caller.
  Generator_System& gs = *this;
  const dimension_type n_rows = gs.num_rows();
  const dimension_type eps_index = gs.num_columns() - 1;
  for (dimension_type i = n_rows; i-- > 0; ) {
    const Generator& g = gs[i];
    if (g[eps_index] > 0) {
      // `g' is a point: adding the closure point.
      Generator cp = g;
      cp[eps_index] = 0;
      // Enforcing normalization.
      cp.normalize();
      gs.add_pending_row(cp);
    }
  }
  PPL_ASSERT(OK());
}

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 215 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::Dense_Matrix::num_columns(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), and PPL_ASSERT.

                                              {
  PPL_ASSERT(!is_necessarily_closed());
  // NOTE: we always add (pending) rows at the end of the generator system.
  // Updating `index_first_pending', if needed, is done by the caller.
  Generator_System& gs = *this;
  const dimension_type n_rows = gs.num_rows();
  const dimension_type eps_index = gs.num_columns() - 1;
  for (dimension_type i = 0; i < n_rows; i++) {
    const Generator& g = gs[i];
    if (!g.is_line_or_ray() && g[eps_index] == 0) {
      // `g' is a closure point: adding the point.
      // Note: normalization is preserved.
      Generator p = g;
      p[eps_index] = p[0];
      gs.add_pending_row(p);
    }
  }
  PPL_ASSERT(OK());
}

bool Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension	(	Topology	new_topology,
		dimension_type	new_space_dim
	)

private

Adjusts *this so that it matches the new_topology and new_space_dim (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.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::generators(), Parma_Polyhedra_Library::Grid_Generator_System::Grid_Generator_System(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                                                        {
  PPL_ASSERT(space_dimension() <= new_space_dim);

  const dimension_type old_space_dim = space_dimension();
  const Topology old_topology = topology();
  dimension_type cols_to_be_added = new_space_dim - old_space_dim;

  // Dealing with empty generator systems first.
  if (has_no_rows()) {
    if (num_columns() == 0)
      if (new_topology == NECESSARILY_CLOSED) {
        add_zero_columns(cols_to_be_added + 1);
        set_necessarily_closed();
      }
      else {
        add_zero_columns(cols_to_be_added + 2);
        set_not_necessarily_closed();
      }
    else
      // Here `num_columns() > 0'.
      if (old_topology != new_topology)
        if (new_topology == NECESSARILY_CLOSED) {
          switch (cols_to_be_added) {
          case 0:
            remove_trailing_columns(1);
            break;
          case 1:
            // Nothing to do.
            break;
          default:
            add_zero_columns(cols_to_be_added - 1);
          }
          set_necessarily_closed();
        }
        else {
          // Here old_topology == NECESSARILY_CLOSED
          //  and new_topology == NOT_NECESSARILY_CLOSED.
          add_zero_columns(cols_to_be_added + 1);
          set_not_necessarily_closed();
        }
      else
        // Here topologies agree.
        if (cols_to_be_added > 0)
          add_zero_columns(cols_to_be_added);
    PPL_ASSERT(OK());
    return true;
  }

  // Here the generator system is not empty.
  if (cols_to_be_added > 0)
    if (old_topology != new_topology)
      if (new_topology == NECESSARILY_CLOSED) {
        // A NOT_NECESSARILY_CLOSED generator system
        // can be converted to a NECESSARILY_CLOSED one
        // only if it does not contain closure points.
        // This check has to be performed under the user viewpoint.
        if (has_closure_points())
          return false;
        // For a correct implementation, we have to remove those
        // closure points that were matching a point (i.e., those
        // that are in the generator system, but are invisible to
        // the user).
        Generator_System& gs = *this;
        dimension_type num_closure_points = 0;
        dimension_type gs_end = gs.num_rows();
        for (dimension_type i = 0; i < gs_end; ) {
          // All the closure points seen so far have consecutive
          // indices starting from `i'.
          if (num_closure_points > 0) {
            // Let next generator have index `i'.
            using std::swap;
            swap(gs[i], gs[i+num_closure_points]);
          }
          if (gs[i].is_closure_point()) {
            ++num_closure_points;
            --gs_end;
          }
          else
            ++i;
        }
        // We may have identified some closure points.
        if (num_closure_points > 0) {
          PPL_ASSERT(num_closure_points == num_rows() - gs_end);
          remove_trailing_rows(num_closure_points);
        }
        // Remove the epsilon column, re-normalize and, after that,
        // add the missing dimensions. This ensures that
        // non-zero epsilon coefficients will be cleared.
        remove_trailing_columns(1);
        set_necessarily_closed();
        normalize();
        add_zero_columns(cols_to_be_added);
      }
      else {
        // A NECESSARILY_CLOSED generator system is converted to
        // a NOT_NECESSARILY_CLOSED one by adding a further column
        // and setting the epsilon coordinate of all points to 1.
        // Note: normalization is preserved.
        add_zero_columns(cols_to_be_added + 1);
        Generator_System& gs = *this;
        const dimension_type eps_index = new_space_dim + 1;
        for (dimension_type i = num_rows(); i-- > 0; )
          gs[i][eps_index] = gs[i][0];
        set_not_necessarily_closed();
      }
    else {
      // Topologies agree: first add the required zero columns ...
      add_zero_columns(cols_to_be_added);
      // ... and, if needed, move the epsilon coefficients
      // to the new last column.
      if (old_topology == NOT_NECESSARILY_CLOSED)
        swap_columns(old_space_dim + 1, new_space_dim + 1);
    }
  else
    // Here `cols_to_be_added == 0'.
    if (old_topology != new_topology) {
      if (new_topology == NECESSARILY_CLOSED) {
        // A NOT_NECESSARILY_CLOSED generator system
        // can be converted in to a NECESSARILY_CLOSED one
        // only if it does not contain closure points.
        if (has_closure_points())
          return false;
        // We just remove the column of the epsilon coefficients.
        remove_trailing_columns(1);
        set_necessarily_closed();
      }
      else {
        // Add the column of the epsilon coefficients
        // and set the epsilon coordinate of all points to 1.
        // Note: normalization is preserved.
        add_zero_columns(1);
        Generator_System& gs = *this;
        const dimension_type eps_index = new_space_dim + 1;
        for (dimension_type i = num_rows(); i-- > 0; )
          gs[i][eps_index] = gs[i][0];
        set_not_necessarily_closed();
      }
    }
  // We successfully adjusted dimensions and topology.
  PPL_ASSERT(OK());
  return true;
}

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 789 of file Generator_System.cc.

References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Dense_Matrix::num_columns(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), PPL_ASSERT, PPL_DIRTY_TEMP_COEFFICIENT, remove_invalid_lines_and_rays(), space_dimension(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), Parma_Polyhedra_Library::Linear_System::strong_normalize(), and Parma_Polyhedra_Library::swap().

                                                              {
  Generator_System& x = *this;
  // `v' is the index of a column corresponding to
  // a "user" variable (i.e., it cannot be the inhomogeneous term,
  // nor the epsilon dimension of NNC polyhedra).
  PPL_ASSERT(v > 0 && v <= x.space_dimension());
  PPL_ASSERT(expr.space_dimension() <= x.space_dimension());
  PPL_ASSERT(denominator > 0);

  const dimension_type n_columns = x.num_columns();
  const dimension_type n_rows = x.num_rows();

  // Compute the numerator of the affine transformation and assign it
  // to the column of `*this' indexed by `v'.
  PPL_DIRTY_TEMP_COEFFICIENT(numerator);
  for (dimension_type i = n_rows; i-- > 0; ) {
    Generator& row = x[i];
    Scalar_Products::assign(numerator, expr, row);
    using std::swap;
    swap(numerator, row[v]);
  }

  if (denominator != 1) {
    // Since we want integer elements in the matrix,
    // we multiply by `denominator' all the columns of `*this'
    // having an index different from `v'.
    for (dimension_type i = n_rows; i-- > 0; ) {
      Generator& row = x[i];
      for (dimension_type j = n_columns; j-- > 0; )
        if (j != v)
          row[j] *= denominator;
    }
  }

  // If the mapping is not invertible we may have transformed
  // valid lines and rays into the origin of the space.
  const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0);
  if (not_invertible)
    x.remove_invalid_lines_and_rays();

  // Strong normalization also resets the sortedness flag.
  x.strong_normalize();
}

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::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 836 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_sorted(), Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Dense_Matrix::num_columns(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, Parma_Polyhedra_Library::Generator::RAY, and Parma_Polyhedra_Library::Generator::type().

                                                   {
  const Generator_System& x = *this;
  const dimension_type x_num_rows = x.num_rows();
  const dimension_type x_num_columns = x.num_columns();
  s << "topology " << (is_necessarily_closed()
                       ? "NECESSARILY_CLOSED"
                       : "NOT_NECESSARILY_CLOSED")
    << "\n"
    << x_num_rows << " x " << x_num_columns << ' '
    << (x.is_sorted() ? "(sorted)" : "(not_sorted)")
    << "\n"
    << "index_first_pending " << x.first_pending_row()
    << "\n";
  for (dimension_type i = 0; i < x_num_rows; ++i) {
    const Generator& g = x[i];
    for (dimension_type j = 0; j < x_num_columns; ++j)
      s << g[j] << ' ';
    switch (g.type()) {
    case Generator::LINE:
      s << "L";
      break;
    case Generator::RAY:
      s << "R";
      break;
    case Generator::POINT:
      s << "P";
      break;
    case Generator::CLOSURE_POINT:
      s << "C";
      break;
    }
    s << "\n";
  }
}

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 874 of file Generator_System.cc.

References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Generator::LINE, Parma_Polyhedra_Library::Dense_Matrix::num_columns(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), Parma_Polyhedra_Library::Generator::POINT, PPL_ASSERT, and Parma_Polyhedra_Library::Generator::RAY.

                                             {
  std::string str;
  if (!(s >> str) || str != "topology")
    return false;
  if (!(s >> str))
    return false;
  if (str == "NECESSARILY_CLOSED")
    set_necessarily_closed();
  else {
    if (str != "NOT_NECESSARILY_CLOSED")
      return false;
    set_not_necessarily_closed();
  }

  dimension_type nrows;
  dimension_type ncols;
  if (!(s >> nrows))
    return false;
  if (!(s >> str) || str != "x")
    return false;
  if (!(s >> ncols))
      return false;
  resize_no_copy(nrows, ncols);

  if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
    return false;
  set_sorted(str == "(sorted)");
  dimension_type index;
  if (!(s >> str) || str != "index_first_pending")
    return false;
  if (!(s >> index))
    return false;
  set_index_first_pending_row(index);

  Generator_System& x = *this;
  for (dimension_type i = 0; i < x.num_rows(); ++i) {
    for (dimension_type j = 0; j < x.num_columns(); ++j)
      if (!(s >> x[i][j]))
        return false;

    if (!(s >> str))
      return false;
    if (str == "L")
      x[i].set_is_line();
    else if (str == "R" || str == "P" || str == "C")
      x[i].set_is_ray_or_point();
    else
      return false;

    // Checking for equality of actual and declared types.
    switch (x[i].type()) {
    case Generator::LINE:
      if (str == "L")
        continue;
      break;
    case Generator::RAY:
      if (str == "R")
        continue;
      break;
    case Generator::POINT:
      if (str == "P")
        continue;
      break;
    case Generator::CLOSURE_POINT:
      if (str == "C")
        continue;
      break;
    }
    // Reaching this point means that the input was illegal.
    return false;
  }

  // Check invariants.
  PPL_ASSERT(OK());
  return true;
}

Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::begin ( ) const

inline

Returns the const_iterator pointing to the first generator, if *this is not empty; otherwise, returns the past-the-end const_iterator.

Reimplemented from Parma_Polyhedra_Library::Dense_Matrix.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

References Parma_Polyhedra_Library::Dense_Matrix::begin(), and Parma_Polyhedra_Library::Linear_System::is_necessarily_closed().

                              {
  const_iterator i(Linear_System::begin(), *this);
  if (!is_necessarily_closed())
    i.skip_forward();
  return i;
}

void Parma_Polyhedra_Library::Generator_System::clear ( )

inline

Removes all the generators from the generator system and sets its space dimension to 0.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

                        {
  Linear_System::clear();
}

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

References Parma_Polyhedra_Library::Dense_Matrix::has_no_rows().

                              {
  return Linear_System::has_no_rows();
}

Generator_System::const_iterator Parma_Polyhedra_Library::Generator_System::end ( ) const

inline

Returns the past-the-end const_iterator.

Reimplemented from Parma_Polyhedra_Library::Dense_Matrix.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

References Parma_Polyhedra_Library::Dense_Matrix::end().

                            {
  const const_iterator i(Linear_System::end(), *this);
  return i;
}

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

                                                 {
  return Linear_System::external_memory_in_bytes();
}

void Parma_Polyhedra_Library::Generator_System::finalize ( )

static

Finalizes the class.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 1021 of file Generator_System.cc.

References PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::Init::~Init().

                              {
  PPL_ASSERT(zero_dim_univ_p != 0);
  delete zero_dim_univ_p;
  zero_dim_univ_p = 0;
}

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 236 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), and adjust_topology_and_space_dimension().

                                              {
  if (is_necessarily_closed())
    return false;
  // Adopt the point of view of the user.
  for (Generator_System::const_iterator i = begin(),
         this_end = end(); i != this_end; ++i)
    if (i->is_closure_point())
      return true;
  return false;
}

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 248 of file Generator_System.cc.

References Parma_Polyhedra_Library::Dense_Matrix::num_columns().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

                                      {
  const Generator_System& gs = *this;
  // Avoiding the repeated tests on topology.
  if (is_necessarily_closed())
    for (dimension_type i = num_rows(); i-- > 0; ) {
      if (!gs[i].is_line_or_ray())
        return true;
    }
  else {
    // !is_necessarily_closed()
    const dimension_type eps_index = gs.num_columns() - 1;
    for (dimension_type i = num_rows(); i-- > 0; )
    if (gs[i][eps_index] != 0)
      return true;
  }
  return false;
}

void Parma_Polyhedra_Library::Generator_System::initialize ( )

static

Initializes the class.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 1014 of file Generator_System.cc.

References PPL_ASSERT, and Parma_Polyhedra_Library::Generator::zero_dim_point().

                                {
  PPL_ASSERT(zero_dim_univ_p == 0);
  zero_dim_univ_p
    = new Generator_System(Generator::zero_dim_point());
}

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 284 of file Generator_System.cc.

References Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), PPL_ASSERT, Parma_Polyhedra_Library::Generator::space_dimension(), and Parma_Polyhedra_Library::Linear_Row::topology().

Referenced by Parma_Polyhedra_Library::Implementation::Termination::all_affine_ranking_functions_PR_original(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_evolving_rays(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_preimage(), Generator_System(), and Parma_Polyhedra_Library::Polyhedron::map_space_dimensions().

                                              {
  // We are sure that the matrix has no pending rows
  // and that the new row is not a pending generator.
  PPL_ASSERT(num_pending_rows() == 0);
  if (topology() == g.topology())
    Linear_System::insert(g);
  else
    // `*this' and `g' have different topologies.
    if (is_necessarily_closed()) {
      // Padding the matrix with the column
      // corresponding to the epsilon coefficients:
      // all points must have epsilon coordinate equal to 1
      // (i.e., the epsilon coefficient is equal to the divisor);
      // rays and lines must have epsilon coefficient equal to 0.
      // Note: normalization is preserved.
      const dimension_type eps_index = num_columns();
      add_zero_columns(1);
      Generator_System& gs = *this;
      for (dimension_type i = num_rows(); i-- > 0; ) {
        Generator& gen = gs[i];
        if (!gen.is_line_or_ray())
          gen[eps_index] = gen[0];
      }
      set_not_necessarily_closed();
      // Inserting the new generator.
      Linear_System::insert(g);
    }
    else {
      // The generator system is NOT necessarily closed:
      // copy the generator, adding the missing dimensions
      // and the epsilon coefficient.
      const dimension_type new_size = 2 + std::max(g.space_dimension(),
                                                   space_dimension());
      Generator tmp_g(g, new_size);
      // If it was a point, set the epsilon coordinate to 1
      // (i.e., set the coefficient equal to the divisor).
      // Note: normalization is preserved.
      if (!tmp_g.is_line_or_ray())
        tmp_g[new_size - 1] = tmp_g[0];
      tmp_g.set_not_necessarily_closed();
      // Inserting the new generator.
      Linear_System::insert(tmp_g);
    }
  PPL_ASSERT(OK());
}

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 331 of file Generator_System.cc.

References Parma_Polyhedra_Library::Linear_System::insert_pending(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), PPL_ASSERT, Parma_Polyhedra_Library::Generator::space_dimension(), and Parma_Polyhedra_Library::Linear_Row::topology().

                                                      {
  if (topology() == g.topology())
    Linear_System::insert_pending(g);
  else
    // `*this' and `g' have different topologies.
    if (is_necessarily_closed()) {
      // Padding the matrix with the column
      // corresponding to the epsilon coefficients:
      // all points must have epsilon coordinate equal to 1
      // (i.e., the epsilon coefficient is equal to the divisor);
      // rays and lines must have epsilon coefficient equal to 0.
      // Note: normalization is preserved.
      const dimension_type eps_index = num_columns();
      add_zero_columns(1);
      Generator_System& gs = *this;
      for (dimension_type i = num_rows(); i-- > 0; ) {
        Generator& gen = gs[i];
        if (!gen.is_line_or_ray())
          gen[eps_index] = gen[0];
      }
      set_not_necessarily_closed();
      // Inserting the new generator.
      Linear_System::insert_pending(g);
    }
    else {
      // The generator system is NOT necessarily closed:
      // copy the generator, adding the missing dimensions
      // and the epsilon coefficient.
      const dimension_type new_size = 2 + std::max(g.space_dimension(),
                                                   space_dimension());
      Generator tmp_g(g, new_size);
      // If it was a point, set the epsilon coordinate to 1
      // (i.e., set the coefficient equal to the divisor).
      // Note: normalization is preserved.
      if (!tmp_g.is_line_or_ray())
        tmp_g[new_size - 1] = tmp_g[0];
      tmp_g.set_not_necessarily_closed();
      // Inserting the new generator.
      Linear_System::insert_pending(tmp_g);
    }
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Generator_System::m_swap ( Generator_System & y )

inline

Swaps *this with y.

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

Referenced by swap().

                                            {
  Linear_System::m_swap(y);
}

dimension_type Parma_Polyhedra_Library::Generator_System::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a Generator_System can handle.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

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

                                      {
  return Linear_System::max_space_dimension();
}

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 375 of file Generator_System.cc.

References PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::Polyhedron::quick_equivalence_test(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().

                                     {
  // We are sure that this method is applied only to a matrix
  // that does not contain pending rows.
  PPL_ASSERT(num_pending_rows() == 0);
  const Generator_System& gs = *this;
  dimension_type n = 0;
  // If the Linear_System happens to be sorted, take advantage of the fact
  // that lines are at the top of the system.
  if (is_sorted()) {
    dimension_type nrows = num_rows();
    for (dimension_type i = 0; i < nrows && gs[i].is_line(); ++i)
      ++n;
  }
  else
    for (dimension_type i = num_rows(); i-- > 0 ; )
      if (gs[i].is_line())
        ++n;
  return n;
}

PPL::dimension_type Parma_Polyhedra_Library::Generator_System::num_rays ( ) const

private

Returns the number of rays of the system.

Definition at line 396 of file Generator_System.cc.

References PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::Grid_Generator_System::num_parameters(), and Parma_Polyhedra_Library::Polyhedron::OK().

                                    {
  // We are sure that this method is applied only to a matrix
  // that does not contain pending rows.
  PPL_ASSERT(num_pending_rows() == 0);
  const Generator_System& gs = *this;
  dimension_type n = 0;
  // If the Linear_System happens to be sorted, take advantage of the fact
  // that rays and points are at the bottom of the system and
  // rays have the inhomogeneous term equal to zero.
  if (is_sorted()) {
    for (dimension_type i = num_rows(); i != 0 && gs[--i].is_ray_or_point(); )
      if (gs[i].is_line_or_ray())
        ++n;
  }
  else
    for (dimension_type i = num_rows(); i-- > 0 ; )
      if (gs[i].is_ray())
        ++n;
  return n;
}

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

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 1028 of file Generator_System.cc.

References Parma_Polyhedra_Library::Dense_Matrix::OK().

Referenced by adjust_topology_and_space_dimension().

                              {
  // A Generator_System must be a valid Linear_System; do not check for
  // strong normalization, since this will be done when
  // checking each individual generator.
  if (!Linear_System::OK(false))
    return false;

  // Checking each generator in the system.
  const Generator_System& x = *this;
  for (dimension_type i = num_rows(); i-- > 0; )
    if (!x[i].OK())
      return false;

  // All checks passed.
  return true;
}

Generator_System & Parma_Polyhedra_Library::Generator_System::operator= ( const Generator_System & y )

inline

Assignment operator.

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

                                                     {
  Linear_System::operator=(y);
  return *this;
}

Generator & Parma_Polyhedra_Library::Generator_System::operator[] ( dimension_type k )

inlineprivate

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

Referenced by operator[]().

                                                   {
  return static_cast<Generator&>(Linear_System::operator[](k));
}

const Generator & Parma_Polyhedra_Library::Generator_System::operator[] ( dimension_type k ) const

inlineprivate

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

References operator[]().

                                                         {
  return static_cast<const Generator&>(Linear_System::operator[](k));
}

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.

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 418 of file Generator_System.cc.

                                                            {
  // Note: this method is not public and it is the responsibility
  // of the caller to actually test for dimension compatibility.
  // We simply assert it.
  PPL_ASSERT(space_dimension() >= c.space_dimension());
  // Number of generators: the case of an empty polyhedron
  // has already been filtered out by the caller.
  const dimension_type n_rows = num_rows();
  PPL_ASSERT(n_rows > 0);
  const Generator_System& gs = *this;

  // `result' will keep the relation holding between the generators
  // we have seen so far and the constraint `c'.
  Poly_Con_Relation result = Poly_Con_Relation::saturates();

  switch (c.type()) {

  case Constraint::EQUALITY:
    {
      // The hyperplane defined by the equality `c' is included
      // in the set of points satisfying `c' (it is the same set!).
      result = result && Poly_Con_Relation::is_included();
      // The following integer variable will hold the scalar product sign
      // of either the first point or the first non-saturating ray we find.
      // If it is equal to 2, then it means that we haven't found such
      // a generator yet.
      int first_point_or_nonsaturating_ray_sign = 2;

      for (dimension_type i = n_rows; i-- > 0; ) {
        const Generator& g = gs[i];
        const int sp_sign = Scalar_Products::sign(c, g);
        // Checking whether the generator saturates the equality.
        // If that is the case, then we have to do something only if
        // the generator is a point.
        if (sp_sign == 0) {
          if (g.is_point()) {
            if (first_point_or_nonsaturating_ray_sign == 2)
              // It is the first time that we find a point and
              // we have not found a non-saturating ray yet.
              first_point_or_nonsaturating_ray_sign = 0;
            else
              // We already found a point or a non-saturating ray.
              if (first_point_or_nonsaturating_ray_sign != 0)
                return Poly_Con_Relation::strictly_intersects();
          }
        }
        else
          // Here we know that sp_sign != 0.
          switch (g.type()) {

          case Generator::LINE:
            // If a line does not saturate `c', then there is a strict
            // intersection between the points satisfying `c'
            // and the points generated by `gs'.
            return Poly_Con_Relation::strictly_intersects();

          case Generator::RAY:
            if (first_point_or_nonsaturating_ray_sign == 2) {
              // It is the first time that we have a non-saturating ray
              // and we have not found any point yet.
              first_point_or_nonsaturating_ray_sign = sp_sign;
              result = Poly_Con_Relation::is_disjoint();
            }
            else
              // We already found a point or a non-saturating ray.
              if (sp_sign != first_point_or_nonsaturating_ray_sign)
                return Poly_Con_Relation::strictly_intersects();
            break;

          case Generator::POINT:
          case Generator::CLOSURE_POINT:
            // NOTE: a non-saturating closure point is treated as
            // a normal point.
            if (first_point_or_nonsaturating_ray_sign == 2) {
              // It is the first time that we find a point and
              // we have not found a non-saturating ray yet.
              first_point_or_nonsaturating_ray_sign = sp_sign;
              result = Poly_Con_Relation::is_disjoint();
            }
            else
              // We already found a point or a non-saturating ray.
              if (sp_sign != first_point_or_nonsaturating_ray_sign)
                return Poly_Con_Relation::strictly_intersects();
            break;
          }
      }
    }
    break;

  case Constraint::NONSTRICT_INEQUALITY:
    {
      // The hyperplane implicitly defined by the non-strict inequality `c'
      // is included in the set of points satisfying `c'.
      result = result && Poly_Con_Relation::is_included();
      // The following Boolean variable will be set to `false'
      // as soon as either we find (any) point or we find a
      // non-saturating ray.
      bool first_point_or_nonsaturating_ray = true;

      for (dimension_type i = n_rows; i-- > 0; ) {
        const Generator& g = gs[i];
        const int sp_sign = Scalar_Products::sign(c, g);
        // Checking whether the generator saturates the non-strict
        // inequality. If that is the case, then we have to do something
        // only if the generator is a point.
        if (sp_sign == 0) {
          if (g.is_point()) {
            if (first_point_or_nonsaturating_ray)
              // It is the first time that we have a point and
              // we have not found a non-saturating ray yet.
              first_point_or_nonsaturating_ray = false;
            else
              // We already found a point or a non-saturating ray before.
              if (result == Poly_Con_Relation::is_disjoint())
                // Since g saturates c, we have a strict intersection if
                // none of the generators seen so far are included in `c'.
                return Poly_Con_Relation::strictly_intersects();
          }
        }
        else
          // Here we know that sp_sign != 0.
          switch (g.type()) {

          case Generator::LINE:
            // If a line does not saturate `c', then there is a strict
            // intersection between the points satisfying `c' and
            // the points generated by `gs'.
            return Poly_Con_Relation::strictly_intersects();

          case Generator::RAY:
            if (first_point_or_nonsaturating_ray) {
              // It is the first time that we have a non-saturating ray
              // and we have not found any point yet.
              first_point_or_nonsaturating_ray = false;
              result = (sp_sign > 0)
                ? Poly_Con_Relation::is_included()
                : Poly_Con_Relation::is_disjoint();
            }
            else {
              // We already found a point or a non-saturating ray.
              if ((sp_sign > 0
                   && result == Poly_Con_Relation::is_disjoint())
                  || (sp_sign < 0
                      && result.implies(Poly_Con_Relation::is_included())))
                // We have a strict intersection if either:
                // - `g' satisfies `c' but none of the generators seen
                //    so far are included in `c'; or
                // - `g' does not satisfy `c' and all the generators
                //    seen so far are included in `c'.
                return Poly_Con_Relation::strictly_intersects();
              if (sp_sign > 0)
                // Here all the generators seen so far either saturate
                // or are included in `c'.
                // Since `g' does not saturate `c' ...
                result = Poly_Con_Relation::is_included();
            }
            break;

          case Generator::POINT:
          case Generator::CLOSURE_POINT:
            // NOTE: a non-saturating closure point is treated as
            // a normal point.
            if (first_point_or_nonsaturating_ray) {
              // It is the first time that we have a point and
              // we have not found a non-saturating ray yet.
              // - If point `g' saturates `c', then all the generators
              //   seen so far saturate `c'.
              // - If point `g' is included (but does not saturate) `c',
              //   then all the generators seen so far are included in `c'.
              // - If point `g' does not satisfy `c', then all the
              //   generators seen so far are disjoint from `c'.
              first_point_or_nonsaturating_ray = false;
              if (sp_sign > 0)
                result = Poly_Con_Relation::is_included();
              else if (sp_sign < 0)
                result = Poly_Con_Relation::is_disjoint();
            }
            else {
              // We already found a point or a non-saturating ray before.
              if ((sp_sign > 0
                   && result == Poly_Con_Relation::is_disjoint())
                  || (sp_sign < 0
                      && result.implies(Poly_Con_Relation::is_included())))
                // We have a strict intersection if either:
                // - `g' satisfies or saturates `c' but none of the
                //    generators seen so far are included in `c'; or
                // - `g' does not satisfy `c' and all the generators
                //    seen so far are included in `c'.
                return Poly_Con_Relation::strictly_intersects();
              if (sp_sign > 0)
                // Here all the generators seen so far either saturate
                // or are included in `c'.
                // Since `g' does not saturate `c' ...
                result = Poly_Con_Relation::is_included();
            }
            break;
          }
      }
    }
    break;

  case Constraint::STRICT_INEQUALITY:
    {
      // The hyperplane implicitly defined by the strict inequality `c'
      // is disjoint from the set of points satisfying `c'.
      result = result && Poly_Con_Relation::is_disjoint();
      // The following Boolean variable will be set to `false'
      // as soon as either we find (any) point or we find a
      // non-saturating ray.
      bool first_point_or_nonsaturating_ray = true;
      for (dimension_type i = n_rows; i-- > 0; ) {
        const Generator& g = gs[i];
        // Using the reduced scalar product operator to avoid
        // both topology and num_columns mismatches.
        const int sp_sign = Scalar_Products::reduced_sign(c, g);
        // Checking whether the generator saturates the strict inequality.
        // If that is the case, then we have to do something
        // only if the generator is a point.
        if (sp_sign == 0) {
          if (g.is_point()) {
            if (first_point_or_nonsaturating_ray)
              // It is the first time that we have a point and
              // we have not found a non-saturating ray yet.
              first_point_or_nonsaturating_ray = false;
            else
              // We already found a point or a non-saturating ray before.
              if (result == Poly_Con_Relation::is_included())
                return Poly_Con_Relation::strictly_intersects();
          }
        }
        else
          // Here we know that sp_sign != 0.
          switch (g.type()) {

          case Generator::LINE:
            // If a line does not saturate `c', then there is a strict
            // intersection between the points satisfying `c' and the points
            // generated by `gs'.
            return Poly_Con_Relation::strictly_intersects();

          case Generator::RAY:
            if (first_point_or_nonsaturating_ray) {
              // It is the first time that we have a non-saturating ray
              // and we have not found any point yet.
              first_point_or_nonsaturating_ray = false;
              result = (sp_sign > 0)
                ? Poly_Con_Relation::is_included()
                : Poly_Con_Relation::is_disjoint();
            }
            else {
              // We already found a point or a non-saturating ray before.
              if ((sp_sign > 0
                   && result.implies(Poly_Con_Relation::is_disjoint()))
                  ||
                  (sp_sign <= 0
                   && result == Poly_Con_Relation::is_included()))
                return Poly_Con_Relation::strictly_intersects();
              if (sp_sign < 0)
                // Here all the generators seen so far either saturate
                // or are disjoint from `c'.
                // Since `g' does not saturate `c' ...
                result = Poly_Con_Relation::is_disjoint();
            }
            break;

          case Generator::POINT:
          case Generator::CLOSURE_POINT:
            if (first_point_or_nonsaturating_ray) {
              // It is the first time that we have a point and
              // we have not found a non-saturating ray yet.
              // - If point `g' saturates `c', then all the generators
              //   seen so far saturate `c'.
              // - If point `g' is included in (but does not saturate) `c',
              //   then all the generators seen so far are included in `c'.
              // - If point `g' strictly violates `c', then all the
              //   generators seen so far are disjoint from `c'.
              first_point_or_nonsaturating_ray = false;
              if (sp_sign > 0)
                result = Poly_Con_Relation::is_included();
              else if (sp_sign < 0)
                result = Poly_Con_Relation::is_disjoint();
            }
            else {
              // We already found a point or a non-saturating ray before.
              if ((sp_sign > 0
                   && result.implies(Poly_Con_Relation::is_disjoint()))
                  ||
                  (sp_sign <= 0
                   && result == Poly_Con_Relation::is_included()))
                return Poly_Con_Relation::strictly_intersects();
              if (sp_sign < 0)
                // Here all the generators seen so far either saturate
                // or are disjoint from `c'.
                // Since `g' does not saturate `c' ...
                result = Poly_Con_Relation::is_disjoint();
            }
            break;
          }
      }
    }
    break;
  }
  // We have seen all generators.
  return result;
}

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 952 of file Generator_System.cc.

References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), Parma_Polyhedra_Library::Generator::is_line_or_ray(), Parma_Polyhedra_Library::Dense_Matrix::num_rows(), PPL_ASSERT, Parma_Polyhedra_Library::Dense_Matrix::remove_trailing_rows(), Parma_Polyhedra_Library::Linear_System::set_sorted(), and Parma_Polyhedra_Library::swap().

Referenced by affine_image(), and simplify().

                                                   {
  // The origin of the vector space cannot be a valid line/ray.
  // NOTE: the following swaps will mix generators without even trying
  // to preserve sortedness: as a matter of fact, it will almost always
  // be the case that the input generator system is NOT sorted.
  using std::swap;
  Generator_System& gs = *this;
  const dimension_type old_n_rows = gs.num_rows();
  dimension_type n_rows = old_n_rows;
  if (num_pending_rows() == 0) {
    for (dimension_type i = n_rows; i-- > 0; ) {
      Generator& g = gs[i];
      if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
        // An invalid line/ray has been found.
        --n_rows;
        swap(g, gs[n_rows]);
        gs.set_sorted(false);
      }
    }
    set_index_first_pending_row(n_rows);
  }
  else {
    // If the matrix has some pending rows, we can not
    // swap the "normal" rows with the pending rows. So
    // we must put at the end of the "normal" rows
    // the invalid "normal" rows, put them at the end
    // of the matrix, find the invalid rows in the pending
    // part and then erase the invalid rows that now
    // are in the bottom part of the matrix.
    PPL_ASSERT(num_pending_rows() > 0);
    dimension_type first_pending = first_pending_row();
    for (dimension_type i = first_pending; i-- > 0; ) {
      Generator& g = gs[i];
      if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
        // An invalid line/ray has been found.
        --first_pending;
        swap(g, gs[first_pending]);
        gs.set_sorted(false);
      }
    }
    const dimension_type num_invalid_rows
      = first_pending_row() - first_pending;
    set_index_first_pending_row(first_pending);
    for (dimension_type i = 0; i < num_invalid_rows; ++i)
      swap(gs[n_rows - i], gs[first_pending + i]);
    n_rows -= num_invalid_rows;
    for (dimension_type i = n_rows; i-- > first_pending; ) {
      Generator& g = gs[i];
      if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
        // An invalid line/ray has been found.
        --n_rows;
        swap(g, gs[n_rows]);
        gs.set_sorted(false);
      }
    }
  }
  gs.remove_trailing_rows(old_n_rows - n_rows);
}

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 726 of file Generator_System.cc.

Referenced by Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), and Parma_Polyhedra_Library::Polyhedron::simplify_using_context_assign().

                                                                          {
  PPL_ASSERT(c.space_dimension() <= space_dimension());

  // Setting `sps' to the appropriate scalar product sign operator.
  // This also avoids problems when having _legal_ topology mismatches
  // (which could also cause a mismatch in the number of columns).
  Topology_Adjusted_Scalar_Product_Sign sps(c);

  const Generator_System& gs = *this;
  switch (c.type()) {
  case Constraint::EQUALITY:
    // Equalities must be saturated by all generators.
    for (dimension_type i = gs.num_rows(); i-- > 0; )
      if (sps(c, gs[i]) != 0)
        return false;
    break;
  case Constraint::NONSTRICT_INEQUALITY:
    // Non-strict inequalities must be saturated by lines and
    // satisfied by all the other generators.
    for (dimension_type i = gs.num_rows(); i-- > 0; ) {
      const Generator& g = gs[i];
      const int sp_sign = sps(c, g);
      if (g.is_line()) {
        if (sp_sign != 0)
          return false;
      }
      else
        // `g' is a ray, point or closure point.
        if (sp_sign < 0)
          return false;
    }
    break;
  case Constraint::STRICT_INEQUALITY:
    // Strict inequalities must be saturated by lines,
    // satisfied by all generators, and must not be saturated by points.
    for (dimension_type i = gs.num_rows(); i-- > 0; ) {
      const Generator& g = gs[i];
      const int sp_sign = sps(c, g);
      switch (g.type()) {
      case Generator::POINT:
        if (sp_sign <= 0)
          return false;
        break;
      case Generator::LINE:
        if (sp_sign != 0)
          return false;
        break;
      default:
        // `g' is a ray or closure point.
        if (sp_sign < 0)
          return false;
        break;
      }
    }
    break;
  }
  // If we reach this point, `c' is satisfied by all generators.
  return true;
}

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::simplify ( )

inlineprivate

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

References remove_invalid_lines_and_rays().

                           {
  Linear_System::simplify();
  remove_invalid_lines_and_rays();
}

dimension_type Parma_Polyhedra_Library::Generator_System::space_dimension ( ) const

inline

Returns the dimension of the vector space enclosing *this.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), adjust_topology_and_space_dimension(), affine_image(), Parma_Polyhedra_Library::Affine_Space::Affine_Space(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Grid_Generator_System::space_dimension(), and Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible().

                                        {
  return Linear_System::space_dimension();
}

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

                                              {
  return Linear_System::total_memory_in_bytes();
}

const Generator_System & Parma_Polyhedra_Library::Generator_System::zero_dim_univ ( )

inlinestatic

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

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

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

References PPL_ASSERT, and zero_dim_univ_p.

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

                                {
  PPL_ASSERT(zero_dim_univ_p != 0);
  return *zero_dim_univ_p;
}

Friends And Related Function Documentation

friend class const_iterator

friend

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

std::ostream & operator<<	(	std::ostream &	s,
		const Generator_System &	gs
	)

Writes false if gs is empty. Otherwise, writes on s the generators of gs, all in one row and separated by ", ".

std::ostream & operator<<	(	std::ostream &	s,
		const Generator_System &	gs
	)

References begin(), and end().

                                                                     {
  Generator_System::const_iterator i = gs.begin();
  const Generator_System::const_iterator gs_end = gs.end();
  if (i == gs_end)
    return s << "false";
  while (true) {
    s << *i++;
    if (i == gs_end)
      return s;
    s << ", ";
  }
}

bool operator==	(	const Polyhedron &	x,
		const Polyhedron &	y
	)

friend

friend class Parma_Polyhedra_Library::Grid_Generator_System

friend

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

friend class Parma_Polyhedra_Library::Polyhedron

friend

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

void swap	(	Generator_System &	x,
		Generator_System &	y
	)

Referenced by adjust_topology_and_space_dimension().

void swap	(	Generator_System &	x,
		Generator_System &	y
	)

References m_swap().

                                               {
  x.m_swap(y);
}

Member Data Documentation

const PPL::Generator_System * Parma_Polyhedra_Library::Generator_System::zero_dim_univ_p = 0

staticprivate

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 354 of file Generator_System.defs.hh.

Referenced by zero_dim_univ().

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

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Attributes

Friends

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation