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

A linear congruence. More...

#include <Congruence.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Congruence:

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

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Congruence (const Congruence &cg)
 Ordinary copy-constructor.
 Congruence (const Constraint &c)
 Copy-constructs (modulo 0) from equality constraint c.
 ~Congruence ()
 Destructor.
Congruenceoperator= (const Congruence &cg)
 Assignment operator.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
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.
Coefficient_traits::const_reference modulus () const
 Returns a const reference to the modulus of *this.
Congruenceoperator/= (const Coefficient_traits::const_reference k)
 Multiplies k into the modulus of *this.
bool is_trivial_true () const
 Returns true if and only if *this is a trivially true congruence.
bool is_trivial_false () const
 Returns true if and only if *this is a trivially false congruence.
bool is_proper_congruence () const
 Returns true if the modulus is greater than zero.
bool is_equality () const
 Returns true if *this is an equality.
bool is_equal_at_dimension (dimension_type dim, const Congruence &cg) const
 Returns true if *this is equal to cg in dimension dim.
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.
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 of the internal representation of *this.
bool OK () const
 Checks if all the invariants are satisfied.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Congruence can handle.
static const Congruencezero_dim_integrality ()
 Returns a reference to the true (zero-dimension space) congruence $0 = 1 \pmod{1}$, also known as the integrality congruence.
static const Congruencezero_dim_false ()
 Returns a reference to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$.

Protected Member Functions

void sign_normalize ()
 Normalizes the signs.
void normalize ()
 Normalizes signs and the inhomogeneous term.
void strong_normalize ()
 Calls normalize, then divides out common factors.

Private Member Functions

Coefficientmodulus ()
 Returns a reference to the modulus of *this.
void set_is_equality ()
 Marks this congruence as a linear equality.
void negate (dimension_type start, dimension_type end)
 Negates the elements from index start to index end.
 Congruence ()
 Default constructor: private and not implemented.
 Congruence (const Congruence &cg, dimension_type sz, dimension_type capacity)
 Copy-constructs with specified size and capacity.
 Congruence (const Constraint &c, dimension_type sz, dimension_type capacity)
 Constructs from a constraint, with specified size and capacity.
 Congruence (const Congruence &cg, Coefficient_traits::const_reference k)
 Copy-constructs from cg, multiplying k into the modulus.
 Congruence (Linear_Expression &le, Coefficient_traits::const_reference m, bool capacity=true)
 Constructs from Linear_Expression le, using modulus m.
void swap (Congruence &y)
 Swaps *this with y.
void throw_invalid_argument (const char *method, const char *message) const
 Throws a std::invalid_argument exception containing error message message.
void throw_dimension_incompatible (const char *method, const char *v_name, Variable v) const
 Throws a std::invalid_argument exception containing the appropriate error message.

Friends

class PPL::Scalar_Products
class PPL::Congruence_System
class PPL::Congruence_System::const_iterator
class PPL::Grid
class PPL::Linear_Expression
Congruence PPL::operator%= (const Linear_Expression &e1, const Linear_Expression &e2)
Congruence PPL::operator%= (const Linear_Expression &e, const Coefficient_traits::const_reference n)
Congruence PPL::operator/ (const Congruence &cg, const Coefficient_traits::const_reference k)
Congruence PPL::operator/ (const Constraint &c, const Coefficient_traits::const_reference m)
bool PPL::operator== (const Congruence &x, const Congruence &y)
bool PPL::operator!= (const Congruence &x, const Congruence &y)
std::ostream & PPL::IO_Operators::operator<< (std::ostream &s, const Congruence_System &cgs)
void swap (PPL::Congruence &x, PPL::Congruence &y)
 Specializes std::swap.

Related Functions

(Note that these are not member functions.)

std::ostream & operator<< (std::ostream &s, const Congruence &c)
 Output operators.
bool operator== (const Congruence &x, const Congruence &y)
 Returns true if and only if x and y are equivalent.
bool operator!= (const Congruence &x, const Congruence &y)
 Returns false if and only if x and y are equivalent.
Congruence operator/ (const Congruence &cg, const Coefficient_traits::const_reference k)
 Returns a copy of cg, multiplying k into the copy's modulus.
Congruence operator/ (const Constraint &c, const Coefficient_traits::const_reference m)
 Creates a congruence from c, with m as the modulus.


Detailed Description

A linear congruence.

An object of the class Congruence is a congruence:

where $n$ is the dimension of the space, $a_i$ is the integer coefficient of variable $x_i$, $b$ is the integer inhomogeneous term and $m$ is the integer modulus; if $m = 0$, then $\cg$ represents the equality congruence $\sum_{i=0}^{n-1} a_i x_i + b = 0$ and, if $m \neq 0$, then the congruence $\cg$ is said to be a proper congruence.

How to build a congruence
Congruences $\pmod{1}$ are typically built by applying the congruence symbol `%=' to a pair of linear expressions. Congruences with modulus m are typically constructed by building a congruence $\pmod{1}$ using the given pair of linear expressions and then adding the modulus m using the modulus symbol is `/'.
The space dimension of a congruence 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 congruence $3x + 5y - z = 0$, having space dimension $3$:
  Congruence eq_cg((3*x + 5*y - z %= 0) / 0);
The following code builds the congruence $4x = 2y - 13 \pmod{1}$, having space dimension $2$:
  Congruence mod1_cg(4*x %= 2*y - 13);
The following code builds the congruence $4x = 2y - 13 \pmod{2}$, having space dimension $2$:
  Congruence mod2_cg((4*x %= 2*y - 13) / 2);
An unsatisfiable congruence on the zero-dimension space $\Rset^0$ can be specified as follows: Equivalent, but more involved ways are the following:
  Congruence false_cg1((Linear_Expression::zero() %= 1) / 0);
  Congruence false_cg2((Linear_Expression::zero() %= 1) / 2);
In contrast, the following code defines an unsatisfiable congruence having space dimension $3$:
  Congruence false_cg3((0*z %= 1) / 0);
How to inspect a congruence
Several methods are provided to examine a congruence and extract all the encoded information: its space dimension, its modulus and the value of its integer coefficients.
Example 2
The following code shows how it is possible to access the modulus as well as each of the coefficients. Given a congruence with linear expression e and modulus m (in this case $x - 5y + 3z = 4 \pmod{5}$), we construct a new congruence with the same modulus m but where the linear expression is $2 e$ ($2x - 10y + 6z = 8 \pmod{5}$).
  Congruence cg1((x - 5*y + 3*z %= 4) / 5);
  cout << "Congruence cg1: " << cg1 << endl;
  Coefficient m = cg1.modulus();
  if (m == 0)
    cout << "Congruence cg1 is an equality." << endl;
  else {
    Linear_Expression e;
    for (int i = cg1.space_dimension() - 1; i >= 0; --i)
      e += 2 * cg1.coefficient(Variable(i)) * Variable(i);
      e += 2 * cg1.inhomogeneous_term();
    Congruence cg2((e %= 0) / m);
    cout << "Congruence cg2: " << cg2 << endl;
  }
The actual output could be the following:
  Congruence cg1: A - 5*B + 3*C %= 4 / 5
  Congruence cg2: 2*A - 10*B + 6*C %= 8 / 5
Note that, in general, the particular output obtained can be syntactically different from the (semantically equivalent) congruence considered.

Definition at line 215 of file Congruence.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Congruence::Congruence ( const Congruence cg  )  [inline]

Ordinary copy-constructor.

Definition at line 34 of file Congruence.inlines.hh.

00035   : Row(cg) {
00036 }

Parma_Polyhedra_Library::Congruence::Congruence ( const Constraint c  )  [explicit]

Copy-constructs (modulo 0) from equality constraint c.

Exceptions:
std::invalid_argument Thrown if c is a relation.

Definition at line 36 of file Congruence.cc.

References Parma_Polyhedra_Library::Row::size().

00037   : Row(c.is_equality()
00038         ? c
00039         : (throw_invalid_argument("Congruence(c)",
00040                                   "constraint c must be an equality."),
00041            c),
00042         c.space_dimension() + 2,
00043         compute_capacity(c.space_dimension() + 2, Row::max_size())) {
00044 
00045   (*this)[size()-1] = 0;
00046 }

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

Destructor.

Definition at line 55 of file Congruence.inlines.hh.

00055                         {
00056 }

Parma_Polyhedra_Library::Congruence::Congruence (  )  [private]

Default constructor: private and not implemented.

Parma_Polyhedra_Library::Congruence::Congruence ( const Congruence cg,
dimension_type  sz,
dimension_type  capacity 
) [inline, private]

Copy-constructs with specified size and capacity.

Definition at line 39 of file Congruence.inlines.hh.

00041   : Row(cg, sz, capacity) {
00042 }

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

Constructs from a constraint, with specified size and capacity.

Definition at line 48 of file Congruence.cc.

00050   : Row(c.is_equality()
00051         ? c
00052         : (throw_invalid_argument("Congruence(c)",
00053                                   "constraint c must be an equality."),
00054            c),
00055         sz,
00056         capacity) {
00057 
00058   (*this)[sz-1] = 0;
00059 }

Parma_Polyhedra_Library::Congruence::Congruence ( const Congruence cg,
Coefficient_traits::const_reference  k 
) [inline, private]

Copy-constructs from cg, multiplying k into the modulus.

If cg represents the congruence $ e_1 = e_2 \pmod{m}$, then the result represents the congruence $ e_1 = e_2 \pmod{mk}$.

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

References Parma_Polyhedra_Library::Row::size().

00047   : Row(cg) {
00048   if (k >= 0)
00049     (*this)[size()-1] *= k;
00050   else
00051     (*this)[size()-1] *= -k;
00052 }

Parma_Polyhedra_Library::Congruence::Congruence ( Linear_Expression le,
Coefficient_traits::const_reference  m,
bool  capacity = true 
) [inline, private]

Constructs from Linear_Expression le, using modulus m.

Builds a congruence with modulus m, stealing the coefficients from le.

Parameters:
le The Linear_Expression holding the coefficients.
m The modulus for the congruence.
capacity If true then the size of the le row is expanded and the modulus is stored in the extra space. In this case it is assumed that le has spare capacity of at least one element. If false then the modulus is stored in the last element of the le row.

Definition at line 203 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::expand_within_capacity(), Parma_Polyhedra_Library::Row::size(), and Parma_Polyhedra_Library::Row::swap().

00205                                       {
00206   Row::swap(static_cast<Row&>(le));
00207   if (capacity)
00208     Row::expand_within_capacity(size()+1);
00209   if (m >= 0)
00210     (*this)[size()-1] = m;
00211   else
00212     (*this)[size()-1] = -m;
00213 }


Member Function Documentation

Congruence & Parma_Polyhedra_Library::Congruence::operator= ( const Congruence cg  )  [inline]

Assignment operator.

Definition at line 72 of file Congruence.inlines.hh.

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

00072                                          {
00073   Row::operator=(c);
00074   return *this;
00075 }

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

Returns the maximum space dimension a Congruence can handle.

Definition at line 130 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::max_size().

00130                                 {
00131   // The first coefficient holds the inhomogeneous term, while
00132   // the last coefficient is for the modulus.
00133   return max_size() - 2;
00134 }

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

Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::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 142 of file Congruence.inlines.hh.

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

Referenced by Parma_Polyhedra_Library::Grid::expand_space_dimension(), and operator<<().

00142                                               {
00143   if (v.space_dimension() > space_dimension())
00144     throw_dimension_incompatible("coefficient(v)", "v", v);
00145   return (*this)[v.id()+1];
00146 }

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

Returns the inhomogeneous term of *this.

Definition at line 149 of file Congruence.inlines.hh.

Referenced by Parma_Polyhedra_Library::Grid::expand_space_dimension(), is_trivial_false(), is_trivial_true(), operator<<(), Parma_Polyhedra_Library::Grid::relation_with(), and Parma_Polyhedra_Library::Grid::simplify().

00149                                      {
00150   return (*this)[0];
00151 }

Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::modulus (  )  const [inline]

Congruence & Parma_Polyhedra_Library::Congruence::operator/= ( const Coefficient_traits::const_reference  k  )  [inline]

Multiplies k into the modulus of *this.

If called with *this representing the congruence $ e_1 = e_2 \pmod{m}$, then it returns with *this representing the congruence $ e_1 = e_2 \pmod{mk}$.

Definition at line 105 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::size().

00105                                                                 {
00106   if (k >= 0)
00107     (*this)[size()-1] *= k;
00108   else
00109     (*this)[size()-1] *= -k;
00110   return *this;
00111 }

bool Parma_Polyhedra_Library::Congruence::is_trivial_true (  )  const

Returns true if and only if *this is a trivially true congruence.

Trivially true congruences are of one the following two forms:

  • an equality: $\sum_{i=0}^{n-1} 0 x_i + 0 == 0$; or
  • a proper congruence: $\sum_{i=0}^{n-1} 0 x_i + b \%= 0 / m$, where n is the space dimension and m is the modulus.

Definition at line 181 of file Congruence.cc.

References inhomogeneous_term(), is_equality(), is_proper_congruence(), modulus(), and space_dimension().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), and Parma_Polyhedra_Library::Grid::add_congruence().

00181                                      {
00182   if ((is_equality() && inhomogeneous_term() == 0)
00183       || (is_proper_congruence()
00184           && (inhomogeneous_term() % modulus() == 0))) {
00185     for (unsigned i = 1; i <= space_dimension(); i++)
00186       if ((*this)[i] != 0)
00187         return false;
00188     return true;
00189   }
00190   return false;
00191 }

bool Parma_Polyhedra_Library::Congruence::is_trivial_false (  )  const

Returns true if and only if *this is a trivially false congruence.

Trivially false congruences have one of the following two forms:

  • an equality: $\sum_{i=0}^{n-1} 0 x_i + b == 0$ where $b \neq 0$; or
  • a congruence: $\sum_{i=0}^{n-1} 0 x_i + b \%= 0 / m$, where $b \neq 0 \pmod{m}$.

Definition at line 194 of file Congruence.cc.

References inhomogeneous_term(), is_proper_congruence(), modulus(), and space_dimension().

00194                                       {
00195   if (inhomogeneous_term() == 0
00196       || (is_proper_congruence()
00197           && ((inhomogeneous_term() % modulus()) == 0)))
00198     return false;
00199   for (unsigned i = 1; i <= space_dimension(); i++)
00200     if ((*this)[i] != 0)
00201       return false;
00202   return true;
00203 }

bool Parma_Polyhedra_Library::Congruence::is_proper_congruence (  )  const [inline]

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

bool Parma_Polyhedra_Library::Congruence::is_equal_at_dimension ( dimension_type  dim,
const Congruence cg 
) const [inline]

Returns true if *this is equal to cg in dimension dim.

Definition at line 176 of file Congruence.inlines.hh.

References modulus(), and Parma_Polyhedra_Library::Row::operator[]().

Referenced by Parma_Polyhedra_Library::Grid::select_wider_congruences().

00177                                                               {
00178   return operator[](dim) * cg.modulus() == cg[dim] * modulus();
00179 }

const Congruence & Parma_Polyhedra_Library::Congruence::zero_dim_integrality (  )  [inline, static]

Returns a reference to the true (zero-dimension space) congruence $0 = 1 \pmod{1}$, also known as the integrality congruence.

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

References Parma_Polyhedra_Library::Linear_Expression::zero().

Referenced by Parma_Polyhedra_Library::Grid::Grid(), and Parma_Polyhedra_Library::Grid::minimized_congruences().

00059                                  {
00060   static const Congruence zdi(Linear_Expression::zero() %= Coefficient(-1));
00061   return zdi;
00062 }

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

Returns a reference to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$.

Definition at line 65 of file Congruence.inlines.hh.

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

Referenced by Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Grid::set_empty(), and Parma_Polyhedra_Library::Congruence_System::zero_dim_empty().

00065                            {
00066   static const Congruence
00067     zdf((Linear_Expression::zero() %= Coefficient_one()) / 0);
00068   return zdf;
00069 }

memory_size_type Parma_Polyhedra_Library::Congruence::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 198 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Checked::total_memory_in_bytes().

00198                                         {
00199   return Row::total_memory_in_bytes();
00200 }

memory_size_type Parma_Polyhedra_Library::Congruence::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 193 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Checked::external_memory_in_bytes().

00193                                            {
00194   return Row::external_memory_in_bytes();
00195 }

void Parma_Polyhedra_Library::Congruence::ascii_dump (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Row.

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 206 of file Congruence.cc.

References Parma_Polyhedra_Library::Row::size().

00206                                              {
00207   const Row& x = *this;
00208   dimension_type x_size = x.size();
00209   for (dimension_type i = 0; i < x_size - 1; ++i)
00210     s << x[i] << ' ';
00211   if (x_size)
00212     s << "m " << x[x_size - 1];
00213   s << std::endl;
00214 }

void Parma_Polyhedra_Library::Congruence::print (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Row.

bool Parma_Polyhedra_Library::Congruence::ascii_load ( std::istream &  s  ) 

Loads from s an ASCII representation of the internal representation of *this.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 219 of file Congruence.cc.

References Parma_Polyhedra_Library::Row::size().

00219                                        {
00220   std::string str;
00221   Congruence& x = *this;
00222   dimension_type col = 0;
00223   while (col < x.size() - 1)
00224     if (!(s >> x[col]))
00225       return false;
00226     else
00227       col++;
00228 
00229   if (!(s >> str) || str.compare("m"))
00230     return false;
00231 
00232   if (!(s >> x[col]))
00233     return false;
00234 
00235   return true;
00236 }

bool Parma_Polyhedra_Library::Congruence::OK (  )  const

Checks if all the invariants are satisfied.

Definition at line 239 of file Congruence.cc.

References modulus().

Referenced by Parma_Polyhedra_Library::Congruence_System::OK().

00239                         {
00240   // Modulus check.
00241   if (modulus() < 0) {
00242 #ifndef NDEBUG
00243     std::cerr << "Congruence has a negative modulus " << modulus() << "."
00244               << std::endl;
00245 #endif
00246     return false;
00247   }
00248 
00249   // All tests passed.
00250   return true;
00251 }

void Parma_Polyhedra_Library::Congruence::sign_normalize (  )  [protected]

Normalizes the signs.

The signs of the coefficients and the inhomogeneous term are normalized, leaving the first non-zero homogeneous coefficient positive.

Definition at line 62 of file Congruence.cc.

References Parma_Polyhedra_Library::neg_assign(), and Parma_Polyhedra_Library::Row::size().

Referenced by normalize().

00062                               {
00063   Row& x = *this;
00064   const dimension_type sz = x.size() - 1;
00065   // `first_non_zero' indicates the index of the first
00066   // coefficient of the row different from zero, disregarding
00067   // the very first coefficient (inhomogeneous term).
00068   dimension_type first_non_zero;
00069   for (first_non_zero = 1; first_non_zero < sz; ++first_non_zero)
00070     if (x[first_non_zero] != 0)
00071       break;
00072   if (first_non_zero < sz)
00073     // If the first non-zero coefficient of the row is negative,
00074     // negate all the coefficients and the inhomogeneous term.
00075     if (x[first_non_zero] < 0) {
00076       for (dimension_type j = first_non_zero; j < sz; ++j)
00077         neg_assign(x[j]);
00078       // Also negate the inhomogeneous term.
00079       neg_assign(x[0]);
00080     }
00081 }

void Parma_Polyhedra_Library::Congruence::normalize (  )  [protected]

Normalizes signs and the inhomogeneous term.

Applies sign_normalize, then reduces the inhomogeneous term to the smallest possible positive number.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 84 of file Congruence.cc.

References modulus(), sign_normalize(), and Parma_Polyhedra_Library::Row::size().

Referenced by strong_normalize().

00084                          {
00085   sign_normalize();
00086 
00087   dimension_type sz = size();
00088   if (sz == 0)
00089     return;
00090 
00091   Coefficient_traits::const_reference mod = modulus();
00092   if (mod == 0)
00093     return;
00094 
00095   Coefficient& row_0 = (*this)[0];
00096   // Factor the modulus out of the inhomogeneous term.
00097   row_0 %= mod;
00098   if (row_0 < 0)
00099     // Make inhomogeneous term positive.
00100     row_0 += mod;
00101   return;
00102 }

void Parma_Polyhedra_Library::Congruence::strong_normalize (  )  [protected]

Calls normalize, then divides out common factors.

Strongly normalized Congruences have equivalent semantics if and only if their syntaxes (as output by operator<<) are equal.

Definition at line 105 of file Congruence.cc.

References Parma_Polyhedra_Library::Row::normalize(), and normalize().

Referenced by Parma_Polyhedra_Library::Congruence_System::operator<<(), and operator==().

00105                                 {
00106   normalize();
00107   Row::normalize();
00108 }

Coefficient & Parma_Polyhedra_Library::Congruence::modulus (  )  [inline, private]

Returns a reference to the modulus of *this.

Definition at line 160 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::size().

00160                     {
00161   assert(size() > 0);
00162   return (*this)[size()-1];
00163 }

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

Marks this congruence as a linear equality.

Definition at line 182 of file Congruence.inlines.hh.

References modulus().

Referenced by Parma_Polyhedra_Library::Grid::simplify().

00182                             {
00183   modulus() = 0;
00184 }

void Parma_Polyhedra_Library::Congruence::negate ( dimension_type  start,
dimension_type  end 
) [inline, private]

Negates the elements from index start to index end.

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

References Parma_Polyhedra_Library::neg_assign().

Referenced by Parma_Polyhedra_Library::Grid::simplify().

00187                                                            {
00188   while (start <= end)
00189     neg_assign(operator[](start++));
00190 }

void Parma_Polyhedra_Library::Congruence::swap ( Congruence y  )  [inline, private]

Swaps *this with y.

Definition at line 216 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::swap().

00216                               {
00217   Row::swap(y);
00218 }

void Parma_Polyhedra_Library::Congruence::throw_invalid_argument ( const char *  method,
const char *  message 
) const [private]

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

Definition at line 129 of file Congruence.cc.

Referenced by throw_dimension_incompatible().

00130                                                                    {
00131   std::ostringstream s;
00132   s << "PPL::Congruence::" << method << ":" << std::endl
00133     << message;
00134   throw std::invalid_argument(s.str());
00135 }

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

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

Definition at line 138 of file Congruence.cc.

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

Referenced by coefficient().

00140                                                                       {
00141   std::ostringstream s;
00142   s << "this->space_dimension() == " << space_dimension() << ", "
00143     << v_name << ".space_dimension() == " << v.space_dimension() << ".";
00144   throw_invalid_argument(method, s.str().c_str());
00145 }


Friends And Related Function Documentation

friend class PPL::Scalar_Products [friend]

Definition at line 460 of file Congruence.defs.hh.

friend class PPL::Congruence_System [friend]

Definition at line 461 of file Congruence.defs.hh.

Definition at line 462 of file Congruence.defs.hh.

friend class PPL::Grid [friend]

Definition at line 465 of file Congruence.defs.hh.

friend class PPL::Linear_Expression [friend]

Definition at line 466 of file Congruence.defs.hh.

Congruence PPL::operator%= ( const Linear_Expression e1,
const Linear_Expression e2 
) [friend]

Congruence PPL::operator%= ( const Linear_Expression e,
const Coefficient_traits::const_reference  n 
) [friend]

Congruence PPL::operator/ ( const Congruence cg,
const Coefficient_traits::const_reference  k 
) [friend]

Congruence PPL::operator/ ( const Constraint c,
const Coefficient_traits::const_reference  m 
) [friend]

bool PPL::operator== ( const Congruence x,
const Congruence y 
) [friend]

bool PPL::operator!= ( const Congruence x,
const Congruence y 
) [friend]

std::ostream& PPL::IO_Operators::operator<< ( std::ostream &  s,
const Congruence_System cgs 
) [friend]

Referenced by operator<<().

void swap ( PPL::Congruence x,
PPL::Congruence y 
) [friend]

Specializes std::swap.

Definition at line 226 of file Congruence.inlines.hh.

00227                                            {
00228   x.swap(y);
00229 }

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

Output operators.

Definition at line 149 of file Congruence.cc.

References coefficient(), Parma_Polyhedra_Library::Coefficient_zero(), inhomogeneous_term(), is_proper_congruence(), modulus(), Parma_Polyhedra_Library::neg_assign(), PPL::IO_Operators::operator<<, and space_dimension().

00149                                                               {
00150   const int num_variables = c.space_dimension();
00151   bool first = true;
00152   for (int v = 0; v < num_variables; ++v) {
00153     Coefficient cv = c.coefficient(Variable(v));
00154     if (cv != 0) {
00155       if (!first) {
00156         if (cv > 0)
00157           s << " + ";
00158         else {
00159           s << " - ";
00160           neg_assign(cv);
00161         }
00162       }
00163       else
00164         first = false;
00165       if (cv == -1)
00166         s << "-";
00167       else if (cv != 1)
00168         s << cv << "*";
00169       s << PPL::Variable(v);
00170     }
00171   }
00172   if (first)
00173     s << Coefficient_zero();
00174   s << " = " << -c.inhomogeneous_term();
00175   if (c.is_proper_congruence())
00176     s << " (mod " << c.modulus() << ")";
00177   return s;
00178 }

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

Returns true if and only if x and y are equivalent.

Definition at line 115 of file Congruence.inlines.hh.

References strong_normalize().

00115                                                      {
00116   Congruence x_temp(x);
00117   Congruence y_temp(y);
00118   x_temp.strong_normalize();
00119   y_temp.strong_normalize();
00120   return static_cast<const Row&>(x_temp) == static_cast<const Row&>(y_temp);
00121 }

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

Returns false if and only if x and y are equivalent.

Definition at line 125 of file Congruence.inlines.hh.

00125                                                      {
00126   return !(x == y);
00127 }

Congruence operator/ ( const Congruence cg,
const Coefficient_traits::const_reference  k 
) [related]

Returns a copy of cg, multiplying k into the copy's modulus.

If cg represents the congruence $ e_1 = e_2 \pmod{m}$, then the result represents the congruence $ e_1 = e_2 \pmod{mk}$.

Definition at line 90 of file Congruence.inlines.hh.

00091                                                      {
00092   Congruence ret (cg, k);
00093   return ret;
00094 }

Congruence operator/ ( const Constraint c,
const Coefficient_traits::const_reference  m 
) [related]

Creates a congruence from c, with m as the modulus.

Definition at line 98 of file Congruence.inlines.hh.

00099                                                      {
00100   Congruence ret (c);
00101   return ret / m;
00102 }


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