1 // -----------------------------------------------------------
2 // Copyright (c) 2001 Jeremy Siek
3 // Copyright (c) 2003-2006 Gennaro Prota
4 // Copyright (c) 2014 Ahmed Charles
5 //
6 // Distributed under the Boost Software License, Version 1.0.
7 // (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // -----------------------------------------------------------
11
12 #include <assert.h>
13 #include "bitset_test.hpp"
14 #include "boost/dynamic_bitset/dynamic_bitset.hpp"
15 #include "boost/limits.hpp"
16 #include "boost/config.hpp"
17
18
19 template <typename Block>
run_test_cases(BOOST_EXPLICIT_TEMPLATE_TYPE (Block))20 void run_test_cases( BOOST_EXPLICIT_TEMPLATE_TYPE(Block) )
21 {
22 // a bunch of typedefs which will be handy later on
23 typedef boost::dynamic_bitset<Block> bitset_type;
24 typedef bitset_test<bitset_type> Tests;
25 // typedef typename bitset_type::size_type size_type; // unusable with Borland 5.5.1
26
27 std::string long_string = get_long_string();
28 std::size_t ul_width = std::numeric_limits<unsigned long>::digits;
29
30 //=====================================================================
31 // Test b.empty()
32 {
33 bitset_type b;
34 Tests::empty(b);
35 }
36 {
37 bitset_type b(1, 1ul);
38 Tests::empty(b);
39 }
40 {
41 bitset_type b(bitset_type::bits_per_block
42 + bitset_type::bits_per_block/2, 15ul);
43 Tests::empty(b);
44 }
45 //=====================================================================
46 // Test b.to_long()
47 {
48 boost::dynamic_bitset<Block> b;
49 Tests::to_ulong(b);
50 }
51 {
52 boost::dynamic_bitset<Block> b(std::string("1"));
53 Tests::to_ulong(b);
54 }
55 {
56 boost::dynamic_bitset<Block> b(bitset_type::bits_per_block,
57 static_cast<unsigned long>(-1));
58 Tests::to_ulong(b);
59 }
60 {
61 std::string str(ul_width - 1, '1');
62 boost::dynamic_bitset<Block> b(str);
63 Tests::to_ulong(b);
64 }
65 {
66 std::string ul_str(ul_width, '1');
67 boost::dynamic_bitset<Block> b(ul_str);
68 Tests::to_ulong(b);
69 }
70 { // case overflow
71 boost::dynamic_bitset<Block> b(long_string);
72 Tests::to_ulong(b);
73 }
74 //=====================================================================
75 // Test to_string(b, str)
76 {
77 boost::dynamic_bitset<Block> b;
78 Tests::to_string(b);
79 }
80 {
81 boost::dynamic_bitset<Block> b(std::string("0"));
82 Tests::to_string(b);
83 }
84 {
85 boost::dynamic_bitset<Block> b(long_string);
86 Tests::to_string(b);
87 }
88 //=====================================================================
89 // Test b.count()
90 {
91 boost::dynamic_bitset<Block> b;
92 Tests::count(b);
93 }
94 {
95 boost::dynamic_bitset<Block> b(std::string("0"));
96 Tests::count(b);
97 }
98 {
99 boost::dynamic_bitset<Block> b(std::string("1"));
100 Tests::count(b);
101 }
102 {
103 boost::dynamic_bitset<Block> b(8, 255ul);
104 Tests::count(b);
105 }
106 {
107 boost::dynamic_bitset<Block> b(long_string);
108 Tests::count(b);
109 }
110 //=====================================================================
111 // Test b.size()
112 {
113 boost::dynamic_bitset<Block> b;
114 Tests::size(b);
115 }
116 {
117 boost::dynamic_bitset<Block> b(std::string("0"));
118 Tests::size(b);
119 }
120 {
121 boost::dynamic_bitset<Block> b(long_string);
122 Tests::size(b);
123 }
124 //=====================================================================
125 // Test b.all()
126 {
127 boost::dynamic_bitset<Block> b;
128 Tests::all(b);
129 Tests::all(~b);
130 Tests::all(b.set());
131 Tests::all(b.reset());
132 }
133 {
134 boost::dynamic_bitset<Block> b(std::string("0"));
135 Tests::all(b);
136 Tests::all(~b);
137 Tests::all(b.set());
138 Tests::all(b.reset());
139 }
140 {
141 boost::dynamic_bitset<Block> b(long_string);
142 Tests::all(b);
143 Tests::all(~b);
144 Tests::all(b.set());
145 Tests::all(b.reset());
146 }
147 //=====================================================================
148 // Test b.any()
149 {
150 boost::dynamic_bitset<Block> b;
151 Tests::any(b);
152 Tests::any(~b);
153 Tests::any(b.set());
154 Tests::any(b.reset());
155 }
156 {
157 boost::dynamic_bitset<Block> b(std::string("0"));
158 Tests::any(b);
159 Tests::any(~b);
160 Tests::any(b.set());
161 Tests::any(b.reset());
162 }
163 {
164 boost::dynamic_bitset<Block> b(long_string);
165 Tests::any(b);
166 Tests::any(~b);
167 Tests::any(b.set());
168 Tests::any(b.reset());
169 }
170 //=====================================================================
171 // Test b.none()
172 {
173 boost::dynamic_bitset<Block> b;
174 Tests::none(b);
175 Tests::none(~b);
176 Tests::none(b.set());
177 Tests::none(b.reset());
178 }
179 {
180 boost::dynamic_bitset<Block> b(std::string("0"));
181 Tests::none(b);
182 Tests::none(~b);
183 Tests::none(b.set());
184 Tests::none(b.reset());
185 }
186 {
187 boost::dynamic_bitset<Block> b(long_string);
188 Tests::none(b);
189 Tests::none(~b);
190 Tests::none(b.set());
191 Tests::none(b.reset());
192 }
193 //=====================================================================
194 // Test a.is_subset_of(b)
195 {
196 boost::dynamic_bitset<Block> a, b;
197 Tests::subset(a, b);
198 }
199 {
200 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
201 Tests::subset(a, b);
202 }
203 {
204 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
205 Tests::subset(a, b);
206 }
207 {
208 boost::dynamic_bitset<Block> a(long_string), b(long_string);
209 Tests::subset(a, b);
210 }
211 {
212 boost::dynamic_bitset<Block> a(long_string), b(long_string);
213 a[long_string.size()/2].flip();
214 Tests::subset(a, b);
215 }
216 {
217 boost::dynamic_bitset<Block> a(long_string), b(long_string);
218 b[long_string.size()/2].flip();
219 Tests::subset(a, b);
220 }
221 //=====================================================================
222 // Test a.is_proper_subset_of(b)
223 {
224 boost::dynamic_bitset<Block> a, b;
225 Tests::proper_subset(a, b);
226 }
227 {
228 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
229 Tests::proper_subset(a, b);
230 }
231 {
232 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
233 Tests::proper_subset(a, b);
234 }
235 {
236 boost::dynamic_bitset<Block> a(long_string), b(long_string);
237 Tests::proper_subset(a, b);
238 }
239 {
240 boost::dynamic_bitset<Block> a(long_string), b(long_string);
241 a[long_string.size()/2].flip();
242 Tests::proper_subset(a, b);
243 }
244 {
245 boost::dynamic_bitset<Block> a(long_string), b(long_string);
246 b[long_string.size()/2].flip();
247 Tests::proper_subset(a, b);
248 }
249 //=====================================================================
250 // Test intersects
251 {
252 bitset_type a; // empty
253 bitset_type b;
254 Tests::intersects(a, b);
255 }
256 {
257 bitset_type a;
258 bitset_type b(5, 8ul);
259 Tests::intersects(a, b);
260 }
261 {
262 bitset_type a(8, 0ul);
263 bitset_type b(15, 0ul);
264 b[9] = 1;
265 Tests::intersects(a, b);
266 }
267 {
268 bitset_type a(15, 0ul);
269 bitset_type b(22, 0ul);
270 a[14] = b[14] = 1;
271 Tests::intersects(a, b);
272 }
273 //=====================================================================
274 // Test find_first
275 {
276 // empty bitset
277 bitset_type b;
278 Tests::find_first(b);
279 }
280 {
281 // bitset of size 1
282 bitset_type b(1, 1ul);
283 Tests::find_first(b);
284 }
285 {
286 // all-0s bitset
287 bitset_type b(4 * bitset_type::bits_per_block, 0ul);
288 Tests::find_first(b);
289 }
290 {
291 // first bit on
292 bitset_type b(1, 1ul);
293 Tests::find_first(b);
294 }
295 {
296 // last bit on
297 bitset_type b(4 * bitset_type::bits_per_block - 1, 0ul);
298 b.set(b.size() - 1);
299 Tests::find_first(b);
300 }
301 //=====================================================================
302 // Test find_next
303 {
304 // empty bitset
305 bitset_type b;
306
307 // check
308 Tests::find_next(b, 0);
309 Tests::find_next(b, 1);
310 Tests::find_next(b, 200);
311 Tests::find_next(b, b.npos);
312 }
313 {
314 // bitset of size 1 (find_next can never find)
315 bitset_type b(1, 1ul);
316
317 // check
318 Tests::find_next(b, 0);
319 Tests::find_next(b, 1);
320 Tests::find_next(b, 200);
321 Tests::find_next(b, b.npos);
322 }
323 {
324 // all-1s bitset
325 bitset_type b(16 * bitset_type::bits_per_block);
326 b.set();
327
328 // check
329 const typename bitset_type::size_type larger_than_size = 5 + b.size();
330 for(typename bitset_type::size_type i = 0; i <= larger_than_size; ++i) {
331 Tests::find_next(b, i);
332 }
333 Tests::find_next(b, b.npos);
334 }
335 {
336 // a bitset with 1s at block boundary only
337 const int num_blocks = 32;
338 const int block_width = bitset_type::bits_per_block;
339
340 bitset_type b(num_blocks * block_width);
341 typename bitset_type::size_type i = block_width - 1;
342 for ( ; i < b.size(); i += block_width) {
343
344 b.set(i);
345 typename bitset_type::size_type first_in_block = i - (block_width - 1);
346 b.set(first_in_block);
347 }
348
349 // check
350 const typename bitset_type::size_type larger_than_size = 5 + b.size();
351 for (i = 0; i <= larger_than_size; ++i) {
352 Tests::find_next(b, i);
353 }
354 Tests::find_next(b, b.npos);
355
356 }
357 {
358 // bitset with alternate 1s and 0s
359 const typename bitset_type::size_type sz = 1000;
360 bitset_type b(sz);
361
362 typename bitset_type::size_type i = 0;
363 for ( ; i < sz; ++i) {
364 b[i] = (i%2 == 0);
365 }
366
367 // check
368 const typename bitset_type::size_type larger_than_size = 5 + b.size();
369 for (i = 0; i <= larger_than_size; ++i) {
370 Tests::find_next(b, i);
371 }
372 Tests::find_next(b, b.npos);
373
374 }
375 //=====================================================================
376 // Test operator==
377 {
378 boost::dynamic_bitset<Block> a, b;
379 Tests::operator_equal(a, b);
380 }
381 {
382 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
383 Tests::operator_equal(a, b);
384 }
385 {
386 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
387 Tests::operator_equal(a, b);
388 }
389 {
390 boost::dynamic_bitset<Block> a(long_string), b(long_string);
391 Tests::operator_equal(a, b);
392 }
393 {
394 boost::dynamic_bitset<Block> a(long_string), b(long_string);
395 a[long_string.size()/2].flip();
396 Tests::operator_equal(a, b);
397 }
398 {
399 boost::dynamic_bitset<Block> a(long_string), b(long_string);
400 b[long_string.size()/2].flip();
401 Tests::operator_equal(a, b);
402 }
403 //=====================================================================
404 // Test operator!=
405 {
406 boost::dynamic_bitset<Block> a, b;
407 Tests::operator_not_equal(a, b);
408 }
409 {
410 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
411 Tests::operator_not_equal(a, b);
412 }
413 {
414 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
415 Tests::operator_not_equal(a, b);
416 }
417 {
418 boost::dynamic_bitset<Block> a(long_string), b(long_string);
419 Tests::operator_not_equal(a, b);
420 }
421 {
422 boost::dynamic_bitset<Block> a(long_string), b(long_string);
423 a[long_string.size()/2].flip();
424 Tests::operator_not_equal(a, b);
425 }
426 {
427 boost::dynamic_bitset<Block> a(long_string), b(long_string);
428 b[long_string.size()/2].flip();
429 Tests::operator_not_equal(a, b);
430 }
431 //=====================================================================
432 // Test operator<
433 {
434 boost::dynamic_bitset<Block> a, b;
435 Tests::operator_less_than(a, b);
436 }
437 {
438 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
439 Tests::operator_less_than(a, b);
440 }
441 {
442 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
443 Tests::operator_less_than(a, b);
444 }
445 {
446 boost::dynamic_bitset<Block> a(std::string("10")), b(std::string("11"));
447 Tests::operator_less_than(a, b);
448 }
449 {
450 boost::dynamic_bitset<Block> a(long_string), b(long_string);
451 Tests::operator_less_than(a, b);
452 }
453 {
454 boost::dynamic_bitset<Block> a(long_string), b(long_string);
455 a[long_string.size()/2].flip();
456 Tests::operator_less_than(a, b);
457 }
458 {
459 boost::dynamic_bitset<Block> a(long_string), b(long_string);
460 b[long_string.size()/2].flip();
461 Tests::operator_less_than(a, b);
462 }
463 // check for consistency with ulong behaviour
464 {
465 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
466 assert(a < b);
467 }
468 {
469 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
470 assert(!(a < b));
471 }
472 {
473 boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
474 assert(!(a < b));
475 }
476 //=====================================================================
477 // Test operator<=
478 {
479 boost::dynamic_bitset<Block> a, b;
480 Tests::operator_less_than_eq(a, b);
481 }
482 {
483 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
484 Tests::operator_less_than_eq(a, b);
485 }
486 {
487 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
488 Tests::operator_less_than_eq(a, b);
489 }
490 {
491 boost::dynamic_bitset<Block> a(long_string), b(long_string);
492 Tests::operator_less_than_eq(a, b);
493 }
494 {
495 boost::dynamic_bitset<Block> a(long_string), b(long_string);
496 a[long_string.size()/2].flip();
497 Tests::operator_less_than_eq(a, b);
498 }
499 {
500 boost::dynamic_bitset<Block> a(long_string), b(long_string);
501 b[long_string.size()/2].flip();
502 Tests::operator_less_than_eq(a, b);
503 }
504 // check for consistency with ulong behaviour
505 {
506 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
507 assert(a <= b);
508 }
509 {
510 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
511 assert(a <= b);
512 }
513 {
514 boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
515 assert(!(a <= b));
516 }
517 //=====================================================================
518 // Test operator>
519 {
520 boost::dynamic_bitset<Block> a, b;
521 Tests::operator_greater_than(a, b);
522 }
523 {
524 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
525 Tests::operator_greater_than(a, b);
526 }
527 {
528 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
529 Tests::operator_greater_than(a, b);
530 }
531 {
532 boost::dynamic_bitset<Block> a(long_string), b(long_string);
533 Tests::operator_greater_than(a, b);
534 }
535 {
536 boost::dynamic_bitset<Block> a(long_string), b(long_string);
537 a[long_string.size()/2].flip();
538 Tests::operator_greater_than(a, b);
539 }
540 {
541 boost::dynamic_bitset<Block> a(long_string), b(long_string);
542 b[long_string.size()/2].flip();
543 Tests::operator_greater_than(a, b);
544 }
545 // check for consistency with ulong behaviour
546 {
547 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
548 assert(!(a > b));
549 }
550 {
551 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
552 assert(!(a > b));
553 }
554 {
555 boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
556 assert(a > b);
557 }
558 //=====================================================================
559 // Test operator<=
560 {
561 boost::dynamic_bitset<Block> a, b;
562 Tests::operator_greater_than_eq(a, b);
563 }
564 {
565 boost::dynamic_bitset<Block> a(std::string("0")), b(std::string("0"));
566 Tests::operator_greater_than_eq(a, b);
567 }
568 {
569 boost::dynamic_bitset<Block> a(std::string("1")), b(std::string("1"));
570 Tests::operator_greater_than_eq(a, b);
571 }
572 {
573 boost::dynamic_bitset<Block> a(long_string), b(long_string);
574 Tests::operator_greater_than_eq(a, b);
575 }
576 {
577 boost::dynamic_bitset<Block> a(long_string), b(long_string);
578 a[long_string.size()/2].flip();
579 Tests::operator_greater_than_eq(a, b);
580 }
581 {
582 boost::dynamic_bitset<Block> a(long_string), b(long_string);
583 b[long_string.size()/2].flip();
584 Tests::operator_greater_than_eq(a, b);
585 }
586 // check for consistency with ulong behaviour
587 {
588 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 5ul);
589 assert(!(a >= b));
590 }
591 {
592 boost::dynamic_bitset<Block> a(3, 4ul), b(3, 4ul);
593 assert(a >= b);
594 }
595 {
596 boost::dynamic_bitset<Block> a(3, 5ul), b(3, 4ul);
597 assert(a >= b);
598 }
599 //=====================================================================
600 // Test b.test(pos)
601 { // case pos >= b.size()
602 boost::dynamic_bitset<Block> b;
603 Tests::test_bit(b, 0);
604 }
605 { // case pos < b.size()
606 boost::dynamic_bitset<Block> b(std::string("0"));
607 Tests::test_bit(b, 0);
608 }
609 { // case pos == b.size() / 2
610 boost::dynamic_bitset<Block> b(long_string);
611 Tests::test_bit(b, long_string.size()/2);
612 }
613 //=====================================================================
614 // Test b.test_set(pos)
615 { // case pos >= b.size()
616 boost::dynamic_bitset<Block> b;
617 Tests::test_set_bit(b, 0, true);
618 Tests::test_set_bit(b, 0, false);
619 }
620 { // case pos < b.size()
621 boost::dynamic_bitset<Block> b(std::string("0"));
622 Tests::test_set_bit(b, 0, true);
623 Tests::test_set_bit(b, 0, false);
624 }
625 { // case pos == b.size() / 2
626 boost::dynamic_bitset<Block> b(long_string);
627 Tests::test_set_bit(b, long_string.size() / 2, true);
628 Tests::test_set_bit(b, long_string.size() / 2, false);
629 }
630 //=====================================================================
631 // Test b << pos
632 { // case pos == 0
633 std::size_t pos = 0;
634 boost::dynamic_bitset<Block> b(std::string("1010"));
635 Tests::operator_shift_left(b, pos);
636 }
637 { // case pos == size()/2
638 std::size_t pos = long_string.size() / 2;
639 boost::dynamic_bitset<Block> b(long_string);
640 Tests::operator_shift_left(b, pos);
641 }
642 { // case pos >= n
643 std::size_t pos = long_string.size();
644 boost::dynamic_bitset<Block> b(long_string);
645 Tests::operator_shift_left(b, pos);
646 }
647 //=====================================================================
648 // Test b >> pos
649 { // case pos == 0
650 std::size_t pos = 0;
651 boost::dynamic_bitset<Block> b(std::string("1010"));
652 Tests::operator_shift_right(b, pos);
653 }
654 { // case pos == size()/2
655 std::size_t pos = long_string.size() / 2;
656 boost::dynamic_bitset<Block> b(long_string);
657 Tests::operator_shift_right(b, pos);
658 }
659 { // case pos >= n
660 std::size_t pos = long_string.size();
661 boost::dynamic_bitset<Block> b(long_string);
662 Tests::operator_shift_right(b, pos);
663 }
664 //=====================================================================
665 // Test a & b
666 {
667 boost::dynamic_bitset<Block> lhs, rhs;
668 Tests::operator_and(lhs, rhs);
669 }
670 {
671 boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
672 Tests::operator_and(lhs, rhs);
673 }
674 {
675 boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
676 Tests::operator_and(lhs, rhs);
677 }
678 {
679 boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
680 Tests::operator_and(lhs, rhs);
681 }
682 //=====================================================================
683 // Test a | b
684 {
685 boost::dynamic_bitset<Block> lhs, rhs;
686 Tests::operator_or(lhs, rhs);
687 }
688 {
689 boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
690 Tests::operator_or(lhs, rhs);
691 }
692 {
693 boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
694 Tests::operator_or(lhs, rhs);
695 }
696 {
697 boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
698 Tests::operator_or(lhs, rhs);
699 }
700 //=====================================================================
701 // Test a^b
702 {
703 boost::dynamic_bitset<Block> lhs, rhs;
704 Tests::operator_xor(lhs, rhs);
705 }
706 {
707 boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
708 Tests::operator_xor(lhs, rhs);
709 }
710 {
711 boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
712 Tests::operator_xor(lhs, rhs);
713 }
714 {
715 boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
716 Tests::operator_xor(lhs, rhs);
717 }
718 //=====================================================================
719 // Test a-b
720 {
721 boost::dynamic_bitset<Block> lhs, rhs;
722 Tests::operator_sub(lhs, rhs);
723 }
724 {
725 boost::dynamic_bitset<Block> lhs(std::string("1")), rhs(std::string("0"));
726 Tests::operator_sub(lhs, rhs);
727 }
728 {
729 boost::dynamic_bitset<Block> lhs(long_string.size(), 0), rhs(long_string);
730 Tests::operator_sub(lhs, rhs);
731 }
732 {
733 boost::dynamic_bitset<Block> lhs(long_string.size(), 1), rhs(long_string);
734 Tests::operator_sub(lhs, rhs);
735 }
736 }
737
738 int
test_main(int,char * [])739 test_main(int, char*[])
740 {
741 run_test_cases<unsigned char>();
742 run_test_cases<unsigned short>();
743 run_test_cases<unsigned int>();
744 run_test_cases<unsigned long>();
745 # ifdef BOOST_HAS_LONG_LONG
746 run_test_cases< ::boost::ulong_long_type>();
747 # endif
748
749 return 0;
750 }
751