00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <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
00161 std::ostream&
00162 PPL::IO_Operators::operator<<(std::ostream& s, const Generator& g) {
00163 bool needed_divisor = false;
00164 bool extra_parentheses = false;
00165 const int num_variables = g.space_dimension();
00166 Generator::Type t = g.type();
00167 switch (t) {
00168 case Generator::LINE:
00169 s << "l(";
00170 break;
00171 case Generator::RAY:
00172 s << "r(";
00173 break;
00174 case Generator::POINT:
00175 s << "p(";
00176 goto any_point;
00177 case Generator::CLOSURE_POINT:
00178 s << "c(";
00179 any_point:
00180 if (g[0] != 1) {
00181 needed_divisor = true;
00182 int num_non_zero_coefficients = 0;
00183 for (int v = 0; v < num_variables; ++v)
00184 if (g[v+1] != 0)
00185 if (++num_non_zero_coefficients > 1) {
00186 extra_parentheses = true;
00187 s << "(";
00188 break;
00189 }
00190 }
00191 break;
00192 }
00193
00194 bool first = true;
00195 for (int v = 0; v < num_variables; ++v) {
00196 Coefficient gv = g[v+1];
00197 if (gv != 0) {
00198 if (!first) {
00199 if (gv > 0)
00200 s << " + ";
00201 else {
00202 s << " - ";
00203 neg_assign(gv);
00204 }
00205 }
00206 else
00207 first = false;
00208 if (gv == -1)
00209 s << "-";
00210 else if (gv != 1)
00211 s << gv << "*";
00212 s << PPL::Variable(v);
00213 }
00214 }
00215 if (first)
00216
00217 s << 0;
00218 if (extra_parentheses)
00219 s << ")";
00220 if (needed_divisor)
00221 s << "/" << g[0];
00222 s << ")";
00223 return s;
00224 }
00225
00227 std::ostream&
00228 PPL::IO_Operators::operator<<(std::ostream& s, const Generator::Type& t) {
00229 const char* n = 0;
00230 switch (t) {
00231 case Generator::LINE:
00232 n = "LINE";
00233 break;
00234 case Generator::RAY:
00235 n = "RAY";
00236 break;
00237 case Generator::POINT:
00238 n = "POINT";
00239 break;
00240 case Generator::CLOSURE_POINT:
00241 n = "CLOSURE_POINT";
00242 break;
00243 }
00244 s << n;
00245 return s;
00246 }
00247
00248 bool
00249 PPL::Generator::is_matching_closure_point(const Generator& p) const {
00250 assert(topology() == p.topology()
00251 && space_dimension() == p.space_dimension()
00252 && type() == CLOSURE_POINT
00253 && p.type() == POINT);
00254 const Generator& cp = *this;
00255 if (cp[0] == p[0]) {
00256
00257
00258 for (dimension_type i = cp.size() - 2; i > 0; --i)
00259 if (cp[i] != p[i])
00260 return false;
00261 return true;
00262 }
00263 else {
00264
00265
00266 TEMP_INTEGER(gcd);
00267 gcd_assign(gcd, cp[0], p[0]);
00268 const bool rel_prime = (gcd == 1);
00269 TEMP_INTEGER(cp_0_scaled);
00270 TEMP_INTEGER(p_0_scaled);
00271 if (!rel_prime) {
00272 exact_div_assign(cp_0_scaled, cp[0], gcd);
00273 exact_div_assign(p_0_scaled, p[0], gcd);
00274 }
00275 const Coefficient& cp_div = rel_prime ? cp[0] : cp_0_scaled;
00276 const Coefficient& p_div = rel_prime ? p[0] : p_0_scaled;
00277 TEMP_INTEGER(prod1);
00278 TEMP_INTEGER(prod2);
00279 for (dimension_type i = cp.size() - 2; i > 0; --i) {
00280 prod1 = cp[i] * p_div;
00281 prod2 = p[i] * cp_div;
00282 if (prod1 != prod2)
00283 return false;
00284 }
00285 return true;
00286 }
00287 }
00288
00289 PPL_OUTPUT_DEFINITIONS(Generator);
00290
00291 bool
00292 PPL::Generator::OK() const {
00293 const Generator& g = *this;
00294
00295
00296 const dimension_type min_size = is_necessarily_closed() ? 1 : 2;
00297 if (size() < min_size) {
00298 #ifndef NDEBUG
00299 std::cerr << "Generator has fewer coefficients than the minimum "
00300 << "allowed by its topology:"
00301 << std::endl
00302 << "size is " << size()
00303 << ", minimum is " << min_size << "."
00304 << std::endl;
00305 #endif
00306 return false;
00307 }
00308
00309
00310 Generator tmp = g;
00311 tmp.strong_normalize();
00312 if (tmp != g) {
00313 #ifndef NDEBUG
00314 std::cerr << "Generators should be strongly normalized!"
00315 << std::endl;
00316 #endif
00317 return false;
00318 }
00319
00320 switch (g.type()) {
00321 case LINE:
00322
00323 case RAY:
00324 if (g[0] != 0) {
00325 #ifndef NDEBUG
00326 std::cerr << "Lines must have a zero inhomogeneous term!"
00327 << std::endl;
00328 #endif
00329 return false;
00330 }
00331 if (!g.is_necessarily_closed() && g[size() - 1] != 0) {
00332 #ifndef NDEBUG
00333 std::cerr << "Lines and rays must have a zero coefficient "
00334 << "for the epsilon dimension!"
00335 << std::endl;
00336 #endif
00337 return false;
00338 }
00339
00340
00341 if (g.all_homogeneous_terms_are_zero()) {
00342 #ifndef NDEBUG
00343 std::cerr << "The origin of the vector space cannot be a line or a ray!"
00344 << std::endl;
00345 #endif
00346 return false;
00347 }
00348 break;
00349
00350 case POINT:
00351 if (g[0] <= 0) {
00352 #ifndef NDEBUG
00353 std::cerr << "Points must have a positive divisor!"
00354 << std::endl;
00355 #endif
00356 return false;
00357 }
00358 if (!g.is_necessarily_closed())
00359 if (g[size() - 1] <= 0) {
00360 #ifndef NDEBUG
00361 std::cerr << "In the NNC topology, points must have epsilon > 0"
00362 << std::endl;
00363 #endif
00364 return false;
00365 }
00366 break;
00367
00368 case CLOSURE_POINT:
00369 if (g[0] <= 0) {
00370 #ifndef NDEBUG
00371 std::cerr << "Closure points must have a positive divisor!"
00372 << std::endl;
00373 #endif
00374 return false;
00375 }
00376 break;
00377 }
00378
00379
00380 return true;
00381 }