A 2-dimensional matrix of coefficients. More...

#include <Dense_Matrix.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::Dense_Matrix:

Classes
class	const_iterator
	An iterator over a matrix. More...
Public Member Functions
	Dense_Matrix ()
	Builds an empty matrix.
	Dense_Matrix (dimension_type n_rows, dimension_type n_columns, Dense_Row::Flags row_flags=Dense_Row::Flags())
	Builds a zero matrix with specified dimensions and flags.
	Dense_Matrix (const Dense_Matrix &y)
	Copy constructor.
	~Dense_Matrix ()
	Destructor.
Dense_Matrix &	operator= (const Dense_Matrix &y)
	Assignment operator.
bool	has_no_rows () const
	Returns `true` if and only if `*this` has no rows.
const_iterator	begin () const
	Returns the const_iterator pointing to the first row, if `*this` is not empty; otherwise, returns the past-the-end const_iterator.
const_iterator	end () const
	Returns the past-the-end const_iterator.
void	m_swap (Dense_Matrix &y)
	Swaps `*this` with `y`.
void	add_zero_rows (dimension_type n, Dense_Row::Flags row_flags)
	Adds to the matrix `n` rows of zeroes with flags set to `row_flags`.
void	add_zero_columns (dimension_type n)
	Adds `n` columns of zeroes to the matrix.
void	add_zero_columns (dimension_type n, dimension_type i)
	Adds `n` columns of zeroes to the matrix before the i-th column.
void	add_zero_rows_and_columns (dimension_type n, dimension_type m, Dense_Row::Flags row_flags)
	Adds `n` rows and `m` columns of zeroes to the matrix.
void	add_row (const Dense_Row &y)
	Adds a copy of the row `y` to the matrix.
void	add_recycled_row (Dense_Row &y)
	Adds the row `y` to the matrix.
void	remove_trailing_columns (dimension_type n)
	Makes the matrix shrink by removing its `n` trailing columns.
void	remove_column (dimension_type i)
	Makes the matrix shrink by removing its i-th column.
void	resize_no_copy (dimension_type new_n_rows, dimension_type new_n_columns, Dense_Row::Flags row_flags)
	Resizes the matrix without worrying about the old contents.
void	swap_columns (dimension_type i, dimension_type j)
	Swaps the columns having indexes `i` and `j`.
void	permute_columns (const std::vector< dimension_type > &cycles)
	Permutes the columns of the matrix.
void	clear ()
	Clears the matrix 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(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`.
void	remove_trailing_rows (dimension_type n)
	Removes from the matrix the last `n` rows.
bool	OK () const
	Checks if all the invariants are satisfied.
Accessors
dimension_type	num_columns () const
	Returns the number of columns of the matrix (i.e., the size of the rows).
dimension_type	num_rows () const
	Returns the number of rows in the matrix.
Subscript operators
Dense_Row &	operator[] (dimension_type k)
	Returns a reference to the `k-th` row of the matrix.
const Dense_Row &	operator[] (dimension_type k) const
	Returns a constant reference to the `k-th` row of the matrix.
Static Public Member Functions
static dimension_type	max_num_rows ()
	Returns the maximum number of rows of a Dense_Matrix.
static dimension_type	max_num_columns ()
	Returns the maximum number of columns of a Dense_Matrix.
Protected Attributes
std::vector< Dense_Row >	rows
	Contains the rows of the matrix.
dimension_type	row_size
	Size of the initialized part of each row.
dimension_type	row_capacity
	Capacity allocated for each row.
Related Functions
(Note that these are not member functions.)
bool	operator== (const Dense_Matrix &x, const Dense_Matrix &y)
void	swap (Dense_Matrix &x, Dense_Matrix &y)
	Swaps `x` with `y`.
bool	operator== (const Dense_Matrix &x, const Dense_Matrix &y)
	Returns `true` if and only if `x` and `y` are identical.
bool	operator!= (const Dense_Matrix &x, const Dense_Matrix &y)
	Returns `true` if and only if `x` and `y` are different.
bool	operator!= (const Dense_Matrix &x, const Dense_Matrix &y)
void	swap (Dense_Matrix &x, Dense_Matrix &y)

Detailed Description

A 2-dimensional matrix of coefficients.

A Dense_Matrix object is a sequence of Dense_Row objects and is characterized by the matrix dimensions (the number of rows and columns). All the rows in a matrix, besides having the same size (corresponding to the number of columns of the matrix), are also bound to have the same capacity.

Definition at line 46 of file Dense_Matrix.defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Dense_Matrix::Dense_Matrix ( )

inline

Builds an empty matrix.

Rows' size and capacity are initialized to $0$ .

Definition at line 124 of file Dense_Matrix.inlines.hh.

References OK(), and PPL_ASSERT.

  : rows(),
    row_size(0),
    row_capacity(0) {
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::Dense_Matrix::Dense_Matrix	(	dimension_type	n_rows,
		dimension_type	n_columns,
		Dense_Row::Flags	row_flags = `Dense_Row::Flags()`
	)

Builds a zero matrix with specified dimensions and flags.

Parameters:

n_rows	The number of rows of the matrix that will be created;
n_columns	The number of columns of the matrix that will be created.
row_flags	The flags used to build the rows of the matrix; by default, the rows will have all flags unset.

Definition at line 33 of file Dense_Matrix.cc.

References max_num_rows(), OK(), PPL_ASSERT, row_capacity, and rows.

  :
#ifdef NDEBUG
    rows(n_rows),
#else
    rows(n_rows <= max_num_rows() ? n_rows : 0),
#endif
    row_size(n_columns),
    row_capacity(compute_capacity(n_columns, max_num_columns())) {
  PPL_ASSERT(n_rows <= max_num_rows());
  // Construct in direct order: will destroy in reverse order.
  for (dimension_type i = 0; i < n_rows; ++i) {
    rows[i].set_flags(row_flags);
    rows[i].resize(n_columns, row_capacity);
  }
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::Dense_Matrix::Dense_Matrix ( const Dense_Matrix & y )

inline

Copy constructor.

Definition at line 132 of file Dense_Matrix.inlines.hh.

References OK(), and PPL_ASSERT.

  : rows(y.rows),
    row_size(y.row_size),
    row_capacity(y.row_capacity) {
  PPL_ASSERT(OK());
}

Parma_Polyhedra_Library::Dense_Matrix::~Dense_Matrix ( )

inline

Destructor.

Definition at line 140 of file Dense_Matrix.inlines.hh.

{
}

Member Function Documentation

void Parma_Polyhedra_Library::Dense_Matrix::add_recycled_row ( Dense_Row & y )

Adds the row y to the matrix.

Parameters:

y	The row to be added: it must have the same size and capacity as `*this`. It is not declared `const` because its data-structures will recycled to build the new matrix row.

Turns the $r \times c$ matrix $M$ into the $(r+1) \times c$ matrix $\genfrac{(}{)}{0pt}{}{M}{y}$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 219 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), Parma_Polyhedra_Library::Dense_Row::OK(), PPL_ASSERT, and Parma_Polyhedra_Library::swap().

Referenced by add_row().

                                              {
  // The added row must have the same size and capacity as the
  // existing rows of the system.
  PPL_ASSERT(y.OK(row_size, row_capacity));
  using std::swap;
  const dimension_type new_rows_size = rows.size() + 1;
  if (rows.capacity() < new_rows_size) {
    // Reallocation will take place.
    std::vector<Dense_Row> new_rows;
    new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
    new_rows.insert(new_rows.end(), new_rows_size, Dense_Row());
    // Put the new row in place.
    dimension_type i = new_rows_size-1;
    swap(new_rows[i], y);
    // Steal the old rows.
    while (i-- > 0)
      new_rows[i].m_swap(rows[i]);
    // Put the new rows into place.
    swap(rows, new_rows);
  }
  else
    // Reallocation will NOT take place.
    // Inserts a new empty row at the end,
    // then substitutes it with a copy of the given row.
    swap(*rows.insert(rows.end(), Dense_Row()), y);

  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::add_row ( const Dense_Row & y )

inline

Adds a copy of the row y to the matrix.

Parameters:

y	The row to be copied: it must have the same number of columns as the matrix.

Turns the $r \times c$ matrix $M$ into the $(r+1) \times c$ matrix $\genfrac{(}{)}{0pt}{}{M}{y}$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 155 of file Dense_Matrix.inlines.hh.

References add_recycled_row(), OK(), PPL_ASSERT, and row_capacity.

Referenced by Parma_Polyhedra_Library::Linear_System::add_row(), and Parma_Polyhedra_Library::Grid_Generator_System::insert().

                                        {
  Dense_Row new_row(y, row_capacity);
  add_recycled_row(new_row);
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::add_zero_columns ( dimension_type n )

Adds n columns of zeroes to the matrix.

Parameters:

n	The number of columns to be added: must be strictly positive.

Turns the $r \times c$ matrix $M$ into the $r \times (c+n)$ matrix $(M \, 0)$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 88 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), PPL_ASSERT, and Parma_Polyhedra_Library::swap().

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Congruence_System::clear(), and Parma_Polyhedra_Library::Grid_Generator_System::clear().

                                                        {
  PPL_ASSERT(n > 0);
  PPL_ASSERT(n <= max_num_columns() - num_columns());
  const dimension_type num_rows = rows.size();
  const dimension_type new_num_columns = row_size + n;

  if (new_num_columns <= row_capacity)
    // We have enough capacity: we resize existing rows.
    for (dimension_type i = num_rows; i-- > 0; )
      rows[i].expand_within_capacity(new_num_columns);
  else {
    // Capacity exhausted: we must reallocate the rows and
    // make sure all the rows have the same capacity.
    const dimension_type new_row_capacity
      = compute_capacity(new_num_columns, max_num_columns());
    PPL_ASSERT(new_row_capacity <= max_num_columns());
    for (dimension_type i = num_rows; i-- > 0; ) {
      Dense_Row new_row(rows[i], new_num_columns, new_row_capacity);
      using std::swap;
      swap(rows[i], new_row);
    }
    row_capacity = new_row_capacity;
  }
  // Rows have been expanded.
  row_size = new_num_columns;
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::add_zero_columns	(	dimension_type	n,
		dimension_type	i
	)

Adds n columns of zeroes to the matrix before the i-th column.

Parameters:

n	The number of columns to be added: must be strictly positive.
i	The column before which the new columns have to be added.

The matrix is expanded avoiding reallocation whenever possible.

Definition at line 117 of file Dense_Matrix.cc.

References PPL_ASSERT.

                                                                    {
  const dimension_type old_num_columns = num_columns();

  PPL_ASSERT(i <= old_num_columns);

  add_zero_columns(n);

  if (i == old_num_columns)
    return;

  // Shift to the right the columns between i and old_num_columns.
  std::vector<dimension_type> swaps;
  const dimension_type num_columns_to_swap = old_num_columns - i;
  swaps.reserve(3 * num_columns_to_swap);

  for (dimension_type j = 0; j < num_columns_to_swap; ++j) {
    swaps.push_back(i + j);
    swaps.push_back(old_num_columns + j);
    swaps.push_back(0);
  }
  permute_columns(swaps);

  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::add_zero_rows	(	dimension_type	n,
		Dense_Row::Flags	row_flags
	)

Adds to the matrix n rows of zeroes with flags set to row_flags.

Parameters:

n	The number of rows to be added: must be strictly positive.
row_flags	Flags for the newly added rows.

Turns the $r \times c$ matrix $M$ into the $(r+n) \times c$ matrix $\genfrac{(}{)}{0pt}{}{M}{0}$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 54 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), PPL_ASSERT, and Parma_Polyhedra_Library::swap().

Referenced by Parma_Polyhedra_Library::Grid_Generator_System::recycling_insert(), and Parma_Polyhedra_Library::Grid::simplify().

                                                           {
  PPL_ASSERT(n > 0);
  PPL_ASSERT(n <= max_num_rows() - num_rows());
  const dimension_type old_num_rows = rows.size();
  const dimension_type new_num_rows = old_num_rows + n;

  if (rows.capacity() < new_num_rows) {
    // Reallocation will take place.
    std::vector<Dense_Row> new_rows;
    new_rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
    new_rows.insert(new_rows.end(), new_num_rows, Dense_Row(row_flags));
    // Construct the new rows.
    dimension_type i = new_num_rows;
    while (i-- > old_num_rows)
      new_rows[i].resize(row_size, row_capacity);
    // Steal the old rows.
    ++i;
    while (i-- > 0)
      new_rows[i].m_swap(rows[i]);
    // Put the new vector into place.
    using std::swap;
    swap(rows, new_rows);
  }
  else {
    // Reallocation will NOT take place.
    rows.insert(rows.end(), n, Dense_Row(row_flags));
    for (dimension_type i = new_num_rows; i-- > old_num_rows; )
      rows[i].resize(row_size, row_capacity);
  }
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::add_zero_rows_and_columns	(	dimension_type	n,
		dimension_type	m,
		Dense_Row::Flags	row_flags
	)

Adds n rows and m columns of zeroes to the matrix.

Parameters:

n	The number of rows to be added: must be strictly positive.
m	The number of columns to be added: must be strictly positive.
row_flags	Flags for the newly added rows.

Turns the $r \times c$ matrix $M$ into the $(r+n) \times (c+m)$ matrix $\bigl(\genfrac{}{}{0pt}{}{M}{0} \genfrac{}{}{0pt}{}{0}{0}\bigr)$ . The matrix is expanded avoiding reallocation whenever possible.

Definition at line 143 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), PPL_ASSERT, row_capacity, row_size, rows, and Parma_Polyhedra_Library::swap().

Referenced by Parma_Polyhedra_Library::Grid_Generator_System::recycling_insert().

                                                                       {
  PPL_ASSERT(n > 0);
  PPL_ASSERT(n <= max_num_rows() - num_rows());
  PPL_ASSERT(m > 0);
  PPL_ASSERT(m <= max_num_columns() - num_columns());
  const dimension_type old_num_rows = rows.size();
  const dimension_type new_num_rows = old_num_rows + n;
  const dimension_type new_num_columns = row_size + m;

  if (new_num_columns <= row_capacity) {
    // We can recycle the old rows.
    if (rows.capacity() < new_num_rows) {
      // Reallocation will take place.
      std::vector<Dense_Row> new_rows;
      new_rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
      new_rows.insert(new_rows.end(), new_num_rows, Dense_Row(row_flags));
      // Construct the new rows.
      dimension_type i = new_num_rows;
      while (i-- > old_num_rows)
        new_rows[i].resize(new_num_columns, row_capacity);
      // Expand and steal the old rows.
      ++i;
      while (i-- > 0) {
        rows[i].expand_within_capacity(new_num_columns);
        new_rows[i].m_swap(rows[i]);
      }
      // Put the new vector into place.
      using std::swap;
      swap(rows, new_rows);
    }
    else {
      // Reallocation will NOT take place.
      rows.insert(rows.end(), n, Dense_Row(row_flags));
      // Construct the new rows.
      dimension_type i = new_num_rows;
      while (i-- > old_num_rows)
        rows[i].resize(new_num_columns, row_capacity);
      // Expand the old rows.
      ++i;
      while (i-- > 0)
        rows[i].expand_within_capacity(new_num_columns);
    }
    row_size = new_num_columns;
  }
  else {
    // We cannot even recycle the old rows.
    Dense_Matrix new_matrix;
    new_matrix.rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
    new_matrix.rows.insert(new_matrix.rows.end(), new_num_rows,
                           Dense_Row(row_flags));
    // Construct the new rows.
    new_matrix.row_size = new_num_columns;
    new_matrix.row_capacity = compute_capacity(new_num_columns,
                                               max_num_columns());
    dimension_type i = new_num_rows;
    while (i-- > old_num_rows)
      new_matrix.rows[i].resize(new_matrix.row_size, new_matrix.row_capacity);
    // Copy the old rows.
    ++i;
    while (i-- > 0) {
      Dense_Row new_row(rows[i],
                        new_matrix.row_size,
                        new_matrix.row_capacity);
      using std::swap;
      swap(new_matrix.rows[i], new_row);
    }
    // Put the new vector into place.
    m_swap(new_matrix);
  }

  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::ascii_dump ( ) const

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

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

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

Writes to s an ASCII representation of *this.

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

Definition at line 333 of file Dense_Matrix.cc.

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

                                               {
  const Dense_Matrix& x = *this;
  dimension_type x_num_rows = x.num_rows();
  dimension_type x_num_columns = x.num_columns();
  s << x_num_rows << " x " << x_num_columns << "\n";
  for (dimension_type i = 0; i < x_num_rows; ++i)
    x[i].ascii_dump(s);
}

bool Parma_Polyhedra_Library::Dense_Matrix::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 in Parma_Polyhedra_Library::Grid_Generator_System, Parma_Polyhedra_Library::Linear_System, Parma_Polyhedra_Library::Generator_System, Parma_Polyhedra_Library::Congruence_System, and Parma_Polyhedra_Library::Constraint_System.

Definition at line 345 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::ascii_load(), and PPL_ASSERT.

                                         {
  Dense_Matrix& x = *this;
  std::string str;
  dimension_type x_num_rows;
  dimension_type x_num_cols;
  if (!(s >> x_num_rows))
    return false;
  if (!(s >> str) || str != "x")
    return false;
  if (!(s >> x_num_cols))
    return false;

  resize_no_copy(x_num_rows, x_num_cols, Dense_Row::Flags());

  for (dimension_type row = 0; row < x_num_rows; ++row)
    if (!x[row].ascii_load(s))
      return false;

  // Check invariants.
  PPL_ASSERT(OK());
  return true;
}

Dense_Matrix::const_iterator Parma_Polyhedra_Library::Dense_Matrix::begin ( ) const

inline

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

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

Definition at line 106 of file Dense_Matrix.inlines.hh.

References rows.

Referenced by Parma_Polyhedra_Library::Constraint_System::begin(), Parma_Polyhedra_Library::Congruence_System::begin(), and Parma_Polyhedra_Library::Generator_System::begin().

                          {
  return const_iterator(rows.begin());
}

void Parma_Polyhedra_Library::Dense_Matrix::clear ( )

inline

Clears the matrix deallocating all its rows.

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

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

References OK(), PPL_ASSERT, row_capacity, row_size, rows, and swap().

                    {
  // Clear `rows' and minimize its capacity.
  std::vector<Dense_Row> tmp;
  using std::swap;
  swap(rows, tmp);
  row_size = 0;
  row_capacity = 0;
  PPL_ASSERT(OK());
}

Dense_Matrix::const_iterator Parma_Polyhedra_Library::Dense_Matrix::end ( ) const

inline

Returns the past-the-end const_iterator.

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

Definition at line 111 of file Dense_Matrix.inlines.hh.

References rows.

Referenced by Parma_Polyhedra_Library::Constraint_System::end(), Parma_Polyhedra_Library::Congruence_System::end(), and Parma_Polyhedra_Library::Generator_System::end().

                        {
  return const_iterator(rows.end());
}

PPL::memory_size_type Parma_Polyhedra_Library::Dense_Matrix::external_memory_in_bytes ( ) const

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

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

Definition at line 453 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::external_memory_in_bytes().

Referenced by total_memory_in_bytes().

                                                {
  memory_size_type n = rows.capacity() * sizeof(Dense_Row);
  for (dimension_type i = num_rows(); i-- > 0; )
    n += rows[i].external_memory_in_bytes(row_capacity);
  return n;
}

bool Parma_Polyhedra_Library::Dense_Matrix::has_no_rows ( ) const

inline

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

Note:: The unusual naming for this method is intentional: we do not want it to be named empty because this would cause an error prone name clash with the corresponding methods in derived classes Constraint_System and Congruence_System (which have a different semantics).

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

References rows.

                                {
  return rows.empty();
}

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

inline

Swaps *this with y.

Definition at line 116 of file Dense_Matrix.inlines.hh.

References row_capacity, row_size, rows, and swap().

Referenced by swap().

                                    {
  using std::swap;
  swap(rows, y.rows);
  swap(row_size, y.row_size);
  swap(row_capacity, y.row_capacity);
}

dimension_type Parma_Polyhedra_Library::Dense_Matrix::max_num_columns ( )

inlinestatic

Returns the maximum number of columns of a Dense_Matrix.

Definition at line 39 of file Dense_Matrix.inlines.hh.

References Parma_Polyhedra_Library::Dense_Row::max_size().

Referenced by Parma_Polyhedra_Library::Linear_System::max_space_dimension(), and Parma_Polyhedra_Library::Congruence_System::max_space_dimension().

                              {
  return Dense_Row::max_size();
}

dimension_type Parma_Polyhedra_Library::Dense_Matrix::max_num_rows ( )

inlinestatic

Returns the maximum number of rows of a Dense_Matrix.

Definition at line 34 of file Dense_Matrix.inlines.hh.

Referenced by Dense_Matrix().

                           {
  return std::vector<Dense_Row>().max_size();
}

dimension_type Parma_Polyhedra_Library::Dense_Matrix::num_columns ( ) const

inline

Returns the number of columns of the matrix (i.e., the size of the rows).

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 179 of file Dense_Matrix.inlines.hh.

References row_size.

                                {
  return row_size;
}

dimension_type Parma_Polyhedra_Library::Dense_Matrix::num_rows ( ) const

inline

Returns the number of rows in the matrix.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System.

Definition at line 174 of file Dense_Matrix.inlines.hh.

References rows.

                             {
  return rows.size();
}

bool Parma_Polyhedra_Library::Dense_Matrix::OK ( ) const

Checks if all the invariants are satisfied.

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

Definition at line 461 of file Dense_Matrix.cc.

Referenced by add_row(), clear(), Dense_Matrix(), Parma_Polyhedra_Library::Constraint_System::OK(), Parma_Polyhedra_Library::Congruence_System::OK(), Parma_Polyhedra_Library::Generator_System::OK(), Parma_Polyhedra_Library::Grid_Generator_System::OK(), operator=(), and remove_trailing_rows().

                          {
  if (row_size > row_capacity) {
#ifndef NDEBUG
    std::cerr << "Dense_Matrix completely broken: "
              << "row_capacity is " << row_capacity
              << ", row_size is " << row_size
              << std::endl;
#endif
    return false;
  }

  const Dense_Matrix& x = *this;
  for (dimension_type i = 0, n_rows = num_rows(); i < n_rows; ++i)
    if (!x[i].OK(row_size, row_capacity))
      return false;

  // All checks passed.
  return true;
}

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

inline

Assignment operator.

Definition at line 144 of file Dense_Matrix.inlines.hh.

References OK(), PPL_ASSERT, row_capacity, row_size, and rows.

                                             {
  if (this != &y) {
    rows = y.rows;
    row_size = y.row_size;
    row_capacity = y.row_capacity;
  }
  PPL_ASSERT(OK());
  return *this;
}

Dense_Row & Parma_Polyhedra_Library::Dense_Matrix::operator[] ( dimension_type k )

inline

Returns a reference to the k-th row of the matrix.

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

Definition at line 162 of file Dense_Matrix.inlines.hh.

References PPL_ASSERT, and rows.

                                               {
  PPL_ASSERT(k < rows.size());
  return rows[k];
}

const Dense_Row & Parma_Polyhedra_Library::Dense_Matrix::operator[] ( dimension_type k ) const

inline

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

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

Definition at line 168 of file Dense_Matrix.inlines.hh.

References PPL_ASSERT, and rows.

                                                     {
  PPL_ASSERT(k < rows.size());
  return rows[k];
}

void Parma_Polyhedra_Library::Dense_Matrix::permute_columns ( const std::vector< dimension_type > & cycles )

Permutes the columns of the matrix.

Reimplemented in Parma_Polyhedra_Library::Grid_Generator_System, and Parma_Polyhedra_Library::Linear_System.

Definition at line 409 of file Dense_Matrix.cc.

References PPL_ASSERT, PPL_DIRTY_TEMP_COEFFICIENT, and Parma_Polyhedra_Library::swap().

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

                                                                        {
  PPL_DIRTY_TEMP_COEFFICIENT(tmp);
  const dimension_type n = cycles.size();
  PPL_ASSERT(cycles[n - 1] == 0);
  using std::swap;
  for (dimension_type k = num_rows(); k-- > 0; ) {
    Dense_Row& rows_k = rows[k];
    for (dimension_type i = 0, j = 0; i < n; i = ++j) {
      // Make `j' be the index of the next cycle terminator.
      while (cycles[j] != 0)
        ++j;
      // Cycles of length less than 2 are not allowed.
      PPL_ASSERT(j - i >= 2);
      if (j - i == 2)
        // For cycles of length 2 no temporary is needed, just a swap.
        swap(rows_k[cycles[i]], rows_k[cycles[i+1]]);
      else {
        // Longer cycles need a temporary.
        swap(rows_k[cycles[j-1]], tmp);
        for (dimension_type l = j-1; l > i; --l)
          swap(rows_k[cycles[l-1]], rows_k[cycles[l]]);
        swap(tmp, rows_k[cycles[i]]);
      }
    }
  }
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::print ( ) const

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

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

void Parma_Polyhedra_Library::Dense_Matrix::remove_column ( dimension_type i )

Makes the matrix shrink by removing its i-th column.

Definition at line 393 of file Dense_Matrix.cc.

References PPL_ASSERT.

                                                     {
  PPL_ASSERT(i < row_size);
  const dimension_type n_cols = num_columns();
  if (i != n_cols - 1) {
    std::vector<dimension_type> cycle;
    for (dimension_type j = n_cols - 1; j >= i; --j)
      cycle.push_back(j);
    cycle.push_back(0);
    permute_columns(cycle);
  }
  remove_trailing_columns(1);
  
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::remove_trailing_columns ( dimension_type n )

Makes the matrix shrink by removing its n trailing columns.

Reimplemented in Parma_Polyhedra_Library::Linear_System.

Definition at line 382 of file Dense_Matrix.cc.

References PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::Grid_Generator_System::remove_higher_space_dimensions(), and Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions().

                                                               {
  PPL_ASSERT(n > 0);
  PPL_ASSERT(n <= row_size);
  row_size -= n;
  for (dimension_type i = num_rows(); i-- > 0; )
    rows[i].shrink(row_size);
  
  PPL_ASSERT(OK());
}

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

inline

Removes from the matrix the last n rows.

Definition at line 190 of file Dense_Matrix.inlines.hh.

References OK(), PPL_ASSERT, and rows.

                                                         {
  PPL_ASSERT(n <= rows.size());
  if (n != 0)
    rows.resize(rows.size() - n);
  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::resize_no_copy	(	dimension_type	new_n_rows,
		dimension_type	new_n_columns,
		Dense_Row::Flags	row_flags
	)

Resizes the matrix without worrying about the old contents.

Parameters:

new_n_rows	The number of rows of the resized matrix;
new_n_columns	The number of columns of the resized matrix.
row_flags	The flags of the rows eventually added to the matrix.

The matrix is expanded to the specified dimensions avoiding reallocation whenever possible. The contents of the original matrix is lost.

Definition at line 249 of file Dense_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), PPL_ASSERT, and Parma_Polyhedra_Library::swap().

                                                            {
  dimension_type old_n_rows = rows.size();
  // Note that, if we have `new_n_rows <= old_n_rows' and
  // `new_n_columns >= row_size', the matrix will keep its sortedness.
  // This is obvious if `new_n_columns == row_size'.
  // If `new_n_columns > row_size', then sortedness is maintained
  // because trailing zeroes will be added to all rows.
  if (new_n_rows > old_n_rows) {
    if (new_n_columns <= row_capacity) {
      // We can recycle the old rows.
      if (rows.capacity() < new_n_rows) {
        // Reallocation (of vector `rows') will take place.
        std::vector<Dense_Row> new_rows;
        new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
        new_rows.insert(new_rows.end(), new_n_rows, Dense_Row(row_flags));
        // Construct the new rows (be careful: each new row must have
        // the same capacity as each one of the old rows).
        dimension_type i = new_n_rows;
        while (i-- > old_n_rows)
          new_rows[i].resize(new_n_columns, row_capacity);
        // Steal the old rows.
        ++i;
        while (i-- > 0)
          new_rows[i].m_swap(rows[i]);
        // Put the new vector into place.
        using std::swap;
        swap(rows, new_rows);
      }
      else {
        // Reallocation (of vector `rows') will NOT take place.
        rows.insert(rows.end(), new_n_rows - old_n_rows, Dense_Row(row_flags));
        // Be careful: each new row must have
        // the same capacity as each one of the old rows.
        for (dimension_type i = new_n_rows; i-- > old_n_rows; )
          rows[i].resize(new_n_columns, row_capacity);
      }
    }
    else {
      // We cannot even recycle the old rows: allocate a new matrix and swap.
      Dense_Matrix new_matrix(new_n_rows, new_n_columns, row_flags);
      m_swap(new_matrix);
      return;
    }
  }
  else if (new_n_rows < old_n_rows) {
    // Drop some rows.
    rows.resize(new_n_rows);
    old_n_rows = new_n_rows;
  }
  // Here we have the right number of rows.
  if (new_n_columns != row_size) {
    if (new_n_columns < row_size) {
      // Shrink the existing rows.
      for (dimension_type i = old_n_rows; i-- > 0; )
        rows[i].shrink(new_n_columns);
    }
    else
      // We need more columns.
      if (new_n_columns <= row_capacity)
        // But we have enough capacity: we resize existing rows.
        for (dimension_type i = old_n_rows; i-- > 0; )
          rows[i].expand_within_capacity(new_n_columns);
      else {
        // Capacity exhausted: we must reallocate the rows and
        // make sure all the rows have the same capacity.
        const dimension_type new_row_capacity
          = compute_capacity(new_n_columns, max_num_columns());
        for (dimension_type i = old_n_rows; i-- > 0; ) {
          Dense_Row new_row(new_n_columns, new_row_capacity, row_flags);
          using std::swap;
          swap(rows[i], new_row);
        }
        row_capacity = new_row_capacity;
      }
    // Rows have grown or shrunk.
    row_size = new_n_columns;
  }

  PPL_ASSERT(OK());
}

void Parma_Polyhedra_Library::Dense_Matrix::swap_columns	(	dimension_type	i,
		dimension_type	j
	)

Swaps the columns having indexes i and j.

Definition at line 369 of file Dense_Matrix.cc.

References PPL_ASSERT, and Parma_Polyhedra_Library::swap().

Referenced by Parma_Polyhedra_Library::Grid::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Generator_System::adjust_topology_and_space_dimension(), Parma_Polyhedra_Library::Grid_Generator_System::recycling_insert(), and Parma_Polyhedra_Library::Grid_Generator_System::remove_space_dimensions().

                                                        {
  PPL_ASSERT(i != j && i < num_columns() && j < num_columns());
  for (dimension_type k = num_rows(); k-- > 0; ) {
    Dense_Row& rows_k = rows[k];
    using std::swap;
    swap(rows_k[i], rows_k[j]);
  }

  PPL_ASSERT(OK());
}

memory_size_type Parma_Polyhedra_Library::Dense_Matrix::total_memory_in_bytes ( ) const

inline

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

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

Definition at line 44 of file Dense_Matrix.inlines.hh.

References external_memory_in_bytes().

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

Friends And Related Function Documentation

bool operator!=	(	const Dense_Matrix &	x,
		const Dense_Matrix &	y
	)

                                                         {
  return !(x == y);
}

bool operator!=	(	const Dense_Matrix &	x,
		const Dense_Matrix &	y
	)

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

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

References num_columns(), and num_rows().

Referenced by Parma_Polyhedra_Library::Dense_Matrix::const_iterator::operator!=().

                                                            {
  if (x.num_columns() != y.num_columns())
    return false;
  const dimension_type x_num_rows = x.num_rows();
  const dimension_type y_num_rows = y.num_rows();
  if (x_num_rows != y_num_rows)
    return false;
  for (dimension_type i = x_num_rows; i-- > 0; )
    if (x[i] != y[i])
      return false;
  return true;
}

void swap	(	Dense_Matrix &	x,
		Dense_Matrix &	y
	)

References m_swap().

                                       {
  x.m_swap(y);
}

void swap	(	Dense_Matrix &	x,
		Dense_Matrix &	y
	)

Referenced by clear(), and m_swap().

Member Data Documentation

dimension_type Parma_Polyhedra_Library::Dense_Matrix::row_capacity

protected

Capacity allocated for each row.

Definition at line 174 of file Dense_Matrix.defs.hh.

Referenced by Parma_Polyhedra_Library::Linear_System::add_pending_rows(), add_row(), add_zero_rows_and_columns(), clear(), Dense_Matrix(), Parma_Polyhedra_Library::Congruence_System::insert(), m_swap(), and operator=().

dimension_type Parma_Polyhedra_Library::Dense_Matrix::row_size

protected

Size of the initialized part of each row.

Definition at line 171 of file Dense_Matrix.defs.hh.

Referenced by Parma_Polyhedra_Library::Linear_System::add_pending_rows(), add_zero_rows_and_columns(), clear(), Parma_Polyhedra_Library::Congruence_System::insert(), m_swap(), Parma_Polyhedra_Library::Linear_System::merge_rows_assign(), num_columns(), and operator=().

std::vector<Dense_Row> Parma_Polyhedra_Library::Dense_Matrix::rows

protected

Contains the rows of the matrix.

Definition at line 168 of file Dense_Matrix.defs.hh.

Referenced by add_zero_rows_and_columns(), begin(), clear(), Dense_Matrix(), end(), has_no_rows(), Parma_Polyhedra_Library::Congruence_System::insert(), m_swap(), num_rows(), operator=(), operator[](), remove_trailing_rows(), Parma_Polyhedra_Library::Grid::simplify(), and Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat().

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

Classes

Public Member Functions

Static Public Member Functions

Protected Attributes

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation