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
00025 #include "Generator.defs.hh"
00026
00027 #include "Variable.defs.hh"
00028 #include <iostream>
00029 #include <sstream>
00030 #include <stdexcept>
00031
00032 namespace PPL = Parma_Polyhedra_Library;
00033
00034 void
00035 PPL::Generator::throw_dimension_incompatible(const char* method,
00036 const char* name_var,
00037 const Variable v) const {
00038 std::ostringstream s;
00039 s << "PPL::Generator::" << method << ":" << std::endl
00040 << "this->space_dimension() == " << space_dimension() << ", "
00041 << name_var << ".space_dimension() == " << v.space_dimension() << ".";
00042 throw std::invalid_argument(s.str());
00043 }
00044
00045 void
00046 PPL::Generator::throw_invalid_argument(const char* method,
00047 const char* reason) const {
00048 std::ostringstream s;
00049 s << "PPL::Generator::" << method << ":" << std::endl
00050 << reason << ".";
00051 throw std::invalid_argument(s.str());
00052 }
00053
00054 PPL::Generator
00055 PPL::Generator::point(const Linear_Expression& e,
00056 Coefficient_traits::const_reference d) {
00057 if (d == 0)
00058 throw std::invalid_argument("PPL::point(e, d):\n"
00059 "d == 0.");
00060 Linear_Expression ec = e;
00061 Generator g(ec, Generator::POINT, NECESSARILY_CLOSED);
00062 g[0] = d;
00063
00064
00065
00066
00067 if (d < 0)
00068 for (dimension_type i = g.size(); i-- > 0; )
00069 neg_assign(g[i]);
00070
00071
00072 g.normalize();
00073 return g;
00074 }
00075
00076 PPL::Generator
00077 PPL::Generator::closure_point(const Linear_Expression& e,
00078 Coefficient_traits::const_reference d) {
00079 if (d == 0)
00080 throw std::invalid_argument("PPL::closure_point(e, d):\n"
00081 "d == 0.");
00082
00083 Linear_Expression ec = 0 * Variable(e.space_dimension());
00084 ec += e;
00085
00086 Generator g = point(ec, d);
00087
00088 g.set_not_necessarily_closed();
00089
00090 g.normalize();
00091 return g;
00092 }
00093
00094 PPL::Generator
00095 PPL::Generator::ray(const Linear_Expression& e) {
00096
00097 if (e.all_homogeneous_terms_are_zero())
00098 throw std::invalid_argument("PPL::ray(e):\n"
00099 "e == 0, but the origin cannot be a ray.");
00100
00101 Linear_Expression ec = e;
00102 Generator g(ec, Generator::RAY, NECESSARILY_CLOSED);
00103 g[0] = 0;
00104
00105 g.normalize();
00106 return g;
00107 }
00108
00109 PPL::Generator
00110 PPL::Generator::line(const Linear_Expression& e) {
00111
00112 if (e.all_homogeneous_terms_are_zero())
00113 throw std::invalid_argument("PPL::line(e):\n"
00114 "e == 0, but the origin cannot be a line.");
00115
00116 Linear_Expression ec = e;
00117 Generator g(ec, Generator::LINE, NECESSARILY_CLOSED);
00118 g[0] = 0;
00119
00120 g.strong_normalize();
00121 return g;
00122 }
00123
00124 bool
00125 PPL::Generator::is_equivalent_to(const Generator& y) const {
00126 const Generator& x = *this;
00127 const dimension_type x_space_dim = x.space_dimension();
00128 if (x_space_dim != y.space_dimension())
00129 return false;
00130
00131 const Type x_type = x.type();
00132 if (x_type != y.type())
00133 return false;
00134
00135 if (x_type == POINT
00136 && !(x.is_necessarily_closed() && y.is_necessarily_closed())) {
00137
00138
00139
00140 Linear_Expression x_expr(x);
00141 Linear_Expression y_expr(y);
00142
00143 x_expr.normalize();
00144 y_expr.normalize();
00145
00146 for (dimension_type i = x_space_dim + 1; i-- > 0; )
00147 if (x_expr[i] != y_expr[i])
00148 return false;
00149 return true;
00150 }
00151
00152
00153
00154 for (dimension_type i = x_space_dim + 1; i-- > 0; )
00155 if (x[i] != y[i])
00156 return false;
00157 return true;
00158 }
00159
00160 const PPL::Generator* PPL::Generator::zero_dim_point_p = 0;
00161 const PPL::Generator* PPL::Generator::zero_dim_closure_point_p = 0;
00162
00163 void
00164 PPL::Generator::initialize() {
00165 assert(zero_dim_point_p == 0);
00166 zero_dim_point_p
00167 = new Generator(point());
00168
00169 assert(zero_dim_closure_point_p == 0);
00170 zero_dim_closure_point_p
00171 = new Generator(closure_point());
00172 }
00173
00174 void
00175 PPL::Generator::finalize() {
00176 assert(zero_dim_point_p != 0);
00177 delete zero_dim_point_p;
00178 zero_dim_point_p = 0;
00179
00180 assert(zero_dim_closure_point_p != 0);
00181 delete zero_dim_closure_point_p;
00182 zero_dim_closure_point_p = 0;
00183 }
00184
00186 std::ostream&
00187 PPL::IO_Operators::operator<<(std::ostream& s, const Generator& g) {
00188 bool needed_divisor = false;
00189 bool extra_parentheses = false;
00190 const dimension_type num_variables = g.space_dimension();
00191 Generator::Type t = g.type();
00192 switch (t) {
00193 case Generator::LINE:
00194 s << "l(";
00195 break;
00196 case Generator::RAY:
00197 s << "r(";
00198 break;
00199 case Generator::POINT:
00200 s << "p(";
00201 goto any_point;
00202 case Generator::CLOSURE_POINT:
00203 s << "c(";
00204 any_point:
00205 if (g[0] != 1) {
00206 needed_divisor = true;
00207 dimension_type num_non_zero_coefficients = 0;
00208 for (dimension_type v = 0; v < num_variables; ++v)
00209 if (g[v+1] != 0)
00210 if (++num_non_zero_coefficients > 1) {
00211 extra_parentheses = true;
00212 s << "(";
00213 break;
00214 }
00215 }
00216 break;
00217 }
00218
00219 TEMP_INTEGER(gv);
00220 bool first = true;
00221 for (dimension_type v = 0; v < num_variables; ++v) {
00222 gv = g[v+1];
00223 if (gv != 0) {
00224 if (!first) {
00225 if (gv > 0)
00226 s << " + ";
00227 else {
00228 s << " - ";
00229 neg_assign(gv);
00230 }
00231 }
00232 else
00233 first = false;
00234 if (gv == -1)
00235 s << "-";
00236 else if (gv != 1)
00237 s << gv << "*";
00238 s << PPL::Variable(v);
00239 }
00240 }
00241 if (first)
00242
00243 s << 0;
00244 if (extra_parentheses)
00245 s << ")";
00246 if (needed_divisor)
00247 s << "/" << g[0];
00248 s << ")";
00249 return s;
00250 }
00251
00253 std::ostream&
00254 PPL::IO_Operators::operator<<(std::ostream& s, const Generator::Type& t) {
00255 const char* n = 0;
00256 switch (t) {
00257 case Generator::LINE:
00258 n = "LINE";
00259 break;
00260 case Generator::RAY:
00261 n = "RAY";
00262 break;
00263 case Generator::POINT:
00264 n = "POINT";
00265 break;
00266 case Generator::CLOSURE_POINT:
00267 n = "CLOSURE_POINT";
00268 break;
00269 }
00270 s << n;
00271 return s;
00272 }
00273
00274 bool
00275 PPL::Generator::is_matching_closure_point(const Generator& p) const {
00276 assert(topology() == p.topology()
00277 && space_dimension() == p.space_dimension()
00278 && type() == CLOSURE_POINT
00279 && p.type() == POINT);
00280 const Generator& cp = *this;
00281 if (cp[0] == p[0]) {
00282
00283
00284 for (dimension_type i = cp.size() - 2; i > 0; --i)
00285 if (cp[i] != p[i])
00286 return false;
00287 return true;
00288 }
00289 else {
00290
00291
00292 TEMP_INTEGER(gcd);
00293 gcd_assign(gcd, cp[0], p[0]);
00294 const bool rel_prime = (gcd == 1);
00295 TEMP_INTEGER(cp_0_scaled);
00296 TEMP_INTEGER(p_0_scaled);
00297 if (!rel_prime) {
00298 exact_div_assign(cp_0_scaled, cp[0], gcd);
00299 exact_div_assign(p_0_scaled, p[0], gcd);
00300 }
00301 const Coefficient& cp_div = rel_prime ? cp[0] : cp_0_scaled;
00302 const Coefficient& p_div = rel_prime ? p[0] : p_0_scaled;
00303 TEMP_INTEGER(prod1);
00304 TEMP_INTEGER(prod2);
00305 for (dimension_type i = cp.size() - 2; i > 0; --i) {
00306 prod1 = cp[i] * p_div;
00307 prod2 = p[i] * cp_div;
00308 if (prod1 != prod2)
00309 return false;
00310 }
00311 return true;
00312 }
00313 }
00314
00315 PPL_OUTPUT_DEFINITIONS(Generator)
00316
00317 bool
00318 PPL::Generator::OK() const {
00319
00320 if (!Linear_Row::OK())
00321 return false;
00322
00323
00324 const dimension_type min_size = is_necessarily_closed() ? 1 : 2;
00325 if (size() < min_size) {
00326 #ifndef NDEBUG
00327 std::cerr << "Generator has fewer coefficients than the minimum "
00328 << "allowed by its topology:"
00329 << std::endl
00330 << "size is " << size()
00331 << ", minimum is " << min_size << "."
00332 << std::endl;
00333 #endif
00334 return false;
00335 }
00336
00337
00338 const Generator& g = *this;
00339 Generator tmp = g;
00340 tmp.strong_normalize();
00341 if (tmp != g) {
00342 #ifndef NDEBUG
00343 std::cerr << "Generators should be strongly normalized!"
00344 << std::endl;
00345 #endif
00346 return false;
00347 }
00348
00349 switch (g.type()) {
00350 case LINE:
00351
00352 case RAY:
00353 if (g[0] != 0) {
00354 #ifndef NDEBUG
00355 std::cerr << "Lines must have a zero inhomogeneous term!"
00356 << std::endl;
00357 #endif
00358 return false;
00359 }
00360 if (!g.is_necessarily_closed() && g[size() - 1] != 0) {
00361 #ifndef NDEBUG
00362 std::cerr << "Lines and rays must have a zero coefficient "
00363 << "for the epsilon dimension!"
00364 << std::endl;
00365 #endif
00366 return false;
00367 }
00368
00369
00370 if (g.all_homogeneous_terms_are_zero()) {
00371 #ifndef NDEBUG
00372 std::cerr << "The origin of the vector space cannot be a line or a ray!"
00373 << std::endl;
00374 #endif
00375 return false;
00376 }
00377 break;
00378
00379 case POINT:
00380 if (g[0] <= 0) {
00381 #ifndef NDEBUG
00382 std::cerr << "Points must have a positive divisor!"
00383 << std::endl;
00384 #endif
00385 return false;
00386 }
00387 if (!g.is_necessarily_closed())
00388 if (g[size() - 1] <= 0) {
00389 #ifndef NDEBUG
00390 std::cerr << "In the NNC topology, points must have epsilon > 0"
00391 << std::endl;
00392 #endif
00393 return false;
00394 }
00395 break;
00396
00397 case CLOSURE_POINT:
00398 if (g[0] <= 0) {
00399 #ifndef NDEBUG
00400 std::cerr << "Closure points must have a positive divisor!"
00401 << std::endl;
00402 #endif
00403 return false;
00404 }
00405 break;
00406 }
00407
00408
00409 return true;
00410 }