A matrix of bits. More...

#include <Bit_Matrix_defs.hh>

Classes
struct	Bit_Row_Less_Than
	Ordering predicate (used when implementing the sort algorithm). More...

Public Member Functions
	Bit_Matrix ()
	Default constructor. More...

	Bit_Matrix (dimension_type n_rows, dimension_type n_columns)
	Construct a bit matrix with `n_rows` rows and `n_columns` columns. More...

	Bit_Matrix (const Bit_Matrix &y)
	Copy constructor. More...

	~Bit_Matrix ()
	Destructor. More...

Bit_Matrix &	operator= (const Bit_Matrix &y)
	Assignment operator. More...

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

Bit_Row &	operator[] (dimension_type k)
	Subscript operator. More...

const Bit_Row &	operator[] (dimension_type k) const
	Constant subscript operator. More...

void	clear ()
	Clears the matrix deallocating all its rows. More...

void	transpose ()
	Transposes the matrix. More...

void	transpose_assign (const Bit_Matrix &y)
	Makes `*this` a transposed copy of `y`. More...

dimension_type	num_columns () const
	Returns the number of columns of `*this`. More...

dimension_type	num_rows () const
	Returns the number of rows of `*this`. More...

void	sort_rows ()
	Sorts the rows and removes duplicates. More...

bool	sorted_contains (const Bit_Row &row) const
	Looks for `row` in `*this`, which is assumed to be sorted. More...

void	add_recycled_row (Bit_Row &row)
	Adds `row` to `*this`. More...

void	remove_trailing_rows (dimension_type n)
	Removes the last `n` rows. More...

void	remove_trailing_columns (dimension_type n)
	Removes the last `n` columns. More...

void	resize (dimension_type new_n_rows, dimension_type new_n_columns)
	Resizes the matrix copying the old contents. More...

bool	OK () const
	Checks if all the invariants are satisfied. More...

void	ascii_dump () const
	Writes to `std::cerr` an ASCII representation of `*this`. More...

void	ascii_dump (std::ostream &s) const
	Writes to `s` an ASCII representation of `*this`. More...

void	print () const
	Prints `*this` to `std::cerr` using `operator<<`. More...

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise. More...

memory_size_type	total_memory_in_bytes () const
	Returns the total size in bytes of the memory occupied by `*this`. More...

memory_size_type	external_memory_in_bytes () const
	Returns the size in bytes of the memory managed by `*this`. More...

bool	check_sorted () const
	Checks whether `*this` is sorted. It does NOT check for duplicates. More...

Static Public Member Functions
static dimension_type	max_num_rows ()
	Returns the maximum number of rows of a Bit_Matrix. More...

Private Attributes
std::vector< Bit_Row >	rows
	Contains the rows of the matrix. More...

dimension_type	row_size
	Size of the initialized part of each row. More...

Friends
template<typename Row >
class	Parma_Polyhedra_Library::Linear_System

Related Functions
(Note that these are not member functions.)
bool	operator== (const Bit_Matrix &x, const Bit_Matrix &y)

void	swap (Bit_Matrix &x, Bit_Matrix &y)
	Swaps `x` with `y`. More...

bool	operator== (const Bit_Matrix &x, const Bit_Matrix &y)
	Returns `true` if and only if `x` and `y` are equal. More...

bool	operator!= (const Bit_Matrix &x, const Bit_Matrix &y)
	Returns `true` if and only if `x` and `y` are not equal. More...

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

void	swap (Bit_Matrix &x, Bit_Matrix &y)

Detailed Description

A matrix of bits.

Definition at line 47 of file Bit_Matrix_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix ( )

inline

Default constructor.

Definition at line 33 of file Bit_Matrix_inlines.hh.

   : rows(),
     row_size(0) {
 }

Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix	(	dimension_type	n_rows,
		dimension_type	n_columns
	)

inline

Construct a bit matrix with n_rows rows and n_columns columns.

Definition at line 44 of file Bit_Matrix_inlines.hh.

   : rows(n_rows),
     row_size(n_columns) {
 }

Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix ( const Bit_Matrix & y )

inline

Copy constructor.

Definition at line 51 of file Bit_Matrix_inlines.hh.

   : rows(y.rows),
     row_size(y.row_size) {
 }

Parma_Polyhedra_Library::Bit_Matrix::~Bit_Matrix ( )

inline

Destructor.

Definition at line 57 of file Bit_Matrix_inlines.hh.

57 {

58 }

Member Function Documentation

void Parma_Polyhedra_Library::Bit_Matrix::add_recycled_row ( Bit_Row & row )

Adds row to *this.

Parameters

row	The row whose implementation will be recycled.

The only thing that can be done with row upon return is destruction.

Definition at line 74 of file Bit_Matrix.cc.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::conversion().

                                             {
   const dimension_type new_rows_size = rows.size() + 1;
   if (rows.capacity() < new_rows_size) {
     // Reallocation will take place.
     std::vector<Bit_Row> new_rows;
     new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
     new_rows.insert(new_rows.end(), new_rows_size, Bit_Row());
     // Put the new row in place.
     dimension_type i = new_rows_size-1;
     new_rows[i].m_swap(row);
     // Steal the old rows.
     while (i-- > 0) {
       new_rows[i].m_swap(rows[i]);
     }
     // Put the new rows into place.
     using std::swap;
     swap(rows, new_rows);
   }
   else {
     // Reallocation will NOT take place: append an empty row
     // and swap it with the new row.
     rows.insert(rows.end(), Bit_Row())->m_swap(row);
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Bit_Matrix::ascii_dump ( ) const

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

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

Writes to s an ASCII representation of *this.

Definition at line 173 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::Implementation::BD_Shapes::separator.

                                              {
   const Bit_Matrix& x = *this;
   const char separator = ' ';
   s << num_rows() << separator << 'x' << separator
     << num_columns() << "\n";
   for (dimension_type i = 0; i < num_rows(); ++i) {
     for (dimension_type j = 0; j < num_columns(); ++j) {
       s << x[i][j] << separator;
     }
     s << "\n";
   }
 }

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

Definition at line 189 of file Bit_Matrix.cc.

References clear().

                                        {
   Bit_Matrix& x = *this;
   dimension_type nrows;
   dimension_type ncols;
   std::string str;
   if (!(s >> nrows)) {
     return false;
   }
   if (!(s >> str) || str != "x") {
     return false;
   }
   if (!(s >> ncols)) {
     return false;
   }
   resize(nrows, ncols);
 
   for (dimension_type i = 0; i < num_rows(); ++i) {
     for (dimension_type j = 0; j < num_columns(); ++j) {
       int bit;
       if (!(s >> bit)) {
         return false;
       }
       if (bit != 0) {
         x[i].set(j);
       }
       else {
         x[i].clear(j);
       }
     }
   }
   // Check invariants.
   PPL_ASSERT(OK());
   return true;
 }

bool Parma_Polyhedra_Library::Bit_Matrix::check_sorted ( ) const

Checks whether *this is sorted. It does NOT check for duplicates.

Definition at line 263 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::compare().

Referenced by sorted_contains().

                                   {
   const Bit_Matrix& x = *this;
   for (dimension_type i = num_rows(); i-- > 1; ) {
     if (compare(x[i-1], x[i]) > 0) {
       return false;
     }
   }
   return true;
 }

void Parma_Polyhedra_Library::Bit_Matrix::clear ( )

inline

Clears the matrix deallocating all its rows.

Definition at line 109 of file Bit_Matrix_inlines.hh.

References row_size, rows, and Parma_Polyhedra_Library::swap().

Referenced by ascii_load(), Parma_Polyhedra_Library::BD_Shape< T >::shortest_path_reduction_assign(), Parma_Polyhedra_Library::Polyhedron::update_sat_c(), and Parma_Polyhedra_Library::Polyhedron::update_sat_g().

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

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

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

Definition at line 225 of file Bit_Matrix.cc.

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();
   }
   return n;
 }

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

inline

Swaps *this with y.

Definition at line 81 of file Bit_Matrix_inlines.hh.

References row_size, rows, and Parma_Polyhedra_Library::swap().

Referenced by resize(), and swap().

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

dimension_type Parma_Polyhedra_Library::Bit_Matrix::max_num_rows ( )

inlinestatic

Returns the maximum number of rows of a Bit_Matrix.

Definition at line 39 of file Bit_Matrix_inlines.hh.

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

dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_columns ( ) const

inline

Returns the number of columns of *this.

Definition at line 99 of file Bit_Matrix_inlines.hh.

References row_size.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::conversion(), operator==(), Parma_Polyhedra_Library::Polyhedron::simplify(), and transpose_assign().

                               {
   return row_size;
 }

dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_rows ( ) const

inline

Returns the number of rows of *this.

Definition at line 104 of file Bit_Matrix_inlines.hh.

References rows.

Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::conversion(), operator==(), Parma_Polyhedra_Library::Linear_System< Row >::sort_and_remove_with_sat(), and transpose_assign().

                            {
   return rows.size();
 }

bool Parma_Polyhedra_Library::Bit_Matrix::OK ( ) const

Checks if all the invariants are satisfied.

Definition at line 234 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::Bit_Row::last(), and Parma_Polyhedra_Library::Bit_Row::OK().

Referenced by operator=(), remove_trailing_columns(), and remove_trailing_rows().

                         {
 #ifndef NDEBUG
   using std::endl;
   using std::cerr;
 #endif
 
   const Bit_Matrix& x = *this;
   for (dimension_type i = num_rows(); i-- > 0; ) {
     const Bit_Row& row = x[i];
     if (!row.OK()) {
       return false;
     }
     else if (row.last() != C_Integer<unsigned long>::max
              && row.last() >= row_size) {
 #ifndef NDEBUG
       cerr << "Bit_Matrix[" << i << "] is a row with too many bits!"
            << endl
            << "(row_size == " << row_size
            << ", row.last() == " << row.last() << ")"
            << endl;
 #endif
       return false;
     }
   }
   return true;
 }

PPL::Bit_Matrix & Parma_Polyhedra_Library::Bit_Matrix::operator= ( const Bit_Matrix & y )

Assignment operator.

Definition at line 36 of file Bit_Matrix.cc.

References OK(), row_size, and rows.

                                             {
   rows = y.rows;
   row_size = y.row_size;
   PPL_ASSERT(OK());
   return *this;
 }

Bit_Row & Parma_Polyhedra_Library::Bit_Matrix::operator[] ( dimension_type k )

inline

Subscript operator.

Definition at line 87 of file Bit_Matrix_inlines.hh.

References rows.

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

const Bit_Row & Parma_Polyhedra_Library::Bit_Matrix::operator[] ( dimension_type k ) const

inline

Constant subscript operator.

Definition at line 93 of file Bit_Matrix_inlines.hh.

References rows.

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

void Parma_Polyhedra_Library::Bit_Matrix::print ( ) const

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

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

inline

Removes the last n columns.

The last n columns of the matrix are all made of zeros. If such an assumption is not met, the behavior is undefined.

Definition at line 72 of file Bit_Matrix_inlines.hh.

References OK(), and row_size.

Referenced by Parma_Polyhedra_Library::Polyhedron::conversion().

                                                           {
   // The number of columns to be erased cannot be greater
   // than the actual number of the columns of the matrix.
   PPL_ASSERT(n <= row_size);
   row_size -= n;
   PPL_ASSERT(OK());
 }

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

inline

Removes the last n rows.

Definition at line 61 of file Bit_Matrix_inlines.hh.

References OK(), and rows.

Referenced by Parma_Polyhedra_Library::Polyhedron::conversion(), Parma_Polyhedra_Library::Polyhedron::select_H79_constraints(), Parma_Polyhedra_Library::Polyhedron::simplify(), and Parma_Polyhedra_Library::Linear_System< Row >::sort_and_remove_with_sat().

                                                        {
   // The number of rows to be erased cannot be greater
   // than the actual number of the rows of the matrix.
   PPL_ASSERT(n <= rows.size());
   if (n != 0) {
     rows.resize(rows.size() - n);
   }
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Bit_Matrix::resize	(	dimension_type	new_n_rows,
		dimension_type	new_n_columns
	)

Resizes the matrix copying the old contents.

Definition at line 132 of file Bit_Matrix.cc.

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

Referenced by Parma_Polyhedra_Library::Polyhedron::add_and_minimize(), Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::update_sat_c(), and Parma_Polyhedra_Library::Polyhedron::update_sat_g().

                                                       {
   PPL_ASSERT(OK());
   const dimension_type old_num_rows = num_rows();
   if (new_n_columns < row_size) {
     const dimension_type num_preserved_rows
       = std::min(old_num_rows, new_n_rows);
     Bit_Matrix& x = *this;
     for (dimension_type i = num_preserved_rows; i-- > 0; ) {
       x[i].clear_from(new_n_columns);
     }
   }
   row_size = new_n_columns;
   if (new_n_rows > old_num_rows) {
     if (rows.capacity() < new_n_rows) {
       // Reallocation will take place.
       std::vector<Bit_Row> new_rows;
       new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
       new_rows.insert(new_rows.end(), new_n_rows, Bit_Row());
       // Steal the old rows.
       for (dimension_type i = old_num_rows; 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(), new_n_rows - old_num_rows, Bit_Row());
     }
   }
   else if (new_n_rows < old_num_rows) {
     // Drop some rows.
     rows.resize(new_n_rows);
   }
 
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Bit_Matrix::sort_rows ( )

Sorts the rows and removes duplicates.

Definition at line 44 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::Implementation::indirect_sort_and_unique().

Referenced by Parma_Polyhedra_Library::Polyhedron::select_H79_constraints().

                          {
   const dimension_type num_elems = rows.size();
   if (num_elems < 2) {
     return;
   }
   // Build the function objects implementing indirect sort comparison,
   // indirect unique comparison and indirect swap operation.
   using namespace Implementation;
   typedef std::vector<Bit_Row> Cont;
   typedef Indirect_Sort_Compare<Cont, Bit_Row_Less_Than> Sort_Compare;
   typedef Indirect_Unique_Compare<Cont> Unique_Compare;
   typedef Indirect_Swapper<Cont> Swapper;
   const dimension_type num_duplicates
     = indirect_sort_and_unique(num_elems,
                                Sort_Compare(rows),
                                Unique_Compare(rows),
                                Swapper(rows));
 
   if (num_duplicates > 0) {
     typedef Cont::iterator Iter;
     typedef std::iterator_traits<Iter>::difference_type diff_t;
     Iter last = rows.end();
     Iter first = last - static_cast<diff_t>(num_duplicates);
     rows.erase(first, last);
   }
 
   PPL_ASSERT(OK());
 }

bool Parma_Polyhedra_Library::Bit_Matrix::sorted_contains ( const Bit_Row & row ) const

inline

Looks for row in *this, which is assumed to be sorted.

Returns: true if row belongs to *this, false otherwise.

Parameters

row	The row that will be searched for in the matrix.

Given a sorted bit matrix (this ensures better efficiency), tells whether it contains the given row.

Definition at line 128 of file Bit_Matrix_inlines.hh.

References check_sorted(), and rows.

Referenced by Parma_Polyhedra_Library::Polyhedron::select_H79_constraints().

                                                     {
   PPL_ASSERT(check_sorted());
   return std::binary_search(rows.begin(), rows.end(), row,
                             Bit_Row_Less_Than());
 }

memory_size_type Parma_Polyhedra_Library::Bit_Matrix::total_memory_in_bytes ( ) const

inline

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

Definition at line 117 of file Bit_Matrix_inlines.hh.

References external_memory_in_bytes().

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

void Parma_Polyhedra_Library::Bit_Matrix::transpose ( )

Transposes the matrix.

Definition at line 101 of file Bit_Matrix.cc.

                          {
   const Bit_Matrix& x = *this;
   const dimension_type nrows = num_rows();
   const dimension_type ncols = num_columns();
   Bit_Matrix tmp(ncols, nrows);
   for (dimension_type i = nrows; i-- > 0; ) {
     for (unsigned long j = x[i].last();
          j != C_Integer<unsigned long>::max; j = x[i].prev(j)) {
       tmp[j].set(i);
     }
   }
   m_swap(tmp);
   PPL_ASSERT(OK());
 }

void Parma_Polyhedra_Library::Bit_Matrix::transpose_assign ( const Bit_Matrix & y )

Makes *this a transposed copy of y.

Definition at line 117 of file Bit_Matrix.cc.

References num_columns(), and num_rows().

                                                    {
   const dimension_type y_num_rows = y.num_rows();
   const dimension_type y_num_columns = y.num_columns();
   Bit_Matrix tmp(y_num_columns, y_num_rows);
   for (dimension_type i = y_num_rows; i-- > 0; ) {
     for (unsigned long j = y[i].last();
          j != C_Integer<unsigned long>::max; j = y[i].prev(j)) {
       tmp[j].set(i);
     }
   }
   m_swap(tmp);
   PPL_ASSERT(OK());
 }

Friends And Related Function Documentation

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

                                                      {
   return !(x == y);
 }

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

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

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

References num_columns(), and num_rows().

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

template<typename Row >

friend class Parma_Polyhedra_Library::Linear_System

friend

Definition at line 166 of file Bit_Matrix_defs.hh.

void swap	(	Bit_Matrix &	x,
		Bit_Matrix &	y
	)

void swap	(	Bit_Matrix &	x,
		Bit_Matrix &	y
	)

References m_swap().

                                    {
   x.m_swap(y);
 }

Member Data Documentation

dimension_type Parma_Polyhedra_Library::Bit_Matrix::row_size

private

Size of the initialized part of each row.

Definition at line 157 of file Bit_Matrix_defs.hh.

Referenced by clear(), m_swap(), num_columns(), operator=(), and remove_trailing_columns().

std::vector<Bit_Row> Parma_Polyhedra_Library::Bit_Matrix::rows

private

Contains the rows of the matrix.

Definition at line 154 of file Bit_Matrix_defs.hh.

Referenced by clear(), m_swap(), num_rows(), operator=(), operator[](), remove_trailing_rows(), and sorted_contains().

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

Classes

Public Member Functions

Static Public Member Functions

Private Attributes

Friends

Related Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation