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

A matrix of bits. More...

#include <Bit_Matrix.defs.hh>

List of all members.

Public Member Functions

 Bit_Matrix ()
 Default constructor.
 Bit_Matrix (dimension_type n_rows, dimension_type n_columns)
 Construct a bit matrix with n_rows rows and n_columns columns.
 Bit_Matrix (const Bit_Matrix &y)
 Copy-constructor.
 ~Bit_Matrix ()
 Destructor.
Bit_Matrixoperator= (const Bit_Matrix &y)
 Assignment operator.
void swap (Bit_Matrix &y)
 Swaps *this with y.
Bit_Rowoperator[] (dimension_type k)
 Subscript operator.
const Bit_Rowoperator[] (dimension_type k) const
 Constant subscript operator.
void clear ()
 Clears the matrix deallocating all its rows.
void transpose ()
 Transposes the matrix.
void transpose_assign (const Bit_Matrix &y)
 Makes *this a transposed copy of y.
dimension_type num_columns () const
 Returns the number of columns of *this.
dimension_type num_rows () const
 Returns the number of rows of *this.
void sort_rows ()
 Sorts the rows and removes duplicates.
bool sorted_contains (const Bit_Row &row) const
 Looks for row in *this, which is assumed to be sorted.
void add_row (const Bit_Row &row)
 Adds row to *this.
void rows_erase_to_end (dimension_type first_to_erase)
 Erases the rows from the first_to_erase -th to the last one.
void columns_erase_to_end (dimension_type first_to_erase)
 Erases the columns from the first_to_erase -th to the last one.
void resize (dimension_type new_n_rows, dimension_type new_n_columns)
 Resizes the matrix copying the old contents.
bool OK () const
 Checks if all the invariants are satisfied.
void ascii_dump () const
 Writes to std::cerr an ASCII representation of *this.
void ascii_dump (std::ostream &s) const
 Writes to s an ASCII representation of *this.
void print () const
 Prints *this to std::cerr using operator<<.
bool ascii_load (std::istream &s)
 Loads from s an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets *this accordingly. Returns true if successful, false otherwise.
memory_size_type total_memory_in_bytes () const
 Returns the total size in bytes of the memory occupied by *this.
memory_size_type external_memory_in_bytes () const
 Returns the size in bytes of the memory managed by *this.
bool check_sorted () const
 Checks whether *this is sorted. It does NOT check for duplicates.

Static Public Member Functions

static dimension_type max_num_rows ()
 Returns the maximum number of rows of a Bit_Matrix.

Private Attributes

std::vector< Bit_Rowrows
 Contains the rows of the matrix.
dimension_type row_size
 Size of the initialized part of each row.

Friends

void Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat (Bit_Matrix &sat)

Related Functions

(Note that these are not member functions.)

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

Classes

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


Detailed Description

A matrix of bits.

Definition at line 36 of file Bit_Matrix.defs.hh.


Constructor & Destructor Documentation

Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix (  )  [inline]

Default constructor.

Definition at line 32 of file Bit_Matrix.inlines.hh.

00033   : rows(),
00034     row_size(0) {
00035 }

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 43 of file Bit_Matrix.inlines.hh.

00045   : rows(n_rows),
00046     row_size(n_columns) {
00047 }

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

Copy-constructor.

Definition at line 50 of file Bit_Matrix.inlines.hh.

00051   : rows(y.rows),
00052     row_size(y.row_size) {
00053 }

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

Destructor.

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

00056                         {
00057 }


Member Function Documentation

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.

00036                                            {
00037   rows = y.rows;
00038   row_size = y.row_size;
00039   assert(OK());
00040   return *this;
00041 }

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

Swaps *this with y.

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

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

Referenced by clear(), resize(), swap(), transpose(), and transpose_assign().

00079                               {
00080   std::swap(row_size, y.row_size);
00081   std::swap(rows, y.rows);
00082 }

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

Subscript operator.

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

References rows.

00085                                              {
00086   assert(k < rows.size());
00087   return rows[k];
00088 }

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

Constant subscript operator.

Definition at line 91 of file Bit_Matrix.inlines.hh.

References rows.

00091                                                    {
00092   assert(k < rows.size());
00093   return rows[k];
00094 }

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

Clears the matrix deallocating all its rows.

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

References row_size, rows, and swap().

Referenced by ascii_load(), Parma_Polyhedra_Library::Polyhedron::set_empty(), 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().

00107                   {
00108   // Clear `rows' and minimize its capacity.
00109   std::vector<Bit_Row>().swap(rows);
00110   row_size = 0;
00111 }

void Parma_Polyhedra_Library::Bit_Matrix::transpose (  ) 

Transposes the matrix.

Definition at line 81 of file Bit_Matrix.cc.

References num_columns(), num_rows(), OK(), and swap().

00081                          {
00082   const Bit_Matrix& x = *this;
00083   const dimension_type nrows = num_rows();
00084   const dimension_type ncols = num_columns();
00085   Bit_Matrix tmp(ncols, nrows);
00086   for (dimension_type i = nrows; i-- > 0; )
00087     for (unsigned long j = x[i].last(); j != ULONG_MAX; j = x[i].prev(j))
00088       tmp[j].set(i);
00089   swap(tmp);
00090   assert(OK());
00091 }

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

dimension_type Parma_Polyhedra_Library::Bit_Matrix::max_num_rows (  )  [inline, static]

Returns the maximum number of rows of a Bit_Matrix.

Definition at line 38 of file Bit_Matrix.inlines.hh.

Referenced by add_row(), and resize().

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

dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_columns (  )  const [inline]

dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_rows (  )  const [inline]

void Parma_Polyhedra_Library::Bit_Matrix::sort_rows (  ) 

Sorts the rows and removes duplicates.

Definition at line 44 of file Bit_Matrix.cc.

References OK(), and rows.

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

00044                          {
00045   typedef std::vector<Bit_Row>::iterator Iter;
00046   // Sorting without removing duplicates.
00047   Iter first = rows.begin();
00048   Iter last = rows.end();
00049   swapping_sort(first, last, Bit_Row_Less_Than());
00050   // Moving all the duplicate elements at the end of the vector.
00051   Iter new_last = swapping_unique(first, last);
00052   // Removing duplicates.
00053   rows.erase(new_last, last);
00054   assert(OK());
00055 }

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 125 of file Bit_Matrix.inlines.hh.

References check_sorted(), and rows.

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

00125                                                     {
00126   assert(check_sorted());
00127   return std::binary_search(rows.begin(), rows.end(), row,
00128                             Bit_Row_Less_Than());
00129 }

void Parma_Polyhedra_Library::Bit_Matrix::add_row ( const Bit_Row row  ) 

Adds row to *this.

Definition at line 58 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), max_num_rows(), OK(), rows, Parma_Polyhedra_Library::swap(), and Parma_Polyhedra_Library::Bit_Row::swap().

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

00058                                          {
00059   const dimension_type new_rows_size = rows.size() + 1;
00060   if (rows.capacity() < new_rows_size) {
00061     // Reallocation will take place.
00062     std::vector<Bit_Row> new_rows;
00063     new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
00064     new_rows.insert(new_rows.end(), new_rows_size, Bit_Row());
00065     // Put the new row in place.
00066     dimension_type i = new_rows_size-1;
00067     new_rows[i] = row;
00068     // Steal the old rows.
00069     while (i-- > 0)
00070       new_rows[i].swap(rows[i]);
00071     // Put the new rows into place.
00072     std::swap(rows, new_rows);
00073   }
00074   else
00075     // Reallocation will NOT take place: append a new empty row.
00076     rows.push_back(row);
00077   assert(OK());
00078 }

void Parma_Polyhedra_Library::Bit_Matrix::rows_erase_to_end ( dimension_type  first_to_erase  )  [inline]

Erases the rows from the first_to_erase -th to the last one.

Definition at line 60 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::sort_and_remove_with_sat().

00060                                                                  {
00061   // The first row to be erased cannot be greater
00062   // than the actual number of the rows of the matrix.
00063   assert(first_to_erase <= rows.size());
00064   if (first_to_erase < rows.size())
00065     rows.erase(rows.begin() + first_to_erase, rows.end());
00066   assert(OK());
00067 }

void Parma_Polyhedra_Library::Bit_Matrix::columns_erase_to_end ( dimension_type  first_to_erase  )  [inline]

Erases the columns from the first_to_erase -th to the last one.

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

References OK(), and row_size.

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

00070                                                                     {
00071   // The first column to be erased cannot be greater
00072   // than the actual number of the columns of the matrix.
00073   assert(first_to_erase <= row_size);
00074   row_size = first_to_erase;
00075   assert(OK());
00076 }

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 106 of file Bit_Matrix.cc.

References Parma_Polyhedra_Library::compute_capacity(), max_num_rows(), num_rows(), OK(), row_size, rows, Parma_Polyhedra_Library::swap(), and swap().

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

00107                                                      {
00108   assert(OK());
00109   const dimension_type old_num_rows = num_rows();
00110   if (new_n_columns < row_size) {
00111     const dimension_type num_preserved_rows
00112       = std::min(old_num_rows, new_n_rows);
00113     Bit_Matrix& x = *this;
00114     for (dimension_type i = num_preserved_rows; i-- > 0; )
00115       x[i].clear_from(new_n_columns);
00116   }
00117   row_size = new_n_columns;
00118   if (new_n_rows > old_num_rows) {
00119     if (rows.capacity() < new_n_rows) {
00120       // Reallocation will take place.
00121       std::vector<Bit_Row> new_rows;
00122       new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
00123       new_rows.insert(new_rows.end(), new_n_rows, Bit_Row());
00124       // Steal the old rows.
00125       for (dimension_type i = old_num_rows; i-- > 0; )
00126         new_rows[i].swap(rows[i]);
00127       // Put the new vector into place.
00128       std::swap(rows, new_rows);
00129     }
00130     else
00131       // Reallocation will NOT take place.
00132       rows.insert(rows.end(), new_n_rows - old_num_rows, Bit_Row());
00133   }
00134   else if (new_n_rows < old_num_rows)
00135     // Drop some rows.
00136     rows.erase(rows.begin() + new_n_rows, rows.end());
00137 
00138   assert(OK());
00139 }

bool Parma_Polyhedra_Library::Bit_Matrix::OK (  )  const

Checks if all the invariants are satisfied.

Definition at line 195 of file Bit_Matrix.cc.

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

Referenced by add_row(), ascii_load(), columns_erase_to_end(), Parma_Polyhedra_Library::Polyhedron::OK(), operator=(), resize(), rows_erase_to_end(), sort_rows(), transpose(), and transpose_assign().

00195                         {
00196 #ifndef NDEBUG
00197   using std::endl;
00198   using std::cerr;
00199 #endif
00200 
00201   const Bit_Matrix& x = *this;
00202   for (dimension_type i = num_rows(); i-- > 1; ) {
00203     const Bit_Row& row = x[i];
00204     if (!row.OK())
00205       return false;
00206     else if (row.last() != ULONG_MAX && row.last() >= row_size) {
00207 #ifndef NDEBUG
00208       cerr << "Bit_Matrix[" << i << "] is a row with too many bits!"
00209            << endl
00210            << "(row_size == " << row_size
00211            << ", row.last() == " << row.last() << ")"
00212            << endl;
00213 #endif
00214       return false;
00215     }
00216   }
00217   return true;
00218 }

void Parma_Polyhedra_Library::Bit_Matrix::ascii_dump (  )  const

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

Referenced by Parma_Polyhedra_Library::Polyhedron::ascii_dump(), and Parma_Polyhedra_Library::BD_Shape< T >::ascii_dump().

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

Writes to s an ASCII representation of *this.

Definition at line 142 of file Bit_Matrix.cc.

References num_columns(), and num_rows().

00142                                              {
00143   const Bit_Matrix& x = *this;
00144   const char separator = ' ';
00145   s << num_rows() << separator << 'x' << separator
00146     << num_columns() << "\n";
00147   for (dimension_type i = 0; i < num_rows(); ++i) {
00148     for (dimension_type j = 0; j < num_columns(); ++j)
00149       s << x[i][j] << separator;
00150     s << "\n";
00151   }
00152 }

void Parma_Polyhedra_Library::Bit_Matrix::print (  )  const

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

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 157 of file Bit_Matrix.cc.

References clear(), num_columns(), num_rows(), OK(), and resize().

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

00157                                        {
00158   Bit_Matrix& x = *this;
00159   dimension_type nrows;
00160   dimension_type ncols;
00161   std::string str;
00162   if (!(s >> nrows))
00163     return false;
00164   if (!(s >> str))
00165     return false;
00166   if (!(s >> ncols))
00167     return false;
00168   resize(nrows, ncols);
00169 
00170   for (dimension_type i = 0; i < num_rows(); ++i)
00171     for (dimension_type j = 0; j < num_columns(); ++j) {
00172       int bit;
00173       if (!(s >> bit))
00174         return false;
00175       if (bit)
00176         x[i].set(j);
00177       else
00178         x[i].clear(j);
00179     }
00180 
00181   // Check invariants.
00182   assert(OK());
00183   return true;
00184 }

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 114 of file Bit_Matrix.inlines.hh.

References external_memory_in_bytes().

00114                                         {
00115   return sizeof(*this) + external_memory_in_bytes();
00116 }

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 187 of file Bit_Matrix.cc.

References num_rows(), and rows.

Referenced by Parma_Polyhedra_Library::Polyhedron::external_memory_in_bytes(), Parma_Polyhedra_Library::BD_Shape< T >::external_memory_in_bytes(), and total_memory_in_bytes().

00187                                               {
00188   memory_size_type n = rows.capacity() * sizeof(Row);
00189   for (dimension_type i = num_rows(); i-- > 0; )
00190     n += rows[i].external_memory_in_bytes();
00191   return n;
00192 }

bool Parma_Polyhedra_Library::Bit_Matrix::check_sorted (  )  const

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

Definition at line 222 of file Bit_Matrix.cc.

References num_rows().

Referenced by sorted_contains().

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


Friends And Related Function Documentation

void Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat ( Bit_Matrix sat  )  [friend]

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

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

Definition at line 233 of file Bit_Matrix.cc.

References num_columns(), and num_rows().

00233                                                         {
00234   const dimension_type x_num_rows = x.num_rows();
00235   if (x_num_rows != y.num_rows()
00236       || x.num_columns() != y.num_columns())
00237     return false;
00238   for (dimension_type i = x_num_rows; i-- > 0; )
00239     if (x[i] != y[i])
00240       return false;
00241   return true;
00242 }

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

Returns true if and only if x and y are not equal.

Definition at line 133 of file Bit_Matrix.inlines.hh.

00133                                                      {
00134   return !(x == y);
00135 }

Specializes std::swap.

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

References swap().

00145                                            {
00146   x.swap(y);
00147 }


Member Data Documentation

Size of the initialized part of each row.

Definition at line 136 of file Bit_Matrix.defs.hh.

Referenced by clear(), columns_erase_to_end(), num_columns(), OK(), operator=(), resize(), and swap().


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

Generated on Sat Oct 11 10:41:06 2008 for PPL by  doxygen 1.5.6