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

A linear equality or inequality. More...

#include <Constraint.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Constraint:

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

Collaboration graph
[legend]

List of all members.

Public Types

enum  Type { EQUALITY, NONSTRICT_INEQUALITY, STRICT_INEQUALITY }
 The constraint type. More...

Public Member Functions

 Constraint (const Constraint &c)
 Ordinary copy-constructor.
 ~Constraint ()
 Destructor.
Constraintoperator= (const Constraint &c)
 Assignment operator.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
Type type () const
 Returns the constraint type of *this.
bool is_equality () const
 Returns true if and only if *this is an equality constraint.
bool is_inequality () const
 Returns true if and only if *this is an inequality constraint (either strict or non-strict).
bool is_nonstrict_inequality () const
 Returns true if and only if *this is a non-strict inequality constraint.
bool is_strict_inequality () const
 Returns true if and only if *this is a strict inequality constraint.
Coefficient_traits::const_reference coefficient (Variable v) const
 Returns the coefficient of v in *this.
Coefficient_traits::const_reference inhomogeneous_term () const
 Returns the inhomogeneous term of *this.
memory_size_type total_memory_in_bytes () const
 Returns a lower bound to 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.
bool is_tautological () const
 Returns true if and only if *this is a tautology (i.e., an always true constraint).
bool is_inconsistent () const
 Returns true if and only if *this is inconsistent (i.e., an always false constraint).
bool is_equivalent_to (const Constraint &y) const
 Returns true if and only if *this and y are equivalent constraints.
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.
bool OK () const
 Checks if all the invariants are satisfied.
void swap (Constraint &y)
 Swaps *this with y.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Constraint can handle.
static const Constraintzero_dim_false ()
 The unsatisfiable (zero-dimension space) constraint $0 = 1$.
static const Constraintzero_dim_positivity ()
 The true (zero-dimension space) constraint $0 \leq 1$, also known as positivity constraint.

Private Member Functions

friend Parma_Polyhedra_Library::Linear_Expression::Linear_Expression (const Constraint &c)
 Constraint ()
 Default constructor: private and not implemented.
 Constraint (Linear_Expression &e, Type type, Topology topology)
 Builds a constraint of type type and topology topology, stealing the coefficients from e.
void throw_dimension_incompatible (const char *method, const char *name_var, Variable v) const
 Throws a std::invalid_argument exception containing the appropriate error message.
 Constraint (const Constraint &c, dimension_type sz)
 Copy-constructor with given size.
void set_is_equality ()
 Sets the constraint type to EQUALITY.
void set_is_inequality ()
 Sets the constraint to be an inequality.

Static Private Member Functions

static Constraint construct_epsilon_geq_zero ()
 Builds a new copy of the zero-dimension space constraint $\epsilon \geq 0$ (used to implement NNC polyhedra).
static const Constraintepsilon_geq_zero ()
 Returns the zero-dimension space constraint $\epsilon \geq 0$.
static const Constraintepsilon_leq_one ()
 The zero-dimension space constraint $\epsilon \leq 1$ (used to implement NNC polyhedra).

Friends

class Parma_Polyhedra_Library::Congruence
class Parma_Polyhedra_Library::Scalar_Products
class Parma_Polyhedra_Library::Topology_Adjusted_Scalar_Product_Sign
class Parma_Polyhedra_Library::Constraint_System
class Parma_Polyhedra_Library::Constraint_System::const_iterator
class Parma_Polyhedra_Library::Polyhedron
Constraint operator== (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 = e2.
Constraint operator== (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e = n.
Constraint operator== (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n = e.
Constraint operator>= (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 >= e2.
Constraint operator>= (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e >= n.
Constraint operator>= (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n >= e.
Constraint operator<= (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 <= e2.
Constraint operator<= (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e <= n.
Constraint operator<= (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n <= e.
Constraint operator> (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 > e2.
Constraint operator> (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e > n.
Constraint operator> (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n > e.
Constraint operator< (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the constraint e1 < e2.
Constraint operator< (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the constraint e < n.
Constraint operator< (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the constraint n < e.

Related Functions

(Note that these are not member functions.)

bool operator== (const Constraint &x, const Constraint &y)
 Returns true if and only if x is equivalent to y.
bool operator!= (const Constraint &x, const Constraint &y)
 Returns true if and only if x is not equivalent to y.
void swap (Parma_Polyhedra_Library::Constraint &x, Parma_Polyhedra_Library::Constraint &y)
 Specializes std::swap.
std::ostream & operator<< (std::ostream &s, const Constraint &c)
 Output operator.
std::ostream & operator<< (std::ostream &s, const Constraint::Type &t)
 Output operator.


Detailed Description

A linear equality or inequality.

An object of the class Constraint is either:

where $n$ is the dimension of the space, $a_i$ is the integer coefficient of variable $x_i$ and $b$ is the integer inhomogeneous term.

How to build a constraint
Constraints are typically built by applying a relation symbol to a pair of linear expressions. Available relation symbols are equality (==), non-strict inequalities (>= and <=) and strict inequalities (< and >). The space dimension of a constraint is defined as the maximum space dimension of the arguments of its constructor.
In the following examples it is assumed that variables x, y and z are defined as follows:
  Variable x(0);
  Variable y(1);
  Variable z(2);
Example 1
The following code builds the equality constraint $3x + 5y - z = 0$, having space dimension $3$:
  Constraint eq_c(3*x + 5*y - z == 0);
The following code builds the (non-strict) inequality constraint $4x \geq 2y - 13$, having space dimension $2$:
  Constraint ineq_c(4*x >= 2*y - 13);
The corresponding strict inequality constraint $4x > 2y - 13$ is obtained as follows:
  Constraint strict_ineq_c(4*x > 2*y - 13);
An unsatisfiable constraint on the zero-dimension space $\Rset^0$ can be specified as follows: Equivalent, but more involved ways are the following: In contrast, the following code defines an unsatisfiable constraint having space dimension $3$:
  Constraint false_c(0*z == 1);
How to inspect a constraint
Several methods are provided to examine a constraint and extract all the encoded information: its space dimension, its type (equality, non-strict inequality, strict inequality) and the value of its integer coefficients.
Example 2
The following code shows how it is possible to access each single coefficient of a constraint. Given an inequality constraint (in this case $x - 5y + 3z \leq 4$), we construct a new constraint corresponding to its complement (thus, in this case we want to obtain the strict inequality constraint $x - 5y + 3z > 4$).
  Constraint c1(x - 5*y + 3*z <= 4);
  cout << "Constraint c1: " << c1 << endl;
  if (c1.is_equality())
    cout << "Constraint c1 is not an inequality." << endl;
  else {
    Linear_Expression e;
    for (int i = c1.space_dimension() - 1; i >= 0; i--)
      e += c1.coefficient(Variable(i)) * Variable(i);
    e += c1.inhomogeneous_term();
    Constraint c2 = c1.is_strict_inequality() ? (e <= 0) : (e < 0);
    cout << "Complement c2: " << c2 << endl;
  }
The actual output is the following:
  Constraint c1: -A + 5*B - 3*C >= -4
  Complement c2: A - 5*B + 3*C > 4
Note that, in general, the particular output obtained can be syntactically different from the (semantically equivalent) constraint considered.

Definition at line 224 of file Constraint.defs.hh.


Member Enumeration Documentation

The constraint type.

Enumerator:
EQUALITY  The constraint is an equality.
NONSTRICT_INEQUALITY  The constraint is a non-strict inequality.
STRICT_INEQUALITY  The constraint is a strict inequality.

Definition at line 242 of file Constraint.defs.hh.

00242             {
00244     EQUALITY,
00246     NONSTRICT_INEQUALITY,
00248     STRICT_INEQUALITY
00249   };


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Constraint::Constraint ( const Constraint c  )  [inline]

Ordinary copy-constructor.

Definition at line 40 of file Constraint.inlines.hh.

00041   : Linear_Row(c) {
00042 }

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

Destructor.

Definition at line 50 of file Constraint.inlines.hh.

00050                         {
00051 }

Parma_Polyhedra_Library::Constraint::Constraint (  )  [private]

Default constructor: private and not implemented.

Parma_Polyhedra_Library::Constraint::Constraint ( Linear_Expression e,
Type  type,
Topology  topology 
) [inline, private]

Parma_Polyhedra_Library::Constraint::Constraint ( const Constraint c,
dimension_type  sz 
) [inline, private]

Copy-constructor with given size.

Definition at line 45 of file Constraint.inlines.hh.

00046   : Linear_Row(c, sz, sz) {
00047 }


Member Function Documentation

Constraint & Parma_Polyhedra_Library::Constraint::operator= ( const Constraint c  )  [inline]

Assignment operator.

Definition at line 54 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Row::operator=().

00054                                          {
00055   Linear_Row::operator=(c);
00056   return *this;
00057 }

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

Returns the maximum space dimension a Constraint can handle.

Reimplemented from Parma_Polyhedra_Library::Linear_Row.

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

References Parma_Polyhedra_Library::Linear_Row::max_space_dimension().

00060                                 {
00061   return Linear_Row::max_space_dimension();
00062 }

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

Constraint::Type Parma_Polyhedra_Library::Constraint::type (  )  const [inline]

bool Parma_Polyhedra_Library::Constraint::is_equality (  )  const [inline]

bool Parma_Polyhedra_Library::Constraint::is_inequality (  )  const [inline]

bool Parma_Polyhedra_Library::Constraint::is_nonstrict_inequality (  )  const [inline]

Returns true if and only if *this is a non-strict inequality constraint.

Definition at line 92 of file Constraint.inlines.hh.

References NONSTRICT_INEQUALITY, and type().

Referenced by Parma_Polyhedra_Library::BD_Shape< T >::bds_difference_assign(), and Parma_Polyhedra_Library::Polyhedron::expand_space_dimension().

00092                                           {
00093   return type() == NONSTRICT_INEQUALITY;
00094 }

bool Parma_Polyhedra_Library::Constraint::is_strict_inequality (  )  const [inline]

Coefficient_traits::const_reference Parma_Polyhedra_Library::Constraint::coefficient ( Variable  v  )  const [inline]

Returns the coefficient of v in *this.

Exceptions:
std::invalid_argument thrown if the index of v is greater than or equal to the space dimension of *this.

Definition at line 112 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Linear_Row::coefficient(), Parma_Polyhedra_Library::Variable::id(), space_dimension(), Parma_Polyhedra_Library::Variable::space_dimension(), and throw_dimension_incompatible().

Referenced by Parma_Polyhedra_Library::Polyhedron::expand_space_dimension(), Parma_Polyhedra_Library::BD_Shape< T >::extract_bounded_difference(), operator<<(), ppl_Constraint_coefficient(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().

00112                                               {
00113   if (v.space_dimension() > space_dimension())
00114     throw_dimension_incompatible("coefficient(v)", "v", v);
00115   return Linear_Row::coefficient(v.id());
00116 }

Coefficient_traits::const_reference Parma_Polyhedra_Library::Constraint::inhomogeneous_term (  )  const [inline]

const Constraint & Parma_Polyhedra_Library::Constraint::zero_dim_false (  )  [inline, static]

The unsatisfiable (zero-dimension space) constraint $0 = 1$.

Definition at line 291 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Coefficient_one(), and Parma_Polyhedra_Library::Linear_Expression::zero().

Referenced by Parma_Polyhedra_Library::Constraint_System::zero_dim_empty().

00291                            {
00292   static const Constraint zdf(Linear_Expression::zero() == Coefficient_one());
00293   return zdf;
00294 }

const Constraint & Parma_Polyhedra_Library::Constraint::zero_dim_positivity (  )  [inline, static]

The true (zero-dimension space) constraint $0 \leq 1$, also known as positivity constraint.

Definition at line 297 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Coefficient_one(), and Parma_Polyhedra_Library::Linear_Expression::zero().

Referenced by Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints().

00297                                 {
00298   static const Constraint zdp(Linear_Expression::zero() <= Coefficient_one());
00299   return zdp;
00300 }

memory_size_type Parma_Polyhedra_Library::Constraint::total_memory_in_bytes (  )  const [inline]

Returns a lower bound to the total size in bytes of the memory occupied by *this.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 129 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().

00129                                         {
00130   return Linear_Row::total_memory_in_bytes();
00131 }

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

Returns the size in bytes of the memory managed by *this.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 124 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().

00124                                            {
00125   return Linear_Row::external_memory_in_bytes();
00126 }

bool Parma_Polyhedra_Library::Constraint::is_tautological (  )  const

Returns true if and only if *this is a tautology (i.e., an always true constraint).

A tautology can have either one of the following forms:

  • an equality: $\sum_{i=0}^{n-1} 0 x_i + 0 = 0$; or
  • a non-strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b \geq 0$, where $b \geq 0$; or
  • a strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b > 0$, where $b > 0$.

Definition at line 53 of file Constraint.cc.

References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), is_equality(), Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), and Parma_Polyhedra_Library::Row::size().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_constraint(), Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), is_equivalent_to(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().

00053                                      {
00054   assert(size() > 0);
00055   const Constraint& x = *this;
00056   if (x.all_homogeneous_terms_are_zero())
00057     if (is_equality())
00058       return x[0] == 0;
00059     else
00060       // Non-strict inequality constraint.
00061       return x[0] >= 0;
00062   else
00063     // There is a non-zero homogeneous coefficient.
00064     if (is_necessarily_closed())
00065       return false;
00066     else {
00067       // The constraint is NOT necessarily closed.
00068       const dimension_type eps_index = size() - 1;
00069       const int eps_sign = sgn(x[eps_index]);
00070       if (eps_sign > 0)
00071         // We have found the constraint epsilon >= 0.
00072         return true;
00073       if (eps_sign == 0)
00074         // One of the `true' dimensions has a non-zero coefficient.
00075         return false;
00076       else {
00077         // Here the epsilon coefficient is negative: strict inequality.
00078         if (x[0] <= 0)
00079           // A strict inequality such as `lhs - k > 0',
00080           // where k is a non negative integer, cannot be trivially true.
00081           return false;
00082         // Checking for another non-zero coefficient.
00083         for (dimension_type i = eps_index; --i > 0; )
00084           if (x[i] != 0)
00085             return false;
00086         // We have the inequality `k > 0',
00087         // where k is a positive integer.
00088         return true;
00089       }
00090     }
00091 }

bool Parma_Polyhedra_Library::Constraint::is_inconsistent (  )  const

Returns true if and only if *this is inconsistent (i.e., an always false constraint).

An inconsistent constraint can have either one of the following forms:

  • an equality: $\sum_{i=0}^{n-1} 0 x_i + b = 0$, where $b \neq 0$; or
  • a non-strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b \geq 0$, where $b < 0$; or
  • a strict inequality: $\sum_{i=0}^{n-1} 0 x_i + b > 0$, where $b \leq 0$.

Definition at line 94 of file Constraint.cc.

References Parma_Polyhedra_Library::Linear_Row::all_homogeneous_terms_are_zero(), is_equality(), Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), and Parma_Polyhedra_Library::Row::size().

Referenced by is_equivalent_to(), Parma_Polyhedra_Library::Polyhedron::poly_difference_assign(), Parma_Polyhedra_Library::Polyhedron::relation_with(), and Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box().

00094                                      {
00095   assert(size() > 0);
00096   const Constraint& x = *this;
00097   if (x.all_homogeneous_terms_are_zero())
00098     // The inhomogeneous term is the only non-zero coefficient.
00099     if (is_equality())
00100       return x[0] != 0;
00101     else
00102       // Non-strict inequality constraint.
00103       return x[0] < 0;
00104   else
00105     // There is a non-zero homogeneous coefficient.
00106     if (is_necessarily_closed())
00107       return false;
00108     else {
00109       // The constraint is NOT necessarily closed.
00110       const dimension_type eps_index = size() - 1;
00111       if (x[eps_index] >= 0)
00112         // If positive, we have found the constraint epsilon >= 0.
00113         // If zero, one of the `true' dimensions has a non-zero coefficient.
00114         // In both cases, it is not trivially false.
00115         return false;
00116       else {
00117         // Here the epsilon coefficient is negative: strict inequality.
00118         if (x[0] > 0)
00119           // A strict inequality such as `lhs + k > 0',
00120           // where k is a positive integer, cannot be trivially false.
00121           return false;
00122         // Checking for another non-zero coefficient.
00123         for (dimension_type i = eps_index; --i > 0; )
00124           if (x[i] != 0)
00125             return false;
00126         // We have the inequality `k > 0',
00127         // where k is zero or a negative integer.
00128         return true;
00129       }
00130     }
00131 }

bool Parma_Polyhedra_Library::Constraint::is_equivalent_to ( const Constraint y  )  const

Returns true if and only if *this and y are equivalent constraints.

Constraints having different space dimensions are not equivalent. Note that constraints having different types may nonetheless be equivalent, if they both are tautologies or inconsistent.

Definition at line 134 of file Constraint.cc.

References is_inconsistent(), is_tautological(), Parma_Polyhedra_Library::Row::normalize(), space_dimension(), STRICT_INEQUALITY, and type().

Referenced by operator!=(), and operator==().

00134                                                          {
00135   const Constraint& x = *this;
00136   const dimension_type x_space_dim = x.space_dimension();
00137   if (x_space_dim != y.space_dimension())
00138     return false;
00139 
00140   const Type x_type = x.type();
00141   if (x_type != y.type()) {
00142     // Check for special cases.
00143     if (x.is_tautological())
00144       return y.is_tautological();
00145     else
00146       return x.is_inconsistent() && y.is_inconsistent();
00147   }
00148 
00149   if (x_type == STRICT_INEQUALITY) {
00150     // Due to the presence of epsilon-coefficients, syntactically
00151     // different strict inequalities may actually encode the same
00152     // topologically open half-space.
00153     // First, drop the epsilon-coefficient ...
00154     Linear_Expression x_expr(x);
00155     Linear_Expression y_expr(y);
00156     // ... then, re-normalize ...
00157     x_expr.normalize();
00158     y_expr.normalize();
00159     // ... and finally check for syntactic equality.
00160     for (dimension_type i = x_space_dim + 1; i-- > 0; )
00161       if (x_expr[i] != y_expr[i])
00162         return false;
00163     return true;
00164   }
00165 
00166   // `x' and 'y' are of the same type and they are not strict inequalities;
00167   // thus, the epsilon-coefficient, if present, is zero.
00168   // It is sufficient to check for syntactic equality.
00169   for (dimension_type i = x_space_dim + 1; i-- > 0; )
00170     if (x[i] != y[i])
00171       return false;
00172   return true;
00173 }

void Parma_Polyhedra_Library::Constraint::ascii_dump (  )  const

Writes to std::cerr an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Linear_Row.

void Parma_Polyhedra_Library::Constraint::ascii_dump ( std::ostream &  s  )  const [inline]

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Linear_Row.

Definition at line 316 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Linear_Row::ascii_dump().

00316                                           {
00317   Linear_Row::ascii_dump(s);
00318 }

void Parma_Polyhedra_Library::Constraint::print (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Linear_Row.

bool Parma_Polyhedra_Library::Constraint::ascii_load ( std::istream &  s  )  [inline]

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

Definition at line 321 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Linear_Row::ascii_load().

00321                                     {
00322   return Linear_Row::ascii_load(s);
00323 }

bool Parma_Polyhedra_Library::Constraint::OK (  )  const

Checks if all the invariants are satisfied.

Definition at line 240 of file Constraint.cc.

References Parma_Polyhedra_Library::Linear_Row::is_necessarily_closed(), Parma_Polyhedra_Library::Row::size(), and Parma_Polyhedra_Library::Linear_Row::strong_normalize().

00240                         {
00241   // Topology consistency check.
00242   const dimension_type min_size = is_necessarily_closed() ? 1 : 2;
00243   if (size() < min_size) {
00244 #ifndef NDEBUG
00245     std::cerr << "Constraint has fewer coefficients than the minimum "
00246               << "allowed by its topology:"
00247               << std::endl
00248               << "size is " << size()
00249               << ", minimum is " << min_size << "."
00250               << std::endl;
00251 #endif
00252     return false;
00253   }
00254 
00255   // Normalization check.
00256   Constraint tmp = *this;
00257   tmp.strong_normalize();
00258   if (tmp != *this) {
00259 #ifndef NDEBUG
00260     std::cerr << "Constraint is not strongly normalized as it should be."
00261               << std::endl;
00262 #endif
00263     return false;
00264   }
00265 
00266   // All tests passed.
00267   return true;
00268 }

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

Swaps *this with y.

Definition at line 326 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Linear_Row::swap().

Referenced by swap().

00326                               {
00327   Linear_Row::swap(y);
00328 }

Parma_Polyhedra_Library::Constraint::Parma_Polyhedra_Library::Linear_Expression::Linear_Expression ( const Constraint c  )  [private]

void Parma_Polyhedra_Library::Constraint::throw_dimension_incompatible ( const char *  method,
const char *  name_var,
Variable  v 
) const [private]

Throws a std::invalid_argument exception containing the appropriate error message.

Definition at line 35 of file Constraint.cc.

References Parma_Polyhedra_Library::Variable::space_dimension(), and space_dimension().

Referenced by coefficient().

00037                                                                       {
00038   std::ostringstream s;
00039   s << "PPL::Constraint::" << method << ":" << std::endl
00040     << "this->space_dimension() == " << space_dimension() << ", "
00041     << name_var << ".space_dimension() == " << v.space_dimension() << ".";
00042   throw std::invalid_argument(s.str());
00043 }

PPL::Constraint Parma_Polyhedra_Library::Constraint::construct_epsilon_geq_zero (  )  [static, private]

Builds a new copy of the zero-dimension space constraint $\epsilon \geq 0$ (used to implement NNC polyhedra).

Definition at line 46 of file Constraint.cc.

References NONSTRICT_INEQUALITY, and Parma_Polyhedra_Library::NOT_NECESSARILY_CLOSED.

Referenced by epsilon_geq_zero().

00046                                           {
00047   Linear_Expression e = Variable(0);
00048   Constraint c(e, NONSTRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
00049   return c;
00050 }

const Constraint & Parma_Polyhedra_Library::Constraint::epsilon_geq_zero (  )  [inline, static, private]

Returns the zero-dimension space constraint $\epsilon \geq 0$.

Definition at line 303 of file Constraint.inlines.hh.

References construct_epsilon_geq_zero().

Referenced by Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints().

00303                              {
00304   static const Constraint eps_geq_zero = construct_epsilon_geq_zero();
00305   return eps_geq_zero;
00306 }

const Constraint & Parma_Polyhedra_Library::Constraint::epsilon_leq_one (  )  [inline, static, private]

void Parma_Polyhedra_Library::Constraint::set_is_equality (  )  [inline, private]

void Parma_Polyhedra_Library::Constraint::set_is_inequality (  )  [inline, private]

Sets the constraint to be an inequality.

Whether the constraint type will become NONSTRICT_INEQUALITY or STRICT_INEQUALITY depends on the topology and the value of the low-level coefficients of the constraint.

Definition at line 107 of file Constraint.inlines.hh.

References Parma_Polyhedra_Library::Linear_Row::set_is_ray_or_point_or_inequality().

00107                               {
00108   set_is_ray_or_point_or_inequality();
00109 }


Friends And Related Function Documentation

friend class Parma_Polyhedra_Library::Congruence [friend]

Definition at line 361 of file Constraint.defs.hh.

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

Definition at line 363 of file Constraint.defs.hh.

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

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

friend class Parma_Polyhedra_Library::Polyhedron [friend]

Definition at line 367 of file Constraint.defs.hh.

Constraint operator== ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 = e2.

Definition at line 147 of file Constraint.inlines.hh.

00147                                                                      {
00148   Linear_Expression diff = e1 - e2;
00149   Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
00150   // Enforce normalization.
00151   c.strong_normalize();
00152   return c;
00153 }

Constraint operator== ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e = n.

Definition at line 220 of file Constraint.inlines.hh.

00220                                                                             {
00221   Linear_Expression diff = e - n;
00222   Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
00223   // Enforce normalization.
00224   c.strong_normalize();
00225   return c;
00226 }

Constraint operator== ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n = e.

Definition at line 186 of file Constraint.inlines.hh.

00186                                                                             {
00187   Linear_Expression diff = n - e;
00188   Constraint c(diff, Constraint::EQUALITY, NECESSARILY_CLOSED);
00189   // Enforce normalization.
00190   c.strong_normalize();
00191   return c;
00192 }

Constraint operator>= ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 >= e2.

Definition at line 157 of file Constraint.inlines.hh.

00157                                                                      {
00158   Linear_Expression diff = e1 - e2;
00159   Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
00160   // Enforce normalization.
00161   c.normalize();
00162   return c;
00163 }

Constraint operator>= ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e >= n.

Definition at line 230 of file Constraint.inlines.hh.

00230                                                                             {
00231   Linear_Expression diff = e - n;
00232   Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
00233   // Enforce normalization.
00234   c.normalize();
00235   return c;
00236 }

Constraint operator>= ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n >= e.

Definition at line 196 of file Constraint.inlines.hh.

00196                                                                             {
00197   Linear_Expression diff = n - e;
00198   Constraint c(diff, Constraint::NONSTRICT_INEQUALITY, NECESSARILY_CLOSED);
00199   // Enforce normalization.
00200   c.normalize();
00201   return c;
00202 }

Constraint operator<= ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 <= e2.

Definition at line 256 of file Constraint.inlines.hh.

00256                                                                      {
00257   return e2 >= e1;
00258 }

Constraint operator<= ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e <= n.

Definition at line 268 of file Constraint.inlines.hh.

00268                                                                             {
00269   return n >= e;
00270 }

Constraint operator<= ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n <= e.

Definition at line 262 of file Constraint.inlines.hh.

00262                                                                             {
00263   return e >= n;
00264 }

Constraint operator> ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 > e2.

Definition at line 167 of file Constraint.inlines.hh.

00167                                                                     {
00168   Linear_Expression diff;
00169   // Setting the epsilon coefficient to -1.
00170   // NOTE: this also enforces normalization.
00171   const dimension_type e1_dim = e1.space_dimension();
00172   const dimension_type e2_dim = e2.space_dimension();
00173   if (e1_dim > e2_dim)
00174     diff -= Variable(e1_dim);
00175   else
00176     diff -= Variable(e2_dim);
00177   diff += e1;
00178   diff -= e2;
00179 
00180   Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
00181   return c;
00182 }

Constraint operator> ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e > n.

Definition at line 240 of file Constraint.inlines.hh.

00240                                                                            {
00241   Linear_Expression diff;
00242   // Setting the epsilon coefficient to -1.
00243   // NOTE: this also enforces normalization.
00244   diff -= Variable(e.space_dimension());
00245   diff += e;
00246   diff -= n;
00247 
00248   Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
00249   c.set_not_necessarily_closed();
00250   c.set_is_inequality();
00251   return c;
00252 }

Constraint operator> ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n > e.

Definition at line 206 of file Constraint.inlines.hh.

00206                                                                            {
00207   Linear_Expression diff;
00208   // Setting the epsilon coefficient to -1.
00209   // NOTE: this also enforces normalization.
00210   diff -= Variable(e.space_dimension());
00211   diff += n;
00212   diff -= e;
00213 
00214   Constraint c(diff, Constraint::STRICT_INEQUALITY, NOT_NECESSARILY_CLOSED);
00215   return c;
00216 }

Constraint operator< ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Returns the constraint e1 < e2.

Definition at line 274 of file Constraint.inlines.hh.

00274                                                                     {
00275   return e2 > e1;
00276 }

Constraint operator< ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [friend]

Returns the constraint e < n.

Definition at line 286 of file Constraint.inlines.hh.

00286                                                                            {
00287   return n > e;
00288 }

Constraint operator< ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [friend]

Returns the constraint n < e.

Definition at line 280 of file Constraint.inlines.hh.

00280                                                                            {
00281   return e > n;
00282 }

bool operator== ( const Constraint x,
const Constraint y 
) [related]

Returns true if and only if x is equivalent to y.

Definition at line 135 of file Constraint.inlines.hh.

References is_equivalent_to().

00135                                                      {
00136   return x.is_equivalent_to(y);
00137 }

bool operator!= ( const Constraint x,
const Constraint y 
) [related]

Returns true if and only if x is not equivalent to y.

Definition at line 141 of file Constraint.inlines.hh.

References is_equivalent_to().

00141                                                      {
00142   return !x.is_equivalent_to(y);
00143 }

Specializes std::swap.

Definition at line 336 of file Constraint.inlines.hh.

References swap().

00337                                            {
00338   x.swap(y);
00339 }

std::ostream & operator<< ( std::ostream &  s,
const Constraint c 
) [related]

Output operator.

Definition at line 177 of file Constraint.cc.

References coefficient(), Parma_Polyhedra_Library::Coefficient_zero(), EQUALITY, inhomogeneous_term(), Parma_Polyhedra_Library::neg_assign(), NONSTRICT_INEQUALITY, relation_symbol(), space_dimension(), STRICT_INEQUALITY, and type().

00177                                                               {
00178   const int num_variables = c.space_dimension();
00179   bool first = true;
00180   for (int v = 0; v < num_variables; ++v) {
00181     Coefficient cv = c.coefficient(Variable(v));
00182     if (cv != 0) {
00183       if (!first) {
00184         if (cv > 0)
00185           s << " + ";
00186         else {
00187           s << " - ";
00188           neg_assign(cv);
00189         }
00190       }
00191       else
00192         first = false;
00193       if (cv == -1)
00194         s << "-";
00195       else if (cv != 1)
00196         s << cv << "*";
00197       s << PPL::Variable(v);
00198     }
00199   }
00200   if (first)
00201     s << Coefficient_zero();
00202   const char* relation_symbol = 0;
00203   switch (c.type()) {
00204   case Constraint::EQUALITY:
00205     relation_symbol = " = ";
00206     break;
00207   case Constraint::NONSTRICT_INEQUALITY:
00208     relation_symbol = " >= ";
00209     break;
00210   case Constraint::STRICT_INEQUALITY:
00211     relation_symbol = " > ";
00212     break;
00213   }
00214   s << relation_symbol << -c.inhomogeneous_term();
00215   return s;
00216 }

std::ostream & operator<< ( std::ostream &  s,
const Constraint::Type t 
) [related]

Output operator.

Definition at line 220 of file Constraint.cc.

References EQUALITY, NONSTRICT_INEQUALITY, and STRICT_INEQUALITY.

00220                                                                   {
00221   const char* n = 0;
00222   switch (t) {
00223   case Constraint::EQUALITY:
00224     n = "EQUALITY";
00225     break;
00226   case Constraint::NONSTRICT_INEQUALITY:
00227     n = "NONSTRICT_INEQUALITY";
00228     break;
00229   case Constraint::STRICT_INEQUALITY:
00230     n = "STRICT_INEQUALITY";
00231     break;
00232   }
00233   s << n;
00234   return s;
00235 }


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

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