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

A system of constraints. More...

#include <Constraint_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Constraint_System:

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

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Constraint_System ()
 Default constructor: builds an empty system of constraints.
 Constraint_System (const Constraint &c)
 Builds the singleton system containing only constraint c.
 Constraint_System (const Constraint_System &cs)
 Ordinary copy-constructor.
 ~Constraint_System ()
 Destructor.
Constraint_Systemoperator= (const Constraint_System &y)
 Assignment operator.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
bool has_strict_inequalities () const
 Returns true if and only if *this contains one or more strict inequality constraints.
void clear ()
 Removes all the constraints from the constraint system and sets its space dimension to 0.
void insert (const Constraint &c)
 Inserts in *this a copy of the constraint c, increasing the number of space dimensions if needed.
const_iterator begin () const
 Returns the const_iterator pointing to the first constraint, 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 (Constraint_System &y)
 Swaps *this with y.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Constraint_System can handle.
static const Constraint_Systemzero_dim_empty ()
 Returns the singleton system containing only Constraint::zero_dim_false().

Private Member Functions

 Constraint_System (Topology topol)
 Builds an empty system of constraints having the specified topology.
 Constraint_System (Topology topol, dimension_type n_rows, dimension_type n_columns)
 Builds a system of n_rows constraints 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 strict inequalities.
Constraintoperator[] (dimension_type k)
 Returns the k- th constraint of the system.
const Constraintoperator[] (dimension_type k) const
 Returns a constant reference to the k- th constraint of the system.
bool satisfies_all_constraints (const Generator &g) const
 Returns true if g satisfies all the constraints.
void affine_preimage (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
 Substitutes a given column of coefficients by a given affine expression.
dimension_type num_equalities () const
 Returns the number of equality constraints.
dimension_type num_inequalities () const
 Returns the number of inequality constraints.
void simplify ()
 Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of constraints.
void insert_pending (const Constraint &c)
 Inserts in *this a copy of the constraint c, increasing the number of space dimensions if needed. It is a pending constraint.
void add_low_level_constraints ()
 Adds low-level constraints to the constraint system.

Friends

class const_iterator
class Parma_Polyhedra_Library::Polyhedron
class Parma_Polyhedra_Library::LP_Problem
bool operator== (const Polyhedron &x, const Polyhedron &y)
 Returns true if and only if x and y are the same polyhedron.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &s, const Constraint_System &cs)
 Output operator.
void swap (Parma_Polyhedra_Library::Constraint_System &x, Parma_Polyhedra_Library::Constraint_System &y)
 Specializes std::swap.

Classes

class  const_iterator
 An iterator over a system of constraints. More...


Detailed Description

A system of constraints.

An object of the class Constraint_System is a system of constraints, i.e., a multiset of objects of the class Constraint. When inserting constraints in a system, space dimensions are automatically adjusted so that all the constraints in the system are defined on the same vector space.

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 builds a system of constraints corresponding to a square in $\Rset^2$:
  Constraint_System cs;
  cs.insert(x >= 0);
  cs.insert(x <= 3);
  cs.insert(y >= 0);
  cs.insert(y <= 3);
Note that: the constraint system is created with space dimension zero; the first and third constraint insertions increase the space dimension to $1$ and $2$, respectively.
Example 2
By adding four strict inequalities to the constraint system of the previous example, we can remove just the four vertices from the square defined above.
  cs.insert(x + y > 0);
  cs.insert(x + y < 6);
  cs.insert(x - y < 3);
  cs.insert(y - x < 3);
Example 3
The following code builds a system of constraints corresponding to a half-strip in $\Rset^2$:
  Constraint_System cs;
  cs.insert(x >= 0);
  cs.insert(x - y <= 0);
  cs.insert(x - y + 1 >= 0);
Note:
After inserting a multiset of constraints in a constraint system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent constraint system will be available, where original constraints may have been reordered, removed (if they are trivial, duplicate or implied by other constraints), linearly combined, etc.

Definition at line 127 of file Constraint_System.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Constraint_System::Constraint_System (  )  [inline]

Default constructor: builds an empty system of constraints.

Definition at line 31 of file Constraint_System.inlines.hh.

00032   : Linear_System(NECESSARILY_CLOSED) {
00033 }

Parma_Polyhedra_Library::Constraint_System::Constraint_System ( const Constraint c  )  [inline, explicit]

Builds the singleton system containing only constraint c.

Definition at line 36 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::insert().

00037   : Linear_System(c.topology()) {
00038   Linear_System::insert(c);
00039 }

Parma_Polyhedra_Library::Constraint_System::Constraint_System ( const Constraint_System cs  )  [inline]

Ordinary copy-constructor.

Definition at line 42 of file Constraint_System.inlines.hh.

00043   : Linear_System(cs) {
00044 }

Parma_Polyhedra_Library::Constraint_System::~Constraint_System (  )  [inline]

Destructor.

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

00059                                       {
00060 }

Parma_Polyhedra_Library::Constraint_System::Constraint_System ( Topology  topol  )  [inline, explicit, private]

Builds an empty system of constraints having the specified topology.

Definition at line 47 of file Constraint_System.inlines.hh.

00048   : Linear_System(topol) {
00049 }

Parma_Polyhedra_Library::Constraint_System::Constraint_System ( Topology  topol,
dimension_type  n_rows,
dimension_type  n_columns 
) [inline, private]

Builds a system of n_rows constraints on a n_columns - 1 dimensional space (including the $\epsilon$ dimension, if topol is NOT_NECESSARILY_CLOSED).

Definition at line 52 of file Constraint_System.inlines.hh.

00055   : Linear_System(topol, n_rows, n_columns) {
00056 }


Member Function Documentation

Constraint_System & Parma_Polyhedra_Library::Constraint_System::operator= ( const Constraint_System y  )  [inline]

Assignment operator.

Definition at line 63 of file Constraint_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::Constraint_System::max_space_dimension (  )  [inline, static]

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

Returns the dimension of the vector space enclosing *this.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 84 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::space_dimension().

Referenced by Parma_Polyhedra_Library::Grid::add_congruences(), Parma_Polyhedra_Library::Grid::add_congruences_and_minimize(), Parma_Polyhedra_Library::Grid::add_constraints(), Parma_Polyhedra_Library::Grid::add_constraints_and_minimize(), Parma_Polyhedra_Library::Grid::add_recycled_congruences(), Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Grid::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Grid::add_recycled_constraints_and_minimize(), adjust_topology_and_space_dimension(), affine_preimage(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::LP_Problem::compute_generator(), Parma_Polyhedra_Library::Polyhedron::constraints(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), insert(), insert_pending(), Parma_Polyhedra_Library::BD_Shape< T >::limited_BHMZ05_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::limited_CC76_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::OK(), Parma_Polyhedra_Library::LP_Problem::OK(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), satisfies_all_constraints(), Parma_Polyhedra_Library::LP_Problem::space_dimension(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), and Parma_Polyhedra_Library::Grid::throw_dimension_incompatible().

00084                                          {
00085   return Linear_System::space_dimension();
00086 }

bool Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities (  )  const

Returns true if and only if *this contains one or more strict inequality constraints.

Definition at line 197 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Constraint::is_tautological(), Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().

Referenced by Parma_Polyhedra_Library::LP_Problem::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::Polyhedron::is_topologically_closed(), Parma_Polyhedra_Library::BD_Shape< T >::limited_BHMZ05_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::limited_CC76_extrapolation_assign(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::LP_Problem::OK(), and ppl_Constraint_System_has_strict_inequalities().

00197                                                     {
00198   if (is_necessarily_closed())
00199     return false;
00200   const Constraint_System& cs = *this;
00201   const dimension_type eps_index = cs.num_columns() - 1;
00202   // We verify if the system has strict inequalities
00203   // also in the pending part.
00204   for (dimension_type i = cs.num_rows(); i-- > 0; ) {
00205     const Constraint& c = cs[i];
00206     // Optimized type checking: we already know the topology;
00207     // also, equalities have the epsilon coefficient equal to zero.
00208     // NOTE: the constraint eps_leq_one should not be considered
00209     //       a strict inequality.
00210     if (c[eps_index] < 0 && !c.is_tautological())
00211       return true;
00212   }
00213   return false;
00214 }

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

void Parma_Polyhedra_Library::Constraint_System::insert ( const Constraint c  ) 

Inserts in *this a copy of the constraint c, increasing the number of space dimensions if needed.

Definition at line 217 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::LP_Problem::add_constraint(), Parma_Polyhedra_Library::LP_Problem::add_constraints(), add_low_level_constraints(), Parma_Polyhedra_Library::Polyhedron::BHRZ03_combining_constraints(), Parma_Polyhedra_Library::Bounding_Box::constraints(), Parma_Polyhedra_Library::BD_Shape< T >::constraints(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::Polyhedron::limited_BHRZ03_extrapolation_assign(), limited_extrapolation_assign(), limited_extrapolation_assign_with_tokens(), Parma_Polyhedra_Library::Polyhedron::limited_H79_extrapolation_assign(), Parma_Polyhedra_Library::BD_Shape< T >::minimized_constraints(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), ppl_Constraint_System_insert_Constraint(), ppl_LP_Problem_add_constraints(), ppl_new_C_Polyhedron_from_constraints(), ppl_new_LP_Problem(), ppl_new_NNC_Polyhedron_from_constraints(), ppl_Polyhedron_add_constraints(), ppl_Polyhedron_add_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::select_CH78_constraints(), Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().

00217                                                 {
00218   // We are sure that the matrix has no pending rows
00219   // and that the new row is not a pending constraint.
00220   assert(num_pending_rows() == 0);
00221   if (topology() == c.topology())
00222     Linear_System::insert(c);
00223   else
00224     // `*this' and `c' have different topologies.
00225     if (is_necessarily_closed()) {
00226       // Padding the matrix with a columns of zeroes
00227       // corresponding to the epsilon coefficients.
00228       add_zero_columns(1);
00229       set_not_necessarily_closed();
00230       Linear_System::insert(c);
00231     }
00232     else {
00233       // Here `*this' is NNC and `c' is necessarily closed.
00234       // Copying the constraint adding the epsilon coefficient
00235       // and the missing space dimensions, if any.
00236       // FIXME: provide a resizing copy-constructor taking
00237       // topology and the space dimension.
00238       const dimension_type new_size = 2 + std::max(c.space_dimension(),
00239                                                    space_dimension());
00240       Constraint tmp_c(c, new_size);
00241       tmp_c.set_not_necessarily_closed();
00242       Linear_System::insert(tmp_c);
00243     }
00244   assert(OK());
00245 }

const Constraint_System & Parma_Polyhedra_Library::Constraint_System::zero_dim_empty (  )  [inline, static]

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

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 162 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::begin().

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::affine_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::H79_Certificate::compare(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), Parma_Polyhedra_Library::Congruence_System::Congruence_System(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::H79_Certificate::H79_Certificate(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition(), operator<<(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), ppl_Constraint_System_begin(), ppl_LP_Problem_constraints(), ppl_Polyhedron_get_constraints(), ppl_Polyhedron_get_minimized_constraints(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().

00162                                {
00163   const_iterator i(Linear_System::begin(), *this);
00164   i.skip_forward();
00165   return i;
00166 }

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

Returns the past-the-end const_iterator.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 169 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::end().

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::add_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::affine_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::BD_Shape(), Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), Parma_Polyhedra_Library::BHRZ03_Certificate::BHRZ03_Certificate(), Parma_Polyhedra_Library::C_Polyhedron::C_Polyhedron(), Parma_Polyhedra_Library::H79_Certificate::compare(), Parma_Polyhedra_Library::BHRZ03_Certificate::compare(), Parma_Polyhedra_Library::Congruence_System::Congruence_System(), Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::get_limiting_shape(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::H79_Certificate::H79_Certificate(), Parma_Polyhedra_Library::Polyhedra_Powerset< PH >::linear_partition(), operator<<(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), ppl_Constraint_System_end(), ppl_LP_Problem_constraints(), ppl_Polyhedron_get_constraints(), ppl_Polyhedron_get_minimized_constraints(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().

00169                              {
00170   const const_iterator i(Linear_System::end(), *this);
00171   return i;
00172 }

bool Parma_Polyhedra_Library::Constraint_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 Constraint.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 562 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Matrix::num_rows(), and Parma_Polyhedra_Library::Matrix::OK().

Referenced by adjust_topology_and_space_dimension(), ascii_load(), insert(), insert_pending(), and Parma_Polyhedra_Library::Polyhedron::OK().

00562                                {
00563   // A Constraint_System must be a valid Linear_System; do not check for
00564   // strong normalization, since this will be done when
00565   // checking each individual constraint.
00566   if (!Linear_System::OK(false))
00567     return false;
00568 
00569   // Checking each constraint in the system.
00570   const Constraint_System& x = *this;
00571   for (dimension_type i = num_rows(); i-- > 0; )
00572     if (!x[i].OK())
00573       return false;
00574 
00575   // All checks passed.
00576   return true;
00577 }

void Parma_Polyhedra_Library::Constraint_System::ascii_dump (  )  const

void Parma_Polyhedra_Library::Constraint_System::ascii_dump ( std::ostream &  s  )  const

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 456 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Constraint::EQUALITY, 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::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, and Parma_Polyhedra_Library::Constraint::type().

00456                                                     {
00457   const Constraint_System& x = *this;
00458   const dimension_type x_num_rows = x.num_rows();
00459   const dimension_type x_num_columns = x.num_columns();
00460   s << "topology " << (is_necessarily_closed()
00461                        ? "NECESSARILY_CLOSED"
00462                        : "NOT_NECESSARILY_CLOSED")
00463     << "\n"
00464     << x_num_rows << " x " << x_num_columns << ' '
00465     << (x.is_sorted() ? "(sorted)" : "(not_sorted)")
00466     << "\n"
00467     << "index_first_pending " << x.first_pending_row()
00468     << "\n";
00469   for (dimension_type i = 0; i < x_num_rows; ++i) {
00470     const Constraint& c = x[i];
00471     for (dimension_type j = 0; j < x_num_columns; ++j)
00472       s << c[j] << ' ';
00473     switch (c.type()) {
00474     case Constraint::EQUALITY:
00475       s << "=";
00476       break;
00477     case Constraint::NONSTRICT_INEQUALITY:
00478       s << ">=";
00479       break;
00480     case Constraint::STRICT_INEQUALITY:
00481       s << ">";
00482       break;
00483     }
00484     s << "\n";
00485   }
00486 }

void Parma_Polyhedra_Library::Constraint_System::print (  )  const

Prints *this to std::cerr using operator<<.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

bool Parma_Polyhedra_Library::Constraint_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.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 491 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Constraint::NONSTRICT_INEQUALITY, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), 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(), Parma_Polyhedra_Library::Linear_System::set_sorted(), and Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY.

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

00491                                               {
00492   std::string str;
00493   if (!(s >> str) || str != "topology")
00494     return false;
00495   if (!(s >> str))
00496     return false;
00497   if (str == "NECESSARILY_CLOSED")
00498     set_necessarily_closed();
00499   else {
00500     if (str != "NOT_NECESSARILY_CLOSED")
00501       return false;
00502     set_not_necessarily_closed();
00503   }
00504 
00505   dimension_type nrows;
00506   dimension_type ncols;
00507   if (!(s >> nrows))
00508     return false;
00509   if (!(s >> str))
00510     return false;
00511   if (!(s >> ncols))
00512       return false;
00513   resize_no_copy(nrows, ncols);
00514 
00515   if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00516     return false;
00517   set_sorted(str == "(sorted)");
00518   dimension_type index;
00519   if (!(s >> str) || str != "index_first_pending")
00520     return false;
00521   if (!(s >> index))
00522     return false;
00523   set_index_first_pending_row(index);
00524 
00525   Constraint_System& x = *this;
00526   for (dimension_type i = 0; i < x.num_rows(); ++i) {
00527     for (dimension_type j = 0; j < x.num_columns(); ++j)
00528       if (!(s >> x[i][j]))
00529         return false;
00530 
00531     if (!(s >> str))
00532       return false;
00533     if (str == "=")
00534       x[i].set_is_equality();
00535     else
00536       x[i].set_is_inequality();
00537 
00538     // Checking for equality of actual and declared types.
00539     switch (x[i].type()) {
00540     case Constraint::EQUALITY:
00541       if (str == "=")
00542         continue;
00543       break;
00544     case Constraint::NONSTRICT_INEQUALITY:
00545       if (str == ">=")
00546         continue;
00547       break;
00548     case Constraint::STRICT_INEQUALITY:
00549       if (str == ">")
00550         continue;
00551       break;
00552     }
00553     // Reaching this point means that the input was illegal.
00554     return false;
00555   }
00556   // Check for well-formedness.
00557   assert(OK());
00558   return true;
00559 }

memory_size_type Parma_Polyhedra_Library::Constraint_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.

Definition at line 197 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().

00197                                                {
00198   return Linear_System::total_memory_in_bytes();
00199 }

memory_size_type Parma_Polyhedra_Library::Constraint_System::external_memory_in_bytes (  )  const [inline]

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

Swaps *this with y.

Definition at line 187 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::swap().

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

00187                                             {
00188   Linear_System::swap(y);
00189 }

bool Parma_Polyhedra_Library::Constraint_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 strict inequalities.

Definition at line 39 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::erase_to_end(), Parma_Polyhedra_Library::Linear_System::first_pending_row(), has_strict_inequalities(), Parma_Polyhedra_Library::Linear_System::is_sorted(), Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::NOT_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::remove_trailing_columns(), 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(), Parma_Polyhedra_Library::Linear_System::set_sorted(), Parma_Polyhedra_Library::Linear_System::sort_rows(), space_dimension(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_System::topology(), and Parma_Polyhedra_Library::Linear_System::unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::constraints(), 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);
00052         set_necessarily_closed();
00053       }
00054       else {
00055         cols_to_be_added += 2;
00056         add_zero_columns(cols_to_be_added);
00057         set_not_necessarily_closed();
00058       }
00059     else
00060       // Here `num_columns() > 0'.
00061       if (old_topology != new_topology)
00062         if (new_topology == NECESSARILY_CLOSED) {
00063           switch (cols_to_be_added) {
00064           case 0:
00065             remove_trailing_columns(1);
00066             break;
00067           case 1:
00068             // Nothing to do.
00069             break;
00070           default:
00071             add_zero_columns(--cols_to_be_added);
00072           }
00073           set_necessarily_closed();
00074         }
00075         else {
00076           // Here old_topology == NECESSARILY_CLOSED
00077           //  and new_topology == NOT_NECESSARILY_CLOSED.
00078           add_zero_columns(++cols_to_be_added);
00079           set_not_necessarily_closed();
00080         }
00081       else {
00082         // Here topologies agree.
00083         if (cols_to_be_added > 0)
00084           add_zero_columns(cols_to_be_added);
00085       }
00086     assert(OK());
00087     return true;
00088   }
00089 
00090   // Here `num_rows() > 0'.
00091   if (cols_to_be_added > 0)
00092     if (old_topology != new_topology)
00093       if (new_topology == NECESSARILY_CLOSED) {
00094         // A NOT_NECESSARILY_CLOSED constraint system
00095         // can be converted to a NECESSARILY_CLOSED one
00096         // only if it does not contain strict inequalities.
00097         if (has_strict_inequalities())
00098           return false;
00099         // Since there were no strict inequalities,
00100         // the only constraints that may have a non-zero epsilon coefficient
00101         // are the eps-leq-one and the eps-geq-zero constraints.
00102         // If they are present, we erase these rows, so that the
00103         // epsilon column will only contain zeroes: as a consequence,
00104         // we just decrement the number of columns to be added.
00105         Constraint_System& cs = *this;
00106         const dimension_type eps_index = old_space_dim + 1;
00107         dimension_type cs_num_rows = cs.num_rows();
00108         bool was_sorted = cs.is_sorted();
00109         if (was_sorted)
00110           cs.set_sorted(false);
00111 
00112         // If we have no pending rows, we only check if
00113         // we must erase some rows.
00114         if (cs.num_pending_rows() == 0) {
00115           for (dimension_type i = cs_num_rows; i-- > 0; )
00116             if (cs[i][eps_index] != 0) {
00117               --cs_num_rows;
00118               std::swap(cs[i], cs[cs_num_rows]);
00119             }
00120           cs.erase_to_end(cs_num_rows);
00121           cs.unset_pending_rows();
00122         }
00123         else {
00124           // There are pending rows, and we cannot swap them
00125           // into the non-pending part of the matrix.
00126           // Thus, we first work on the non-pending part as if it was
00127           // an independent matrix; then we work on the pending part.
00128           const dimension_type old_first_pending = cs.first_pending_row();
00129           dimension_type new_first_pending = old_first_pending;
00130           for (dimension_type i = new_first_pending; i-- > 0; )
00131             if (cs[i][eps_index] != 0) {
00132               --new_first_pending;
00133               std::swap(cs[i], cs[new_first_pending]);
00134             }
00135           const dimension_type num_swaps
00136             = old_first_pending - new_first_pending;
00137           cs.set_index_first_pending_row(new_first_pending);
00138           // Move the swapped rows to the real end of the matrix.
00139           for (dimension_type i = num_swaps; i-- > 0; )
00140             std::swap(cs[old_first_pending - i], cs[cs_num_rows - i]);
00141           cs_num_rows -= num_swaps;
00142           // Now iterate through the pending rows.
00143           for (dimension_type i = cs_num_rows; i-- > new_first_pending; )
00144             if (cs[i][eps_index] != 0) {
00145               --cs_num_rows;
00146               std::swap(cs[i], cs[cs_num_rows]);
00147             }
00148           cs.erase_to_end(cs_num_rows);
00149         }
00150 
00151         // If `cs' was sorted we sort it again.
00152         if (was_sorted)
00153           cs.sort_rows();
00154         if (--cols_to_be_added > 0)
00155           add_zero_columns(cols_to_be_added);
00156         set_necessarily_closed();
00157       }
00158       else {
00159         // A NECESSARILY_CLOSED constraint system is converted to
00160         // a NOT_NECESSARILY_CLOSED one by adding a further column
00161         // of zeroes for the epsilon coefficients.
00162         add_zero_columns(++cols_to_be_added);
00163         set_not_necessarily_closed();
00164       }
00165     else {
00166       // Topologies agree: first add the required zero columns ...
00167       add_zero_columns(cols_to_be_added);
00168       // ... and, if needed, move the epsilon coefficients
00169       // to the new last column.
00170       if (old_topology == NOT_NECESSARILY_CLOSED)
00171         swap_columns(old_space_dim + 1, new_space_dim + 1);
00172     }
00173   else
00174     // Here `cols_to_be_added == 0'.
00175     if (old_topology != new_topology)
00176       if (new_topology == NECESSARILY_CLOSED) {
00177         // A NOT_NECESSARILY_CLOSED constraint system
00178         // can be converted to a NECESSARILY_CLOSED one
00179         // only if it does not contain strict inequalities.
00180         if (has_strict_inequalities())
00181           return false;
00182         // We just remove the column of the epsilon coefficients.
00183         remove_trailing_columns(1);
00184         set_necessarily_closed();
00185       }
00186       else {
00187         // We just add the column of the epsilon coefficients.
00188         add_zero_columns(1);
00189         set_not_necessarily_closed();
00190       }
00191   // We successfully adjusted space dimensions and topology.
00192   assert(OK());
00193   return true;
00194 }

Constraint & Parma_Polyhedra_Library::Constraint_System::operator[] ( dimension_type  k  )  [inline, private]

Returns the k- th constraint of the system.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 69 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::operator[]().

00069                                                     {
00070   return static_cast<Constraint&>(Linear_System::operator[](k));
00071 }

const Constraint & Parma_Polyhedra_Library::Constraint_System::operator[] ( dimension_type  k  )  const [inline, private]

Returns a constant reference to the k- th constraint of the system.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 74 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::operator[]().

00074                                                           {
00075   return static_cast<const Constraint&>(Linear_System::operator[](k));
00076 }

bool Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints ( const Generator g  )  const [private]

Returns true if g satisfies all the constraints.

Definition at line 308 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Generator::CLOSURE_POINT, Parma_Polyhedra_Library::Constraint::EQUALITY, Parma_Polyhedra_Library::Constraint::is_inequality(), Parma_Polyhedra_Library::Generator::is_line(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), 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, space_dimension(), Parma_Polyhedra_Library::Generator::space_dimension(), Parma_Polyhedra_Library::Constraint::STRICT_INEQUALITY, Parma_Polyhedra_Library::Constraint::type(), and Parma_Polyhedra_Library::Generator::type().

Referenced by Parma_Polyhedra_Library::LP_Problem::OK(), and Parma_Polyhedra_Library::Polyhedron::relation_with().

00308                                                                         {
00309   assert(g.space_dimension() <= space_dimension());
00310 
00311   // Setting `sps' to the appropriate scalar product sign operator.
00312   // This also avoids problems when having _legal_ topology mismatches
00313   // (which could also cause a mismatch in the number of columns).
00314   Topology_Adjusted_Scalar_Product_Sign sps(g);
00315 
00316   const Constraint_System& cs = *this;
00317   if (cs.is_necessarily_closed()) {
00318     if (g.is_line()) {
00319       // Lines must saturate all constraints.
00320       for (dimension_type i = cs.num_rows(); i-- > 0; )
00321         if (sps(g, cs[i]) != 0)
00322           return false;
00323     }
00324     else
00325       // `g' is either a ray, a point or a closure point.
00326       for (dimension_type i = cs.num_rows(); i-- > 0; ) {
00327         const Constraint& c = cs[i];
00328         const int sp_sign = sps(g, c);
00329         if (c.is_inequality()) {
00330           // As `cs' is necessarily closed,
00331           // `c' is a non-strict inequality.
00332           if (sp_sign < 0)
00333             return false;
00334         }
00335         else
00336           // `c' is an equality.
00337           if (sp_sign != 0)
00338             return false;
00339       }
00340   }
00341   else
00342     // `cs' is not necessarily closed.
00343     switch (g.type()) {
00344 
00345     case Generator::LINE:
00346       // Lines must saturate all constraints.
00347       for (dimension_type i = cs.num_rows(); i-- > 0; )
00348         if (sps(g, cs[i]) != 0)
00349           return false;
00350       break;
00351 
00352     case Generator::POINT:
00353       // Have to perform the special test
00354       // when dealing with a strict inequality.
00355       for (dimension_type i = cs.num_rows(); i-- > 0; ) {
00356         const Constraint& c = cs[i];
00357         const int sp_sign = sps(g, c);
00358         switch (c.type()) {
00359         case Constraint::EQUALITY:
00360           if (sp_sign != 0)
00361             return false;
00362           break;
00363         case Constraint::NONSTRICT_INEQUALITY:
00364           if (sp_sign < 0)
00365             return false;
00366           break;
00367         case Constraint::STRICT_INEQUALITY:
00368           if (sp_sign <= 0)
00369             return false;
00370           break;
00371         }
00372       }
00373       break;
00374 
00375     case Generator::RAY:
00376       // Intentionally fall through.
00377     case Generator::CLOSURE_POINT:
00378       for (dimension_type i = cs.num_rows(); i-- > 0; ) {
00379         const Constraint& c = cs[i];
00380         const int sp_sign = sps(g, c);
00381         if (c.is_inequality()) {
00382           // Constraint `c' is either a strict or a non-strict inequality.
00383           if (sp_sign < 0)
00384             return false;
00385         }
00386         else
00387           // Constraint `c' is an equality.
00388           if (sp_sign != 0)
00389             return false;
00390       }
00391       break;
00392     }
00393 
00394   // If we reach this point, `g' satisfies all constraints.
00395   return true;
00396 }

void Parma_Polyhedra_Library::Constraint_System::affine_preimage ( dimension_type  v,
const Linear_Expression expr,
Coefficient_traits::const_reference  denominator 
) [private]

Substitutes a given column of coefficients by a given affine expression.

Parameters:
v Index of the column to which the affine transformation is substituted.
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 Section Images and Preimages of Affine Transfer Relations) 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 substitutes the matrix of constraints by a new matrix whose elements ${a'}_{ij}$ are built from the old one $a_{ij}$ as follows:

\[ {a'}_{ij} = \begin{cases} a_{ij} * \mathrm{denominator} + a_{iv} * \mathrm{expr}[j] \quad \text{for } j \neq v; \\ \mathrm{expr}[v] * a_{iv} \quad \text{for } j = v. \end{cases} \]

expr is a constant parameter and unaltered by this computation.

Definition at line 401 of file Constraint_System.cc.

References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), space_dimension(), and Parma_Polyhedra_Library::Linear_System::strong_normalize().

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

00403                                                                  {
00404   Constraint_System& x = *this;
00405   // `v' is the index of a column corresponding to
00406   // a "user" variable (i.e., it cannot be the inhomogeneous term,
00407   // nor the epsilon dimension of NNC polyhedra).
00408   assert(v > 0 && v <= x.space_dimension());
00409   assert(expr.space_dimension() <= x.space_dimension());
00410   assert(denominator > 0);
00411 
00412   const dimension_type n_columns = x.num_columns();
00413   const dimension_type n_rows = x.num_rows();
00414   const dimension_type expr_size = expr.size();
00415   const bool not_invertible = (v >= expr_size || expr[v] == 0);
00416 
00417   if (denominator != 1)
00418     for (dimension_type i = n_rows; i-- > 0; ) {
00419       Constraint& row = x[i];
00420       Coefficient& row_v = row[v];
00421       if (row_v != 0) {
00422         for (dimension_type j = n_columns; j-- > 0; )
00423           if (j != v) {
00424             Coefficient& row_j = row[j];
00425             row_j *= denominator;
00426             if (j < expr_size)
00427               add_mul_assign(row_j, row_v, expr[j]);
00428           }
00429         if (not_invertible)
00430           row_v = 0;
00431         else
00432           row_v *= expr[v];
00433       }
00434     }
00435   else
00436     // Here `denominator' == 1: optimized computation
00437     // only considering columns having indexes < expr_size.
00438     for (dimension_type i = n_rows; i-- > 0; ) {
00439       Constraint& row = x[i];
00440       Coefficient& row_v = row[v];
00441       if (row_v != 0) {
00442         for (dimension_type j = expr_size; j-- > 0; )
00443           if (j != v)
00444             add_mul_assign(row[j], row_v, expr[j]);
00445         if (not_invertible)
00446           row_v = 0;
00447         else
00448           row_v *= expr[v];
00449       }
00450     }
00451   // Strong normalization also resets the sortedness flag.
00452   x.strong_normalize();
00453 }

PPL::dimension_type Parma_Polyhedra_Library::Constraint_System::num_equalities (  )  const [private]

Returns the number of equality constraints.

Definition at line 293 of file Constraint_System.cc.

References num_inequalities(), Parma_Polyhedra_Library::Linear_System::num_pending_rows(), and Parma_Polyhedra_Library::Matrix::num_rows().

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

00293                                            {
00294   // We are sure that we call this method only when
00295   // the matrix has no pending rows.
00296   assert(num_pending_rows() == 0);
00297   return num_rows() - num_inequalities();
00298 }

PPL::dimension_type Parma_Polyhedra_Library::Constraint_System::num_inequalities (  )  const [private]

Returns the number of inequality constraints.

Definition at line 274 of file Constraint_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 num_equalities().

00274                                              {
00275   // We are sure that we call this method only when
00276   // the matrix has no pending rows.
00277   assert(num_pending_rows() == 0);
00278   const Constraint_System& cs = *this;
00279   dimension_type n = 0;
00280   // If the Linear_System happens to be sorted, take advantage of the fact
00281   // that inequalities are at the bottom of the system.
00282   if (is_sorted())
00283     for (dimension_type i = num_rows(); i > 0 && cs[--i].is_inequality(); )
00284       ++n;
00285   else
00286     for (dimension_type i = num_rows(); i-- > 0 ; )
00287       if (cs[i].is_inequality())
00288         ++n;
00289   return n;
00290 }

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

Applies Gaussian's elimination and back-substitution so as to provide a partial simplification of the system of constraints.

It is assumed that the system has no pending constraints.

Reimplemented from Parma_Polyhedra_Library::Linear_System.

Definition at line 202 of file Constraint_System.inlines.hh.

References Parma_Polyhedra_Library::Linear_System::simplify().

Referenced by Parma_Polyhedra_Library::Polyhedron::OK(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().

00202                             {
00203   Linear_System::simplify();
00204 }

void Parma_Polyhedra_Library::Constraint_System::insert_pending ( const Constraint c  )  [private]

Inserts in *this a copy of the constraint c, increasing the number of space dimensions if needed. It is a pending constraint.

Definition at line 248 of file Constraint_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_System::insert_pending(), Parma_Polyhedra_Library::Linear_System::is_necessarily_closed(), OK(), Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed(), space_dimension(), Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Linear_Row::topology(), and Parma_Polyhedra_Library::Linear_System::topology().

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

00248                                                         {
00249   if (topology() == c.topology())
00250     Linear_System::insert_pending(c);
00251   else
00252     // `*this' and `c' have different topologies.
00253     if (is_necessarily_closed()) {
00254       // Padding the matrix with a columns of zeroes
00255       // corresponding to the epsilon coefficients.
00256       add_zero_columns(1);
00257       set_not_necessarily_closed();
00258       Linear_System::insert_pending(c);
00259     }
00260     else {
00261       // Here `*this' is NNC and `c' is necessarily closed.
00262       // Copying the constraint adding the epsilon coefficient
00263       // and the missing space dimensions, if any.
00264       const dimension_type new_size = 2 + std::max(c.space_dimension(),
00265                                                    space_dimension());
00266       Constraint tmp_c(c, new_size);
00267       tmp_c.set_not_necessarily_closed();
00268       Linear_System::insert_pending(tmp_c);
00269     }
00270   assert(OK());
00271 }

void Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints (  )  [inline, private]


Friends And Related Function Documentation

friend class const_iterator [friend]

Definition at line 289 of file Constraint_System.defs.hh.

friend class Parma_Polyhedra_Library::Polyhedron [friend]

Definition at line 290 of file Constraint_System.defs.hh.

friend class Parma_Polyhedra_Library::LP_Problem [friend]

Definition at line 291 of file Constraint_System.defs.hh.

bool operator== ( const Polyhedron x,
const Polyhedron y 
) [friend]

Returns true if and only if x and y are the same polyhedron.

Note that x and y may be topology- and/or dimension-incompatible polyhedra: in those cases, the value false is returned.

Definition at line 2815 of file Polyhedron_public.cc.

02815                                                         {
02816   // If the two polyhedra are topology-incompatible or dimension-incompatible,
02817   // then they cannot be the same polyhedron.
02818   if (x.topology() != y.topology() || x.space_dim != y.space_dim)
02819     return false;
02820 
02821   if (x.marked_empty())
02822     return y.is_empty();
02823   else if (y.marked_empty())
02824     return x.is_empty();
02825   else if (x.space_dim == 0)
02826     return true;
02827 
02828   switch (x.quick_equivalence_test(y)) {
02829   case Polyhedron::TVB_TRUE:
02830     return true;
02831 
02832   case Polyhedron::TVB_FALSE:
02833     return false;
02834 
02835   default:
02836     if (x.is_included_in(y))
02837       if (x.marked_empty())
02838         return y.is_empty();
02839       else
02840         return y.is_included_in(x);
02841     else
02842       return false;
02843   }
02844 }

std::ostream & operator<< ( std::ostream &  s,
const Constraint_System cs 
) [related]

Output operator.

Writes true if cs is empty. Otherwise, writes on s the constraints of cs, all in one row and separated by ", ".

Definition at line 581 of file Constraint_System.cc.

References begin(), and end().

00581                                                                       {
00582   Constraint_System::const_iterator i = cs.begin();
00583   const Constraint_System::const_iterator cs_end = cs.end();
00584   if (i == cs_end)
00585     s << "true";
00586   else {
00587     while (i != cs_end) {
00588       s << *i++;
00589       if (i != cs_end)
00590         s << ", ";
00591     }
00592   }
00593   return s;
00594 }

Specializes std::swap.

Definition at line 213 of file Constraint_System.inlines.hh.

References swap().

00214                                                   {
00215   x.swap(y);
00216 }


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

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