1 /* Grid_Generator class implementation (non-inline functions).
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #include "ppl-config.h"
25 #include "Grid_Generator_defs.hh"
26
27 #include "Variables_Set_defs.hh"
28 #include "math_utilities_defs.hh"
29
30 #include <iostream>
31 #include <sstream>
32
33 namespace PPL = Parma_Polyhedra_Library;
34
35 void
throw_dimension_incompatible(const char * method,const char * name_var,const Variable v) const36 PPL::Grid_Generator::throw_dimension_incompatible(const char* method,
37 const char* name_var,
38 const Variable v) const {
39 std::ostringstream s;
40 s << "PPL::Grid_Generator::" << method << ":" << std::endl
41 << "this->space_dimension() == " << space_dimension() << ", "
42 << name_var << ".space_dimension() == " << v.space_dimension() << ".";
43 throw std::invalid_argument(s.str());
44 }
45
46 void
throw_invalid_argument(const char * method,const char * reason) const47 PPL::Grid_Generator::throw_invalid_argument(const char* method,
48 const char* reason) const {
49 std::ostringstream s;
50 s << "PPL::Grid_Generator::" << method << ":" << std::endl
51 << reason << ".";
52 throw std::invalid_argument(s.str());
53 }
54
55 PPL::Grid_Generator
parameter(const Linear_Expression & e,Coefficient_traits::const_reference d,Representation r)56 PPL::Grid_Generator::parameter(const Linear_Expression& e,
57 Coefficient_traits::const_reference d,
58 Representation r) {
59 if (d == 0) {
60 throw std::invalid_argument("PPL::parameter(e, d):\n"
61 "d == 0.");
62 }
63 // Add 1 to space dimension to allow for parameter divisor column.
64 Linear_Expression ec(e, e.space_dimension() + 1, r);
65
66 ec.set_inhomogeneous_term(Coefficient_zero());
67 const Variable divisor_var(e.space_dimension());
68 ec.set(divisor_var, d);
69
70 // If the divisor is negative, negate it and all the coefficients of
71 // the parameter, so as to satisfy the invariant.
72 if (d < 0) {
73 neg_assign(ec);
74 }
75
76 // Using this constructor saves reallocation when creating the
77 // coefficients.
78 const Grid_Generator gg(ec, PARAMETER);
79
80 // NOTE: normalize() must *not* be called here, because this is a parameter,
81 // and it would change the represented parameter.
82 return gg;
83 }
84
85 PPL::Grid_Generator
grid_point(const Linear_Expression & e,Coefficient_traits::const_reference d,Representation r)86 PPL::Grid_Generator::grid_point(const Linear_Expression& e,
87 Coefficient_traits::const_reference d,
88 Representation r) {
89 if (d == 0) {
90 throw std::invalid_argument("PPL::grid_point(e, d):\n"
91 "d == 0.");
92 }
93 // Add 1 to space dimension to allow for parameter divisor column.
94 Linear_Expression ec(e, 1 + e.space_dimension(), r);
95 ec.set_inhomogeneous_term(d);
96
97 // If the divisor is negative, negate it and all the coefficients of
98 // the point, so as to satisfy the invariant.
99 if (d < 0) {
100 neg_assign(ec);
101 }
102
103 // Using this constructor saves reallocation when creating the
104 // coefficients.
105 Grid_Generator gg(ec, POINT);
106
107 // Enforce normalization.
108 gg.expr.normalize();
109 return gg;
110 }
111
112 PPL::Grid_Generator
grid_point(Representation r)113 PPL::Grid_Generator::grid_point(Representation r) {
114 return grid_point(Linear_Expression::zero(), Coefficient_one(), r);
115 }
116
117 PPL::Grid_Generator
grid_point(const Linear_Expression & e,Representation r)118 PPL::Grid_Generator::grid_point(const Linear_Expression& e,
119 Representation r) {
120 return grid_point(e, Coefficient_one(), r);
121 }
122
123 PPL::Grid_Generator
grid_line(const Linear_Expression & e,Representation r)124 PPL::Grid_Generator::grid_line(const Linear_Expression& e, Representation r) {
125 // The origin of the space cannot be a line.
126 if (e.all_homogeneous_terms_are_zero()) {
127 throw std::invalid_argument("PPL::grid_line(e):\n"
128 "e == 0, but the origin cannot be a line.");
129 }
130
131 // Add 1 to space dimension to allow for parameter divisor column.
132 Linear_Expression ec(e, 1 + e.space_dimension(), r);
133 ec.set_inhomogeneous_term(Coefficient_zero());
134 // Using this constructor saves reallocation when creating the
135 // coefficients.
136 Grid_Generator gg(ec, LINE);
137
138 // Enforce normalization.
139 gg.strong_normalize();
140 return gg;
141 }
142
143 void
swap_space_dimensions(Variable v1,Variable v2)144 PPL::Grid_Generator::swap_space_dimensions(Variable v1, Variable v2) {
145 PPL_ASSERT(v1.space_dimension() <= space_dimension());
146 PPL_ASSERT(v2.space_dimension() <= space_dimension());
147 expr.swap_space_dimensions(v1, v2);
148 // *this is still normalized but it may not be strongly normalized.
149 if (!is_parameter()) {
150 sign_normalize();
151 }
152 PPL_ASSERT(OK());
153 }
154
155 bool
remove_space_dimensions(const Variables_Set & vars)156 PPL::Grid_Generator::remove_space_dimensions(const Variables_Set& vars) {
157 PPL_ASSERT(vars.space_dimension() <= space_dimension());
158
159 expr.remove_space_dimensions(vars);
160
161 PPL_ASSERT(OK());
162 return true;
163 }
164
165 void
166 PPL::Grid_Generator
permute_space_dimensions(const std::vector<Variable> & cycle)167 ::permute_space_dimensions(const std::vector<Variable>& cycle) {
168 if (cycle.size() < 2) {
169 // No-op. No need to call sign_normalize().
170 return;
171 }
172
173 expr.permute_space_dimensions(cycle);
174
175 // *this is still normalized but may be not strongly normalized: sign
176 // normalization is necessary.
177 // Sign-normalizing a parameter changes its meaning, so do nothing for
178 // parameters.
179 if (!is_parameter()) {
180 sign_normalize();
181 }
182 PPL_ASSERT(OK());
183 }
184
185 void
ascii_dump(std::ostream & s) const186 PPL::Grid_Generator::ascii_dump(std::ostream& s) const {
187 expr.ascii_dump(s);
188 s << ' ';
189 switch (type()) {
190 case LINE:
191 s << "L";
192 break;
193 case PARAMETER:
194 s << "Q";
195 break;
196 case POINT:
197 s << "P";
198 break;
199 }
200 s << "\n";
201 }
202
PPL_OUTPUT_DEFINITIONS(Grid_Generator)203 PPL_OUTPUT_DEFINITIONS(Grid_Generator)
204
205 bool
206 PPL::Grid_Generator::ascii_load(std::istream& s) {
207
208 if (!expr.ascii_load(s)) {
209 return false;
210 }
211
212 std::string str;
213
214 if (!(s >> str)) {
215 return false;
216 }
217 if (str == "L") {
218 set_is_line();
219 }
220 else if (str == "P" || str == "Q") {
221 set_is_parameter_or_point();
222 }
223 else {
224 return false;
225 }
226
227 PPL_ASSERT(OK());
228 return true;
229 }
230
231 void
set_is_parameter()232 PPL::Grid_Generator::set_is_parameter() {
233 if (is_line()) {
234 set_is_parameter_or_point();
235 }
236 else if (!is_line_or_parameter()) {
237 // The grid generator is a point.
238 expr.set(Variable(expr.space_dimension() - 1), expr.inhomogeneous_term());
239 expr.set_inhomogeneous_term(Coefficient_zero());
240 }
241 }
242
243 void
linear_combine(const Grid_Generator & y,dimension_type i)244 PPL::Grid_Generator::linear_combine(const Grid_Generator& y,
245 dimension_type i) {
246 expr.linear_combine(y.expr, i);
247 strong_normalize();
248 }
249
250 /*! \relates Parma_Polyhedra_Library::Grid_Generator */
251 int
compare(const Grid_Generator & x,const Grid_Generator & y)252 PPL::compare(const Grid_Generator& x, const Grid_Generator& y) {
253 const bool x_is_line_or_equality = x.is_line_or_equality();
254 const bool y_is_line_or_equality = y.is_line_or_equality();
255 if (x_is_line_or_equality != y_is_line_or_equality) {
256 // Equalities (lines) precede inequalities (ray/point).
257 return y_is_line_or_equality ? 2 : -2;
258 }
259
260 return compare(x.expr, y.expr);
261 }
262
263 bool
is_equivalent_to(const Grid_Generator & y) const264 PPL::Grid_Generator::is_equivalent_to(const Grid_Generator& y) const {
265 const Grid_Generator& x = *this;
266 const dimension_type x_space_dim = x.space_dimension();
267 if (x_space_dim != y.space_dimension()) {
268 return false;
269 }
270
271 const Type x_type = x.type();
272 if (x_type != y.type()) {
273 return false;
274 }
275
276 Grid_Generator tmp_x = *this;
277 Grid_Generator tmp_y = y;
278 const Variable last_var(x_space_dim);
279 if (x_type == POINT || x_type == LINE) {
280 tmp_x.expr.set(last_var, Coefficient_zero());
281 tmp_y.expr.set(last_var, Coefficient_zero());
282 }
283 // Normalize the copies, including the divisor column.
284 tmp_x.expr.normalize();
285 tmp_y.expr.normalize();
286 // Check for equality.
287 return tmp_x.is_equal_to(tmp_y);
288 }
289
290 bool
is_equal_to(const Grid_Generator & y) const291 PPL::Grid_Generator::is_equal_to(const Grid_Generator& y) const {
292 return expr.is_equal_to(y.expr) && kind_ == y.kind_;
293 }
294
295 bool
all_homogeneous_terms_are_zero() const296 PPL::Grid_Generator::all_homogeneous_terms_are_zero() const {
297 // This does not check neither the first nor the last coefficient.
298 return expr.all_zeroes(1, expr.space_dimension());
299 }
300
301 void
scale_to_divisor(Coefficient_traits::const_reference d)302 PPL::Grid_Generator::scale_to_divisor(Coefficient_traits::const_reference d) {
303 PPL_ASSERT(d != 0);
304 if (is_line()) {
305 return;
306 }
307
308 PPL_DIRTY_TEMP_COEFFICIENT(factor);
309 exact_div_assign(factor, d, divisor());
310 set_divisor(d);
311 PPL_ASSERT(factor > 0);
312 if (factor > 1) {
313 // Don't scale the first and last coefficients.
314 expr.mul_assign(factor, 1, expr.space_dimension());
315 }
316 }
317
318 void
sign_normalize()319 PPL::Grid_Generator::sign_normalize() {
320 if (is_line_or_equality()) {
321 expr.sign_normalize();
322 }
323 }
324
325 bool
check_strong_normalized() const326 PPL::Grid_Generator::check_strong_normalized() const {
327 Grid_Generator tmp = *this;
328 tmp.strong_normalize();
329 return compare(*this, tmp) == 0;
330 }
331
332 const PPL::Grid_Generator* PPL::Grid_Generator::zero_dim_point_p = 0;
333
334 void
initialize()335 PPL::Grid_Generator::initialize() {
336 PPL_ASSERT(zero_dim_point_p == 0);
337 zero_dim_point_p = new Grid_Generator(grid_point());
338 }
339
340 void
finalize()341 PPL::Grid_Generator::finalize() {
342 PPL_ASSERT(zero_dim_point_p != 0);
343 delete zero_dim_point_p;
344 zero_dim_point_p = 0;
345 }
346
347 void
fancy_print(std::ostream & s) const348 PPL::Grid_Generator::fancy_print(std::ostream& s) const {
349 bool need_divisor = false;
350 bool extra_parentheses = false;
351 const dimension_type num_variables = space_dimension();
352 const Grid_Generator::Type t = type();
353 switch (t) {
354 case Grid_Generator::LINE:
355 s << "l(";
356 break;
357 case Grid_Generator::PARAMETER:
358 s << "q(";
359 if (expr.coefficient(Variable(num_variables)) == 1) {
360 break;
361 }
362 goto any_point;
363 case Grid_Generator::POINT:
364 s << "p(";
365 if (expr.inhomogeneous_term() > 1) {
366 any_point:
367 need_divisor = true;
368 if (!expr.all_zeroes(1, num_variables + 1)) {
369 extra_parentheses = true;
370 s << "(";
371 break;
372 }
373 }
374 break;
375 }
376
377 PPL_DIRTY_TEMP_COEFFICIENT(c);
378 bool first = true;
379 for (Linear_Expression::const_iterator i = expr.begin(),
380 i_end = expr.lower_bound(Variable(num_variables)); i != i_end; ++i) {
381 c = *i;
382 if (!first) {
383 if (c > 0) {
384 s << " + ";
385 }
386 else {
387 s << " - ";
388 neg_assign(c);
389 }
390 }
391 else {
392 first = false;
393 }
394 if (c == -1) {
395 s << "-";
396 }
397 else if (c != 1) {
398 s << c << "*";
399 }
400 IO_Operators::operator<<(s, i.variable());
401 }
402 if (first) {
403 // A grid generator in the origin.
404 s << 0;
405 }
406 if (extra_parentheses) {
407 s << ")";
408 }
409 if (need_divisor) {
410 s << "/" << divisor();
411 }
412 s << ")";
413 }
414
415 /*! \relates Parma_Polyhedra_Library::Grid_Generator */
416 std::ostream&
operator <<(std::ostream & s,const Grid_Generator & g)417 PPL::IO_Operators::operator<<(std::ostream& s, const Grid_Generator& g) {
418 g.fancy_print(s);
419 return s;
420 }
421
422 /*! \relates Parma_Polyhedra_Library::Grid_Generator */
423 std::ostream&
operator <<(std::ostream & s,const Grid_Generator::Type & t)424 PPL::IO_Operators::operator<<(std::ostream& s,
425 const Grid_Generator::Type& t) {
426 const char* n = 0;
427 switch (t) {
428 case Grid_Generator::LINE:
429 n = "LINE";
430 break;
431 case Grid_Generator::PARAMETER:
432 n = "PARAMETER";
433 break;
434 case Grid_Generator::POINT:
435 n = "POINT";
436 break;
437 }
438 s << n;
439 return s;
440 }
441
442 bool
OK() const443 PPL::Grid_Generator::OK() const {
444 // NOTE: do not check for normalization, as it does not hold.
445 const Grid_Generator& x = *this;
446
447 if (!x.is_necessarily_closed()) {
448 #ifndef NDEBUG
449 std::cerr << "Grid_Generator should be necessarily closed.\n";
450 #endif
451 return false;
452 }
453
454 if (x.expr.space_dimension() < 1) {
455 #ifndef NDEBUG
456 std::cerr << "Grid_Generator has fewer coefficients than the minimum "
457 << "allowed:\nspace dimension is " << x.expr.space_dimension()
458 << ", minimum is 1.\n";
459 #endif
460 return false;
461 }
462
463 switch (x.type()) {
464 case Grid_Generator::LINE:
465 if (x.expr.inhomogeneous_term() != 0) {
466 #ifndef NDEBUG
467 std::cerr << "Inhomogeneous terms of lines must be zero!\n";
468 #endif
469 return false;
470 }
471 break;
472
473 case Grid_Generator::PARAMETER:
474 if (x.expr.inhomogeneous_term() != 0) {
475 #ifndef NDEBUG
476 std::cerr << "Inhomogeneous terms of parameters must be zero!\n";
477 #endif
478 return false;
479 }
480 if (x.divisor() <= 0) {
481 #ifndef NDEBUG
482 std::cerr << "Parameters must have positive divisors!\n";
483 #endif
484 return false;
485 }
486 break;
487
488 case Grid_Generator::POINT:
489 if (x.expr.inhomogeneous_term() <= 0) {
490 #ifndef NDEBUG
491 std::cerr << "Points must have positive divisors!\n";
492 #endif
493 return false;
494 }
495 if (x.expr.coefficient(Variable(space_dimension())) != 0) {
496 #ifndef NDEBUG
497 std::cerr << "Points must have a zero parameter divisor!\n";
498 #endif
499 return false;
500 }
501 break;
502
503 } // switch (x.type())
504
505 // All tests passed.
506 return true;
507 }
508