PPL  1.0
Parma_Polyhedra_Library::Congruence_System Class Reference

A system of congruences. More...

#include <ppl.hh>

List of all members.

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 $ e_1 = e_2 $, builds the singleton system containing only constraint $ e_1 = e_2 \pmod{0}$.
 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.
 Congruence_System (const Congruence_System &cgs, Representation r)
 Copy constructor with specified representation.
 ~Congruence_System ()
 Destructor.
Congruence_Systemoperator= (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.
void insert (Congruence &cg, Recycle_Input)
 Inserts in *this the congruence cg, stealing its contents and 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 &y)
 Inserts in *this a copy of the congruences in y, increasing the number of space dimensions if needed.
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.
void permute_space_dimensions (const std::vector< Variable > &cycle)
 Permutes the space dimensions of the system.
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.

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

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.
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$:
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:
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_argumentThrown 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_argumentThrown 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:
dimsThe 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:
cycleA 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 
)
related
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 ", ".

void swap ( Congruence_System x,
Congruence_System y 
)
related
void swap ( Congruence_System x,
Congruence_System y 
)
related

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