A system of congruences. More...

#include <Congruence_System_defs.hh>

Collaboration diagram for Parma_Polyhedra_Library::Congruence_System:

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

Public Types
typedef Congruence	row_type

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

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

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

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

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

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

	~Congruence_System ()
	Destructor. More...

Congruence_System &	operator= (const Congruence_System &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...

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

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

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

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

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

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

const_iterator	end () const
	Returns the past-the-end const_iterator. 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 (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise. More...

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

dimension_type	num_equalities () const
	Returns the number of equalities. More...

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

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

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

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

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

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

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

Static Public Attributes
static const Representation	default_representation = SPARSE

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

Private Member Functions
dimension_type	num_rows () const
	Returns the number of rows in the system. More...

bool	has_no_rows () const
	Returns `true` if num_rows()==0. More...

const Congruence &	operator[] (dimension_type k) const
	Returns a constant reference to the `k-` th congruence of the system. More...

void	normalize_moduli ()
	Adjusts all expressions to have the same moduli. More...

void	affine_preimage (Variable v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
	Substitutes a given column of coefficients by a given affine expression. More...

void	concatenate (const Congruence_System &y)
	Concatenates copies of the congruences from `y` onto `*this`. More...

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

void	remove_rows (dimension_type first, dimension_type last, bool keep_sorted)
	Makes the system shrink by removing the rows in [first,last). More...

void	remove_trailing_rows (dimension_type n)

bool	has_a_free_dimension () const
	Returns `true` if and only if any of the dimensions in `*this` is free of constraint. More...

Private Attributes
Swapping_Vector< Congruence >	rows

dimension_type	space_dimension_

Representation	representation_

Static Private Attributes
static const Congruence_System *	zero_dim_empty_p = 0
	Holds (between class initialization and finalization) a pointer to the singleton system containing only Congruence::zero_dim_false(). More...

Friends
class	Grid

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

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

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

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.

Definition at line 103 of file Congruence_System_defs.hh.

Member Typedef Documentation

typedef Congruence Parma_Polyhedra_Library::Congruence_System::row_type

Definition at line 106 of file Congruence_System_defs.hh.

Constructor & Destructor Documentation

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

inlineexplicit

Default constructor: builds an empty system of congruences.

Definition at line 68 of file Congruence_System_inlines.hh.

   : rows(),
     space_dimension_(0),
     representation_(r) {
 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System	(	dimension_type	d,
		Representation	r = `default_representation`
	)

inlineexplicit

Builds an empty (i.e. zero rows) system of dimension d.

Definition at line 111 of file Congruence_System_inlines.hh.

   : rows(),
     space_dimension_(d),
     representation_(r) {
 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System	(	const Congruence &	cg,
		Representation	r = `default_representation`
	)

inlineexplicit

Builds the singleton system containing only congruence cg.

Definition at line 75 of file Congruence_System_inlines.hh.

References insert().

   : rows(),
     space_dimension_(0),
     representation_(r) {
   insert(cg);
 }

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.

Definition at line 83 of file Congruence_System_inlines.hh.

References insert().

   : rows(),
     space_dimension_(0),
     representation_(r) {
   insert(c);
 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System	(	const Constraint_System &	cs,
		Representation	r = `default_representation`
	)

explicit

Builds a system containing copies of any equalities in cs.

Definition at line 41 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Constraint_System::begin(), Parma_Polyhedra_Library::Constraint_System::end(), and insert().

   : rows(),
     space_dimension_(cs.space_dimension()),
     representation_(r) {
   for (Constraint_System::const_iterator i = cs.begin(),
          cs_end = cs.end(); i != cs_end; ++i) {
     if (i->is_equality()) {
       insert(*i);
     }
   }
 }

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

Definition at line 91 of file Congruence_System_inlines.hh.

   : rows(cgs.rows),
     space_dimension_(cgs.space_dimension_),
     representation_(cgs.representation_) {
 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System	(	const Congruence_System &	cgs,
		Representation	r
	)

inline

Copy constructor with specified representation.

Definition at line 98 of file Congruence_System_inlines.hh.

References num_rows(), representation(), and rows.

   : rows(cgs.rows),
     space_dimension_(cgs.space_dimension_),
     representation_(r) {
   if (cgs.representation() != r) {
     for (dimension_type i = 0; i < num_rows(); ++i) {
       rows[i].set_representation(representation());
     }
   }
 }

Parma_Polyhedra_Library::Congruence_System::~Congruence_System ( )

inline

Destructor.

Definition at line 118 of file Congruence_System_inlines.hh.

118 {

119 }

Member Function Documentation

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.

Definition at line 463 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Coefficient_zero(), Parma_Polyhedra_Library::Linear_Expression::set_space_dimension(), and Parma_Polyhedra_Library::swap().

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

                                                         {
   const dimension_type old_num_rows = num_rows();
   set_space_dimension(space_dimension() + dims);
 
   rows.resize(rows.size() + dims);
 
   // Swap the added rows to the front of the vector.
   for (dimension_type row = old_num_rows; row-- > 0; ) {
     swap(rows[row], rows[row + dims]);
   }
 
   const dimension_type dim = space_dimension();
   // Set the space dimension and the diagonal element of each added row.
   for (dimension_type row = dims; row-- > 0; ) {
     Linear_Expression expr(representation());
     expr.set_space_dimension(space_dimension());
     PPL_ASSERT(dim >= row + 1);
     expr += Variable(dim - row - 1);
     // This constructor steals the contents of `expr'.
     Congruence cg(expr, Coefficient_zero(), Recycle_Input());
     swap(rows[row], cg);
   }
 
   PPL_ASSERT(OK());
 }

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

private

Substitutes a given column of coefficients by a given affine expression.

Parameters

v	Index of the column to which the affine transformation is substituted;
expr	The numerator of the affine transformation: $\sum_{i = 0}^{n - 1} a_i x_i + b$ ;
denominator	The denominator of the affine transformation.

We allow affine transformations (see the Section Operations on Rational Grids) to have rational coefficients. Since the coefficients of linear expressions are integers we also provide an integer denominator that will be used as denominator of the affine transformation. The denominator is required to be a positive integer and its default value is 1.

The affine transformation substitutes the matrix of congruences by a new matrix whose elements ${a'}_{ij}$ are built from the old one $a_{ij}$ as follows:

${a'}_{ij} = \begin{cases} a_{ij} * \mathrm{denominator} + a_{iv} * \mathrm{expr}[j] \quad \text{for } j \neq v; \\ \mathrm{expr}[v] * a_{iv} \quad \text{for } j = v. \end{cases}$

expr is a constant parameter and unaltered by this computation.

Definition at line 329 of file Congruence_System.cc.

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

                                                                {
   PPL_ASSERT(v.space_dimension() <= space_dimension());
   PPL_ASSERT(expr.space_dimension() <= space_dimension());
   PPL_ASSERT(denominator > 0);
 
   for (dimension_type i = num_rows(); i-- > 0; ) {
     rows[i].affine_preimage(v, expr, denominator);
   }
 }

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

Writes to s an ASCII representation of *this.

Definition at line 342 of file Congruence_System.cc.

References Parma_Polyhedra_Library::ascii_dump(), ascii_dump(), num_rows(), and space_dimension().

                                                     {
   const Congruence_System& x = *this;
   const dimension_type x_num_rows = x.num_rows();
   const dimension_type x_space_dim = x.space_dimension();
   s << x_num_rows << " x " << x_space_dim << " ";
   Parma_Polyhedra_Library::ascii_dump(s, representation());
   s << std::endl;
   for (dimension_type i = 0; i < x_num_rows; ++i) {
     x[i].ascii_dump(s);
   }
 }

void Parma_Polyhedra_Library::Congruence_System::ascii_dump ( ) const

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

Referenced by ascii_dump(), and Parma_Polyhedra_Library::Grid::OK().

bool Parma_Polyhedra_Library::Congruence_System::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.

Definition at line 357 of file Congruence_System.cc.

References Parma_Polyhedra_Library::ascii_load(), Parma_Polyhedra_Library::Congruence::ascii_load(), and c.

                                               {
   std::string str;
   dimension_type num_rows;
   dimension_type space_dim;
   if (!(s >> num_rows)) {
     return false;
   }
   if (!(s >> str) || str != "x") {
     return false;
   }
   if (!(s >> space_dim)) {
     return false;
   }
   clear();
   space_dimension_ = space_dim;
 
   if (!Parma_Polyhedra_Library::ascii_load(s, representation_)) {
     return false;
   }
 
   Congruence c;
   for (dimension_type i = 0; i < num_rows; ++i) {
     if (!c.ascii_load(s)) {
       return false;
     }
     insert_verbatim(c, Recycle_Input());
   }
 
   // Check invariants.
   PPL_ASSERT(OK());
   return true;
 }

Congruence_System::const_iterator Parma_Polyhedra_Library::Congruence_System::begin ( ) const

inline

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

Definition at line 230 of file Congruence_System_inlines.hh.

References rows, and Parma_Polyhedra_Library::Congruence_System::const_iterator::skip_forward().

                                {
   const_iterator i(rows.begin(), *this);
   i.skip_forward();
   return i;
 }

void Parma_Polyhedra_Library::Congruence_System::clear ( )

inline

Removes all the congruences and sets the space dimension to 0.

Definition at line 156 of file Congruence_System_inlines.hh.

References rows, and space_dimension_.

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

                          {
   rows.clear();
   space_dimension_ = 0;
 }

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

private

Concatenates copies of the congruences from y onto *this.

Parameters

y	The congruence system to append to `this`. The number of rows in `y` must be strictly positive.

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 y in the lower right-hand side, and padding with zeroes.

Definition at line 490 of file Congruence_System.cc.

References num_rows(), rows, Parma_Polyhedra_Library::Congruence::set_representation(), Parma_Polyhedra_Library::Congruence::shift_space_dimensions(), space_dimension(), and Parma_Polyhedra_Library::swap().

                                                             {
   // TODO: this implementation is just an executable specification.
   Congruence_System cgs = y;
 
   const dimension_type added_rows = cgs.num_rows();
   const dimension_type added_columns = cgs.space_dimension();
 
   const dimension_type old_num_rows = num_rows();
   const dimension_type old_space_dim = space_dimension();
 
   set_space_dimension(space_dimension() + added_columns);
 
   rows.resize(rows.size() + added_rows);
 
   // Move the congruences into *this from `cgs', shifting the
   // coefficients along into the appropriate columns.
   for (dimension_type i = added_rows; i-- > 0; ) {
     Congruence& cg_old = cgs.rows[i];
     Congruence& cg_new = rows[old_num_rows + i];
     cg_old.set_representation(representation());
     cg_old.shift_space_dimensions(Variable(0), old_space_dim);
     swap(cg_old, cg_new);
   }
 }

bool Parma_Polyhedra_Library::Congruence_System::empty ( ) const

inline

Returns true if and only if *this has no congruences.

Definition at line 243 of file Congruence_System_inlines.hh.

References begin(), and end().

                                {
   return begin() == end();
 }

Congruence_System::const_iterator Parma_Polyhedra_Library::Congruence_System::end ( ) const

inline

Returns the past-the-end const_iterator.

Definition at line 237 of file Congruence_System_inlines.hh.

References rows.

                              {
   const const_iterator i(rows.end(), *this);
   return i;
 }

memory_size_type Parma_Polyhedra_Library::Congruence_System::external_memory_in_bytes ( ) const

inline

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

Definition at line 258 of file Congruence_System_inlines.hh.

References rows.

                                                   {
   return rows.external_memory_in_bytes();
 }

void Parma_Polyhedra_Library::Congruence_System::finalize ( )

static

Finalizes the class.

Definition at line 400 of file Congruence_System.cc.

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

                                {
   PPL_ASSERT(zero_dim_empty_p != 0);
   delete zero_dim_empty_p;
   zero_dim_empty_p = 0;
 }

bool Parma_Polyhedra_Library::Congruence_System::has_a_free_dimension ( ) const

private

Returns true if and only if any of the dimensions in *this is free of constraint.

Any equality or proper congruence affecting a dimension constrains that dimension.

This method assumes the system is in minimal form.

Definition at line 310 of file Congruence_System.cc.

                                                  {
   // Search for a dimension that is free of any congruence or equality
   // constraint.  Assumes a minimized system.
   std::set<dimension_type> candidates;
   for (dimension_type i = space_dimension(); i-- > 0; ) {
     candidates.insert(i + 1);
   }
 
   for (dimension_type i = num_rows(); i-- > 0; ) {
     rows[i].expression().has_a_free_dimension_helper(candidates);
     if (candidates.empty()) {
       return false;
     }
   }
   return !candidates.empty();
 }

bool Parma_Polyhedra_Library::Congruence_System::has_linear_equalities ( ) const

Returns true if and only if *this contains one or more linear equalities.

Definition at line 232 of file Congruence_System.cc.

References num_rows().

                                                   {
   const Congruence_System& cgs = *this;
   for (dimension_type i = cgs.num_rows(); i-- > 0; ) {
     if (cgs[i].modulus() == 0) {
       return true;
     }
   }
   return false;
 }

bool Parma_Polyhedra_Library::Congruence_System::has_no_rows ( ) const

inlineprivate

Returns true if num_rows()==0.

Definition at line 42 of file Congruence_System_inlines.hh.

References num_rows().

Referenced by Parma_Polyhedra_Library::Grid::add_recycled_congruences(), and Parma_Polyhedra_Library::Grid::intersection_assign().

                                      {
   return num_rows() == 0;
 }

void Parma_Polyhedra_Library::Congruence_System::initialize ( )

static

Initializes the class.

Definition at line 393 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::zero_dim_false().

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

                                  {
   PPL_ASSERT(zero_dim_empty_p == 0);
   zero_dim_empty_p
     = new Congruence_System(Congruence::zero_dim_false());
 }

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.

Definition at line 53 of file Congruence_System_inlines.hh.

                                               {
   Congruence tmp = cg;
   insert(tmp, Recycle_Input());
 }

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.

Definition at line 59 of file Congruence_System_inlines.hh.

References insert_verbatim(), OK(), Parma_Polyhedra_Library::Congruence::OK(), and Parma_Polyhedra_Library::Congruence::strong_normalize().

                                                        {
   PPL_ASSERT(cg.OK());
   cg.strong_normalize();
   PPL_ASSERT(cg.OK());
   insert_verbatim(cg, Recycle_Input());
   PPL_ASSERT(OK());
 }

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.

Definition at line 132 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Constraint::space_dimension(), Parma_Polyhedra_Library::Congruence::strong_normalize(), and Parma_Polyhedra_Library::swap().

                                                 {
   if (c.space_dimension() > space_dimension()) {
     set_space_dimension(c.space_dimension());
   }
   Congruence cg(c, space_dimension(), representation());
   cg.strong_normalize();
   rows.resize(num_rows() + 1);
 
   swap(cg, rows.back());
 
   PPL_ASSERT(OK());
 }

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.

Definition at line 164 of file Congruence_System.cc.

References num_rows(), rows, space_dimension(), and Parma_Polyhedra_Library::swap().

                                                        {
   Congruence_System& x = *this;
 
   const dimension_type x_num_rows = x.num_rows();
   const dimension_type y_num_rows = y.num_rows();
 
   // Grow to the required size.
   if (space_dimension() < y.space_dimension()) {
     set_space_dimension(y.space_dimension());
   }
 
   rows.resize(rows.size() + y_num_rows);
 
   // Copy the rows of `y', with the new space dimension.
   for (dimension_type i = y_num_rows; i-- > 0; ) {
     Congruence copy(y[i], space_dimension(), representation());
     swap(copy, x.rows[x_num_rows+i]);
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence_System::insert	(	Congruence_System &	cgs,
		Recycle_Input
	)

Inserts into *this the congruences in cgs, increasing the number of space dimensions if needed.

Definition at line 146 of file Congruence_System.cc.

References clear(), num_rows(), rows, space_dimension(), and Parma_Polyhedra_Library::swap().

                                                                   {
   const dimension_type old_num_rows = num_rows();
   const dimension_type cgs_num_rows = cgs.num_rows();
   if (space_dimension() < cgs.space_dimension()) {
     set_space_dimension(cgs.space_dimension());
   }
   rows.resize(old_num_rows + cgs_num_rows);
   for (dimension_type i = cgs_num_rows; i-- > 0; ) {
     cgs.rows[i].set_space_dimension(space_dimension());
     cgs.rows[i].set_representation(representation());
     swap(cgs.rows[i], rows[old_num_rows + i]);
   }
   cgs.clear();
 
   PPL_ASSERT(OK());
 }

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

private

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

This method inserts cg in the given form, instead of first strong normalizing cg as insert would do.

Definition at line 111 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::OK(), Parma_Polyhedra_Library::Congruence::set_representation(), Parma_Polyhedra_Library::Congruence::set_space_dimension(), Parma_Polyhedra_Library::Congruence::space_dimension(), and Parma_Polyhedra_Library::swap().

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

                                                                    {
   // TODO: Remove this.
   PPL_ASSERT(cg.OK());
 
   cg.set_representation(representation());
 
   if (cg.space_dimension() >= space_dimension()) {
     set_space_dimension(cg.space_dimension());
   }
   else {
     cg.set_space_dimension(space_dimension());
   }
 
   rows.resize(num_rows() + 1);
 
   swap(cg, rows.back());
 
   PPL_ASSERT(OK());
 }

bool Parma_Polyhedra_Library::Congruence_System::is_equal_to ( const Congruence_System & y ) const

Returns true if and only if *this is exactly equal to y.

Definition at line 227 of file Congruence_System.cc.

                                                                     {
   return (*this) == cgs;
 }

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

inline

Swaps *this with y.

Definition at line 248 of file Congruence_System_inlines.hh.

References OK(), representation_, rows, space_dimension_, swap(), and Parma_Polyhedra_Library::swap().

Referenced by swap().

                                               {
   using std::swap;
   swap(rows, y.rows);
   swap(space_dimension_, y.space_dimension_);
   swap(representation_, y.representation_);
   PPL_ASSERT(OK());
   PPL_ASSERT(y.OK());
 }

dimension_type Parma_Polyhedra_Library::Congruence_System::max_space_dimension ( )

inlinestatic

Returns the maximum space dimension a Congruence_System can handle.

Definition at line 146 of file Congruence_System_inlines.hh.

References Parma_Polyhedra_Library::Congruence::max_space_dimension().

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

                                        {
   return Congruence::max_space_dimension();
 }

void Parma_Polyhedra_Library::Congruence_System::normalize_moduli ( )

private

Adjusts all expressions to have the same moduli.

Definition at line 186 of file Congruence_System.cc.

References Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::lcm_assign(), num_rows(), and PPL_DIRTY_TEMP_COEFFICIENT.

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

                                        {
   const Congruence_System& cgs = *this;
   dimension_type row = cgs.num_rows();
   if (row > 0) {
     // Calculate the LCM of all the moduli.
     PPL_DIRTY_TEMP_COEFFICIENT(lcm);
     // Find last proper congruence.
     while (true) {
       --row;
       lcm = cgs[row].modulus();
       if (lcm > 0) {
         break;
       }
       if (row == 0) {
         // All rows are equalities.
         return;
       }
     }
     while (row > 0) {
       --row;
       const Coefficient& modulus = cgs[row].modulus();
       if (modulus > 0) {
         lcm_assign(lcm, lcm, modulus);
       }
     }
 
     // Represent every row using the LCM as the modulus.
     PPL_DIRTY_TEMP_COEFFICIENT(factor);
     for (row = num_rows(); row-- > 0; ) {
       const Coefficient& modulus = cgs[row].modulus();
       if (modulus <= 0 || modulus == lcm) {
         continue;
       }
       exact_div_assign(factor, lcm, modulus);
       rows[row].scale(factor);
     }
   }
   PPL_ASSERT(OK());
 }

PPL::dimension_type Parma_Polyhedra_Library::Congruence_System::num_equalities ( ) const

Returns the number of equalities.

Definition at line 251 of file Congruence_System.cc.

Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), Parma_Polyhedra_Library::Grid::congruence_widening_assign(), Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate(), and Parma_Polyhedra_Library::Grid::quick_equivalence_test().

                                            {
   const Congruence_System& cgs = *this;
   dimension_type n = 0;
   for (dimension_type i = num_rows(); i-- > 0 ; ) {
     if (cgs[i].is_equality()) {
       ++n;
     }
   }
   return n;
 }

PPL::dimension_type Parma_Polyhedra_Library::Congruence_System::num_proper_congruences ( ) const

Returns the number of proper congruences.

Definition at line 263 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::is_proper_congruence().

Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PSET >::approximate_partition_aux(), and Parma_Polyhedra_Library::Grid_Certificate::Grid_Certificate().

                                                    {
   const Congruence_System& cgs = *this;
   dimension_type n = 0;
   for (dimension_type i = num_rows(); i-- > 0 ; ) {
     const Congruence& cg = cgs[i];
     if (cg.is_proper_congruence()) {
       ++n;
     }
   }
   return n;
 }

dimension_type Parma_Polyhedra_Library::Congruence_System::num_rows ( ) const

inlineprivate

Returns the number of rows in the system.

Definition at line 37 of file Congruence_System_inlines.hh.

References rows.

                                   {
   return rows.size();
 }

bool Parma_Polyhedra_Library::Congruence_System::OK ( ) const

Checks if all the invariants are satisfied.

Returns true if and only if all rows have space dimension space_dimension_, each row in the system is a valid Congruence and the space dimension is consistent with the number of congruences.

Definition at line 407 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::OK(), Parma_Polyhedra_Library::Congruence::representation(), and Parma_Polyhedra_Library::Congruence::space_dimension().

Referenced by Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), insert(), m_swap(), set_representation(), and Parma_Polyhedra_Library::Grid::simplify().

                                {
   // All rows must have space dimension `space_dimension()'
   // and representation `representation()'.
   for (dimension_type i = num_rows(); i-- > 0; ) {
     const Congruence& cg = rows[i];
     if (cg.space_dimension() != space_dimension()) {
       return false;
     }
     if (cg.representation() != representation()) {
       return false;
     }
     if (!cg.OK()) {
       return false;
     }
   }
   // All checks passed.
   return true;
 }

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

inline

Assignment operator.

Definition at line 122 of file Congruence_System_inlines.hh.

References swap().

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

const Congruence & Parma_Polyhedra_Library::Congruence_System::operator[] ( dimension_type k ) const

inlineprivate

Returns a constant reference to the k- th congruence of the system.

Definition at line 32 of file Congruence_System_inlines.hh.

References rows.

                                                           {
   return rows[k];
 }

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

Definition at line 56 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::permute_space_dimensions().

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

                                                            {
   for (dimension_type k = rows.size(); k-- > 0; ) {
     Congruence& rows_k = rows[k];
     rows_k.permute_space_dimensions(cycle);
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence_System::print ( ) const

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

void Parma_Polyhedra_Library::Congruence_System::remove_rows	(	dimension_type	first,
		dimension_type	last,
		bool	keep_sorted
	)

private

Makes the system shrink by removing the rows in [first,last).

If keep_sorted is true, the ordering of the remaining rows will be preserved.

Definition at line 65 of file Congruence_System.cc.

References Parma_Polyhedra_Library::swap().

                                                       {
   PPL_ASSERT(first <= last);
   PPL_ASSERT(last <= num_rows());
   const dimension_type n = last - first;
 
   // Swap the rows in [first, last) with the rows in [size() - n, size())
   // (note that these intervals may not be disjunct).
   if (keep_sorted) {
     for (dimension_type i = last; i < rows.size(); ++i) {
       swap(rows[i], rows[i - n]);
     }
   }
   else {
     const dimension_type offset = rows.size() - n - first;
     for (dimension_type i = first; i < last; ++i) {
       swap(rows[i], rows[i + offset]);
     }
   }
 
   rows.resize(rows.size() - n);
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Congruence_System::remove_trailing_rows ( dimension_type n )

inlineprivate

Definition at line 47 of file Congruence_System_inlines.hh.

References num_rows(), and rows.

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

                                                         {
   PPL_ASSERT(num_rows() >= n);
   rows.resize(num_rows() - n);
 }

Representation Parma_Polyhedra_Library::Congruence_System::representation ( ) const

inline

Returns the current representation of *this.

Definition at line 129 of file Congruence_System_inlines.hh.

References representation_.

Referenced by Congruence_System().

                                         {
   return representation_;
 }

bool Parma_Polyhedra_Library::Congruence_System::satisfies_all_congruences ( const Grid_Generator & g ) const

protected

Returns true if g satisfies all the congruences.

Definition at line 277 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Scalar_Products::assign(), Parma_Polyhedra_Library::Grid_Generator::divisor(), Parma_Polyhedra_Library::Congruence::is_equality(), Parma_Polyhedra_Library::Grid_Generator::is_line(), Parma_Polyhedra_Library::Congruence::modulus(), PPL_DIRTY_TEMP_COEFFICIENT, and Parma_Polyhedra_Library::Grid_Generator::space_dimension().

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

                                                          {
   PPL_ASSERT(g.space_dimension() <= space_dimension());
 
   const Congruence_System& cgs = *this;
   PPL_DIRTY_TEMP_COEFFICIENT(sp);
   if (g.is_line()) {
     for (dimension_type i = cgs.num_rows(); i-- > 0; ) {
       const Congruence& cg = cgs[i];
       Scalar_Products::assign(sp, g, cg);
       if (sp != 0) {
         return false;
       }
     }
   }
   else {
     const Coefficient& divisor = g.divisor();
     for (dimension_type i = cgs.num_rows(); i-- > 0; ) {
       const Congruence& cg = cgs[i];
       Scalar_Products::assign(sp, g, cg);
       if (cg.is_equality()) {
         if (sp != 0) {
           return false;
         }
       }
       else if (sp % (cg.modulus() * divisor) != 0) {
         return false;
       }
     }
   }
   return true;
 }

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

inline

Converts *this to the specified representation.

Definition at line 134 of file Congruence_System_inlines.hh.

References num_rows(), OK(), representation_, and rows.

                                                       {
   if (representation_ == r) {
     return;
   }
   representation_ = r;
   for (dimension_type i = 0; i < num_rows(); ++i) {
     rows[i].set_representation(r);
   }
   PPL_ASSERT(OK());
 }

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.

Definition at line 92 of file Congruence_System.cc.

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Grid::remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Grid::set_empty().

                                                         {
   if (space_dimension() != new_space_dim) {
     space_dimension_ = new_space_dim;
     for (dimension_type i = num_rows(); i-- > 0; ) {
       rows[i].set_space_dimension(new_space_dim);
     }
   }
   PPL_ASSERT(OK());
   return true;
 }

dimension_type Parma_Polyhedra_Library::Congruence_System::space_dimension ( ) const

inline

Returns the dimension of the vector space enclosing *this.

Definition at line 151 of file Congruence_System_inlines.hh.

References space_dimension_.

                                          {
   return space_dimension_;
 }

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

Swaps the columns having indexes i and j.

Definition at line 104 of file Congruence_System.cc.

                                                                     {
   for (dimension_type k = num_rows(); k-- > 0; ) {
     rows[k].swap_space_dimensions(v1, v2);
   }
 }

memory_size_type Parma_Polyhedra_Library::Congruence_System::total_memory_in_bytes ( ) const

inline

Returns the total size in bytes of the memory occupied by *this.

Definition at line 263 of file Congruence_System_inlines.hh.

References rows.

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

const Congruence_System & Parma_Polyhedra_Library::Congruence_System::zero_dim_empty ( )

inlinestatic

Returns the system containing only Congruence::zero_dim_false().

Definition at line 162 of file Congruence_System_inlines.hh.

References zero_dim_empty_p.

Referenced by Parma_Polyhedra_Library::Box< ITV >::congruences(), Parma_Polyhedra_Library::BD_Shape< T >::minimized_congruences(), and Parma_Polyhedra_Library::Octagonal_Shape< T >::minimized_congruences().

                                   {
   PPL_ASSERT(zero_dim_empty_p != 0);
   return *zero_dim_empty_p;
 }

Friends And Related Function Documentation

friend class Grid

friend

Definition at line 516 of file Congruence_System_defs.hh.

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

References begin(), end(), and Parma_Polyhedra_Library::Congruence::strong_normalize().

                                                                        {
   Congruence_System::const_iterator i = cgs.begin();
   const Congruence_System::const_iterator cgs_end = cgs.end();
   if (i == cgs_end) {
     return s << "true";
   }
   while (true) {
     Congruence cg = *i;
     cg.strong_normalize();
     s << cg;
     ++i;
     if (i == cgs_end) {
       return s;
     }
     s << ", ";
   }
 }

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 ", ".

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

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

References num_rows().

                                                                       {
   if (x.num_rows() != y.num_rows()) {
     return false;
   }
   for (dimension_type i = x.num_rows(); i-- > 0; ) {
     // NOTE: this also checks for space dimension.
     if (x[i] != y[i]) {
       return false;
     }
   }
   return true;
 }

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

friend

void swap	(	Congruence_System &	x,
		Congruence_System &	y
	)

References m_swap().

                                                  {
   x.m_swap(y);
 }

void swap	(	Congruence_System &	x,
		Congruence_System &	y
	)

Member Data Documentation

const Representation Parma_Polyhedra_Library::Congruence_System::default_representation = SPARSE

static

Definition at line 108 of file Congruence_System_defs.hh.

Representation Parma_Polyhedra_Library::Congruence_System::representation_

private

Definition at line 503 of file Congruence_System_defs.hh.

Referenced by m_swap(), representation(), and set_representation().

Swapping_Vector<Congruence> Parma_Polyhedra_Library::Congruence_System::rows

private

Definition at line 499 of file Congruence_System_defs.hh.

Referenced by begin(), clear(), concatenate(), Congruence_System(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::conversion(), end(), external_memory_in_bytes(), insert(), m_swap(), num_rows(), operator[](), remove_trailing_rows(), set_representation(), Parma_Polyhedra_Library::Grid::simplify(), and total_memory_in_bytes().

dimension_type Parma_Polyhedra_Library::Congruence_System::space_dimension_

private

Definition at line 501 of file Congruence_System_defs.hh.

Referenced by clear(), m_swap(), and space_dimension().

const PPL::Congruence_System * Parma_Polyhedra_Library::Congruence_System::zero_dim_empty_p = 0

staticprivate

Holds (between class initialization and finalization) a pointer to the singleton system containing only Congruence::zero_dim_false().

Definition at line 497 of file Congruence_System_defs.hh.

Referenced by zero_dim_empty().

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

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