00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef PPL_DB_Matrix_templates_hh
00024 #define PPL_DB_Matrix_templates_hh 1
00025
00026 namespace Parma_Polyhedra_Library {
00027
00028 template <typename T>
00029 DB_Matrix<T>::DB_Matrix(const dimension_type n_rows)
00030 : rows(n_rows),
00031 row_size(n_rows),
00032 row_capacity(compute_capacity(n_rows, max_num_columns())) {
00033
00034 for (dimension_type i = 0; i < n_rows; ++i)
00035 rows[i].construct(n_rows, row_capacity);
00036 assert(OK());
00037 }
00038
00039 template <typename T>
00040 template <typename U>
00041 DB_Matrix<T>::DB_Matrix(const DB_Matrix<U>& y)
00042 : rows(y.rows.size()),
00043 row_size(y.row_size),
00044 row_capacity(compute_capacity(y.row_size, max_num_columns())) {
00045
00046 for (dimension_type i = 0, n_rows = rows.size(); i < n_rows; ++i)
00047 rows[i].construct_upward_approximation(y[i], row_capacity);
00048 assert(OK());
00049 }
00050
00051 template <typename T>
00052 void
00053 DB_Matrix<T>::grow(const dimension_type new_n_rows) {
00054 const dimension_type old_n_rows = rows.size();
00055 assert(new_n_rows >= old_n_rows);
00056
00057 if (new_n_rows > old_n_rows) {
00058 if (new_n_rows <= row_capacity) {
00059
00060 if (rows.capacity() < new_n_rows) {
00061
00062 std::vector<DB_Row<T> > new_rows;
00063 new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
00064 new_rows.insert(new_rows.end(), new_n_rows, DB_Row<T>());
00065
00066 dimension_type i = new_n_rows;
00067 while (i-- > old_n_rows)
00068 new_rows[i].construct(new_n_rows, row_capacity);
00069
00070 ++i;
00071 while (i-- > 0)
00072 new_rows[i].swap(rows[i]);
00073
00074 std::swap(rows, new_rows);
00075 }
00076 else {
00077
00078 rows.insert(rows.end(), new_n_rows - old_n_rows, DB_Row<T>());
00079 for (dimension_type i = new_n_rows; i-- > old_n_rows; )
00080 rows[i].construct(new_n_rows, row_capacity);
00081 }
00082 }
00083 else {
00084
00085 DB_Matrix new_matrix;
00086 new_matrix.rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
00087 new_matrix.rows.insert(new_matrix.rows.end(), new_n_rows, DB_Row<T>());
00088
00089 new_matrix.row_size = new_n_rows;
00090 new_matrix.row_capacity = compute_capacity(new_n_rows,
00091 max_num_columns());
00092 dimension_type i = new_n_rows;
00093 while (i-- > old_n_rows)
00094 new_matrix.rows[i].construct(new_matrix.row_size,
00095 new_matrix.row_capacity);
00096
00097 ++i;
00098 while (i-- > 0) {
00099
00100 DB_Row<T> new_row(rows[i],
00101 new_matrix.row_size,
00102 new_matrix.row_capacity);
00103 std::swap(new_matrix.rows[i], new_row);
00104 }
00105
00106 swap(new_matrix);
00107 return;
00108 }
00109 }
00110
00111 if (new_n_rows > row_size) {
00112
00113 if (new_n_rows <= row_capacity)
00114
00115 for (dimension_type i = old_n_rows; i-- > 0; )
00116 rows[i].expand_within_capacity(new_n_rows);
00117 else {
00118
00119
00120 const dimension_type new_row_capacity
00121 = compute_capacity(new_n_rows, max_num_columns());
00122 for (dimension_type i = old_n_rows; i-- > 0; ) {
00123
00124 DB_Row<T> new_row(rows[i], new_n_rows, new_row_capacity);
00125 std::swap(rows[i], new_row);
00126 }
00127 row_capacity = new_row_capacity;
00128 }
00129
00130 row_size = new_n_rows;
00131 }
00132 }
00133
00134 template <typename T>
00135 void
00136 DB_Matrix<T>::resize_no_copy(const dimension_type new_n_rows) {
00137 dimension_type old_n_rows = rows.size();
00138
00139 if (new_n_rows > old_n_rows) {
00140
00141 if (new_n_rows <= row_capacity) {
00142
00143 if (rows.capacity() < new_n_rows) {
00144
00145 std::vector<DB_Row<T> > new_rows;
00146 new_rows.reserve(compute_capacity(new_n_rows, max_num_rows()));
00147 new_rows.insert(new_rows.end(), new_n_rows, DB_Row<T>());
00148
00149
00150 dimension_type i = new_n_rows;
00151 while (i-- > old_n_rows)
00152 new_rows[i].construct(new_n_rows, row_capacity);
00153
00154 ++i;
00155 while (i-- > 0)
00156 new_rows[i].swap(rows[i]);
00157
00158 std::swap(rows, new_rows);
00159 }
00160 else {
00161
00162 rows.insert(rows.end(), new_n_rows - old_n_rows, DB_Row<T>());
00163
00164
00165 for (dimension_type i = new_n_rows; i-- > old_n_rows; )
00166 rows[i].construct(new_n_rows, row_capacity);
00167 }
00168 }
00169 else {
00170
00171 DB_Matrix new_matrix(new_n_rows);
00172 swap(new_matrix);
00173 return;
00174 }
00175 }
00176 else if (new_n_rows < old_n_rows) {
00177
00178 rows.erase(rows.begin() + new_n_rows, rows.end());
00179
00180 for (dimension_type i = new_n_rows; i-- > 0; )
00181 rows[i].shrink(new_n_rows);
00182 old_n_rows = new_n_rows;
00183 }
00184
00185 if (new_n_rows > row_size) {
00186
00187 if (new_n_rows <= row_capacity)
00188
00189 for (dimension_type i = old_n_rows; i-- > 0; )
00190 rows[i].expand_within_capacity(new_n_rows);
00191 else {
00192
00193
00194 const dimension_type new_row_capacity
00195 = compute_capacity(new_n_rows, max_num_columns());
00196 for (dimension_type i = old_n_rows; i-- > 0; ) {
00197 DB_Row<T> new_row(new_n_rows, new_row_capacity);
00198 std::swap(rows[i], new_row);
00199 }
00200 row_capacity = new_row_capacity;
00201 }
00202 }
00203
00204 row_size = new_n_rows;
00205 }
00206
00207 template <typename T>
00208 void
00209 DB_Matrix<T>::ascii_dump(std::ostream& s) const {
00210 const DB_Matrix<T>& x = *this;
00211 const char separator = ' ';
00212 const dimension_type nrows = x.num_rows();
00213 s << nrows << separator << "\n";
00214 for (dimension_type i = 0; i < nrows; ++i) {
00215 for (dimension_type j = 0; j < nrows; ++j) {
00216 using namespace IO_Operators;
00217 s << x[i][j] << separator;
00218 }
00219 s << "\n";
00220 }
00221 }
00222
00223 PPL_OUTPUT_TEMPLATE_DEFINITIONS(T, DB_Matrix<T>)
00224
00225 template <typename T>
00226 bool
00227 DB_Matrix<T>::ascii_load(std::istream& s) {
00228 dimension_type nrows;
00229 if (!(s >> nrows))
00230 return false;
00231 resize_no_copy(nrows);
00232 DB_Matrix& x = *this;
00233 for (dimension_type i = 0; i < nrows; ++i)
00234 for (dimension_type j = 0; j < nrows; ++j) {
00235 Result r = input(x[i][j], s, ROUND_UP);
00236
00237 if (!s || r == V_CVT_STR_UNK)
00238 return false;
00239 }
00240
00241
00242 assert(OK());
00243 return true;
00244 }
00245
00246 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
00247
00248 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
00249 template <typename T>
00250 bool
00251 operator==(const DB_Matrix<T>& x, const DB_Matrix<T>& y) {
00252 const dimension_type x_num_rows = x.num_rows();
00253 if (x_num_rows != y.num_rows())
00254 return false;
00255 for (dimension_type i = x_num_rows; i-- > 0; )
00256 if (x[i] != y[i])
00257 return false;
00258 return true;
00259 }
00260
00261 template <typename T>
00262 memory_size_type
00263 DB_Matrix<T>::external_memory_in_bytes() const {
00264 memory_size_type n = rows.capacity() * sizeof(DB_Row<T>);
00265 for (dimension_type i = num_rows(); i-- > 0; )
00266 n += rows[i].external_memory_in_bytes(row_capacity);
00267 return n;
00268 }
00269
00270 template <typename T>
00271 bool
00272 DB_Matrix<T>::OK() const {
00273 #ifndef NDEBUG
00274 using std::endl;
00275 using std::cerr;
00276 #endif
00277
00278
00279 if (num_rows() != row_size) {
00280 #ifndef NDEBUG
00281 cerr << "DB_Matrix has fewer columns than rows:\n"
00282 << "row_size is " << row_size
00283 << ", num_rows() is " << num_rows() << "!"
00284 << endl;
00285 #endif
00286 return false;
00287 }
00288
00289 const DB_Matrix& x = *this;
00290 const dimension_type n_rows = x.num_rows();
00291 for (dimension_type i = 0; i < n_rows; ++i) {
00292 if (!x[i].OK(row_size, row_capacity))
00293 return false;
00294 }
00295
00296
00297 return true;
00298 }
00299
00300 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
00301
00302 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
00303 template <typename T>
00304 std::ostream&
00305 IO_Operators::operator<<(std::ostream& s, const DB_Matrix<T>& c) {
00306 const dimension_type n = c.num_rows();
00307 for (dimension_type i = 0; i < n; ++i) {
00308 for (dimension_type j = 0; j < n; ++j)
00309 s << c[i][j] << " ";
00310 s << "\n";
00311 }
00312 return s;
00313 }
00314
00315 }
00316
00317 #endif // !defined(PPL_DB_Matrix_templates_hh)