00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <ppl-config.h>
00024
00025 #include "Bit_Matrix.defs.hh"
00026 #include "globals.defs.hh"
00027 #include <iostream>
00028 #include <string>
00029 #include <climits>
00030
00031 #include "swapping_sort.icc"
00032
00033 namespace PPL = Parma_Polyhedra_Library;
00034
00035 PPL::Bit_Matrix&
00036 PPL::Bit_Matrix::operator=(const Bit_Matrix& y){
00037 rows = y.rows;
00038 row_size = y.row_size;
00039 assert(OK());
00040 return *this;
00041 }
00042
00043 void
00044 PPL::Bit_Matrix::sort_rows() {
00045 typedef std::vector<Bit_Row>::iterator Iter;
00046
00047 Iter first = rows.begin();
00048 Iter last = rows.end();
00049 swapping_sort(first, last, Bit_Row_Less_Than());
00050
00051 Iter new_last = swapping_unique(first, last);
00052
00053 rows.erase(new_last, last);
00054 assert(OK());
00055 }
00056
00057 void
00058 PPL::Bit_Matrix::add_row(const Bit_Row& row) {
00059 const dimension_type new_rows_size = rows.size() + 1;
00060 if (rows.capacity() < new_rows_size) {
00061
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
00066 dimension_type i = new_rows_size-1;
00067 new_rows[i] = row;
00068
00069 while (i-- > 0)
00070 new_rows[i].swap(rows[i]);
00071
00072 std::swap(rows, new_rows);
00073 }
00074 else
00075
00076 rows.push_back(row);
00077 assert(OK());
00078 }
00079
00080 void
00081 PPL::Bit_Matrix::transpose() {
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 }
00092
00093 void
00094 PPL::Bit_Matrix::transpose_assign(const Bit_Matrix& y) {
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 }
00104
00105 void
00106 PPL::Bit_Matrix::resize(dimension_type new_n_rows,
00107 dimension_type new_n_columns) {
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
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
00125 for (dimension_type i = old_num_rows; i-- > 0; )
00126 new_rows[i].swap(rows[i]);
00127
00128 std::swap(rows, new_rows);
00129 }
00130 else
00131
00132 rows.insert(rows.end(), new_n_rows - old_num_rows, Bit_Row());
00133 }
00134 else if (new_n_rows < old_num_rows)
00135
00136 rows.erase(rows.begin() + new_n_rows, rows.end());
00137
00138 assert(OK());
00139 }
00140
00141 void
00142 PPL::Bit_Matrix::ascii_dump(std::ostream& s) const {
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 }
00153
00154 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Bit_Matrix)
00155
00156 bool
00157 PPL::Bit_Matrix::ascii_load(std::istream& s) {
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
00182 assert(OK());
00183 return true;
00184 }
00185
00186 PPL::memory_size_type
00187 PPL::Bit_Matrix::external_memory_in_bytes() const {
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 }
00193
00194 bool
00195 PPL::Bit_Matrix::OK() const {
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 }
00219
00220 #ifndef NDEBUG
00221 bool
00222 PPL::Bit_Matrix::check_sorted() const {
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 }
00229 #endif
00230
00232 bool
00233 PPL::operator==(const Bit_Matrix& x, const Bit_Matrix& y) {
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 }
00243