29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
32 #pragma GCC system_header
43 namespace std _GLIBCXX_VISIBILITY(default)
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
65 class _Bool2UChar<bool>
68 typedef unsigned char type;
78 template<
typename _WordT =
unsigned long long,
83 "_WordT not an unsigned integral type");
85 typedef _WordT block_type;
86 typedef _Alloc allocator_type;
87 typedef size_t size_type;
89 static const size_type _S_bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
90 static const size_type npos =
static_cast<size_type
>(-1);
105 __dynamic_bitset_base(size_type __nbits,
unsigned long long __val = 0ULL,
106 const allocator_type& __alloc = allocator_type())
107 :
_M_w(__nbits / _S_bits_per_block
108 + (__nbits % _S_bits_per_block > 0),
111 unsigned long long __mask = ~static_cast<block_type>(0);
113 sizeof(
unsigned long long) /
sizeof(block_type));
114 for (
size_t __i = 0; __i < __n; ++__i)
116 this->
_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
117 __mask <<= _S_bits_per_block;
122 _M_assign(
const __dynamic_bitset_base& __b)
123 { this->
_M_w = __b._M_w; }
126 _M_swap(__dynamic_bitset_base& __b)
134 _M_resize(
size_t __nbits,
bool __value)
136 size_t __sz = __nbits / _S_bits_per_block;
137 if (__nbits % _S_bits_per_block > 0)
144 _M_get_allocator()
const
145 {
return this->
_M_w.get_allocator(); }
148 _S_whichword(size_type __pos) noexcept
149 {
return __pos / _S_bits_per_block; }
152 _S_whichbyte(size_type __pos) noexcept
153 {
return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
156 _S_whichbit(size_type __pos) noexcept
157 {
return __pos % _S_bits_per_block; }
160 _S_maskbit(size_type __pos) noexcept
161 {
return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
164 _M_getword(size_type __pos)
165 {
return this->
_M_w[_S_whichword(__pos)]; }
168 _M_getword(size_type __pos)
const
169 {
return this->
_M_w[_S_whichword(__pos)]; }
180 _M_do_and(
const __dynamic_bitset_base& __x)
182 if (__x._M_w.size() == this->
_M_w.
size())
183 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
184 this->
_M_w[__i] &= __x._M_w[__i];
190 _M_do_or(
const __dynamic_bitset_base& __x)
192 if (__x._M_w.size() == this->
_M_w.
size())
193 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
194 this->
_M_w[__i] |= __x._M_w[__i];
200 _M_do_xor(
const __dynamic_bitset_base& __x)
202 if (__x._M_w.size() == this->
_M_w.
size())
203 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
204 this->
_M_w[__i] ^= __x._M_w[__i];
210 _M_do_dif(
const __dynamic_bitset_base& __x)
212 if (__x._M_w.size() == this->
_M_w.
size())
213 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
214 this->
_M_w[__i] &= ~__x._M_w[__i];
220 _M_do_left_shift(
size_t __shift);
223 _M_do_right_shift(
size_t __shift);
228 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
235 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
236 this->
_M_w[__i] = ~static_cast<block_type>(0);
242 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
243 this->
_M_w[__i] = static_cast<block_type>(0);
247 _M_is_equal(
const __dynamic_bitset_base& __x)
const
249 if (__x.size() == this->
size())
251 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
252 if (this->
_M_w[__i] != __x._M_w[__i])
261 _M_is_less(
const __dynamic_bitset_base& __x)
const
263 if (__x.size() == this->
size())
265 for (
size_t __i = this->
_M_w.
size(); __i > 0; --__i)
267 if (this->
_M_w[__i-1] < __x._M_w[__i-1])
269 else if (this->
_M_w[__i-1] > __x._M_w[__i-1])
279 _M_are_all_aux()
const
281 for (
size_t __i = 0; __i < this->
_M_w.
size() - 1; ++__i)
282 if (
_M_w[__i] != ~static_cast<block_type>(0))
284 return ((this->
_M_w.
size() - 1) * _S_bits_per_block
285 + __builtin_popcountl(this->_M_hiword()));
291 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
292 if (this->
_M_w[__i] != static_cast<block_type>(0))
298 _M_is_subset_of(
const __dynamic_bitset_base& __b)
300 if (__b.size() == this->
size())
302 for (
size_t __i = 0; __i <
_M_w.
size(); ++__i)
303 if (this->
_M_w[__i] != (this->
_M_w[__i] | __b._M_w[__i]))
312 _M_is_proper_subset_of(
const __dynamic_bitset_base& __b)
const
314 if (this->is_subset_of(__b))
329 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
330 __result += __builtin_popcountl(this->
_M_w[__i]);
335 _M_size() const noexcept
339 _M_do_to_ulong()
const;
342 _M_do_to_ullong()
const;
346 _M_do_find_first(
size_t __not_found)
const;
350 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
354 _M_do_append_block(block_type __block, size_type __pos)
356 size_t __offset = __pos % _S_bits_per_block;
361 this->_M_hiword() |= (__block << __offset);
362 this->
_M_w.
push_back(__block >> (_S_bits_per_block - __offset));
368 template<
typename _WordT,
typename _Alloc>
370 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(
size_t __shift)
372 if (__builtin_expect(__shift != 0, 1))
374 const size_t __wshift = __shift / _S_bits_per_block;
375 const size_t __offset = __shift % _S_bits_per_block;
378 for (
size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
379 this->_M_w[__n] = this->_M_w[__n - __wshift];
382 const size_t __sub_offset = _S_bits_per_block - __offset;
383 for (
size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
384 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
385 | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
386 this->_M_w[__wshift] = this->_M_w[0] << __offset;
394 template<
typename _WordT,
typename _Alloc>
396 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(
size_t __shift)
398 if (__builtin_expect(__shift != 0, 1))
400 const size_t __wshift = __shift / _S_bits_per_block;
401 const size_t __offset = __shift % _S_bits_per_block;
402 const size_t __limit = this->_M_w.size() - __wshift - 1;
405 for (
size_t __n = 0; __n <= __limit; ++__n)
406 this->_M_w[__n] = this->_M_w[__n + __wshift];
409 const size_t __sub_offset = (_S_bits_per_block
411 for (
size_t __n = 0; __n < __limit; ++__n)
412 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
413 | (this->_M_w[__n + __wshift + 1] << __sub_offset));
414 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
422 template<
typename _WordT,
typename _Alloc>
424 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong()
const
426 size_t __n =
sizeof(
unsigned long) /
sizeof(block_type);
427 for (
size_t __i = __n; __i < this->_M_w.size(); ++__i)
429 __throw_overflow_error(__N(
"__dynamic_bitset_base::_M_do_to_ulong"));
430 unsigned long __res = 0UL;
431 for (
size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
432 __res += this->_M_w[__i] << (__i * _S_bits_per_block);
436 template<
typename _WordT,
typename _Alloc>
438 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong()
const
440 size_t __n =
sizeof(
unsigned long long) /
sizeof(block_type);
441 for (
size_t __i = __n; __i < this->_M_w.size(); ++__i)
443 __throw_overflow_error(__N(
"__dynamic_bitset_base::_M_do_to_ullong"));
444 unsigned long long __res = 0ULL;
445 for (
size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
446 __res += this->_M_w[__i] << (__i * _S_bits_per_block);
450 template<
typename _WordT,
typename _Alloc>
452 __dynamic_bitset_base<_WordT, _Alloc>
453 ::_M_do_find_first(
size_t __not_found)
const
455 for (
size_t __i = 0; __i < this->_M_w.size(); ++__i)
457 _WordT __thisword = this->_M_w[__i];
458 if (__thisword != static_cast<_WordT>(0))
459 return (__i * _S_bits_per_block
460 + __builtin_ctzl(__thisword));
466 template<
typename _WordT,
typename _Alloc>
468 __dynamic_bitset_base<_WordT, _Alloc>
469 ::_M_do_find_next(
size_t __prev,
size_t __not_found)
const
475 if (__prev >= this->_M_w.size() * _S_bits_per_block)
479 size_t __i = _S_whichword(__prev);
480 _WordT __thisword = this->_M_w[__i];
483 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
485 if (__thisword != static_cast<_WordT>(0))
486 return (__i * _S_bits_per_block
487 + __builtin_ctzl(__thisword));
490 for (++__i; __i < this->_M_w.size(); ++__i)
492 __thisword = this->_M_w[__i];
493 if (__thisword != static_cast<_WordT>(0))
494 return (__i * _S_bits_per_block
495 + __builtin_ctzl(__thisword));
567 template<
typename _WordT =
unsigned long long,
573 "_WordT not an unsigned integral type");
578 typedef _WordT block_type;
579 typedef _Alloc allocator_type;
580 typedef size_t size_type;
582 static const size_type bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
584 static const size_type npos =
static_cast<size_type
>(-1);
592 size_type __shift = this->_M_Nb % bits_per_block;
594 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
602 _M_unchecked_set(size_type __pos)
604 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
609 _M_unchecked_set(size_type __pos,
int __val)
612 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
614 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
619 _M_unchecked_reset(size_type __pos)
621 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
626 _M_unchecked_flip(size_type __pos)
628 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
633 _M_unchecked_test(size_type __pos)
const
634 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
635 != static_cast<_WordT>(0)); }
667 this->_M_wp = &__b._M_getword(__pos);
668 this->_M_bpos = _Base::_S_whichbit(__pos);
679 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
681 *this->_M_wp &= ~
_Base::_S_maskbit(this->_M_bpos);
689 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
690 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
692 *this->_M_wp &= ~
_Base::_S_maskbit(this->_M_bpos);
699 {
return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
702 operator bool()
const
703 {
return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
709 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
716 typedef bool const_reference;
722 :
_Base(__alloc), _M_Nb(0)
728 const allocator_type& __alloc = allocator_type())
729 :
_Base(__nbits, __val, __alloc),
734 const allocator_type& __alloc = allocator_type())
735 : _Base(__alloc), _M_Nb(0)
747 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
750 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
752 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
754 _CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'),
755 const allocator_type& __alloc = allocator_type())
759 if (__pos > __str.
size())
760 __throw_out_of_range(__N(
"dynamic_bitset::bitset initial position "
764 this->_M_Nb = (__n > __str.
size() ? __str.
size() - __pos : __n);
765 this->
resize(this->_M_Nb);
766 this->_M_copy_from_string(__str, __pos, __n,
767 _CharT(
'0'), _CharT(
'1'));
778 const allocator_type& __alloc = allocator_type())
783 while (__str[__len] !=
'\0')
786 this->_M_copy_from_ptr<char,std::char_traits<char>>
787 (__str, __len, 0, __len,
'0',
'1');
811 std::swap(this->_M_Nb, __b._M_Nb);
822 this->_M_assign(__b);
823 this->_M_Nb = __b._M_Nb;
842 {
return this->_M_get_allocator(); }
848 resize(size_type __nbits,
bool __value =
false)
850 this->_M_resize(__nbits, __value);
851 this->_M_Nb = __nbits;
852 this->_M_do_sanitize();
871 if (
size_t __offset = this->
size() % bits_per_block == 0)
872 this->_M_do_append_block(block_type(0), this->_M_Nb);
874 this->_M_unchecked_set(this->_M_Nb, __bit);
883 this->_M_do_append_block(__block, this->_M_Nb);
884 this->_M_Nb += bits_per_block;
892 { this->
append(__il.begin(), __il.end()); }
897 template <
typename _BlockInputIterator>
899 append(_BlockInputIterator __first, _BlockInputIterator __last)
901 for (; __first != __last; ++__first)
916 this->_M_do_and(__rhs);
923 this->_M_do_and(std::move(__rhs));
930 this->_M_do_or(__rhs);
937 this->_M_do_xor(__rhs);
944 this->_M_do_dif(__rhs);
959 if (__builtin_expect(__pos < this->_M_Nb, 1))
961 this->_M_do_left_shift(__pos);
962 this->_M_do_sanitize();
972 if (__builtin_expect(__pos < this->_M_Nb, 1))
974 this->_M_do_right_shift(__pos);
975 this->_M_do_sanitize();
991 this->_M_do_sanitize();
1002 set(size_type __pos,
bool __val =
true)
1005 __throw_out_of_range(__N(
"dynamic_bitset::set"));
1006 return this->_M_unchecked_set(__pos, __val);
1015 this->_M_do_reset();
1030 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
1031 return this->_M_unchecked_reset(__pos);
1041 this->_M_do_sanitize();
1054 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
1055 return this->_M_unchecked_flip(__pos);
1078 {
return _M_unchecked_test(__pos); }
1089 {
return this->_M_do_to_ulong(); }
1099 {
return this->_M_do_to_ullong(); }
1109 template<
typename _CharT = char,
1113 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
1116 _M_copy_to_string(__result, __zero, __one);
1121 template<
typename _CharT,
typename _Traits>
1123 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
1126 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1129 _Traits, _Alloc1>& __str,
size_t __pos,
size_t __n,
1130 _CharT __zero = _CharT(
'0'),
1131 _CharT __one = _CharT(
'1'))
1132 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
1133 __pos, __n, __zero, __one); }
1135 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1138 _CharT __zero = _CharT(
'0'),
1139 _CharT __one = _CharT(
'1'))
const;
1144 {
return this->_M_do_count(); }
1149 {
return this->_M_Nb; }
1154 {
return this->_M_size(); }
1159 {
return (this->_M_Nb == 0); }
1178 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1179 return _M_unchecked_test(__pos);
1188 {
return this->_M_are_all_aux() == _M_Nb; }
1196 {
return this->_M_is_any(); }
1204 {
return !this->_M_is_any(); }
1224 {
return this->_M_do_find_first(this->_M_Nb); }
1234 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1238 {
return this->_M_is_subset_of(__b); }
1242 {
return this->_M_is_proper_subset_of(__b); }
1246 template<
typename _WordT,
typename _Alloc>
1247 template<
typename _CharT,
typename _Traits>
1249 dynamic_bitset<_WordT, _Alloc>::
1250 _M_copy_from_ptr(
const _CharT* __str,
size_t __len,
1251 size_t __pos,
size_t __n, _CharT __zero, _CharT __one)
1255 for (
size_t __i = __nbits; __i > 0; --__i)
1257 const _CharT __c = __str[__pos + __nbits - __i];
1258 if (_Traits::eq(__c, __zero))
1260 else if (_Traits::eq(__c, __one))
1261 _M_unchecked_set(__i - 1);
1263 __throw_invalid_argument(__N(
"dynamic_bitset::_M_copy_from_ptr"));
1267 template<
typename _WordT,
typename _Alloc>
1268 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1270 dynamic_bitset<_WordT, _Alloc>::
1272 _CharT __zero, _CharT __one)
const
1274 __str.
assign(_M_Nb, __zero);
1275 for (
size_t __i = _M_Nb; __i > 0; --__i)
1276 if (_M_unchecked_test(__i - 1))
1277 _Traits::assign(__str[_M_Nb - __i], __one);
1283 template<
typename _WordT,
typename _Alloc>
1287 {
return __lhs._M_is_equal(__rhs); }
1289 template<
typename _WordT,
typename _Alloc>
1293 {
return !__lhs._M_is_equal(__rhs); }
1295 template<
typename _WordT,
typename _Alloc>
1297 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1299 {
return __lhs._M_is_less(__rhs); }
1301 template<
typename _WordT,
typename _Alloc>
1303 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1305 {
return !(__lhs > __rhs); }
1307 template<
typename _WordT,
typename _Alloc>
1311 {
return __rhs < __lhs; }
1313 template<
typename _WordT,
typename _Alloc>
1317 {
return !(__lhs < __rhs); }
1330 template<
typename _WordT,
typename _Alloc>
1331 inline dynamic_bitset<_WordT, _Alloc>
1340 template<
typename _WordT,
typename _Alloc>
1341 inline dynamic_bitset<_WordT, _Alloc>
1350 template <
typename _WordT,
typename _Alloc>
1351 inline dynamic_bitset<_WordT, _Alloc>
1360 template <
typename _WordT,
typename _Alloc>
1361 inline dynamic_bitset<_WordT, _Alloc>
1380 template<
typename _CharT,
typename _Traits,
1381 typename _WordT,
typename _Alloc>
1386 typedef typename _Traits::char_type char_type;
1388 typedef typename __istream_type::ios_base __ios_base;
1393 const char_type __zero = __is.
widen(
'0');
1394 const char_type __one = __is.
widen(
'1');
1396 typename __ios_base::iostate __state = __ios_base::goodbit;
1397 typename __istream_type::sentry __sentry(__is);
1404 static typename _Traits::int_type __eof = _Traits::eof();
1406 typename _Traits::int_type __c1 = __is.
rdbuf()->sbumpc();
1407 if (_Traits::eq_int_type(__c1, __eof))
1409 __state |= __ios_base::eofbit;
1414 const char_type __c2 = _Traits::to_char_type(__c1);
1415 if (_Traits::eq(__c2, __zero))
1417 else if (_Traits::eq(__c2, __one))
1420 eq_int_type(__is.
rdbuf()->sputbackc(__c2),
1423 __state |= __ios_base::failbit;
1433 __is._M_setstate(__ios_base::badbit);
1434 __throw_exception_again;
1437 { __is._M_setstate(__ios_base::badbit); }
1443 __state |= __ios_base::failbit;
1445 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.
size(),
1452 template <
typename _CharT,
typename _Traits,
1453 typename _WordT,
typename _Alloc>
1455 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1460 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1461 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1462 return __os << __tmp;
1466 _GLIBCXX_END_NAMESPACE_VERSION
1470 #undef _GLIBCXX_BITSET_BITS_PER_WORD