]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // ----------------------------------------------------------- |
2 | // Copyright (c) 2001 Jeremy Siek | |
3 | // Copyright (c) 2003-2006, 2008 Gennaro Prota | |
4 | // Copyright (c) 2014 Ahmed Charles | |
5 | // Copyright (c) 2014 Riccardo Marcangelo | |
92f5a8d4 | 6 | // Copyright (c) 2018 Evgeny Shulgin |
7c673cae FG |
7 | // |
8 | // Distributed under the Boost Software License, Version 1.0. | |
9 | // (See accompanying file LICENSE_1_0.txt or copy at | |
10 | // http://www.boost.org/LICENSE_1_0.txt) | |
11 | // | |
12 | // ----------------------------------------------------------- | |
13 | ||
14 | #ifndef BOOST_BITSET_TEST_HPP_GP_20040319 | |
15 | #define BOOST_BITSET_TEST_HPP_GP_20040319 | |
16 | ||
92f5a8d4 | 17 | #include <boost/config.hpp> |
7c673cae FG |
18 | #if !defined (BOOST_NO_STD_LOCALE) |
19 | # include <locale> | |
20 | #endif | |
21 | ||
22 | #include <vector> | |
23 | #include <fstream> // used for operator<< | |
24 | #include <string> // for (basic_string and) getline() | |
25 | #include <algorithm> // for std::min | |
26 | #include <assert.h> // <cassert> is sometimes macro-guarded :-( | |
27 | ||
92f5a8d4 TL |
28 | #include <boost/limits.hpp> |
29 | #include <boost/dynamic_bitset/dynamic_bitset.hpp> | |
30 | #include <boost/core/lightweight_test.hpp> | |
31 | #include <boost/filesystem.hpp> | |
7c673cae | 32 | |
7c673cae FG |
33 | template <typename Block> |
34 | inline bool nth_bit(Block num, std::size_t n) | |
35 | { | |
92f5a8d4 | 36 | #ifndef NDEBUG |
7c673cae FG |
37 | #ifdef __BORLANDC__ |
38 | // Borland deduces Block as a const qualified type, | |
39 | // and thus finds numeric_limits<Block> to be zero :( | |
40 | // (though not directly relevant here, see also | |
41 | // lib issue 559) | |
42 | int block_width = sizeof(Block) * CHAR_BIT; | |
43 | #else | |
44 | int block_width = std::numeric_limits<Block>::digits; | |
45 | #endif | |
7c673cae | 46 | assert(n < (std::size_t) block_width); |
92f5a8d4 TL |
47 | #endif |
48 | ||
7c673cae FG |
49 | return (num >> n) & 1; |
50 | } | |
51 | ||
52 | // A long, 'irregular', string useful for various tests | |
53 | std::string get_long_string() | |
54 | { | |
55 | const char * const p = | |
56 | // 6 5 4 3 2 1 | |
57 | // 3210987654321098765432109876543210987654321098765432109876543210 | |
58 | "1110011100011110000011110000011111110000000000000110101110000000" | |
59 | "1010101000011100011101010111110000101011111000001111100011100011" | |
60 | "0000000110000001000000111100000111100010101111111000000011100011" | |
61 | "1111111111111111111111111111111111111111111111111111111111111100" | |
62 | "1000001100000001111111111111110000000011111000111100001010100000" | |
63 | "101000111100011010101110011011000000010"; | |
64 | ||
65 | return std::string(p); | |
66 | } | |
67 | ||
92f5a8d4 | 68 | class scoped_temp_file |
7c673cae | 69 | { |
92f5a8d4 TL |
70 | public: |
71 | scoped_temp_file() | |
72 | : m_path(boost::filesystem::unique_path()) | |
73 | { | |
74 | } | |
75 | ||
76 | ~scoped_temp_file() | |
77 | { | |
78 | boost::filesystem::remove(m_path); | |
79 | } | |
80 | ||
81 | const boost::filesystem::path& path() const | |
82 | { | |
83 | return m_path; | |
84 | } | |
85 | ||
86 | private: | |
87 | boost::filesystem::path m_path; | |
88 | }; | |
7c673cae FG |
89 | |
90 | #if defined BOOST_OLD_IOSTREAMS || defined BOOST_NO_STD_LOCALE | |
91 | template <typename Stream> | |
92 | bool is_one_or_zero(const Stream & /*s*/, char c) | |
93 | { | |
94 | return c == '1' || c == '0'; | |
95 | } | |
96 | template <typename Stream> | |
97 | bool is_white_space(const Stream & /*s*/, char c) | |
98 | { | |
99 | return std::isspace(c); | |
100 | } | |
101 | #else | |
102 | template <typename Stream, typename Ch> | |
103 | bool is_one_or_zero(const Stream& s, Ch c) | |
104 | { | |
105 | typedef typename Stream::traits_type Tr; | |
106 | const Ch zero = s.widen('0'); | |
107 | const Ch one = s.widen('1'); | |
108 | ||
109 | return Tr::eq(c, one) || Tr::eq(c, zero); | |
110 | } | |
111 | template <typename Stream, typename Ch> | |
112 | bool is_white_space(const Stream & s, Ch c) | |
113 | { | |
114 | // NOTE: the using directive is to satisfy Borland 5.6.4 | |
115 | // with its own library (STLport), which doesn't | |
116 | // like std::isspace(c, loc) | |
117 | using namespace std; | |
118 | return isspace(c, s.getloc()); | |
119 | } | |
120 | #endif // defined BOOST_OLD_IOSTREAMS | |
121 | ||
122 | ||
123 | template <typename Stream> | |
124 | bool has_flags(const Stream& s, std::ios::iostate flags) | |
125 | { | |
126 | return (s.rdstate() & flags) != std::ios::goodbit; | |
127 | } | |
128 | ||
129 | ||
130 | // constructors | |
131 | // default (can't do this generically) | |
132 | ||
133 | template <typename Bitset> | |
134 | struct bitset_test { | |
135 | ||
136 | typedef typename Bitset::block_type Block; | |
137 | BOOST_STATIC_CONSTANT(int, bits_per_block = Bitset::bits_per_block); | |
138 | ||
139 | // from unsigned long | |
140 | // | |
141 | // Note: this is templatized so that we check that the do-the-right-thing | |
142 | // constructor dispatch is working correctly. | |
143 | // | |
144 | template <typename NumBits, typename Value> | |
145 | static void from_unsigned_long(NumBits num_bits, Value num) | |
146 | { | |
147 | // An object of size sz = num_bits is constructed: | |
148 | // - the first m bit positions are initialized to the corresponding | |
149 | // bit values in num (m being the smaller of sz and ulong_width) | |
150 | // | |
151 | // - any remaining bit positions are initialized to zero | |
152 | // | |
153 | ||
154 | Bitset b(static_cast<typename Bitset::size_type>(num_bits), static_cast<unsigned long>(num)); | |
155 | ||
156 | // OK, we can now cast to size_type | |
157 | typedef typename Bitset::size_type size_type; | |
158 | const size_type sz = static_cast<size_type>(num_bits); | |
159 | ||
92f5a8d4 | 160 | BOOST_TEST(b.size() == sz); |
7c673cae FG |
161 | |
162 | const std::size_t ulong_width = std::numeric_limits<unsigned long>::digits; | |
163 | size_type m = sz; | |
164 | if (ulong_width < sz) | |
165 | m = ulong_width; | |
166 | ||
167 | size_type i = 0; | |
168 | for ( ; i < m; ++i) | |
92f5a8d4 | 169 | BOOST_TEST(b.test(i) == nth_bit(static_cast<unsigned long>(num), i)); |
7c673cae | 170 | for ( ; i < sz; ++i) |
92f5a8d4 | 171 | BOOST_TEST(b.test(i) == 0); |
7c673cae FG |
172 | } |
173 | ||
174 | // from string | |
175 | // | |
176 | // Note: The corresponding function in dynamic_bitset (constructor | |
177 | // from a string) has several default arguments. Actually we don't | |
178 | // test the correct working of those defaults here (except for the | |
179 | // default of num_bits). I'm not sure what to do in this regard. | |
180 | // | |
181 | // Note2: the default argument expression for num_bits doesn't use | |
182 | // static_cast, to avoid a gcc 2.95.3 'sorry, not implemented' | |
183 | // | |
184 | template <typename Ch, typename Tr, typename Al> | |
185 | static void from_string(const std::basic_string<Ch, Tr, Al>& str, | |
186 | std::size_t pos, | |
187 | std::size_t max_char, | |
188 | std::size_t num_bits = (std::size_t)(-1)) | |
189 | { | |
190 | ||
191 | std::size_t rlen = (std::min)(max_char, str.size() - pos); | |
192 | ||
193 | // The resulting size N of the bitset is num_bits, if | |
194 | // that is different from the default arg, rlen otherwise. | |
195 | // Put M = the smaller of N and rlen, then character | |
196 | // position pos + M - 1 corresponds to bit position zero. | |
197 | // Subsequent decreasing character positions correspond to | |
198 | // increasing bit positions. | |
199 | ||
200 | const bool size_upon_string = num_bits == (std::size_t)(-1); | |
201 | Bitset b = size_upon_string ? | |
202 | Bitset(str, pos, max_char) | |
203 | : Bitset(str, pos, max_char, num_bits); | |
204 | ||
205 | const std::size_t actual_size = size_upon_string? rlen : num_bits; | |
92f5a8d4 | 206 | BOOST_TEST(b.size() == actual_size); |
7c673cae FG |
207 | std::size_t m = (std::min)(num_bits, rlen); |
208 | std::size_t j; | |
209 | for (j = 0; j < m; ++j) | |
92f5a8d4 | 210 | BOOST_TEST(b[j] == (str[pos + m - 1 - j] == '1')); |
7c673cae FG |
211 | // If M < N, remaining bit positions are zero |
212 | for (; j < actual_size; ++j) | |
92f5a8d4 | 213 | BOOST_TEST(b[j] == 0); |
7c673cae FG |
214 | |
215 | ||
216 | } | |
217 | ||
218 | static void to_block_range(const Bitset & b /*, BlockOutputIterator result*/) | |
219 | { | |
220 | typedef typename Bitset::size_type size_type; | |
221 | ||
222 | Block sentinel = 0xF0; | |
223 | int s = 8; // number of sentinels (must be *even*) | |
224 | int offset = s/2; | |
225 | std::vector<Block> v(b.num_blocks() + s, sentinel); | |
226 | ||
227 | boost::to_block_range(b, v.begin() + offset); | |
228 | ||
229 | assert(v.size() >= (size_type)s && (s >= 2) && (s % 2 == 0)); | |
230 | // check sentinels at both ends | |
231 | for(int i = 0; i < s/2; ++i) { | |
92f5a8d4 TL |
232 | BOOST_TEST(v[i] == sentinel); |
233 | BOOST_TEST(v[v.size()-1-i] == sentinel); | |
7c673cae FG |
234 | } |
235 | ||
236 | typename std::vector<Block>::const_iterator p = v.begin() + offset; | |
237 | for(size_type n = 0; n < b.num_blocks(); ++n, ++p) { | |
238 | typename Bitset::block_width_type i = 0; | |
239 | for(; i < bits_per_block; ++i) { | |
240 | size_type bit = n * bits_per_block + i; | |
92f5a8d4 | 241 | BOOST_TEST(nth_bit(*p, i) == (bit < b.size()? b[bit] : 0)); |
7c673cae FG |
242 | } |
243 | } | |
244 | } | |
245 | ||
246 | // TODO from_block_range (below) should be splitted | |
247 | ||
248 | // PRE: std::equal(first1, last1, first2) == true | |
249 | static void from_block_range(const std::vector<Block>& blocks) | |
250 | { | |
251 | { // test constructor from block range | |
252 | Bitset bset(blocks.begin(), blocks.end()); | |
253 | std::size_t n = blocks.size(); | |
254 | for (std::size_t b = 0; b < n; ++b) { | |
255 | typename Bitset::block_width_type i = 0; | |
256 | for (; i < bits_per_block; ++i) { | |
257 | std::size_t bit = b * bits_per_block + i; | |
92f5a8d4 | 258 | BOOST_TEST(bset[bit] == nth_bit(blocks[b], i)); |
7c673cae FG |
259 | } |
260 | } | |
92f5a8d4 | 261 | BOOST_TEST(bset.size() == n * bits_per_block); |
7c673cae FG |
262 | } |
263 | { // test boost::from_block_range | |
264 | const typename Bitset::size_type n = blocks.size(); | |
265 | Bitset bset(n * bits_per_block); | |
266 | boost::from_block_range(blocks.begin(), blocks.end(), bset); | |
267 | for (std::size_t b = 0; b < n; ++b) { | |
268 | typename Bitset::block_width_type i = 0; | |
269 | for (; i < bits_per_block; ++i) { | |
270 | std::size_t bit = b * bits_per_block + i; | |
92f5a8d4 | 271 | BOOST_TEST(bset[bit] == nth_bit(blocks[b], i)); |
7c673cae FG |
272 | } |
273 | } | |
92f5a8d4 | 274 | BOOST_TEST(n <= bset.num_blocks()); |
7c673cae FG |
275 | } |
276 | } | |
277 | ||
278 | // copy constructor (absent from std::bitset) | |
279 | static void copy_constructor(const Bitset& b) | |
280 | { | |
281 | Bitset copy(b); | |
92f5a8d4 | 282 | BOOST_TEST(b == copy); |
7c673cae FG |
283 | |
284 | // Changes to the copy do not affect the original | |
285 | if (b.size() > 0) { | |
286 | std::size_t pos = copy.size() / 2; | |
287 | copy.flip(pos); | |
92f5a8d4 | 288 | BOOST_TEST(copy[pos] != b[pos]); |
7c673cae FG |
289 | } |
290 | } | |
291 | ||
292 | // copy assignment operator (absent from std::bitset) | |
293 | static void copy_assignment_operator(const Bitset& lhs, const Bitset& rhs) | |
294 | { | |
295 | Bitset b(lhs); | |
296 | b = rhs; | |
297 | b = b; // self assignment check | |
92f5a8d4 | 298 | BOOST_TEST(b == rhs); |
7c673cae FG |
299 | |
300 | // Changes to the copy do not affect the original | |
301 | if (b.size() > 0) { | |
302 | std::size_t pos = b.size() / 2; | |
303 | b.flip(pos); | |
92f5a8d4 | 304 | BOOST_TEST(b[pos] != rhs[pos]); |
7c673cae FG |
305 | } |
306 | } | |
307 | ||
308 | static void max_size(const Bitset& b) | |
309 | { | |
92f5a8d4 | 310 | BOOST_TEST(b.max_size() > 0); |
7c673cae FG |
311 | } |
312 | ||
313 | #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES | |
314 | ||
315 | // move constructor (absent from std::bitset) | |
316 | static void move_constructor(const Bitset& b) | |
317 | { | |
318 | Bitset copy(boost::move(b)); | |
92f5a8d4 | 319 | BOOST_TEST(b == copy); |
7c673cae FG |
320 | } |
321 | ||
322 | // move assignment operator (absent from std::bitset) | |
323 | static void move_assignment_operator(const Bitset& lhs, const Bitset& rhs) | |
324 | { | |
325 | Bitset b(lhs); | |
326 | Bitset c(rhs); | |
327 | b = boost::move(c); | |
328 | b = boost::move(b); // self assignment check | |
92f5a8d4 | 329 | BOOST_TEST(b == rhs); |
7c673cae FG |
330 | } |
331 | ||
332 | #endif // BOOST_NO_CXX11_RVALUE_REFERENCES | |
333 | ||
334 | static void swap(const Bitset& lhs, const Bitset& rhs) | |
335 | { | |
336 | // bitsets must be swapped | |
337 | Bitset copy1(lhs); | |
338 | Bitset copy2(rhs); | |
339 | copy1.swap(copy2); | |
340 | ||
92f5a8d4 TL |
341 | BOOST_TEST(copy1 == rhs); |
342 | BOOST_TEST(copy2 == lhs); | |
7c673cae FG |
343 | |
344 | // references must be stable under a swap | |
345 | for(typename Bitset::size_type i = 0; i < lhs.size(); ++i) { | |
346 | Bitset b1(lhs); | |
347 | Bitset b2(rhs); | |
348 | typename Bitset::reference ref = b1[i]; | |
349 | bool x = ref; | |
350 | if (i < b2.size()) | |
351 | b2[i] = !x; // make sure b2[i] is different | |
352 | b1.swap(b2); | |
92f5a8d4 | 353 | BOOST_TEST(b2[i] == x); // now it must be equal.. |
7c673cae | 354 | b2.flip(i); |
92f5a8d4 TL |
355 | BOOST_TEST(ref == b2[i]); // .. and ref must be into b2 |
356 | BOOST_TEST(ref == !x); | |
7c673cae FG |
357 | } |
358 | ||
359 | } | |
360 | ||
361 | static void resize(const Bitset& lhs) | |
362 | { | |
363 | Bitset b(lhs); | |
364 | ||
365 | // Test no change in size | |
366 | b.resize(lhs.size()); | |
92f5a8d4 | 367 | BOOST_TEST(b == lhs); |
7c673cae FG |
368 | |
369 | // Test increase in size | |
370 | b.resize(lhs.size() * 2, true); | |
371 | ||
372 | std::size_t i; | |
373 | for (i = 0; i < lhs.size(); ++i) | |
92f5a8d4 | 374 | BOOST_TEST(b[i] == lhs[i]); |
7c673cae | 375 | for (; i < b.size(); ++i) |
92f5a8d4 | 376 | BOOST_TEST(b[i] == true); |
7c673cae FG |
377 | |
378 | // Test decrease in size | |
379 | b.resize(lhs.size()); | |
380 | for (i = 0; i < lhs.size(); ++i) | |
92f5a8d4 | 381 | BOOST_TEST(b[i] == lhs[i]); |
7c673cae FG |
382 | } |
383 | ||
384 | static void clear(const Bitset& lhs) | |
385 | { | |
386 | Bitset b(lhs); | |
387 | b.clear(); | |
92f5a8d4 | 388 | BOOST_TEST(b.size() == 0); |
7c673cae FG |
389 | } |
390 | ||
391 | static void pop_back(const Bitset& lhs) | |
392 | { | |
393 | Bitset b(lhs); | |
394 | b.pop_back(); | |
92f5a8d4 | 395 | BOOST_TEST(b.size() == lhs.size() - 1); |
7c673cae | 396 | for (std::size_t i = 0; i < b.size(); ++i) |
92f5a8d4 | 397 | BOOST_TEST(b[i] == lhs[i]); |
7c673cae FG |
398 | |
399 | b.pop_back(); | |
92f5a8d4 | 400 | BOOST_TEST(b.size() == lhs.size() - 2); |
7c673cae | 401 | for (std::size_t j = 0; j < b.size(); ++j) |
92f5a8d4 | 402 | BOOST_TEST(b[j] == lhs[j]); |
7c673cae FG |
403 | } |
404 | ||
405 | static void append_bit(const Bitset& lhs) | |
406 | { | |
407 | Bitset b(lhs); | |
408 | b.push_back(true); | |
92f5a8d4 TL |
409 | BOOST_TEST(b.size() == lhs.size() + 1); |
410 | BOOST_TEST(b[b.size() - 1] == true); | |
7c673cae | 411 | for (std::size_t i = 0; i < lhs.size(); ++i) |
92f5a8d4 | 412 | BOOST_TEST(b[i] == lhs[i]); |
7c673cae FG |
413 | |
414 | b.push_back(false); | |
92f5a8d4 TL |
415 | BOOST_TEST(b.size() == lhs.size() + 2); |
416 | BOOST_TEST(b[b.size() - 1] == false); | |
417 | BOOST_TEST(b[b.size() - 2] == true); | |
7c673cae | 418 | for (std::size_t j = 0; j < lhs.size(); ++j) |
92f5a8d4 | 419 | BOOST_TEST(b[j] == lhs[j]); |
7c673cae FG |
420 | } |
421 | ||
422 | static void append_block(const Bitset& lhs) | |
423 | { | |
424 | Bitset b(lhs); | |
425 | Block value(128); | |
426 | b.append(value); | |
92f5a8d4 | 427 | BOOST_TEST(b.size() == lhs.size() + bits_per_block); |
7c673cae | 428 | for (typename Bitset::block_width_type i = 0; i < bits_per_block; ++i) |
92f5a8d4 | 429 | BOOST_TEST(b[lhs.size() + i] == bool((value >> i) & 1)); |
7c673cae FG |
430 | } |
431 | ||
432 | static void append_block_range(const Bitset& lhs, const std::vector<Block>& blocks) | |
433 | { | |
434 | Bitset b(lhs), c(lhs); | |
435 | b.append(blocks.begin(), blocks.end()); | |
436 | for (typename std::vector<Block>::const_iterator i = blocks.begin(); | |
437 | i != blocks.end(); ++i) | |
438 | c.append(*i); | |
92f5a8d4 | 439 | BOOST_TEST(b == c); |
7c673cae FG |
440 | } |
441 | ||
442 | // operator[] and reference members | |
443 | // PRE: b[i] == bit_vec[i] | |
444 | static void operator_bracket(const Bitset& lhs, const std::vector<bool>& bit_vec) | |
445 | { | |
446 | Bitset b(lhs); | |
447 | std::size_t i, j, k; | |
448 | ||
449 | // x = b[i] | |
450 | // x = ~b[i] | |
451 | for (i = 0; i < b.size(); ++i) { | |
452 | bool x = b[i]; | |
92f5a8d4 | 453 | BOOST_TEST(x == bit_vec[i]); |
7c673cae | 454 | x = ~b[i]; |
92f5a8d4 | 455 | BOOST_TEST(x == !bit_vec[i]); |
7c673cae FG |
456 | } |
457 | Bitset prev(b); | |
458 | ||
459 | // b[i] = x | |
460 | for (j = 0; j < b.size(); ++j) { | |
461 | bool x = !prev[j]; | |
462 | b[j] = x; | |
463 | for (k = 0; k < b.size(); ++k) | |
464 | if (j == k) | |
92f5a8d4 | 465 | BOOST_TEST(b[k] == x); |
7c673cae | 466 | else |
92f5a8d4 | 467 | BOOST_TEST(b[k] == prev[k]); |
7c673cae FG |
468 | b[j] = prev[j]; |
469 | } | |
470 | b.flip(); | |
471 | ||
472 | // b[i] = b[j] | |
473 | for (i = 0; i < b.size(); ++i) { | |
474 | b[i] = prev[i]; | |
475 | for (j = 0; j < b.size(); ++j) { | |
476 | if (i == j) | |
92f5a8d4 | 477 | BOOST_TEST(b[j] == prev[j]); |
7c673cae | 478 | else |
92f5a8d4 | 479 | BOOST_TEST(b[j] == !prev[j]); |
7c673cae FG |
480 | } |
481 | b[i] = !prev[i]; | |
482 | } | |
483 | ||
484 | // b[i].flip() | |
485 | for (i = 0; i < b.size(); ++i) { | |
486 | b[i].flip(); | |
487 | for (j = 0; j < b.size(); ++j) { | |
488 | if (i == j) | |
92f5a8d4 | 489 | BOOST_TEST(b[j] == prev[j]); |
7c673cae | 490 | else |
92f5a8d4 | 491 | BOOST_TEST(b[j] == !prev[j]); |
7c673cae FG |
492 | } |
493 | b[i].flip(); | |
494 | } | |
495 | } | |
496 | ||
497 | //=========================================================================== | |
498 | // bitwise operators | |
499 | ||
500 | // bitwise and assignment | |
501 | ||
502 | // PRE: b.size() == rhs.size() | |
503 | static void and_assignment(const Bitset& b, const Bitset& rhs) | |
504 | { | |
505 | Bitset lhs(b); | |
506 | Bitset prev(lhs); | |
507 | lhs &= rhs; | |
508 | // Clears each bit in lhs for which the corresponding bit in rhs is | |
509 | // clear, and leaves all other bits unchanged. | |
510 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
511 | if (rhs[I] == 0) | |
92f5a8d4 | 512 | BOOST_TEST(lhs[I] == 0); |
7c673cae | 513 | else |
92f5a8d4 | 514 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
515 | } |
516 | ||
517 | // PRE: b.size() == rhs.size() | |
518 | static void or_assignment(const Bitset& b, const Bitset& rhs) | |
519 | { | |
520 | Bitset lhs(b); | |
521 | Bitset prev(lhs); | |
522 | lhs |= rhs; | |
523 | // Sets each bit in lhs for which the corresponding bit in rhs is set, and | |
524 | // leaves all other bits unchanged. | |
525 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
526 | if (rhs[I] == 1) | |
92f5a8d4 | 527 | BOOST_TEST(lhs[I] == 1); |
7c673cae | 528 | else |
92f5a8d4 | 529 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
530 | } |
531 | ||
532 | // PRE: b.size() == rhs.size() | |
533 | static void xor_assignment(const Bitset& b, const Bitset& rhs) | |
534 | { | |
535 | Bitset lhs(b); | |
536 | Bitset prev(lhs); | |
537 | lhs ^= rhs; | |
538 | // Flips each bit in lhs for which the corresponding bit in rhs is set, | |
539 | // and leaves all other bits unchanged. | |
540 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
541 | if (rhs[I] == 1) | |
92f5a8d4 | 542 | BOOST_TEST(lhs[I] == !prev[I]); |
7c673cae | 543 | else |
92f5a8d4 | 544 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
545 | } |
546 | ||
547 | // PRE: b.size() == rhs.size() | |
548 | static void sub_assignment(const Bitset& b, const Bitset& rhs) | |
549 | { | |
550 | Bitset lhs(b); | |
551 | Bitset prev(lhs); | |
552 | lhs -= rhs; | |
553 | // Resets each bit in lhs for which the corresponding bit in rhs is set, | |
554 | // and leaves all other bits unchanged. | |
555 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
556 | if (rhs[I] == 1) | |
92f5a8d4 | 557 | BOOST_TEST(lhs[I] == 0); |
7c673cae | 558 | else |
92f5a8d4 | 559 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
560 | } |
561 | ||
562 | static void shift_left_assignment(const Bitset& b, std::size_t pos) | |
563 | { | |
564 | Bitset lhs(b); | |
565 | Bitset prev(lhs); | |
566 | lhs <<= pos; | |
567 | // Replaces each bit at position I in lhs with the following value: | |
568 | // - If I < pos, the new value is zero | |
569 | // - If I >= pos, the new value is the previous value of the bit at | |
570 | // position I - pos | |
571 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
572 | if (I < pos) | |
92f5a8d4 | 573 | BOOST_TEST(lhs[I] == 0); |
7c673cae | 574 | else |
92f5a8d4 | 575 | BOOST_TEST(lhs[I] == prev[I - pos]); |
7c673cae FG |
576 | } |
577 | ||
578 | static void shift_right_assignment(const Bitset& b, std::size_t pos) | |
579 | { | |
580 | Bitset lhs(b); | |
581 | Bitset prev(lhs); | |
582 | lhs >>= pos; | |
583 | // Replaces each bit at position I in lhs with the following value: | |
584 | // - If pos >= N - I, the new value is zero | |
585 | // - If pos < N - I, the new value is the previous value of the bit at | |
586 | // position I + pos | |
587 | std::size_t N = lhs.size(); | |
588 | for (std::size_t I = 0; I < N; ++I) | |
589 | if (pos >= N - I) | |
92f5a8d4 | 590 | BOOST_TEST(lhs[I] == 0); |
7c673cae | 591 | else |
92f5a8d4 | 592 | BOOST_TEST(lhs[I] == prev[I + pos]); |
7c673cae FG |
593 | } |
594 | ||
595 | ||
596 | static void set_all(const Bitset& b) | |
597 | { | |
598 | Bitset lhs(b); | |
599 | lhs.set(); | |
600 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
92f5a8d4 | 601 | BOOST_TEST(lhs[I] == 1); |
7c673cae FG |
602 | } |
603 | ||
604 | static void set_one(const Bitset& b, std::size_t pos, bool value) | |
605 | { | |
606 | Bitset lhs(b); | |
607 | std::size_t N = lhs.size(); | |
608 | if (pos < N) { | |
609 | Bitset prev(lhs); | |
610 | // Stores a new value in the bit at position pos in lhs. | |
611 | lhs.set(pos, value); | |
92f5a8d4 | 612 | BOOST_TEST(lhs[pos] == value); |
7c673cae FG |
613 | |
614 | // All other values of lhs remain unchanged | |
615 | for (std::size_t I = 0; I < N; ++I) | |
616 | if (I != pos) | |
92f5a8d4 | 617 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
618 | } else { |
619 | // Not in range, doesn't satisfy precondition. | |
620 | } | |
621 | } | |
622 | ||
92f5a8d4 TL |
623 | static void set_segment(const Bitset& b, std::size_t pos, |
624 | std::size_t len, bool value) | |
625 | { | |
626 | Bitset lhs(b); | |
627 | std::size_t N = lhs.size(); | |
628 | Bitset prev(lhs); | |
629 | lhs.set(pos, len, value); | |
630 | for (std::size_t I = 0; I < N; ++I) | |
631 | { | |
632 | if (I < pos || I >= pos + len) | |
633 | BOOST_TEST(lhs[I] == prev[I]); | |
634 | else | |
635 | BOOST_TEST(lhs[I] == value); | |
636 | } | |
637 | } | |
638 | ||
7c673cae FG |
639 | static void reset_all(const Bitset& b) |
640 | { | |
641 | Bitset lhs(b); | |
642 | // Resets all bits in lhs | |
643 | lhs.reset(); | |
644 | for (std::size_t I = 0; I < lhs.size(); ++I) | |
92f5a8d4 | 645 | BOOST_TEST(lhs[I] == 0); |
7c673cae FG |
646 | } |
647 | ||
648 | static void reset_one(const Bitset& b, std::size_t pos) | |
649 | { | |
650 | Bitset lhs(b); | |
651 | std::size_t N = lhs.size(); | |
652 | if (pos < N) { | |
653 | Bitset prev(lhs); | |
654 | lhs.reset(pos); | |
655 | // Resets the bit at position pos in lhs | |
92f5a8d4 | 656 | BOOST_TEST(lhs[pos] == 0); |
7c673cae FG |
657 | |
658 | // All other values of lhs remain unchanged | |
659 | for (std::size_t I = 0; I < N; ++I) | |
660 | if (I != pos) | |
92f5a8d4 | 661 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
662 | } else { |
663 | // Not in range, doesn't satisfy precondition. | |
664 | } | |
665 | } | |
666 | ||
92f5a8d4 TL |
667 | static void reset_segment(const Bitset& b, std::size_t pos, |
668 | std::size_t len) | |
669 | { | |
670 | Bitset lhs(b); | |
671 | std::size_t N = lhs.size(); | |
672 | Bitset prev(lhs); | |
673 | lhs.reset(pos, len); | |
674 | for (std::size_t I = 0; I < N; ++I) | |
675 | { | |
676 | if (I < pos || I >= pos + len) | |
677 | BOOST_TEST(lhs[I] == prev[I]); | |
678 | else | |
679 | BOOST_TEST(!lhs[I]); | |
680 | } | |
681 | } | |
682 | ||
7c673cae FG |
683 | static void operator_flip(const Bitset& b) |
684 | { | |
685 | Bitset lhs(b); | |
686 | Bitset x(lhs); | |
92f5a8d4 | 687 | BOOST_TEST(~lhs == x.flip()); |
7c673cae FG |
688 | } |
689 | ||
690 | static void flip_all(const Bitset& b) | |
691 | { | |
692 | Bitset lhs(b); | |
693 | std::size_t N = lhs.size(); | |
694 | Bitset prev(lhs); | |
695 | lhs.flip(); | |
696 | // Toggles all the bits in lhs | |
697 | for (std::size_t I = 0; I < N; ++I) | |
92f5a8d4 | 698 | BOOST_TEST(lhs[I] == !prev[I]); |
7c673cae FG |
699 | } |
700 | ||
701 | static void flip_one(const Bitset& b, std::size_t pos) | |
702 | { | |
703 | Bitset lhs(b); | |
704 | std::size_t N = lhs.size(); | |
705 | if (pos < N) { | |
706 | Bitset prev(lhs); | |
707 | lhs.flip(pos); | |
708 | // Toggles the bit at position pos in lhs | |
92f5a8d4 | 709 | BOOST_TEST(lhs[pos] == !prev[pos]); |
7c673cae FG |
710 | |
711 | // All other values of lhs remain unchanged | |
712 | for (std::size_t I = 0; I < N; ++I) | |
713 | if (I != pos) | |
92f5a8d4 | 714 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
715 | } else { |
716 | // Not in range, doesn't satisfy precondition. | |
717 | } | |
718 | } | |
719 | ||
92f5a8d4 TL |
720 | static void flip_segment(const Bitset& b, std::size_t pos, |
721 | std::size_t len) | |
722 | { | |
723 | Bitset lhs(b); | |
724 | std::size_t N = lhs.size(); | |
725 | Bitset prev(lhs); | |
726 | lhs.flip(pos, len); | |
727 | for (std::size_t I = 0; I < N; ++I) | |
728 | { | |
729 | if (I < pos || I >= pos + len) | |
730 | BOOST_TEST(lhs[I] == prev[I]); | |
731 | else | |
732 | BOOST_TEST(lhs[I] != prev[I]); | |
733 | } | |
734 | } | |
735 | ||
7c673cae FG |
736 | // empty |
737 | static void empty(const Bitset& b) | |
738 | { | |
92f5a8d4 | 739 | BOOST_TEST(b.empty() == (b.size() == 0)); |
7c673cae FG |
740 | } |
741 | ||
742 | // to_ulong() | |
743 | static void to_ulong(const Bitset& lhs) | |
744 | { | |
745 | typedef unsigned long result_type; | |
746 | std::size_t n = std::numeric_limits<result_type>::digits; | |
747 | std::size_t sz = lhs.size(); | |
748 | ||
749 | bool will_overflow = false; | |
750 | for (std::size_t i = n; i < sz; ++i) { | |
751 | if (lhs.test(i) != 0) { | |
752 | will_overflow = true; | |
753 | break; | |
754 | } | |
755 | } | |
756 | if (will_overflow) { | |
757 | try { | |
758 | (void)lhs.to_ulong(); | |
92f5a8d4 | 759 | BOOST_TEST(false); // It should have thrown an exception |
7c673cae FG |
760 | } catch (std::overflow_error & ex) { |
761 | // Good! | |
92f5a8d4 | 762 | BOOST_TEST(!!ex.what()); |
7c673cae | 763 | } catch (...) { |
92f5a8d4 | 764 | BOOST_TEST(false); // threw the wrong exception |
7c673cae FG |
765 | } |
766 | } else { | |
767 | result_type num = lhs.to_ulong(); | |
768 | // Be sure the number is right | |
769 | if (sz == 0) | |
92f5a8d4 | 770 | BOOST_TEST(num == 0); |
7c673cae FG |
771 | else { |
772 | for (std::size_t i = 0; i < sz; ++i) | |
92f5a8d4 | 773 | BOOST_TEST(lhs[i] == (i < n ? nth_bit(num, i) : 0)); |
7c673cae FG |
774 | } |
775 | } | |
776 | } | |
777 | ||
778 | // to_string() | |
779 | static void to_string(const Bitset& b) | |
780 | { | |
781 | std::string str; | |
782 | boost::to_string(b, str); | |
92f5a8d4 | 783 | BOOST_TEST(str.size() == b.size()); |
7c673cae | 784 | for (std::size_t i = 0; i < b.size(); ++i) |
92f5a8d4 | 785 | BOOST_TEST(str[b.size() - 1 - i] ==(b.test(i)? '1':'0')); |
7c673cae FG |
786 | } |
787 | ||
788 | static void count(const Bitset& b) | |
789 | { | |
790 | std::size_t c = b.count(); | |
791 | std::size_t actual = 0; | |
792 | for (std::size_t i = 0; i < b.size(); ++i) | |
793 | if (b[i]) | |
794 | ++actual; | |
92f5a8d4 | 795 | BOOST_TEST(c == actual); |
7c673cae FG |
796 | } |
797 | ||
798 | static void size(const Bitset& b) | |
799 | { | |
92f5a8d4 | 800 | BOOST_TEST(Bitset(b).set().count() == b.size()); |
7c673cae FG |
801 | } |
802 | ||
803 | static void capacity_test_one(const Bitset& lhs) | |
804 | { | |
805 | //empty bitset | |
806 | Bitset b(lhs); | |
92f5a8d4 | 807 | BOOST_TEST(b.capacity() == 0); |
7c673cae FG |
808 | } |
809 | ||
810 | static void capacity_test_two(const Bitset& lhs) | |
811 | { | |
812 | //bitset constructed with size "100" | |
813 | Bitset b(lhs); | |
92f5a8d4 | 814 | BOOST_TEST(b.capacity() >= 100); |
7c673cae | 815 | b.resize(200); |
92f5a8d4 | 816 | BOOST_TEST(b.capacity() >= 200); |
7c673cae FG |
817 | } |
818 | ||
819 | static void reserve_test_one(const Bitset& lhs) | |
820 | { | |
821 | //empty bitset | |
822 | Bitset b(lhs); | |
823 | b.reserve(16); | |
92f5a8d4 | 824 | BOOST_TEST(b.capacity() >= 16); |
7c673cae FG |
825 | } |
826 | ||
827 | static void reserve_test_two(const Bitset& lhs) | |
828 | { | |
829 | //bitset constructed with size "100" | |
830 | Bitset b(lhs); | |
92f5a8d4 | 831 | BOOST_TEST(b.capacity() >= 100); |
7c673cae | 832 | b.reserve(60); |
92f5a8d4 TL |
833 | BOOST_TEST(b.size() == 100); |
834 | BOOST_TEST(b.capacity() >= 100); | |
7c673cae | 835 | b.reserve(160); |
92f5a8d4 TL |
836 | BOOST_TEST(b.size() == 100); |
837 | BOOST_TEST(b.capacity() >= 160); | |
7c673cae FG |
838 | } |
839 | ||
840 | static void shrink_to_fit_test_one(const Bitset& lhs) | |
841 | { | |
842 | //empty bitset | |
843 | Bitset b(lhs); | |
844 | b.shrink_to_fit(); | |
92f5a8d4 TL |
845 | BOOST_TEST(b.size() == 0); |
846 | BOOST_TEST(b.capacity() == 0); | |
7c673cae FG |
847 | } |
848 | ||
849 | static void shrink_to_fit_test_two(const Bitset& lhs) | |
850 | { | |
851 | //bitset constructed with size "100" | |
852 | Bitset b(lhs); | |
853 | b.shrink_to_fit(); | |
92f5a8d4 TL |
854 | BOOST_TEST(b.capacity() >= 100); |
855 | BOOST_TEST(b.size() == 100); | |
7c673cae | 856 | b.reserve(200); |
92f5a8d4 TL |
857 | BOOST_TEST(b.capacity() >= 200); |
858 | BOOST_TEST(b.size() == 100); | |
7c673cae | 859 | b.shrink_to_fit(); |
92f5a8d4 TL |
860 | BOOST_TEST(b.capacity() < 200); |
861 | BOOST_TEST(b.size() == 100); | |
7c673cae FG |
862 | } |
863 | ||
864 | static void all(const Bitset& b) | |
865 | { | |
92f5a8d4 | 866 | BOOST_TEST(b.all() == (b.count() == b.size())); |
7c673cae FG |
867 | bool result = true; |
868 | for(std::size_t i = 0; i < b.size(); ++i) | |
869 | if(!b[i]) { | |
870 | result = false; | |
871 | break; | |
872 | } | |
92f5a8d4 | 873 | BOOST_TEST(b.all() == result); |
7c673cae FG |
874 | } |
875 | ||
876 | static void any(const Bitset& b) | |
877 | { | |
92f5a8d4 | 878 | BOOST_TEST(b.any() == (b.count() != 0)); |
7c673cae FG |
879 | bool result = false; |
880 | for(std::size_t i = 0; i < b.size(); ++i) | |
881 | if(b[i]) { | |
882 | result = true; | |
883 | break; | |
884 | } | |
92f5a8d4 | 885 | BOOST_TEST(b.any() == result); |
7c673cae FG |
886 | } |
887 | ||
888 | static void none(const Bitset& b) | |
889 | { | |
890 | bool result = true; | |
891 | for(std::size_t i = 0; i < b.size(); ++i) { | |
892 | if(b[i]) { | |
893 | result = false; | |
894 | break; | |
895 | } | |
896 | } | |
92f5a8d4 | 897 | BOOST_TEST(b.none() == result); |
7c673cae FG |
898 | |
899 | // sanity | |
92f5a8d4 TL |
900 | BOOST_TEST(b.none() == !b.any()); |
901 | BOOST_TEST(b.none() == (b.count() == 0)); | |
7c673cae FG |
902 | } |
903 | ||
904 | static void subset(const Bitset& a, const Bitset& b) | |
905 | { | |
92f5a8d4 | 906 | BOOST_TEST(a.size() == b.size()); // PRE |
7c673cae FG |
907 | |
908 | bool is_subset = true; | |
909 | if (b.size()) { // could use b.any() but let's be safe | |
910 | for(std::size_t i = 0; i < a.size(); ++i) { | |
911 | if(a.test(i) && !b.test(i)) { | |
912 | is_subset = false; | |
913 | break; | |
914 | } | |
915 | } | |
916 | } | |
917 | else { | |
918 | // sanity | |
92f5a8d4 TL |
919 | BOOST_TEST(a.count() == 0); |
920 | BOOST_TEST(a.any() == false); | |
7c673cae FG |
921 | |
922 | //is_subset = (a.any() == false); | |
923 | } | |
924 | ||
92f5a8d4 | 925 | BOOST_TEST(a.is_subset_of(b) == is_subset); |
7c673cae FG |
926 | } |
927 | ||
928 | static void proper_subset(const Bitset& a, const Bitset& b) | |
929 | { | |
930 | // PRE: a.size() == b.size() | |
92f5a8d4 | 931 | BOOST_TEST(a.size() == b.size()); |
7c673cae FG |
932 | |
933 | bool is_proper = false; | |
934 | ||
935 | if (b.size() != 0) { | |
936 | ||
937 | // check it's a subset | |
938 | subset(a, b); | |
939 | ||
940 | // is it proper? | |
941 | for (std::size_t i = 0; i < a.size(); ++i) { | |
942 | if (!a.test(i) && b.test(i)) { | |
943 | is_proper = true; | |
944 | // sanity | |
92f5a8d4 TL |
945 | BOOST_TEST(a.count() < b.count()); |
946 | BOOST_TEST(b.any()); | |
7c673cae FG |
947 | } |
948 | } | |
949 | } | |
950 | ||
92f5a8d4 | 951 | BOOST_TEST(a.is_proper_subset_of(b) == is_proper); |
7c673cae | 952 | if (is_proper) |
92f5a8d4 | 953 | BOOST_TEST(b.is_proper_subset_of(a) != is_proper);// antisymmetry |
7c673cae FG |
954 | } |
955 | ||
956 | static void intersects(const Bitset& a, const Bitset& b) | |
957 | { | |
958 | bool have_intersection = false; | |
959 | ||
960 | typename Bitset::size_type m = a.size() < b.size() ? a.size() : b.size(); | |
961 | for(typename Bitset::size_type i = 0; i < m && !have_intersection; ++i) | |
962 | if(a[i] == true && b[i] == true) | |
963 | have_intersection = true; | |
964 | ||
92f5a8d4 | 965 | BOOST_TEST(a.intersects(b) == have_intersection); |
7c673cae | 966 | // also check commutativity |
92f5a8d4 | 967 | BOOST_TEST(b.intersects(a) == have_intersection); |
7c673cae FG |
968 | } |
969 | ||
970 | static void find_first(const Bitset& b) | |
971 | { | |
972 | // find first non-null bit, if any | |
973 | typename Bitset::size_type i = 0; | |
974 | while (i < b.size() && b[i] == 0) | |
975 | ++i; | |
976 | ||
977 | if (i == b.size()) | |
92f5a8d4 | 978 | BOOST_TEST(b.find_first() == Bitset::npos); // not found; |
7c673cae | 979 | else { |
92f5a8d4 TL |
980 | BOOST_TEST(b.find_first() == i); |
981 | BOOST_TEST(b.test(i) == true); | |
7c673cae FG |
982 | } |
983 | ||
984 | } | |
985 | ||
986 | static void find_next(const Bitset& b, typename Bitset::size_type prev) | |
987 | { | |
92f5a8d4 | 988 | BOOST_TEST(next_bit_on(b, prev) == b.find_next(prev)); |
7c673cae FG |
989 | } |
990 | ||
991 | static void operator_equal(const Bitset& a, const Bitset& b) | |
992 | { | |
993 | if (a == b) { | |
994 | for (std::size_t I = 0; I < a.size(); ++I) | |
92f5a8d4 | 995 | BOOST_TEST(a[I] == b[I]); |
7c673cae FG |
996 | } else { |
997 | if (a.size() == b.size()) { | |
998 | bool diff = false; | |
999 | for (std::size_t I = 0; I < a.size(); ++I) | |
1000 | if (a[I] != b[I]) { | |
1001 | diff = true; | |
1002 | break; | |
1003 | } | |
92f5a8d4 | 1004 | BOOST_TEST(diff); |
7c673cae FG |
1005 | } |
1006 | } | |
1007 | } | |
1008 | ||
1009 | static void operator_not_equal(const Bitset& a, const Bitset& b) | |
1010 | { | |
1011 | if (a != b) { | |
1012 | if (a.size() == b.size()) { | |
1013 | bool diff = false; | |
1014 | for (std::size_t I = 0; I < a.size(); ++I) | |
1015 | if (a[I] != b[I]) { | |
1016 | diff = true; | |
1017 | break; | |
1018 | } | |
92f5a8d4 | 1019 | BOOST_TEST(diff); |
7c673cae FG |
1020 | } |
1021 | } else { | |
1022 | for (std::size_t I = 0; I < a.size(); ++I) | |
92f5a8d4 | 1023 | BOOST_TEST(a[I] == b[I]); |
7c673cae FG |
1024 | } |
1025 | } | |
1026 | ||
1027 | static bool less_than(const Bitset& a, const Bitset& b) | |
1028 | { | |
b32b8144 FG |
1029 | |
1030 | typedef BOOST_DEDUCED_TYPENAME Bitset::size_type size_type; | |
1031 | ||
1032 | size_type asize(a.size()); | |
1033 | size_type bsize(b.size()); | |
1034 | ||
1035 | if (!bsize) | |
1036 | { | |
7c673cae | 1037 | return false; |
b32b8144 FG |
1038 | } |
1039 | else if (!asize) | |
1040 | { | |
1041 | return true; | |
1042 | } | |
7c673cae | 1043 | else |
b32b8144 FG |
1044 | { |
1045 | ||
1046 | // Compare from most significant to least. | |
1047 | ||
1048 | size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize)); | |
1049 | size_type I; | |
1050 | for (I = 0; I < leqsize; ++I,--asize,--bsize) | |
1051 | { | |
1052 | ||
1053 | size_type i = asize-1; | |
1054 | size_type j = bsize-1; | |
1055 | ||
1056 | if (a[i] < b[j]) | |
1057 | return true; | |
1058 | else if (a[i] > b[j]) | |
1059 | return false; | |
1060 | // if (a[i] = b[j]) skip to next | |
1061 | } | |
1062 | return (a.size() < b.size()); | |
1063 | } | |
7c673cae FG |
1064 | } |
1065 | ||
1066 | static typename Bitset::size_type next_bit_on(const Bitset& b, typename Bitset::size_type prev) | |
1067 | { | |
1068 | // helper function for find_next() | |
1069 | // | |
1070 | ||
1071 | if (b.none() == true || prev == Bitset::npos) | |
1072 | return Bitset::npos; | |
1073 | ||
1074 | ++prev; | |
1075 | ||
1076 | if (prev >= b.size()) | |
1077 | return Bitset::npos; | |
1078 | ||
1079 | typename Bitset::size_type i = prev; | |
1080 | while (i < b.size() && b[i] == 0) | |
1081 | ++i; | |
1082 | ||
1083 | return i==b.size() ? Bitset::npos : i; | |
1084 | ||
1085 | } | |
1086 | ||
1087 | static void operator_less_than(const Bitset& a, const Bitset& b) | |
1088 | { | |
1089 | if (less_than(a, b)) | |
92f5a8d4 | 1090 | BOOST_TEST(a < b); |
7c673cae | 1091 | else |
92f5a8d4 | 1092 | BOOST_TEST(!(a < b)); |
7c673cae FG |
1093 | } |
1094 | ||
1095 | static void operator_greater_than(const Bitset& a, const Bitset& b) | |
1096 | { | |
1097 | if (less_than(a, b) || a == b) | |
92f5a8d4 | 1098 | BOOST_TEST(!(a > b)); |
7c673cae | 1099 | else |
92f5a8d4 | 1100 | BOOST_TEST(a > b); |
7c673cae FG |
1101 | } |
1102 | ||
1103 | static void operator_less_than_eq(const Bitset& a, const Bitset& b) | |
1104 | { | |
1105 | if (less_than(a, b) || a == b) | |
92f5a8d4 | 1106 | BOOST_TEST(a <= b); |
7c673cae | 1107 | else |
92f5a8d4 | 1108 | BOOST_TEST(!(a <= b)); |
7c673cae FG |
1109 | } |
1110 | ||
1111 | static void operator_greater_than_eq(const Bitset& a, const Bitset& b) | |
1112 | { | |
1113 | if (less_than(a, b)) | |
92f5a8d4 | 1114 | BOOST_TEST(!(a >= b)); |
7c673cae | 1115 | else |
92f5a8d4 | 1116 | BOOST_TEST(a >= b); |
7c673cae FG |
1117 | } |
1118 | ||
1119 | static void test_bit(const Bitset& b, std::size_t pos) | |
1120 | { | |
1121 | Bitset lhs(b); | |
1122 | std::size_t N = lhs.size(); | |
1123 | if (pos < N) { | |
92f5a8d4 | 1124 | BOOST_TEST(lhs.test(pos) == lhs[pos]); |
7c673cae FG |
1125 | } else { |
1126 | // Not in range, doesn't satisfy precondition. | |
1127 | } | |
1128 | } | |
1129 | ||
1130 | static void test_set_bit(const Bitset& b, std::size_t pos, bool value) | |
1131 | { | |
1132 | Bitset lhs(b); | |
1133 | std::size_t N = lhs.size(); | |
1134 | if (pos < N) { | |
1135 | Bitset prev(lhs); | |
1136 | // Stores a new value in the bit at position pos in lhs. | |
92f5a8d4 TL |
1137 | BOOST_TEST(lhs.test_set(pos, value) == prev[pos]); |
1138 | BOOST_TEST(lhs[pos] == value); | |
7c673cae FG |
1139 | |
1140 | // All other values of lhs remain unchanged | |
1141 | for (std::size_t I = 0; I < N; ++I) | |
1142 | if (I != pos) | |
92f5a8d4 | 1143 | BOOST_TEST(lhs[I] == prev[I]); |
7c673cae FG |
1144 | } else { |
1145 | // Not in range, doesn't satisfy precondition. | |
1146 | } | |
1147 | } | |
1148 | ||
1149 | static void operator_shift_left(const Bitset& lhs, std::size_t pos) | |
1150 | { | |
1151 | Bitset x(lhs); | |
92f5a8d4 | 1152 | BOOST_TEST((lhs << pos) == (x <<= pos)); |
7c673cae FG |
1153 | } |
1154 | ||
1155 | static void operator_shift_right(const Bitset& lhs, std::size_t pos) | |
1156 | { | |
1157 | Bitset x(lhs); | |
92f5a8d4 | 1158 | BOOST_TEST((lhs >> pos) == (x >>= pos)); |
7c673cae FG |
1159 | } |
1160 | ||
1161 | // operator| | |
1162 | static | |
1163 | void operator_or(const Bitset& lhs, const Bitset& rhs) | |
1164 | { | |
1165 | Bitset x(lhs); | |
92f5a8d4 | 1166 | BOOST_TEST((lhs | rhs) == (x |= rhs)); |
7c673cae FG |
1167 | } |
1168 | ||
1169 | // operator& | |
1170 | static | |
1171 | void operator_and(const Bitset& lhs, const Bitset& rhs) | |
1172 | { | |
1173 | Bitset x(lhs); | |
92f5a8d4 | 1174 | BOOST_TEST((lhs & rhs) == (x &= rhs)); |
7c673cae FG |
1175 | } |
1176 | ||
1177 | // operator^ | |
1178 | static | |
1179 | void operator_xor(const Bitset& lhs, const Bitset& rhs) | |
1180 | { | |
1181 | Bitset x(lhs); | |
92f5a8d4 | 1182 | BOOST_TEST((lhs ^ rhs) == (x ^= rhs)); |
7c673cae FG |
1183 | } |
1184 | ||
1185 | // operator- | |
1186 | static | |
1187 | void operator_sub(const Bitset& lhs, const Bitset& rhs) | |
1188 | { | |
1189 | Bitset x(lhs); | |
92f5a8d4 | 1190 | BOOST_TEST((lhs - rhs) == (x -= rhs)); |
7c673cae FG |
1191 | } |
1192 | ||
1193 | //------------------------------------------------------------------------------ | |
1194 | // I/O TESTS | |
1195 | // The following tests assume the results of extraction (i.e.: contents, | |
1196 | // state and width of is, contents of b) only depend on input (the string | |
1197 | // str). In other words, they don't consider "unexpected" errors such as | |
1198 | // stream corruption or out of memory. The reason is simple: if e.g. the | |
1199 | // stream buffer throws, the stream layer may eat the exception and | |
1200 | // transform it into a badbit. But we can't trust the stream state here, | |
1201 | // because one of the things that we want to test is exactly whether it | |
1202 | // is set correctly. Similarly for insertion. | |
1203 | // | |
1204 | // To provide for these cases would require that the test functions know | |
1205 | // in advance whether the stream buffer and/or allocations will fail, and | |
1206 | // when; that is, we should write both a special allocator and a special | |
1207 | // stream buffer capable of throwing "on demand" and pass them here. | |
1208 | ||
1209 | // Seems overkill for these kinds of unit tests. | |
1210 | //------------------------------------------------------------------------- | |
1211 | ||
1212 | // operator<<( [basic_]ostream, | |
1213 | template <typename Stream> | |
1214 | static void stream_inserter(const Bitset & b, | |
1215 | Stream & s, | |
1216 | const char * file_name | |
1217 | ) | |
1218 | { | |
1219 | #if defined BOOST_OLD_IOSTREAMS | |
1220 | typedef char char_type; | |
1221 | typedef std::string string_type; | |
1222 | typedef ifstream corresponding_input_stream_type; | |
1223 | #else | |
1224 | typedef typename Stream::char_type char_type; | |
1225 | typedef std::basic_string<char_type> string_type; | |
1226 | typedef std::basic_ifstream<char_type> corresponding_input_stream_type; | |
1227 | ||
1228 | std::ios::iostate except = s.exceptions(); | |
1229 | #endif | |
1230 | ||
1231 | typedef typename Bitset::size_type size_type; | |
1232 | std::streamsize w = s.width(); | |
1233 | char_type fill_char = s.fill(); | |
1234 | std::ios::iostate oldstate = s.rdstate(); | |
1235 | bool stream_was_good = s.good(); | |
1236 | ||
1237 | bool did_throw = false; | |
1238 | try { | |
1239 | s << b; | |
1240 | } | |
1241 | #if defined BOOST_OLD_IOSTREAMS | |
1242 | catch(...) { | |
92f5a8d4 | 1243 | BOOST_TEST(false); |
7c673cae FG |
1244 | } |
1245 | #else | |
1246 | catch (const std::ios_base::failure &) { | |
92f5a8d4 | 1247 | BOOST_TEST((except & s.rdstate()) != 0); |
7c673cae FG |
1248 | did_throw = true; |
1249 | } catch (...) { | |
1250 | did_throw = true; | |
1251 | } | |
1252 | #endif | |
1253 | ||
92f5a8d4 | 1254 | BOOST_TEST(did_throw || !stream_was_good || (s.width() == 0)); |
7c673cae FG |
1255 | |
1256 | if (!stream_was_good) { | |
92f5a8d4 | 1257 | BOOST_TEST(s.good() == false); |
7c673cae FG |
1258 | |
1259 | // this should actually be oldstate == s.rdstate() | |
1260 | // but some implementations add badbit in the | |
1261 | // sentry constructor | |
1262 | // | |
92f5a8d4 TL |
1263 | BOOST_TEST((oldstate & s.rdstate()) == oldstate); |
1264 | BOOST_TEST(s.width() == w); | |
7c673cae FG |
1265 | } |
1266 | else { | |
1267 | if(!did_throw) | |
92f5a8d4 | 1268 | BOOST_TEST(s.width() == 0); |
7c673cae FG |
1269 | // This test require that os be an output _and_ input stream. |
1270 | // Of course dynamic_bitset's operator << doesn't require that. | |
1271 | ||
1272 | size_type total_len = w <= 0 || static_cast<size_type>(w) < b.size()? b.size() : static_cast<size_type>(w); | |
1273 | const string_type padding (total_len - b.size(), fill_char); | |
1274 | string_type expected; | |
1275 | boost::to_string(b, expected); | |
1276 | if ((s.flags() & std::ios::adjustfield) != std::ios::left) | |
1277 | expected = padding + expected; | |
1278 | else | |
1279 | expected = expected + padding; | |
1280 | ||
1281 | assert(expected.length() == total_len); | |
1282 | ||
1283 | // close, and reopen the file stream to verify contents | |
1284 | s.close(); | |
1285 | corresponding_input_stream_type is(file_name); | |
1286 | string_type contents; | |
1287 | std::getline(is, contents, char_type()); | |
92f5a8d4 | 1288 | BOOST_TEST(contents == expected); |
7c673cae FG |
1289 | } |
1290 | } | |
1291 | ||
1292 | // operator>>( [basic_]istream | |
1293 | template <typename Stream, typename String> | |
1294 | static void stream_extractor(Bitset& b, | |
1295 | Stream& is, | |
1296 | String& str | |
1297 | ) | |
1298 | { | |
1299 | // save necessary info then do extraction | |
1300 | // | |
1301 | const std::streamsize w = is.width(); | |
1302 | Bitset a_copy(b); | |
1303 | bool stream_was_good = is.good(); | |
1304 | ||
1305 | bool did_throw = false; | |
1306 | ||
1307 | #if defined BOOST_OLD_IOSTREAMS | |
1308 | bool has_stream_exceptions = false; | |
1309 | is >> b; | |
1310 | #else | |
1311 | const std::ios::iostate except = is.exceptions(); | |
1312 | bool has_stream_exceptions = true; | |
1313 | try { | |
1314 | is >> b; | |
1315 | } | |
1316 | catch(const std::ios::failure &) { | |
1317 | did_throw = true; | |
1318 | } | |
1319 | ||
1320 | // postconditions | |
92f5a8d4 | 1321 | BOOST_TEST(except == is.exceptions()); // paranoid |
7c673cae FG |
1322 | #endif |
1323 | //------------------------------------------------------------------ | |
1324 | ||
1325 | // postconditions | |
92f5a8d4 | 1326 | BOOST_TEST(b.size() <= b.max_size()); |
7c673cae | 1327 | if(w > 0) |
92f5a8d4 | 1328 | BOOST_TEST(b.size() <= static_cast<typename Bitset::size_type>(w)); |
7c673cae FG |
1329 | |
1330 | // throw if and only if required | |
1331 | if(has_stream_exceptions) { | |
1332 | const bool exceptional_state = has_flags(is, is.exceptions()); | |
92f5a8d4 | 1333 | BOOST_TEST(exceptional_state == did_throw); |
7c673cae FG |
1334 | } |
1335 | ||
1336 | typedef typename String::size_type size_type; | |
1337 | typedef typename String::value_type Ch; | |
1338 | size_type after_digits = 0; | |
1339 | ||
1340 | if(!stream_was_good) { | |
92f5a8d4 TL |
1341 | BOOST_TEST(has_flags(is, std::ios::failbit)); |
1342 | BOOST_TEST(b == a_copy); | |
1343 | BOOST_TEST(is.width() == (did_throw ? w : 0)); | |
7c673cae FG |
1344 | } |
1345 | else { | |
1346 | // stream was good(), parse the string; | |
1347 | // it may contain three parts, all of which are optional | |
1348 | // {spaces} {digits} {non-digits} | |
1349 | // opt opt opt | |
1350 | // | |
1351 | // The values of b.max_size() and is.width() may lead to | |
1352 | // ignore part of the digits, if any. | |
1353 | ||
1354 | size_type pos = 0; | |
1355 | size_type len = str.length(); | |
1356 | // {spaces} | |
1357 | for( ; pos < len && is_white_space(is, str[pos]); ++pos) | |
1358 | {} | |
1359 | size_type after_spaces = pos; | |
1360 | // {digits} or part of them | |
1361 | const typename Bitset::size_type max_digits = | |
1362 | w > 0 && static_cast<typename Bitset::size_type>(w) < b.max_size() | |
1363 | ? static_cast<typename Bitset::size_type>(w) : b.max_size(); | |
1364 | ||
1365 | for( ; pos < len && (pos - after_spaces) < max_digits; ++pos) { | |
1366 | if(!is_one_or_zero(is, str[pos])) | |
1367 | break; | |
1368 | } | |
1369 | after_digits = pos; | |
1370 | size_type num_digits = after_digits - after_spaces; | |
1371 | ||
1372 | // eofbit | |
1373 | if((after_digits == len && max_digits > num_digits )) | |
92f5a8d4 | 1374 | BOOST_TEST(has_flags(is, std::ios::eofbit)); |
7c673cae | 1375 | else |
92f5a8d4 | 1376 | BOOST_TEST(!has_flags(is, std::ios::eofbit)); |
7c673cae FG |
1377 | |
1378 | // failbit <=> there are no digits, except for the library | |
1379 | // issue explained below. | |
1380 | // | |
1381 | if(num_digits == 0) { | |
1382 | if(after_digits == len && has_stream_exceptions && | |
1383 | (is.exceptions() & std::ios::eofbit) != std::ios::goodbit) { | |
1384 | // This is a special case related to library issue 195: | |
1385 | // reaching eof when skipping whitespaces in the sentry ctor. | |
1386 | // The resolution says the sentry constructor should set *both* | |
1387 | // eofbit and failbit; but many implementations deliberately | |
1388 | // set eofbit only. See for instance: | |
1389 | // http://gcc.gnu.org/ml/libstdc++/2000-q1/msg00086.html | |
1390 | // | |
92f5a8d4 | 1391 | BOOST_TEST(did_throw); |
7c673cae FG |
1392 | |
1393 | } | |
1394 | else { | |
92f5a8d4 | 1395 | BOOST_TEST(has_flags(is, std::ios::failbit)); |
7c673cae FG |
1396 | } |
1397 | } | |
1398 | else | |
92f5a8d4 | 1399 | BOOST_TEST(!has_flags(is, std::ios::failbit)); |
7c673cae FG |
1400 | |
1401 | ||
1402 | if(num_digits == 0 && after_digits == len) { | |
1403 | // The VC6 library has a bug/non-conformity in the sentry | |
1404 | // constructor. It uses code like | |
1405 | // // skip whitespaces... | |
1406 | // int_type _C = rdbuf()->sgetc(); | |
1407 | // while (!_Tr::eq_int_type(_Tr::eof(), _C) ... | |
1408 | // | |
1409 | // For an empty file the while statement is never "entered" | |
1410 | // and the stream remains in good() state; thus the sentry | |
1411 | // object gives "true" when converted to bool. This is worse | |
1412 | // than the case above, because not only failbit is not set, | |
1413 | // but no bit is set at all, end we end up clearing the | |
1414 | // bitset though there's nothing in the file to be extracted. | |
1415 | // Note that the dynamic_bitset docs say a sentry object is | |
1416 | // constructed and then converted to bool, thus we rely on | |
1417 | // what the underlying library does. | |
1418 | // | |
1419 | #if !defined(BOOST_DINKUMWARE_STDLIB) || (BOOST_DINKUMWARE_STDLIB >= 306) | |
92f5a8d4 | 1420 | BOOST_TEST(b == a_copy); |
7c673cae | 1421 | #else |
92f5a8d4 | 1422 | BOOST_TEST(b.empty() == true); |
7c673cae FG |
1423 | #endif |
1424 | } | |
1425 | else { | |
1426 | String sub = str.substr(after_spaces, num_digits); | |
92f5a8d4 | 1427 | BOOST_TEST(b == Bitset(sub)); |
7c673cae FG |
1428 | } |
1429 | ||
1430 | // check width | |
92f5a8d4 | 1431 | BOOST_TEST(is.width() == 0 |
7c673cae FG |
1432 | || (after_digits == len && num_digits == 0 && did_throw)); |
1433 | } | |
1434 | ||
1435 | ||
1436 | // clear the stream to allow further reading then | |
1437 | // retrieve any remaining chars with a single getline() | |
1438 | is.exceptions(std::ios::goodbit); | |
1439 | is.clear(); | |
1440 | String remainder; | |
1441 | std::getline(is, remainder, Ch()); | |
1442 | if(stream_was_good) | |
92f5a8d4 | 1443 | BOOST_TEST(remainder == str.substr(after_digits)); |
7c673cae | 1444 | else |
92f5a8d4 | 1445 | BOOST_TEST(remainder == str); |
7c673cae FG |
1446 | |
1447 | } | |
1448 | ||
1449 | ||
1450 | }; | |
1451 | ||
1452 | ||
1453 | ||
1454 | #endif // include guard |