1 /* Test Grid::relation_with(const Constraint&).
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 // A point and an inequality.
29 bool
test01()30 test01() {
31 Variable A(0);
32 Variable B(1);
33
34 Grid gr(2, EMPTY);
35 gr.add_grid_generator(grid_point(A - B));
36 print_generators(gr, "*** gr ***");
37
38 bool ok = gr.relation_with(A - B >= 1) == Poly_Con_Relation::is_included();
39
40 return ok;
41 }
42
43 // A line.
44 bool
test02()45 test02() {
46 Variable A(0);
47 Variable B(1);
48
49 Grid gr(2, EMPTY);
50 gr.add_grid_generator(grid_point());
51 gr.add_grid_generator(grid_line(A));
52 print_generators(gr, "*** gr ***");
53
54 using namespace Parma_Polyhedra_Library::IO_Operators;
55
56 bool ok = (gr.relation_with(A + 0*B == 0)
57 == Poly_Con_Relation::strictly_intersects()
58 && gr.relation_with(B > -2)
59 == Poly_Con_Relation::is_included()
60 && gr.relation_with(B > 2)
61 == Poly_Con_Relation::is_disjoint()
62 && gr.relation_with(B >= 2)
63 == Poly_Con_Relation::is_disjoint()
64 && gr.relation_with(B < -2)
65 == Poly_Con_Relation::is_disjoint()
66 && gr.relation_with(B <= -2)
67 == Poly_Con_Relation::is_disjoint()
68 && gr.relation_with(B == -2)
69 == Poly_Con_Relation::is_disjoint());
70
71 return ok;
72 }
73
74 // Inclusion of a point grid.
75 bool
test03()76 test03() {
77 Variable A(0);
78 Variable B(1);
79
80 Grid gr(2, EMPTY);
81 gr.add_grid_generator(grid_point(A + B));
82 print_generators(gr, "*** gr ***");
83
84 bool ok = (gr.relation_with(B == 1)
85 == (Poly_Con_Relation::is_included()
86 && Poly_Con_Relation::saturates()));
87
88 return ok;
89 }
90
91 // Empty grid.
92
93 bool
test04()94 test04() {
95 Variable B(1);
96
97 Grid gr(2, EMPTY);
98 print_generators(gr, "*** gr ***");
99
100 bool ok = (gr.relation_with(B == 0)
101 == (Poly_Con_Relation::is_included()
102 && Poly_Con_Relation::is_disjoint()
103 && Poly_Con_Relation::saturates())
104 && gr.relation_with(B > 0)
105 == (Poly_Con_Relation::is_included()
106 && Poly_Con_Relation::is_disjoint()
107 && Poly_Con_Relation::saturates()));
108
109 return ok;
110 }
111
112 // Zero dimension universe grid.
113 bool
test05()114 test05() {
115 Grid gr;
116 print_generators(gr, "*** gr ***");
117
118 bool ok = (// False.
119 gr.relation_with(Linear_Expression(1) == 0)
120 == Poly_Con_Relation::is_disjoint()
121 && gr.relation_with(Linear_Expression(0) > 0)
122 == (Poly_Con_Relation::saturates()
123 && Poly_Con_Relation::is_disjoint())
124 // True.
125 && gr.relation_with(Linear_Expression(1) == 1)
126 == (Poly_Con_Relation::saturates()
127 && Poly_Con_Relation::is_included())
128 && gr.relation_with(Linear_Expression(0) >= 0)
129 == (Poly_Con_Relation::saturates()
130 && Poly_Con_Relation::is_included())
131 // False.
132 && gr.relation_with(Linear_Expression(1) < 0)
133 == Poly_Con_Relation::is_disjoint()
134 // True.
135 && gr.relation_with(Linear_Expression(1) >= 0)
136 == Poly_Con_Relation::is_included());
137
138 return ok;
139 }
140
141 // A disjoint grid.
142 bool
test06()143 test06() {
144 Variable A(0);
145 Variable B(1);
146
147 Grid gr(2, EMPTY);
148 gr.add_grid_generator(grid_point());
149 gr.add_grid_generator(grid_point(2*A + 5*B));
150 print_generators(gr, "*** gr ***");
151
152 bool ok = (gr.relation_with(5*A - 2*B == 1)
153 == Poly_Con_Relation::is_disjoint()
154 && gr.relation_with(5*A - 2*B > 1)
155 == Poly_Con_Relation::is_disjoint()
156 && gr.relation_with(5*A - 2*B >= 1)
157 == Poly_Con_Relation::is_disjoint());
158
159 return ok;
160 }
161
162 // Point with a divisor that is greater than zero.
163 bool
test07()164 test07() {
165 Variable A(0);
166
167 Grid gr(3, EMPTY);
168 gr.add_grid_generator(grid_point(A, 2));
169 print_generators(gr, "*** gr ***");
170
171 bool ok = (gr.relation_with(A == 3)
172 == Poly_Con_Relation::is_disjoint()
173 && gr.relation_with(2*A == 1)
174 == (Poly_Con_Relation::is_included()
175 && Poly_Con_Relation::saturates())
176 && gr.relation_with(2*A < 1)
177 == Poly_Con_Relation::is_disjoint()
178 && gr.relation_with(2*A >= 1)
179 == (Poly_Con_Relation::is_included()
180 && Poly_Con_Relation::saturates()));
181
182 return ok;
183 }
184
185 // Grid with a divisor that is greater than zero: separate spaces.
186 bool
test08()187 test08() {
188 Variable A(0);
189
190 Grid gr(1, EMPTY);
191 gr.add_grid_generator(grid_point());
192 gr.add_grid_generator(parameter(A, 5));
193 print_generators(gr, "*** gr ***");
194
195 bool ok = (gr.relation_with(10*A == 1)
196 == Poly_Con_Relation::is_disjoint()
197 && gr.relation_with(Linear_Expression(10) > 10)
198 == Poly_Con_Relation::is_disjoint());
199
200 return ok;
201 }
202
203 // Grid with a divisor that is greater than zero: inclusion.
204 bool
test09()205 test09() {
206 Variable A(0);
207
208 Grid gr(1, EMPTY);
209 gr.add_grid_generator(grid_point());
210 gr.add_grid_generator(parameter(A, 5));
211 print_generators(gr, "*** gr ***");
212
213 bool ok = (gr.relation_with(Linear_Expression(10) == 10)
214 == (Poly_Con_Relation::is_included()
215 && Poly_Con_Relation::saturates())
216 && gr.relation_with(Linear_Expression(10) >= 10)
217 == (Poly_Con_Relation::is_included()
218 && Poly_Con_Relation::saturates()));
219
220 return ok;
221 }
222
223 // Grid with a divisor that is greater than zero: strict intersection.
224 bool
test10()225 test10() {
226 Variable A(0);
227 Variable B(1);
228
229 Grid gr(2, EMPTY);
230 gr.add_grid_generator(grid_point());
231 gr.add_grid_generator(parameter(A, 5));
232 print_generators(gr, "*** gr ***");
233
234 bool ok = (gr.relation_with(A + B == 0)
235 == Poly_Con_Relation::strictly_intersects()
236 && gr.relation_with(A + B >= 0)
237 == Poly_Con_Relation::strictly_intersects());
238
239 return ok;
240 }
241
242 // Space dimension exception.
243 bool
test11()244 test11() {
245 Variable A(0);
246 Variable B(1);
247
248 Grid gr(1);
249 print_generators(gr, "*** gr ***");
250
251 try {
252 gr.relation_with(A + B >= 0);
253 }
254 catch (const std::invalid_argument& e) {
255 nout << "invalid_argument: " << e.what() << endl;
256 return true;
257 }
258 catch (...) {
259 }
260 return false;
261 }
262
263 // Empty grid, where updating finds the grid empty.
264 bool
test12()265 test12() {
266 Variable A(0);
267 Variable B(1);
268
269 Grid gr(2);
270 gr.add_constraint(A == 1);
271 gr.add_constraint(A == 2);
272 print_congruences(gr, "*** gr ***");
273
274 bool ok = (gr.relation_with(B == 0)
275 == (Poly_Con_Relation::is_included()
276 && Poly_Con_Relation::is_disjoint()
277 && Poly_Con_Relation::saturates())
278 && gr.relation_with(B >= 0)
279 == (Poly_Con_Relation::is_included()
280 && Poly_Con_Relation::is_disjoint()
281 && Poly_Con_Relation::saturates()));
282
283 return ok;
284 }
285
286 // Generators that require the relation_with(cg) GCD calculation.
287 bool
test13()288 test13() {
289 Variable A(0);
290
291 Grid gr(1, EMPTY);
292 gr.add_grid_generator(grid_point(A));
293 gr.add_grid_generator(grid_point(3*A));
294 print_generators(gr, "*** gr ***");
295
296 bool ok = (gr.relation_with(A == 0)
297 == Poly_Con_Relation::is_disjoint());
298
299 return ok;
300 }
301
302 // Strict intersection, where generators require the relation_with(cg)
303 // GCD calculation.
304 bool
test14()305 test14() {
306 Variable A(0);
307 Variable B(1);
308
309 Grid gr(2, EMPTY);
310 gr.add_grid_generator(grid_point(3*A));
311 gr.add_grid_generator(grid_point(6*A));
312 print_generators(gr, "*** gr ***");
313
314 bool ok = (gr.relation_with(A + B == 0)
315 == Poly_Con_Relation::strictly_intersects());
316
317 return ok;
318 }
319
320 // Strict intersection, where generators require the relation_with(cg)
321 // GCD calculation, with a parameter.
322 bool
test15()323 test15() {
324 Variable A(0);
325 Variable B(1);
326
327 Grid gr(2, EMPTY);
328 gr.add_grid_generator(grid_point(3*A));
329 gr.add_grid_generator(parameter(3*A));
330 print_generators(gr, "*** gr ***");
331
332 bool ok = (gr.relation_with(A + B == 0)
333 == Poly_Con_Relation::strictly_intersects());
334
335 return ok;
336 }
337
338 // generators are out of date and the grid is empty.
339 bool
test16()340 test16() {
341 Variable A(0);
342 Variable B(1);
343
344 Grid gr(2);
345 gr.add_congruence((A %= 0) / 2);
346 gr.add_congruence((A %= 1) / 2);
347 print_congruences(gr, "*** gr ***");
348
349 bool ok = (gr.relation_with(A + B == 8)
350 == (Poly_Con_Relation::is_included()
351 && Poly_Con_Relation::is_disjoint()
352 && Poly_Con_Relation::saturates())
353 && gr.relation_with(A + B > 8)
354 == (Poly_Con_Relation::is_included()
355 && Poly_Con_Relation::is_disjoint()
356 && Poly_Con_Relation::saturates()));
357
358 return ok;
359 }
360
361 // A simple example.
362 bool
test17()363 test17() {
364 Variable A(0);
365 Variable B(1);
366
367 Grid gr(2, EMPTY);
368 gr.add_grid_generator(grid_point(B));
369 gr.add_grid_generator(parameter(A));
370 print_generators(gr, "*** gr ***");
371
372 bool ok = (gr.relation_with(A > 1)
373 == Poly_Con_Relation::strictly_intersects()
374 && gr.relation_with(A >= 1)
375 == Poly_Con_Relation::strictly_intersects()
376 && gr.relation_with(A < 1)
377 == Poly_Con_Relation::strictly_intersects()
378 && gr.relation_with(A <= 1)
379 == Poly_Con_Relation::strictly_intersects());
380
381 return ok;
382 }
383
384 // A grid in 3D.
385 bool
test18()386 test18() {
387 Variable A(0);
388 Variable B(1);
389 Variable C(2);
390
391 // Regularly spaced parallel lines along a slanted plane in 3D.
392 Grid gr(3, EMPTY);
393 gr.add_grid_generator(grid_point(A + B + C));
394 gr.add_grid_generator(grid_line(A - 2*B + 3*C));
395 gr.add_grid_generator(parameter(A - B, 3));
396 print_generators(gr, "*** gr ***");
397
398 bool ok = (gr.relation_with(A + B + C == 0)
399 == Poly_Con_Relation::strictly_intersects()
400 && gr.relation_with(A + B == 0)
401 == Poly_Con_Relation::strictly_intersects()
402 && gr.relation_with(A == 0)
403 == Poly_Con_Relation::strictly_intersects()
404 && gr.relation_with(Linear_Expression(0) == 0)
405 == (Poly_Con_Relation::is_included()
406 && Poly_Con_Relation::saturates()));
407
408 return ok;
409 }
410
411 // Zero dimension empty grid.
412 bool
test19()413 test19() {
414 Grid gr(0, EMPTY);
415 print_generators(gr, "*** gr ***");
416
417 bool ok = (// False.
418 gr.relation_with(Linear_Expression(1) == 0)
419 == (Poly_Con_Relation::is_disjoint()
420 && Poly_Con_Relation::is_included()
421 && Poly_Con_Relation::saturates())
422 // True.
423 && gr.relation_with(Linear_Expression(1) == 1)
424 == (Poly_Con_Relation::is_disjoint()
425 && Poly_Con_Relation::is_included()
426 && Poly_Con_Relation::saturates())
427 // False.
428 && gr.relation_with(Linear_Expression(1) < 0)
429 == (Poly_Con_Relation::is_disjoint()
430 && Poly_Con_Relation::is_included()
431 && Poly_Con_Relation::saturates())
432 // True.
433 && gr.relation_with(Linear_Expression(1) >= 0)
434 == (Poly_Con_Relation::is_disjoint()
435 && Poly_Con_Relation::is_included()
436 && Poly_Con_Relation::saturates()));
437
438 return ok;
439 }
440
441 // A variant of test06.
442 bool
test20()443 test20() {
444 Variable A(0);
445 Variable B(1);
446
447 Grid gr(2, EMPTY);
448 gr.add_grid_generator(grid_point());
449 gr.add_grid_generator(grid_point(2*A + 5*B));
450 // Force minimization.
451 (void) gr.minimized_grid_generators();
452 print_generators(gr, "*** gr ***");
453
454 bool ok = (gr.relation_with(5*A - 2*B == 1)
455 == Poly_Con_Relation::is_disjoint()
456 && gr.relation_with(5*A - 2*B > 1)
457 == Poly_Con_Relation::is_disjoint()
458 && gr.relation_with(5*A - 2*B >= 1)
459 == Poly_Con_Relation::is_disjoint());
460
461 return ok;
462 }
463
464 } // namespace
465
466 BEGIN_MAIN
467 DO_TEST(test01);
468 DO_TEST(test02);
469 DO_TEST(test03);
470 DO_TEST(test04);
471 DO_TEST(test05);
472 DO_TEST(test06);
473 DO_TEST(test07);
474 DO_TEST(test08);
475 DO_TEST(test09);
476 DO_TEST(test10);
477 DO_TEST(test11);
478 DO_TEST(test12);
479 DO_TEST(test13);
480 DO_TEST(test14);
481 DO_TEST(test15);
482 DO_TEST(test16);
483 DO_TEST(test17);
484 DO_TEST(test18);
485 DO_TEST(test19);
486 DO_TEST(test20);
487 END_MAIN
488