1 /* Test Grid::is_bounded().
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 // Empty.
29 bool
test01()30 test01() {
31   Grid gr(7, EMPTY);
32 
33   bool ok = (gr.is_bounded());
34 
35   print_congruences(gr, "*** gr ***");
36 
37   return ok;
38 }
39 
40 // Zero dimension empty.
41 bool
test02()42 test02() {
43   Grid gr(0, EMPTY);
44 
45   bool ok = (gr.is_bounded());
46 
47   print_congruences(gr, "*** gr ***");
48 
49   return ok;
50 }
51 
52 // Zero dimension universe.
53 bool
test03()54 test03() {
55   Grid gr(0);
56 
57   bool ok = (gr.is_bounded());
58 
59   print_congruences(gr, "*** gr ***");
60 
61   return ok;
62 }
63 
64 // Point.
65 bool
test04()66 test04() {
67   Variable A(0);
68   Variable B(1);
69 
70   Grid gr_gs_min(2, EMPTY);
71   gr_gs_min.add_grid_generator(grid_point(3*A + 2*B));
72 
73   Grid gr_gs_needs_min(2, EMPTY);
74   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 2*B));
75 
76   Grid gr_cgs_needs_min(2);
77   gr_cgs_needs_min.add_congruence((A == 3) / 0);
78   gr_cgs_needs_min.add_congruence((B == 2) / 0);
79 
80   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
81   // same grids.
82 
83   bool ok = gr_gs_min.is_bounded()
84     && gr_gs_needs_min.is_bounded()
85     && gr_cgs_needs_min.is_bounded();
86 
87   print_congruences(gr_gs_min, "*** gr_gs_min **");
88   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
89   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
90 
91   return ok;
92 }
93 
94 // Line.
95 bool
test05()96 test05() {
97   Variable A(0);
98   Variable B(1);
99   Variable C(2);
100 
101   Grid gr_gs_min(3, EMPTY);
102   gr_gs_min.add_grid_generator(grid_point(3*A + 2*B));
103   gr_gs_min.add_grid_generator(grid_line(C));
104 
105   Grid gr_gs_needs_min(3, EMPTY);
106   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 2*B));
107   gr_gs_needs_min.add_grid_generator(grid_line(C));
108 
109   Grid gr_cgs_needs_min(3);
110   gr_cgs_needs_min.add_congruence((A == 3) / 0);
111   gr_cgs_needs_min.add_congruence((B == 2) / 0);
112 
113   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
114   // same grids.
115 
116   bool ok = !gr_gs_min.is_bounded()
117     && !gr_gs_needs_min.is_bounded()
118     && !gr_cgs_needs_min.is_bounded();
119 
120   print_congruences(gr_gs_min, "*** gr_gs_min **");
121   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
122   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
123 
124   return ok;
125 }
126 
127 // Rectilinear.
128 bool
test06()129 test06() {
130   Variable A(0);
131   Variable B(1);
132   Variable C(2);
133 
134   Grid gr_gs_min(3, EMPTY);
135   gr_gs_min.add_grid_generator(grid_point(3*A + 2*B));
136   gr_gs_min.add_grid_generator(grid_point(3*A + B));
137 
138   Grid gr_gs_needs_min(3, EMPTY);
139   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 2*B));
140   gr_gs_needs_min.add_grid_generator(grid_point(3*A + B));
141 
142   Grid gr_cgs_needs_min(3);
143   gr_cgs_needs_min.add_congruence((A == 3) / 0);
144   gr_cgs_needs_min.add_congruence(B %= 0);
145   gr_cgs_needs_min.add_congruence((C == 0) / 0);
146 
147   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
148   // same grids.
149 
150   bool ok = !gr_gs_min.is_bounded()
151     && !gr_gs_needs_min.is_bounded()
152     && !gr_cgs_needs_min.is_bounded();
153 
154   print_congruences(gr_gs_min, "*** gr_gs_min **");
155   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
156   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
157 
158   return ok;
159 }
160 
161 // Rectilinear with lines.
162 bool
test07()163 test07() {
164   Variable A(0);
165   Variable B(1);
166   Variable C(2);
167 
168   Grid gr_gs_min(3, EMPTY);
169   gr_gs_min.add_grid_generator(grid_point(3*A + 2*B));
170   gr_gs_min.add_grid_generator(grid_point(3*A + B));
171   gr_gs_min.add_grid_generator(grid_line(C));
172 
173   Grid gr_gs_needs_min(3, EMPTY);
174   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 2*B));
175   gr_gs_needs_min.add_grid_generator(grid_point(3*A + B));
176   gr_gs_needs_min.add_grid_generator(grid_line(C));
177 
178   Grid gr_cgs_needs_min(3);
179   gr_cgs_needs_min.add_congruence((A == 3) / 0);
180   gr_cgs_needs_min.add_congruence(B %= 0);
181 
182   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
183   // same grids.
184 
185   bool ok = !gr_gs_min.is_bounded()
186     && !gr_gs_needs_min.is_bounded()
187     && !gr_cgs_needs_min.is_bounded();
188 
189   print_congruences(gr_gs_min, "*** gr_gs_min **");
190   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
191   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
192 
193   return ok;
194 }
195 
196 // Skew.
197 bool
test08()198 test08() {
199   Variable A(0);
200   Variable B(1);
201 
202   Grid gr_gs_min(2, EMPTY);
203   gr_gs_min.add_grid_generator(grid_point());
204   gr_gs_min.add_grid_generator(grid_point(A));
205   gr_gs_min.add_grid_generator(grid_point(3*A + 3*B, 4));
206 
207   Grid gr_gs_needs_min(2, EMPTY);
208   gr_gs_needs_min.add_grid_generator(grid_point());
209   gr_gs_needs_min.add_grid_generator(grid_point(A));
210   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 3*B, 4));
211 
212   Grid gr_cgs_needs_min(2);
213   gr_cgs_needs_min.add_congruence((4*B %= 0) / 3);
214   gr_cgs_needs_min.add_congruence(A - B %= 0);
215 
216   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
217   // same grids.
218 
219   bool ok = !gr_gs_min.is_bounded()
220     && !gr_gs_needs_min.is_bounded()
221     && !gr_cgs_needs_min.is_bounded();
222 
223   print_congruences(gr_gs_min, "*** gr_gs_min **");
224   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
225   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
226 
227   return ok;
228 }
229 
230 // Skew with lines.
231 bool
test09()232 test09() {
233   Variable A(0);
234   Variable B(1);
235   Variable C(2);
236 
237   Grid gr_gs_min(3, EMPTY);
238   gr_gs_min.add_grid_generator(grid_point());
239   gr_gs_min.add_grid_generator(grid_point(A));
240   gr_gs_min.add_grid_generator(grid_line(C));
241   gr_gs_min.add_grid_generator(grid_point(3*A + 3*B, 4));
242   Grid gr_gs_needs_min(3, EMPTY);
243   gr_gs_needs_min.add_grid_generator(grid_point());
244   gr_gs_needs_min.add_grid_generator(grid_point(A));
245   gr_gs_needs_min.add_grid_generator(grid_line(C));
246   gr_gs_needs_min.add_grid_generator(grid_point(3*A + 3*B, 4));
247 
248   Grid gr_cgs_needs_min(3);
249   gr_cgs_needs_min.add_congruence((4*B %= 0) / 3);
250   gr_cgs_needs_min.add_congruence(A - B %= 0);
251 
252   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
253   // same grids.
254 
255   bool ok = !gr_gs_min.is_bounded()
256     && !gr_gs_needs_min.is_bounded()
257     && !gr_cgs_needs_min.is_bounded();
258 
259   print_congruences(gr_gs_min, "*** gr_gs_min **");
260   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
261   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
262 
263   return ok;
264 }
265 
266 // Plane.
267 bool
test10()268 test10() {
269   Variable A(0);
270   Variable B(1);
271   Variable C(2);
272   Variable D(3);
273 
274   Grid gr_gs_min(4, EMPTY);
275   gr_gs_min.add_grid_generator(grid_point());
276   gr_gs_min.add_grid_generator(grid_line(B));
277   gr_gs_min.add_grid_generator(grid_line(C));
278 
279   Grid gr_gs_needs_min(4, EMPTY);
280   gr_gs_needs_min.add_grid_generator(grid_point());
281   gr_gs_needs_min.add_grid_generator(grid_line(B));
282   gr_gs_needs_min.add_grid_generator(grid_line(C));
283 
284   Grid gr_cgs_needs_min(4);
285   gr_cgs_needs_min.add_congruence((A == 0) / 0);
286   gr_cgs_needs_min.add_congruence((D == 0) / 0);
287 
288   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
289   // same grids.
290 
291   bool ok = !gr_gs_min.is_bounded()
292     && !gr_gs_needs_min.is_bounded()
293     && !gr_cgs_needs_min.is_bounded();
294 
295   print_congruences(gr_gs_min, "*** gr_gs_min **");
296   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
297   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
298 
299   return ok;
300 }
301 
302 // Point in 6D.
303 bool
test11()304 test11() {
305   Variable A(0);
306   Variable B(1);
307   Variable C(2);
308   Variable D(3);
309   Variable E(4);
310   Variable F(5);
311 
312   Grid gr_gs_min(6, EMPTY);
313   gr_gs_min.add_grid_generator(grid_point(7*A - 11*B + 19*F));
314 
315   Grid gr_gs_needs_min(6, EMPTY);
316   gr_gs_needs_min.add_grid_generator(grid_point(7*A - 11*B + 19*F));
317 
318   Grid gr_cgs_needs_min(6);
319   gr_cgs_needs_min.add_congruence((A == 7) / 0);
320   gr_cgs_needs_min.add_congruence((B == -11) / 0);
321   gr_cgs_needs_min.add_congruence((C == 0) / 0);
322   gr_cgs_needs_min.add_congruence((D == 0) / 0);
323   gr_cgs_needs_min.add_congruence((E == 0) / 0);
324   gr_cgs_needs_min.add_congruence((F == 19) / 0);
325 
326   // Grids gr_gs_min, gr_gs_needs_min and gr_cgs_needs_min are the
327   // same grids.
328 
329   bool ok = gr_gs_min.is_bounded()
330     && gr_gs_needs_min.is_bounded()
331     && gr_cgs_needs_min.is_bounded();
332 
333   print_congruences(gr_gs_min, "*** gr_gs_min **");
334   print_congruences(gr_gs_needs_min, "*** gr_gs_needs_min **");
335   print_congruences(gr_cgs_needs_min, "*** gr_cgs_needs_min **");
336 
337   return ok;
338 }
339 
340 // A single point, duplicated.
341 bool
test12()342 test12() {
343   Variable A(0);
344   Variable B(1);
345 
346   Grid gr(2, EMPTY);
347   gr.add_grid_generator(grid_point(3*A + 2*B));
348   gr.add_grid_generator(grid_point(3*A + 2*B));
349 
350   bool ok = (gr.is_bounded());
351 
352   print_congruences(gr, "*** gr ***");
353 
354   return ok;
355 }
356 
357 // A parameter that comes first in the generator system.
358 bool
test13()359 test13() {
360   Variable A(0);
361   Variable B(1);
362 
363   Grid_Generator_System gs;
364   gs.insert(parameter(3*A + 2*B));
365   gs.insert(grid_point(3*A + 2*B));
366 
367   Grid gr(gs);
368 
369   bool ok = (!gr.is_bounded());
370 
371   print_congruences(gr, "*** gr ***");
372 
373   return ok;
374 }
375 
376 } // namespace
377 
378 BEGIN_MAIN
379   DO_TEST(test01);
380   DO_TEST(test02);
381   DO_TEST(test03);
382   DO_TEST(test04);
383   DO_TEST(test05);
384   DO_TEST(test06);
385   DO_TEST(test07);
386   DO_TEST(test08);
387   DO_TEST(test09);
388   DO_TEST(test10);
389   DO_TEST(test11);
390   DO_TEST(test12);
391   DO_TEST(test13);
392 END_MAIN
393