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