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 "Interval.defs.hh"
00027 #include "Generator.defs.hh"
00028 #include "LP_Problem.defs.hh"
00029 #include <algorithm>
00030 #include <deque>
00031
00032 namespace Parma_Polyhedra_Library {
00033
00034 inline memory_size_type
00035 Polyhedron::total_memory_in_bytes() const {
00036 return sizeof(*this) + external_memory_in_bytes();
00037 }
00038
00039 inline dimension_type
00040 Polyhedron::max_space_dimension() {
00041 using std::min;
00042
00043
00044 return min(std::numeric_limits<dimension_type>::max() - 1,
00045 min(Constraint_System::max_space_dimension(),
00046 Generator_System::max_space_dimension()
00047 )
00048 );
00049 }
00050
00051 inline Topology
00052 Polyhedron::topology() const {
00053
00054
00055 return con_sys.topology();
00056 }
00057
00058 inline bool
00059 Polyhedron::is_necessarily_closed() const {
00060
00061
00062 return con_sys.is_necessarily_closed();
00063 }
00064
00065 inline dimension_type
00066 Polyhedron::space_dimension() const {
00067 return space_dim;
00068 }
00069
00070 inline void
00071 Polyhedron::upper_bound_assign(const Polyhedron& y) {
00072 poly_hull_assign(y);
00073 }
00074
00075 inline void
00076 Polyhedron::difference_assign(const Polyhedron& y) {
00077 poly_difference_assign(y);
00078 }
00079
00080 inline
00081 Polyhedron::~Polyhedron() {
00082 }
00083
00084 inline void
00085 Polyhedron::swap(Polyhedron& y) {
00086 if (topology() != y.topology())
00087 throw_topology_incompatible("swap(y)", "y", y);
00088 std::swap(con_sys, y.con_sys);
00089 std::swap(gen_sys, y.gen_sys);
00090 std::swap(sat_c, y.sat_c);
00091 std::swap(sat_g, y.sat_g);
00092 std::swap(status, y.status);
00093 std::swap(space_dim, y.space_dim);
00094 }
00095
00096 }
00097
00099 inline void
00100 std::swap(Parma_Polyhedra_Library::Polyhedron& x,
00101 Parma_Polyhedra_Library::Polyhedron& y) {
00102 x.swap(y);
00103 }
00104
00105 namespace Parma_Polyhedra_Library {
00106
00107 inline bool
00108 Polyhedron::marked_empty() const {
00109 return status.test_empty();
00110 }
00111
00112 inline bool
00113 Polyhedron::constraints_are_up_to_date() const {
00114 return status.test_c_up_to_date();
00115 }
00116
00117 inline bool
00118 Polyhedron::generators_are_up_to_date() const {
00119 return status.test_g_up_to_date();
00120 }
00121
00122 inline bool
00123 Polyhedron::constraints_are_minimized() const {
00124 return status.test_c_minimized();
00125 }
00126
00127 inline bool
00128 Polyhedron::generators_are_minimized() const {
00129 return status.test_g_minimized();
00130 }
00131
00132 inline bool
00133 Polyhedron::sat_c_is_up_to_date() const {
00134 return status.test_sat_c_up_to_date();
00135 }
00136
00137 inline bool
00138 Polyhedron::sat_g_is_up_to_date() const {
00139 return status.test_sat_g_up_to_date();
00140 }
00141
00142 inline bool
00143 Polyhedron::has_pending_constraints() const {
00144 return status.test_c_pending();
00145 }
00146
00147 inline bool
00148 Polyhedron::has_pending_generators() const {
00149 return status.test_g_pending();
00150 }
00151
00152 inline bool
00153 Polyhedron::has_something_pending() const {
00154 return status.test_c_pending() || status.test_g_pending();
00155 }
00156
00157 inline bool
00158 Polyhedron::can_have_something_pending() const {
00159 return constraints_are_minimized()
00160 && generators_are_minimized()
00161 && (sat_c_is_up_to_date() || sat_g_is_up_to_date());
00162 }
00163
00164 inline void
00165 Polyhedron::set_constraints_up_to_date() {
00166 status.set_c_up_to_date();
00167 }
00168
00169 inline void
00170 Polyhedron::set_generators_up_to_date() {
00171 status.set_g_up_to_date();
00172 }
00173
00174 inline void
00175 Polyhedron::set_constraints_minimized() {
00176 set_constraints_up_to_date();
00177 status.set_c_minimized();
00178 }
00179
00180 inline void
00181 Polyhedron::set_generators_minimized() {
00182 set_generators_up_to_date();
00183 status.set_g_minimized();
00184 }
00185
00186 inline void
00187 Polyhedron::set_constraints_pending() {
00188 status.set_c_pending();
00189 }
00190
00191 inline void
00192 Polyhedron::set_generators_pending() {
00193 status.set_g_pending();
00194 }
00195
00196 inline void
00197 Polyhedron::set_sat_c_up_to_date() {
00198 status.set_sat_c_up_to_date();
00199 }
00200
00201 inline void
00202 Polyhedron::set_sat_g_up_to_date() {
00203 status.set_sat_g_up_to_date();
00204 }
00205
00206 inline void
00207 Polyhedron::clear_empty() {
00208 status.reset_empty();
00209 }
00210
00211 inline void
00212 Polyhedron::clear_constraints_minimized() {
00213 status.reset_c_minimized();
00214 }
00215
00216 inline void
00217 Polyhedron::clear_generators_minimized() {
00218 status.reset_g_minimized();
00219 }
00220
00221 inline void
00222 Polyhedron::clear_pending_constraints() {
00223 status.reset_c_pending();
00224 }
00225
00226 inline void
00227 Polyhedron::clear_pending_generators() {
00228 status.reset_g_pending();
00229 }
00230
00231 inline void
00232 Polyhedron::clear_sat_c_up_to_date() {
00233 status.reset_sat_c_up_to_date();
00234
00235 }
00236
00237 inline void
00238 Polyhedron::clear_sat_g_up_to_date() {
00239 status.reset_sat_g_up_to_date();
00240
00241 }
00242
00243 inline void
00244 Polyhedron::clear_constraints_up_to_date() {
00245 clear_pending_constraints();
00246 clear_constraints_minimized();
00247 clear_sat_c_up_to_date();
00248 clear_sat_g_up_to_date();
00249 status.reset_c_up_to_date();
00250
00251 }
00252
00253 inline void
00254 Polyhedron::clear_generators_up_to_date() {
00255 clear_pending_generators();
00256 clear_generators_minimized();
00257 clear_sat_c_up_to_date();
00258 clear_sat_g_up_to_date();
00259 status.reset_g_up_to_date();
00260
00261 }
00262
00263 inline bool
00264 Polyhedron::process_pending() const {
00265 assert(space_dim > 0 && !marked_empty());
00266 assert(has_something_pending());
00267
00268 Polyhedron& x = const_cast<Polyhedron&>(*this);
00269
00270 if (x.has_pending_constraints())
00271 return x.process_pending_constraints();
00272
00273 assert(x.has_pending_generators());
00274 x.process_pending_generators();
00275 return true;
00276 }
00277
00278 inline bool
00279 Polyhedron::is_empty() const {
00280 if (marked_empty())
00281 return true;
00282
00283
00284
00285 if (generators_are_up_to_date() && !has_pending_constraints())
00286 return false;
00287 return !minimize();
00288 }
00289
00290 inline bool
00291 Polyhedron::bounds_from_above(const Linear_Expression& expr) const {
00292 return bounds(expr, true);
00293 }
00294
00295 inline bool
00296 Polyhedron::bounds_from_below(const Linear_Expression& expr) const {
00297 return bounds(expr, false);
00298 }
00299
00300 inline bool
00301 Polyhedron::maximize(const Linear_Expression& expr,
00302 Coefficient& sup_n, Coefficient& sup_d,
00303 bool& maximum) const {
00304 Generator g(point());
00305 return max_min(expr, true, sup_n, sup_d, maximum, g);
00306 }
00307
00308 inline bool
00309 Polyhedron::maximize(const Linear_Expression& expr,
00310 Coefficient& sup_n, Coefficient& sup_d, bool& maximum,
00311 Generator& g) const {
00312 return max_min(expr, true, sup_n, sup_d, maximum, g);
00313 }
00314
00315 inline bool
00316 Polyhedron::minimize(const Linear_Expression& expr,
00317 Coefficient& inf_n, Coefficient& inf_d,
00318 bool& minimum) const {
00319 Generator g(point());
00320 return max_min(expr, false, inf_n, inf_d, minimum, g);
00321 }
00322
00323 inline bool
00324 Polyhedron::minimize(const Linear_Expression& expr,
00325 Coefficient& inf_n, Coefficient& inf_d, bool& minimum,
00326 Generator& g) const {
00327 return max_min(expr, false, inf_n, inf_d, minimum, g);
00328 }
00329
00331 inline bool
00332 operator!=(const Polyhedron& x, const Polyhedron& y) {
00333 return !(x == y);
00334 }
00335
00336 inline bool
00337 Polyhedron::strictly_contains(const Polyhedron& y) const {
00338 const Polyhedron& x = *this;
00339 return x.contains(y) && !y.contains(x);
00340 }
00341
00342 }
00343
00344 #endif // !defined(PPL_Polyhedron_inlines_hh)