1 /* 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 "Generator_defs.hh"
26 #include "Variable_defs.hh"
27 #include "Variables_Set_defs.hh"
28 #include "math_utilities_defs.hh"
29
30 #include <iostream>
31 #include <sstream>
32 #include <stdexcept>
33
34 namespace PPL = Parma_Polyhedra_Library;
35
36 void
throw_dimension_incompatible(const char * method,const char * v_name,const Variable v) const37 PPL::Generator::throw_dimension_incompatible(const char* method,
38 const char* v_name,
39 const Variable v) const {
40 std::ostringstream s;
41 s << "PPL::Generator::" << method << ":" << std::endl
42 << "this->space_dimension() == " << space_dimension() << ", "
43 << v_name << ".space_dimension() == " << v.space_dimension() << ".";
44 throw std::invalid_argument(s.str());
45 }
46
47 void
throw_invalid_argument(const char * method,const char * reason) const48 PPL::Generator::throw_invalid_argument(const char* method,
49 const char* reason) const {
50 std::ostringstream s;
51 s << "PPL::Generator::" << method << ":" << std::endl
52 << reason << ".";
53 throw std::invalid_argument(s.str());
54 }
55
56 PPL::Generator
point(const Linear_Expression & e,Coefficient_traits::const_reference d,Representation r)57 PPL::Generator::point(const Linear_Expression& e,
58 Coefficient_traits::const_reference d,
59 Representation r) {
60 if (d == 0) {
61 throw std::invalid_argument("PPL::point(e, d):\n"
62 "d == 0.");
63 }
64 Linear_Expression ec(e, r);
65 ec.set_inhomogeneous_term(d);
66 Generator g(ec, Generator::POINT, NECESSARILY_CLOSED);
67
68 // If the divisor is negative, we negate it as well as
69 // all the coefficients of the point, because we want to preserve
70 // the invariant: the divisor of a point is strictly positive.
71 if (d < 0) {
72 neg_assign(g.expr);
73 }
74
75 // Enforce normalization.
76 g.expr.normalize();
77 return g;
78 }
79
80 PPL::Generator
point(const Linear_Expression & e,Representation r)81 PPL::Generator::point(const Linear_Expression& e,
82 Representation r) {
83 return point(e, Coefficient_one(), r);
84 }
85
86 PPL::Generator
point(Representation r)87 PPL::Generator::point(Representation r) {
88 return point(Linear_Expression::zero(), Coefficient_one(), r);
89 }
90
91 PPL::Generator
closure_point(const Linear_Expression & e,Coefficient_traits::const_reference d,Representation r)92 PPL::Generator::closure_point(const Linear_Expression& e,
93 Coefficient_traits::const_reference d,
94 Representation r) {
95 if (d == 0) {
96 throw std::invalid_argument("PPL::closure_point(e, d):\n"
97 "d == 0.");
98 }
99 Linear_Expression ec(e, r);
100 ec.set_inhomogeneous_term(d);
101
102 Generator g(ec, Generator::POINT, NOT_NECESSARILY_CLOSED);
103
104 // If the divisor is negative, we negate it as well as
105 // all the coefficients of the point, because we want to preserve
106 // the invariant: the divisor of a point is strictly positive.
107 if (d < 0) {
108 neg_assign(g.expr);
109 }
110
111 // Enforce normalization.
112 g.expr.normalize();
113 return g;
114 }
115
116 PPL::Generator
closure_point(const Linear_Expression & e,Representation r)117 PPL::Generator::closure_point(const Linear_Expression& e,
118 Representation r) {
119 return closure_point(e, Coefficient_one(), r);
120 }
121
122 PPL::Generator
closure_point(Representation r)123 PPL::Generator::closure_point(Representation r) {
124 return closure_point(Linear_Expression::zero(), Coefficient_one(), r);
125 }
126
127 PPL::Generator
ray(const Linear_Expression & e,Representation r)128 PPL::Generator::ray(const Linear_Expression& e, Representation r) {
129 // The origin of the space cannot be a ray.
130 if (e.all_homogeneous_terms_are_zero()) {
131 throw std::invalid_argument("PPL::ray(e):\n"
132 "e == 0, but the origin cannot be a ray.");
133 }
134
135 Linear_Expression ec(e, r);
136 ec.set_inhomogeneous_term(0);
137 const Generator g(ec, Generator::RAY, NECESSARILY_CLOSED);
138
139 return g;
140 }
141
142 PPL::Generator
line(const Linear_Expression & e,Representation r)143 PPL::Generator::line(const Linear_Expression& e, Representation r) {
144 // The origin of the space cannot be a line.
145 if (e.all_homogeneous_terms_are_zero()) {
146 throw std::invalid_argument("PPL::line(e):\n"
147 "e == 0, but the origin cannot be a line.");
148 }
149
150 Linear_Expression ec(e, r);
151 ec.set_inhomogeneous_term(0);
152 const Generator g(ec, Generator::LINE, NECESSARILY_CLOSED);
153
154 return g;
155 }
156
157 void
swap_space_dimensions(Variable v1,Variable v2)158 PPL::Generator::swap_space_dimensions(Variable v1, Variable v2) {
159 PPL_ASSERT(v1.space_dimension() <= space_dimension());
160 PPL_ASSERT(v2.space_dimension() <= space_dimension());
161 expr.swap_space_dimensions(v1, v2);
162 // *this is still normalized but it may not be strongly normalized.
163 sign_normalize();
164 PPL_ASSERT(OK());
165 }
166
167 bool
remove_space_dimensions(const Variables_Set & vars)168 PPL::Generator::remove_space_dimensions(const Variables_Set& vars) {
169 PPL_ASSERT(vars.space_dimension() <= space_dimension());
170 expr.remove_space_dimensions(vars);
171
172 if (is_line_or_ray() && expr.all_homogeneous_terms_are_zero()) {
173 // Become a point.
174 set_is_ray_or_point();
175 expr.set_inhomogeneous_term(1);
176 if (is_not_necessarily_closed()) {
177 set_epsilon_coefficient(1);
178 }
179
180 PPL_ASSERT(OK());
181 return false;
182 }
183 else {
184 strong_normalize();
185 PPL_ASSERT(OK());
186 return true;
187 }
188 }
189
190 void
191 PPL::Generator
permute_space_dimensions(const std::vector<Variable> & cycle)192 ::permute_space_dimensions(const std::vector<Variable>& cycle) {
193 if (cycle.size() < 2) {
194 // No-op. No need to call sign_normalize().
195 return;
196 }
197
198 expr.permute_space_dimensions(cycle);
199
200 // *this is still normalized but may be not strongly normalized: sign
201 // normalization is necessary.
202 sign_normalize();
203 PPL_ASSERT(OK());
204 }
205
206 void
linear_combine(const Generator & y,dimension_type i)207 PPL::Generator::linear_combine(const Generator& y, dimension_type i) {
208 expr.linear_combine(y.expr, i);
209 strong_normalize();
210 }
211
212 /*! \relates Parma_Polyhedra_Library::Generator */
213 int
compare(const Generator & x,const Generator & y)214 PPL::compare(const Generator& x, const Generator& y) {
215 const bool x_is_line_or_equality = x.is_line_or_equality();
216 const bool y_is_line_or_equality = y.is_line_or_equality();
217 if (x_is_line_or_equality != y_is_line_or_equality) {
218 // Equalities (lines) precede inequalities (ray/point).
219 return y_is_line_or_equality ? 2 : -2;
220 }
221
222 return compare(x.expr, y.expr);
223 }
224
225 bool
is_equivalent_to(const Generator & y) const226 PPL::Generator::is_equivalent_to(const Generator& y) const {
227 const Generator& x = *this;
228 const dimension_type x_space_dim = x.space_dimension();
229 if (x_space_dim != y.space_dimension()) {
230 return false;
231 }
232
233 const Type x_type = x.type();
234 if (x_type != y.type()) {
235 return false;
236 }
237
238 if (x_type == POINT
239 && !(x.is_necessarily_closed() && y.is_necessarily_closed())) {
240 // Due to the presence of epsilon-coefficients, syntactically
241 // different points may actually encode the same generator.
242 // First, drop the epsilon-coefficient ...
243 Linear_Expression x_expr(x.expression());
244 Linear_Expression y_expr(y.expression());
245 // ... second, re-normalize ...
246 x_expr.normalize();
247 y_expr.normalize();
248 // ... and finally check for syntactic equality.
249 return x_expr.is_equal_to(y_expr);
250 }
251
252 // Here the epsilon-coefficient, if present, is zero.
253 // It is sufficient to check for syntactic equality.
254 return x.expr.is_equal_to(y.expr);
255 }
256
257 bool
is_equal_to(const Generator & y) const258 PPL::Generator::is_equal_to(const Generator& y) const {
259 return expr.is_equal_to(y.expr) && kind_ == y.kind_
260 && topology_ == y.topology_;
261 }
262
263 void
sign_normalize()264 PPL::Generator::sign_normalize() {
265 if (is_line_or_equality()) {
266 expr.sign_normalize();
267 }
268 }
269
270 bool
check_strong_normalized() const271 PPL::Generator::check_strong_normalized() const {
272 Generator tmp = *this;
273 tmp.strong_normalize();
274 return compare(*this, tmp) == 0;
275 }
276
277 const PPL::Generator* PPL::Generator::zero_dim_point_p = 0;
278 const PPL::Generator* PPL::Generator::zero_dim_closure_point_p = 0;
279
280 void
initialize()281 PPL::Generator::initialize() {
282 PPL_ASSERT(zero_dim_point_p == 0);
283 zero_dim_point_p
284 = new Generator(point());
285
286 PPL_ASSERT(zero_dim_closure_point_p == 0);
287 zero_dim_closure_point_p
288 = new Generator(closure_point());
289 }
290
291 void
finalize()292 PPL::Generator::finalize() {
293 PPL_ASSERT(zero_dim_point_p != 0);
294 delete zero_dim_point_p;
295 zero_dim_point_p = 0;
296
297 PPL_ASSERT(zero_dim_closure_point_p != 0);
298 delete zero_dim_closure_point_p;
299 zero_dim_closure_point_p = 0;
300 }
301
302 void
fancy_print(std::ostream & s) const303 PPL::Generator::fancy_print(std::ostream& s) const {
304 bool needed_divisor = false;
305 bool extra_parentheses = false;
306 const dimension_type num_variables = space_dimension();
307 const Generator::Type t = type();
308 switch (t) {
309 case Generator::LINE:
310 s << "l(";
311 break;
312 case Generator::RAY:
313 s << "r(";
314 break;
315 case Generator::POINT:
316 s << "p(";
317 goto any_point;
318 case Generator::CLOSURE_POINT:
319 s << "c(";
320 any_point:
321 if (expr.inhomogeneous_term() != 1) {
322 needed_divisor = true;
323 if (!expr.all_zeroes(1, num_variables + 1)) {
324 extra_parentheses = true;
325 s << "(";
326 }
327 }
328 break;
329 }
330
331 PPL_DIRTY_TEMP_COEFFICIENT(c);
332 bool first = true;
333 for (Linear_Expression::const_iterator i = expr.begin(),
334 i_end = expr.lower_bound(Variable(num_variables)); i != i_end; ++i) {
335 c = *i;
336 if (!first) {
337 if (c > 0) {
338 s << " + ";
339 }
340 else {
341 s << " - ";
342 neg_assign(c);
343 }
344 }
345 else {
346 first = false;
347 }
348 if (c == -1) {
349 s << "-";
350 }
351 else if (c != 1) {
352 s << c << "*";
353 }
354 IO_Operators::operator<<(s, i.variable());
355 }
356 if (first) {
357 // A point or closure point in the origin.
358 s << 0;
359 }
360 if (extra_parentheses) {
361 s << ")";
362 }
363 if (needed_divisor) {
364 s << "/" << expr.inhomogeneous_term();
365 }
366 s << ")";
367 }
368
369 /*! \relates Parma_Polyhedra_Library::Generator */
370 std::ostream&
operator <<(std::ostream & s,const Generator & g)371 PPL::IO_Operators::operator<<(std::ostream& s, const Generator& g) {
372 g.fancy_print(s);
373 return s;
374 }
375
376 /*! \relates Parma_Polyhedra_Library::Generator */
377 std::ostream&
operator <<(std::ostream & s,const Generator::Type & t)378 PPL::IO_Operators::operator<<(std::ostream& s, const Generator::Type& t) {
379 const char* n = 0;
380 switch (t) {
381 case Generator::LINE:
382 n = "LINE";
383 break;
384 case Generator::RAY:
385 n = "RAY";
386 break;
387 case Generator::POINT:
388 n = "POINT";
389 break;
390 case Generator::CLOSURE_POINT:
391 n = "CLOSURE_POINT";
392 break;
393 }
394 s << n;
395 return s;
396 }
397
398 bool
is_matching_closure_point(const Generator & p) const399 PPL::Generator::is_matching_closure_point(const Generator& p) const {
400 PPL_ASSERT(topology() == p.topology()
401 && space_dimension() == p.space_dimension()
402 && type() == CLOSURE_POINT
403 && p.type() == POINT);
404 const Generator& cp = *this;
405 if (cp.expr.inhomogeneous_term() == p.expr.inhomogeneous_term()) {
406 // Divisors are equal: we can simply compare coefficients
407 // (disregarding the epsilon coefficient).
408 return cp.expr.is_equal_to(p.expr, 1, cp.expr.space_dimension());
409 }
410 else {
411 // Divisors are different: divide them by their GCD
412 // to simplify the following computation.
413 PPL_DIRTY_TEMP_COEFFICIENT(gcd);
414 gcd_assign(gcd, cp.expr.inhomogeneous_term(), p.expr.inhomogeneous_term());
415 const bool rel_prime = (gcd == 1);
416 PPL_DIRTY_TEMP_COEFFICIENT(cp_0_scaled);
417 PPL_DIRTY_TEMP_COEFFICIENT(p_0_scaled);
418 if (!rel_prime) {
419 exact_div_assign(cp_0_scaled, cp.expr.inhomogeneous_term(), gcd);
420 exact_div_assign(p_0_scaled, p.expr.inhomogeneous_term(), gcd);
421 }
422 const Coefficient& cp_div = rel_prime ? cp.expr.inhomogeneous_term() : cp_0_scaled;
423 const Coefficient& p_div = rel_prime ? p.expr.inhomogeneous_term() : p_0_scaled;
424 return cp.expr.is_equal_to(p.expr, p_div, cp_div, 1, cp.expr.space_dimension());
425 }
426 }
427
PPL_OUTPUT_DEFINITIONS(Generator)428 PPL_OUTPUT_DEFINITIONS(Generator)
429
430
431 bool
432 PPL::Generator::OK() const {
433 // Topology consistency checks.
434 if (is_not_necessarily_closed() && expr.space_dimension() == 0) {
435 #ifndef NDEBUG
436 std::cerr << "Generator has fewer coefficients than the minimum "
437 << "allowed by its topology."
438 << std::endl;
439 #endif
440 return false;
441 }
442
443 // Normalization check.
444 Generator tmp = *this;
445 tmp.strong_normalize();
446 if (tmp != *this) {
447 #ifndef NDEBUG
448 std::cerr << "Generators should be strongly normalized!"
449 << std::endl;
450 #endif
451 return false;
452 }
453
454 switch (type()) {
455 case LINE:
456 // Intentionally fall through.
457 case RAY:
458 if (expr.inhomogeneous_term() != 0) {
459 #ifndef NDEBUG
460 std::cerr << "Lines must have a zero inhomogeneous term!"
461 << std::endl;
462 #endif
463 return false;
464 }
465 if (!is_necessarily_closed() && epsilon_coefficient() != 0) {
466 #ifndef NDEBUG
467 std::cerr << "Lines and rays must have a zero coefficient "
468 << "for the epsilon dimension!"
469 << std::endl;
470 #endif
471 return false;
472 }
473 // The following test is correct, since we already checked
474 // that the epsilon coordinate is zero.
475 if (expr.all_homogeneous_terms_are_zero()) {
476 #ifndef NDEBUG
477 std::cerr << "The origin of the vector space cannot be a line or a ray!"
478 << std::endl;
479 #endif
480 return false;
481 }
482 break;
483
484 case POINT:
485 if (expr.inhomogeneous_term() <= 0) {
486 #ifndef NDEBUG
487 std::cerr << "Points must have a positive divisor!"
488 << std::endl;
489 #endif
490 return false;
491 }
492 if (!is_necessarily_closed()) {
493 if (epsilon_coefficient() <= 0) {
494 #ifndef NDEBUG
495 std::cerr << "In the NNC topology, points must have epsilon > 0"
496 << std::endl;
497 #endif
498 return false;
499 }
500 }
501 break;
502
503 case CLOSURE_POINT:
504 if (expr.inhomogeneous_term() <= 0) {
505 #ifndef NDEBUG
506 std::cerr << "Closure points must have a positive divisor!"
507 << std::endl;
508 #endif
509 return false;
510 }
511 break;
512 }
513
514 // All tests passed.
515 return true;
516 }
517