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_Polyhedron_inlines_hh
00024 #define PPL_Polyhedron_inlines_hh 1
00025
00026 #include "Generator.defs.hh"
00027 #include "compiler.hh"
00028 #include <algorithm>
00029 #include <deque>
00030
00031 namespace Parma_Polyhedra_Library {
00032
00033 inline memory_size_type
00034 Polyhedron::total_memory_in_bytes() const {
00035 return sizeof(*this) + external_memory_in_bytes();
00036 }
00037
00038 inline dimension_type
00039 Polyhedron::space_dimension() const {
00040 return space_dim;
00041 }
00042
00043 inline int32_t
00044 Polyhedron::hash_code() const {
00045 return space_dimension() & 0x7fffffff;
00046 }
00047
00048 inline dimension_type
00049 Polyhedron::max_space_dimension() {
00050 using std::min;
00051
00052
00053 return min(std::numeric_limits<dimension_type>::max() - 1,
00054 min(Constraint_System::max_space_dimension(),
00055 Generator_System::max_space_dimension()
00056 )
00057 );
00058 }
00059
00060 inline Topology
00061 Polyhedron::topology() const {
00062
00063
00064 return con_sys.topology();
00065 }
00066
00067 inline bool
00068 Polyhedron::is_discrete() const {
00069 return affine_dimension() == 0;
00070 }
00071
00072 inline bool
00073 Polyhedron::is_necessarily_closed() const {
00074
00075
00076 return con_sys.is_necessarily_closed();
00077 }
00078
00079 inline void
00080 Polyhedron::upper_bound_assign(const Polyhedron& y) {
00081 poly_hull_assign(y);
00082 }
00083
00084 inline void
00085 Polyhedron::difference_assign(const Polyhedron& y) {
00086 poly_difference_assign(y);
00087 }
00088
00089 inline void
00090 Polyhedron::widening_assign(const Polyhedron& y, unsigned* tp) {
00091 H79_widening_assign(y, tp);
00092 }
00093
00094 inline
00095 Polyhedron::~Polyhedron() {
00096 }
00097
00098 inline void
00099 Polyhedron::swap(Polyhedron& y) {
00100 if (topology() != y.topology())
00101 throw_topology_incompatible("swap(y)", "y", y);
00102 std::swap(con_sys, y.con_sys);
00103 std::swap(gen_sys, y.gen_sys);
00104 std::swap(sat_c, y.sat_c);
00105 std::swap(sat_g, y.sat_g);
00106 std::swap(status, y.status);
00107 std::swap(space_dim, y.space_dim);
00108 }
00109
00110 inline bool
00111 Polyhedron::can_recycle_constraint_systems() {
00112 return true;
00113 }
00114
00115
00116 inline bool
00117 Polyhedron::can_recycle_congruence_systems() {
00118 return false;
00119 }
00120
00121 inline bool
00122 Polyhedron::marked_empty() const {
00123 return status.test_empty();
00124 }
00125
00126 inline bool
00127 Polyhedron::constraints_are_up_to_date() const {
00128 return status.test_c_up_to_date();
00129 }
00130
00131 inline bool
00132 Polyhedron::generators_are_up_to_date() const {
00133 return status.test_g_up_to_date();
00134 }
00135
00136 inline bool
00137 Polyhedron::constraints_are_minimized() const {
00138 return status.test_c_minimized();
00139 }
00140
00141 inline bool
00142 Polyhedron::generators_are_minimized() const {
00143 return status.test_g_minimized();
00144 }
00145
00146 inline bool
00147 Polyhedron::sat_c_is_up_to_date() const {
00148 return status.test_sat_c_up_to_date();
00149 }
00150
00151 inline bool
00152 Polyhedron::sat_g_is_up_to_date() const {
00153 return status.test_sat_g_up_to_date();
00154 }
00155
00156 inline bool
00157 Polyhedron::has_pending_constraints() const {
00158 return status.test_c_pending();
00159 }
00160
00161 inline bool
00162 Polyhedron::has_pending_generators() const {
00163 return status.test_g_pending();
00164 }
00165
00166 inline bool
00167 Polyhedron::has_something_pending() const {
00168 return status.test_c_pending() || status.test_g_pending();
00169 }
00170
00171 inline bool
00172 Polyhedron::can_have_something_pending() const {
00173 return constraints_are_minimized()
00174 && generators_are_minimized()
00175 && (sat_c_is_up_to_date() || sat_g_is_up_to_date());
00176 }
00177
00178 inline bool
00179 Polyhedron::is_empty() const {
00180 if (marked_empty())
00181 return true;
00182
00183
00184
00185 if (generators_are_up_to_date() && !has_pending_constraints())
00186 return false;
00187 return !minimize();
00188 }
00189
00190 inline void
00191 Polyhedron::set_constraints_up_to_date() {
00192 status.set_c_up_to_date();
00193 }
00194
00195 inline void
00196 Polyhedron::set_generators_up_to_date() {
00197 status.set_g_up_to_date();
00198 }
00199
00200 inline void
00201 Polyhedron::set_constraints_minimized() {
00202 set_constraints_up_to_date();
00203 status.set_c_minimized();
00204 }
00205
00206 inline void
00207 Polyhedron::set_generators_minimized() {
00208 set_generators_up_to_date();
00209 status.set_g_minimized();
00210 }
00211
00212 inline void
00213 Polyhedron::set_constraints_pending() {
00214 status.set_c_pending();
00215 }
00216
00217 inline void
00218 Polyhedron::set_generators_pending() {
00219 status.set_g_pending();
00220 }
00221
00222 inline void
00223 Polyhedron::set_sat_c_up_to_date() {
00224 status.set_sat_c_up_to_date();
00225 }
00226
00227 inline void
00228 Polyhedron::set_sat_g_up_to_date() {
00229 status.set_sat_g_up_to_date();
00230 }
00231
00232 inline void
00233 Polyhedron::clear_empty() {
00234 status.reset_empty();
00235 }
00236
00237 inline void
00238 Polyhedron::clear_constraints_minimized() {
00239 status.reset_c_minimized();
00240 }
00241
00242 inline void
00243 Polyhedron::clear_generators_minimized() {
00244 status.reset_g_minimized();
00245 }
00246
00247 inline void
00248 Polyhedron::clear_pending_constraints() {
00249 status.reset_c_pending();
00250 }
00251
00252 inline void
00253 Polyhedron::clear_pending_generators() {
00254 status.reset_g_pending();
00255 }
00256
00257 inline void
00258 Polyhedron::clear_sat_c_up_to_date() {
00259 status.reset_sat_c_up_to_date();
00260
00261 }
00262
00263 inline void
00264 Polyhedron::clear_sat_g_up_to_date() {
00265 status.reset_sat_g_up_to_date();
00266
00267 }
00268
00269 inline void
00270 Polyhedron::clear_constraints_up_to_date() {
00271 clear_pending_constraints();
00272 clear_constraints_minimized();
00273 clear_sat_c_up_to_date();
00274 clear_sat_g_up_to_date();
00275 status.reset_c_up_to_date();
00276
00277 }
00278
00279 inline void
00280 Polyhedron::clear_generators_up_to_date() {
00281 clear_pending_generators();
00282 clear_generators_minimized();
00283 clear_sat_c_up_to_date();
00284 clear_sat_g_up_to_date();
00285 status.reset_g_up_to_date();
00286
00287 }
00288
00289 inline bool
00290 Polyhedron::process_pending() const {
00291 assert(space_dim > 0 && !marked_empty());
00292 assert(has_something_pending());
00293
00294 Polyhedron& x = const_cast<Polyhedron&>(*this);
00295
00296 if (x.has_pending_constraints())
00297 return x.process_pending_constraints();
00298
00299 assert(x.has_pending_generators());
00300 x.process_pending_generators();
00301 return true;
00302 }
00303
00304 inline bool
00305 Polyhedron::bounds_from_above(const Linear_Expression& expr) const {
00306 return bounds(expr, true);
00307 }
00308
00309 inline bool
00310 Polyhedron::bounds_from_below(const Linear_Expression& expr) const {
00311 return bounds(expr, false);
00312 }
00313
00314 inline bool
00315 Polyhedron::maximize(const Linear_Expression& expr,
00316 Coefficient& sup_n, Coefficient& sup_d,
00317 bool& maximum) const {
00318 Generator g(point());
00319 return max_min(expr, true, sup_n, sup_d, maximum, g);
00320 }
00321
00322 inline bool
00323 Polyhedron::maximize(const Linear_Expression& expr,
00324 Coefficient& sup_n, Coefficient& sup_d, bool& maximum,
00325 Generator& g) const {
00326 return max_min(expr, true, sup_n, sup_d, maximum, g);
00327 }
00328
00329 inline bool
00330 Polyhedron::minimize(const Linear_Expression& expr,
00331 Coefficient& inf_n, Coefficient& inf_d,
00332 bool& minimum) const {
00333 Generator g(point());
00334 return max_min(expr, false, inf_n, inf_d, minimum, g);
00335 }
00336
00337 inline bool
00338 Polyhedron::minimize(const Linear_Expression& expr,
00339 Coefficient& inf_n, Coefficient& inf_d, bool& minimum,
00340 Generator& g) const {
00341 return max_min(expr, false, inf_n, inf_d, minimum, g);
00342 }
00343
00344 inline Constraint_System
00345 Polyhedron::simplified_constraints() const {
00346 assert(constraints_are_up_to_date());
00347 Constraint_System cs(con_sys);
00348 if (cs.num_pending_rows() > 0)
00349 cs.unset_pending_rows();
00350 if (has_pending_constraints() || !constraints_are_minimized())
00351 cs.simplify();
00352 return cs;
00353 }
00354
00355 inline Congruence_System
00356 Polyhedron::congruences() const {
00357 return Congruence_System(minimized_constraints());
00358 }
00359
00360 inline Congruence_System
00361 Polyhedron::minimized_congruences() const {
00362 return Congruence_System(minimized_constraints());
00363 }
00364
00365 inline Grid_Generator_System
00366 Polyhedron::minimized_grid_generators() const {
00367 return grid_generators();
00368 }
00369
00370 inline bool
00371 Polyhedron::add_congruence_and_minimize(const Congruence& cg) {
00372 add_congruence(cg);
00373 return minimize();
00374 }
00375
00376 inline bool
00377 Polyhedron::add_congruences_and_minimize(const Congruence_System& cgs) {
00378 add_congruences(cgs);
00379 return minimize();
00380 }
00381
00382 inline void
00383 Polyhedron::add_recycled_congruences(Congruence_System& cgs) {
00384 add_congruences(cgs);
00385 }
00386
00387 inline bool
00388 Polyhedron::add_recycled_congruences_and_minimize(Congruence_System& cgs) {
00389 return add_congruences_and_minimize(cgs);
00390 }
00391
00393 inline bool
00394 operator!=(const Polyhedron& x, const Polyhedron& y) {
00395 return !(x == y);
00396 }
00397
00398 inline bool
00399 Polyhedron::strictly_contains(const Polyhedron& y) const {
00400 const Polyhedron& x = *this;
00401 return x.contains(y) && !y.contains(x);
00402 }
00403
00404 namespace Interfaces {
00405
00406 inline bool
00407 is_necessarily_closed_for_interfaces(const Polyhedron& ph) {
00408 return ph.is_necessarily_closed();
00409 }
00410
00411 }
00412
00413 }
00414
00415 namespace std {
00416
00418 inline void
00419 swap(Parma_Polyhedra_Library::Polyhedron& x,
00420 Parma_Polyhedra_Library::Polyhedron& y) {
00421 x.swap(y);
00422 }
00423
00424 }
00425
00426 #endif // !defined(PPL_Polyhedron_inlines_hh)