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

A system of congruences. More...

#include <Congruence_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Congruence_System:

Inheritance graph
[legend]
Collaboration diagram for Parma_Polyhedra_Library::Congruence_System:

Collaboration graph
[legend]

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

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.

Private Member Functions

 Congruence_System (dimension_type d)
 Builds an empty (i.e. zero rows) system of dimension d.
void concatenate (const Congruence_System &cgs)
 Concatenates copies of the congruences from cgs onto *this.
void normalize_moduli ()
 Adjusts all expressions to have the same moduli.
bool increase_space_dimension (dimension_type new_space_dim)
 Increase the number of space dimensions to new_space_dim.
void insert_verbatim (const Congruence &cg)
 Inserts in *this an exact copy of the congruence cg, increasing the number of space dimensions if needed.
Congruence & operator[] (dimension_type k)
 Returns the k- th congruence of the system.
const Congruence & operator[] (dimension_type k) const
 Returns a constant reference to the k- th congruence of the system.
bool has_a_free_dimension () const
 Returns true if and only if any of the dimensions in *this is free of constraint.
void affine_preimage (dimension_type v, const Linear_Expression &expr, Coefficient_traits::const_reference denominator)
 Substitutes a given column of coefficients by a given affine expression.
void remove_higher_space_dimensions (dimension_type new_dimension)
 Removes the higher dimensions of the system so that the resulting system will have dimension new_dimension.
void resize_no_copy (dimension_type new_num_rows, dimension_type new_num_columns)
 Resizes the system without worrying about the old contents.

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

Friends

class const_iterator
class Grid
class Grid_Certificate
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)

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.

Definition at line 120 of file Congruence_System.defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Congruence_System::Congruence_System (  )  [inline]

Default constructor: builds an empty system of congruences.

Definition at line 48 of file Congruence_System.inlines.hh.

Referenced by initialize().

00049   : Matrix(0, 2) {
00050 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System ( const Congruence &  cg  )  [inline, explicit]

Builds the singleton system containing only congruence cg.

Definition at line 53 of file Congruence_System.inlines.hh.

References insert().

00054   : Matrix(0, 2) {
00055   insert(cg);
00056 }

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.

Definition at line 59 of file Congruence_System.inlines.hh.

References insert().

00060   : Matrix(0, 2) {
00061   insert(c);
00062 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System ( const Constraint_System &  cs  )  [explicit]

Builds a system containing copies of any equalities in cs.

Definition at line 40 of file Congruence_System.cc.

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

00041   : Matrix(0, cs.space_dimension() + 2) {
00042   for (Constraint_System::const_iterator i = cs.begin(),
00043          cs_end = cs.end(); i != cs_end; ++i)
00044     if (i->is_equality())
00045       insert(*i);
00046 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System ( const Congruence_System &  cgs  )  [inline]

Ordinary copy-constructor.

Definition at line 65 of file Congruence_System.inlines.hh.

00066   : Matrix(cs) {
00067 }

Parma_Polyhedra_Library::Congruence_System::~Congruence_System (  )  [inline]

Destructor.

Definition at line 75 of file Congruence_System.inlines.hh.

00075                                       {
00076 }

Parma_Polyhedra_Library::Congruence_System::Congruence_System ( dimension_type  d  )  [inline, explicit, private]

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

Definition at line 70 of file Congruence_System.inlines.hh.

00071   : Matrix(0, d + 2) {
00072 }

Member Function Documentation

Congruence_System & Parma_Polyhedra_Library::Congruence_System::operator= ( const Congruence_System &  cgs  )  [inline]

Assignment operator.

Definition at line 79 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::operator=().

00079                                                        {
00080   Matrix::operator=(y);
00081   return *this;
00082 }

dimension_type Parma_Polyhedra_Library::Congruence_System::max_space_dimension (  )  [inline, static]

Returns the maximum space dimension a Congruence_System can handle.

Definition at line 85 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::max_num_columns().

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

00085                                        {
00086   return Matrix::max_num_columns() - 2;
00087 }

dimension_type Parma_Polyhedra_Library::Congruence_System::space_dimension (  )  const [inline]

Returns the dimension of the vector space enclosing *this.

Definition at line 90 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::num_columns().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Grid::add_congruences(), Parma_Polyhedra_Library::Box< ITV >::add_congruences(), Parma_Polyhedra_Library::Box< ITV >::add_congruences_no_check(), Parma_Polyhedra_Library::Grid::add_recycled_congruences(), Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize(), affine_preimage(), Parma_Polyhedra_Library::Box< ITV >::Box(), concatenate(), Parma_Polyhedra_Library::Grid::construct(), has_a_free_dimension(), increase_space_dimension(), Parma_Polyhedra_Library::Grid::limited_congruence_extrapolation_assign(), Parma_Polyhedra_Library::Grid::limited_extrapolation_assign(), Parma_Polyhedra_Library::Grid::limited_generator_extrapolation_assign(), Parma_Polyhedra_Library::Octagonal_Shape< T >::Octagonal_Shape(), Parma_Polyhedra_Library::Grid::OK(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_with_congruences(), Parma_Polyhedra_Library::Box< ITV >::refine_with_congruences(), Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruences(), remove_higher_space_dimensions(), satisfies_all_congruences(), Parma_Polyhedra_Library::Grid::select_wider_congruences(), Parma_Polyhedra_Library::Polyhedron::throw_dimension_incompatible(), Parma_Polyhedra_Library::Grid::throw_dimension_incompatible(), and Parma_Polyhedra_Library::Box< ITV >::throw_dimension_incompatible().

00090                                          {
00091   return Matrix::num_columns() - 2;
00092 }

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

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

Definition at line 223 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().

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

00223                                                                     {
00224   if (num_rows() != cgs.num_rows())
00225     return false;
00226 
00227   for (dimension_type row = cgs.num_rows(); row-- > 0; )
00228     for (dimension_type col = cgs.num_columns(); col-- > 0; ) {
00229       if (operator[](row)[col] == cgs[row][col])
00230         continue;
00231       return false;
00232     }
00233   return true;
00234 }

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 237 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().

00237                                                   {
00238   const Congruence_System& cgs = *this;
00239   const dimension_type modulus_index = cgs.num_columns() - 1;
00240   for (dimension_type i = cgs.num_rows(); i-- > 0; )
00241     if (cgs[i][modulus_index] == 0)
00242       return true;
00243   return false;
00244 }

void Parma_Polyhedra_Library::Congruence_System::clear (  )  [inline]

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 95 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), and Parma_Polyhedra_Library::Matrix::clear().

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

00095                          {
00096   Matrix::clear();
00097   add_zero_columns(2);          // Modulus and constant term.
00098 }

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 41 of file Congruence_System.inlines.hh.

References insert_verbatim(), OK(), operator[](), and Parma_Polyhedra_Library::Matrix::rows.

Referenced by Parma_Polyhedra_Library::Grid::add_congruence_no_check(), Congruence_System(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::congruences(), Parma_Polyhedra_Library::Box< ITV >::congruences(), Parma_Polyhedra_Library::Grid::construct(), Parma_Polyhedra_Library::Grid::contains_integer_point(), Parma_Polyhedra_Library::Grid::Grid(), Parma_Polyhedra_Library::Grid::intersection_assign(), Parma_Polyhedra_Library::Grid::limited_congruence_extrapolation_assign(), Parma_Polyhedra_Library::Grid::limited_extrapolation_assign(), Parma_Polyhedra_Library::Grid::limited_generator_extrapolation_assign(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::minimized_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::minimized_congruences(), Parma_Polyhedra_Library::BD_Shape< T >::minimized_congruences(), and Parma_Polyhedra_Library::Grid::select_wider_congruences().

00041                                               {
00042   insert_verbatim(cg);
00043   static_cast<Congruence&>(operator[](rows.size()-1)).strong_normalize();
00044   assert(OK());
00045 }

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 99 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_recycled_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::has_no_rows(), Parma_Polyhedra_Library::Matrix::num_columns(), OK(), operator[](), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::rows, Parma_Polyhedra_Library::Constraint::space_dimension(), and Parma_Polyhedra_Library::Matrix::swap_columns().

00099                                                 {
00100   const dimension_type cg_size = c.space_dimension() + 2;
00101   const dimension_type old_num_columns = num_columns();
00102   if (cg_size < old_num_columns) {
00103     // Create a congruence of the required size from `c'.
00104     Congruence cg(c, old_num_columns, row_capacity);
00105     add_recycled_row(cg);
00106   }
00107   else {
00108     if (cg_size > old_num_columns) {
00109       // Resize the system, if necessary.
00110       add_zero_columns(cg_size - old_num_columns);
00111       if (!has_no_rows())
00112         // Move the moduli to the last column.
00113         swap_columns(old_num_columns - 1, cg_size - 1);
00114     }
00115     Congruence cg(c, cg_size, row_capacity);
00116     add_recycled_row(cg);
00117   }
00118   operator[](rows.size()-1).strong_normalize();
00119 
00120   assert(OK());
00121 }

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.

Definition at line 155 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Matrix::swap_columns().

00155                                                        {
00156   Congruence_System& x = *this;
00157 
00158   const dimension_type x_num_rows = x.num_rows();
00159   const dimension_type y_num_rows = y.num_rows();
00160   const dimension_type old_num_columns = x.num_columns();
00161   const dimension_type y_num_columns = y.num_columns();
00162   // Grow to the required size.
00163   if (old_num_columns >= y_num_columns)
00164     add_zero_rows(y_num_rows, Row::Flags());
00165   else {
00166     add_zero_rows_and_columns(y_num_rows,
00167                               y_num_columns - old_num_columns,
00168                               Row::Flags());
00169     // Swap the modulus column into the new last column.
00170     swap_columns(old_num_columns - 1, num_columns() - 1);
00171   }
00172 
00173   // Copy the rows of `y', forcing size and capacity.
00174   const dimension_type x_mod_index = x.num_columns() - 1;
00175   const dimension_type y_mod_index = y_num_columns - 1;
00176   for (dimension_type i = y_num_rows; i-- > 0; ) {
00177     Row copy(y[i], x.row_size, x.row_capacity);
00178     // Swap the modulus to the correct column.
00179     std::swap(copy[x_mod_index], copy[y_mod_index]);
00180     std::swap(copy, x[x_num_rows+i]);
00181   }
00182   assert(OK());
00183 }

void Parma_Polyhedra_Library::Congruence_System::recycling_insert ( Congruence_System &  cgs  ) 

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

Definition at line 124 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), operator[](), Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00124                                                              {
00125   const dimension_type old_num_rows = num_rows();
00126   const dimension_type cgs_num_rows = cgs.num_rows();
00127   const dimension_type old_num_columns = num_columns();
00128   dimension_type cgs_num_columns = cgs.num_columns();
00129   if (old_num_columns >= cgs_num_columns)
00130     add_zero_rows(cgs_num_rows, Row::Flags());
00131   else {
00132     add_zero_rows_and_columns(cgs_num_rows,
00133                               cgs_num_columns - old_num_columns,
00134                               Row::Flags());
00135     // Swap the modulus column into the new last column.
00136     swap_columns(old_num_columns - 1, num_columns() - 1);
00137   }
00138   --cgs_num_columns; // Convert to modulus index.
00139   const dimension_type mod_index = num_columns() - 1;
00140   for (dimension_type i = cgs_num_rows; i-- > 0; ) {
00141     // Swap one coefficient at a time into the newly added rows, instead
00142     // of swapping each entire row.  This ensures that the added rows
00143     // have the same capacities as the existing rows.
00144     Congruence& new_cg = operator[](old_num_rows + i);
00145     Congruence& old_cg = cgs[i];
00146     for (dimension_type j = cgs_num_columns; j-- > 0; )
00147       std::swap(new_cg[j], old_cg[j]);
00148     std::swap(new_cg[mod_index], old_cg[cgs_num_columns]); // Modulus.
00149   }
00150 
00151   assert(OK());
00152 }

void Parma_Polyhedra_Library::Congruence_System::initialize (  )  [static]

Initializes the class.

Definition at line 430 of file Congruence_System.cc.

References Congruence_System(), zero_dim_empty_p, and Parma_Polyhedra_Library::Congruence::zero_dim_false().

00430                                  {
00431   assert(zero_dim_empty_p == 0);
00432   zero_dim_empty_p
00433     = new Congruence_System(Congruence::zero_dim_false());
00434 }

void Parma_Polyhedra_Library::Congruence_System::finalize (  )  [static]

Finalizes the class.

Definition at line 437 of file Congruence_System.cc.

References zero_dim_empty_p.

00437                                {
00438   assert(zero_dim_empty_p != 0);
00439   delete zero_dim_empty_p;
00440   zero_dim_empty_p = 0;
00441 }

const Congruence_System & Parma_Polyhedra_Library::Congruence_System::zero_dim_empty (  )  [inline, static]

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

Definition at line 107 of file Congruence_System.inlines.hh.

References zero_dim_empty_p.

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

00107                                   {
00108   assert(zero_dim_empty_p != 0);
00109   return *zero_dim_empty_p;
00110 }

bool Parma_Polyhedra_Library::Congruence_System::empty (  )  const [inline]

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

Definition at line 188 of file Congruence_System.inlines.hh.

References begin(), and end().

00188                                {
00189   return begin() == end();
00190 }

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.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 175 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::begin().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruences(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruences(), Parma_Polyhedra_Library::Box< ITV >::add_congruences_no_check(), Parma_Polyhedra_Library::Grid::add_recycled_congruences(), Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize(), Parma_Polyhedra_Library::Pointset_Powerset< PS >::approximate_partition(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::congruences(), Parma_Polyhedra_Library::Constraint_System::Constraint_System(), Parma_Polyhedra_Library::Grid::difference_assign(), empty(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::minimized_congruences(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_with_congruences(), and Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruences().

00175                                {
00176   const_iterator i(Matrix::begin(), *this);
00177   i.skip_forward();
00178   return i;
00179 }

Congruence_System::const_iterator Parma_Polyhedra_Library::Congruence_System::end (  )  const [inline]

Returns the past-the-end const_iterator.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 182 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::end().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::add_congruences(), Parma_Polyhedra_Library::BD_Shape< T >::add_congruences(), Parma_Polyhedra_Library::Box< ITV >::add_congruences_no_check(), Parma_Polyhedra_Library::Grid::add_recycled_congruences(), Parma_Polyhedra_Library::Grid::add_recycled_congruences_and_minimize(), Parma_Polyhedra_Library::Pointset_Powerset< PS >::approximate_partition(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::congruences(), Parma_Polyhedra_Library::Constraint_System::Constraint_System(), Parma_Polyhedra_Library::Grid::difference_assign(), empty(), Parma_Polyhedra_Library::Grid::expand_space_dimension(), Parma_Polyhedra_Library::Partially_Reduced_Product< D1, D2, R >::minimized_congruences(), Parma_Polyhedra_Library::Box< ITV >::refine_no_check(), Parma_Polyhedra_Library::Polyhedron::refine_with_congruences(), Parma_Polyhedra_Library::Octagonal_Shape< T >::refine_with_congruences(), and Parma_Polyhedra_Library::BD_Shape< T >::refine_with_congruences().

00182                              {
00183   const const_iterator i(Matrix::end(), *this);
00184   return i;
00185 }

bool Parma_Polyhedra_Library::Congruence_System::OK (  )  const

Checks if all the invariants are satisfied.

Returns true if and only if *this is a valid Matrix, each row in the system is a valid Congruence and the number of columns is consistent with the number of congruences.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 444 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Congruence::OK(), and Parma_Polyhedra_Library::Matrix::OK().

Referenced by ascii_load(), increase_space_dimension(), insert(), insert_verbatim(), normalize_moduli(), Parma_Polyhedra_Library::Grid::OK(), recycling_insert(), remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Grid::simplify().

00444                                {
00445   // A Congruence_System must be a valid Matrix.
00446   if (!Matrix::OK())
00447     return false;
00448 
00449   if (num_rows()) {
00450     if (num_columns() < 2) {
00451 #ifndef NDEBUG
00452       std::cerr << "Congruence_System has rows and fewer than two columns."
00453                 << std::endl;
00454 #endif
00455       return false;
00456     }
00457   }
00458 
00459   // Checking each congruence in the system.
00460   const Congruence_System& x = *this;
00461   for (dimension_type i = num_rows(); i-- > 0; ) {
00462     const Congruence& cg = x[i];
00463     if (!cg.OK())
00464       return false;
00465   }
00466 
00467   // All checks passed.
00468   return true;
00469 }

void Parma_Polyhedra_Library::Congruence_System::ascii_dump (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

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

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 391 of file Congruence_System.cc.

References ascii_dump(), Parma_Polyhedra_Library::Matrix::num_columns(), and Parma_Polyhedra_Library::Matrix::num_rows().

00391                                                     {
00392   const Congruence_System& x = *this;
00393   dimension_type x_num_rows = x.num_rows();
00394   dimension_type x_num_columns = x.num_columns();
00395   s << x_num_rows << " x " << x_num_columns
00396     << std::endl;
00397   if (x_num_rows && x_num_columns)
00398     for (dimension_type i = 0; i < x_num_rows; ++i)
00399       x[i].ascii_dump(s);
00400 }

void Parma_Polyhedra_Library::Congruence_System::print (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

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.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 405 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), and resize_no_copy().

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

00405                                               {
00406   std::string str;
00407   dimension_type num_rows;
00408   dimension_type num_columns;
00409   if (!(s >> num_rows))
00410     return false;
00411   if (!(s >> str))
00412     return false;
00413   if (!(s >> num_columns))
00414     return false;
00415   resize_no_copy(num_rows, num_columns);
00416 
00417   Congruence_System& x = *this;
00418   for (dimension_type i = 0; i < x.num_rows(); ++i)
00419     if (!x[i].ascii_load(s))
00420       return false;
00421 
00422   // Check invariants.
00423   assert(OK());
00424   return true;
00425 }

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.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 203 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::total_memory_in_bytes().

00203                                                {
00204   return Matrix::total_memory_in_bytes();
00205 }

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.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 198 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::external_memory_in_bytes().

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

00198                                                   {
00199   return Matrix::external_memory_in_bytes();
00200 }

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

Returns the number of equalities.

Definition at line 254 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_rows().

Referenced by Parma_Polyhedra_Library::Pointset_Powerset< PS >::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().

00254                                            {
00255   const Congruence_System& cgs = *this;
00256   dimension_type n = 0;
00257   for (dimension_type i = num_rows(); i-- > 0 ; )
00258     if (cgs[i].is_equality())
00259       ++n;
00260   return n;
00261 }

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

Returns the number of proper congruences.

Definition at line 264 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Congruence::is_proper_congruence(), and Parma_Polyhedra_Library::Matrix::num_rows().

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

00264                                                    {
00265   const Congruence_System& cgs = *this;
00266   dimension_type n = 0;
00267   for (dimension_type i = num_rows(); i-- > 0 ; ) {
00268     const Congruence& cg = cgs[i];
00269     if (cg.is_proper_congruence())
00270       ++n;
00271   }
00272   return n;
00273 }

void Parma_Polyhedra_Library::Congruence_System::swap ( Congruence_System &  cgs  )  [inline]

Swaps *this with y.

Definition at line 193 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::swap().

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

00193                                             {
00194   Matrix::swap(y);
00195 }

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(\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 506 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Linear_Row::LINE_OR_EQUALITY, Parma_Polyhedra_Library::NECESSARILY_CLOSED, Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Matrix::swap_columns().

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions(), and Parma_Polyhedra_Library::Grid::add_space_dimensions_and_project().

00506                                                                    {
00507   assert(num_columns() > 0);
00508   dimension_type col = num_columns() - 1;
00509   dimension_type old_num_rows = num_rows();
00510   add_zero_rows_and_columns(dims, dims,
00511                             Linear_Row::Flags(NECESSARILY_CLOSED,
00512                                               Linear_Row::LINE_OR_EQUALITY));
00513   // Swap the modulus column into the new last column.
00514   swap_columns(col, col + dims);
00515 
00516   // Swap the added columns to the front of the matrix.
00517   for (dimension_type row = old_num_rows; row-- > 0; )
00518     std::swap(operator[](row), operator[](row + dims));
00519 
00520   col += dims - 1;
00521   // Set the diagonal element of each added row.
00522   for (dimension_type row = dims; row-- > 0; )
00523     const_cast<Coefficient&>(operator[](row)[col - row]) = 1;
00524 }

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 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(), space_dimension(), Parma_Polyhedra_Library::Grid_Generator::space_dimension(), and TEMP_INTEGER.

Referenced by Parma_Polyhedra_Library::Grid::is_included_in(), Parma_Polyhedra_Library::Grid::is_universe(), and Parma_Polyhedra_Library::Grid::relation_with().

00277                                                          {
00278   assert(g.space_dimension() <= space_dimension());
00279 
00280   const Congruence_System& cgs = *this;
00281   TEMP_INTEGER(sp);
00282   if (g.is_line())
00283     for (dimension_type i = cgs.num_rows(); i-- > 0; ) {
00284       const Congruence& cg = cgs[i];
00285       Scalar_Products::assign(sp, g, cg);
00286       if (sp != 0)
00287         return false;
00288     }
00289   else {
00290     const Coefficient& divisor = g.divisor();
00291     for (dimension_type i = cgs.num_rows(); i-- > 0; ) {
00292       const Congruence& cg = cgs[i];
00293       Scalar_Products::assign(sp, g, cg);
00294       if (cg.is_equality()) {
00295         if (sp != 0)
00296           return false;
00297       }
00298       else if (sp % (cg.modulus() * divisor) != 0)
00299         return false;
00300     }
00301   }
00302   return true;
00303 }

void Parma_Polyhedra_Library::Congruence_System::concatenate ( const Congruence_System &  cgs  )  [private]

Concatenates copies of the congruences from cgs onto *this.

Parameters:
cgs The congruence system to append to this. The number of rows in cgs 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 cgs in the lower right-hand side, and padding with zeroes.

Definition at line 527 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), operator[](), space_dimension(), and Parma_Polyhedra_Library::swap().

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

00527                                                                     {
00528   // TODO: this implementation is just an executable specification.
00529   Congruence_System cgs = const_cgs;
00530 
00531   dimension_type added_rows = cgs.num_rows();
00532   dimension_type added_columns = cgs.space_dimension();
00533 
00534   dimension_type old_num_rows = num_rows();
00535   dimension_type old_modi = num_columns() - 1;
00536   dimension_type old_space_dim = space_dimension();
00537 
00538   add_zero_rows_and_columns(added_rows, added_columns,
00539                             Row::Flags());
00540 
00541   dimension_type cgs_num_columns = cgs.num_columns();
00542   dimension_type modi = num_columns() - 1;
00543 
00544   // Swap the modulus and the new last column, in the old rows.
00545   for (dimension_type i = old_num_rows; i-- > 0; ) {
00546     Congruence& cg = operator[](i);
00547     std::swap(cg[old_modi], cg[modi]);
00548   }
00549 
00550   // Move the congruences into *this from `cgs', shifting the
00551   // coefficients along into the appropriate columns.
00552   for (dimension_type i = added_rows; i-- > 0; ) {
00553     Congruence& cg_old = cgs[i];
00554     Congruence& cg_new = operator[](old_num_rows + i);
00555     // The inhomogeneous term is moved to the same column.
00556     std::swap(cg_new[0], cg_old[0]);
00557     // All homogeneous terms are shifted by `space_dim' columns.
00558     for (dimension_type j = cgs_num_columns; j-- > 1; )
00559       std::swap(cg_old[j], cg_new[old_space_dim + j]);
00560   }
00561 }

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(), Parma_Polyhedra_Library::Congruence::modulus(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), operator[](), Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::Row::size(), and TEMP_INTEGER.

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

00186                                        {
00187   dimension_type row = num_rows();
00188   if (row > 0) {
00189     // Calculate the LCM of all the moduli.
00190     TEMP_INTEGER(lcm);
00191     // Find last proper congruence.
00192     while (true) {
00193       lcm = operator[](--row).modulus();
00194       if (lcm > 0)
00195         break;
00196       if (row == 0)
00197         // All rows are equalities.
00198         return;
00199     }
00200     while (row > 0) {
00201       const Coefficient& modulus = operator[](--row).modulus();
00202       if (modulus > 0)
00203         lcm_assign(lcm, lcm, modulus);
00204     }
00205 
00206     // Represent every row using the LCM as the modulus.
00207     TEMP_INTEGER(factor);
00208     dimension_type row_size = operator[](0).size();
00209     for (row = num_rows(); row-- > 0; ) {
00210       const Coefficient& modulus = operator[](row).modulus();
00211       if (modulus <= 0 || modulus == lcm)
00212         continue;
00213       exact_div_assign(factor, lcm, modulus);
00214       for (dimension_type col = row_size; col-- > 0; )
00215         operator[](row)[col] *= factor;
00216       operator[](row)[row_size-1] = lcm;
00217     }
00218   }
00219   assert(OK());
00220 }

bool Parma_Polyhedra_Library::Congruence_System::increase_space_dimension ( dimension_type  new_space_dim  )  [private]

Increase the number of space dimensions to new_space_dim.

new_space_dim must at least equal to the current space dimension.

Definition at line 50 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), space_dimension(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00050                                                              {
00051   assert(space_dimension() <= new_space_dim);
00052 
00053   const dimension_type cols_to_add = new_space_dim - space_dimension();
00054 
00055   if (cols_to_add) {
00056     if (num_rows()) {
00057       const dimension_type old_num_columns = num_columns();
00058       add_zero_columns(cols_to_add);
00059       // Move the moduli.
00060       swap_columns(num_columns() - 1, old_num_columns - 1);
00061     }
00062     else
00063       // Empty system.
00064       add_zero_columns(cols_to_add);
00065   }
00066 
00067   assert(OK());
00068   return true;
00069 }

void Parma_Polyhedra_Library::Congruence_System::insert_verbatim ( const Congruence &  cg  )  [private]

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

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

Definition at line 72 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::add_recycled_row(), Parma_Polyhedra_Library::Matrix::add_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Matrix::has_no_rows(), Parma_Polyhedra_Library::Matrix::num_columns(), OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00072                                                           {
00073   const dimension_type old_num_columns = num_columns();
00074   const dimension_type cg_size = cg.size();
00075 
00076   if (cg_size > old_num_columns) {
00077     // Resize the system, if necessary.
00078     add_zero_columns(cg_size - old_num_columns);
00079     if (!has_no_rows())
00080       // Move the moduli to the last column.
00081       swap_columns(old_num_columns - 1, cg_size - 1);
00082     add_row(cg);
00083   }
00084   else if (cg_size < old_num_columns) {
00085     // Create a resized copy of `cg'.
00086     Congruence rc(cg, old_num_columns, row_capacity);
00087     // Move the modulus to its place.
00088     std::swap(rc[cg_size - 1], rc[old_num_columns - 1]);
00089     add_recycled_row(rc);
00090   }
00091   else
00092     // Here cg_size == old_num_columns.
00093     add_row(cg);
00094 
00095   assert(OK());
00096 }

Congruence & Parma_Polyhedra_Library::Congruence_System::operator[] ( dimension_type  k  )  [inline, private]

Returns the k- th congruence of the system.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 31 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::operator[]().

Referenced by concatenate(), has_a_free_dimension(), insert(), normalize_moduli(), and recycling_insert().

00031                                                     {
00032   return static_cast<Congruence&>(Matrix::operator[](k));
00033 }

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

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

Definition at line 36 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::operator[]().

00036                                                           {
00037   return static_cast<const Congruence&>(Matrix::operator[](k));
00038 }

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 306 of file Congruence_System.cc.

References Parma_Polyhedra_Library::Matrix::num_rows(), operator[](), and space_dimension().

00306                                                  {
00307   // Search for a dimension that is free of any congruence or equality
00308   // constraint.  Assumes a minimized system.
00309   dimension_type space_dim = space_dimension();
00310   std::vector<bool> free_dim(space_dim, true);
00311   dimension_type free_dims = space_dim;
00312   for (dimension_type row = num_rows(); row-- > 0; ) {
00313     const Congruence& cg = operator[](row);
00314     for (dimension_type dim = space_dim; dim-- > 0; )
00315       if (free_dim[dim] && cg[dim+1] != 0) {
00316         if (--free_dims == 0) {
00317           // All dimensions are constrained.
00318 #ifndef NDEBUG
00319           free_dim[dim] = false;
00320           // Check that there are free_dims dimensions marked free
00321           // in free_dim.
00322           dimension_type count = 0;
00323           for (dimension_type i = space_dim; i-- > 0; )
00324             count += free_dim[i];
00325           assert(count == free_dims);
00326 #endif
00327           return true;
00328         }
00329         free_dim[dim] = false;
00330       }
00331   }
00332   // At least one dimension is free of constraint.
00333   return false;
00334 }

void Parma_Polyhedra_Library::Congruence_System::affine_preimage ( dimension_type  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 338 of file Congruence_System.cc.

References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Linear_Expression::space_dimension(), and space_dimension().

Referenced by Parma_Polyhedra_Library::Grid::affine_image(), and Parma_Polyhedra_Library::Grid::affine_preimage().

00340                                                                {
00341   // `v' is the index of a column corresponding to a "user" variable
00342   // (i.e., it cannot be the inhomogeneous term).
00343   assert(v > 0 && v <= space_dimension());
00344   assert(expr.space_dimension() <= space_dimension());
00345   assert(denominator > 0);
00346 
00347   const dimension_type num_columns = this->num_columns();
00348   const dimension_type num_rows = this->num_rows();
00349   const dimension_type expr_size = expr.size();
00350   const bool not_invertible = (v >= expr_size || expr[v] == 0);
00351   Congruence_System& x = *this;
00352 
00353   if (denominator == 1)
00354     // Optimized computation only considering columns having indexes <
00355     // expr_size.
00356     for (dimension_type i = num_rows; i-- > 0; ) {
00357       Congruence& row = x[i];
00358       Coefficient& row_v = row[v];
00359       if (row_v != 0) {
00360         for (dimension_type j = expr_size; j-- > 0; )
00361           if (j != v)
00362             // row[j] = row[j] + row_v * expr[j]
00363             add_mul_assign(row[j], row_v, expr[j]);
00364         if (not_invertible)
00365           row_v = 0;
00366         else
00367           row_v *= expr[v];
00368       }
00369     }
00370   else
00371     for (dimension_type i = num_rows; i-- > 0; ) {
00372       Congruence& row = x[i];
00373       Coefficient& row_v = row[v];
00374       if (row_v != 0) {
00375         for (dimension_type j = num_columns; j-- > 0; )
00376           if (j != v) {
00377             Coefficient& row_j = row[j];
00378             row_j *= denominator;
00379             if (j < expr_size)
00380               add_mul_assign(row_j, row_v, expr[j]);
00381           }
00382         if (not_invertible)
00383           row_v = 0;
00384         else
00385           row_v *= expr[v];
00386       }
00387     }
00388 }

void Parma_Polyhedra_Library::Congruence_System::remove_higher_space_dimensions ( dimension_type  new_dimension  )  [private]

Removes the higher dimensions of the system so that the resulting system will have dimension new_dimension.

The value of new_dimension must be at most the space dimension of *this.

Definition at line 565 of file Congruence_System.cc.

References OK(), Parma_Polyhedra_Library::Matrix::remove_trailing_columns(), space_dimension(), and Parma_Polyhedra_Library::Matrix::swap_columns().

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

00565                                                                    {
00566   dimension_type space_dim = space_dimension();
00567 
00568   assert(new_dimension <= space_dim);
00569 
00570   // The removal of no dimensions from any system is a no-op.  Note
00571   // that this case also captures the only legal removal of dimensions
00572   // from a system in a 0-dim space.
00573   if (new_dimension == space_dim)
00574     return;
00575 
00576   // Swap the modulus column into the column that will become the last
00577   // column.
00578   swap_columns(new_dimension + 1, space_dim + 1);
00579 
00580   remove_trailing_columns(space_dim - new_dimension);
00581   assert(OK());
00582 }

void Parma_Polyhedra_Library::Congruence_System::resize_no_copy ( dimension_type  new_num_rows,
dimension_type  new_num_columns 
) [inline, private]

Resizes the system without worrying about the old contents.

Parameters:
new_num_rows The number of rows of the resized system;
new_num_columns The number of columns of the resized system.
The system is expanded to the specified dimensions avoiding reallocation whenever possible. The contents of the original system is lost.

Definition at line 101 of file Congruence_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::resize_no_copy().

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

00102                                                                         {
00103   Matrix::resize_no_copy(new_num_rows, new_num_columns, Row::Flags());
00104 }

Friends And Related Function Documentation

friend class const_iterator [friend]

Definition at line 407 of file Congruence_System.defs.hh.

friend class Grid [friend]

Definition at line 408 of file Congruence_System.defs.hh.

friend class Grid_Certificate [friend]

Definition at line 409 of file Congruence_System.defs.hh.

void swap ( Parma_Polyhedra_Library::Congruence_System &  x,
Parma_Polyhedra_Library::Congruence_System &  y 
) [friend]

Specializes std::swap.

Definition at line 214 of file Congruence_System.inlines.hh.

00215                                                   {
00216   x.swap(y);
00217 }

bool operator== ( const Congruence_System &  x,
const Congruence_System &  y 
) [friend]

Definition at line 490 of file Congruence_System.cc.

00490                                                                       {
00491   if (x.num_columns() == y.num_columns()) {
00492     dimension_type num_rows = x.num_rows();
00493     if (num_rows == y.num_rows()) {
00494       while (num_rows--) {
00495         if (x[num_rows] == y[num_rows])
00496           continue;
00497         return false;
00498       }
00499       return true;
00500     }
00501   }
00502   return false;
00503 }

Member Data Documentation

const PPL::Congruence_System * Parma_Polyhedra_Library::Congruence_System::zero_dim_empty_p = 0 [static, private]

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

Definition at line 369 of file Congruence_System.defs.hh.

Referenced by finalize(), initialize(), and zero_dim_empty().

The documentation for this class was generated from the following files:
Generated on Sat Oct 11 10:41:08 2008 for PPL by  doxygen 1.5.6