00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <config.h>
00024
00025 #include "Matrix.defs.hh"
00026 #include "Row.defs.hh"
00027 #include <algorithm>
00028 #include <iostream>
00029 #include <string>
00030
00031 namespace PPL = Parma_Polyhedra_Library;
00032
00033 PPL::Matrix::Matrix(const dimension_type n_rows,
00034 const dimension_type n_columns,
00035 Row::Flags row_flags)
00036 : rows((assert(n_rows <= max_num_rows()),
00037 n_rows)),
00038 row_size(n_columns),
00039 row_capacity(compute_capacity(n_columns, max_num_columns())) {
00040
00041 for (dimension_type i = 0; i < n_rows; ++i)
00042 rows[i].construct(n_columns, row_capacity, row_flags);
00043 assert(OK());
00044 }
00045
00046 void
00047 PPL::Matrix::add_zero_rows(const dimension_type n, Row::Flags row_flags) {
00048 assert(n > 0);
00049 assert(n <= max_num_rows() - num_rows());
00050 const dimension_type old_num_rows = rows.size();
00051 const dimension_type new_num_rows = old_num_rows + n;
00052
00053 if (rows.capacity() < new_num_rows) {
00054
00055 std::vector<Row> new_rows;
00056 new_rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
00057 new_rows.insert(new_rows.end(), new_num_rows, Row());
00058
00059 dimension_type i = new_num_rows;
00060 while (i-- > old_num_rows)
00061 new_rows[i].construct(row_size, row_capacity, row_flags);
00062
00063 ++i;
00064 while (i-- > 0)
00065 new_rows[i].swap(rows[i]);
00066
00067 std::swap(rows, new_rows);
00068 }
00069 else {
00070
00071 rows.insert(rows.end(), n, Row());
00072 for (dimension_type i = new_num_rows; i-- > old_num_rows; )
00073 rows[i].construct(row_size, row_capacity, row_flags);
00074 }
00075 }
00076
00077 void
00078 PPL::Matrix::add_zero_columns(const dimension_type n) {
00079 assert(n > 0);
00080 assert(n <= max_num_columns() - num_columns());
00081 const dimension_type num_rows = rows.size();
00082 const dimension_type new_num_columns = row_size + n;
00083
00084 if (new_num_columns <= row_capacity)
00085
00086 for (dimension_type i = num_rows; i-- > 0; )
00087 rows[i].expand_within_capacity(new_num_columns);
00088 else {
00089
00090
00091 const dimension_type new_row_capacity
00092 = compute_capacity(new_num_columns, max_num_columns());
00093 assert(new_row_capacity <= max_num_columns());
00094 for (dimension_type i = num_rows; i-- > 0; ) {
00095 Row new_row(rows[i], new_num_columns, new_row_capacity);
00096 std::swap(rows[i], new_row);
00097 }
00098 row_capacity = new_row_capacity;
00099 }
00100
00101 row_size = new_num_columns;
00102 }
00103
00104 void
00105 PPL::Matrix::add_zero_rows_and_columns(const dimension_type n,
00106 const dimension_type m,
00107 Row::Flags row_flags) {
00108 assert(n > 0);
00109 assert(n <= max_num_rows() - num_rows());
00110 assert(m > 0);
00111 assert(m <= max_num_columns() - num_columns());
00112 const dimension_type old_num_rows = rows.size();
00113 const dimension_type new_num_rows = old_num_rows + n;
00114 const dimension_type new_num_columns = row_size + m;
00115
00116 if (new_num_columns <= row_capacity) {
00117
00118 if (rows.capacity() < new_num_rows) {
00119
00120 std::vector<Row> new_rows;
00121 new_rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
00122 new_rows.insert(new_rows.end(), new_num_rows, Row());
00123
00124 dimension_type i = new_num_rows;
00125 while (i-- > old_num_rows)
00126 new_rows[i].construct(new_num_columns, row_capacity, row_flags);
00127
00128 ++i;
00129 while (i-- > 0) {
00130 rows[i].expand_within_capacity(new_num_columns);
00131 new_rows[i].swap(rows[i]);
00132 }
00133
00134 std::swap(rows, new_rows);
00135 }
00136 else {
00137
00138 rows.insert(rows.end(), n, Row());
00139
00140 dimension_type i = new_num_rows;
00141 while (i-- > old_num_rows)
00142 rows[i].construct(new_num_columns, row_capacity, row_flags);
00143
00144 ++i;
00145 while (i-- > 0)
00146 rows[i].expand_within_capacity(new_num_columns);
00147 }
00148 row_size = new_num_columns;
00149 }
00150 else {
00151
00152 Matrix new_matrix;
00153 new_matrix.rows.reserve(compute_capacity(new_num_rows, max_num_rows()));
00154 new_matrix.rows.insert(new_matrix.rows.end(), new_num_rows, Row());
00155
00156 new_matrix.row_size = new_num_columns;
00157 new_matrix.row_capacity = compute_capacity(new_num_columns,
00158 max_num_columns());
00159 dimension_type i = new_num_rows;
00160 while (i-- > old_num_rows)
00161 new_matrix.rows[i].construct(new_matrix.row_size,
00162 new_matrix.row_capacity,
00163 row_flags);
00164
00165 ++i;
00166 while (i-- > 0) {
00167 Row new_row(rows[i],
00168 new_matrix.row_size,
00169 new_matrix.row_capacity);
00170 std::swap(new_matrix.rows[i], new_row);
00171 }
00172
00173 swap(new_matrix);
00174 }
00175 }
00176
00177 void
00178 PPL::Matrix::add_recycled_row(Row& y) {
00179
00180
00181 assert(y.OK(row_size, row_capacity));
00182 const dimension_type new_rows_size = rows.size() + 1;
00183 if (rows.capacity() < new_rows_size) {
00184
00185 std::vector<Row> new_rows;
00186 new_rows.reserve(compute_capacity(new_rows_size, max_num_rows()));
00187 new_rows.insert(new_rows.end(), new_rows_size, Row());
00188
00189 dimension_type i = new_rows_size-1;
00190 std::swap(new_rows[i], y);
00191
00192 while (i-- > 0)
00193 new_rows[i].swap(rows[i]);
00194
00195 std::swap(rows, new_rows);
00196 }
00197 else
00198
00199
00200
00201 std::swap(*rows.insert(rows.end(), Row()), y);
00202
00203 assert(OK());
00204 }
00205
00206 void
00207 PPL::Matrix::resize_no_copy(const dimension_type new_n_rows,
00208 const dimension_type new_n_columns,
00209 Row::Flags row_flags) {
00210 dimension_type old_n_rows = rows.size();
00211
00212
00213
00214
00215
00216 if (new_n_rows > old_n_rows) {
00217 if (new_n_columns <= row_capacity) {
00218
00219 if (rows.capacity() < new_n_rows) {
00220
00221 std::vector<Row> new_rows;
00222 new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
00223 new_rows.insert(new_rows.end(), new_n_rows, Row());
00224
00225
00226 dimension_type i = new_n_rows;
00227 while (i-- > old_n_rows)
00228 new_rows[i].construct(new_n_columns, row_capacity, row_flags);
00229
00230 ++i;
00231 while (i-- > 0)
00232 new_rows[i].swap(rows[i]);
00233
00234 std::swap(rows, new_rows);
00235 }
00236 else {
00237
00238 rows.insert(rows.end(), new_n_rows - old_n_rows, Row());
00239
00240
00241 for (dimension_type i = new_n_rows; i-- > old_n_rows; )
00242 rows[i].construct(new_n_columns, row_capacity, row_flags);
00243 }
00244 }
00245 else {
00246
00247 Matrix new_matrix(new_n_rows, new_n_columns, row_flags);
00248 swap(new_matrix);
00249 return;
00250 }
00251 }
00252 else if (new_n_rows < old_n_rows) {
00253
00254 rows.erase(rows.begin() + new_n_rows, rows.end());
00255 old_n_rows = new_n_rows;
00256 }
00257
00258 if (new_n_columns != row_size) {
00259 if (new_n_columns < row_size) {
00260
00261 for (dimension_type i = old_n_rows; i-- > 0; )
00262 rows[i].shrink(new_n_columns);
00263 }
00264 else
00265
00266 if (new_n_columns <= row_capacity)
00267
00268 for (dimension_type i = old_n_rows; i-- > 0; )
00269 rows[i].expand_within_capacity(new_n_columns);
00270 else {
00271
00272
00273 const dimension_type new_row_capacity
00274 = compute_capacity(new_n_columns, max_num_columns());
00275 for (dimension_type i = old_n_rows; i-- > 0; ) {
00276 Row new_row(new_n_columns, new_row_capacity, row_flags);
00277 std::swap(rows[i], new_row);
00278 }
00279 row_capacity = new_row_capacity;
00280 }
00281
00282 row_size = new_n_columns;
00283 }
00284 }
00285
00286 void
00287 PPL::Matrix::ascii_dump(std::ostream& s) const {
00288 const Matrix& x = *this;
00289 dimension_type x_num_rows = x.num_rows();
00290 dimension_type x_num_columns = x.num_columns();
00291 s << x_num_rows << " x " << x_num_columns << "\n";
00292 for (dimension_type i = 0; i < x_num_rows; ++i)
00293 x[i].ascii_dump(s);
00294 }
00295
00296 PPL_OUTPUT_DEFINITIONS_ASCII_ONLY(Matrix);
00297
00298 bool
00299 PPL::Matrix::ascii_load(std::istream& s) {
00300 Matrix& x = *this;
00301 std::string str;
00302 dimension_type x_num_rows;
00303 dimension_type x_num_cols;
00304 if (!(s >> x_num_rows))
00305 return false;
00306 if (!(s >> str) || (str.compare("x") != 0))
00307 return false;
00308 if (!(s >> x_num_cols))
00309 return false;
00310
00311 resize_no_copy(x_num_rows, x_num_cols, Row::Flags());
00312
00313 for (dimension_type row = 0; row < x_num_rows; ++row)
00314 if (!x[row].ascii_load(s))
00315 return false;
00316
00317
00318 assert(OK());
00319 return true;
00320 }
00321
00322 void
00323 PPL::Matrix::swap_columns(const dimension_type i, const dimension_type j) {
00324 assert(i != j && i < num_columns() && j < num_columns());
00325 for (dimension_type k = num_rows(); k-- > 0; ) {
00326 Row& rows_k = rows[k];
00327 std::swap(rows_k[i], rows_k[j]);
00328 }
00329 }
00330
00331 void
00332 PPL::Matrix::remove_trailing_columns(const dimension_type n) {
00333 assert(n > 0);
00334 assert(n <= row_size);
00335 row_size -= n;
00336 for (dimension_type i = num_rows(); i-- > 0; )
00337 rows[i].shrink(row_size);
00338 }
00339
00340 void
00341 PPL::Matrix::permute_columns(const std::vector<dimension_type>& cycles) {
00342 TEMP_INTEGER(tmp);
00343 const dimension_type n = cycles.size();
00344 assert(cycles[n - 1] == 0);
00345 for (dimension_type k = num_rows(); k-- > 0; ) {
00346 Row& rows_k = rows[k];
00347 for (dimension_type i = 0, j = 0; i < n; i = ++j) {
00348
00349 while (cycles[j] != 0)
00350 ++j;
00351
00352 assert(j - i >= 2);
00353 if (j - i == 2)
00354
00355 std::swap(rows_k[cycles[i]], rows_k[cycles[i+1]]);
00356 else {
00357
00358 std::swap(rows_k[cycles[j-1]], tmp);
00359 for (dimension_type l = j-1; l > i; --l)
00360 std::swap(rows_k[cycles[l-1]], rows_k[cycles[l]]);
00361 std::swap(tmp, rows_k[cycles[i]]);
00362 }
00363 }
00364 }
00365 }
00366
00368 bool
00369 PPL::operator==(const Matrix& x, const Matrix& y) {
00370 if (x.num_columns() != y.num_columns())
00371 return false;
00372 const dimension_type x_num_rows = x.num_rows();
00373 const dimension_type y_num_rows = y.num_rows();
00374 if (x_num_rows != y_num_rows)
00375 return false;
00376 for (dimension_type i = x_num_rows; i-- > 0; )
00377 if (x[i] != y[i])
00378 return false;
00379 return true;
00380 }
00381
00382 PPL::memory_size_type
00383 PPL::Matrix::external_memory_in_bytes() const {
00384 memory_size_type n = rows.capacity() * sizeof(Row);
00385 for (dimension_type i = num_rows(); i-- > 0; )
00386 n += rows[i].external_memory_in_bytes(row_capacity);
00387 return n;
00388 }
00389
00390 bool
00391 PPL::Matrix::OK() const {
00392 if (row_size > row_capacity) {
00393 #ifndef NDEBUG
00394 std::cerr << "Matrix completely broken: "
00395 << "row_capacity is " << row_capacity
00396 << ", row_size is " << row_size
00397 << std::endl;
00398 #endif
00399 return false;
00400 }
00401
00402 const Matrix& x = *this;
00403 for (dimension_type i = 0, n_rows = num_rows(); i < n_rows; ++i)
00404 if (!x[i].OK(row_size, row_capacity))
00405 return false;
00406
00407
00408 return true;
00409 }