1 | // -*- C++ -*- |
2 | //===---------------------------- bitset ----------------------------------===// |
3 | // |
4 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
5 | // See https://llvm.org/LICENSE.txt for license information. |
6 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | |
10 | #ifndef _LIBCPP_BITSET |
11 | #define _LIBCPP_BITSET |
12 | |
13 | /* |
14 | bitset synopsis |
15 | |
16 | namespace std |
17 | { |
18 | |
19 | namespace std { |
20 | |
21 | template <size_t N> |
22 | class bitset |
23 | { |
24 | public: |
25 | // bit reference: |
26 | class reference |
27 | { |
28 | friend class bitset; |
29 | reference() noexcept; |
30 | public: |
31 | ~reference() noexcept; |
32 | reference& operator=(bool x) noexcept; // for b[i] = x; |
33 | reference& operator=(const reference&) noexcept; // for b[i] = b[j]; |
34 | bool operator~() const noexcept; // flips the bit |
35 | operator bool() const noexcept; // for x = b[i]; |
36 | reference& flip() noexcept; // for b[i].flip(); |
37 | }; |
38 | |
39 | // 23.3.5.1 constructors: |
40 | constexpr bitset() noexcept; |
41 | constexpr bitset(unsigned long long val) noexcept; |
42 | template <class charT> |
43 | explicit bitset(const charT* str, |
44 | typename basic_string<charT>::size_type n = basic_string<charT>::npos, |
45 | charT zero = charT('0'), charT one = charT('1')); |
46 | template<class charT, class traits, class Allocator> |
47 | explicit bitset(const basic_string<charT,traits,Allocator>& str, |
48 | typename basic_string<charT,traits,Allocator>::size_type pos = 0, |
49 | typename basic_string<charT,traits,Allocator>::size_type n = |
50 | basic_string<charT,traits,Allocator>::npos, |
51 | charT zero = charT('0'), charT one = charT('1')); |
52 | |
53 | // 23.3.5.2 bitset operations: |
54 | bitset& operator&=(const bitset& rhs) noexcept; |
55 | bitset& operator|=(const bitset& rhs) noexcept; |
56 | bitset& operator^=(const bitset& rhs) noexcept; |
57 | bitset& operator<<=(size_t pos) noexcept; |
58 | bitset& operator>>=(size_t pos) noexcept; |
59 | bitset& set() noexcept; |
60 | bitset& set(size_t pos, bool val = true); |
61 | bitset& reset() noexcept; |
62 | bitset& reset(size_t pos); |
63 | bitset operator~() const noexcept; |
64 | bitset& flip() noexcept; |
65 | bitset& flip(size_t pos); |
66 | |
67 | // element access: |
68 | constexpr bool operator[](size_t pos) const; // for b[i]; |
69 | reference operator[](size_t pos); // for b[i]; |
70 | unsigned long to_ulong() const; |
71 | unsigned long long to_ullong() const; |
72 | template <class charT, class traits, class Allocator> |
73 | basic_string<charT, traits, Allocator> to_string(charT zero = charT('0'), charT one = charT('1')) const; |
74 | template <class charT, class traits> |
75 | basic_string<charT, traits, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const; |
76 | template <class charT> |
77 | basic_string<charT, char_traits<charT>, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const; |
78 | basic_string<char, char_traits<char>, allocator<char> > to_string(char zero = '0', char one = '1') const; |
79 | size_t count() const noexcept; |
80 | constexpr size_t size() const noexcept; |
81 | bool operator==(const bitset& rhs) const noexcept; |
82 | bool operator!=(const bitset& rhs) const noexcept; |
83 | bool test(size_t pos) const; |
84 | bool all() const noexcept; |
85 | bool any() const noexcept; |
86 | bool none() const noexcept; |
87 | bitset operator<<(size_t pos) const noexcept; |
88 | bitset operator>>(size_t pos) const noexcept; |
89 | }; |
90 | |
91 | // 23.3.5.3 bitset operators: |
92 | template <size_t N> |
93 | bitset<N> operator&(const bitset<N>&, const bitset<N>&) noexcept; |
94 | |
95 | template <size_t N> |
96 | bitset<N> operator|(const bitset<N>&, const bitset<N>&) noexcept; |
97 | |
98 | template <size_t N> |
99 | bitset<N> operator^(const bitset<N>&, const bitset<N>&) noexcept; |
100 | |
101 | template <class charT, class traits, size_t N> |
102 | basic_istream<charT, traits>& |
103 | operator>>(basic_istream<charT, traits>& is, bitset<N>& x); |
104 | |
105 | template <class charT, class traits, size_t N> |
106 | basic_ostream<charT, traits>& |
107 | operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x); |
108 | |
109 | template <size_t N> struct hash<std::bitset<N>>; |
110 | |
111 | } // std |
112 | |
113 | */ |
114 | |
115 | #include <__config> |
116 | #include <__bit_reference> |
117 | #include <cstddef> |
118 | #include <climits> |
119 | #include <string> |
120 | #include <stdexcept> |
121 | #include <iosfwd> |
122 | #include <__functional_base> |
123 | |
124 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
125 | #pragma GCC system_header |
126 | #endif |
127 | |
128 | _LIBCPP_PUSH_MACROS |
129 | #include <__undef_macros> |
130 | |
131 | |
132 | _LIBCPP_BEGIN_NAMESPACE_STD |
133 | |
134 | template <size_t _N_words, size_t _Size> |
135 | class __bitset; |
136 | |
137 | template <size_t _N_words, size_t _Size> |
138 | struct __has_storage_type<__bitset<_N_words, _Size> > |
139 | { |
140 | static const bool value = true; |
141 | }; |
142 | |
143 | template <size_t _N_words, size_t _Size> |
144 | class __bitset |
145 | { |
146 | public: |
147 | typedef ptrdiff_t difference_type; |
148 | typedef size_t size_type; |
149 | typedef size_type __storage_type; |
150 | protected: |
151 | typedef __bitset __self; |
152 | typedef __storage_type* __storage_pointer; |
153 | typedef const __storage_type* __const_storage_pointer; |
154 | static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); |
155 | |
156 | friend class __bit_reference<__bitset>; |
157 | friend class __bit_const_reference<__bitset>; |
158 | friend class __bit_iterator<__bitset, false>; |
159 | friend class __bit_iterator<__bitset, true>; |
160 | friend struct __bit_array<__bitset>; |
161 | |
162 | __storage_type __first_[_N_words]; |
163 | |
164 | typedef __bit_reference<__bitset> reference; |
165 | typedef __bit_const_reference<__bitset> const_reference; |
166 | typedef __bit_iterator<__bitset, false> iterator; |
167 | typedef __bit_iterator<__bitset, true> const_iterator; |
168 | |
169 | _LIBCPP_INLINE_VISIBILITY |
170 | _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT; |
171 | _LIBCPP_INLINE_VISIBILITY |
172 | explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT; |
173 | |
174 | _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT |
175 | {return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} |
176 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT |
177 | {return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} |
178 | _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT |
179 | {return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} |
180 | _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT |
181 | {return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} |
182 | |
183 | _LIBCPP_INLINE_VISIBILITY |
184 | void operator&=(const __bitset& __v) _NOEXCEPT; |
185 | _LIBCPP_INLINE_VISIBILITY |
186 | void operator|=(const __bitset& __v) _NOEXCEPT; |
187 | _LIBCPP_INLINE_VISIBILITY |
188 | void operator^=(const __bitset& __v) _NOEXCEPT; |
189 | |
190 | void flip() _NOEXCEPT; |
191 | _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const |
192 | {return to_ulong(integral_constant<bool, _Size < sizeof(unsigned long) * CHAR_BIT>());} |
193 | _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const |
194 | {return to_ullong(integral_constant<bool, _Size < sizeof(unsigned long long) * CHAR_BIT>());} |
195 | |
196 | bool all() const _NOEXCEPT; |
197 | bool any() const _NOEXCEPT; |
198 | _LIBCPP_INLINE_VISIBILITY |
199 | size_t __hash_code() const _NOEXCEPT; |
200 | private: |
201 | #ifdef _LIBCPP_CXX03_LANG |
202 | void __init(unsigned long long __v, false_type) _NOEXCEPT; |
203 | _LIBCPP_INLINE_VISIBILITY |
204 | void __init(unsigned long long __v, true_type) _NOEXCEPT; |
205 | #endif // _LIBCPP_CXX03_LANG |
206 | unsigned long to_ulong(false_type) const; |
207 | _LIBCPP_INLINE_VISIBILITY |
208 | unsigned long to_ulong(true_type) const; |
209 | unsigned long long to_ullong(false_type) const; |
210 | _LIBCPP_INLINE_VISIBILITY |
211 | unsigned long long to_ullong(true_type) const; |
212 | _LIBCPP_INLINE_VISIBILITY |
213 | unsigned long long to_ullong(true_type, false_type) const; |
214 | unsigned long long to_ullong(true_type, true_type) const; |
215 | }; |
216 | |
217 | template <size_t _N_words, size_t _Size> |
218 | inline |
219 | _LIBCPP_CONSTEXPR |
220 | __bitset<_N_words, _Size>::__bitset() _NOEXCEPT |
221 | #ifndef _LIBCPP_CXX03_LANG |
222 | : __first_{0} |
223 | #endif |
224 | { |
225 | #ifdef _LIBCPP_CXX03_LANG |
226 | _VSTD::fill_n(__first_, _N_words, __storage_type(0)); |
227 | #endif |
228 | } |
229 | |
230 | #ifdef _LIBCPP_CXX03_LANG |
231 | |
232 | template <size_t _N_words, size_t _Size> |
233 | void |
234 | __bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) _NOEXCEPT |
235 | { |
236 | __storage_type __t[sizeof(unsigned long long) / sizeof(__storage_type)]; |
237 | size_t __sz = _Size; |
238 | for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word, __sz -= __bits_per_word ) |
239 | if ( __sz < __bits_per_word) |
240 | __t[__i] = static_cast<__storage_type>(__v) & ( 1ULL << __sz ) - 1; |
241 | else |
242 | __t[__i] = static_cast<__storage_type>(__v); |
243 | |
244 | _VSTD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_); |
245 | _VSTD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]), |
246 | __storage_type(0)); |
247 | } |
248 | |
249 | template <size_t _N_words, size_t _Size> |
250 | inline _LIBCPP_INLINE_VISIBILITY |
251 | void |
252 | __bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) _NOEXCEPT |
253 | { |
254 | __first_[0] = __v; |
255 | if (_Size < __bits_per_word) |
256 | __first_[0] &= ( 1ULL << _Size ) - 1; |
257 | |
258 | _VSTD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0)); |
259 | } |
260 | |
261 | #endif // _LIBCPP_CXX03_LANG |
262 | |
263 | template <size_t _N_words, size_t _Size> |
264 | inline |
265 | _LIBCPP_CONSTEXPR |
266 | __bitset<_N_words, _Size>::__bitset(unsigned long long __v) _NOEXCEPT |
267 | #ifndef _LIBCPP_CXX03_LANG |
268 | #if __SIZEOF_SIZE_T__ == 8 |
269 | : __first_{__v} |
270 | #elif __SIZEOF_SIZE_T__ == 4 |
271 | : __first_{static_cast<__storage_type>(__v), |
272 | _Size >= 2 * __bits_per_word ? static_cast<__storage_type>(__v >> __bits_per_word) |
273 | : static_cast<__storage_type>((__v >> __bits_per_word) & (__storage_type(1) << (_Size - __bits_per_word)) - 1)} |
274 | #else |
275 | #error This constructor has not been ported to this platform |
276 | #endif |
277 | #endif |
278 | { |
279 | #ifdef _LIBCPP_CXX03_LANG |
280 | __init(__v, integral_constant<bool, sizeof(unsigned long long) == sizeof(__storage_type)>()); |
281 | #endif |
282 | } |
283 | |
284 | template <size_t _N_words, size_t _Size> |
285 | inline |
286 | void |
287 | __bitset<_N_words, _Size>::operator&=(const __bitset& __v) _NOEXCEPT |
288 | { |
289 | for (size_type __i = 0; __i < _N_words; ++__i) |
290 | __first_[__i] &= __v.__first_[__i]; |
291 | } |
292 | |
293 | template <size_t _N_words, size_t _Size> |
294 | inline |
295 | void |
296 | __bitset<_N_words, _Size>::operator|=(const __bitset& __v) _NOEXCEPT |
297 | { |
298 | for (size_type __i = 0; __i < _N_words; ++__i) |
299 | __first_[__i] |= __v.__first_[__i]; |
300 | } |
301 | |
302 | template <size_t _N_words, size_t _Size> |
303 | inline |
304 | void |
305 | __bitset<_N_words, _Size>::operator^=(const __bitset& __v) _NOEXCEPT |
306 | { |
307 | for (size_type __i = 0; __i < _N_words; ++__i) |
308 | __first_[__i] ^= __v.__first_[__i]; |
309 | } |
310 | |
311 | template <size_t _N_words, size_t _Size> |
312 | void |
313 | __bitset<_N_words, _Size>::flip() _NOEXCEPT |
314 | { |
315 | // do middle whole words |
316 | size_type __n = _Size; |
317 | __storage_pointer __p = __first_; |
318 | for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) |
319 | *__p = ~*__p; |
320 | // do last partial word |
321 | if (__n > 0) |
322 | { |
323 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
324 | __storage_type __b = *__p & __m; |
325 | *__p &= ~__m; |
326 | *__p |= ~__b & __m; |
327 | } |
328 | } |
329 | |
330 | template <size_t _N_words, size_t _Size> |
331 | unsigned long |
332 | __bitset<_N_words, _Size>::to_ulong(false_type) const |
333 | { |
334 | const_iterator __e = __make_iter(_Size); |
335 | const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true); |
336 | if (__i != __e) |
337 | __throw_overflow_error("bitset to_ulong overflow error" ); |
338 | |
339 | return __first_[0]; |
340 | } |
341 | |
342 | template <size_t _N_words, size_t _Size> |
343 | inline |
344 | unsigned long |
345 | __bitset<_N_words, _Size>::to_ulong(true_type) const |
346 | { |
347 | return __first_[0]; |
348 | } |
349 | |
350 | template <size_t _N_words, size_t _Size> |
351 | unsigned long long |
352 | __bitset<_N_words, _Size>::to_ullong(false_type) const |
353 | { |
354 | const_iterator __e = __make_iter(_Size); |
355 | const_iterator __i = _VSTD::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true); |
356 | if (__i != __e) |
357 | __throw_overflow_error("bitset to_ullong overflow error" ); |
358 | |
359 | return to_ullong(true_type()); |
360 | } |
361 | |
362 | template <size_t _N_words, size_t _Size> |
363 | inline |
364 | unsigned long long |
365 | __bitset<_N_words, _Size>::to_ullong(true_type) const |
366 | { |
367 | return to_ullong(true_type(), integral_constant<bool, sizeof(__storage_type) < sizeof(unsigned long long)>()); |
368 | } |
369 | |
370 | template <size_t _N_words, size_t _Size> |
371 | inline |
372 | unsigned long long |
373 | __bitset<_N_words, _Size>::to_ullong(true_type, false_type) const |
374 | { |
375 | return __first_[0]; |
376 | } |
377 | |
378 | template <size_t _N_words, size_t _Size> |
379 | unsigned long long |
380 | __bitset<_N_words, _Size>::to_ullong(true_type, true_type) const |
381 | { |
382 | unsigned long long __r = __first_[0]; |
383 | for (std::size_t __i = 1; __i < sizeof(unsigned long long) / sizeof(__storage_type); ++__i) |
384 | __r |= static_cast<unsigned long long>(__first_[__i]) << (sizeof(__storage_type) * CHAR_BIT); |
385 | return __r; |
386 | } |
387 | |
388 | template <size_t _N_words, size_t _Size> |
389 | bool |
390 | __bitset<_N_words, _Size>::all() const _NOEXCEPT |
391 | { |
392 | // do middle whole words |
393 | size_type __n = _Size; |
394 | __const_storage_pointer __p = __first_; |
395 | for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) |
396 | if (~*__p) |
397 | return false; |
398 | // do last partial word |
399 | if (__n > 0) |
400 | { |
401 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
402 | if (~*__p & __m) |
403 | return false; |
404 | } |
405 | return true; |
406 | } |
407 | |
408 | template <size_t _N_words, size_t _Size> |
409 | bool |
410 | __bitset<_N_words, _Size>::any() const _NOEXCEPT |
411 | { |
412 | // do middle whole words |
413 | size_type __n = _Size; |
414 | __const_storage_pointer __p = __first_; |
415 | for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) |
416 | if (*__p) |
417 | return true; |
418 | // do last partial word |
419 | if (__n > 0) |
420 | { |
421 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
422 | if (*__p & __m) |
423 | return true; |
424 | } |
425 | return false; |
426 | } |
427 | |
428 | template <size_t _N_words, size_t _Size> |
429 | inline |
430 | size_t |
431 | __bitset<_N_words, _Size>::__hash_code() const _NOEXCEPT |
432 | { |
433 | size_t __h = 0; |
434 | for (size_type __i = 0; __i < _N_words; ++__i) |
435 | __h ^= __first_[__i]; |
436 | return __h; |
437 | } |
438 | |
439 | template <size_t _Size> |
440 | class __bitset<1, _Size> |
441 | { |
442 | public: |
443 | typedef ptrdiff_t difference_type; |
444 | typedef size_t size_type; |
445 | typedef size_type __storage_type; |
446 | protected: |
447 | typedef __bitset __self; |
448 | typedef __storage_type* __storage_pointer; |
449 | typedef const __storage_type* __const_storage_pointer; |
450 | static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); |
451 | |
452 | friend class __bit_reference<__bitset>; |
453 | friend class __bit_const_reference<__bitset>; |
454 | friend class __bit_iterator<__bitset, false>; |
455 | friend class __bit_iterator<__bitset, true>; |
456 | friend struct __bit_array<__bitset>; |
457 | |
458 | __storage_type __first_; |
459 | |
460 | typedef __bit_reference<__bitset> reference; |
461 | typedef __bit_const_reference<__bitset> const_reference; |
462 | typedef __bit_iterator<__bitset, false> iterator; |
463 | typedef __bit_iterator<__bitset, true> const_iterator; |
464 | |
465 | _LIBCPP_INLINE_VISIBILITY |
466 | _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT; |
467 | _LIBCPP_INLINE_VISIBILITY |
468 | explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long __v) _NOEXCEPT; |
469 | |
470 | _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) _NOEXCEPT |
471 | {return reference(&__first_, __storage_type(1) << __pos);} |
472 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t __pos) const _NOEXCEPT |
473 | {return const_reference(&__first_, __storage_type(1) << __pos);} |
474 | _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) _NOEXCEPT |
475 | {return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} |
476 | _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const _NOEXCEPT |
477 | {return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} |
478 | |
479 | _LIBCPP_INLINE_VISIBILITY |
480 | void operator&=(const __bitset& __v) _NOEXCEPT; |
481 | _LIBCPP_INLINE_VISIBILITY |
482 | void operator|=(const __bitset& __v) _NOEXCEPT; |
483 | _LIBCPP_INLINE_VISIBILITY |
484 | void operator^=(const __bitset& __v) _NOEXCEPT; |
485 | |
486 | _LIBCPP_INLINE_VISIBILITY |
487 | void flip() _NOEXCEPT; |
488 | |
489 | _LIBCPP_INLINE_VISIBILITY |
490 | unsigned long to_ulong() const; |
491 | _LIBCPP_INLINE_VISIBILITY |
492 | unsigned long long to_ullong() const; |
493 | |
494 | _LIBCPP_INLINE_VISIBILITY |
495 | bool all() const _NOEXCEPT; |
496 | _LIBCPP_INLINE_VISIBILITY |
497 | bool any() const _NOEXCEPT; |
498 | |
499 | _LIBCPP_INLINE_VISIBILITY |
500 | size_t __hash_code() const _NOEXCEPT; |
501 | }; |
502 | |
503 | template <size_t _Size> |
504 | inline |
505 | _LIBCPP_CONSTEXPR |
506 | __bitset<1, _Size>::__bitset() _NOEXCEPT |
507 | : __first_(0) |
508 | { |
509 | } |
510 | |
511 | template <size_t _Size> |
512 | inline |
513 | _LIBCPP_CONSTEXPR |
514 | __bitset<1, _Size>::__bitset(unsigned long long __v) _NOEXCEPT |
515 | : __first_( |
516 | _Size == __bits_per_word ? static_cast<__storage_type>(__v) |
517 | : static_cast<__storage_type>(__v) & ((__storage_type(1) << _Size) - 1) |
518 | ) |
519 | { |
520 | } |
521 | |
522 | template <size_t _Size> |
523 | inline |
524 | void |
525 | __bitset<1, _Size>::operator&=(const __bitset& __v) _NOEXCEPT |
526 | { |
527 | __first_ &= __v.__first_; |
528 | } |
529 | |
530 | template <size_t _Size> |
531 | inline |
532 | void |
533 | __bitset<1, _Size>::operator|=(const __bitset& __v) _NOEXCEPT |
534 | { |
535 | __first_ |= __v.__first_; |
536 | } |
537 | |
538 | template <size_t _Size> |
539 | inline |
540 | void |
541 | __bitset<1, _Size>::operator^=(const __bitset& __v) _NOEXCEPT |
542 | { |
543 | __first_ ^= __v.__first_; |
544 | } |
545 | |
546 | template <size_t _Size> |
547 | inline |
548 | void |
549 | __bitset<1, _Size>::flip() _NOEXCEPT |
550 | { |
551 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); |
552 | __first_ = ~__first_; |
553 | __first_ &= __m; |
554 | } |
555 | |
556 | template <size_t _Size> |
557 | inline |
558 | unsigned long |
559 | __bitset<1, _Size>::to_ulong() const |
560 | { |
561 | return __first_; |
562 | } |
563 | |
564 | template <size_t _Size> |
565 | inline |
566 | unsigned long long |
567 | __bitset<1, _Size>::to_ullong() const |
568 | { |
569 | return __first_; |
570 | } |
571 | |
572 | template <size_t _Size> |
573 | inline |
574 | bool |
575 | __bitset<1, _Size>::all() const _NOEXCEPT |
576 | { |
577 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); |
578 | return !(~__first_ & __m); |
579 | } |
580 | |
581 | template <size_t _Size> |
582 | inline |
583 | bool |
584 | __bitset<1, _Size>::any() const _NOEXCEPT |
585 | { |
586 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); |
587 | return __first_ & __m; |
588 | } |
589 | |
590 | template <size_t _Size> |
591 | inline |
592 | size_t |
593 | __bitset<1, _Size>::__hash_code() const _NOEXCEPT |
594 | { |
595 | return __first_; |
596 | } |
597 | |
598 | template <> |
599 | class __bitset<0, 0> |
600 | { |
601 | public: |
602 | typedef ptrdiff_t difference_type; |
603 | typedef size_t size_type; |
604 | typedef size_type __storage_type; |
605 | protected: |
606 | typedef __bitset __self; |
607 | typedef __storage_type* __storage_pointer; |
608 | typedef const __storage_type* __const_storage_pointer; |
609 | static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); |
610 | |
611 | friend class __bit_reference<__bitset>; |
612 | friend class __bit_const_reference<__bitset>; |
613 | friend class __bit_iterator<__bitset, false>; |
614 | friend class __bit_iterator<__bitset, true>; |
615 | friend struct __bit_array<__bitset>; |
616 | |
617 | typedef __bit_reference<__bitset> reference; |
618 | typedef __bit_const_reference<__bitset> const_reference; |
619 | typedef __bit_iterator<__bitset, false> iterator; |
620 | typedef __bit_iterator<__bitset, true> const_iterator; |
621 | |
622 | _LIBCPP_INLINE_VISIBILITY |
623 | _LIBCPP_CONSTEXPR __bitset() _NOEXCEPT; |
624 | _LIBCPP_INLINE_VISIBILITY |
625 | explicit _LIBCPP_CONSTEXPR __bitset(unsigned long long) _NOEXCEPT; |
626 | |
627 | _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t) _NOEXCEPT |
628 | {return reference(0, 1);} |
629 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR const_reference __make_ref(size_t) const _NOEXCEPT |
630 | {return const_reference(0, 1);} |
631 | _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t) _NOEXCEPT |
632 | {return iterator(0, 0);} |
633 | _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t) const _NOEXCEPT |
634 | {return const_iterator(0, 0);} |
635 | |
636 | _LIBCPP_INLINE_VISIBILITY void operator&=(const __bitset&) _NOEXCEPT {} |
637 | _LIBCPP_INLINE_VISIBILITY void operator|=(const __bitset&) _NOEXCEPT {} |
638 | _LIBCPP_INLINE_VISIBILITY void operator^=(const __bitset&) _NOEXCEPT {} |
639 | |
640 | _LIBCPP_INLINE_VISIBILITY void flip() _NOEXCEPT {} |
641 | |
642 | _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const {return 0;} |
643 | _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const {return 0;} |
644 | |
645 | _LIBCPP_INLINE_VISIBILITY bool all() const _NOEXCEPT {return true;} |
646 | _LIBCPP_INLINE_VISIBILITY bool any() const _NOEXCEPT {return false;} |
647 | |
648 | _LIBCPP_INLINE_VISIBILITY size_t __hash_code() const _NOEXCEPT {return 0;} |
649 | }; |
650 | |
651 | inline |
652 | _LIBCPP_CONSTEXPR |
653 | __bitset<0, 0>::__bitset() _NOEXCEPT |
654 | { |
655 | } |
656 | |
657 | inline |
658 | _LIBCPP_CONSTEXPR |
659 | __bitset<0, 0>::__bitset(unsigned long long) _NOEXCEPT |
660 | { |
661 | } |
662 | |
663 | template <size_t _Size> class _LIBCPP_TEMPLATE_VIS bitset; |
664 | template <size_t _Size> struct hash<bitset<_Size> >; |
665 | |
666 | template <size_t _Size> |
667 | class _LIBCPP_TEMPLATE_VIS bitset |
668 | : private __bitset<_Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1, _Size> |
669 | { |
670 | public: |
671 | static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1; |
672 | typedef __bitset<__n_words, _Size> base; |
673 | |
674 | public: |
675 | typedef typename base::reference reference; |
676 | typedef typename base::const_reference const_reference; |
677 | |
678 | // 23.3.5.1 constructors: |
679 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR bitset() _NOEXCEPT {} |
680 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
681 | bitset(unsigned long long __v) _NOEXCEPT : base(__v) {} |
682 | template<class _CharT, class = _EnableIf<_IsCharLikeType<_CharT>::value> > |
683 | explicit bitset(const _CharT* __str, |
684 | typename basic_string<_CharT>::size_type __n = basic_string<_CharT>::npos, |
685 | _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')); |
686 | template<class _CharT, class _Traits, class _Allocator> |
687 | explicit bitset(const basic_string<_CharT,_Traits,_Allocator>& __str, |
688 | typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos = 0, |
689 | typename basic_string<_CharT,_Traits,_Allocator>::size_type __n = |
690 | (basic_string<_CharT,_Traits,_Allocator>::npos), |
691 | _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')); |
692 | |
693 | // 23.3.5.2 bitset operations: |
694 | _LIBCPP_INLINE_VISIBILITY |
695 | bitset& operator&=(const bitset& __rhs) _NOEXCEPT; |
696 | _LIBCPP_INLINE_VISIBILITY |
697 | bitset& operator|=(const bitset& __rhs) _NOEXCEPT; |
698 | _LIBCPP_INLINE_VISIBILITY |
699 | bitset& operator^=(const bitset& __rhs) _NOEXCEPT; |
700 | bitset& operator<<=(size_t __pos) _NOEXCEPT; |
701 | bitset& operator>>=(size_t __pos) _NOEXCEPT; |
702 | _LIBCPP_INLINE_VISIBILITY |
703 | bitset& set() _NOEXCEPT; |
704 | bitset& set(size_t __pos, bool __val = true); |
705 | _LIBCPP_INLINE_VISIBILITY |
706 | bitset& reset() _NOEXCEPT; |
707 | bitset& reset(size_t __pos); |
708 | _LIBCPP_INLINE_VISIBILITY |
709 | bitset operator~() const _NOEXCEPT; |
710 | _LIBCPP_INLINE_VISIBILITY |
711 | bitset& flip() _NOEXCEPT; |
712 | bitset& flip(size_t __pos); |
713 | |
714 | // element access: |
715 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR |
716 | const_reference operator[](size_t __p) const {return base::__make_ref(__p);} |
717 | _LIBCPP_INLINE_VISIBILITY reference operator[](size_t __p) {return base::__make_ref(__p);} |
718 | _LIBCPP_INLINE_VISIBILITY |
719 | unsigned long to_ulong() const; |
720 | _LIBCPP_INLINE_VISIBILITY |
721 | unsigned long long to_ullong() const; |
722 | template <class _CharT, class _Traits, class _Allocator> |
723 | basic_string<_CharT, _Traits, _Allocator> to_string(_CharT __zero = _CharT('0'), |
724 | _CharT __one = _CharT('1')) const; |
725 | template <class _CharT, class _Traits> |
726 | _LIBCPP_INLINE_VISIBILITY |
727 | basic_string<_CharT, _Traits, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'), |
728 | _CharT __one = _CharT('1')) const; |
729 | template <class _CharT> |
730 | _LIBCPP_INLINE_VISIBILITY |
731 | basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'), |
732 | _CharT __one = _CharT('1')) const; |
733 | _LIBCPP_INLINE_VISIBILITY |
734 | basic_string<char, char_traits<char>, allocator<char> > to_string(char __zero = '0', |
735 | char __one = '1') const; |
736 | _LIBCPP_INLINE_VISIBILITY |
737 | size_t count() const _NOEXCEPT; |
738 | _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR size_t size() const _NOEXCEPT {return _Size;} |
739 | _LIBCPP_INLINE_VISIBILITY |
740 | bool operator==(const bitset& __rhs) const _NOEXCEPT; |
741 | _LIBCPP_INLINE_VISIBILITY |
742 | bool operator!=(const bitset& __rhs) const _NOEXCEPT; |
743 | bool test(size_t __pos) const; |
744 | _LIBCPP_INLINE_VISIBILITY |
745 | bool all() const _NOEXCEPT; |
746 | _LIBCPP_INLINE_VISIBILITY |
747 | bool any() const _NOEXCEPT; |
748 | _LIBCPP_INLINE_VISIBILITY bool none() const _NOEXCEPT {return !any();} |
749 | _LIBCPP_INLINE_VISIBILITY |
750 | bitset operator<<(size_t __pos) const _NOEXCEPT; |
751 | _LIBCPP_INLINE_VISIBILITY |
752 | bitset operator>>(size_t __pos) const _NOEXCEPT; |
753 | |
754 | private: |
755 | |
756 | _LIBCPP_INLINE_VISIBILITY |
757 | size_t __hash_code() const _NOEXCEPT {return base::__hash_code();} |
758 | |
759 | friend struct hash<bitset>; |
760 | }; |
761 | |
762 | template <size_t _Size> |
763 | template<class _CharT, class> |
764 | bitset<_Size>::bitset(const _CharT* __str, |
765 | typename basic_string<_CharT>::size_type __n, |
766 | _CharT __zero, _CharT __one) |
767 | { |
768 | size_t __rlen = _VSTD::min(__n, char_traits<_CharT>::length(__str)); |
769 | for (size_t __i = 0; __i < __rlen; ++__i) |
770 | if (__str[__i] != __zero && __str[__i] != __one) |
771 | __throw_invalid_argument("bitset string ctor has invalid argument" ); |
772 | |
773 | size_t _Mp = _VSTD::min(__rlen, _Size); |
774 | size_t __i = 0; |
775 | for (; __i < _Mp; ++__i) |
776 | { |
777 | _CharT __c = __str[_Mp - 1 - __i]; |
778 | if (__c == __zero) |
779 | (*this)[__i] = false; |
780 | else |
781 | (*this)[__i] = true; |
782 | } |
783 | _VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false); |
784 | } |
785 | |
786 | template <size_t _Size> |
787 | template<class _CharT, class _Traits, class _Allocator> |
788 | bitset<_Size>::bitset(const basic_string<_CharT,_Traits,_Allocator>& __str, |
789 | typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos, |
790 | typename basic_string<_CharT,_Traits,_Allocator>::size_type __n, |
791 | _CharT __zero, _CharT __one) |
792 | { |
793 | if (__pos > __str.size()) |
794 | __throw_out_of_range("bitset string pos out of range" ); |
795 | |
796 | size_t __rlen = _VSTD::min(__n, __str.size() - __pos); |
797 | for (size_t __i = __pos; __i < __pos + __rlen; ++__i) |
798 | if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one)) |
799 | __throw_invalid_argument("bitset string ctor has invalid argument" ); |
800 | |
801 | size_t _Mp = _VSTD::min(__rlen, _Size); |
802 | size_t __i = 0; |
803 | for (; __i < _Mp; ++__i) |
804 | { |
805 | _CharT __c = __str[__pos + _Mp - 1 - __i]; |
806 | if (_Traits::eq(__c, __zero)) |
807 | (*this)[__i] = false; |
808 | else |
809 | (*this)[__i] = true; |
810 | } |
811 | _VSTD::fill(base::__make_iter(__i), base::__make_iter(_Size), false); |
812 | } |
813 | |
814 | template <size_t _Size> |
815 | inline |
816 | bitset<_Size>& |
817 | bitset<_Size>::operator&=(const bitset& __rhs) _NOEXCEPT |
818 | { |
819 | base::operator&=(__rhs); |
820 | return *this; |
821 | } |
822 | |
823 | template <size_t _Size> |
824 | inline |
825 | bitset<_Size>& |
826 | bitset<_Size>::operator|=(const bitset& __rhs) _NOEXCEPT |
827 | { |
828 | base::operator|=(__rhs); |
829 | return *this; |
830 | } |
831 | |
832 | template <size_t _Size> |
833 | inline |
834 | bitset<_Size>& |
835 | bitset<_Size>::operator^=(const bitset& __rhs) _NOEXCEPT |
836 | { |
837 | base::operator^=(__rhs); |
838 | return *this; |
839 | } |
840 | |
841 | template <size_t _Size> |
842 | bitset<_Size>& |
843 | bitset<_Size>::operator<<=(size_t __pos) _NOEXCEPT |
844 | { |
845 | __pos = _VSTD::min(__pos, _Size); |
846 | _VSTD::copy_backward(base::__make_iter(0), base::__make_iter(_Size - __pos), base::__make_iter(_Size)); |
847 | _VSTD::fill_n(base::__make_iter(0), __pos, false); |
848 | return *this; |
849 | } |
850 | |
851 | template <size_t _Size> |
852 | bitset<_Size>& |
853 | bitset<_Size>::operator>>=(size_t __pos) _NOEXCEPT |
854 | { |
855 | __pos = _VSTD::min(__pos, _Size); |
856 | _VSTD::copy(base::__make_iter(__pos), base::__make_iter(_Size), base::__make_iter(0)); |
857 | _VSTD::fill_n(base::__make_iter(_Size - __pos), __pos, false); |
858 | return *this; |
859 | } |
860 | |
861 | template <size_t _Size> |
862 | inline |
863 | bitset<_Size>& |
864 | bitset<_Size>::set() _NOEXCEPT |
865 | { |
866 | _VSTD::fill_n(base::__make_iter(0), _Size, true); |
867 | return *this; |
868 | } |
869 | |
870 | template <size_t _Size> |
871 | bitset<_Size>& |
872 | bitset<_Size>::set(size_t __pos, bool __val) |
873 | { |
874 | if (__pos >= _Size) |
875 | __throw_out_of_range("bitset set argument out of range" ); |
876 | |
877 | (*this)[__pos] = __val; |
878 | return *this; |
879 | } |
880 | |
881 | template <size_t _Size> |
882 | inline |
883 | bitset<_Size>& |
884 | bitset<_Size>::reset() _NOEXCEPT |
885 | { |
886 | _VSTD::fill_n(base::__make_iter(0), _Size, false); |
887 | return *this; |
888 | } |
889 | |
890 | template <size_t _Size> |
891 | bitset<_Size>& |
892 | bitset<_Size>::reset(size_t __pos) |
893 | { |
894 | if (__pos >= _Size) |
895 | __throw_out_of_range("bitset reset argument out of range" ); |
896 | |
897 | (*this)[__pos] = false; |
898 | return *this; |
899 | } |
900 | |
901 | template <size_t _Size> |
902 | inline |
903 | bitset<_Size> |
904 | bitset<_Size>::operator~() const _NOEXCEPT |
905 | { |
906 | bitset __x(*this); |
907 | __x.flip(); |
908 | return __x; |
909 | } |
910 | |
911 | template <size_t _Size> |
912 | inline |
913 | bitset<_Size>& |
914 | bitset<_Size>::flip() _NOEXCEPT |
915 | { |
916 | base::flip(); |
917 | return *this; |
918 | } |
919 | |
920 | template <size_t _Size> |
921 | bitset<_Size>& |
922 | bitset<_Size>::flip(size_t __pos) |
923 | { |
924 | if (__pos >= _Size) |
925 | __throw_out_of_range("bitset flip argument out of range" ); |
926 | |
927 | reference r = base::__make_ref(__pos); |
928 | r = ~r; |
929 | return *this; |
930 | } |
931 | |
932 | template <size_t _Size> |
933 | inline |
934 | unsigned long |
935 | bitset<_Size>::to_ulong() const |
936 | { |
937 | return base::to_ulong(); |
938 | } |
939 | |
940 | template <size_t _Size> |
941 | inline |
942 | unsigned long long |
943 | bitset<_Size>::to_ullong() const |
944 | { |
945 | return base::to_ullong(); |
946 | } |
947 | |
948 | template <size_t _Size> |
949 | template <class _CharT, class _Traits, class _Allocator> |
950 | basic_string<_CharT, _Traits, _Allocator> |
951 | bitset<_Size>::to_string(_CharT __zero, _CharT __one) const |
952 | { |
953 | basic_string<_CharT, _Traits, _Allocator> __r(_Size, __zero); |
954 | for (size_t __i = 0; __i < _Size; ++__i) |
955 | { |
956 | if ((*this)[__i]) |
957 | __r[_Size - 1 - __i] = __one; |
958 | } |
959 | return __r; |
960 | } |
961 | |
962 | template <size_t _Size> |
963 | template <class _CharT, class _Traits> |
964 | inline |
965 | basic_string<_CharT, _Traits, allocator<_CharT> > |
966 | bitset<_Size>::to_string(_CharT __zero, _CharT __one) const |
967 | { |
968 | return to_string<_CharT, _Traits, allocator<_CharT> >(__zero, __one); |
969 | } |
970 | |
971 | template <size_t _Size> |
972 | template <class _CharT> |
973 | inline |
974 | basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> > |
975 | bitset<_Size>::to_string(_CharT __zero, _CharT __one) const |
976 | { |
977 | return to_string<_CharT, char_traits<_CharT>, allocator<_CharT> >(__zero, __one); |
978 | } |
979 | |
980 | template <size_t _Size> |
981 | inline |
982 | basic_string<char, char_traits<char>, allocator<char> > |
983 | bitset<_Size>::to_string(char __zero, char __one) const |
984 | { |
985 | return to_string<char, char_traits<char>, allocator<char> >(__zero, __one); |
986 | } |
987 | |
988 | template <size_t _Size> |
989 | inline |
990 | size_t |
991 | bitset<_Size>::count() const _NOEXCEPT |
992 | { |
993 | return static_cast<size_t>(__count_bool_true(base::__make_iter(0), _Size)); |
994 | } |
995 | |
996 | template <size_t _Size> |
997 | inline |
998 | bool |
999 | bitset<_Size>::operator==(const bitset& __rhs) const _NOEXCEPT |
1000 | { |
1001 | return _VSTD::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0)); |
1002 | } |
1003 | |
1004 | template <size_t _Size> |
1005 | inline |
1006 | bool |
1007 | bitset<_Size>::operator!=(const bitset& __rhs) const _NOEXCEPT |
1008 | { |
1009 | return !(*this == __rhs); |
1010 | } |
1011 | |
1012 | template <size_t _Size> |
1013 | bool |
1014 | bitset<_Size>::test(size_t __pos) const |
1015 | { |
1016 | if (__pos >= _Size) |
1017 | __throw_out_of_range("bitset test argument out of range" ); |
1018 | |
1019 | return (*this)[__pos]; |
1020 | } |
1021 | |
1022 | template <size_t _Size> |
1023 | inline |
1024 | bool |
1025 | bitset<_Size>::all() const _NOEXCEPT |
1026 | { |
1027 | return base::all(); |
1028 | } |
1029 | |
1030 | template <size_t _Size> |
1031 | inline |
1032 | bool |
1033 | bitset<_Size>::any() const _NOEXCEPT |
1034 | { |
1035 | return base::any(); |
1036 | } |
1037 | |
1038 | template <size_t _Size> |
1039 | inline |
1040 | bitset<_Size> |
1041 | bitset<_Size>::operator<<(size_t __pos) const _NOEXCEPT |
1042 | { |
1043 | bitset __r = *this; |
1044 | __r <<= __pos; |
1045 | return __r; |
1046 | } |
1047 | |
1048 | template <size_t _Size> |
1049 | inline |
1050 | bitset<_Size> |
1051 | bitset<_Size>::operator>>(size_t __pos) const _NOEXCEPT |
1052 | { |
1053 | bitset __r = *this; |
1054 | __r >>= __pos; |
1055 | return __r; |
1056 | } |
1057 | |
1058 | template <size_t _Size> |
1059 | inline _LIBCPP_INLINE_VISIBILITY |
1060 | bitset<_Size> |
1061 | operator&(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT |
1062 | { |
1063 | bitset<_Size> __r = __x; |
1064 | __r &= __y; |
1065 | return __r; |
1066 | } |
1067 | |
1068 | template <size_t _Size> |
1069 | inline _LIBCPP_INLINE_VISIBILITY |
1070 | bitset<_Size> |
1071 | operator|(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT |
1072 | { |
1073 | bitset<_Size> __r = __x; |
1074 | __r |= __y; |
1075 | return __r; |
1076 | } |
1077 | |
1078 | template <size_t _Size> |
1079 | inline _LIBCPP_INLINE_VISIBILITY |
1080 | bitset<_Size> |
1081 | operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT |
1082 | { |
1083 | bitset<_Size> __r = __x; |
1084 | __r ^= __y; |
1085 | return __r; |
1086 | } |
1087 | |
1088 | template <size_t _Size> |
1089 | struct _LIBCPP_TEMPLATE_VIS hash<bitset<_Size> > |
1090 | : public unary_function<bitset<_Size>, size_t> |
1091 | { |
1092 | _LIBCPP_INLINE_VISIBILITY |
1093 | size_t operator()(const bitset<_Size>& __bs) const _NOEXCEPT |
1094 | {return __bs.__hash_code();} |
1095 | }; |
1096 | |
1097 | template <class _CharT, class _Traits, size_t _Size> |
1098 | basic_istream<_CharT, _Traits>& |
1099 | operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Size>& __x); |
1100 | |
1101 | template <class _CharT, class _Traits, size_t _Size> |
1102 | basic_ostream<_CharT, _Traits>& |
1103 | operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Size>& __x); |
1104 | |
1105 | _LIBCPP_END_NAMESPACE_STD |
1106 | |
1107 | _LIBCPP_POP_MACROS |
1108 | |
1109 | #endif // _LIBCPP_BITSET |
1110 | |