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

The base class for systems of constraints and generators. More...

#include <Linear_System.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Linear_System:

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

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Linear_System (Topology topol)
 Builds an empty linear system with specified topology.
 Linear_System (Topology topol, dimension_type n_rows, dimension_type n_columns)
 Builds a system with specified topology and dimensions.
 Linear_System (const Linear_System &y)
 Copy-constructor: pending rows are transformed into non-pending ones.
 Linear_System (const Linear_System &y, With_Pending)
 Full copy-constructor: pending rows are copied as pending.
Linear_Systemoperator= (const Linear_System &y)
 Assignment operator: pending rows are transformed into non-pending ones.
void assign_with_pending (const Linear_System &y)
 Full assignment operator: pending rows are copied as pending.
void swap (Linear_System &y)
 Swaps *this with y.
dimension_type space_dimension () const
 Returns the space dimension of the rows in the system.
void remove_trailing_columns (dimension_type n)
 Makes the system shrink by removing its n trailing columns.
void permute_columns (const std::vector< dimension_type > &cycles)
 Permutes the columns of the system.
void strong_normalize ()
 Strongly normalizes the system.
void sign_normalize ()
 Sign-normalizes the system.
bool check_sorted () const
 Returns true if and only if *this is sorted, without checking for duplicates.
void set_necessarily_closed ()
 Sets the system topology to NECESSARILY_CLOSED.
void set_not_necessarily_closed ()
 Sets the system topology to NOT_NECESSARILY_CLOSED.
void set_rows_topology ()
 Sets the topology of all rows equal to the system topology.
void unset_pending_rows ()
 Sets the index to indicate that the system has no pending rows.
void set_index_first_pending_row (dimension_type i)
 Sets the index of the first pending row to i.
void set_sorted (bool b)
 Sets the sortedness flag of the system to b.
void resize_no_copy (dimension_type new_n_rows, dimension_type new_n_columns)
 Resizes the system without worrying about the old contents.
void add_rows_and_columns (dimension_type n)
 Adds n rows and columns to the system.
void insert (const Linear_Row &r)
 Adds a copy of r to the system, automatically resizing the system or the row's copy, if needed.
void insert_pending (const Linear_Row &r)
 Adds a copy of the given row to the pending part of the system, automatically resizing the system or the row, if needed.
void add_row (const Linear_Row &r)
 Adds a copy of the given row to the system.
void add_pending_row (Linear_Row::Flags flags)
 Adds a new empty row to the system, setting only its flags.
void add_pending_row (const Linear_Row &r)
 Adds a copy of the given row to the pending part of the system.
void add_rows (const Linear_System &y)
 Adds to *this a copy of the rows of `y'.
void add_pending_rows (const Linear_System &y)
 Adds a copy of the rows of `y' to the pending part of `*this'.
void sort_rows ()
 Sorts the non-pending rows (in growing order) and eliminates duplicated ones.
void sort_rows (dimension_type first_row, dimension_type last_row)
 Sorts the rows (in growing order) form first_row to last_row and eliminates duplicated ones.
void merge_rows_assign (const Linear_System &y)
 Assigns to *this the result of merging its rows with those of y, obtaining a sorted system.
void sort_pending_and_remove_duplicates ()
 Sorts the pending rows and eliminates those that also occur in the non-pending part of the system.
void sort_and_remove_with_sat (Saturation_Matrix &sat)
 Sorts the system, removing duplicates, keeping the saturation matrix consistent.
dimension_type gauss (dimension_type n_lines_or_equalities)
 Minimizes the subsystem of equations contained in *this.
void back_substitute (dimension_type n_lines_or_equalities)
 Back-substitutes the coefficients to reduce the complexity of the system.
void simplify ()
 Applies Gaussian's elimination and back-substitution so as to simplify the linear system.
void normalize ()
 Normalizes the system by dividing each row for the GCD of the row's elements.
void clear ()
 Clears the system deallocating all its rows.
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) 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.
bool OK (bool check_strong_normalized=true) const
 Checks if all the invariants are satisfied.
Subscript operators
Linear_Rowoperator[] (dimension_type k)
 Returns a reference to the k-th row of the system.
const Linear_Rowoperator[] (dimension_type k) const
 Returns a constant reference to the k-th row of the system.
Accessors
Topology topology () const
 Returns the system topology.
bool is_sorted () const
 Returns the value of the sortedness flag.
bool is_necessarily_closed () const
 Returns true if and only if the system topology is NECESSARILY_CLOSED.
dimension_type num_lines_or_equalities () const
 Returns the number of rows in the system that represent either lines or equalities.
dimension_type first_pending_row () const
 Returns the index of the first pending row.
dimension_type num_pending_rows () const
 Returns the number of rows that are in the pending part of the system.

Static Public Member Functions

static dimension_type max_space_dimension ()
 Returns the maximum space dimension a Linear_System can handle.

Private Attributes

Topology row_topology
 The topological kind of the rows in the system.
dimension_type index_first_pending
 The index of the first pending row.
bool sorted
 true if rows are sorted in the ascending order as defined by bool compare(const Linear_Row&, const Linear_Row&). If false may not be sorted.

Related Functions

(Note that these are not member functions.)

void swap (Parma_Polyhedra_Library::Linear_System &x, Parma_Polyhedra_Library::Linear_System &y)
 Specializes std::swap.
bool operator== (const Linear_System &x, const Linear_System &y)
 Returns true if and only if x and y are identical.
bool operator!= (const Linear_System &x, const Linear_System &y)
 Returns true if and only if x and y are different.

Classes

struct  Row_Less_Than
 Ordering predicate (used when implementing the sort algorithm). More...
struct  With_Pending
 A tag class. More...
class  With_Saturation_Matrix_iterator
 An iterator keeping a Linear_System consistent with a Saturation_Matrix. More...


Detailed Description

The base class for systems of constraints and generators.

An object of this class represents either a constraint system or a generator system. Each Linear_System object can be viewed as a finite sequence of strong-normalized Linear_Row objects, where each Linear_Row implements a constraint or a generator. Linear systems are characterized by the matrix of coefficients, also encoding the number, size and capacity of Linear_row objects, as well as a few additional information, including:

Definition at line 54 of file Linear_System.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Linear_System::Linear_System ( Topology  topol  )  [inline]

Builds an empty linear system with specified topology.

Rows size and capacity are initialized to $0$.

Definition at line 56 of file Linear_System.inlines.hh.

00057   : Matrix(),
00058     row_topology(topol),
00059     index_first_pending(0),
00060     sorted(true) {
00061 }

Parma_Polyhedra_Library::Linear_System::Linear_System ( Topology  topol,
dimension_type  n_rows,
dimension_type  n_columns 
) [inline]

Builds a system with specified topology and dimensions.

Parameters:
topol The topology of the system that will be created;
n_rows The number of rows of the system that will be created;
n_columns The number of columns of the system that will be created.
Creates a n_rows $\times$ n_columns system whose coefficients are all zero and whose rows are all initialized to be of the given topology.

Definition at line 64 of file Linear_System.inlines.hh.

00066   : Matrix(n_rows, n_columns, Linear_Row::Flags(topol)),
00067     row_topology(topol),
00068     index_first_pending(n_rows),
00069     sorted(true) {
00070 }

Parma_Polyhedra_Library::Linear_System::Linear_System ( const Linear_System y  )  [inline]

Copy-constructor: pending rows are transformed into non-pending ones.

Definition at line 94 of file Linear_System.inlines.hh.

References num_pending_rows(), sorted, and unset_pending_rows().

00095   : Matrix(y),
00096     row_topology(y.row_topology) {
00097   unset_pending_rows();
00098   // Previously pending rows may violate sortedness.
00099   sorted = (y.num_pending_rows() > 0) ? false : y.sorted;
00100   assert(num_pending_rows() == 0);
00101 }

Parma_Polyhedra_Library::Linear_System::Linear_System ( const Linear_System y,
With_Pending   
) [inline]

Full copy-constructor: pending rows are copied as pending.

Definition at line 104 of file Linear_System.inlines.hh.

00105   : Matrix(y),
00106     row_topology(y.row_topology),
00107     index_first_pending(y.index_first_pending),
00108     sorted(y.sorted) {
00109 }


Member Function Documentation

Linear_System & Parma_Polyhedra_Library::Linear_System::operator= ( const Linear_System y  )  [inline]

Assignment operator: pending rows are transformed into non-pending ones.

Definition at line 112 of file Linear_System.inlines.hh.

References num_pending_rows(), Parma_Polyhedra_Library::Matrix::operator=(), row_topology, sorted, and unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Generator_System::operator=(), and Parma_Polyhedra_Library::Constraint_System::operator=().

00112                                                {
00113   Matrix::operator=(y);
00114   row_topology = y.row_topology;
00115   unset_pending_rows();
00116   // Previously pending rows may violate sortedness.
00117   sorted = (y.num_pending_rows() > 0) ? false : y.sorted;
00118   assert(num_pending_rows() == 0);
00119   return *this;
00120 }

void Parma_Polyhedra_Library::Linear_System::assign_with_pending ( const Linear_System y  )  [inline]

Full assignment operator: pending rows are copied as pending.

Definition at line 123 of file Linear_System.inlines.hh.

References index_first_pending, Parma_Polyhedra_Library::Matrix::operator=(), row_topology, and sorted.

Referenced by Parma_Polyhedra_Library::Polyhedron::operator=(), and Parma_Polyhedra_Library::Polyhedron::Polyhedron().

00123                                                          {
00124   Matrix::operator=(y);
00125   row_topology = y.row_topology;
00126   index_first_pending = y.index_first_pending;
00127   sorted = y.sorted;
00128 }

void Parma_Polyhedra_Library::Linear_System::swap ( Linear_System y  )  [inline]

Swaps *this with y.

Definition at line 131 of file Linear_System.inlines.hh.

References index_first_pending, row_topology, sorted, and Parma_Polyhedra_Library::Matrix::swap().

Referenced by swap(), Parma_Polyhedra_Library::Generator_System::swap(), and Parma_Polyhedra_Library::Constraint_System::swap().

00131                                     {
00132   Matrix::swap(y);
00133   std::swap(row_topology, y.row_topology);
00134   std::swap(index_first_pending, y.index_first_pending);
00135   std::swap(sorted, y.sorted);
00136 }

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

Returns the maximum space dimension a Linear_System can handle.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

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

References Parma_Polyhedra_Library::Matrix::max_num_columns().

Referenced by Parma_Polyhedra_Library::Generator_System::max_space_dimension(), and Parma_Polyhedra_Library::Constraint_System::max_space_dimension().

00193                                    {
00194   // Column zero holds the inhomogeneous term or the divisor.
00195   // In NNC linear systems, the last column holds the coefficient
00196   // of the epsilon dimension.
00197   return max_num_columns() - 2;
00198 }

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

Returns the space dimension of the rows in the system.

The computation of the space dimension correctly ignores the column encoding the inhomogeneous terms of constraint (resp., the divisors of generators); if the system topology is NOT_NECESSARILY_CLOSED, also the column of the $\epsilon$-dimension coefficients will be ignored.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 201 of file Linear_System.inlines.hh.

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

Referenced by Parma_Polyhedra_Library::Generator_System::space_dimension(), and Parma_Polyhedra_Library::Constraint_System::space_dimension().

00201                                      {
00202   const dimension_type n_columns = num_columns();
00203   return (n_columns == 0)
00204     ? 0
00205     : n_columns - (is_necessarily_closed() ? 1 : 2);
00206 }

void Parma_Polyhedra_Library::Linear_System::remove_trailing_columns ( dimension_type  n  )  [inline]

void Parma_Polyhedra_Library::Linear_System::permute_columns ( const std::vector< dimension_type > &  cycles  )  [inline]

Permutes the columns of the system.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 217 of file Linear_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::permute_columns(), and sign_normalize().

Referenced by Parma_Polyhedra_Library::Polyhedron::bounded_affine_preimage(), Parma_Polyhedra_Library::Polyhedron::map_space_dimensions(), and Parma_Polyhedra_Library::Grid_Generator_System::permute_columns().

00217                                                                       {
00218   Matrix::permute_columns(cycles);
00219   // The rows with permuted columns are still normalized but may
00220   // be not strongly normalized: sign normalization is necessary.
00221   sign_normalize();
00222 }

Linear_Row & Parma_Polyhedra_Library::Linear_System::operator[] ( dimension_type  k  )  [inline]

const Linear_Row & Parma_Polyhedra_Library::Linear_System::operator[] ( dimension_type  k  )  const [inline]

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 183 of file Linear_System.inlines.hh.

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

00183                                                       {
00184   return static_cast<const Linear_Row&>(Matrix::operator[](k));
00185 }

void Parma_Polyhedra_Library::Linear_System::strong_normalize (  ) 

Strongly normalizes the system.

Definition at line 463 of file Linear_System.cc.

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

Referenced by Parma_Polyhedra_Library::Generator_System::affine_image(), Parma_Polyhedra_Library::Constraint_System::affine_preimage(), Parma_Polyhedra_Library::Polyhedron::OK(), OK(), and remove_trailing_columns().

00463                                    {
00464   Linear_System& x = *this;
00465   // We strongly normalize also the pending rows.
00466   for (dimension_type i = num_rows(); i-- > 0; )
00467     x[i].strong_normalize();
00468   set_sorted(false);
00469 }

void Parma_Polyhedra_Library::Linear_System::sign_normalize (  ) 

Sign-normalizes the system.

Definition at line 472 of file Linear_System.cc.

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

Referenced by permute_columns(), and Parma_Polyhedra_Library::Polyhedron::simplify().

00472                                  {
00473   Linear_System& x = *this;
00474   // We sign-normalize also the pending rows.
00475   for (dimension_type i = num_rows(); i-- > 0; )
00476     x[i].sign_normalize();
00477   set_sorted(false);
00478 }

Topology Parma_Polyhedra_Library::Linear_System::topology (  )  const [inline]

bool Parma_Polyhedra_Library::Linear_System::is_sorted (  )  const [inline]

Returns the value of the sortedness flag.

Definition at line 41 of file Linear_System.inlines.hh.

References check_sorted(), and sorted.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_row(), add_rows(), add_rows_and_columns(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Generator_System::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), back_substitute(), Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::minimize(), Parma_Polyhedra_Library::Constraint_System::num_inequalities(), Parma_Polyhedra_Library::Generator_System::num_lines(), Parma_Polyhedra_Library::Generator_System::num_rays(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Grid_Generator_System::OK(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), sort_pending_and_remove_duplicates(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

00041                                {
00042   // The flag `sorted' does not really reflect the sortedness status
00043   // of a system (if `sorted' evaluates to `false' nothing is known).
00044   // This assertion is used to ensure that the system
00045   // is actually sorted when `sorted' value is 'true'.
00046   assert(!sorted || check_sorted());
00047   return sorted;
00048 }

bool Parma_Polyhedra_Library::Linear_System::is_necessarily_closed (  )  const [inline]

Returns true if and only if the system topology is NECESSARILY_CLOSED.

Definition at line 173 of file Linear_System.inlines.hh.

References Parma_Polyhedra_Library::NECESSARILY_CLOSED, and row_topology.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points(), Parma_Polyhedra_Library::Generator_System::add_corresponding_points(), Parma_Polyhedra_Library::Constraint_System::add_low_level_constraints(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), ascii_dump(), Parma_Polyhedra_Library::Generator_System::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::ascii_dump(), Parma_Polyhedra_Library::Generator_System::begin(), Parma_Polyhedra_Library::Generator_System::has_closure_points(), Parma_Polyhedra_Library::Generator_System::has_points(), Parma_Polyhedra_Library::Constraint_System::has_strict_inequalities(), insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), insert_pending(), Parma_Polyhedra_Library::Generator_System::insert_pending(), Parma_Polyhedra_Library::Constraint_System::insert_pending(), Parma_Polyhedra_Library::Polyhedron::is_necessarily_closed(), Parma_Polyhedra_Library::Polyhedron::minimize(), OK(), Parma_Polyhedra_Library::Generator_System::const_iterator::operator++(), Parma_Polyhedra_Library::Constraint_System::satisfies_all_constraints(), set_rows_topology(), and space_dimension().

00173                                            {
00174   return row_topology == NECESSARILY_CLOSED;
00175 }

PPL::dimension_type Parma_Polyhedra_Library::Linear_System::num_lines_or_equalities (  )  const

Returns the number of rows in the system that represent either lines or equalities.

Definition at line 40 of file Linear_System.cc.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), back_substitute(), and gauss().

00040                                                 {
00041   assert(num_pending_rows() == 0);
00042   const Linear_System& x = *this;
00043   dimension_type n = 0;
00044   for (dimension_type i = num_rows(); i-- > 0; )
00045     if (x[i].is_line_or_equality())
00046       ++n;
00047   return n;
00048 }

dimension_type Parma_Polyhedra_Library::Linear_System::first_pending_row (  )  const [inline]

dimension_type Parma_Polyhedra_Library::Linear_System::num_pending_rows (  )  const [inline]

Returns the number of rows that are in the pending part of the system.

Definition at line 78 of file Linear_System.inlines.hh.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), add_pending_row(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_row(), add_rows(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), back_substitute(), gauss(), insert(), Parma_Polyhedra_Library::Grid_Generator_System::insert(), Parma_Polyhedra_Library::Generator_System::insert(), Parma_Polyhedra_Library::Constraint_System::insert(), insert_pending(), Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Linear_System(), merge_rows_assign(), Parma_Polyhedra_Library::Constraint_System::num_equalities(), Parma_Polyhedra_Library::Constraint_System::num_inequalities(), Parma_Polyhedra_Library::Generator_System::num_lines(), num_lines_or_equalities(), Parma_Polyhedra_Library::Generator_System::num_rays(), Parma_Polyhedra_Library::Polyhedron::OK(), operator=(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box(), simplify(), sort_and_remove_with_sat(), sort_pending_and_remove_duplicates(), and sort_rows().

00078                                       {
00079   assert(num_rows() >= first_pending_row());
00080   return num_rows() - first_pending_row();
00081 }

bool Parma_Polyhedra_Library::Linear_System::check_sorted (  )  const

Returns true if and only if *this is sorted, without checking for duplicates.

Definition at line 821 of file Linear_System.cc.

References first_pending_row().

Referenced by is_sorted(), merge_rows_assign(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), OK(), and sort_and_remove_with_sat().

00821                                      {
00822   const Linear_System& x = *this;
00823   for (dimension_type i = first_pending_row(); i-- > 1; )
00824     if (compare(x[i], x[i-1]) < 0)
00825       return false;
00826   return true;
00827 }

void Parma_Polyhedra_Library::Linear_System::set_necessarily_closed (  )  [inline]

void Parma_Polyhedra_Library::Linear_System::set_not_necessarily_closed (  )  [inline]

void Parma_Polyhedra_Library::Linear_System::set_rows_topology (  ) 

Sets the topology of all rows equal to the system topology.

Definition at line 102 of file Linear_System.cc.

References is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_rows(), set_necessarily_closed(), and set_not_necessarily_closed().

Referenced by set_necessarily_closed(), and set_not_necessarily_closed().

00102                                     {
00103   Linear_System& x = *this;
00104   if (is_necessarily_closed())
00105     for (dimension_type i = num_rows(); i-- > 0; )
00106       x[i].set_necessarily_closed();
00107   else
00108     for (dimension_type i = num_rows(); i-- > 0; )
00109       x[i].set_not_necessarily_closed();
00110 }

void Parma_Polyhedra_Library::Linear_System::unset_pending_rows (  )  [inline]

Sets the index to indicate that the system has no pending rows.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 84 of file Linear_System.inlines.hh.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators_and_minimize(), add_rows(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), Linear_System(), merge_rows_assign(), Parma_Polyhedra_Library::Polyhedron::OK(), operator=(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_constraints(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), Parma_Polyhedra_Library::Polyhedron::shrink_bounding_box(), Parma_Polyhedra_Library::Polyhedron::simplify(), simplify(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), Parma_Polyhedra_Library::Polyhedron::time_elapse_assign(), Parma_Polyhedra_Library::Polyhedron::topological_closure_assign(), and Parma_Polyhedra_Library::Grid_Generator_System::unset_pending_rows().

00084                                   {
00085   index_first_pending = num_rows();
00086 }

void Parma_Polyhedra_Library::Linear_System::set_index_first_pending_row ( dimension_type  i  )  [inline]

void Parma_Polyhedra_Library::Linear_System::set_sorted ( bool  b  )  [inline]

Sets the sortedness flag of the system to b.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 51 of file Linear_System.inlines.hh.

References sorted.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_recycled_constraints(), Parma_Polyhedra_Library::Polyhedron::add_recycled_generators(), add_row(), add_rows(), add_rows_and_columns(), Parma_Polyhedra_Library::Constraint_System::adjust_topology_and_space_dimension(), ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), back_substitute(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), gauss(), Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), Parma_Polyhedra_Library::Polyhedron::minimize(), normalize(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g(), Parma_Polyhedra_Library::Polyhedron::Polyhedron(), Parma_Polyhedra_Library::Generator_System::remove_invalid_lines_and_rays(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_constraints(), Parma_Polyhedra_Library::Polyhedron::remove_pending_to_obtain_generators(), resize_no_copy(), Parma_Polyhedra_Library::Grid_Generator_System::set_sorted(), sign_normalize(), Parma_Polyhedra_Library::Polyhedron::simplify(), simplify(), sort_and_remove_with_sat(), strong_normalize(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators(), and Parma_Polyhedra_Library::Polyhedron::topological_closure_assign().

00051                                       {
00052   sorted = b;
00053 }

void Parma_Polyhedra_Library::Linear_System::resize_no_copy ( dimension_type  new_n_rows,
dimension_type  new_n_columns 
) [inline]

Resizes the system without worrying about the old contents.

Parameters:
new_n_rows The number of rows of the resized system;
new_n_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.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 147 of file Linear_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::resize_no_copy(), row_topology, and set_sorted().

Referenced by ascii_load(), Parma_Polyhedra_Library::Generator_System::ascii_load(), Parma_Polyhedra_Library::Constraint_System::ascii_load(), Parma_Polyhedra_Library::Polyhedron::minimize(), and Parma_Polyhedra_Library::Grid_Generator_System::resize_no_copy().

00148                                                                   {
00149   Matrix::resize_no_copy(new_n_rows, new_n_columns,
00150                          Linear_Row::Flags(row_topology));
00151   // Even though `*this' may happen to keep its sortedness, we believe
00152   // that checking such a property is not worth the effort.  In fact,
00153   // it is very likely that the system will be overwritten as soon as
00154   // we return.
00155   set_sorted(false);
00156 }

void Parma_Polyhedra_Library::Linear_System::add_rows_and_columns ( dimension_type  n  ) 

Adds n rows and columns to the system.

Parameters:
n The number of rows and columns to be added: must be strictly positive.
Turns the system $M \in \Rset^r \times \Rset^c$ into the system $N \in \Rset^{r+n} \times \Rset^{c+n}$ such that $N = \bigl(\genfrac{}{}{0pt}{}{0}{M}\genfrac{}{}{0pt}{}{J}{o}\bigr)$, where $J$ is the specular image of the $n \times n$ identity matrix.

Definition at line 730 of file Linear_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows_and_columns(), is_sorted(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), row_topology, Parma_Polyhedra_Library::Linear_Row::set_is_line_or_equality(), and set_sorted().

Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_embed(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions_and_project(), and Parma_Polyhedra_Library::Polyhedron::concatenate_assign().

00730                                                              {
00731   assert(n > 0);
00732   const bool was_sorted = is_sorted();
00733   const dimension_type old_n_rows = num_rows();
00734   const dimension_type old_n_columns = num_columns();
00735   add_zero_rows_and_columns(n, n, Linear_Row::Flags(row_topology));
00736   Linear_System& x = *this;
00737   // The old system is moved to the bottom.
00738   for (dimension_type i = old_n_rows; i-- > 0; )
00739     std::swap(x[i], x[i + n]);
00740   for (dimension_type i = n, c = old_n_columns; i-- > 0; ) {
00741     // The top right-hand sub-system (i.e., the system made of new
00742     // rows and columns) is set to the specular image of the identity
00743     // matrix.
00744     Linear_Row& r = x[i];
00745     r[c++] = 1;
00746     r.set_is_line_or_equality();
00747     // Note: `r' is strongly normalized.
00748   }
00749   // If the old system was empty, the last row added is either
00750   // a positivity constraint or a point.
00751   if (old_n_columns == 0) {
00752     x[n-1].set_is_ray_or_point_or_inequality();
00753     // Since ray, points and inequalities come after lines
00754     // and equalities, this case implies the system is sorted.
00755     set_sorted(true);
00756   }
00757   else if (was_sorted)
00758     set_sorted(compare(x[n-1], x[n]) <= 0);
00759 
00760   // A well-formed system has to be returned.
00761   assert(OK(true));
00762 }

void Parma_Polyhedra_Library::Linear_System::insert ( const Linear_Row r  ) 

Adds a copy of r to the system, automatically resizing the system or the row's copy, if needed.

Definition at line 182 of file Linear_System.cc.

References add_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_Row::topology(), and topology().

Referenced by Parma_Polyhedra_Library::Constraint_System::Constraint_System(), Parma_Polyhedra_Library::Generator_System::Generator_System(), Parma_Polyhedra_Library::Generator_System::insert(), and Parma_Polyhedra_Library::Constraint_System::insert().

00182                                             {
00183   // The added row must be strongly normalized and have the same
00184   // topology of the system.
00185   assert(r.check_strong_normalized());
00186   assert(topology() == r.topology());
00187   // This method is only used when the system has no pending rows.
00188   assert(num_pending_rows() == 0);
00189 
00190   const dimension_type old_num_rows = num_rows();
00191   const dimension_type old_num_columns = num_columns();
00192   const dimension_type r_size = r.size();
00193 
00194   // Resize the system, if necessary.
00195   if (r_size > old_num_columns) {
00196     add_zero_columns(r_size - old_num_columns);
00197     if (!is_necessarily_closed() && old_num_rows != 0)
00198       // Move the epsilon coefficients to the last column
00199       // (note: sorting is preserved).
00200       swap_columns(old_num_columns - 1, r_size - 1);
00201     add_row(r);
00202   }
00203   else if (r_size < old_num_columns)
00204     if (is_necessarily_closed() || old_num_rows == 0)
00205       add_row(Linear_Row(r, old_num_columns, row_capacity));
00206     else {
00207       // Create a resized copy of the row (and move the epsilon
00208       // coefficient to its last position).
00209       Linear_Row tmp_row(r, old_num_columns, row_capacity);
00210       std::swap(tmp_row[r_size - 1], tmp_row[old_num_columns - 1]);
00211       add_row(tmp_row);
00212     }
00213   else
00214     // Here r_size == old_num_columns.
00215     add_row(r);
00216 
00217   // The added row was not a pending row.
00218   assert(num_pending_rows() == 0);
00219   // Do not check for strong normalization,
00220   // because no modification of rows has occurred.
00221   assert(OK(false));
00222 }

void Parma_Polyhedra_Library::Linear_System::insert_pending ( const Linear_Row r  ) 

Adds a copy of the given row to the pending part of the system, automatically resizing the system or the row, if needed.

Definition at line 225 of file Linear_System.cc.

References add_pending_row(), Parma_Polyhedra_Library::Matrix::add_zero_columns(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Row::size(), Parma_Polyhedra_Library::Matrix::swap_columns(), Parma_Polyhedra_Library::Linear_Row::topology(), and topology().

Referenced by Parma_Polyhedra_Library::Generator_System::insert_pending(), and Parma_Polyhedra_Library::Constraint_System::insert_pending().

00225                                                     {
00226   // The added row must be strongly normalized and have the same
00227   // topology of the system.
00228   assert(r.check_strong_normalized());
00229   assert(topology() == r.topology());
00230 
00231   const dimension_type old_num_rows = num_rows();
00232   const dimension_type old_num_columns = num_columns();
00233   const dimension_type r_size = r.size();
00234 
00235   // Resize the system, if necessary.
00236   if (r_size > old_num_columns) {
00237     add_zero_columns(r_size - old_num_columns);
00238     if (!is_necessarily_closed() && old_num_rows != 0)
00239       // Move the epsilon coefficients to the last column
00240       // (note: sorting is preserved).
00241       swap_columns(old_num_columns - 1, r_size - 1);
00242     add_pending_row(r);
00243   }
00244   else if (r_size < old_num_columns)
00245     if (is_necessarily_closed() || old_num_rows == 0)
00246       add_pending_row(Linear_Row(r, old_num_columns, row_capacity));
00247     else {
00248       // Create a resized copy of the row (and move the epsilon
00249       // coefficient to its last position).
00250       Linear_Row tmp_row(r, old_num_columns, row_capacity);
00251       std::swap(tmp_row[r_size - 1], tmp_row[old_num_columns - 1]);
00252       add_pending_row(tmp_row);
00253     }
00254   else
00255     // Here r_size == old_num_columns.
00256     add_pending_row(r);
00257 
00258   // The added row was a pending row.
00259   assert(num_pending_rows() > 0);
00260   // Do not check for strong normalization,
00261   // because no modification of rows has occurred.
00262   assert(OK(false));
00263 }

void Parma_Polyhedra_Library::Linear_System::add_row ( const Linear_Row r  ) 

Adds a copy of the given row to the system.

Definition at line 348 of file Linear_System.cc.

References Parma_Polyhedra_Library::Matrix::add_row(), Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_size, set_index_first_pending_row(), set_sorted(), and Parma_Polyhedra_Library::Row::size().

Referenced by Parma_Polyhedra_Library::Polyhedron::generalized_affine_image(), and insert().

00348                                              {
00349   // The added row must be strongly normalized and have the same
00350   // number of elements as the existing rows of the system.
00351   assert(r.check_strong_normalized());
00352   assert(r.size() == row_size);
00353   // This method is only used when the system has no pending rows.
00354   assert(num_pending_rows() == 0);
00355 
00356   const bool was_sorted = is_sorted();
00357 
00358   Matrix::add_row(r);
00359 
00360   //  We update `index_first_pending', because it must be equal to
00361   // `num_rows()'.
00362   set_index_first_pending_row(num_rows());
00363 
00364   if (was_sorted) {
00365     const dimension_type nrows = num_rows();
00366     // The added row may have caused the system to be not sorted anymore.
00367     if (nrows > 1) {
00368       // If the system is not empty and the inserted row is the
00369       // greatest one, the system is set to be sorted.
00370       // If it is not the greatest one then the system is no longer sorted.
00371       Linear_System& x = *this;
00372       set_sorted(compare(x[nrows-2], x[nrows-1]) <= 0);
00373     }
00374     else
00375       // A system having only one row is sorted.
00376       set_sorted(true);
00377   }
00378   // The added row was not a pending row.
00379   assert(num_pending_rows() == 0);
00380   // Do not check for strong normalization, because no modification of
00381   // rows has occurred.
00382   assert(OK(false));
00383 }

void Parma_Polyhedra_Library::Linear_System::add_pending_row ( Linear_Row::Flags  flags  ) 

Adds a new empty row to the system, setting only its flags.

Definition at line 424 of file Linear_System.cc.

References Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, and Parma_Polyhedra_Library::Matrix::rows.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Generator_System::add_corresponding_closure_points(), Parma_Polyhedra_Library::Generator_System::add_corresponding_points(), Parma_Polyhedra_Library::Polyhedron::conversion(), and insert_pending().

00424                                                              {
00425   const dimension_type new_rows_size = rows.size() + 1;
00426   if (rows.capacity() < new_rows_size) {
00427     // Reallocation will take place.
00428     std::vector<Row> new_rows;
00429     new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
00430     new_rows.insert(new_rows.end(), new_rows_size, Row());
00431     // Put the new row in place.
00432     Linear_Row new_row(row_size, row_capacity, flags);
00433     dimension_type i = new_rows_size-1;
00434     std::swap(new_rows[i], new_row);
00435     // Steal the old rows.
00436     while (i-- > 0)
00437       new_rows[i].swap(rows[i]);
00438     // Put the new vector into place.
00439     std::swap(rows, new_rows);
00440   }
00441   else {
00442     // Reallocation will NOT take place.
00443     // Insert a new empty row at the end, then construct it assigning
00444     // it the given type.
00445     Row& new_row = *rows.insert(rows.end(), Row());
00446     static_cast<Linear_Row&>(new_row).construct(row_size, row_capacity, flags);
00447   }
00448 
00449   // The added row was a pending row.
00450   assert(num_pending_rows() > 0);
00451 }

void Parma_Polyhedra_Library::Linear_System::add_pending_row ( const Linear_Row r  ) 

Adds a copy of the given row to the pending part of the system.

Definition at line 386 of file Linear_System.cc.

References Parma_Polyhedra_Library::Linear_Row::check_strong_normalized(), Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::Matrix::rows, and Parma_Polyhedra_Library::Row::size().

00386                                                      {
00387   // The added row must be strongly normalized and have the same
00388   // number of elements of the existing rows of the system.
00389   assert(r.check_strong_normalized());
00390   assert(r.size() == row_size);
00391 
00392   const dimension_type new_rows_size = rows.size() + 1;
00393   if (rows.capacity() < new_rows_size) {
00394     // Reallocation will take place.
00395     std::vector<Row> new_rows;
00396     new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
00397     new_rows.insert(new_rows.end(), new_rows_size, Row());
00398     // Put the new row in place.
00399     Row new_row(r, row_capacity);
00400     dimension_type i = new_rows_size-1;
00401     std::swap(new_rows[i], new_row);
00402     // Steal the old rows.
00403     while (i-- > 0)
00404       new_rows[i].swap(rows[i]);
00405     // Put the new rows into place.
00406     std::swap(rows, new_rows);
00407   }
00408   else {
00409     // Reallocation will NOT take place.
00410     // Inserts a new empty row at the end, then substitutes it with a
00411     // copy of the given row.
00412     Row tmp(r, row_capacity);
00413     std::swap(*rows.insert(rows.end(), Row()), tmp);
00414   }
00415 
00416   // The added row was a pending row.
00417   assert(num_pending_rows() > 0);
00418   // Do not check for strong normalization, because no modification of
00419   // rows has occurred.
00420   assert(OK(false));
00421 }

void Parma_Polyhedra_Library::Linear_System::add_rows ( const Linear_System y  ) 

Adds to *this a copy of the rows of `y'.

It is assumed that *this has no pending rows.

Definition at line 288 of file Linear_System.cc.

References add_pending_rows(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), set_sorted(), and unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign(), and Parma_Polyhedra_Library::Polyhedron::poly_hull_assign().

00288                                                  {
00289   assert(num_pending_rows() == 0);
00290 
00291   // Adding no rows is a no-op.
00292   if (y.num_rows() == 0)
00293     return;
00294 
00295   // Check if sortedness is preserved.
00296   if (is_sorted())
00297     if (!y.is_sorted() || y.num_pending_rows() > 0)
00298       set_sorted(false);
00299     else {
00300       // `y' is sorted and has no pending rows.
00301       const dimension_type n_rows = num_rows();
00302       if (n_rows > 0)
00303         set_sorted(compare((*this)[n_rows-1], y[0]) <= 0);
00304     }
00305 
00306   // Add the rows of `y' as if they were pending.
00307   add_pending_rows(y);
00308   // There are no pending_rows.
00309   unset_pending_rows();
00310 
00311   // Do not check for strong normalization,
00312   // because no modification of rows has occurred.
00313   assert(OK(false));
00314 }

void Parma_Polyhedra_Library::Linear_System::add_pending_rows ( const Linear_System y  ) 

Adds a copy of the rows of `y' to the pending part of `*this'.

Definition at line 266 of file Linear_System.cc.

References Parma_Polyhedra_Library::Matrix::add_zero_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, row_topology, and sorted.

Referenced by add_rows(), Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

00266                                                          {
00267   Linear_System& x = *this;
00268   assert(x.row_size == y.row_size);
00269 
00270   const dimension_type x_n_rows = x.num_rows();
00271   const dimension_type y_n_rows = y.num_rows();
00272   // Grow to the required size without changing sortedness.
00273   const bool was_sorted = sorted;
00274   add_zero_rows(y_n_rows, Linear_Row::Flags(row_topology));
00275   sorted = was_sorted;
00276 
00277   // Copy the rows of `y', forcing size and capacity.
00278   for (dimension_type i = y_n_rows; i-- > 0; ) {
00279     Row copy(y[i], x.row_size, x.row_capacity);
00280     std::swap(copy, x[x_n_rows+i]);
00281   }
00282   // Do not check for strong normalization,
00283   // because no modification of rows has occurred.
00284   assert(OK(false));
00285 }

void Parma_Polyhedra_Library::Linear_System::sort_rows (  ) 

void Parma_Polyhedra_Library::Linear_System::sort_rows ( dimension_type  first_row,
dimension_type  last_row 
)

Sorts the rows (in growing order) form first_row to last_row and eliminates duplicated ones.

Definition at line 329 of file Linear_System.cc.

References first_pending_row(), Parma_Polyhedra_Library::Matrix::num_rows(), and Parma_Polyhedra_Library::Matrix::rows.

00330                                                              {
00331   assert(first_row <= last_row && last_row <= num_rows());
00332   // We cannot mix pending and non-pending rows.
00333   assert(first_row >= first_pending_row() || last_row <= first_pending_row());
00334 
00335   // First sort without removing duplicates.
00336   std::vector<Row>::iterator first = rows.begin() + first_row;
00337   std::vector<Row>::iterator last = rows.begin() + last_row;
00338   swapping_sort(first, last, Row_Less_Than());
00339   // Second, move duplicates to the end.
00340   std::vector<Row>::iterator new_last = swapping_unique(first, last);
00341   // Finally, remove duplicates.
00342   rows.erase(new_last, last);
00343   // NOTE: we cannot check for well-formedness of the system here,
00344   // because the caller still has to update `index_first_pending'.
00345 }

void Parma_Polyhedra_Library::Linear_System::merge_rows_assign ( const Linear_System y  ) 

Assigns to *this the result of merging its rows with those of y, obtaining a sorted system.

Duplicated rows will occur only once in the result. On entry, both systems are assumed to be sorted and have no pending rows.

Definition at line 51 of file Linear_System.cc.

References check_sorted(), Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Matrix::max_num_rows(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, Parma_Polyhedra_Library::Matrix::rows, and unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign(), and Parma_Polyhedra_Library::Polyhedron::time_elapse_assign().

00051                                                           {
00052   assert(row_size >= y.row_size);
00053   // Both systems have to be sorted and have no pending rows.
00054   assert(check_sorted() && y.check_sorted());
00055   assert(num_pending_rows() == 0 && y.num_pending_rows() == 0);
00056 
00057   Linear_System& x = *this;
00058 
00059   // A temporary vector of rows...
00060   std::vector<Row> tmp;
00061   // ... with enough capacity not to require any reallocations.
00062   tmp.reserve(compute_capacity(x.num_rows() + y.num_rows(), max_num_rows()));
00063 
00064   dimension_type xi = 0;
00065   dimension_type x_num_rows = x.num_rows();
00066   dimension_type yi = 0;
00067   dimension_type y_num_rows = y.num_rows();
00068 
00069   while (xi < x_num_rows && yi < y_num_rows) {
00070     const int comp = compare(x[xi], y[yi]);
00071     if (comp <= 0) {
00072       // Elements that can be taken from `x' are actually _stolen_ from `x'
00073       std::swap(x[xi++], *tmp.insert(tmp.end(), Linear_Row()));
00074       if (comp == 0)
00075         // A duplicate element.
00076         ++yi;
00077     }
00078     else {
00079       // (comp > 0)
00080       Linear_Row copy(y[yi++], row_size, row_capacity);
00081       std::swap(copy, *tmp.insert(tmp.end(), Linear_Row()));
00082     }
00083   }
00084   // Insert what is left.
00085   if (xi < x_num_rows)
00086     while (xi < x_num_rows)
00087       std::swap(x[xi++], *tmp.insert(tmp.end(), Linear_Row()));
00088   else
00089     while (yi < y_num_rows) {
00090       Linear_Row copy(y[yi++], row_size, row_capacity);
00091       std::swap(copy, *tmp.insert(tmp.end(), Linear_Row()));
00092     }
00093 
00094   // We get the result vector and let the old one be destroyed.
00095   std::swap(tmp, rows);
00096   // There are no pending rows.
00097   unset_pending_rows();
00098   assert(check_sorted());
00099 }

void Parma_Polyhedra_Library::Linear_System::sort_pending_and_remove_duplicates (  ) 

Sorts the pending rows and eliminates those that also occur in the non-pending part of the system.

Definition at line 765 of file Linear_System.cc.

References Parma_Polyhedra_Library::cmp(), Parma_Polyhedra_Library::Matrix::erase_to_end(), first_pending_row(), is_sorted(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), and sort_rows().

Referenced by Parma_Polyhedra_Library::Polyhedron::intersection_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::poly_hull_assign_and_minimize(), Parma_Polyhedra_Library::Polyhedron::process_pending_constraints(), and Parma_Polyhedra_Library::Polyhedron::process_pending_generators().

00765                                                      {
00766   assert(num_pending_rows() > 0);
00767   assert(is_sorted());
00768   Linear_System& x = *this;
00769 
00770   // The non-pending part of the system is already sorted.
00771   // Now sorting the pending part..
00772   const dimension_type first_pending = x.first_pending_row();
00773   x.sort_rows(first_pending, x.num_rows());
00774   // Recompute the number of rows, because we may have removed
00775   // some rows occurring more than once in the pending part.
00776   dimension_type num_rows = x.num_rows();
00777 
00778   dimension_type k1 = 0;
00779   dimension_type k2 = first_pending;
00780   dimension_type num_duplicates = 0;
00781   // In order to erase them, put at the end of the system
00782   // those pending rows that also occur in the non-pending part.
00783   while (k1 < first_pending && k2 < num_rows) {
00784     const int cmp = compare(x[k1], x[k2]);
00785     if (cmp == 0) {
00786       // We found the same row.
00787       ++num_duplicates;
00788       --num_rows;
00789       // By initial sortedness, we can increment index `k1'.
00790       ++k1;
00791       // Do not increment `k2'; instead, swap there the next pending row.
00792       if (k2 < num_rows)
00793         std::swap(x[k2], x[k2 + num_duplicates]);
00794     }
00795     else if (cmp < 0)
00796       // By initial sortedness, we can increment `k1'.
00797       ++k1;
00798     else {
00799       // Here `cmp > 0'.
00800       // Increment `k2' and, if we already found any duplicate,
00801       // swap the next pending row in position `k2'.
00802       ++k2;
00803       if (num_duplicates > 0 && k2 < num_rows)
00804         std::swap(x[k2], x[k2 + num_duplicates]);
00805     }
00806   }
00807   // If needed, swap any duplicates found past the pending rows
00808   // that has not been considered yet; then erase the duplicates.
00809   if (num_duplicates > 0) {
00810     if (k2 < num_rows)
00811       for (++k2; k2 < num_rows; ++k2)
00812         std::swap(x[k2], x[k2 + num_duplicates]);
00813     x.erase_to_end(num_rows);
00814   }
00815   // Do not check for strong normalization,
00816   // because no modification of rows has occurred.
00817   assert(OK(false));
00818 }

void Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat ( Saturation_Matrix sat  ) 

Sorts the system, removing duplicates, keeping the saturation matrix consistent.

Parameters:
sat Saturation matrix with rows corresponding to the rows of *this.

Definition at line 501 of file Linear_System.cc.

References check_sorted(), Parma_Polyhedra_Library::Matrix::erase_to_end(), first_pending_row(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Saturation_Matrix::num_rows(), Parma_Polyhedra_Library::Saturation_Matrix::rows, Parma_Polyhedra_Library::Matrix::rows, Parma_Polyhedra_Library::Saturation_Matrix::rows_erase_to_end(), set_index_first_pending_row(), and set_sorted().

Referenced by Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_constraints_with_sat_c(), Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators(), and Parma_Polyhedra_Library::Polyhedron::obtain_sorted_generators_with_sat_g().

00501                                                                  {
00502   Linear_System& sys = *this;
00503   // We can only sort the non-pending part of the system.
00504   assert(sys.first_pending_row() == sat.num_rows());
00505   if (sys.first_pending_row() <= 1) {
00506     sys.set_sorted(true);
00507     return;
00508   }
00509 
00510   // First, sort `sys' (keeping `sat' consistent) without removing duplicates.
00511   With_Saturation_Matrix_iterator first(sys.rows.begin(), sat.rows.begin());
00512   With_Saturation_Matrix_iterator last = first + sat.num_rows();
00513   swapping_sort(first, last, Row_Less_Than());
00514   // Second, move duplicates in `sys' to the end (keeping `sat' consistent).
00515   With_Saturation_Matrix_iterator new_last = swapping_unique(first, last);
00516 
00517   const dimension_type num_duplicates = last - new_last;
00518   const dimension_type new_first_pending_row
00519     = sys.first_pending_row() - num_duplicates;
00520 
00521   if (sys.num_pending_rows() > 0) {
00522     // In this case, we must put the duplicates after the pending rows.
00523     const dimension_type n_rows = sys.num_rows() - 1;
00524     for (dimension_type i = 0; i < num_duplicates; ++i)
00525       std::swap(sys[new_first_pending_row + i], sys[n_rows - i]);
00526   }
00527   // Erasing the duplicated rows...
00528   sys.erase_to_end(sys.num_rows() - num_duplicates);
00529   sys.set_index_first_pending_row(new_first_pending_row);
00530   // ... and the corresponding rows of the saturation matrix.
00531   sat.rows_erase_to_end(sat.num_rows() - num_duplicates);
00532   assert(sys.check_sorted());
00533   // Now the system is sorted.
00534   sys.set_sorted(true);
00535 }

PPL::dimension_type Parma_Polyhedra_Library::Linear_System::gauss ( dimension_type  n_lines_or_equalities  ) 

Minimizes the subsystem of equations contained in *this.

This method works only on the equalities of the system: the system is required to be partially sorted, so that all the equalities are grouped at its top; it is assumed that the number of equalities is exactly n_lines_or_equalities. The method finds a minimal system for the equalities and returns its rank, i.e., the number of linearly independent equalities. The result is an upper triangular subsystem of equalities: for each equality, the pivot is chosen starting from the right-most columns.

Definition at line 538 of file Linear_System.cc.

References Parma_Polyhedra_Library::Matrix::num_columns(), num_lines_or_equalities(), num_pending_rows(), OK(), and set_sorted().

Referenced by Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().

00538                                                                   {
00539   Linear_System& x = *this;
00540   // This method is only applied to a well-formed linear system
00541   // having no pending rows and exactly `n_lines_or_equalities'
00542   // lines or equalities, all of which occur before the rays or points
00543   // or inequalities.
00544   assert(x.OK(true));
00545   assert(x.num_pending_rows() == 0);
00546   assert(n_lines_or_equalities == x.num_lines_or_equalities());
00547 #ifndef NDEBUG
00548   for (dimension_type i = n_lines_or_equalities; i-- > 0; )
00549     assert(x[i].is_line_or_equality());
00550 #endif
00551 
00552   dimension_type rank = 0;
00553   // Will keep track of the variations on the system of equalities.
00554   bool changed = false;
00555   for (dimension_type j = x.num_columns(); j-- > 0; )
00556     for (dimension_type i = rank; i < n_lines_or_equalities; ++i) {
00557       // Search for the first row having a non-zero coefficient
00558       // (the pivot) in the j-th column.
00559       if (x[i][j] == 0)
00560         continue;
00561       // Pivot found: if needed, swap rows so that this one becomes
00562       // the rank-th row in the linear system.
00563       if (i > rank) {
00564         std::swap(x[i], x[rank]);
00565         // After swapping the system is no longer sorted.
00566         changed = true;
00567       }
00568       // Combine the row containing the pivot with all the lines or
00569       // equalities following it, so that all the elements on the j-th
00570       // column in these rows become 0.
00571       for (dimension_type k = i + 1; k < n_lines_or_equalities; ++k)
00572         if (x[k][j] != 0) {
00573           x[k].linear_combine(x[rank], j);
00574           changed = true;
00575         }
00576       // Already dealt with the rank-th row.
00577       ++rank;
00578       // Consider another column index `j'.
00579       break;
00580     }
00581   if (changed)
00582     x.set_sorted(false);
00583   // A well-formed system is returned.
00584   assert(x.OK(true));
00585   return rank;
00586 }

void Parma_Polyhedra_Library::Linear_System::back_substitute ( dimension_type  n_lines_or_equalities  ) 

Back-substitutes the coefficients to reduce the complexity of the system.

Takes an upper triangular system having n_lines_or_equalities rows. For each row, starting from the one having the minimum number of coefficients different from zero, computes the expression of an element as a function of the remaining ones and then substitutes this expression in all the other rows.

Definition at line 590 of file Linear_System.cc.

References is_sorted(), Parma_Polyhedra_Library::Linear_Row::linear_combine(), Parma_Polyhedra_Library::neg_assign(), Parma_Polyhedra_Library::Matrix::num_columns(), num_lines_or_equalities(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), and set_sorted().

Referenced by Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().

00590                                                             {
00591   Linear_System& x = *this;
00592   // This method is only applied to a well-formed system
00593   // having no pending rows and exactly `n_lines_or_equalities'
00594   // lines or equalities, all of which occur before the first ray
00595   // or point or inequality.
00596   assert(x.OK(true));
00597   assert(x.num_pending_rows() == 0);
00598   assert(n_lines_or_equalities <= x.num_lines_or_equalities());
00599 #ifndef NDEBUG
00600   for (dimension_type i = n_lines_or_equalities; i-- > 0; )
00601     assert(x[i].is_line_or_equality());
00602 #endif
00603 
00604   const dimension_type nrows = x.num_rows();
00605   const dimension_type ncols = x.num_columns();
00606   // Trying to keep sortedness.
00607   bool still_sorted = x.is_sorted();
00608   // This deque of booleans will be used to flag those rows that,
00609   // before exiting, need to be re-checked for sortedness.
00610   std::deque<bool> check_for_sortedness;
00611   if (still_sorted)
00612     check_for_sortedness.insert(check_for_sortedness.end(), nrows, false);
00613 
00614   for (dimension_type k = n_lines_or_equalities; k-- > 0; ) {
00615     // For each line or equality, starting from the last one,
00616     // looks for the last non-zero element.
00617     // `j' will be the index of such a element.
00618     Linear_Row& x_k = x[k];
00619     dimension_type j = ncols - 1;
00620     while (j != 0 && x_k[j] == 0)
00621       --j;
00622 
00623     // Go through the equalities above `x_k'.
00624     for (dimension_type i = k; i-- > 0; ) {
00625       Linear_Row& x_i = x[i];
00626       if (x_i[j] != 0) {
00627         // Combine linearly `x_i' with `x_k'
00628         // so that `x_i[j]' becomes zero.
00629         x_i.linear_combine(x_k, j);
00630         if (still_sorted) {
00631           // Trying to keep sortedness: remember which rows
00632           // have to be re-checked for sortedness at the end.
00633           if (i > 0)
00634             check_for_sortedness[i-1] = true;
00635           check_for_sortedness[i] = true;
00636         }
00637       }
00638     }
00639 
00640     // Due to strong normalization during previous iterations,
00641     // the pivot coefficient `x_k[j]' may now be negative.
00642     // Since an inequality (or ray or point) cannot be multiplied
00643     // by a negative factor, the coefficient of the pivot must be
00644     // forced to be positive.
00645     const bool have_to_negate = (x_k[j] < 0);
00646     if (have_to_negate)
00647       for (dimension_type h = ncols; h-- > 0; )
00648         PPL::neg_assign(x_k[h]);
00649     // Note: we do not mark index `k' in `check_for_sortedness',
00650     // because we will later negate back the row.
00651 
00652     // Go through all the other rows of the system.
00653     for (dimension_type i = n_lines_or_equalities; i < nrows; ++i) {
00654       Linear_Row& x_i = x[i];
00655       if (x_i[j] != 0) {
00656         // Combine linearly the `x_i' with `x_k'
00657         // so that `x_i[j]' becomes zero.
00658         x_i.linear_combine(x_k, j);
00659         if (still_sorted) {
00660           // Trying to keep sortedness: remember which rows
00661           // have to be re-checked for sortedness at the end.
00662           if (i > n_lines_or_equalities)
00663             check_for_sortedness[i-1] = true;
00664           check_for_sortedness[i] = true;
00665         }
00666       }
00667     }
00668     if (have_to_negate)
00669       // Negate `x_k' to restore strong-normalization.
00670       for (dimension_type h = ncols; h-- > 0; )
00671         PPL::neg_assign(x_k[h]);
00672   }
00673 
00674   // Trying to keep sortedness.
00675   for (dimension_type i = 0; still_sorted && i < nrows-1; ++i)
00676     if (check_for_sortedness[i])
00677       // Have to check sortedness of `x[i]' with respect to `x[i+1]'.
00678       still_sorted = (compare(x[i], x[i+1]) <= 0);
00679   // Set the sortedness flag.
00680   x.set_sorted(still_sorted);
00681 
00682   // A well-formed system is returned.
00683   assert(x.OK(true));
00684 }

void Parma_Polyhedra_Library::Linear_System::simplify (  ) 

Applies Gaussian's elimination and back-substitution so as to simplify the linear system.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, and Parma_Polyhedra_Library::Generator_System.

Definition at line 687 of file Linear_System.cc.

References back_substitute(), Parma_Polyhedra_Library::Matrix::erase_to_end(), gauss(), num_pending_rows(), Parma_Polyhedra_Library::Matrix::num_rows(), OK(), set_sorted(), sorted, and unset_pending_rows().

Referenced by Parma_Polyhedra_Library::Generator_System::simplify(), and Parma_Polyhedra_Library::Constraint_System::simplify().

00687                            {
00688   Linear_System& x = *this;
00689   // This method is only applied to a well-formed system
00690   // having no pending rows.
00691   assert(x.OK(true));
00692   assert(x.num_pending_rows() == 0);
00693 
00694   // Partially sort the linear system so that all lines/equalities come first.
00695   dimension_type nrows = x.num_rows();
00696   dimension_type n_lines_or_equalities = 0;
00697   for (dimension_type i = 0; i < nrows; ++i)
00698     if (x[i].is_line_or_equality()) {
00699       if (n_lines_or_equalities < i) {
00700         std::swap(x[i], x[n_lines_or_equalities]);
00701         // The system was not sorted.
00702         assert(!x.sorted);
00703       }
00704       ++n_lines_or_equalities;
00705     }
00706   // Apply Gaussian's elimination to the subsystem of lines/equalities.
00707   const dimension_type rank = x.gauss(n_lines_or_equalities);
00708   // Eliminate any redundant line/equality that has been detected.
00709   if (rank < n_lines_or_equalities) {
00710     const dimension_type
00711       n_rays_or_points_or_inequalities = nrows - n_lines_or_equalities;
00712     const dimension_type
00713       num_swaps = std::min(n_lines_or_equalities - rank,
00714                            n_rays_or_points_or_inequalities);
00715     for (dimension_type i = num_swaps; i-- > 0; )
00716       std::swap(x[--nrows], x[rank + i]);
00717     x.erase_to_end(nrows);
00718     x.unset_pending_rows();
00719     if (n_rays_or_points_or_inequalities > num_swaps)
00720       x.set_sorted(false);
00721     n_lines_or_equalities = rank;
00722   }
00723   // Apply back-substitution to the system of rays/points/inequalities.
00724   x.back_substitute(n_lines_or_equalities);
00725   // A well-formed system is returned.
00726   assert(x.OK(true));
00727 }

void Parma_Polyhedra_Library::Linear_System::normalize (  ) 

Normalizes the system by dividing each row for the GCD of the row's elements.

Definition at line 454 of file Linear_System.cc.

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

Referenced by Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension().

00454                             {
00455   Linear_System& x = *this;
00456   // We normalize also the pending rows.
00457   for (dimension_type i = num_rows(); i-- > 0; )
00458     x[i].normalize();
00459   set_sorted(false);
00460 }

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

Clears the system deallocating all its rows.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 139 of file Linear_System.inlines.hh.

References Parma_Polyhedra_Library::Matrix::clear(), index_first_pending, and sorted.

Referenced by Parma_Polyhedra_Library::Generator_System::clear(), and Parma_Polyhedra_Library::Constraint_System::clear().

00139                      {
00140   // Note: do NOT modify the value of `row_topology'.
00141   Matrix::clear();
00142   index_first_pending = 0;
00143   sorted = true;
00144 }

void Parma_Polyhedra_Library::Linear_System::ascii_dump (  )  const

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

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Referenced by ascii_dump().

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

Writes to s an ASCII representation of *this.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 113 of file Linear_System.cc.

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

00113                                                 {
00114   // Prints the topology, the number of rows, the number of columns
00115   // and the sorted flag.  The specialized methods provided by
00116   // Constraint_System and Generator_System take care of properly
00117   // printing the contents of the system.
00118   const Linear_System& x = *this;
00119   dimension_type x_num_rows = x.num_rows();
00120   dimension_type x_num_columns = x.num_columns();
00121   s << "topology " << (is_necessarily_closed()
00122                        ? "NECESSARILY_CLOSED"
00123                        : "NOT_NECESSARILY_CLOSED")
00124     << "\n"
00125     << x_num_rows << " x " << x_num_columns
00126     << (x.sorted ? "(sorted)" : "(not_sorted)")
00127     << "\n"
00128     << "index_first_pending " << x.first_pending_row()
00129     << "\n";
00130   for (dimension_type i = 0; i < x_num_rows; ++i)
00131     x[i].ascii_dump(s);
00132 }

void Parma_Polyhedra_Library::Linear_System::print (  )  const

bool Parma_Polyhedra_Library::Linear_System::ascii_load ( std::istream &  s  ) 

Loads from s an ASCII representation (as produced by ascii_dump) and sets *this accordingly. Returns true if successful, false otherwise.

Reads into a Linear_System object the information produced by the output of ascii_dump(). The specialized methods provided by Constraint_System and Generator_System take care of properly reading the contents of the system.

Reimplemented from Parma_Polyhedra_Library::Matrix.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 137 of file Linear_System.cc.

References Parma_Polyhedra_Library::Matrix::OK(), resize_no_copy(), set_index_first_pending_row(), set_necessarily_closed(), set_not_necessarily_closed(), and set_sorted().

00137                                           {
00138   std::string str;
00139   if (!(s >> str) || str != "topology")
00140     return false;
00141   if (!(s >> str))
00142     return false;
00143   if (str == "NECESSARILY_CLOSED")
00144     set_necessarily_closed();
00145   else {
00146     if (str != "NOT_NECESSARILY_CLOSED")
00147       return false;
00148     set_not_necessarily_closed();
00149   }
00150 
00151   dimension_type nrows;
00152   dimension_type ncols;
00153   if (!(s >> nrows))
00154     return false;
00155   if (!(s >> str))
00156     return false;
00157   if (!(s >> ncols))
00158     return false;
00159   resize_no_copy(nrows, ncols);
00160 
00161   if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00162     return false;
00163   set_sorted(str == "(sorted)");
00164   dimension_type index;
00165   if (!(s >> str) || str != "index_first_pending")
00166     return false;
00167   if (!(s >> index))
00168     return false;
00169   set_index_first_pending_row(index);
00170 
00171   Linear_System& x = *this;
00172   for (dimension_type row = 0; row < nrows; ++row)
00173     if (!x[row].ascii_load(s))
00174       return false;
00175 
00176   // Check for well-formedness.
00177   assert(OK(true));
00178   return true;
00179 }

memory_size_type Parma_Polyhedra_Library::Linear_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.

Reimplemented in Parma_Polyhedra_Library::Constraint_System, Parma_Polyhedra_Library::Generator_System, and Parma_Polyhedra_Library::Grid_Generator_System.

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

References external_memory_in_bytes().

00036                                            {
00037   return sizeof(*this) + external_memory_in_bytes();
00038 }

memory_size_type Parma_Polyhedra_Library::Linear_System::external_memory_in_bytes (  )  const [inline]

bool Parma_Polyhedra_Library::Linear_System::OK ( bool  check_strong_normalized = true  )  const

Checks if all the invariants are satisfied.

Parameters:
check_strong_normalized true if and only if the strong normalization of all the rows in the system has to be checked.
By default, the strong normalization check is performed. This check may be turned off to avoid useless repeated checking; e.g., when re-checking a well-formed Linear_System after the permutation or deletion of some of its rows.

Definition at line 830 of file Linear_System.cc.

References check_sorted(), first_pending_row(), is_necessarily_closed(), Parma_Polyhedra_Library::Matrix::num_columns(), Parma_Polyhedra_Library::Matrix::num_rows(), Parma_Polyhedra_Library::Matrix::OK(), Parma_Polyhedra_Library::Matrix::row_capacity, Parma_Polyhedra_Library::Matrix::row_size, sorted, strong_normalize(), and topology().

Referenced by back_substitute(), gauss(), Parma_Polyhedra_Library::Polyhedron::simplify(), and simplify().

00830                                                              {
00831 #ifndef NDEBUG
00832   using std::endl;
00833   using std::cerr;
00834 #endif
00835 
00836   // `index_first_pending' must be less than or equal to `num_rows()'.
00837   if (first_pending_row() > num_rows()) {
00838 #ifndef NDEBUG
00839     cerr << "Linear_System has a negative number of pending rows!"
00840          << endl;
00841 #endif
00842     return false;
00843   }
00844 
00845   // An empty system is OK,
00846   // unless it is an NNC system with exactly one column.
00847   if (num_rows() == 0)
00848     if (is_necessarily_closed() || num_columns() != 1)
00849       return true;
00850     else {
00851 #ifndef NDEBUG
00852       cerr << "NNC Linear_System has one column" << endl;
00853 #endif
00854       return false;
00855     }
00856 
00857   // A non-empty system will contain constraints or generators; in
00858   // both cases it must have at least one column for the inhomogeneous
00859   // term and, if it is NNC, another one for the epsilon coefficient.
00860   const dimension_type min_cols = is_necessarily_closed() ? 1 : 2;
00861   if (num_columns() < min_cols) {
00862 #ifndef NDEBUG
00863     cerr << "Linear_System has fewer columns than the minimum "
00864          << "allowed by its topology:"
00865          << endl
00866          << "num_columns is " << num_columns()
00867          << ", minimum is " << min_cols
00868          << endl;
00869 #endif
00870     return false;
00871   }
00872 
00873   const Linear_System& x = *this;
00874   const dimension_type n_rows = num_rows();
00875   for (dimension_type i = 0; i < n_rows; ++i) {
00876     if (!x[i].OK(row_size, row_capacity))
00877       return false;
00878     // Checking for topology mismatches.
00879     if (x.topology() != x[i].topology()) {
00880 #ifndef NDEBUG
00881       cerr << "Topology mismatch between the system "
00882            << "and one of its rows!"
00883            << endl;
00884 #endif
00885       return false;
00886     }
00887   }
00888 
00889   if (check_strong_normalized) {
00890     // Check for strong normalization of rows.
00891     // Note: normalization cannot be checked inside the
00892     // Linear_Row::OK() method, because a Linear_Row object may also
00893     // implement a Linear_Expression object, which in general cannot
00894     // be (strongly) normalized.
00895     Linear_System tmp(x, With_Pending());
00896     tmp.strong_normalize();
00897     if (x != tmp) {
00898 #ifndef NDEBUG
00899       cerr << "Linear_System rows are not strongly normalized!"
00900            << endl;
00901 #endif
00902       return false;
00903     }
00904   }
00905 
00906   if (sorted && !check_sorted()) {
00907 #ifndef NDEBUG
00908     cerr << "The system declares itself to be sorted but it is not!"
00909          << endl;
00910 #endif
00911     return false;
00912   }
00913 
00914   // All checks passed.
00915   return true;
00916 }


Friends And Related Function Documentation

Specializes std::swap.

Definition at line 242 of file Linear_System.inlines.hh.

References swap().

00243                                               {
00244   x.swap(y);
00245 }

bool operator== ( const Linear_System x,
const Linear_System y 
) [related]

Returns true if and only if x and y are identical.

Definition at line 482 of file Linear_System.cc.

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

00482                                                               {
00483   if (x.num_columns() != y.num_columns())
00484     return false;
00485   const dimension_type x_num_rows = x.num_rows();
00486   const dimension_type y_num_rows = y.num_rows();
00487   if (x_num_rows != y_num_rows)
00488     return false;
00489   if (x.first_pending_row() != y.first_pending_row())
00490     return false;
00491   // Notice that calling operator==(const Matrix&, const Matrix&)
00492   // would be wrong here, as equality of the type fields would
00493   // not be checked.
00494   for (dimension_type i = x_num_rows; i-- > 0; )
00495     if (x[i] != y[i])
00496       return false;
00497   return true;
00498 }

bool operator!= ( const Linear_System x,
const Linear_System y 
) [related]

Returns true if and only if x and y are different.

Definition at line 226 of file Linear_System.inlines.hh.

00226                                                            {
00227   return !(x == y);
00228 }


Member Data Documentation

The index of the first pending row.

Definition at line 383 of file Linear_System.defs.hh.

Referenced by assign_with_pending(), clear(), first_pending_row(), set_index_first_pending_row(), swap(), and unset_pending_rows().

true if rows are sorted in the ascending order as defined by bool compare(const Linear_Row&, const Linear_Row&). If false may not be sorted.

Definition at line 390 of file Linear_System.defs.hh.

Referenced by add_pending_rows(), ascii_dump(), assign_with_pending(), clear(), is_sorted(), Linear_System(), OK(), operator=(), set_sorted(), simplify(), sort_rows(), and swap().


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

Generated on Wed Jul 16 22:55:46 2008 for PPL by  doxygen 1.5.6