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