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_BD_Shape_inlines_hh
00024 #define PPL_BD_Shape_inlines_hh 1
00025
00026 #include "Constraint_System.defs.hh"
00027 #include "Constraint_System.inlines.hh"
00028 #include "C_Polyhedron.defs.hh"
00029 #include "Grid.defs.hh"
00030 #include "Octagonal_Shape.defs.hh"
00031 #include "Poly_Con_Relation.defs.hh"
00032 #include "Poly_Gen_Relation.defs.hh"
00033 #include "Temp.defs.hh"
00034 #include <cassert>
00035 #include <vector>
00036 #include <iostream>
00037 #include <algorithm>
00038
00039 namespace Parma_Polyhedra_Library {
00040
00041 template <typename T>
00042 inline dimension_type
00043 BD_Shape<T>::max_space_dimension() {
00044
00045
00046 return std::min(DB_Matrix<N>::max_num_rows() - 1,
00047 DB_Matrix<N>::max_num_columns() - 1);
00048 }
00049
00050 template <typename T>
00051 inline bool
00052 BD_Shape<T>::marked_zero_dim_univ() const {
00053 return status.test_zero_dim_univ();
00054 }
00055
00056 template <typename T>
00057 inline bool
00058 BD_Shape<T>::marked_empty() const {
00059 return status.test_empty();
00060 }
00061
00062 template <typename T>
00063 inline bool
00064 BD_Shape<T>::marked_shortest_path_closed() const {
00065 return status.test_shortest_path_closed();
00066 }
00067
00068 template <typename T>
00069 inline bool
00070 BD_Shape<T>::marked_shortest_path_reduced() const {
00071 return status.test_shortest_path_reduced();
00072 }
00073
00074 template <typename T>
00075 inline void
00076 BD_Shape<T>::set_zero_dim_univ() {
00077 status.set_zero_dim_univ();
00078 }
00079
00080 template <typename T>
00081 inline void
00082 BD_Shape<T>::set_empty() {
00083 status.set_empty();
00084 }
00085
00086 template <typename T>
00087 inline void
00088 BD_Shape<T>::set_shortest_path_closed() {
00089 status.set_shortest_path_closed();
00090 }
00091
00092 template <typename T>
00093 inline void
00094 BD_Shape<T>::set_shortest_path_reduced() {
00095 status.set_shortest_path_reduced();
00096 }
00097
00098 template <typename T>
00099 inline void
00100 BD_Shape<T>::reset_shortest_path_closed() {
00101 status.reset_shortest_path_closed();
00102 }
00103
00104 template <typename T>
00105 inline void
00106 BD_Shape<T>::reset_shortest_path_reduced() {
00107 status.reset_shortest_path_reduced();
00108 }
00109
00110 template <typename T>
00111 inline
00112 BD_Shape<T>::BD_Shape(const dimension_type num_dimensions,
00113 const Degenerate_Element kind)
00114 : dbm(num_dimensions + 1), status(), redundancy_dbm() {
00115 if (kind == EMPTY)
00116 set_empty();
00117 else {
00118 if (num_dimensions > 0)
00119
00120 set_shortest_path_closed();
00121 }
00122 assert(OK());
00123 }
00124
00125 template <typename T>
00126 inline
00127 BD_Shape<T>::BD_Shape(const BD_Shape& y, Complexity_Class)
00128 : dbm(y.dbm), status(y.status), redundancy_dbm() {
00129 if (y.marked_shortest_path_reduced())
00130 redundancy_dbm = y.redundancy_dbm;
00131 }
00132
00133 template <typename T>
00134 template <typename U>
00135 inline
00136 BD_Shape<T>::BD_Shape(const BD_Shape<U>& y, Complexity_Class)
00137
00138
00139 : dbm((y.shortest_path_closure_assign(), y.dbm)),
00140 status(),
00141 redundancy_dbm() {
00142
00143 if (y.marked_empty())
00144 set_empty();
00145 else if (y.marked_zero_dim_univ())
00146 set_zero_dim_univ();
00147 }
00148
00149 template <typename T>
00150 inline Congruence_System
00151 BD_Shape<T>::congruences() const {
00152 return minimized_congruences();
00153 }
00154
00155 template <typename T>
00156 inline bool
00157 BD_Shape<T>::add_constraint_and_minimize(const Constraint& c) {
00158 add_constraint(c);
00159 shortest_path_closure_assign();
00160 return !marked_empty();
00161 }
00162
00163 template <typename T>
00164 inline bool
00165 BD_Shape<T>::add_congruence_and_minimize(const Congruence& cg) {
00166 add_congruence(cg);
00167 shortest_path_closure_assign();
00168 return !marked_empty();
00169 }
00170
00171 template <typename T>
00172 inline void
00173 BD_Shape<T>::add_constraints(const Constraint_System& cs) {
00174 for (Constraint_System::const_iterator i = cs.begin(),
00175 cs_end = cs.end(); i != cs_end; ++i)
00176 add_constraint(*i);
00177 }
00178
00179 template <typename T>
00180 inline bool
00181 BD_Shape<T>::add_constraints_and_minimize(const Constraint_System& cs) {
00182 add_constraints(cs);
00183 shortest_path_closure_assign();
00184 return !marked_empty();
00185 }
00186
00187 template <typename T>
00188 inline void
00189 BD_Shape<T>::add_recycled_constraints(Constraint_System& cs) {
00190 add_constraints(cs);
00191 }
00192
00193 template <typename T>
00194 inline bool
00195 BD_Shape<T>::add_recycled_constraints_and_minimize(Constraint_System& cs) {
00196 return add_constraints_and_minimize(cs);
00197 }
00198
00199 template <typename T>
00200 inline void
00201 BD_Shape<T>::add_congruences(const Congruence_System& cgs) {
00202 for (Congruence_System::const_iterator i = cgs.begin(),
00203 cgs_end = cgs.end(); i != cgs_end; ++i)
00204 add_congruence(*i);
00205 }
00206
00207 template <typename T>
00208 inline bool
00209 BD_Shape<T>::add_congruences_and_minimize(const Congruence_System& cgs) {
00210 add_congruences(cgs);
00211 return !is_empty();
00212 }
00213
00214 template <typename T>
00215 inline void
00216 BD_Shape<T>::add_recycled_congruences(Congruence_System& cgs) {
00217 add_congruences(cgs);
00218 }
00219
00220 template <typename T>
00221 inline bool
00222 BD_Shape<T>::add_recycled_congruences_and_minimize(Congruence_System& cgs) {
00223 return add_congruences_and_minimize(cgs);
00224 }
00225
00226 template <typename T>
00227 inline void
00228 BD_Shape<T>::refine_with_constraint(const Constraint& c) {
00229 const dimension_type c_space_dim = c.space_dimension();
00230
00231 if (c_space_dim > space_dimension())
00232 throw_dimension_incompatible("refine_with_constraint(c)", c);
00233
00234 if (!marked_empty())
00235 refine_no_check(c);
00236 }
00237
00238 template <typename T>
00239 inline void
00240 BD_Shape<T>::refine_with_constraints(const Constraint_System& cs) {
00241
00242 if (cs.space_dimension() > space_dimension())
00243 throw_generic("refine_with_constraints(cs)",
00244 "cs and *this are space-dimension incompatible");
00245
00246 for (Constraint_System::const_iterator i = cs.begin(),
00247 cs_end = cs.end(); !marked_empty() && i != cs_end; ++i)
00248 refine_no_check(*i);
00249 }
00250
00251 template <typename T>
00252 inline void
00253 BD_Shape<T>::refine_with_congruence(const Congruence& cg) {
00254 const dimension_type cg_space_dim = cg.space_dimension();
00255
00256 if (cg_space_dim > space_dimension())
00257 throw_dimension_incompatible("refine_with_congruence(cg)", cg);
00258
00259 if (!marked_empty())
00260 refine_no_check(cg);
00261 }
00262
00263 template <typename T>
00264 void
00265 BD_Shape<T>::refine_with_congruences(const Congruence_System& cgs) {
00266
00267 if (cgs.space_dimension() > space_dimension())
00268 throw_generic("refine_with_congruences(cgs)",
00269 "cgs and *this are space-dimension incompatible");
00270
00271 for (Congruence_System::const_iterator i = cgs.begin(),
00272 cgs_end = cgs.end(); !marked_empty() && i != cgs_end; ++i)
00273 refine_no_check(*i);
00274 }
00275
00276 template <typename T>
00277 inline void
00278 BD_Shape<T>::refine_no_check(const Congruence& cg) {
00279 assert(!marked_empty());
00280 assert(cg.space_dimension() <= space_dimension());
00281
00282 if (cg.is_proper_congruence()) {
00283 if (cg.is_inconsistent())
00284 set_empty();
00285
00286 return;
00287 }
00288
00289 assert(cg.is_equality());
00290 Constraint c(cg);
00291 refine_no_check(c);
00292 }
00293
00294 template <typename T>
00295 inline bool
00296 BD_Shape<T>::can_recycle_constraint_systems() {
00297 return false;
00298 }
00299
00300
00301 template <typename T>
00302 inline bool
00303 BD_Shape<T>::can_recycle_congruence_systems() {
00304 return false;
00305 }
00306
00307 template <typename T>
00308 inline
00309 BD_Shape<T>::BD_Shape(const Constraint_System& cs)
00310 : dbm(cs.space_dimension() + 1), status(), redundancy_dbm() {
00311 if (cs.space_dimension() > 0)
00312
00313 set_shortest_path_closed();
00314 add_constraints(cs);
00315 }
00316
00317 template <typename T>
00318 template <typename Interval>
00319 inline
00320 BD_Shape<T>::BD_Shape(const Box<Interval>& box,
00321 Complexity_Class)
00322 : dbm(box.space_dimension() + 1), status(), redundancy_dbm() {
00323
00324 if (box.is_empty())
00325 set_empty();
00326 else if (box.space_dimension() > 0) {
00327
00328 set_shortest_path_closed();
00329 refine_with_constraints(box.constraints());
00330 }
00331 }
00332
00333 template <typename T>
00334 inline
00335 BD_Shape<T>::BD_Shape(const Grid& grid,
00336 Complexity_Class)
00337 : dbm(grid.space_dimension() + 1), status(), redundancy_dbm() {
00338 if (grid.space_dimension() > 0)
00339
00340 set_shortest_path_closed();
00341
00342 refine_with_congruences(grid.minimized_congruences());
00343 }
00344
00345 template <typename T>
00346 template <typename U>
00347 inline
00348 BD_Shape<T>::BD_Shape(const Octagonal_Shape<U>& os,
00349 Complexity_Class)
00350 : dbm(os.space_dimension() + 1), status(), redundancy_dbm() {
00351
00352 if (os.is_empty())
00353 set_empty();
00354 else if (os.space_dimension() > 0) {
00355
00356 set_shortest_path_closed();
00357 refine_with_constraints(os.constraints());
00358
00359
00360
00361 }
00362 }
00363
00364 template <typename T>
00365 inline BD_Shape<T>&
00366 BD_Shape<T>::operator=(const BD_Shape& y) {
00367 dbm = y.dbm;
00368 status = y.status;
00369 if (y.marked_shortest_path_reduced())
00370 redundancy_dbm = y.redundancy_dbm;
00371 return *this;
00372 }
00373
00374 template <typename T>
00375 inline
00376 BD_Shape<T>::~BD_Shape() {
00377 }
00378
00379 template <typename T>
00380 inline void
00381 BD_Shape<T>::swap(BD_Shape& y) {
00382 std::swap(dbm, y.dbm);
00383 std::swap(status, y.status);
00384 std::swap(redundancy_dbm, y.redundancy_dbm);
00385 }
00386
00387 template <typename T>
00388 inline dimension_type
00389 BD_Shape<T>::space_dimension() const {
00390 return dbm.num_rows() - 1;
00391 }
00392
00393 template <typename T>
00394 inline bool
00395 BD_Shape<T>::is_empty() const {
00396 shortest_path_closure_assign();
00397 return marked_empty();
00398 }
00399
00400 template <typename T>
00401 inline bool
00402 BD_Shape<T>::bounds_from_above(const Linear_Expression& expr) const {
00403 return bounds(expr, true);
00404 }
00405
00406 template <typename T>
00407 inline bool
00408 BD_Shape<T>::bounds_from_below(const Linear_Expression& expr) const {
00409 return bounds(expr, false);
00410 }
00411
00412 template <typename T>
00413 inline bool
00414 BD_Shape<T>::maximize(const Linear_Expression& expr,
00415 Coefficient& sup_n, Coefficient& sup_d,
00416 bool& maximum) const {
00417 return max_min(expr, true, sup_n, sup_d, maximum);
00418 }
00419
00420 template <typename T>
00421 inline bool
00422 BD_Shape<T>::maximize(const Linear_Expression& expr,
00423 Coefficient& sup_n, Coefficient& sup_d, bool& maximum,
00424 Generator& g) const {
00425 return max_min(expr, true, sup_n, sup_d, maximum, g);
00426 }
00427
00428 template <typename T>
00429 inline bool
00430 BD_Shape<T>::minimize(const Linear_Expression& expr,
00431 Coefficient& inf_n, Coefficient& inf_d,
00432 bool& minimum) const {
00433 return max_min(expr, false, inf_n, inf_d, minimum);
00434 }
00435
00436 template <typename T>
00437 inline bool
00438 BD_Shape<T>::minimize(const Linear_Expression& expr,
00439 Coefficient& inf_n, Coefficient& inf_d, bool& minimum,
00440 Generator& g) const {
00441 return max_min(expr, false, inf_n, inf_d, minimum, g);
00442 }
00443
00444 template <typename T>
00445 inline bool
00446 BD_Shape<T>::is_topologically_closed() const {
00447 return true;
00448 }
00449
00450 template <typename T>
00451 inline bool
00452 BD_Shape<T>::is_discrete() const {
00453 return affine_dimension() == 0;
00454 }
00455
00456 template <typename T>
00457 inline void
00458 BD_Shape<T>::topological_closure_assign() {
00459
00460 return;
00461 }
00462
00464 template <typename T>
00465 inline bool
00466 operator==(const BD_Shape<T>& x, const BD_Shape<T>& y) {
00467 const dimension_type x_space_dim = x.space_dimension();
00468
00469 if (x_space_dim != y.space_dimension())
00470 return false;
00471
00472
00473 if (x_space_dim == 0) {
00474 if (x.marked_empty())
00475 return y.marked_empty();
00476 else
00477 return !y.marked_empty();
00478 }
00479
00480
00481 x.shortest_path_closure_assign();
00482 y.shortest_path_closure_assign();
00483
00484
00485
00486 if (x.marked_empty())
00487 return y.marked_empty();
00488 if (y.marked_empty())
00489 return false;
00490
00491
00492 return x.dbm == y.dbm;
00493 }
00494
00496 template <typename T>
00497 inline bool
00498 operator!=(const BD_Shape<T>& x, const BD_Shape<T>& y) {
00499 return !(x == y);
00500 }
00501
00503 template <typename Temp, typename To, typename T>
00504 inline bool
00505 rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00506 const BD_Shape<T>& x,
00507 const BD_Shape<T>& y,
00508 const Rounding_Dir dir,
00509 Temp& tmp0,
00510 Temp& tmp1,
00511 Temp& tmp2) {
00512 const dimension_type x_space_dim = x.space_dimension();
00513
00514 if (x_space_dim != y.space_dimension())
00515 return false;
00516
00517
00518 if (x_space_dim == 0) {
00519 if (x.marked_empty() == y.marked_empty())
00520 assign_r(r, 0, ROUND_NOT_NEEDED);
00521 else
00522 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00523 return true;
00524 }
00525
00526
00527 x.shortest_path_closure_assign();
00528 y.shortest_path_closure_assign();
00529
00530
00531
00532 if (x.marked_empty() || y.marked_empty()) {
00533 if (x.marked_empty() == y.marked_empty())
00534 assign_r(r, 0, ROUND_NOT_NEEDED);
00535 else
00536 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00537 return true;
00538 }
00539
00540 return rectilinear_distance_assign(r, x.dbm, y.dbm, dir, tmp0, tmp1, tmp2);
00541 }
00542
00544 template <typename Temp, typename To, typename T>
00545 inline bool
00546 rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00547 const BD_Shape<T>& x,
00548 const BD_Shape<T>& y,
00549 const Rounding_Dir dir) {
00550 typedef Checked_Number<Temp, Extended_Number_Policy> Checked_Temp;
00551 DIRTY_TEMP(Checked_Temp, tmp0);
00552 DIRTY_TEMP(Checked_Temp, tmp1);
00553 DIRTY_TEMP(Checked_Temp, tmp2);
00554 return rectilinear_distance_assign(r, x, y, dir, tmp0, tmp1, tmp2);
00555 }
00556
00558 template <typename To, typename T>
00559 inline bool
00560 rectilinear_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00561 const BD_Shape<T>& x,
00562 const BD_Shape<T>& y,
00563 const Rounding_Dir dir) {
00564 return rectilinear_distance_assign<To, To, T>(r, x, y, dir);
00565 }
00566
00568 template <typename Temp, typename To, typename T>
00569 inline bool
00570 euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00571 const BD_Shape<T>& x,
00572 const BD_Shape<T>& y,
00573 const Rounding_Dir dir,
00574 Temp& tmp0,
00575 Temp& tmp1,
00576 Temp& tmp2) {
00577 const dimension_type x_space_dim = x.space_dimension();
00578
00579 if (x_space_dim != y.space_dimension())
00580 return false;
00581
00582
00583 if (x_space_dim == 0) {
00584 if (x.marked_empty() == y.marked_empty())
00585 assign_r(r, 0, ROUND_NOT_NEEDED);
00586 else
00587 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00588 return true;
00589 }
00590
00591
00592 x.shortest_path_closure_assign();
00593 y.shortest_path_closure_assign();
00594
00595
00596
00597 if (x.marked_empty() || y.marked_empty()) {
00598 if (x.marked_empty() == y.marked_empty())
00599 assign_r(r, 0, ROUND_NOT_NEEDED);
00600 else
00601 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00602 return true;
00603 }
00604
00605 return euclidean_distance_assign(r, x.dbm, y.dbm, dir, tmp0, tmp1, tmp2);
00606 }
00607
00609 template <typename Temp, typename To, typename T>
00610 inline bool
00611 euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00612 const BD_Shape<T>& x,
00613 const BD_Shape<T>& y,
00614 const Rounding_Dir dir) {
00615 typedef Checked_Number<Temp, Extended_Number_Policy> Checked_Temp;
00616 DIRTY_TEMP(Checked_Temp, tmp0);
00617 DIRTY_TEMP(Checked_Temp, tmp1);
00618 DIRTY_TEMP(Checked_Temp, tmp2);
00619 return euclidean_distance_assign(r, x, y, dir, tmp0, tmp1, tmp2);
00620 }
00621
00623 template <typename To, typename T>
00624 inline bool
00625 euclidean_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00626 const BD_Shape<T>& x,
00627 const BD_Shape<T>& y,
00628 const Rounding_Dir dir) {
00629 return euclidean_distance_assign<To, To, T>(r, x, y, dir);
00630 }
00631
00633 template <typename Temp, typename To, typename T>
00634 inline bool
00635 l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00636 const BD_Shape<T>& x,
00637 const BD_Shape<T>& y,
00638 const Rounding_Dir dir,
00639 Temp& tmp0,
00640 Temp& tmp1,
00641 Temp& tmp2) {
00642 const dimension_type x_space_dim = x.space_dimension();
00643
00644 if (x_space_dim != y.space_dimension())
00645 return false;
00646
00647
00648 if (x_space_dim == 0) {
00649 if (x.marked_empty() == y.marked_empty())
00650 assign_r(r, 0, ROUND_NOT_NEEDED);
00651 else
00652 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00653 return true;
00654 }
00655
00656
00657 x.shortest_path_closure_assign();
00658 y.shortest_path_closure_assign();
00659
00660
00661
00662 if (x.marked_empty() || y.marked_empty()) {
00663 if (x.marked_empty() == y.marked_empty())
00664 assign_r(r, 0, ROUND_NOT_NEEDED);
00665 else
00666 assign_r(r, PLUS_INFINITY, ROUND_NOT_NEEDED);
00667 return true;
00668 }
00669
00670 return l_infinity_distance_assign(r, x.dbm, y.dbm, dir, tmp0, tmp1, tmp2);
00671 }
00672
00674 template <typename Temp, typename To, typename T>
00675 inline bool
00676 l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00677 const BD_Shape<T>& x,
00678 const BD_Shape<T>& y,
00679 const Rounding_Dir dir) {
00680 typedef Checked_Number<Temp, Extended_Number_Policy> Checked_Temp;
00681 DIRTY_TEMP(Checked_Temp, tmp0);
00682 DIRTY_TEMP(Checked_Temp, tmp1);
00683 DIRTY_TEMP(Checked_Temp, tmp2);
00684 return l_infinity_distance_assign(r, x, y, dir, tmp0, tmp1, tmp2);
00685 }
00686
00688 template <typename To, typename T>
00689 inline bool
00690 l_infinity_distance_assign(Checked_Number<To, Extended_Number_Policy>& r,
00691 const BD_Shape<T>& x,
00692 const BD_Shape<T>& y,
00693 const Rounding_Dir dir) {
00694 return l_infinity_distance_assign<To, To, T>(r, x, y, dir);
00695 }
00696
00697 template <typename T>
00698 inline void
00699 BD_Shape<T>::add_dbm_constraint(const dimension_type i,
00700 const dimension_type j,
00701 const N& k) {
00702
00703 assert(i <= space_dimension() && j <= space_dimension() && i != j);
00704 N& dbm_ij = dbm[i][j];
00705 if (dbm_ij > k) {
00706 dbm_ij = k;
00707 if (marked_shortest_path_closed())
00708 reset_shortest_path_closed();
00709 }
00710 }
00711
00712 template <typename T>
00713 inline void
00714 BD_Shape<T>::add_dbm_constraint(const dimension_type i,
00715 const dimension_type j,
00716 Coefficient_traits::const_reference num,
00717 Coefficient_traits::const_reference den) {
00718
00719 assert(i <= space_dimension() && j <= space_dimension() && i != j);
00720 assert(den != 0);
00721 DIRTY_TEMP(N, k);
00722 div_round_up(k, num, den);
00723 add_dbm_constraint(i, j, k);
00724 }
00725
00726 template <typename T>
00727 inline void
00728 BD_Shape<T>::time_elapse_assign(const BD_Shape& y) {
00729
00730 if (space_dimension() != y.space_dimension())
00731 throw_dimension_incompatible("time_elapse_assign(y)", y);
00732
00733 C_Polyhedron px(constraints());
00734 C_Polyhedron py(y.constraints());
00735 px.time_elapse_assign(py);
00736 BD_Shape<T> x(px);
00737 swap(x);
00738 assert(OK());
00739 }
00740
00741 template <typename T>
00742 inline bool
00743 BD_Shape<T>::strictly_contains(const BD_Shape& y) const {
00744 const BD_Shape<T>& x = *this;
00745 return x.contains(y) && !y.contains(x);
00746 }
00747
00748 template <typename T>
00749 inline bool
00750 BD_Shape<T>::upper_bound_assign_and_minimize(const BD_Shape& y) {
00751 upper_bound_assign(y);
00752 assert(marked_empty()
00753 || space_dimension() == 0 || marked_shortest_path_closed());
00754 return !marked_empty();
00755 }
00756
00757 template <typename T>
00758 inline bool
00759 BD_Shape<T>::upper_bound_assign_if_exact(const BD_Shape& y) {
00760
00761 used(y);
00762 return false;
00763 }
00764
00765 template <typename T>
00766 inline void
00767 BD_Shape<T>::remove_higher_space_dimensions(const dimension_type new_dim) {
00768
00769
00770 if (new_dim > space_dimension())
00771 throw_dimension_incompatible("remove_higher_space_dimensions(nd)",
00772 new_dim);
00773
00774
00775
00776
00777 if (new_dim == space_dimension()) {
00778 assert(OK());
00779 return;
00780 }
00781
00782
00783 shortest_path_closure_assign();
00784 dbm.resize_no_copy(new_dim + 1);
00785
00786
00787
00788 if (marked_shortest_path_reduced())
00789 reset_shortest_path_reduced();
00790
00791
00792
00793 if (new_dim == 0 && !marked_empty())
00794 set_zero_dim_univ();
00795 assert(OK());
00796 }
00797
00798 template <typename T>
00799 inline bool
00800 BD_Shape<T>::intersection_assign_and_minimize(const BD_Shape& y) {
00801 intersection_assign(y);
00802 shortest_path_closure_assign();
00803 return !marked_empty();
00804 }
00805
00806 template <typename T>
00807 inline void
00808 BD_Shape<T>::CC76_extrapolation_assign(const BD_Shape& y, unsigned* tp) {
00809 static N stop_points[] = {
00810 N(-2, ROUND_UP),
00811 N(-1, ROUND_UP),
00812 N( 0, ROUND_UP),
00813 N( 1, ROUND_UP),
00814 N( 2, ROUND_UP)
00815 };
00816 CC76_extrapolation_assign(y,
00817 stop_points,
00818 stop_points
00819 + sizeof(stop_points)/sizeof(stop_points[0]),
00820 tp);
00821 }
00822
00823 template <typename T>
00824 inline void
00825 BD_Shape<T>::H79_widening_assign(const BD_Shape& y, unsigned* tp) {
00826
00827 C_Polyhedron px(constraints());
00828 C_Polyhedron py(y.constraints());
00829 px.H79_widening_assign(py, tp);
00830 BD_Shape x(px);
00831 swap(x);
00832 assert(OK());
00833 }
00834
00835 template <typename T>
00836 inline void
00837 BD_Shape<T>::widening_assign(const BD_Shape& y, unsigned* tp) {
00838 H79_widening_assign(y, tp);
00839 }
00840
00841 template <typename T>
00842 inline void
00843 BD_Shape<T>::limited_H79_extrapolation_assign(const BD_Shape& y,
00844 const Constraint_System& cs,
00845 unsigned* tp) {
00846
00847 C_Polyhedron px(constraints());
00848 C_Polyhedron py(y.constraints());
00849 px.limited_H79_extrapolation_assign(py, cs, tp);
00850 BD_Shape x(px);
00851 swap(x);
00852 assert(OK());
00853 }
00854
00855 template <typename T>
00856 inline memory_size_type
00857 BD_Shape<T>::total_memory_in_bytes() const {
00858 return sizeof(*this) + external_memory_in_bytes();
00859 }
00860
00861 template <typename T>
00862 inline int32_t
00863 BD_Shape<T>::hash_code() const {
00864 return space_dimension() & 0x7fffffff;
00865 }
00866
00867 }
00868
00869 namespace std {
00870
00872 template <typename T>
00873 inline void
00874 swap(Parma_Polyhedra_Library::BD_Shape<T>& x,
00875 Parma_Polyhedra_Library::BD_Shape<T>& y) {
00876 x.swap(y);
00877 }
00878
00879 }
00880
00881 #endif // !defined(PPL_BD_Shape_inlines_hh)