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