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

A system of congruences. More...

List of all members.

Public Member Functions

 Congruence_System ()
 Default constructor: builds an empty system of congruences.
 Congruence_System (const Congruence &cg)
 Builds the singleton system containing only congruence cg.
 Congruence_System (const Constraint &c)
 If c represents the constraint $ e_1 = e_2 $, builds the singleton system containing only constraint $ e_1 = e_2 \pmod{0}$.
 Congruence_System (const Constraint_System &cs)
 Builds a system containing copies of any equalities in cs.
 Congruence_System (const Congruence_System &cgs)
 Ordinary copy-constructor.
 ~Congruence_System ()
 Destructor.
Congruence_Systemoperator= (const Congruence_System &cgs)
 Assignment operator.
dimension_type space_dimension () const
 Returns the dimension of the vector space enclosing *this.
bool is_equal_to (const Congruence_System &cgs) const
 Returns true if and only if *this is exactly equal to cgs.
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.
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.
void insert (const Congruence_System &cgs)
 Inserts in *this a copy of the congruences in cgs, increasing the number of space dimensions if needed.
void recycling_insert (Congruence_System &cgs)
 Inserts into *this the congruences in cgs, increasing the number of space dimensions if needed.
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.
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 swap (Congruence_System &cgs)
 Swaps *this with y.
void add_unit_rows_and_columns (dimension_type dims)
 Adds dims rows and dims columns of zeroes to the matrix, initializing the added rows as in the unit congruence system.
void concatenate (const Congruence_System &cgs)
 Concatenates copies of the congruences from cgs onto *this.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Congruence_System can handle.
static const Congruence_Systemzero_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.

Friends

void swap (Parma_Polyhedra_Library::Congruence_System &x, Parma_Polyhedra_Library::Congruence_System &y)
 Specializes std::swap.
bool operator== (const Congruence_System &x, const Congruence_System &y)
 Returns true if and only if x and y are equivalent.

Related Functions

(Note that these are not member functions.)

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

Classes

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


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 $1$ and $2$, 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  )  [inline, explicit]

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.


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 ( 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 relation.

void Parma_Polyhedra_Library::Congruence_System::insert ( const Congruence_System cgs  ) 

Inserts in *this a copy of the congruences in cgs, 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_columns ( dimension_type  dims  ) 

Adds dims rows and dims columns of zeroes to the matrix, initializing the added rows as in the unit congruence system.

Parameters:
dims The number of rows and columns to be added: must be strictly positive.
Turns the $r \times c$ matrix $A$ into the $(r+dims) \times (c+dims)$ matrix $\bigl({0 \atop A}{B \atop A}\bigr)$ where $B$ is the $dims \times dims$ unit matrix of the form $\bigl({0 \atop 1}{1 \atop 0}\bigr)$. The matrix is expanded avoiding reallocation whenever possible.

void Parma_Polyhedra_Library::Congruence_System::concatenate ( const Congruence_System cgs  ) 

Concatenates copies of the congruences from cgs onto *this.

The matrix for the new system of congruences is obtained by leaving the old system in the upper left-hand side and placing the congruences of cgs in the lower right-hand side, and padding with zeroes.


Friends And Related Function Documentation

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

Output operator.

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


Generated on Sun Mar 12 09:14:31 2006 for PPL by  doxygen 1.4.6-20060227