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 "Grid_Generator_System.defs.hh"
00026 #include "Grid_Generator_System.inlines.hh"
00027 #include "Scalar_Products.defs.hh"
00028
00029 #include <cassert>
00030 #include <iostream>
00031
00032 namespace PPL = Parma_Polyhedra_Library;
00033
00034 void
00035 PPL::Grid_Generator_System::recycling_insert(Grid_Generator_System& gs) {
00036 const dimension_type old_num_rows = num_rows();
00037 const dimension_type gs_num_rows = gs.num_rows();
00038 const dimension_type old_num_cols = num_columns();
00039 const dimension_type gs_num_cols = gs.num_columns();
00040 if (old_num_cols >= gs_num_cols)
00041 add_zero_rows(gs_num_rows,
00042 Linear_Row::Flags(NECESSARILY_CLOSED,
00043 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00044 else {
00045 add_zero_rows_and_columns(gs_num_rows,
00046 gs_num_cols - old_num_cols,
00047 Linear_Row::Flags(NECESSARILY_CLOSED,
00048 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00049
00050 swap_columns(old_num_cols - 1, num_columns() - 1);
00051 }
00052 set_index_first_pending_row(old_num_rows + gs_num_rows);
00053
00054
00055
00056 for (dimension_type i = gs_num_rows; i-- > 0; )
00057 operator[](old_num_rows + i).coefficient_swap(gs[i]);
00058 }
00059
00060 void
00061 PPL::Grid_Generator_System::recycling_insert(Grid_Generator& g) {
00062 dimension_type old_num_rows = num_rows();
00063 const dimension_type old_num_cols = num_columns();
00064 const dimension_type g_num_cols = g.size();
00065 if (old_num_cols >= g_num_cols)
00066 add_zero_rows(1,
00067 Linear_Row::Flags(NECESSARILY_CLOSED,
00068 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00069 else {
00070 add_zero_rows_and_columns(1,
00071 g_num_cols - old_num_cols,
00072 Linear_Row::Flags(NECESSARILY_CLOSED,
00073 Linear_Row::RAY_OR_POINT_OR_INEQUALITY));
00074
00075 swap_columns(old_num_cols - 1, num_columns() - 1);
00076 }
00077 set_index_first_pending_row(old_num_rows + 1);
00078
00079
00080
00081 operator[](old_num_rows).coefficient_swap(g);
00082 }
00083
00084 void
00085 PPL::Grid_Generator_System::insert(const Grid_Generator& g) {
00086 dimension_type g_space_dim = g.space_dimension();
00087
00088 if (g.is_parameter())
00089 if (g.all_homogeneous_terms_are_zero()) {
00090 dimension_type initial_space_dim = space_dimension();
00091 if (initial_space_dim < g_space_dim) {
00092
00093 add_zero_columns(g_space_dim - initial_space_dim);
00094
00095 swap_columns(g_space_dim + 1, initial_space_dim + 1);
00096 assert(OK());
00097 }
00098 return;
00099 }
00100
00101 {
00102
00103
00104
00105
00106
00107
00108 assert(num_pending_rows() == 0);
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121 assert(topology() == g.topology());
00122
00123 assert(num_pending_rows() == 0);
00124
00125 const dimension_type old_num_rows = num_rows();
00126 const dimension_type old_num_columns = num_columns();
00127 const dimension_type g_size = g.size();
00128
00129
00130 assert(is_necessarily_closed());
00131 if (g_size > old_num_columns) {
00132 add_zero_columns(g_size - old_num_columns);
00133 if (old_num_rows > 0)
00134
00135
00136 swap_columns(old_num_columns - 1, g_size - 1);
00137 Matrix::add_row(g);
00138 }
00139 else if (g_size < old_num_columns)
00140 if (old_num_rows == 0)
00141 Matrix::add_row(Linear_Row(g, old_num_columns, row_capacity));
00142 else {
00143
00144
00145 Linear_Row tmp_row(g, old_num_columns, row_capacity);
00146 std::swap(tmp_row[g_size - 1], tmp_row[old_num_columns - 1]);
00147 Matrix::add_row(tmp_row);
00148 }
00149 else
00150
00151 Matrix::add_row(g);
00152
00153 }
00154
00155 set_index_first_pending_row(num_rows());
00156 set_sorted(false);
00157
00158 assert(OK());
00159 }
00160
00161 void
00162 PPL::Grid_Generator_System
00163 ::affine_image(dimension_type v,
00164 const Linear_Expression& expr,
00165 Coefficient_traits::const_reference denominator) {
00166
00167
00168 Grid_Generator_System& x = *this;
00169
00170
00171 assert(v > 0 && v <= x.space_dimension());
00172 assert(expr.space_dimension() <= x.space_dimension());
00173 assert(denominator > 0);
00174
00175 const dimension_type n_columns = x.num_columns();
00176 const dimension_type n_rows = x.num_rows();
00177
00178
00179
00180 TEMP_INTEGER(numerator);
00181 for (dimension_type i = n_rows; i-- > 0; ) {
00182 Grid_Generator& row = x[i];
00183 Scalar_Products::assign(numerator, expr, row);
00184 std::swap(numerator, row[v]);
00185 }
00186
00187 if (denominator != 1)
00188
00189
00190
00191 for (dimension_type i = n_rows; i-- > 0; ) {
00192 Grid_Generator& row = x[i];
00193 for (dimension_type j = n_columns; j-- > 0; )
00194 if (j != v)
00195 row[j] *= denominator;
00196 }
00197
00198
00199
00200 const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0);
00201 if (not_invertible)
00202 x.remove_invalid_lines_and_rays();
00203 }
00204
00205 PPL_OUTPUT_DEFINITIONS(Grid_Generator_System);
00206
00207 bool
00208 PPL::Grid_Generator_System::ascii_load(std::istream& s) {
00209
00210
00211
00212
00213
00214
00215 std::string str;
00216 if (!(s >> str) || str != "topology")
00217 return false;
00218 if (!(s >> str))
00219 return false;
00220 if (str == "NECESSARILY_CLOSED")
00221 set_necessarily_closed();
00222 else {
00223 if (str != "NOT_NECESSARILY_CLOSED")
00224 return false;
00225 set_not_necessarily_closed();
00226 }
00227
00228 dimension_type nrows;
00229 dimension_type ncols;
00230 if (!(s >> nrows))
00231 return false;
00232 if (!(s >> str))
00233 return false;
00234 if (!(s >> ncols))
00235 return false;
00236 resize_no_copy(nrows, ncols);
00237
00238 if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00239 return false;
00240 set_sorted(str == "(sorted)");
00241 dimension_type index;
00242 if (!(s >> str) || str != "index_first_pending")
00243 return false;
00244 if (!(s >> index))
00245 return false;
00246 set_index_first_pending_row(index);
00247
00248 Grid_Generator_System& x = *this;
00249 for (dimension_type i = 0; i < x.num_rows(); ++i) {
00250 for (dimension_type j = 0; j < x.num_columns(); ++j)
00251 if (!(s >> const_cast<Coefficient&>(x[i][j])))
00252 return false;
00253
00254 if (!(s >> str))
00255 return false;
00256 if (str == "L")
00257 x[i].set_is_line();
00258 else
00259 x[i].set_is_ray_or_point();
00260
00261
00262 switch (x[i].type()) {
00263 case Grid_Generator::LINE:
00264 if (str == "L")
00265 continue;
00266 break;
00267 case Grid_Generator::PARAMETER:
00268 if (str == "R")
00269 continue;
00270 break;
00271 case Grid_Generator::POINT:
00272 if (str == "P")
00273 continue;
00274 break;
00275 }
00276
00277 return false;
00278 }
00279
00280
00281
00282 assert(OK());
00283 return true;
00284 }
00285
00286 bool
00287 PPL::Grid_Generator_System::OK() const {
00288 if (topology() == NOT_NECESSARILY_CLOSED) {
00289 #ifndef NDEBUG
00290 std::cerr << "Grid_Generator_System is NOT_NECESSARILY_CLOSED"
00291 << std::endl;
00292 #endif
00293 return false;
00294 }
00295
00296 if (is_sorted()) {
00297 #ifndef NDEBUG
00298 std::cerr << "Grid_Generator_System is marked as sorted."
00299 << std::endl;
00300 #endif
00301 return false;
00302 }
00303
00304
00305
00306
00307 if (!Linear_System::OK(false))
00308 return false;
00309
00310
00311 const Grid_Generator_System& x = *this;
00312 for (dimension_type i = num_rows(); i-- > 0; )
00313 if (!x[i].OK())
00314 return false;
00315
00316
00317 return true;
00318 }
00319
00321 std::ostream&
00322 PPL::IO_Operators::operator<<(std::ostream& s,
00323 const Grid_Generator_System& gs) {
00324 Grid_Generator_System::const_iterator i = gs.begin();
00325 const Grid_Generator_System::const_iterator gs_end = gs.end();
00326 if (i == gs_end)
00327 return s << "false";
00328 while (true) {
00329 s << *i++;
00330 if (i == gs_end)
00331 return s;
00332 s << ", ";
00333 }
00334 }
00335
00336 void
00337 PPL::Grid_Generator_System
00338 ::add_universe_rows_and_columns(dimension_type dims) {
00339 assert(num_columns() > 0);
00340 dimension_type col = num_columns() - 1;
00341 add_zero_rows_and_columns(dims, dims,
00342 Linear_Row::Flags(NECESSARILY_CLOSED,
00343 Linear_Row::LINE_OR_EQUALITY));
00344 unset_pending_rows();
00345
00346 swap_columns(col, col + dims);
00347
00348 dimension_type rows = num_rows();
00349 for (dimension_type row = rows - dims; row < rows; ++row, ++col)
00350 const_cast<Coefficient&>(operator[](row)[col]) = 1;
00351 }
00352
00353 void
00354 PPL::Grid_Generator_System
00355 ::remove_space_dimensions(const Variables_Set& to_be_removed) {
00356
00357
00358
00359 if (to_be_removed.empty())
00360 return;
00361
00362
00363
00364 const dimension_type
00365 min_space_dim = to_be_removed.rbegin()->space_dimension();
00366 if (space_dimension() < min_space_dim) {
00367 std::ostringstream s;
00368 s << "PPL::Grid_Generator_System::remove_space_dimensions(vs):\n"
00369 << "this->space_dimension() == " << space_dimension()
00370 << ", required space dimension == " << min_space_dim << ".";
00371 throw std::invalid_argument(s.str());
00372 }
00373
00374
00375
00376 Variables_Set::const_iterator tbr = to_be_removed.begin();
00377 Variables_Set::const_iterator tbr_end = to_be_removed.end();
00378 dimension_type dst_col = tbr->space_dimension();
00379 dimension_type src_col = dst_col + 1;
00380 for (++tbr; tbr != tbr_end; ++tbr) {
00381 dimension_type tbr_col = tbr->space_dimension();
00382
00383 while (src_col < tbr_col)
00384
00385
00386 Matrix::swap_columns(dst_col++, src_col++);
00387 ++src_col;
00388 }
00389
00390 const dimension_type num_cols = num_columns();
00391 while (src_col < num_cols)
00392
00393
00394 Matrix::swap_columns(dst_col++, src_col++);
00395
00396
00397 Matrix::remove_trailing_columns(num_cols - dst_col);
00398
00399
00400
00401 remove_invalid_lines_and_rays();
00402 }
00403
00404 void
00405 PPL::Grid_Generator_System
00406 ::remove_higher_space_dimensions(dimension_type new_dimension) {
00407 dimension_type space_dim = space_dimension();
00408
00409 if (new_dimension > space_dim) {
00410 std::ostringstream s;
00411 s << "PPL::Grid_Generator_System::remove_higher_space_dimensions(n):\n"
00412 << "this->space_dimension() == " << space_dim
00413 << ", required space dimension == " << new_dimension << ".";
00414 throw std::invalid_argument(s.str());
00415 }
00416
00417
00418
00419
00420 if (new_dimension == space_dim)
00421 return;
00422
00423
00424
00425 swap_columns(new_dimension + 1, space_dim + 1);
00426 Matrix::remove_trailing_columns(space_dim - new_dimension);
00427 remove_invalid_lines_and_rays();
00428 assert(OK());
00429 }