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

A linear congruence. More...

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.
Congruence & | operator= (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`.
Congruence & | operator/= (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`.
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 Congruence & | zero_dim_integrality ()
| Returns a reference to the true (zero-dimension space) congruence , also known as the integrality congruence.
static const Congruence & | zero_dim_false ()
| Returns a reference to the false (zero-dimension space) congruence .

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

## Friends

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 is the dimension of the space, is the integer coefficient of variable , is the integer inhomogeneous term and is the integer modulus; if , then represents the equality congruence and, if , then the congruence is said to be a proper congruence.

How to build a congruence
  Congruences 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 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 , having space dimension :

        Congruence eq_cg((3*x + 5*y - z %= 0) / 0);

  The following code builds the congruence , having space dimension :

        Congruence mod1_cg(4*x %= 2*y - 13);

  The following code builds the congruence , having space dimension :

        Congruence mod2_cg((4*x %= 2*y - 13) / 2);

  An unsatisfiable congruence on the zero-dimension space can be specified as follows:

        Congruence false_cg = Congruence::zero_dim_false();

  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 :

        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 ), we construct a new congruence with the same modulus `m` but where the linear expression is ().

        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.

## Constructor & Destructor Documentation

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.

## Member Function Documentation

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

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 , then it returns with *this representing the congruence .

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: ; or
- a proper congruence: , where n is the space dimension and m is the modulus.

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: where ; or
- a congruence: , where .

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

Returns `true` if the modulus is greater than zero.

A congruence with a modulus of 0 is a linear equality.

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

Returns `true` if `*this` is an equality.

A modulus of zero denotes a linear equality.

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.

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.

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.

## Friends And Related Function Documentation

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 , then the result represents the congruence .