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/= (Coefficient_traits::const_reference k)
 Multiplies k into the modulus of *this.
bool is_tautological () const
 Returns true if and only if *this is a tautology (i.e., an always true congruence).
bool is_inconsistent () const
 Returns true if and only if *this is inconsistent (i.e., an always 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 void initialize ()
 Initializes the class.
static void finalize ()
 Finalizes the class.
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}$.
static Congruence create (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the congruence $e1 = e2 \pmod{1}$.
static Congruence create (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the congruence $e = n \pmod{1}$.
static Congruence create (Coefficient_traits::const_reference n, const Linear_Expression &e)
 Returns the congruence $n = e \pmod{1}$.

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

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

Static Private Attributes

static const Congruencezero_dim_false_p = 0
 Holds (between class initialization and finalization) a pointer to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$.
static const Congruencezero_dim_integrality_p = 0
 Holds (between class initialization and finalization) a pointer to the true (zero-dimension space) congruence $0 = 1 \pmod{1}$, also known as the integrality congruence.

Friends

class Parma_Polyhedra_Library::Scalar_Products
class Parma_Polyhedra_Library::Constraint
class Parma_Polyhedra_Library::Congruence_System
class Parma_Polyhedra_Library::Congruence_System::const_iterator
class Parma_Polyhedra_Library::Grid
class Parma_Polyhedra_Library::Linear_Expression
Congruence operator/ (const Congruence &cg, Coefficient_traits::const_reference k)
 Returns a copy of cg, multiplying k into the copy's modulus.
Congruence operator/ (const Constraint &c, Coefficient_traits::const_reference m)
 Creates a congruence from c, with m as the modulus.
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.
std::ostream & operator<< (std::ostream &s, const Congruence_System &cgs)
 Output operator.
void swap (Parma_Polyhedra_Library::Congruence &x, Parma_Polyhedra_Library::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.
Congruence operator%= (const Linear_Expression &e1, const Linear_Expression &e2)
 Returns the congruence $e1 = e2 \pmod{1}$.
Congruence operator%= (const Linear_Expression &e, Coefficient_traits::const_reference n)
 Returns the congruence $e = n \pmod{1}$.


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;
  const Coefficient& m = cg1.modulus();
  if (m == 0)
    cout << "Congruence cg1 is an equality." << endl;
  else {
    Linear_Expression e;
    for (dimension_type i = cg1.space_dimension(); i-- > 0; )
      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 210 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 an inequality.

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   (*this)[size()-1] = 0;
00045 }

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.

Referenced by initialize().

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 47 of file Congruence.cc.

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

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 
) [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, which must be zero or greater.

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

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

00060                                                             {
00061   Row::swap(static_cast<Row&>(le));
00062   assert(m >= 0);
00063   (*this)[size()-1] = m;
00064 }


Member Function Documentation

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

Assignment operator.

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

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

00116                                          {
00117   Row::operator=(c);
00118   return *this;
00119 }

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

Returns the maximum space dimension a Congruence can handle.

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

References Parma_Polyhedra_Library::Row::max_size().

00154                                 {
00155   // The first coefficient holds the inhomogeneous term, while
00156   // the last coefficient is for the modulus.
00157   return max_size() - 2;
00158 }

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

Returns the dimension of the vector space enclosing *this.

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

References Parma_Polyhedra_Library::Row::size().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Grid::add_congruence_no_check(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), coefficient(), Parma_Polyhedra_Library::Constraint::Constraint(), Parma_Polyhedra_Library::extract_interval_congruence(), is_inconsistent(), is_tautological(), operator<<(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::BD_Shape< T >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_with_congruence(), Parma_Polyhedra_Library::Box< ITV >::refine_with_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruence(), Parma_Polyhedra_Library::Polyhedron::relation_with(), Parma_Polyhedra_Library::Octagonal_Shape< T >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::BD_Shape< T >::relation_with(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), Parma_Polyhedra_Library::Octagonal_Shape< T >::throw_dimension_incompatible(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), throw_dimension_incompatible(), Parma_Polyhedra_Library::Box< ITV >::throw_dimension_incompatible(), and Parma_Polyhedra_Library::BD_Shape< T >::throw_dimension_incompatible().

00161                                   {
00162   return size() - 2;
00163 }

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

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

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

Congruence & Parma_Polyhedra_Library::Congruence::operator/= ( 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 129 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::Row::size().

00129                                                           {
00130   if (k >= 0)
00131     (*this)[size()-1] *= k;
00132   else
00133     (*this)[size()-1] *= -k;
00134   return *this;
00135 }

bool Parma_Polyhedra_Library::Congruence::is_tautological (  )  const

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

A tautological congruence has 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 $b = 0 \pmod{m}$.

Definition at line 182 of file Congruence.cc.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruence(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruence(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruence(), Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Polyhedron::add_congruences(), and Parma_Polyhedra_Library::Polyhedron::refine_with_congruence().

00182                                      {
00183   if ((is_equality() && inhomogeneous_term() == 0)
00184       || (is_proper_congruence()
00185           && (inhomogeneous_term() % modulus() == 0))) {
00186     for (unsigned i = space_dimension(); i > 0; --i)
00187       if (operator[](i) != 0)
00188         return false;
00189     return true;
00190   }
00191   return false;
00192 }

bool Parma_Polyhedra_Library::Congruence::is_inconsistent (  )  const

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

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

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

00195                                                               {
00196   return operator[](dim) * cg.modulus() == cg[dim] * modulus();
00197 }

void Parma_Polyhedra_Library::Congruence::initialize (  )  [static]

Initializes the class.

Definition at line 274 of file Congruence.cc.

References Congruence(), Parma_Polyhedra_Library::Linear_Expression::zero(), zero_dim_false_p, and zero_dim_integrality_p.

00274                           {
00275   assert(zero_dim_false_p == 0);
00276   zero_dim_false_p
00277     = new Congruence((Linear_Expression::zero() %= Coefficient(-1)) / 0);
00278 
00279   assert(zero_dim_integrality_p == 0);
00280   zero_dim_integrality_p
00281     = new Congruence(Linear_Expression::zero() %= Coefficient(-1));
00282 }

void Parma_Polyhedra_Library::Congruence::finalize (  )  [static]

Finalizes the class.

Definition at line 285 of file Congruence.cc.

References zero_dim_false_p, and zero_dim_integrality_p.

00285                         {
00286   assert(zero_dim_false_p != 0);
00287   delete zero_dim_false_p;
00288   zero_dim_false_p = 0;
00289 
00290   assert(zero_dim_integrality_p != 0);
00291   delete zero_dim_integrality_p;
00292   zero_dim_integrality_p = 0;
00293 }

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 106 of file Congruence.inlines.hh.

References zero_dim_integrality_p.

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

00106                                  {
00107   return *zero_dim_integrality_p;
00108 }

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

PPL::Congruence Parma_Polyhedra_Library::Congruence::create ( const Linear_Expression e1,
const Linear_Expression e2 
) [static]

Returns the congruence $e1 = e2 \pmod{1}$.

Definition at line 110 of file Congruence.cc.

References Parma_Polyhedra_Library::Linear_Expression::space_dimension().

Referenced by operator%=().

00111                                                      {
00112   // Ensure that diff is created with capacity for the modulus.
00113   dimension_type dim, e1_dim, e2_dim;
00114   e1_dim = e1.space_dimension();
00115   e2_dim = e2.space_dimension();
00116   if (e1_dim > e2_dim)
00117     dim = e1_dim;
00118   else
00119     dim = e2_dim;
00120   Linear_Expression diff(e1_dim > e2_dim ? e1 : e2,
00121                          dim + 2);
00122   diff -= (e1_dim > e2_dim ? e2 : e1);
00123   Congruence cg(diff, 1);
00124   return cg;
00125 }

Congruence Parma_Polyhedra_Library::Congruence::create ( const Linear_Expression e,
Coefficient_traits::const_reference  n 
) [inline, static]

Returns the congruence $e = n \pmod{1}$.

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

References Parma_Polyhedra_Library::Linear_Expression::space_dimension().

00068                                                         {
00069   // Ensure that diff has capacity for the modulus.
00070   Linear_Expression diff(e, e.space_dimension() + 2);
00071   diff -= n;
00072   Congruence cg(diff, 1);
00073   return cg;
00074 }

Congruence Parma_Polyhedra_Library::Congruence::create ( Coefficient_traits::const_reference  n,
const Linear_Expression e 
) [inline, static]

Returns the congruence $n = e \pmod{1}$.

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

References Parma_Polyhedra_Library::Linear_Expression::space_dimension().

00078                                                {
00079   // Ensure that diff has capacity for the modulus.
00080   Linear_Expression diff(e, e.space_dimension() + 2);
00081   diff -= n;
00082   Congruence cg(diff, 1);
00083   return cg;
00084 }

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 216 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::total_memory_in_bytes().

00216                                         {
00217   return Row::total_memory_in_bytes();
00218 }

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 211 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::external_memory_in_bytes().

00211                                            {
00212   return Row::external_memory_in_bytes();
00213 }

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 207 of file Congruence.cc.

References Parma_Polyhedra_Library::Row::size().

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

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 222 of file Congruence.cc.

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

00222                                        {
00223   std::string str;
00224   if (!(s >> str) || str != "size")
00225     return false;
00226   dimension_type new_size;
00227   if (!(s >> new_size))
00228     return false;
00229 
00230   Row& x = *this;
00231   const dimension_type old_size = x.size();
00232   if (new_size < old_size)
00233     x.shrink(new_size);
00234   else if (new_size > old_size) {
00235     Row y(new_size, Row::Flags());
00236     x.swap(y);
00237   }
00238 
00239   if (new_size > 0) {
00240     for (dimension_type col = 0; col < new_size - 1; ++col)
00241       if (!(s >> x[col]))
00242         return false;
00243     if (!(s >> str) || (str.compare("m") != 0))
00244       return false;
00245     if (!(s >> x[new_size-1]))
00246       return false;
00247   }
00248   return true;
00249 }

bool Parma_Polyhedra_Library::Congruence::OK (  )  const

Checks if all the invariants are satisfied.

Reimplemented from Parma_Polyhedra_Library::Row.

Definition at line 252 of file Congruence.cc.

References modulus(), and Parma_Polyhedra_Library::Row::OK().

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

00252                         {
00253   // A Congruence must be a valid Row.
00254   if (!Row::OK())
00255     return false;
00256 
00257   // Modulus check.
00258   if (modulus() < 0) {
00259 #ifndef NDEBUG
00260     std::cerr << "Congruence has a negative modulus " << modulus() << "."
00261               << std::endl;
00262 #endif
00263     return false;
00264   }
00265 
00266   // All tests passed.
00267   return true;
00268 }

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 61 of file Congruence.cc.

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

Referenced by normalize().

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

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 83 of file Congruence.cc.

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

Referenced by strong_normalize().

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

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 104 of file Congruence.cc.

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

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

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

Marks this congruence as a linear equality.

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

References Parma_Polyhedra_Library::Row::size().

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

00200                             {
00201   (*this)[size()-1] = 0;
00202 }

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 205 of file Congruence.inlines.hh.

References Parma_Polyhedra_Library::neg_assign().

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

00205                                                            {
00206   while (start <= end)
00207     neg_assign(operator[](start++));
00208 }

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

Swaps *this with y.

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

References Parma_Polyhedra_Library::swap().

00221                               {
00222   Row::swap(y);
00223 }

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 128 of file Congruence.cc.

Referenced by throw_dimension_incompatible().

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

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 137 of file Congruence.cc.

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

Referenced by coefficient().

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


Friends And Related Function Documentation

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

friend class Parma_Polyhedra_Library::Constraint [friend]

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

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

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

friend class Parma_Polyhedra_Library::Grid [friend]

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

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

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

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 100 of file Congruence.inlines.hh.

00100                                                                      {
00101   Congruence ret(cg, k);
00102   return ret;
00103 }

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

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

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

00123                                                                     {
00124   Congruence ret(c);
00125   return ret / m;
00126 }

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

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

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

00139                                                      {
00140   Congruence x_temp(x);
00141   Congruence y_temp(y);
00142   x_temp.strong_normalize();
00143   y_temp.strong_normalize();
00144   return static_cast<const Row&>(x_temp) == static_cast<const Row&>(y_temp);
00145 }

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

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

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

00149                                                      {
00150   return !(x == y);
00151 }

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

Output operator.

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

Definition at line 473 of file Congruence_System.cc.

00473                                                                        {
00474   Congruence_System::const_iterator i = cgs.begin();
00475   const Congruence_System::const_iterator cgs_end = cgs.end();
00476   if (i == cgs_end)
00477     return s << "true";
00478   while (true) {
00479     Congruence cg = *i++;
00480     cg.strong_normalize();
00481     s << cg;
00482     if (i == cgs_end)
00483       return s;
00484     s << ", ";
00485   }
00486 }

Specializes std::swap.

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

00232                                            {
00233   x.swap(y);
00234 }

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(), space_dimension(), and TEMP_INTEGER.

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

Congruence operator%= ( const Linear_Expression e1,
const Linear_Expression e2 
) [related]

Returns the congruence $e1 = e2 \pmod{1}$.

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

References create().

00088                                                                      {
00089   return Congruence::create(e1, e2);
00090 }

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

Returns the congruence $e = n \pmod{1}$.

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

References create().

00094                                                                             {
00095   return Congruence::create(e, n);
00096 }


Member Data Documentation

Holds (between class initialization and finalization) a pointer to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$.

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

Referenced by finalize(), initialize(), and zero_dim_false().

Holds (between class initialization and finalization) a pointer to the true (zero-dimension space) congruence $0 = 1 \pmod{1}$, also known as the integrality congruence.

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

Referenced by finalize(), initialize(), and zero_dim_integrality().


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

Generated on Sat Oct 11 10:41:07 2008 for PPL by  doxygen 1.5.6