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 "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.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::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::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 bool
00132 PPL::Grid_Generator::is_equivalent_to(const Grid_Generator& y) const {
00133 const Grid_Generator& x = *this;
00134 dimension_type x_space_dim = x.space_dimension();
00135 if (x_space_dim != y.space_dimension())
00136 return false;
00137
00138 const Type x_type = x.type();
00139 if (x_type != y.type())
00140 return false;
00141
00142 Grid_Generator tem(*this);
00143 Grid_Generator tem_y(y);
00144 dimension_type& last = x_space_dim;
00145 ++last;
00146 if (x_type == POINT || x_type == LINE) {
00147 tem[last] = 0;
00148 tem_y[last] = 0;
00149 }
00150
00151 tem.Row::normalize();
00152 tem_y.Row::normalize();
00153
00154 while (last-- > 0)
00155 if (tem[last] != tem_y[last])
00156 return false;
00157 return true;
00158 }
00159
00160 bool
00161 PPL::Grid_Generator::is_equal_to(const Grid_Generator& y) const {
00162 if (type() != y.type())
00163 return false;
00164 for (dimension_type col = (is_parameter() ? size() : size() - 1);
00165 col-- > 0; )
00166 if (Generator::operator[](col) != y.Generator::operator[](col))
00167 return false;
00168 return true;
00169 }
00170
00171 bool
00172 PPL::Grid_Generator::all_homogeneous_terms_are_zero() const {
00173
00174 for (dimension_type i = size() - 1; --i > 0; )
00175 if (operator[](i) != 0)
00176 return false;
00177 return true;
00178 }
00179
00180 void
00181 PPL::Grid_Generator::scale_to_divisor(Coefficient_traits::const_reference d) {
00182 if (is_parameter_or_point()) {
00183 if (d == 0)
00184 throw std::invalid_argument("PPL::Grid_Generator::scale_to_divisor(d):\n"
00185 "d == 0.");
00186
00187 TEMP_INTEGER(factor);
00188 factor = d / divisor();
00189 divisor() = d;
00190 assert(factor > 0);
00191 if (factor > 1)
00192 for (dimension_type col = size() - 2; col >= 1; --col)
00193 Generator::operator[](col) *= factor;
00194 }
00195 }
00196
00198 std::ostream&
00199 PPL::IO_Operators::operator<<(std::ostream& s, const Grid_Generator& g) {
00200 bool need_divisor = false;
00201 bool extra_parentheses = false;
00202 const int num_variables = g.space_dimension();
00203 Grid_Generator::Type t = g.type();
00204 switch (t) {
00205 case Grid_Generator::LINE:
00206 s << "l(";
00207 break;
00208 case Grid_Generator::PARAMETER:
00209 s << "r(";
00210 if (g[num_variables + 1] == 1)
00211 break;
00212 goto any_point;
00213 case Grid_Generator::POINT:
00214 s << "p(";
00215 if (g[0] > 1) {
00216 any_point:
00217 need_divisor = true;
00218 int num_non_zero_coefficients = 0;
00219 for (int v = 0; v < num_variables; ++v)
00220 if (g[v+1] != 0)
00221 if (++num_non_zero_coefficients > 1) {
00222 extra_parentheses = true;
00223 s << "(";
00224 break;
00225 }
00226 }
00227 break;
00228 }
00229
00230 bool first = true;
00231 for (int v = 0; v < num_variables; ++v) {
00232 Coefficient gv = g[v+1];
00233 if (gv != 0) {
00234 if (!first) {
00235 if (gv > 0)
00236 s << " + ";
00237 else {
00238 s << " - ";
00239 neg_assign(gv);
00240 }
00241 }
00242 else
00243 first = false;
00244 if (gv == -1)
00245 s << "-";
00246 else if (gv != 1)
00247 s << gv << "*";
00248 s << PPL::Variable(v);
00249 }
00250 }
00251 if (first)
00252
00253 s << 0;
00254 if (extra_parentheses)
00255 s << ")";
00256 if (need_divisor)
00257 s << "/" << g.divisor();
00258 s << ")";
00259 return s;
00260 }
00261
00263 std::ostream&
00264 PPL::IO_Operators::operator<<(std::ostream& s,
00265 const Grid_Generator::Type& t) {
00266 const char* n = 0;
00267 switch (t) {
00268 case Grid_Generator::LINE:
00269 n = "LINE";
00270 break;
00271 case Grid_Generator::PARAMETER:
00272 n = "PARAMETER";
00273 break;
00274 case Generator::POINT:
00275 n = "POINT";
00276 break;
00277 }
00278 s << n;
00279 return s;
00280 }
00281
00282 bool
00283 PPL::Grid_Generator::OK() const {
00284 if (!is_necessarily_closed()) {
00285 #ifndef NDEBUG
00286 std::cerr << "Grid_Generator Generator should be necessarily closed."
00287 << std::endl;
00288 #endif
00289 return false;
00290 }
00291
00292
00293 if (size() < 1) {
00294 #ifndef NDEBUG
00295 std::cerr << "Grid_Generator has fewer coefficients than the minimum "
00296 << "allowed:" << std::endl
00297 << "size is " << size() << ", minimum is 1." << std::endl;
00298 #endif
00299 return false;
00300 }
00301
00302 switch (type()) {
00303 case Grid_Generator::LINE:
00304 if (operator[](0) != 0) {
00305 #ifndef NDEBUG
00306 std::cerr << "Inhomogeneous terms of lines must be zero!"
00307 << std::endl;
00308 #endif
00309 return false;
00310 }
00311 break;
00312
00313 case Grid_Generator::PARAMETER:
00314 if (operator[](0) != 0) {
00315 #ifndef NDEBUG
00316 std::cerr << "Inhomogeneous terms of parameters must be zero!"
00317 << std::endl;
00318 #endif
00319 return false;
00320 }
00321
00322
00323 case Grid_Generator::POINT:
00324 if (divisor() <= 0) {
00325 #ifndef NDEBUG
00326 std::cerr << "Points and parameters must have positive divisors!"
00327 << std::endl;
00328 #endif
00329 return false;
00330 }
00331 break;
00332
00333 }
00334
00335
00336 return true;
00337 }
00338
00339 PPL_OUTPUT_DEFINITIONS(Grid_Generator);