00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024 #include <ppl-config.h>
00025
00026 #include "Grid.defs.hh"
00027 #include "Variables_Set.defs.hh"
00028 #include <cassert>
00029
00030 namespace PPL = Parma_Polyhedra_Library;
00031
00032
00033 void
00034 PPL::Grid::add_space_dimensions(Congruence_System& cgs,
00035 Grid_Generator_System& gs,
00036 const dimension_type dims) {
00037 assert(cgs.num_columns() - 1 == gs.space_dimension() + 1);
00038 assert(dims > 0);
00039
00040 const dimension_type old_modulus_index = cgs.num_columns() - 1;
00041 cgs.add_zero_columns(dims);
00042
00043 cgs.swap_columns(old_modulus_index, old_modulus_index + dims);
00044
00045 if (congruences_are_minimized() || generators_are_minimized())
00046 dim_kinds.resize(old_modulus_index + dims, CON_VIRTUAL );
00047
00048 gs.add_universe_rows_and_columns(dims);
00049 }
00050
00051
00052 void
00053 PPL::Grid::add_space_dimensions(Grid_Generator_System& gs,
00054 Congruence_System& cgs,
00055 const dimension_type dims) {
00056 assert(cgs.num_columns() - 1 == gs.space_dimension() + 1);
00057 assert(dims > 0);
00058
00059 cgs.add_unit_rows_and_columns(dims);
00060
00061
00062 gs.insert(parameter(0*Variable(space_dim + dims - 1)));
00063
00064 normalize_divisors(gs);
00065
00066 dim_kinds.resize(cgs.num_columns() - 1, EQUALITY );
00067 }
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077 void
00078 PPL::Grid::add_space_dimensions_and_embed(dimension_type m) {
00079 if (m == 0)
00080 return;
00081
00082
00083
00084 if (m > max_space_dimension() - space_dimension())
00085 throw_space_dimension_overflow("add_space_dimensions_and_embed(m)",
00086 "adding m new space dimensions exceeds "
00087 "the maximum allowed space dimension");
00088
00089
00090
00091
00092 if (marked_empty()) {
00093 space_dim += m;
00094 set_empty();
00095 return;
00096 }
00097
00098
00099 if (space_dim == 0) {
00100
00101 assert(status.test_zero_dim_univ());
00102
00103 Grid gr(m, UNIVERSE);
00104 swap(gr);
00105 return;
00106 }
00107
00108
00109
00110
00111
00112
00113
00114
00115 if (congruences_are_up_to_date())
00116 if (generators_are_up_to_date())
00117
00118 add_space_dimensions(con_sys, gen_sys, m);
00119 else {
00120
00121 con_sys.add_zero_columns(m);
00122 dimension_type size = con_sys.num_columns() - 1;
00123
00124 con_sys.swap_columns(size - m, size);
00125 if (congruences_are_minimized())
00126 dim_kinds.resize(size, CON_VIRTUAL);
00127 }
00128 else {
00129
00130 assert(generators_are_up_to_date());
00131 gen_sys.add_universe_rows_and_columns(m);
00132 if (generators_are_minimized())
00133 dim_kinds.resize(gen_sys.space_dimension() + 1, LINE);
00134 }
00135
00136 space_dim += m;
00137
00138
00139
00140 assert(OK());
00141 }
00142
00143
00144
00145
00146
00147
00148
00149
00150
00151 void
00152 PPL::Grid::add_space_dimensions_and_project(dimension_type m) {
00153 if (m == 0)
00154 return;
00155
00156
00157
00158 if (m > max_space_dimension() - space_dimension())
00159 throw_space_dimension_overflow("add_space_dimensions_and_project(m)",
00160 "adding m new space dimensions exceeds "
00161 "the maximum allowed space dimension");
00162
00163
00164
00165 if (marked_empty()) {
00166 space_dim += m;
00167 set_empty();
00168 return;
00169 }
00170
00171 if (space_dim == 0) {
00172 assert(status.test_zero_dim_univ());
00173
00174 Grid gr(m, UNIVERSE);
00175 swap(gr);
00176 return;
00177 }
00178
00179
00180
00181
00182
00183
00184
00185
00186 if (congruences_are_up_to_date())
00187 if (generators_are_up_to_date())
00188
00189 add_space_dimensions(gen_sys, con_sys, m);
00190 else {
00191
00192 con_sys.add_unit_rows_and_columns(m);
00193 if (congruences_are_minimized())
00194 dim_kinds.resize(con_sys.num_columns() - 1, EQUALITY);
00195 }
00196 else {
00197
00198 assert(generators_are_up_to_date());
00199
00200
00201 gen_sys.insert(parameter(0*Variable(space_dim + m - 1)));
00202
00203 normalize_divisors(gen_sys);
00204
00205 if (generators_are_minimized())
00206 dim_kinds.resize(gen_sys.space_dimension() + 1, EQUALITY);
00207 }
00208
00209 space_dim += m;
00210
00211
00212
00213 assert(OK());
00214 }
00215
00216 void
00217 PPL::Grid::concatenate_assign(const Grid& y) {
00218
00219
00220 if (y.space_dim > max_space_dimension() - space_dimension())
00221 throw_space_dimension_overflow("concatenate_assign(y)",
00222 "concatenation exceeds the maximum "
00223 "allowed space dimension");
00224
00225 const dimension_type added_columns = y.space_dim;
00226
00227
00228
00229 if (marked_empty() || y.marked_empty()) {
00230 space_dim += added_columns;
00231 set_empty();
00232 return;
00233 }
00234
00235
00236 if (added_columns == 0)
00237 return;
00238
00239
00240 if (space_dim == 0) {
00241 *this = y;
00242 return;
00243 }
00244
00245 if (!congruences_are_up_to_date())
00246 update_congruences();
00247
00248 con_sys.concatenate(y.congruences());
00249
00250 space_dim += added_columns;
00251
00252 clear_congruences_minimized();
00253 clear_generators_up_to_date();
00254
00255
00256
00257 assert(OK());
00258 }
00259
00260 void
00261 PPL::Grid::remove_space_dimensions(const Variables_Set& to_be_removed) {
00262
00263
00264
00265 if (to_be_removed.empty()) {
00266 assert(OK());
00267 return;
00268 }
00269
00270
00271 const dimension_type min_space_dim = to_be_removed.space_dimension();
00272 if (space_dim < min_space_dim)
00273 throw_dimension_incompatible("remove_space_dimensions(vs)", min_space_dim);
00274
00275 const dimension_type new_space_dim = space_dim - to_be_removed.size();
00276
00277 if (marked_empty()
00278 || (!generators_are_up_to_date() && !update_generators())) {
00279
00280 space_dim = new_space_dim;
00281 set_empty();
00282 assert(OK());
00283 return;
00284 }
00285
00286
00287
00288 if (new_space_dim == 0) {
00289 set_zero_dim_univ();
00290 return;
00291 }
00292
00293 gen_sys.remove_space_dimensions(to_be_removed);
00294
00295 clear_congruences_up_to_date();
00296 clear_generators_minimized();
00297
00298
00299 space_dim = new_space_dim;
00300
00301 assert(OK(true));
00302 }
00303
00304 void
00305 PPL::Grid::remove_higher_space_dimensions(const dimension_type new_dimension) {
00306
00307 if (new_dimension > space_dim)
00308 throw_dimension_incompatible("remove_higher_space_dimensions(nd)",
00309 new_dimension);
00310
00311
00312
00313
00314 if (new_dimension == space_dim) {
00315 assert(OK());
00316 return;
00317 }
00318
00319 if (is_empty()) {
00320
00321
00322 space_dim = new_dimension;
00323 set_empty();
00324 assert(OK());
00325 return;
00326 }
00327
00328 if (new_dimension == 0) {
00329
00330
00331 set_zero_dim_univ();
00332 return;
00333 }
00334
00335
00336 if (generators_are_up_to_date()) {
00337 gen_sys.remove_higher_space_dimensions(new_dimension);
00338 if (generators_are_minimized()) {
00339
00340 dimension_type num_redundant = 0;
00341 const dimension_type num_old_gs = space_dim - new_dimension;
00342 for (dimension_type row = 0; row < num_old_gs; ++row)
00343 dim_kinds[row] == GEN_VIRTUAL || ++num_redundant;
00344 if (num_redundant > 0) {
00345
00346 gen_sys.erase_to_end(gen_sys.num_rows() - num_redundant);
00347 gen_sys.unset_pending_rows();
00348 }
00349 dim_kinds.erase(dim_kinds.begin() + new_dimension + 1, dim_kinds.end());
00350
00351
00352 }
00353 clear_congruences_up_to_date();
00354
00355
00356 Congruence_System cgs(Congruence::zero_dim_false());
00357
00358 cgs.increase_space_dimension(new_dimension + 2);
00359 con_sys.swap(cgs);
00360 }
00361 else {
00362 assert(congruences_are_minimized());
00363 con_sys.remove_higher_space_dimensions(new_dimension);
00364
00365 dimension_type num_redundant = 0;
00366 for (dimension_type row = space_dim; row > new_dimension; --row)
00367 dim_kinds[row] == CON_VIRTUAL || ++num_redundant;
00368 if (num_redundant > 0) {
00369 dimension_type rows = con_sys.num_rows();
00370
00371 for (dimension_type low = 0, high = num_redundant;
00372 high < rows;
00373 ++high, ++low)
00374 std::swap(con_sys[low], con_sys[high]);
00375
00376
00377 con_sys.erase_to_end(rows - num_redundant);
00378 }
00379 dim_kinds.erase(dim_kinds.begin() + new_dimension + 1, dim_kinds.end());
00380 clear_generators_up_to_date();
00381
00382
00383 Grid_Generator_System gs(new_dimension + 2);
00384 gen_sys.swap(gs);
00385 }
00386
00387
00388 space_dim = new_dimension;
00389
00390 assert(OK(true));
00391 }
00392
00393 void
00394 PPL::Grid::expand_space_dimension(Variable var, dimension_type m) {
00395
00396
00397
00398 if (var.space_dimension() > space_dim)
00399 throw_dimension_incompatible("expand_space_dimension(v, m)", "v", var);
00400
00401
00402 if (m == 0)
00403 return;
00404
00405
00406 if (m > max_space_dimension() - space_dimension())
00407 throw_space_dimension_overflow("expand_space_dimension(v, m)",
00408 "adding m new space dimensions exceeds "
00409 "the maximum allowed space dimension");
00410
00411
00412 dimension_type old_dim = space_dim;
00413
00414
00415 add_space_dimensions_and_embed(m);
00416
00417 const dimension_type src_d = var.id();
00418 const Congruence_System& cgs = congruences();
00419 Congruence_System new_congruences;
00420 for (Congruence_System::const_iterator i = cgs.begin(),
00421 cgs_end = cgs.end(); i != cgs_end; ++i) {
00422 const Congruence& cg = *i;
00423
00424
00425 if (cg.coefficient(var) == 0)
00426 continue;
00427
00428
00429 for (dimension_type dst_d = old_dim; dst_d < old_dim+m; ++dst_d) {
00430 Linear_Expression e;
00431 for (dimension_type j = old_dim; j-- > 0; )
00432 e +=
00433 cg.coefficient(Variable(j))
00434 * (j == src_d ? Variable(dst_d) : Variable(j));
00435 new_congruences.insert_verbatim((e + cg.inhomogeneous_term() %= 0)
00436 / cg.modulus());
00437 }
00438 }
00439 add_recycled_congruences(new_congruences);
00440 assert(OK());
00441 }
00442
00443 void
00444 PPL::Grid::fold_space_dimensions(const Variables_Set& to_be_folded,
00445 Variable var) {
00446
00447
00448
00449 if (var.space_dimension() > space_dim)
00450 throw_dimension_incompatible("fold_space_dimensions(tbf, v)", "v", var);
00451
00452
00453 if (to_be_folded.empty())
00454 return;
00455
00456
00457 if (to_be_folded.space_dimension() > space_dim)
00458 throw_dimension_incompatible("fold_space_dimensions(tbf, v)",
00459 "tbf.space_dimension()",
00460 to_be_folded.space_dimension());
00461
00462
00463 if (to_be_folded.find(var.id()) != to_be_folded.end())
00464 throw_invalid_argument("fold_space_dimensions(tbf, v)",
00465 "v should not occur in tbf");
00466
00467
00468
00469
00470 (void) grid_generators();
00471
00472
00473 if (!marked_empty()) {
00474 for (Variables_Set::const_iterator i = to_be_folded.begin(),
00475 tbf_end = to_be_folded.end(); i != tbf_end; ++i) {
00476 Grid copy = *this;
00477 copy.affine_image(var, Linear_Expression(Variable(*i)));
00478 upper_bound_assign(copy);
00479 }
00480 }
00481 remove_space_dimensions(to_be_folded);
00482 assert(OK());
00483 }