A system of congruences. More...

#include <ppl.hh>

Classes
class	const_iterator
	An iterator over a system of congruences. More...

Public Member Functions
	Congruence_System (Representation r=default_representation)
	Default constructor: builds an empty system of congruences.

	Congruence_System (dimension_type d, Representation r=default_representation)
	Builds an empty (i.e. zero rows) system of dimension `d`.

	Congruence_System (const Congruence &cg, Representation r=default_representation)
	Builds the singleton system containing only congruence `cg`.

	Congruence_System (const Constraint &c, Representation r=default_representation)
	If `c` represents the constraint , builds the singleton system containing only constraint $e_1 = e_2 \pmod{0}$ . More...

	Congruence_System (const Constraint_System &cs, Representation r=default_representation)
	Builds a system containing copies of any equalities in `cs`.

	Congruence_System (const Congruence_System &cgs)
	Ordinary copy constructor. More...

	Congruence_System (const Congruence_System &cgs, Representation r)
	Copy constructor with specified representation.

	~Congruence_System ()
	Destructor.

Congruence_System &	operator= (const Congruence_System &y)
	Assignment operator.

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

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

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

bool	is_equal_to (const Congruence_System &y) const
	Returns `true` if and only if `*this` is exactly equal to `y`.

bool	has_linear_equalities () const
	Returns `true` if and only if `*this` contains one or more linear equalities.

void	clear ()
	Removes all the congruences and sets the space dimension to 0.

void	insert (const Congruence &cg)
	Inserts in `*this` a copy of the congruence `cg`, increasing the number of space dimensions if needed. More...

void	insert (Congruence &cg, Recycle_Input)
	Inserts in `*this` the congruence `cg`, stealing its contents and increasing the number of space dimensions if needed. More...

void	insert (const Constraint &c)
	Inserts in `*this` a copy of the equality constraint `c`, seen as a modulo 0 congruence, increasing the number of space dimensions if needed. More...

void	insert (const Congruence_System &y)
	Inserts in `*this` a copy of the congruences in `y`, increasing the number of space dimensions if needed. More...

void	insert (Congruence_System &cgs, Recycle_Input)
	Inserts into `*this` the congruences in `cgs`, increasing the number of space dimensions if needed.

bool	empty () const
	Returns `true` if and only if `*this` has no congruences.

const_iterator	begin () const
	Returns the const_iterator pointing to the first congruence, if `this` is not empty; otherwise, returns the past-the-end const_iterator.

const_iterator	end () const
	Returns the past-the-end const_iterator.

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

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

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

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

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.

memory_size_type	total_memory_in_bytes () const
	Returns 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`.

dimension_type	num_equalities () const
	Returns the number of equalities.

dimension_type	num_proper_congruences () const
	Returns the number of proper congruences.

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

void	add_unit_rows_and_space_dimensions (dimension_type dims)
	Adds `dims` rows and `dims` space dimensions to the matrix, initializing the added rows as in the unit congruence system. More...

void	permute_space_dimensions (const std::vector< Variable > &cycle)
	Permutes the space dimensions of the system. More...

void	swap_space_dimensions (Variable v1, Variable v2)
	Swaps the columns having indexes `i` and `j`.

bool	set_space_dimension (dimension_type new_space_dim)
	Sets the number of space dimensions to `new_space_dim`. More...

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

static void	initialize ()
	Initializes the class.

static void	finalize ()
	Finalizes the class.

static const Congruence_System &	zero_dim_empty ()
	Returns the system containing only Congruence::zero_dim_false().

Protected Member Functions
bool	satisfies_all_congruences (const Grid_Generator &g) const
	Returns `true` if `g` satisfies all the congruences.

Related Functions
(Note that these are not member functions.)
bool	operator== (const Congruence_System &x, const Congruence_System &y)

std::ostream &	operator<< (std::ostream &s, const Congruence_System &cgs)
	Output operator. More...

void	swap (Congruence_System &x, Congruence_System &y)

void	swap (Congruence_System &x, Congruence_System &y)

Detailed Description

A system of congruences.

An object of the class Congruence_System is a system of congruences, i.e., a multiset of objects of the class Congruence. When inserting congruences in a system, space dimensions are automatically adjusted so that all the congruences in the system are defined on the same vector space.

: In all the examples it is assumed that variables x and y are defined as follows:
Variable x(0);

Variable y(1);

Example 1: The following code builds a system of congruences corresponding to an integer grid in $\Rset^2$ :
Congruence_System cgs;

cgs.insert(x %= 0);

cgs.insert(y %= 0);

Note that: the congruence system is created with space dimension zero; the first and second congruence insertions increase the space dimension to and , respectively.

Example 2: By adding to the congruence system of the previous example, the congruence $x + y = 1 \pmod{2}$ :
cgs.insert((x + y %= 1) / 2);

we obtain the grid containing just those integral points where the sum of the x and y values is odd.

Example 3: The following code builds a system of congruences corresponding to the grid in $\Zset^2$ containing just the integral points on the x axis:
Congruence_System cgs;

cgs.insert(x %= 0);

cgs.insert((y %= 0) / 0);

Note: After inserting a multiset of congruences in a congruence system, there are no guarantees that an exact copy of them can be retrieved: in general, only an equivalent congruence system will be available, where original congruences may have been reordered, removed (if they are trivial, duplicate or implied by other congruences), linearly combined, etc.

Constructor & Destructor Documentation

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

inlineexplicit

If c represents the constraint $ e_1 = e_2 $ , builds the singleton system containing only constraint $e_1 = e_2 \pmod{0}$ .

Exceptions

std::invalid_argument Thrown if c is not an equality constraint.

Parma_Polyhedra_Library::Congruence_System::Congruence_System ( const Congruence_System & cgs )

inline

Ordinary copy constructor.

Note: The new Congruence_System will have the same Representation as `cgs' so that it's indistinguishable from `cgs'.

Member Function Documentation

void Parma_Polyhedra_Library::Congruence_System::insert ( const Congruence & cg )

inline

Inserts in *this a copy of the congruence cg, increasing the number of space dimensions if needed.

The copy of cg will be strongly normalized after being inserted.

void Parma_Polyhedra_Library::Congruence_System::insert	(	Congruence &	cg,
		Recycle_Input
	)

inline

Inserts in *this the congruence cg, stealing its contents and increasing the number of space dimensions if needed.

cg will be strongly normalized.

void Parma_Polyhedra_Library::Congruence_System::insert ( const Constraint & c )

Inserts in *this a copy of the equality constraint c, seen as a modulo 0 congruence, increasing the number of space dimensions if needed.

The modulo 0 congruence will be strongly normalized after being inserted.

Exceptions

std::invalid_argument Thrown if c is a relational constraint.

void Parma_Polyhedra_Library::Congruence_System::insert ( const Congruence_System & y )

Inserts in *this a copy of the congruences in y, increasing the number of space dimensions if needed.

The inserted copies will be strongly normalized.

void Parma_Polyhedra_Library::Congruence_System::add_unit_rows_and_space_dimensions ( dimension_type dims )

Adds dims rows and dims space dimensions to the matrix, initializing the added rows as in the unit congruence system.

Parameters

dims	The number of rows and space dimensions to be added: must be strictly positive.

Turns the $r \times c$ matrix $A$ into the $(r+dims) \times (c+dims)$ matrix $\bigl(\genfrac{}{}{0pt}{}{0}{A} \genfrac{}{}{0pt}{}{B}{A}\bigr)$ where $B$ is the $dims \times dims$ unit matrix of the form $\bigl(\genfrac{}{}{0pt}{}{0}{1} \genfrac{}{}{0pt}{}{1}{0}\bigr)$ . The matrix is expanded avoiding reallocation whenever possible.

void Parma_Polyhedra_Library::Congruence_System::permute_space_dimensions ( const std::vector< Variable > & cycle )

Permutes the space dimensions of the system.

Parameters

cycle A vector representing a cycle of the permutation according to which the columns must be rearranged.

The cycle vector represents a cycle of a permutation of space dimensions. For example, the permutation $\{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}$ can be represented by the vector containing $ x_1, x_2, x_3 $ .

bool Parma_Polyhedra_Library::Congruence_System::set_space_dimension ( dimension_type new_space_dim )

Sets the number of space dimensions to new_space_dim.

If new_space_dim is lower than the current space dimension, the coefficients referring to the removed space dimensions are lost.

Friends And Related Function Documentation

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

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

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

void swap	(	Congruence_System &	x,
		Congruence_System &	y
	)

void swap	(	Congruence_System &	x,
		Congruence_System &	y
	)

ppl.hh

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation