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
61 template<
typename _WordT =
unsigned long long,
65 static_assert(std::is_unsigned<_WordT>::value,
"template argument "
66 "_WordT not an unsigned integral type");
68 typedef _WordT block_type;
69 typedef _Alloc allocator_type;
70 typedef size_t size_type;
72 static const size_type _S_bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
73 static const size_type npos =
static_cast<size_type
>(-1);
85 { this->
_M_w.swap(__b._M_w); }
88 __dynamic_bitset_base(size_type __nbits,
unsigned long long __val = 0ULL,
89 const allocator_type& __alloc = allocator_type())
90 :
_M_w(__nbits / _S_bits_per_block
91 + (__nbits % _S_bits_per_block > 0),
94 unsigned long long __mask = ~static_cast<block_type>(0);
96 sizeof(
unsigned long long) /
sizeof(block_type));
97 for (
size_t __i = 0; __i < __n; ++__i)
99 this->
_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
100 __mask <<= _S_bits_per_block;
105 _M_assign(
const __dynamic_bitset_base& __b)
106 { this->
_M_w = __b._M_w; }
109 _M_swap(__dynamic_bitset_base& __b)
110 { this->
_M_w.swap(__b._M_w); }
117 _M_resize(
size_t __nbits,
bool __value)
119 size_t __sz = __nbits / _S_bits_per_block;
120 if (__nbits % _S_bits_per_block > 0)
124 block_type __val = 0;
132 _M_get_allocator()
const
133 {
return this->
_M_w.get_allocator(); }
136 _S_whichword(size_type __pos) noexcept
137 {
return __pos / _S_bits_per_block; }
140 _S_whichbyte(size_type __pos) noexcept
141 {
return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
144 _S_whichbit(size_type __pos) noexcept
145 {
return __pos % _S_bits_per_block; }
148 _S_maskbit(size_type __pos) noexcept
149 {
return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
152 _M_getword(size_type __pos)
153 {
return this->
_M_w[_S_whichword(__pos)]; }
156 _M_getword(size_type __pos)
const
157 {
return this->
_M_w[_S_whichword(__pos)]; }
168 _M_do_and(
const __dynamic_bitset_base& __x)
170 if (__x._M_w.size() == this->
_M_w.
size())
171 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
172 this->
_M_w[__i] &= __x._M_w[__i];
178 _M_do_or(
const __dynamic_bitset_base& __x)
180 if (__x._M_w.size() == this->
_M_w.
size())
181 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
182 this->
_M_w[__i] |= __x._M_w[__i];
188 _M_do_xor(
const __dynamic_bitset_base& __x)
190 if (__x._M_w.size() == this->
_M_w.
size())
191 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
192 this->
_M_w[__i] ^= __x._M_w[__i];
198 _M_do_dif(
const __dynamic_bitset_base& __x)
200 if (__x._M_w.size() == this->
_M_w.
size())
201 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
202 this->
_M_w[__i] &= ~__x._M_w[__i];
208 _M_do_left_shift(
size_t __shift);
211 _M_do_right_shift(
size_t __shift);
216 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
223 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
224 this->
_M_w[__i] = ~static_cast<block_type>(0);
230 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
231 this->
_M_w[__i] = static_cast<block_type>(0);
235 _M_is_equal(
const __dynamic_bitset_base& __x)
const
237 if (__x._M_w.size() == this->
_M_w.
size())
239 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
240 if (this->
_M_w[__i] != __x._M_w[__i])
249 _M_is_less(
const __dynamic_bitset_base& __x)
const
251 if (__x._M_w.size() == this->
_M_w.
size())
253 for (
size_t __i = this->
_M_w.
size(); __i > 0; --__i)
255 if (this->
_M_w[__i-1] < __x._M_w[__i-1])
257 else if (this->
_M_w[__i-1] > __x._M_w[__i-1])
267 _M_are_all_aux()
const
269 for (
size_t __i = 0; __i < this->
_M_w.
size() - 1; ++__i)
270 if (
_M_w[__i] != ~static_cast<block_type>(0))
272 return ((this->
_M_w.
size() - 1) * _S_bits_per_block
273 + __builtin_popcountll(this->_M_hiword()));
279 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
280 if (this->
_M_w[__i] != static_cast<block_type>(0))
286 _M_is_subset_of(
const __dynamic_bitset_base& __b)
288 if (__b._M_w.size() == this->
_M_w.
size())
290 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
291 if (this->
_M_w[__i] != (this->
_M_w[__i] | __b._M_w[__i]))
300 _M_is_proper_subset_of(
const __dynamic_bitset_base& __b)
const
302 if (this->is_subset_of(__b))
317 for (
size_t __i = 0; __i < this->
_M_w.
size(); ++__i)
318 __result += __builtin_popcountll(this->
_M_w[__i]);
323 _M_size() const noexcept
327 _M_do_to_ulong()
const;
330 _M_do_to_ullong()
const;
334 _M_do_find_first(
size_t __not_found)
const;
338 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
342 _M_do_append_block(block_type __block, size_type __pos)
344 size_t __offset = __pos % _S_bits_per_block;
349 this->_M_hiword() |= (__block << __offset);
350 this->
_M_w.
push_back(__block >> (_S_bits_per_block - __offset));
411 template<
typename _WordT =
unsigned long long,
416 static_assert(std::is_unsigned<_WordT>::value,
"template argument "
417 "_WordT not an unsigned integral type");
422 typedef _WordT block_type;
423 typedef _Alloc allocator_type;
424 typedef size_t size_type;
426 static const size_type bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
428 static const size_type npos =
static_cast<size_type
>(-1);
436 size_type __shift = this->_M_Nb % bits_per_block;
438 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
445 size_type __shift = this->_M_Nb % bits_per_block;
447 this->_M_hiword() |= ((~static_cast<block_type>(0)) << __shift);
455 _M_unchecked_set(size_type __pos)
457 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
462 _M_unchecked_set(size_type __pos,
int __val)
465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
467 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
472 _M_unchecked_reset(size_type __pos)
474 this->_M_getword(__pos) &= ~
_Base::_S_maskbit(__pos);
479 _M_unchecked_flip(size_type __pos)
481 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
486 _M_unchecked_test(size_type __pos)
const
487 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
488 != static_cast<_WordT>(0)); }
520 this->_M_wp = &__b._M_getword(__pos);
521 this->_M_bpos = _Base::_S_whichbit(__pos);
532 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
534 *this->_M_wp &= ~
_Base::_S_maskbit(this->_M_bpos);
542 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
543 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
545 *this->_M_wp &= ~
_Base::_S_maskbit(this->_M_bpos);
552 {
return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
555 operator bool()
const
556 {
return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
562 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
569 typedef bool const_reference;
581 const allocator_type& __alloc = allocator_type())
582 :
_Base(__nbits, __val, __alloc),
587 const allocator_type& __alloc = allocator_type())
588 : _Base(__alloc), _M_Nb(0)
603 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
606 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
608 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
610 _CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'),
611 const allocator_type& __alloc = allocator_type())
615 if (__pos > __str.
size())
616 __throw_out_of_range(__N(
"dynamic_bitset::bitset initial position "
620 this->_M_Nb = (__n > __str.
size() ? __str.
size() - __pos : __n);
621 this->
resize(this->_M_Nb);
622 this->_M_copy_from_string(__str, __pos, __n,
623 _CharT(
'0'), _CharT(
'1'));
635 const allocator_type& __alloc = allocator_type())
640 while (__str[__len] !=
'\0')
643 this->_M_copy_from_ptr<char,std::char_traits<char>>
644 (__str, __len, 0, __len,
'0',
'1');
679 this->_M_assign(__b);
680 this->_M_Nb = __b._M_Nb;
699 {
return this->_M_get_allocator(); }
705 resize(size_type __nbits,
bool __value =
false)
709 this->_M_resize(__nbits, __value);
710 this->_M_Nb = __nbits;
711 this->_M_do_sanitize();
730 if (
size_t __offset = this->
size() % bits_per_block == 0)
731 this->_M_do_append_block(block_type(0), this->_M_Nb);
733 this->_M_unchecked_set(this->_M_Nb, __bit);
742 this->_M_do_append_block(__block, this->_M_Nb);
743 this->_M_Nb += bits_per_block;
751 { this->
append(__il.begin(), __il.end()); }
756 template <
typename _BlockInputIterator>
758 append(_BlockInputIterator __first, _BlockInputIterator __last)
760 for (; __first != __last; ++__first)
775 this->_M_do_and(__rhs);
782 this->_M_do_and(std::move(__rhs));
789 this->_M_do_or(__rhs);
796 this->_M_do_xor(__rhs);
803 this->_M_do_dif(__rhs);
818 if (__builtin_expect(__pos < this->_M_Nb, 1))
820 this->_M_do_left_shift(__pos);
821 this->_M_do_sanitize();
831 if (__builtin_expect(__pos < this->_M_Nb, 1))
833 this->_M_do_right_shift(__pos);
834 this->_M_do_sanitize();
850 this->_M_do_sanitize();
861 set(size_type __pos,
bool __val =
true)
864 __throw_out_of_range(__N(
"dynamic_bitset::set"));
865 return this->_M_unchecked_set(__pos, __val);
889 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
890 return this->_M_unchecked_reset(__pos);
900 this->_M_do_sanitize();
913 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
914 return this->_M_unchecked_flip(__pos);
937 {
return _M_unchecked_test(__pos); }
948 {
return this->_M_do_to_ulong(); }
958 {
return this->_M_do_to_ullong(); }
968 template<
typename _CharT = char,
972 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
975 _M_copy_to_string(__result, __zero, __one);
980 template<
typename _CharT,
typename _Traits>
982 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
985 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
988 _Traits, _Alloc1>& __str,
size_t __pos,
size_t __n,
989 _CharT __zero = _CharT(
'0'),
990 _CharT __one = _CharT(
'1'))
991 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
992 __pos, __n, __zero, __one); }
994 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
997 _CharT __zero = _CharT(
'0'),
998 _CharT __one = _CharT(
'1'))
const;
1003 {
return this->_M_do_count(); }
1008 {
return this->_M_Nb; }
1013 {
return this->_M_size(); }
1018 {
return (this->_M_Nb == 0); }
1037 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1038 return _M_unchecked_test(__pos);
1047 {
return this->_M_are_all_aux() == _M_Nb; }
1055 {
return this->_M_is_any(); }
1063 {
return !this->_M_is_any(); }
1083 {
return this->_M_do_find_first(this->_M_Nb); }
1093 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1097 {
return this->_M_is_subset_of(__b); }
1101 {
return this->_M_is_proper_subset_of(__b); }
1104 operator==(
const dynamic_bitset<_WordT, _Alloc>& __lhs,
1105 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1106 {
return __lhs._M_is_equal(__rhs); }
1109 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1110 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1111 {
return __lhs._M_is_less(__rhs); }
1114 template<
typename _WordT,
typename _Alloc>
1115 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1117 dynamic_bitset<_WordT, _Alloc>::
1119 _CharT __zero, _CharT __one)
const
1121 __str.
assign(_M_Nb, __zero);
1122 for (
size_t __i = _M_Nb; __i > 0; --__i)
1123 if (_M_unchecked_test(__i - 1))
1124 _Traits::assign(__str[_M_Nb - __i], __one);
1131 template<
typename _WordT,
typename _Alloc>
1135 {
return !(__lhs == __rhs); }
1137 template<
typename _WordT,
typename _Alloc>
1139 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1141 {
return !(__lhs > __rhs); }
1143 template<
typename _WordT,
typename _Alloc>
1147 {
return __rhs < __lhs; }
1149 template<
typename _WordT,
typename _Alloc>
1153 {
return !(__lhs < __rhs); }
1166 template<
typename _WordT,
typename _Alloc>
1167 inline dynamic_bitset<_WordT, _Alloc>
1176 template<
typename _WordT,
typename _Alloc>
1177 inline dynamic_bitset<_WordT, _Alloc>
1186 template <
typename _WordT,
typename _Alloc>
1187 inline dynamic_bitset<_WordT, _Alloc>
1196 template <
typename _WordT,
typename _Alloc>
1197 inline dynamic_bitset<_WordT, _Alloc>
1208 template <
typename _CharT,
typename _Traits,
1209 typename _WordT,
typename _Alloc>
1211 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1216 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1217 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1218 return __os << __tmp;
1224 _GLIBCXX_END_NAMESPACE_VERSION
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
size_type size() const noexcept
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
Managing sequences of characters and character-like objects.
dynamic_bitset(const dynamic_bitset &__b)
Copy constructor.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
const_reference operator[](size_type __pos) const
Array-indexing support.
char_type widen(char __c) const
Widen char to char_type.
void append(block_type __block)
Append a block.
size_type size() const noexcept
Returns the total number of bits.
bool any() const
Tests whether any of the bits are on.
bool none() const
Tests whether any of the bits are on.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
dynamic_bitset< _WordT, _Alloc > & flip(size_type __pos)
Toggles a given bit to its opposite value.
Primary class template ctype facet.This template class defines classification and conversion function...
size_type find_first() const
Finds the index of the first "on" bit.
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
dynamic_bitset(const std::basic_string< _CharT, _Traits, _Alloc1 > &__str, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __pos=0, typename basic_string< _CharT, _Traits, _Alloc1 >::size_type __n=std::basic_string< _CharT, _Traits, _Alloc1 >::npos, _CharT __zero=_CharT('0'), _CharT __one=_CharT('1'), const allocator_type &__alloc=allocator_type())
Use a subset of a string.
dynamic_bitset & operator=(const dynamic_bitset &__b)
Assignment.
dynamic_bitset(size_type __nbits, unsigned long long __val=0ULL, const allocator_type &__alloc=allocator_type())
Initial bits bitwise-copied from a single word (others set to zero).
void swap(dynamic_bitset &__b)
Swap with another bitset.
void clear()
Clear the bitset.
dynamic_bitset< _WordT, _Alloc > & operator&=(dynamic_bitset< _WordT, _Alloc > &&__rhs)
Operations on dynamic_bitsets.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
dynamic_bitset< _WordT, _Alloc > & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > & operator|=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
constexpr size_type max_size() noexcept
Returns the maximum size of a dynamic_bitset object having the same type as *this. The real answer is max() * bits_per_block but is likely to overflow.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
bool test(size_type __pos) const
Tests the value of a bit.
dynamic_bitset< _WordT, _Alloc > & operator-=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
The dynamic_bitset class represents a sequence of bits.
reference operator[](size_type __pos)
Array-indexing support.
size_type num_blocks() const noexcept
Returns the total number of blocks.
dynamic_bitset< _WordT, _Alloc > & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
void push_back(const value_type &__x)
Add data to the end of the vector.
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
dynamic_bitset< _WordT, _Alloc > & reset()
Sets every bit to false.
Basis for explicit traits specializations.
Template class basic_ostream.
dynamic_bitset & operator=(dynamic_bitset &&__b)
Move assignment.
bool all() const
Tests whether all the bits are on.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
dynamic_bitset< _WordT, _Alloc > & operator^=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > & reset(size_type __pos)
Sets a given bit to false.
dynamic_bitset< _WordT, _Alloc > & set()
Sets every bit to true.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
dynamic_bitset< _WordT, _Alloc > operator<<(size_type __pos) const
Self-explanatory.
dynamic_bitset(dynamic_bitset &&__b)
Move constructor.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
dynamic_bitset< _WordT, _Alloc > & operator&=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > operator~() const
See the no-argument flip().
dynamic_bitset< _WordT, _Alloc > & flip()
Toggles every bit to its opposite value.
dynamic_bitset< _WordT, _Alloc > operator>>(size_type __pos) const
Self-explanatory.
std::basic_string< _CharT, _Traits, _Alloc1 > to_string(_CharT __zero=_CharT('0'), _CharT __one=_CharT('1')) const
Returns a character interpretation of the dynamic_bitset.
bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
static constexpr _Tp max() noexcept
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
size_type count() const noexcept
Returns the number of bits which are set.
The standard allocator, as per [20.4].
allocator_type get_allocator() const
Return the allocator for the bitset.