1 /* Test BD_Shape::generalized_affine_image().
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_test.hh"
25
26 namespace {
27
28 bool
test01()29 test01() {
30 Variable x(0);
31 Variable y(1);
32
33 TBD_Shape bds(2);
34 bds.add_constraint(x <= 4);
35 bds.add_constraint(x >= -6);
36 bds.add_constraint(y == 0);
37
38 print_constraints(bds, "*** bds ***");
39
40 bds.generalized_affine_image(y, LESS_OR_EQUAL, -y + 1);
41
42 BD_Shape<mpq_class> known_result(2);
43 known_result.add_constraint(x <= 4);
44 known_result.add_constraint(x >= -6);
45 known_result.add_constraint(y <= 1);
46
47 bool ok = check_result(bds, known_result);
48
49 print_constraints(bds, "*** bds.generalized_affine_image(y, "
50 "LESS_OR_EQUAL, -y + 1) ***");
51
52 return ok;
53 }
54
55 bool
test02()56 test02() {
57 Variable x(0);
58 Variable y(1);
59
60 TBD_Shape bds(2);
61 bds.add_constraint(x <= 4);
62 bds.add_constraint(x >= -6);
63 bds.add_constraint(y == 0);
64
65 print_constraints(bds, "*** bds ***");
66
67 bds.generalized_affine_image(x, GREATER_OR_EQUAL, -x - 3);
68
69 BD_Shape<mpq_class> known_result(2);
70 known_result.add_constraint(x >= -7);
71 known_result.add_constraint(y == 0);
72
73 bool ok = check_result(bds, known_result);
74
75 print_constraints(bds, "*** bds.generalized_affine_image(x, "
76 "GREATER_OR_EQUAL, -x - 3) ***");
77
78 return ok;
79 }
80
81 bool
test03()82 test03() {
83 Variable A(0);
84 Variable B(1);
85
86 TBD_Shape bds(2);
87 bds.add_constraint(A >= 0);
88 bds.add_constraint(B <= 1);
89
90 print_constraints(bds, "*** bds ***");
91
92 bds.generalized_affine_image(B, LESS_OR_EQUAL, 3*B + 1, 2);
93
94 BD_Shape<mpq_class> known_result(2);
95 known_result.add_constraint(A >= 0);
96 known_result.add_constraint(B <= 2);
97
98 bool ok = check_result(bds, known_result);
99
100 print_constraints(bds, "*** bds.generalized_affine_image(B, "
101 "LESS_OR_EQUAL, 3*B + 1, 2) ***");
102
103 return ok;
104 }
105
106 bool
test04()107 test04() {
108 Variable A(0);
109 Variable B(1);
110
111 TBD_Shape bds(2);
112 bds.add_constraint(A == 0);
113 bds.add_constraint(B >= 1);
114
115 print_constraints(bds, "*** bds ***");
116
117 bds.generalized_affine_image(B, GREATER_OR_EQUAL, B - 2);
118
119 BD_Shape<mpq_class> known_result(2);
120 known_result.add_constraint(A == 0);
121 known_result.add_constraint(B >= -1);
122
123 bool ok = check_result(bds, known_result);
124
125 print_constraints(bds, "*** bds.generalized_affine_image(B, "
126 "GREATER_OR_EQUAL, B - 2) ***");
127
128 return ok;
129 }
130
131 bool
test05()132 test05() {
133 Variable A(0);
134 Variable B(1);
135
136 TBD_Shape bds(2);
137 bds.add_constraint(B <= 1);
138 bds.add_constraint(A - B == 0);
139
140 print_constraints(bds, "*** bds ***");
141
142 bds.generalized_affine_image(A, GREATER_OR_EQUAL, 2*A + 3, 2);
143
144 BD_Shape<mpq_class> known_result(2);
145 known_result.add_constraint(B <= 1);
146 known_result.add_constraint(2*B - 2*A <= -3);
147
148 bool ok = check_result(bds, known_result, "7.63e-17", "3.82e-17", "1.91e-17");
149
150 print_constraints(bds, "*** bds.generalized_affine_image(A, "
151 "GREATER_OR_EQUAL, 2*A + 3, 2) ***");
152
153 return ok;
154 }
155
156 bool
test06()157 test06() {
158 Variable A(0);
159 Variable B(1);
160 Variable C(2);
161
162 TBD_Shape bds(3);
163 bds.add_constraint(A - B == 0);
164 bds.add_constraint(B <= 1);
165 bds.add_constraint(C - A <= 2);
166
167 print_constraints(bds, "*** bds ***");
168
169 bds.generalized_affine_image(C, LESS_OR_EQUAL, 2*C + 1, 5);
170
171 BD_Shape<mpq_class> known_result(3);
172 known_result.add_constraint(A - B == 0);
173 known_result.add_constraint(B <= 1);
174 known_result.add_constraint(5*C <= 7);
175 known_result.add_constraint(A <= 1);
176
177 bool ok = check_result(bds, known_result, "9.54e-8", "9.54e-8", "9.54e-8");
178
179 print_constraints(bds, "*** bds.generalized_affine_image(C, "
180 "LESS_OR_EQUAL, 2*C + 1, 5) ***");
181
182 return ok;
183 }
184
185 bool
test07()186 test07() {
187 Variable A(0);
188 Variable B(1);
189 Variable C(2);
190
191 TBD_Shape bds(3);
192 bds.add_constraint(A - B == 0);
193 bds.add_constraint(B <= 1);
194 bds.add_constraint(C - A <= 2);
195
196 print_constraints(bds, "*** bds ***");
197
198 BD_Shape<mpq_class> known_result(bds);
199
200 bds.generalized_affine_image(C, EQUAL, 5*C - 3, 4);
201
202 known_result.affine_image(C, 5*C - 3, 4);
203
204 bool ok = check_result(bds, known_result);
205
206 print_constraints(bds, "*** bds.generalized_affine_image(C, "
207 "EQUAL, 5*C - 3, 4) ***");
208
209 return ok;
210 }
211
212 bool
test08()213 test08() {
214 Variable A(0);
215 Variable B(1);
216 Variable C(2);
217
218 TBD_Shape bds(3);
219 bds.add_constraint(A - B == 0);
220 bds.add_constraint(B <= 1);
221 bds.add_constraint(C - A <= 2);
222
223 print_constraints(bds, "*** bds ***");
224
225 bds.generalized_affine_image(B, GREATER_OR_EQUAL, -B - 2, 3);
226
227 BD_Shape<mpq_class> known_result(3);
228 known_result.add_constraint(B >= -1);
229 known_result.add_constraint(C - A <= 2);
230 known_result.add_constraint(A <= 1);
231
232 bool ok = check_result(bds, known_result);
233
234 print_constraints(bds, "*** bds.generalized_affine_image(B, "
235 "GREATER_OR_EQUAL, -B - 2, 3) ***");
236
237 return ok;
238 }
239
240 bool
test09()241 test09() {
242 Variable A(0);
243 Variable B(1);
244 Variable C(2);
245
246 TBD_Shape bds(3);
247 bds.add_constraint(A - B == 0);
248 bds.add_constraint(B <= 1);
249 bds.add_constraint(C - A <= 2);
250
251 print_constraints(bds, "*** bds ***");
252
253 bds.generalized_affine_image(B, LESS_OR_EQUAL, 4*A -2*C + 3, -3);
254
255 BD_Shape<mpq_class> known_result(3);
256 known_result.add_constraint(A <= 1);
257 known_result.add_constraint(C - A <= 2);
258
259 bool ok = check_result(bds, known_result);
260
261 print_constraints(bds, "*** bds.generalized_affine_image(B, "
262 "LESS_OR_EQUAL, 4*A - 2*C + 3, -3) ***");
263
264 return ok;
265 }
266
267 bool
test10()268 test10() {
269 Variable A(0);
270 Variable B(1);
271 Variable C(2);
272
273 TBD_Shape bds(3);
274 bds.add_constraint(A - B == 0);
275 bds.add_constraint(B <= 1);
276 bds.add_constraint(C - A <=2);
277
278 print_constraints(bds, "*** bds ***");
279
280 BD_Shape<mpq_class> known_result(bds);
281
282 bds.generalized_affine_image(B, EQUAL, 2*A - 4*B + C + 3, 3);
283
284 known_result.affine_image(B, 2*A - 4*B + C + 3, 3);
285
286 bool ok = check_result(bds, known_result);
287
288 print_constraints(bds, "*** bds.generalized_affine_image(B, "
289 "EQUAL, 2*A - 4*B + C + 3, 3) ***");
290
291 return ok;
292 }
293
294 bool
test11()295 test11() {
296 Variable A(0);
297 Variable B(1);
298 Linear_Expression e1(A);
299 Linear_Expression e2(1);
300
301 TBD_Shape bds(2);
302 bds.add_constraint(A >= 0);
303 bds.add_constraint(A <= 4);
304 bds.add_constraint(B <= 5);
305
306 print_constraints(bds, "*** bds ***");
307
308 bds.generalized_affine_image(e1, EQUAL, e2);
309
310 BD_Shape<mpq_class> known_result(2);
311 known_result.add_constraint(A == 1);
312 known_result.add_constraint(B <= 5);
313
314 bool ok = check_result(bds, known_result);
315
316 print_constraints(bds, "*** bds.generalized_affine_image(A, EQUAL, 1) ***");
317
318 return ok;
319 }
320
321 bool
test12()322 test12() {
323 Variable A(0);
324 Variable B(1);
325 Linear_Expression e1(B - 3);
326 Linear_Expression e2(B + 1);
327
328 TBD_Shape bds(2);
329 bds.add_constraint(A >= 0);
330 bds.add_constraint(A <= 4);
331 bds.add_constraint(B <= 5);
332
333 print_constraints(bds, "*** bds ***");
334
335 bds.generalized_affine_image(e1, EQUAL, e2);
336
337 BD_Shape<mpq_class> known_result(2);
338 known_result.add_constraint(A >= 0);
339 known_result.add_constraint(A <= 4);
340 known_result.add_constraint(B <= 9);
341
342 bool ok = check_result(bds, known_result);
343
344 print_constraints(bds,
345 "*** bds.generalized_affine_image(B-3, EQUAL, B+1) ***");
346
347 return ok;
348 }
349
350 bool
test13()351 test13() {
352 Variable x(0);
353 Variable y(1);
354
355 TBD_Shape bds(2);
356 bds.add_constraint(x >= y);
357
358 try {
359 // This is an incorrect use of the method
360 // BD_Shape::generalized_affine_image(v, r, expr, d): it is illegal
361 // to use a strict relation symbol.
362 bds.generalized_affine_image(x, LESS_THAN, x + 1);
363 }
364 catch (std::invalid_argument& e) {
365 nout << "std::invalid_argument: " << endl;
366 return true;
367 }
368 catch (...) {
369 }
370 return false;
371 }
372
373 bool
test14()374 test14() {
375 Variable x(0);
376 Variable y(1);
377
378 TBD_Shape bds(2);
379 bds.add_constraint(x >= y);
380
381 try {
382 // This is an incorrect use of the method
383 // BD_Shape::generalized_affine_image(v, r, expr, d): it is illegal
384 // to use a strict relation symbol.
385 bds.generalized_affine_image(x, GREATER_THAN, x + 1);
386 }
387 catch (std::invalid_argument& e) {
388 nout << "std::invalid_argument: " << endl;
389 return true;
390 }
391 catch (...) {
392 }
393 return false;
394 }
395
396 bool
test15()397 test15() {
398 Variable x(0);
399 Variable y(1);
400
401 TBD_Shape bds(2);
402 bds.add_constraint(x >= y);
403
404 try {
405 // This is an incorrect use of the method
406 // BD_Shape::generalized_affine_image(v, r, expr, d): it is illegal
407 // to apply it to a expression with the denominator
408 // equal to zero.
409 Coefficient d = 0;
410 bds.generalized_affine_image(x, LESS_OR_EQUAL, x + 1, d);
411 }
412 catch (std::invalid_argument& e) {
413 nout << "std::invalid_argument: " << endl;
414 return true;
415 }
416 catch (...) {
417 }
418 return false;
419 }
420
421 bool
test16()422 test16() {
423 Variable x(0);
424 Variable y(1);
425 Variable z(2);
426
427 TBD_Shape bds(2);
428 bds.add_constraint(x >= y);
429
430 try {
431 // This is an incorrect use of the method
432 // BD_Shape::generalized_affine_image(v, r, expr, d): it is illegal
433 // to apply it to an expression whose space dimension is
434 // greater than the BDS's space dimension.
435 bds.generalized_affine_image(y, GREATER_OR_EQUAL, z);
436 }
437 catch (std::invalid_argument& e) {
438 nout << "std::invalid_argument: " << endl;
439 return true;
440 }
441 catch (...) {
442 }
443 return false;
444 }
445
446 bool
test17()447 test17() {
448 Variable A(0);
449 Variable B(1);
450 Variable C(2);
451
452 TBD_Shape bds(2);
453 bds.add_constraint(A >= 0);
454
455 try {
456 // This is an incorrect use of the method
457 // BD_Shape::generalized_affine_image(lhs, r, rhs):
458 // it is illegal to use a variable in the `rhs' expression that
459 // does not appear in the BDS.
460
461 bds.generalized_affine_image(A + B, GREATER_OR_EQUAL, B + C);
462 }
463 catch (std::invalid_argument& e) {
464 nout << "std::invalid_argument: " << endl;
465 return true;
466 }
467 catch (...) {
468 }
469 return false;
470 }
471
472 bool
test18()473 test18() {
474 Variable A(0);
475 Variable B(1);
476 Variable C(2);
477
478 TBD_Shape bds(2);
479 bds.add_constraint(A >= 1);
480
481 try {
482 // This is an incorrect use of method
483 // BD_Shape::generalized_affine_image(lhs, r, rhs):
484 // it is illegal to use a variable in the `lhs' expression that
485 // does not appear in the BDS.
486 bds.generalized_affine_image(B + C, LESS_OR_EQUAL, A + 1);
487 }
488 catch (std::invalid_argument& e) {
489 nout << "std::invalid_argument: " << endl;
490 return true;
491 }
492 catch (...) {
493 }
494 return false;
495 }
496
497 } // namespace
498
499 BEGIN_MAIN
500 DO_TEST(test01);
501 DO_TEST(test02);
502 DO_TEST(test03);
503 DO_TEST(test04);
504 DO_TEST(test05);
505 DO_TEST(test06);
506 DO_TEST(test07);
507 DO_TEST(test08);
508 DO_TEST(test09);
509 DO_TEST(test10);
510 DO_TEST(test11);
511 DO_TEST(test12);
512 DO_TEST(test13);
513 DO_TEST(test14);
514 DO_TEST(test15);
515 DO_TEST(test16);
516 DO_TEST(test17);
517 DO_TEST(test18);
518 END_MAIN
519