A linear congruence. More...

#include <Congruence_defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::Congruence:

Public Types
typedef Expression_Adapter_Transparent< Linear_Expression >	expr_type
	The type of the (adapted) internal expression. More...

Public Member Functions
	Congruence (Representation r=default_representation)
	Constructs the 0 = 0 congruence with space dimension `0` . More...

	Congruence (const Congruence &cg)
	Ordinary copy constructor. More...

	Congruence (const Congruence &cg, Representation r)
	Copy constructor with specified representation. More...

	Congruence (const Constraint &c, Representation r=default_representation)
	Copy-constructs (modulo 0) from equality constraint `c`. More...

	~Congruence ()
	Destructor. More...

Congruence &	operator= (const Congruence &y)
	Assignment operator. More...

Representation	representation () const
	Returns the current representation of *this. More...

void	set_representation (Representation r)
	Converts *this to the specified representation. More...

dimension_type	space_dimension () const
	Returns the dimension of the vector space enclosing `*this`. More...

void	permute_space_dimensions (const std::vector< Variable > &cycles)

expr_type	expression () const
	Partial read access to the (adapted) internal expression. More...

Coefficient_traits::const_reference	coefficient (Variable v) const
	Returns the coefficient of `v` in `*this`. More...

Coefficient_traits::const_reference	inhomogeneous_term () const
	Returns the inhomogeneous term of `*this`. More...

Coefficient_traits::const_reference	modulus () const
	Returns a const reference to the modulus of `*this`. More...

void	set_modulus (Coefficient_traits::const_reference m)

void	scale (Coefficient_traits::const_reference factor)
	Multiplies all the coefficients, including the modulus, by `factor` . More...

void	affine_preimage (Variable v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)

Congruence &	operator/= (Coefficient_traits::const_reference k)
	Multiplies `k` into the modulus of `*this`. More...

bool	is_tautological () const
	Returns `true` if and only if `*this` is a tautology (i.e., an always true congruence). More...

bool	is_inconsistent () const
	Returns `true` if and only if `*this` is inconsistent (i.e., an always false congruence). More...

bool	is_proper_congruence () const
	Returns `true` if the modulus is greater than zero. More...

bool	is_equality () const
	Returns `true` if `*this` is an equality. More...

memory_size_type	total_memory_in_bytes () const
	Returns a lower bound to the total size in bytes of the memory occupied by `*this`. More...

memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`. More...

bool	OK () const
	Checks if all the invariants are satisfied. More...

void	ascii_dump () const
	Writes to `std::cerr` an ASCII representation of `*this`. More...

void	ascii_dump (std::ostream &s) const
	Writes to `s` an ASCII representation of `*this`. More...

void	print () const
	Prints `*this` to `std::cerr` using `operator<<`. More...

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation of the internal representation of `*this`. More...

void	m_swap (Congruence &y)
	Swaps `*this` with `y`. More...

	Congruence (const Congruence &cg, dimension_type new_space_dimension)
	Copy-constructs with the specified space dimension. More...

	Congruence (const Congruence &cg, dimension_type new_space_dimension, Representation r)
	Copy-constructs with the specified space dimension and representation. More...

	Congruence (const Constraint &cg, dimension_type new_space_dimension, Representation r=default_representation)

	Congruence (Linear_Expression &le, Coefficient_traits::const_reference m, Recycle_Input)
	Constructs from Linear_Expression `le`, using modulus `m`. More...

void	swap_space_dimensions (Variable v1, Variable v2)
	Swaps the coefficients of the variables `v1` and `v2` . More...

void	set_space_dimension (dimension_type n)

void	shift_space_dimensions (Variable v, dimension_type n)

void	sign_normalize ()
	Normalizes the signs. More...

void	normalize ()
	Normalizes signs and the inhomogeneous term. More...

void	strong_normalize ()
	Calls normalize, then divides out common factors. More...

Static Public Member Functions
static dimension_type	max_space_dimension ()
	Returns the maximum space dimension a Congruence can handle. More...

static void	initialize ()
	Initializes the class. More...

static void	finalize ()
	Finalizes the class. More...

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

static const Congruence &	zero_dim_false ()
	Returns a reference to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$ . More...

static Congruence	create (const Linear_Expression &e1, const Linear_Expression &e2, Representation r=default_representation)
	Returns the congruence $e1 = e2 \pmod{1}$ . More...

static Congruence	create (const Linear_Expression &e, Coefficient_traits::const_reference n, Representation r=default_representation)
	Returns the congruence $e = n \pmod{1}$ . More...

static Congruence	create (Coefficient_traits::const_reference n, const Linear_Expression &e, Representation r=default_representation)
	Returns the congruence $n = e \pmod{1}$ . More...

Static Public Attributes
static const Representation	default_representation = SPARSE
	The representation used for new Congruences. More...

Private Member Functions
bool	is_equal_at_dimension (Variable v, const Congruence &cg) const
	Returns `true` if `*this` is equal to `cg` in dimension `v`. More...

void	throw_invalid_argument (const char method, const char message) const
	Throws a `std::invalid_argument` exception containing error message `message`. More...

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

Private Attributes
Linear_Expression	expr

Coefficient	modulus_

Static Private Attributes
static const Congruence *	zero_dim_false_p = 0
	Holds (between class initialization and finalization) a pointer to the false (zero-dimension space) congruence $0 = 1 \pmod{0}$ . More...

static const Congruence *	zero_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. More...

Friends
class	Scalar_Products

class	Grid

bool	operator== (const Congruence &x, const Congruence &y)

bool	operator!= (const Congruence &x, const Congruence &y)

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &s, const Congruence &c)

bool	operator== (const Congruence &x, const Congruence &y)
	Returns `true` if and only if `x` and `y` are equivalent. More...

bool	operator!= (const Congruence &x, const Congruence &y)
	Returns `false` if and only if `x` and `y` are equivalent. More...

std::ostream &	operator<< (std::ostream &s, const Congruence &c)
	Output operators. More...

Congruence	operator%= (const Linear_Expression &e1, const Linear_Expression &e2)
	Returns the congruence $e1 = e2 \pmod{1}$ . More...

Congruence	operator%= (const Linear_Expression &e, Coefficient_traits::const_reference n)
	Returns the congruence $e = n \pmod{1}$ . More...

Congruence	operator/ (const Congruence &cg, Coefficient_traits::const_reference k)
	Returns a copy of `cg`, multiplying `k` into the copy's modulus. More...

Congruence	operator/ (const Constraint &c, Coefficient_traits::const_reference m)
	Creates a congruence from `c`, with `m` as the modulus. More...

void	swap (Congruence &x, Congruence &y)

Congruence	operator%= (const Linear_Expression &e1, const Linear_Expression &e2)

Congruence	operator%= (const Linear_Expression &e, Coefficient_traits::const_reference n)

Congruence	operator/ (const Congruence &cg, Coefficient_traits::const_reference k)

Congruence	operator/ (const Constraint &c, Coefficient_traits::const_reference m)

bool	operator== (const Congruence &x, const Congruence &y)

bool	operator!= (const Congruence &x, const Congruence &y)

void	swap (Congruence &x, Congruence &y)

Detailed Description

A linear congruence.

An object of the class Congruence is a congruence:

$\cg = \sum_{i=0}^{n-1} a_i x_i + b = 0 \pmod m$

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 , having space dimension :
Congruence eq_cg((3*x + 5*y - z %= 0) / 0);

The following code builds the congruence $4x = 2y - 13 \pmod{1}$ , having space dimension :
Congruence mod1_cg(4*x %= 2*y - 13);

The following code builds the congruence $4x = 2y - 13 \pmod{2}$ , having space dimension :
Congruence mod2_cg((4*x %= 2*y - 13) / 2);

An unsatisfiable congruence on the zero-dimension space $\Rset^0$ 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 $x - 5y + 3z = 4 \pmod{5}$ ), we construct a new congruence with the same modulus m but where the linear expression is ( $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 161 of file Congruence_defs.hh.

Member Typedef Documentation

typedef Expression_Adapter_Transparent<Linear_Expression> Parma_Polyhedra_Library::Congruence::expr_type

The type of the (adapted) internal expression.

Definition at line 214 of file Congruence_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Congruence::Congruence ( Representation r = default_representation )

inlineexplicit

Constructs the 0 = 0 congruence with space dimension 0 .

Definition at line 32 of file Congruence_inlines.hh.

References OK().

   : expr(r) {
   PPL_ASSERT(OK());
 }

Parma_Polyhedra_Library::Congruence::Congruence ( const Congruence & cg )

inline

Ordinary copy constructor.

Note: The new Congruence will have the same representation as `cg', not default_representation, so that they are indistinguishable.

Definition at line 38 of file Congruence_inlines.hh.

39 : expr(cg.expr), modulus_(cg.modulus_) {

40 }

Parma_Polyhedra_Library::Congruence::modulus_

Coefficient modulus_

Definition: Congruence_defs.hh:426

Parma_Polyhedra_Library::Congruence::expr

Linear_Expression expr

Definition: Congruence_defs.hh:424

Parma_Polyhedra_Library::Congruence::Congruence	(	const Congruence &	cg,
		Representation	r
	)

inline

Copy constructor with specified representation.

Definition at line 43 of file Congruence_inlines.hh.

44 : expr(cg.expr, r), modulus_(cg.modulus_) {

45 }

Parma_Polyhedra_Library::Congruence::modulus_

Coefficient modulus_

Definition: Congruence_defs.hh:426

Parma_Polyhedra_Library::Congruence::expr

Linear_Expression expr

Definition: Congruence_defs.hh:424

Parma_Polyhedra_Library::Congruence::Congruence	(	const Constraint &	c,
		Representation	r = `default_representation`
	)

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::Constraint::is_equality(), and throw_invalid_argument().

   : expr(c.expression(), c.space_dimension(), r),
     modulus_(0) {
   if (!c.is_equality()) {
     throw_invalid_argument("Congruence(c, r)",
                            "constraint c must be an equality.");
   }
 }

Parma_Polyhedra_Library::Congruence::~Congruence ( )

inline

Destructor.

Definition at line 89 of file Congruence_inlines.hh.

89 {

90 }

Parma_Polyhedra_Library::Congruence::Congruence	(	const Congruence &	cg,
		dimension_type	new_space_dimension
	)

inline

Copy-constructs with the specified space dimension.

Note: The new Congruence will have the same representation as `cg', not default_representation, for consistency with the copy constructor.

Definition at line 48 of file Congruence_inlines.hh.

References OK().

   : expr(cg.expr, new_space_dimension), modulus_(cg.modulus_) {
   PPL_ASSERT(OK());
 }

Parma_Polyhedra_Library::Congruence::Congruence	(	const Congruence &	cg,
		dimension_type	new_space_dimension,
		Representation	r
	)

inline

Copy-constructs with the specified space dimension and representation.

Definition at line 55 of file Congruence_inlines.hh.

References OK().

   : expr(cg.expr, new_space_dimension, r), modulus_(cg.modulus_) {
   PPL_ASSERT(OK());
 }

Parma_Polyhedra_Library::Congruence::Congruence	(	const Constraint &	cg,
		dimension_type	new_space_dimension,
		Representation	r = `default_representation`
	)

Copy-constructs from a constraint, with the specified space dimension and (optional) representation.

Definition at line 45 of file Congruence.cc.

References Parma_Polyhedra_Library::Constraint::is_equality(), and throw_invalid_argument().

   : expr(c.expression(), new_space_dimension, r),
     modulus_(0) {
   if (!c.is_equality()) {
     throw_invalid_argument("Congruence(c, space_dim, r)",
                            "constraint c must be an equality.");
   }
 }

Parma_Polyhedra_Library::Congruence::Congruence	(	Linear_Expression &	le,
		Coefficient_traits::const_reference	m,
		Recycle_Input
	)

inline

Constructs from Linear_Expression le, using modulus m.

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

Note: The new Congruence will have the same representation as `le'.

Parameters

le	The Linear_Expression holding the coefficients.
m	The modulus for the congruence, which must be zero or greater.

Definition at line 93 of file Congruence_inlines.hh.

References expr, OK(), and swap().

   : modulus_(m) {
   PPL_ASSERT(m >= 0);
   swap(expr, le);
 
   PPL_ASSERT(OK());
 }

Member Function Documentation

void Parma_Polyhedra_Library::Congruence::affine_preimage	(	Variable	v,
		const Linear_Expression &	expr,
		Coefficient_traits::const_reference	denominator
	)

Definition at line 115 of file Congruence.cc.

References c, Parma_Polyhedra_Library::Coefficient_zero(), Parma_Polyhedra_Library::Linear_Expression::get(), PPL_DIRTY_TEMP_COEFFICIENT, Parma_Polyhedra_Library::Variable::space_dimension(), and Parma_Polyhedra_Library::Linear_Expression::space_dimension().

                                                                  {
   PPL_DIRTY_TEMP_COEFFICIENT(c);
   c = expr.get(v);
 
   if (c == 0) {
     return;
   }
 
   scale(denominator);
 
   expr.linear_combine(e, 1, c, 0, e.space_dimension() + 1);
 
   if (v.space_dimension() > e.space_dimension() || e.get(v) == 0) {
     // Not invertible
     expr.set(v, Coefficient_zero());
   }
   else {
     c *= e.get(v);
     expr.set(v, c);
   }
 }

void Parma_Polyhedra_Library::Congruence::ascii_dump ( ) const

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

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

Writes to s an ASCII representation of *this.

Definition at line 227 of file Congruence.cc.

                                              {
   expr.ascii_dump(s);
   s << " m " << modulus_ << std::endl;
 }

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

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

Definition at line 235 of file Congruence.cc.

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

                                        {
   expr.ascii_load(s);
 
   std::string str;
   if (!(s >> str) || str != "m") {
     return false;
   }
 
   if (!(s >> modulus_)) {
     return false;
   }
 
   PPL_ASSERT(OK());
   return true;
 }

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 210 of file Congruence_inlines.hh.

References Parma_Polyhedra_Library::Linear_Expression::coefficient(), expr, Parma_Polyhedra_Library::Variable::space_dimension(), space_dimension(), and throw_dimension_incompatible().

Referenced by Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), and is_equal_at_dimension().

                                               {
   if (v.space_dimension() > space_dimension()) {
     throw_dimension_incompatible("coefficient(v)", "v", v);
   }
   return expr.coefficient(v);
 }

PPL::Congruence Parma_Polyhedra_Library::Congruence::create	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2,
		Representation	r = `default_representation`
	)

static

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

Definition at line 139 of file Congruence.cc.

References Parma_Polyhedra_Library::Linear_Expression::space_dimension().

Referenced by operator%=().

                                           {
   Linear_Expression e(e1,
                       std::max(e1.space_dimension(), e2.space_dimension()),
                       r);
   e -= e2;
   return Congruence(e, 1, Recycle_Input());
 }

Congruence Parma_Polyhedra_Library::Congruence::create	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n,
		Representation	r = `default_representation`
	)

inlinestatic

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

Definition at line 104 of file Congruence_inlines.hh.

                                      {
   Linear_Expression diff(e, r);
   diff -= n;
   const Congruence cg(diff, 1, Recycle_Input());
   return cg;
 }

Congruence Parma_Polyhedra_Library::Congruence::create	(	Coefficient_traits::const_reference	n,
		const Linear_Expression &	e,
		Representation	r = `default_representation`
	)

inlinestatic

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

Definition at line 114 of file Congruence_inlines.hh.

                                      {
   Linear_Expression diff(e, r);
   diff -= n;
   const Congruence cg(diff, 1, Recycle_Input());
   return cg;
 }

Congruence::expr_type Parma_Polyhedra_Library::Congruence::expression ( ) const

inline

Partial read access to the (adapted) internal expression.

Definition at line 73 of file Congruence_inlines.hh.

References expr.

                              {
   return expr_type(expr);
 }

memory_size_type Parma_Polyhedra_Library::Congruence::external_memory_in_bytes ( ) const

inline

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

Definition at line 255 of file Congruence_inlines.hh.

References expr, Parma_Polyhedra_Library::external_memory_in_bytes(), Parma_Polyhedra_Library::Linear_Expression::external_memory_in_bytes(), and modulus_.

Referenced by total_memory_in_bytes().

                                            {
   return expr.external_memory_in_bytes()
          + Parma_Polyhedra_Library::external_memory_in_bytes(modulus_);
 }

void Parma_Polyhedra_Library::Congruence::finalize ( )

static

Finalizes the class.

Definition at line 281 of file Congruence.cc.

Referenced by Parma_Polyhedra_Library::Init::~Init().

                         {
   PPL_ASSERT(zero_dim_false_p != 0);
   delete zero_dim_false_p;
   zero_dim_false_p = 0;
 
   PPL_ASSERT(zero_dim_integrality_p != 0);
   delete zero_dim_integrality_p;
   zero_dim_integrality_p = 0;
 }

Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::inhomogeneous_term ( ) const

inline

Returns the inhomogeneous term of *this.

Definition at line 223 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::inhomogeneous_term().

Referenced by Parma_Polyhedra_Library::Box< ITV >::add_congruence_no_check(), Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), operator<<(), Parma_Polyhedra_Library::Box< ITV >::relation_with(), Parma_Polyhedra_Library::Grid::relation_with(), and Parma_Polyhedra_Library::Grid::simplify().

                                      {
   return expr.inhomogeneous_term();
 }

void Parma_Polyhedra_Library::Congruence::initialize ( )

static

Initializes the class.

Definition at line 270 of file Congruence.cc.

References Parma_Polyhedra_Library::Linear_Expression::zero().

Referenced by Parma_Polyhedra_Library::Init::Init().

                           {
   PPL_ASSERT(zero_dim_false_p == 0);
   zero_dim_false_p
     = new Congruence((Linear_Expression::zero() %= Coefficient(-1)) / 0);
 
   PPL_ASSERT(zero_dim_integrality_p == 0);
   zero_dim_integrality_p
     = new Congruence(Linear_Expression::zero() %= Coefficient(-1));
 }

bool Parma_Polyhedra_Library::Congruence::is_equal_at_dimension	(	Variable	v,
		const Congruence &	cg
	)		const

inlineprivate

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

Definition at line 249 of file Congruence_inlines.hh.

References coefficient(), and modulus().

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

                                                               {
   return coefficient(v) * cg.modulus() == cg.coefficient(v) * modulus();
 }

bool Parma_Polyhedra_Library::Congruence::is_equality ( ) const

inline

Returns true if *this is an equality.

A modulus of zero denotes a linear equality.

Definition at line 244 of file Congruence_inlines.hh.

References modulus().

                               {
   return modulus() == 0;
 }

bool Parma_Polyhedra_Library::Congruence::is_inconsistent ( ) const

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

An inconsistent congruence has one of the following two forms:

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

Definition at line 218 of file Congruence.cc.

                                      {
   if (is_equality()) {
     return (inhomogeneous_term() != 0) && expr.all_homogeneous_terms_are_zero();
   }
 
   return (inhomogeneous_term() % modulus() != 0) && expr.all_homogeneous_terms_are_zero();
 }

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.

Definition at line 239 of file Congruence_inlines.hh.

References modulus().

                                        {
   return modulus() > 0;
 }

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

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

                                      {
   if (is_equality()) {
     return (inhomogeneous_term() == 0) && expr.all_homogeneous_terms_are_zero();
   }
   return (inhomogeneous_term() % modulus() == 0) && expr.all_homogeneous_terms_are_zero();
 }

void Parma_Polyhedra_Library::Congruence::m_swap ( Congruence & y )

inline

Swaps *this with y.

Definition at line 266 of file Congruence_inlines.hh.

References expr, modulus_, swap(), and Parma_Polyhedra_Library::swap().

Referenced by swap().

                                 {
   using std::swap;
   swap(expr, y.expr);
   swap(modulus_, y.modulus_);
 }

dimension_type Parma_Polyhedra_Library::Congruence::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a Congruence can handle.

Definition at line 200 of file Congruence_inlines.hh.

References Parma_Polyhedra_Library::Linear_Expression::max_space_dimension().

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

                                 {
   return Linear_Expression::max_space_dimension();
 }

Coefficient_traits::const_reference Parma_Polyhedra_Library::Congruence::modulus ( ) const

inline

Returns a const reference to the modulus of *this.

Definition at line 228 of file Congruence_inlines.hh.

References modulus_.

                           {
   return modulus_;
 }

void Parma_Polyhedra_Library::Congruence::normalize ( )

Normalizes signs and the inhomogeneous term.

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

Definition at line 62 of file Congruence.cc.

References c, and PPL_DIRTY_TEMP_COEFFICIENT.

                          {
   PPL_ASSERT(OK());
   sign_normalize();
 
   if (modulus_ == 0) {
     return;
   }
 
   PPL_DIRTY_TEMP_COEFFICIENT(c);
   c = expr.inhomogeneous_term();
   // Factor the modulus out of the inhomogeneous term.
   c %= modulus_;
   if (c < 0) {
     // Make inhomogeneous term positive.
     c += modulus_;
   }
   expr.set_inhomogeneous_term(c);
 
   PPL_ASSERT(OK());
 }

bool Parma_Polyhedra_Library::Congruence::OK ( ) const

Checks if all the invariants are satisfied.

Definition at line 252 of file Congruence.cc.

Referenced by Congruence(), Parma_Polyhedra_Library::Congruence_System::insert(), Parma_Polyhedra_Library::Congruence_System::insert_verbatim(), Parma_Polyhedra_Library::Congruence_System::OK(), Parma_Polyhedra_Library::Grid::reduce_equality_with_equality(), set_modulus(), and set_space_dimension().

                         {
   // Modulus check.
   if (modulus() < 0) {
 #ifndef NDEBUG
     std::cerr << "Congruence has a negative modulus " << modulus() << "."
               << std::endl;
 #endif
     return false;
   }
 
   // All tests passed.
   return true;
 }

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 169 of file Congruence_inlines.hh.

References modulus_.

                                                           {
   if (k >= 0) {
     modulus_ *= k;
   }
   else {
     modulus_ *= -k;
   }
   return *this;
 }

Congruence & Parma_Polyhedra_Library::Congruence::operator= ( const Congruence & y )

inline

Assignment operator.

Definition at line 154 of file Congruence_inlines.hh.

References swap().

                                          {
   Congruence tmp = y;
   swap(*this, tmp);
   return *this;
 }

void Parma_Polyhedra_Library::Congruence::permute_space_dimensions ( const std::vector< Variable > & cycles )

inline

Definition at line 218 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::permute_space_dimensions().

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

                                                                       {
   expr.permute_space_dimensions(cycles);
 }

void Parma_Polyhedra_Library::Congruence::print ( ) const

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

Representation Parma_Polyhedra_Library::Congruence::representation ( ) const

inline

Returns the current representation of *this.

Definition at line 63 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::representation().

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

                                  {
   return expr.representation();
 }

void Parma_Polyhedra_Library::Congruence::scale ( Coefficient_traits::const_reference factor )

Multiplies all the coefficients, including the modulus, by factor .

Definition at line 103 of file Congruence.cc.

Referenced by Parma_Polyhedra_Library::Grid::multiply_grid(), and Parma_Polyhedra_Library::Grid::reduce_congruence_with_equality().

                                                              {
   if (factor == 1) {
     // Nothing to do.
     return;
   }
 
   expr *= factor;
   modulus_ *= factor;
 }

void Parma_Polyhedra_Library::Congruence::set_modulus ( Coefficient_traits::const_reference m )

inline

Sets the modulus of *this to m . If m is 0, the congruence becomes an equality.

Definition at line 233 of file Congruence_inlines.hh.

References modulus_, and OK().

Referenced by Parma_Polyhedra_Library::Grid::conversion(), and Parma_Polyhedra_Library::Grid::simplify().

                                                            {
   modulus_ = m;
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence::set_representation ( Representation r )

inline

Converts *this to the specified representation.

Definition at line 68 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::set_representation().

Referenced by Parma_Polyhedra_Library::Congruence_System::concatenate(), and Parma_Polyhedra_Library::Congruence_System::insert_verbatim().

                                                {
   expr.set_representation(r);
 }

void Parma_Polyhedra_Library::Congruence::set_space_dimension ( dimension_type n )

inline

Sets the space dimension by n , adding or removing coefficients as needed.

Definition at line 78 of file Congruence_inlines.hh.

References expr, OK(), and Parma_Polyhedra_Library::Linear_Expression::set_space_dimension().

Referenced by Parma_Polyhedra_Library::Congruence_System::insert_verbatim(), and Parma_Polyhedra_Library::Grid::simplify().

                                                 {
   expr.set_space_dimension(n);
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence::shift_space_dimensions	(	Variable	v,
		dimension_type	n
	)

inline

Shift by n positions the coefficients of variables, starting from the coefficient of v. This increases the space dimension by n.

Definition at line 84 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::shift_space_dimensions().

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

                                                                {
   expr.shift_space_dimensions(v, n);
 }

void Parma_Polyhedra_Library::Congruence::sign_normalize ( )

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

                               {
   expr.sign_normalize();
 }

dimension_type Parma_Polyhedra_Library::Congruence::space_dimension ( ) const

inline

Returns the dimension of the vector space enclosing *this.

Definition at line 205 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::space_dimension().

                                   {
   return expr.space_dimension();
 }

void Parma_Polyhedra_Library::Congruence::strong_normalize ( )

Calls normalize, then divides out common factors.

Strongly normalized Congruences have equivalent semantics if and only if they have the same syntax (as output by operator<<).

Definition at line 84 of file Congruence.cc.

References Parma_Polyhedra_Library::gcd_assign().

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

                                 {
   normalize();
 
   Coefficient gcd = expr.gcd(0, expr.space_dimension() + 1);
   if (gcd == 0) {
     gcd = modulus_;
   }
   else {
     gcd_assign(gcd, modulus_, gcd);
   }
 
   if (gcd != 0 && gcd != 1) {
     expr /= gcd;
     modulus_ /= gcd;
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence::swap_space_dimensions	(	Variable	v1,
		Variable	v2
	)

inline

Swaps the coefficients of the variables v1 and v2 .

Definition at line 273 of file Congruence_inlines.hh.

References expr, and Parma_Polyhedra_Library::Linear_Expression::swap_space_dimensions().

                                                           {
   expr.swap_space_dimensions(v1, v2);
 }

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

References Parma_Polyhedra_Library::Variable::space_dimension().

Referenced by coefficient().

                                                                       {
   std::ostringstream s;
   s << "this->space_dimension() == " << space_dimension() << ", "
     << v_name << ".space_dimension() == " << v.space_dimension() << ".";
   const std::string str = s.str();
   throw_invalid_argument(method, str.c_str());
 }

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

Referenced by Congruence().

                                                                    {
   std::ostringstream s;
   s << "PPL::Congruence::" << method << ":" << std::endl
     << message;
   throw std::invalid_argument(s.str());
 }

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.

Definition at line 261 of file Congruence_inlines.hh.

References external_memory_in_bytes().

                                         {
   return external_memory_in_bytes() + sizeof(*this);
 }

const Congruence & Parma_Polyhedra_Library::Congruence::zero_dim_false ( )

inlinestatic

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

Definition at line 149 of file Congruence_inlines.hh.

References zero_dim_false_p.

Referenced by Parma_Polyhedra_Library::Box< ITV >::congruences(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Congruence_System::initialize(), Parma_Polyhedra_Library::BD_Shape< T >::minimized_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::minimized_congruences(), Parma_Polyhedra_Library::Grid::remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Grid::set_empty().

                            {
   return *zero_dim_false_p;
 }

const Congruence & Parma_Polyhedra_Library::Congruence::zero_dim_integrality ( )

inlinestatic

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

Definition at line 144 of file Congruence_inlines.hh.

References zero_dim_integrality_p.

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

                                  {
   return *zero_dim_integrality_p;
 }

Friends And Related Function Documentation

friend class Grid

friend

Definition at line 458 of file Congruence_defs.hh.

bool operator!=	(	const Congruence &	x,
		const Congruence &	y
	)

bool operator!=	(	const Congruence &	x,
		const Congruence &	y
	)

                                                      {
   return !(x == y);
 }

bool operator!=	(	const Congruence &	x,
		const Congruence &	y
	)

friend

Congruence operator%=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

References create().

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

Congruence operator%=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

References create().

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

Congruence operator%=	(	const Linear_Expression &	e1,
		const Linear_Expression &	e2
	)

Congruence operator%=	(	const Linear_Expression &	e,
		Coefficient_traits::const_reference	n
	)

Congruence operator/	(	const Congruence &	cg,
		Coefficient_traits::const_reference	k
	)

                                                                      {
   Congruence ret = cg;
   ret /= k;
   return ret;
 }

Congruence operator/	(	const Constraint &	c,
		Coefficient_traits::const_reference	m
	)

                                                                     {
   Congruence ret(c);
   ret /= m;
   return ret;
 }

Congruence operator/	(	const Congruence &	cg,
		Coefficient_traits::const_reference	k
	)

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

Congruence operator/	(	const Constraint &	c,
		Coefficient_traits::const_reference	m
	)

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

References Parma_Polyhedra_Library::Expression_Adapter< T >::begin(), Parma_Polyhedra_Library::Coefficient_zero(), expression(), inhomogeneous_term(), is_proper_congruence(), Parma_Polyhedra_Library::Expression_Adapter< T >::lower_bound(), modulus(), Parma_Polyhedra_Library::neg_assign(), PPL_DIRTY_TEMP_COEFFICIENT, and space_dimension().

                                                               {
   const dimension_type num_variables = c.space_dimension();
   PPL_DIRTY_TEMP_COEFFICIENT(cv);
   bool first = true;
   const Congruence::expr_type c_e = c.expression();
   for (Congruence::expr_type::const_iterator i = c_e.begin(),
         i_end = c_e.lower_bound(Variable(num_variables)); i != i_end; ++i) {
     cv = *i;
     if (!first) {
       if (cv > 0) {
         s << " + ";
       }
       else {
         s << " - ";
         neg_assign(cv);
       }
     }
     else {
       first = false;
     }
     if (cv == -1) {
       s << "-";
     }
     else if (cv != 1) {
       s << cv << "*";
     }
     s << i.variable();
   }
   if (first) {
     s << Coefficient_zero();
   }
   s << " = " << -c.inhomogeneous_term();
   if (c.is_proper_congruence()) {
     s << " (mod " << c.modulus() << ")";
   }
   return s;
 }

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

bool operator==	(	const Congruence &	x,
		const Congruence &	y
	)

bool operator==	(	const Congruence &	x,
		const Congruence &	y
	)

References expr, Parma_Polyhedra_Library::Linear_Expression::is_equal_to(), modulus(), space_dimension(), and strong_normalize().

                                                      {
   if (x.space_dimension() != y.space_dimension()) {
     return false;
   }
   Congruence x_temp(x);
   Congruence y_temp(y);
   x_temp.strong_normalize();
   y_temp.strong_normalize();
   return x_temp.expr.is_equal_to(y_temp.expr)
     && x_temp.modulus() == y_temp.modulus();
 }

bool operator==	(	const Congruence &	x,
		const Congruence &	y
	)

friend

friend class Scalar_Products

friend

Definition at line 457 of file Congruence_defs.hh.

void swap	(	Congruence &	x,
		Congruence &	y
	)

References m_swap().

                                    {
   x.m_swap(y);
 }

void swap	(	Congruence &	x,
		Congruence &	y
	)

Member Data Documentation

const Representation Parma_Polyhedra_Library::Congruence::default_representation = SPARSE

static

The representation used for new Congruences.

Note: The copy constructor and the copy constructor with specified size use the representation of the original object, so that it is indistinguishable from the original object.

Definition at line 170 of file Congruence_defs.hh.

Linear_Expression Parma_Polyhedra_Library::Congruence::expr

private

Definition at line 424 of file Congruence_defs.hh.

Coefficient Parma_Polyhedra_Library::Congruence::modulus_

private

Definition at line 426 of file Congruence_defs.hh.

Referenced by external_memory_in_bytes(), m_swap(), modulus(), operator/=(), and set_modulus().

const PPL::Congruence * Parma_Polyhedra_Library::Congruence::zero_dim_false_p = 0

staticprivate

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

Definition at line 415 of file Congruence_defs.hh.

Referenced by zero_dim_false().

const PPL::Congruence * Parma_Polyhedra_Library::Congruence::zero_dim_integrality_p = 0

staticprivate

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 422 of file Congruence_defs.hh.

Referenced by zero_dim_integrality().

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Static Private Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation