1 /* Test the Sparse_Matrix class.
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 #if PPL_USE_SPARSE_MATRIX
27
28 #include <vector>
29 #include <algorithm>
30 #include <set>
31
32 namespace {
33
34 bool
test01()35 test01() {
36
37 Sparse_Row row(5);
38
39 if (row.size() != 5)
40 return false;
41
42 row.resize(4);
43
44 if (row.size() != 4)
45 return false;
46
47 return true;
48 }
49
50 bool
test02()51 test02() {
52
53 Sparse_Row row(5);
54
55 row[1] = 5;
56 row[3] = 6;
57
58 Sparse_Row::iterator itr = row.begin();
59
60 if (itr == row.end())
61 return false;
62
63 if (itr.index() != 1)
64 return false;
65
66 if (*itr != 5)
67 return false;
68
69 ++itr;
70
71 if (itr == row.end())
72 return false;
73
74 if (itr.index() != 3)
75 return false;
76
77 if (*itr != 6)
78 return false;
79
80 ++itr;
81
82 if (itr != row.end())
83 return false;
84
85 --itr;
86
87 if (itr == row.end())
88 return false;
89
90 if (itr.index() != 3)
91 return false;
92
93 if (*itr != 6)
94 return false;
95
96 Sparse_Row::const_iterator citr = row.cbegin();
97
98 if (citr == row.cend())
99 return false;
100
101 if (citr.index() != 1)
102 return false;
103
104 if (*citr != 5)
105 return false;
106
107 ++citr;
108
109 if (citr == row.cend())
110 return false;
111
112 if (citr.index() != 3)
113 return false;
114
115 if (*citr != 6)
116 return false;
117
118 ++citr;
119
120 if (citr != row.cend())
121 return false;
122
123 --citr;
124
125 if (citr == row.cend())
126 return false;
127
128 if (citr.index() != 3)
129 return false;
130
131 if (*citr != 6)
132 return false;
133
134 return true;
135 }
136
137 bool
test03()138 test03() {
139
140 Sparse_Row row(10);
141
142 row[1] = 2;
143 row[3] = 4;
144 row[5] = 6;
145 row[7] = 8;
146 row[9] = 10;
147
148 Sparse_Row::iterator itr = row.find(3);
149
150 row.reset(itr);
151
152 if (row.get(3) != 0)
153 return false;
154
155 row[3] = 4;
156
157 itr = row.find(3);
158 Sparse_Row::iterator itr2 = row.find(7);
159
160 row.reset(itr, itr2);
161
162 if (row.get(1) != 2)
163 return false;
164
165 if (row.get(3) != 0)
166 return false;
167
168 if (row.get(5) != 0)
169 return false;
170
171 if (row.get(7) != 8)
172 return false;
173
174 return true;
175 }
176
177 bool
test04()178 test04() {
179
180 Sparse_Row row(2);
181
182 row[1] = 2;
183
184 if (row.get(1) != 2)
185 return false;
186
187 if (row.find(0) != row.end())
188 return false;
189
190 row.swap_coefficients(0, 1);
191
192 if (row.get(0) != 2)
193 return false;
194
195 if (row.find(1) != row.end())
196 return false;
197
198 row.swap_coefficients(0, 1);
199
200 if (row.get(1) != 2)
201 return false;
202
203 if (row.find(0) != row.end())
204 return false;
205
206 row[0] = 3;
207
208 if (row.get(1) != 2)
209 return false;
210
211 if (row.get(0) != 3)
212 return false;
213
214 row.swap_coefficients(0, 1);
215
216 if (row.get(1) != 3)
217 return false;
218
219 if (row.get(0) != 2)
220 return false;
221
222 row.clear();
223
224 if (row.find(1) != row.end())
225 return false;
226
227 if (row.find(0) != row.end())
228 return false;
229
230 row.swap_coefficients(0, 1);
231
232 if (row.find(1) != row.end())
233 return false;
234
235 if (row.find(0) != row.end())
236 return false;
237
238 if (row.begin() != row.end())
239 return false;
240
241 if (row.cbegin() != row.cend())
242 return false;
243
244 return true;
245 }
246
247 class test05_functor {
248 public:
249
250 inline void
operator ()(Coefficient & x,const Coefficient & y) const251 operator()(Coefficient& x, const Coefficient& y) const {
252 x *= 2 - y;
253 }
254
255 inline void
operator ()(Coefficient & x) const256 operator()(Coefficient& x) const {
257 x *= 2;
258 }
259 };
260
261 bool
test05()262 test05() {
263
264 Sparse_Row x(9);
265
266 // x: ***000111
267 // (`*' is an unstored zero)
268
269 x[3] = 0;
270 x[4] = 0;
271 x[5] = 0;
272 x[6] = 1;
273 x[7] = 1;
274 x[8] = 1;
275
276 Sparse_Row y(9);
277
278 // y: *01*01*01
279 // (`*' is an unstored zero)
280
281 y[1] = 0;
282 y[2] = 1;
283 y[4] = 0;
284 y[5] = 1;
285 y[7] = 0;
286 y[8] = 1;
287
288 // x *= 2 - y
289
290 x.combine_needs_first(y, test05_functor(), test05_functor());
291
292 // x: ******221
293 // (`*' is an unstored zero)
294
295 if (x.find(0) != x.end())
296 return false;
297
298 if (x.find(1) != x.end())
299 return false;
300
301 if (x.find(2) != x.end())
302 return false;
303
304 if (x.find(3) != x.end())
305 return false;
306
307 if (x.find(4) != x.end())
308 return false;
309
310 if (x.find(5) != x.end())
311 return false;
312
313 if (x.get(6) != 2)
314 return false;
315
316 if (x.get(7) != 2)
317 return false;
318
319 if (x.get(8) != 1)
320 return false;
321
322 return true;
323 }
324
325 class test06_functor {
326 public:
327
328 inline void
operator ()(Coefficient & x,const Coefficient & y) const329 operator()(Coefficient& x, const Coefficient& y) const {
330 x += y;
331 }
332
333 inline void
operator ()(Coefficient &) const334 operator()(Coefficient& /* x */) const {
335 }
336 };
337
338 bool
test06()339 test06() {
340
341 Sparse_Row x(3);
342
343 x[1] = 0;
344 x[2] = 1;
345
346 // x: *01
347
348 x.combine(x, test06_functor(), test06_functor(), test06_functor());
349
350 // x: *02
351
352 if (x.find(0) != x.end())
353 return false;
354
355 if (x.get(1) != 0)
356 return false;
357
358 if (x.get(2) != 2)
359 return false;
360
361 return true;
362 }
363
364 class test07_functor_1 {
365 public:
366
367 inline void
operator ()(Coefficient & x,const Coefficient & y) const368 operator()(Coefficient& x, const Coefficient& y) const {
369 x = (x % 2) - (y % 2);
370 }
371
372 inline void
operator ()(Coefficient & x) const373 operator()(Coefficient& x) const {
374 x %= 2;
375 }
376 };
377
378 class test07_functor_2 {
379 public:
380
381 inline void
operator ()(Coefficient & x,const Coefficient & y) const382 operator()(Coefficient& x, const Coefficient& y) const {
383 PPL_ASSERT(x == 0);
384 x = -(y % 2);
385 }
386 };
387
388 bool
test07()389 test07() {
390
391 Sparse_Row x(16);
392
393 // 0123456789ABCDEF
394 // x: ****000011112222
395
396 x[ 4] = 0;
397 x[ 5] = 0;
398 x[ 6] = 0;
399 x[ 7] = 0;
400 x[ 8] = 1;
401 x[ 9] = 1;
402 x[10] = 1;
403 x[11] = 1;
404 x[12] = 2;
405 x[13] = 2;
406 x[14] = 2;
407 x[15] = 2;
408
409 Sparse_Row y(16);
410
411 // 0123456789ABCDEF
412 // y: *012*012*012*012
413
414 y[ 1] = 0;
415 y[ 2] = 1;
416 y[ 3] = 2;
417 y[ 5] = 0;
418 y[ 6] = 1;
419 y[ 7] = 2;
420 y[ 9] = 0;
421 y[10] = 1;
422 y[11] = 2;
423 y[13] = 0;
424 y[14] = 1;
425 y[15] = 2;
426
427 // x = (x % 2) - (y % 2)
428
429 x.combine(y, test07_functor_1(), test07_functor_1(), test07_functor_2());
430
431 // 0123456789ABCDEF
432 // x: ******-**1*1**-*
433 //
434 // Legend:
435 // *: unstored zero
436 // -: -1
437
438 if (x.find(0) != x.end()) return false;
439 if (x.find(1) != x.end()) return false;
440 if (x.get(2) != -1) return false;
441 if (x.find(3) != x.end()) return false;
442 if (x.find(4) != x.end()) return false;
443 if (x.find(5) != x.end()) return false;
444 if (x.get(6) != -1) return false;
445 if (x.find(7) != x.end()) return false;
446 if (x.get(8) != 1) return false;
447 if (x.get(9) != 1) return false;
448 if (x.find(10) != x.end()) return false;
449 if (x.get(11) != 1) return false;
450 if (x.find(12) != x.end()) return false;
451 if (x.find(13) != x.end()) return false;
452 if (x.get(14) != -1) return false;
453 if (x.find(15) != x.end()) return false;
454
455 return true;
456 }
457
458 bool
test08()459 test08() {
460
461 Sparse_Row row(4);
462
463 if (row.lower_bound(2) != row.end())
464 return false;
465
466 const Sparse_Row& crow = row;
467
468 if (crow.lower_bound(2) != crow.end())
469 return false;
470
471 row[2] = 3;
472
473 if (row.lower_bound(1).index() != 2)
474 return false;
475
476 if (crow.lower_bound(1).index() != 2)
477 return false;
478
479 if (row.lower_bound(2).index() != 2)
480 return false;
481
482 if (crow.lower_bound(2).index() != 2)
483 return false;
484
485 if (row.lower_bound(3) != row.end())
486 return false;
487
488 if (crow.lower_bound(3) != crow.end())
489 return false;
490
491 // Now the same checks with a dummy hint.
492
493 if (row.lower_bound(row.end(), 1).index() != 2)
494 return false;
495
496 if (crow.lower_bound(crow.end(), 1).index() != 2)
497 return false;
498
499 if (row.lower_bound(row.end(), 2).index() != 2)
500 return false;
501
502 if (crow.lower_bound(crow.end(), 2).index() != 2)
503 return false;
504
505 if (row.lower_bound(row.end(), 3) != row.end())
506 return false;
507
508 if (crow.lower_bound(crow.end(), 3) != crow.end())
509 return false;
510
511 return true;
512 }
513
514 bool
test09()515 test09() {
516 // These test the construction of a Sparse_Row from a Dense_Row.
517 {
518 Dense_Row dense(3);
519 Sparse_Row sparse(dense);
520 if (sparse.size() != dense.size())
521 return false;
522 if (sparse.begin() != sparse.end())
523 return false;
524 }
525
526 {
527 Dense_Row dense(5);
528 dense[1] = 2;
529 dense[3] = 4;
530 Sparse_Row sparse(dense);
531 if (sparse.size() != dense.size())
532 return false;
533 Sparse_Row::iterator itr = sparse.begin();
534
535 if (itr == sparse.end())
536 return false;
537 if (itr.index() != 1)
538 return false;
539 if (*itr != 2)
540 return false;
541
542 ++itr;
543
544 if (itr == sparse.end())
545 return false;
546 if (itr.index() != 3)
547 return false;
548 if (*itr != 4)
549 return false;
550
551 ++itr;
552
553 if (itr != sparse.end())
554 return false;
555 }
556
557 {
558 Dense_Row dense(5);
559 dense[0] = 1;
560 dense[2] = 3;
561 dense[4] = 5;
562 Sparse_Row sparse(dense);
563 if (sparse.size() != dense.size())
564 return false;
565 Sparse_Row::iterator itr = sparse.begin();
566
567 if (itr == sparse.end())
568 return false;
569 if (itr.index() != 0)
570 return false;
571 if (*itr != 1)
572 return false;
573
574 ++itr;
575
576 if (itr == sparse.end())
577 return false;
578 if (itr.index() != 2)
579 return false;
580 if (*itr != 3)
581 return false;
582
583 ++itr;
584
585 if (itr == sparse.end())
586 return false;
587 if (itr.index() != 4)
588 return false;
589 if (*itr != 5)
590 return false;
591
592 ++itr;
593
594 if (itr != sparse.end())
595 return false;
596 }
597
598 return true;
599 }
600
601 bool
test10()602 test10() {
603 Sparse_Row sparse(2);
604 Dense_Row dense(sparse, 8, 8);
605 return true;
606 }
607
608 } // namespace
609
610 BEGIN_MAIN
611 DO_TEST(test01);
612 DO_TEST(test02);
613 DO_TEST(test03);
614 DO_TEST(test04);
615 DO_TEST(test05);
616 DO_TEST(test06);
617 DO_TEST(test07);
618 DO_TEST(test08);
619 DO_TEST(test09);
620 DO_TEST(test10);
621 END_MAIN
622
623 #else // !PPL_USE_SPARSE_MATRIX
624
625 // A dummy test to avoid compiler warnings in BEGIN_MAIN.
626 bool test01() {
627 return true;
628 }
629
630 BEGIN_MAIN
631 DO_TEST(test01);
632 END_MAIN
633
634 #endif // !PPL_USE_SPARSE_MATRIX
635