1 /* Test Grid::congruences().
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 grid.
29 bool
test01()30 test01() {
31 Grid gr1(7, EMPTY);
32
33 Grid known_gr = gr1;
34
35 Congruence_System cgs = gr1.congruences();
36
37 Grid gr2(cgs);
38
39 bool ok = (gr2 == known_gr);
40
41 print_congruences(cgs, "*** cgs ***");
42 print_congruences(gr2, "*** gr2(cgs) ***");
43
44 return ok;
45 }
46
47 // Universe grid.
48 bool
test02()49 test02() {
50 Grid gr1(7);
51
52 Grid known_gr = gr1;
53
54 Congruence_System cgs = gr1.congruences();
55
56 print_congruences(cgs, "*** cgs ***");
57
58 Grid gr2(cgs);
59
60 bool ok = (gr2 == known_gr);
61
62 print_congruences(gr2, "*** gr2(cgs) ***");
63
64 return ok;
65 }
66
67 // Zero dimension empty grid.
68 bool
test03()69 test03() {
70 Grid gr1(0, EMPTY);
71
72 Grid known_gr = gr1;
73
74 Congruence_System cgs = gr1.congruences();
75
76 Grid gr2(cgs);
77
78 bool ok = (gr2 == known_gr);
79
80 print_congruences(cgs, "*** cgs ***");
81 print_congruences(gr2, "*** gr2(cgs) ***");
82
83 return ok;
84 }
85
86 // Zero dimension universe grid.
87 bool
test04()88 test04() {
89 Grid gr1(0);
90
91 Grid known_gr = gr1;
92
93 Congruence_System cgs = gr1.congruences();
94
95 Grid gr2(cgs);
96
97 bool ok = (gr2 == known_gr);
98
99 print_congruences(cgs, "*** cgs ***");
100 print_congruences(gr2, "*** gr2(cgs) ***");
101
102 return ok;
103 }
104
105 // Skew grid in 3D.
106 bool
test05()107 test05() {
108 Variable A(0);
109 Variable B(1);
110
111 Grid gr1(3);
112 gr1.add_congruence((A + B %= 3) / 7);
113 gr1.add_congruence((A %= 0) / 5);
114
115 Grid known_gr = gr1;
116
117 Congruence_System cgs = gr1.congruences();
118
119 Grid gr2(cgs);
120
121 bool ok = (gr2 == known_gr);
122
123 print_congruences(cgs, "*** cgs ***");
124 print_congruences(gr2, "*** gr2(cgs) ***");
125
126 return ok;
127 }
128
129 // 3D rectilinear grid defined by generators.
130 bool
test06()131 test06() {
132 Variable A(0);
133 Variable B(1);
134
135 Grid gr1(3);
136 gr1.add_grid_generator(grid_point(10*B));
137 gr1.add_grid_generator(grid_point(10*A + 10*B));
138
139 Grid known_gr = gr1;
140
141 Congruence_System cgs = gr1.congruences();
142
143 Grid gr2(cgs);
144
145 bool ok = (gr2 == known_gr);
146
147 print_congruences(cgs, "*** cgs ***");
148 print_congruences(gr2, "*** gr2(cgs) ***");
149
150 return ok;
151 }
152
153 // Get a reference to the congruences, empty the grid, use the
154 // reference to create a new grid.
155 bool
test07()156 test07() {
157 Grid gr1(3);
158 gr1.add_congruence(Congruence::zero_dim_integrality());
159
160 const Congruence_System& cgs = gr1.congruences();
161
162 // Empty the grid. The idea is to check that `cgs' still refers to
163 // a congruence system that matches the grid.
164 gr1.add_congruence(Congruence::zero_dim_false());
165
166 Grid known_gr = gr1;
167
168 Grid gr2(cgs);
169
170 bool ok = (gr2 == known_gr);
171
172 print_congruences(cgs, "*** cgs ***");
173 print_congruences(gr2, "*** gr2(cgs) ***");
174
175 return ok;
176 }
177
178 // In zero dimensions get a reference to the universe congruences,
179 // empty the grid, use the reference to create a new grid.
180 bool
test08()181 test08() {
182 Grid gr1(0);
183 gr1.add_congruence(Congruence::zero_dim_integrality());
184
185 const Congruence_System& cgs = gr1.congruences();
186
187 // Empty the grid. The idea is to check that `cgs' still refers to
188 // a congruence system that matches the grid.
189 gr1.add_congruence(Congruence::zero_dim_false());
190
191 Grid known_gr = gr1;
192
193 Grid gr2(cgs);
194
195 bool ok = (gr2 == known_gr);
196
197 print_congruences(cgs, "*** cgs ***");
198 print_congruences(gr2, "*** gr2(cgs) ***");
199
200 return ok;
201 }
202
203 // add congruence systems to a congruence system with smaller space
204 // dimension.
205 // This test showed a bug in Congruence_System insert(), now corrected.
206 bool
test09()207 test09() {
208 Variable A(0);
209 Variable B(1);
210
211 Congruence_System cgs;
212 Congruence_System cgs1;
213 cgs1.insert((A %= 0) / 2);
214 cgs.insert(cgs1);
215 cgs1.insert((A + B %= 0) / 2);
216 cgs.insert(cgs1, Recycle_Input());
217
218 Grid gr(2);
219
220 print_congruences(gr, "*** gr ***");
221
222 gr.add_recycled_congruences(cgs);
223
224 Grid known_gr(2);
225 known_gr.add_congruence((A %= 0) / 2);
226 known_gr.add_congruence((A + B %= 0) / 2);
227
228 bool ok = (gr == known_gr);
229
230 print_congruences(gr, "*** gr.add_recycled_congruences(cgs) ***");
231
232 return ok;
233 }
234
235 // add congruence systems to a congruence system
236 // with larger space dimension.
237 bool
test10()238 test10() {
239 Variable A(0);
240 Variable B(1);
241
242 Congruence_System cgs;
243 Congruence_System cgs1;
244 cgs.insert((A + B %= 0) / 2);
245 cgs1.insert((A %= 0) / 2);
246 cgs.insert(cgs1);
247 print_congruences(cgs, "*** cgs ***");
248 print_congruences(cgs1, "*** cgs1 ***");
249
250 Grid gr(2);
251
252 print_congruences(gr, "*** gr ***");
253
254 gr.add_recycled_congruences(cgs);
255
256 Grid known_gr(2);
257 known_gr.add_congruence((A %= 0) / 2);
258 known_gr.add_congruence((A + B %= 0) / 2);
259
260 bool ok = (gr == known_gr);
261
262 print_congruences(gr, "*** gr.add_recycled_congruences(cgs) ***");
263
264 return ok;
265 }
266
267 // Test is_equal_to() for same congruence systems.
268 bool
test11()269 test11() {
270 Variable A(0);
271 Variable B(1);
272
273 Congruence_System cgs1;
274 cgs1.insert((A %= 0) / 2);
275 cgs1.insert((A + B %= 0) / 2);
276 Congruence_System cgs(cgs1);
277 bool ok = cgs.is_equal_to(cgs1);
278 print_congruences(cgs, "*** cgs ***");
279 print_congruences(cgs1, "*** cgs1 ***");
280
281 return ok;
282 }
283
284 // Test is_equal_to() for congruence systems with different numbers
285 // numbers of congruences.
286 // This test showed a bug in Congruence_System is_equal_to(), now corrected.
287 bool
test12()288 test12() {
289 Variable A(0);
290 Variable B(1);
291
292 Congruence_System cgs1;
293 cgs1.insert((A %= 0) / 2);
294 cgs1.insert((A + B %= 0) / 2);
295 Congruence_System cgs(cgs1);
296 cgs1.insert((B %= 0) / 2);
297
298 bool ok = !cgs.is_equal_to(cgs1);
299 print_congruences(cgs, "*** cgs ***");
300 print_congruences(cgs1, "*** cgs1 ***");
301
302 return ok;
303 }
304
305 // Test is_equal_to() for different congruence systems with the same
306 // number of congruences.
307 bool
test13()308 test13() {
309 Variable A(0);
310 Variable B(1);
311
312 Congruence_System cgs1;
313 Congruence_System cgs2;
314 cgs1.insert((A %= 0) / 2);
315 cgs1.insert((A + B %= 0) / 2);
316 cgs2.insert((B %= 0) / 2);
317 cgs2.insert((A + B %= 0) / 2);
318 bool ok = !cgs1.is_equal_to(cgs2);
319 print_congruences(cgs1, "*** cgs1 ***");
320 print_congruences(cgs2, "*** cgs2 ***");
321
322 return ok;
323 }
324
325 // Test has_linear_equalities() for congruence systems.
326 bool
test14()327 test14() {
328 Variable A(0);
329 Variable B(1);
330
331 Congruence_System cgs;
332 cgs.insert((A + B %= 0) / 2);
333 print_congruences(cgs, "*** cgs.insert((A + B %= 0) / 2) ***");
334 bool ok = !cgs.has_linear_equalities();
335
336 cgs.insert(A == 0);
337 print_congruences(cgs, "*** cgs.insert(A == 0) ***");
338 ok &= cgs.has_linear_equalities();
339
340 return ok;
341 }
342
343 // Test num_equalities() for congruence systems.
344 bool
test15()345 test15() {
346 Variable A(0);
347 Variable B(1);
348
349 Congruence_System cgs;
350 cgs.insert((A + B %= 0) / 2);
351 cgs.insert(A == 0);
352 print_congruences(cgs, "*** cgs ***");
353
354 bool ok = ((cgs.num_equalities() == 1)
355 && (cgs.num_proper_congruences() == 1));
356
357 return ok;
358 }
359
360 // Add to a non-empty congruence system a nonempty constraint system
361 bool
test16()362 test16() {
363 Variable A(0);
364 Variable B(1);
365
366 Congruence_System cgs;
367 cgs.insert(A %= 0);
368 cgs.insert(B == 0);
369
370 Congruence_System known_cgs;
371 known_cgs.insert(B == 0);
372 known_cgs.insert(A %= 0);
373
374 print_congruences(cgs, "*** cgs ***");
375
376 Grid gr(cgs);
377 Grid known_gr(known_cgs);
378
379 bool ok = (gr == known_gr);
380
381 return ok;
382 }
383
384 } // namespace
385
386 BEGIN_MAIN
387 DO_TEST(test01);
388 DO_TEST(test02);
389 DO_TEST(test03);
390 DO_TEST(test04);
391 DO_TEST(test05);
392 DO_TEST(test06);
393 DO_TEST(test07);
394 DO_TEST(test08);
395 DO_TEST(test09);
396 DO_TEST(test10);
397 DO_TEST(test11);
398 DO_TEST(test12);
399 DO_TEST(test13);
400 DO_TEST(test14);
401 DO_TEST(test15);
402 DO_TEST(test16);
403 END_MAIN
404