#include <Bit_Matrix.defs.hh>
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_Matrix & | operator= (const Bit_Matrix &y) |
Assignment operator. | |
void | swap (Bit_Matrix &y) |
Swaps *this with y . | |
Bit_Row & | operator[] (dimension_type k) |
Subscript operator. | |
const Bit_Row & | operator[] (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_Row > | rows |
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... |
Definition at line 36 of file Bit_Matrix.defs.hh.
Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix | ( | ) | [inline] |
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.
Parma_Polyhedra_Library::Bit_Matrix::Bit_Matrix | ( | const Bit_Matrix & | y | ) | [inline] |
Parma_Polyhedra_Library::Bit_Matrix::~Bit_Matrix | ( | ) | [inline] |
PPL::Bit_Matrix & Parma_Polyhedra_Library::Bit_Matrix::operator= | ( | const Bit_Matrix & | y | ) |
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().
Bit_Row & Parma_Polyhedra_Library::Bit_Matrix::operator[] | ( | dimension_type | k | ) | [inline] |
const Bit_Row & Parma_Polyhedra_Library::Bit_Matrix::operator[] | ( | dimension_type | k | ) | const [inline] |
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 | ) |
Makes *this
a transposed copy of y
.
Definition at line 94 of file Bit_Matrix.cc.
References num_columns(), num_rows(), OK(), and swap().
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::minimize(), 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::Polyhedron::process_pending_constraints(), Parma_Polyhedra_Library::Polyhedron::process_pending_generators(), Parma_Polyhedra_Library::Polyhedron::strongly_minimize_constraints(), and Parma_Polyhedra_Library::Polyhedron::strongly_minimize_generators().
00094 { 00095 const dimension_type y_nrows = y.num_rows(); 00096 const dimension_type y_ncols = y.num_columns(); 00097 Bit_Matrix tmp(y_ncols, y_nrows); 00098 for (dimension_type i = y_nrows; i-- > 0; ) 00099 for (unsigned long j = y[i].last(); j != ULONG_MAX; j = y[i].prev(j)) 00100 tmp[j].set(i); 00101 swap(tmp); 00102 assert(OK()); 00103 }
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().
dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_columns | ( | ) | const [inline] |
Returns the number of columns of *this
.
Definition at line 97 of file Bit_Matrix.inlines.hh.
References row_size.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), ascii_dump(), ascii_load(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), drop_redundant_inequalities(), Parma_Polyhedra_Library::Polyhedron::OK(), operator==(), Parma_Polyhedra_Library::Polyhedron::simplify(), transpose(), and transpose_assign().
00097 { 00098 return row_size; 00099 }
dimension_type Parma_Polyhedra_Library::Bit_Matrix::num_rows | ( | ) | const [inline] |
Returns the number of rows of *this
.
Definition at line 102 of file Bit_Matrix.inlines.hh.
References rows.
Referenced by Parma_Polyhedra_Library::Polyhedron::add_space_dimensions(), ascii_dump(), ascii_load(), check_sorted(), Parma_Polyhedra_Library::Polyhedron::concatenate_assign(), Parma_Polyhedra_Library::Polyhedron::conversion(), external_memory_in_bytes(), Parma_Polyhedra_Library::Polyhedron::OK(), OK(), operator==(), resize(), Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat(), transpose(), and transpose_assign().
00102 { 00103 return rows.size(); 00104 }
void Parma_Polyhedra_Library::Bit_Matrix::sort_rows | ( | ) |
Sorts the rows and removes duplicates.
Definition at line 44 of file Bit_Matrix.cc.
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.
true
if row
belongs to *this
, false otherwise.row | The row that will be searched for in the matrix. |
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.
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 }
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.
void swap | ( | Parma_Polyhedra_Library::Bit_Matrix & | x, | |
Parma_Polyhedra_Library::Bit_Matrix & | y | |||
) | [related] |
Specializes std::swap
.
Definition at line 144 of file Bit_Matrix.inlines.hh.
References swap().
00145 { 00146 x.swap(y); 00147 }
std::vector<Bit_Row> Parma_Polyhedra_Library::Bit_Matrix::rows [private] |
Contains the rows of the matrix.
Definition at line 133 of file Bit_Matrix.defs.hh.
Referenced by add_row(), clear(), external_memory_in_bytes(), num_rows(), operator=(), operator[](), resize(), rows_erase_to_end(), Parma_Polyhedra_Library::Linear_System::sort_and_remove_with_sat(), sort_rows(), sorted_contains(), and swap().
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().