29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
32 #pragma GCC system_header
43 namespace std _GLIBCXX_VISIBILITY(default)
45 _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);
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)
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]);
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');
668 std::swap(this->_M_Nb, __b._M_Nb);
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 (this->
size() % bits_per_block == 0)
731 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
733 this->_M_unchecked_set(this->_M_Nb, __bit);
743 this->_M_do_append_block(__block, this->_M_Nb);
744 this->_M_Nb += bits_per_block;
752 { this->
append(__il.begin(), __il.end()); }
757 template <
typename _BlockInputIterator>
759 append(_BlockInputIterator __first, _BlockInputIterator __last)
761 for (; __first != __last; ++__first)
776 this->_M_do_and(__rhs);
783 this->_M_do_and(std::move(__rhs));
790 this->_M_do_or(__rhs);
797 this->_M_do_xor(__rhs);
804 this->_M_do_dif(__rhs);
819 if (__builtin_expect(__pos < this->_M_Nb, 1))
821 this->_M_do_left_shift(__pos);
822 this->_M_do_sanitize();
832 if (__builtin_expect(__pos < this->_M_Nb, 1))
834 this->_M_do_right_shift(__pos);
835 this->_M_do_sanitize();
851 this->_M_do_sanitize();
862 set(size_type __pos,
bool __val =
true)
865 __throw_out_of_range(__N(
"dynamic_bitset::set"));
866 return this->_M_unchecked_set(__pos, __val);
890 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
891 return this->_M_unchecked_reset(__pos);
901 this->_M_do_sanitize();
914 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
915 return this->_M_unchecked_flip(__pos);
938 {
return _M_unchecked_test(__pos); }
949 {
return this->_M_do_to_ulong(); }
959 {
return this->_M_do_to_ullong(); }
969 template<
typename _CharT = char,
973 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
976 _M_copy_to_string(__result, __zero, __one);
981 template<
typename _CharT,
typename _Traits>
983 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
986 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
989 _Traits, _Alloc1>& __str,
size_t __pos,
size_t __n,
990 _CharT __zero = _CharT(
'0'),
991 _CharT __one = _CharT(
'1'))
992 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
993 __pos, __n, __zero, __one); }
995 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
998 _CharT __zero = _CharT(
'0'),
999 _CharT __one = _CharT(
'1'))
const;
1004 {
return this->_M_do_count(); }
1009 {
return this->_M_Nb; }
1014 {
return this->_M_size(); }
1017 _GLIBCXX_NODISCARD
bool
1019 {
return (this->_M_Nb == 0); }
1038 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1039 return _M_unchecked_test(__pos);
1048 {
return this->_M_are_all_aux() == _M_Nb; }
1056 {
return this->_M_is_any(); }
1064 {
return !this->_M_is_any(); }
1084 {
return this->_M_do_find_first(this->_M_Nb); }
1094 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1098 {
return this->_M_is_subset_of(__b); }
1102 {
return this->_M_is_proper_subset_of(__b); }
1105 operator==(
const dynamic_bitset<_WordT, _Alloc>& __lhs,
1106 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1107 {
return __lhs._M_is_equal(__rhs); }
1110 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1111 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1112 {
return __lhs._M_is_less(__rhs); }
1115 template<
typename _WordT,
typename _Alloc>
1116 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1118 dynamic_bitset<_WordT, _Alloc>::
1120 _CharT __zero, _CharT __one)
const
1122 __str.
assign(_M_Nb, __zero);
1123 for (
size_t __i = _M_Nb; __i > 0; --__i)
1124 if (_M_unchecked_test(__i - 1))
1125 _Traits::assign(__str[_M_Nb - __i], __one);
1132 template<
typename _WordT,
typename _Alloc>
1136 {
return !(__lhs == __rhs); }
1138 template<
typename _WordT,
typename _Alloc>
1140 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1142 {
return !(__lhs > __rhs); }
1144 template<
typename _WordT,
typename _Alloc>
1148 {
return __rhs < __lhs; }
1150 template<
typename _WordT,
typename _Alloc>
1154 {
return !(__lhs < __rhs); }
1167 template<
typename _WordT,
typename _Alloc>
1168 inline dynamic_bitset<_WordT, _Alloc>
1177 template<
typename _WordT,
typename _Alloc>
1178 inline dynamic_bitset<_WordT, _Alloc>
1187 template <
typename _WordT,
typename _Alloc>
1188 inline dynamic_bitset<_WordT, _Alloc>
1197 template <
typename _WordT,
typename _Alloc>
1198 inline dynamic_bitset<_WordT, _Alloc>
1209 template <
typename _CharT,
typename _Traits,
1210 typename _WordT,
typename _Alloc>
1212 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1217 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1218 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1219 return __os << __tmp;
1226 _GLIBCXX_END_NAMESPACE_VERSION
dynamic_bitset< _WordT, _Alloc > operator~() const
See the no-argument flip().
Primary class template ctype facet.This template class defines classification and conversion function...
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.
size_type count() const noexcept
Returns the number of bits which are set.
dynamic_bitset(dynamic_bitset &&__b)
Move constructor.
dynamic_bitset(const dynamic_bitset &__b)
Copy constructor.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
allocator_type get_allocator() const
Return the allocator for the bitset.
reference operator[](size_type __pos)
Array-indexing support.
size_type size() const noexcept
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
const_reference operator[](size_type __pos) const
Array-indexing support.
dynamic_bitset< _WordT, _Alloc > & operator&=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > & operator|=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
bool none() const
Tests whether any of the bits are on.
dynamic_bitset< _WordT, _Alloc > & flip(size_type __pos)
Toggles a given bit to its opposite value.
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
Template class basic_ostream.
dynamic_bitset< _WordT, _Alloc > operator<<(size_type __pos) const
Self-explanatory.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset< _WordT, _Alloc > & operator-=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset< _WordT, _Alloc > & flip()
Toggles every bit to its opposite value.
dynamic_bitset< _WordT, _Alloc > & reset()
Sets every bit to false.
dynamic_bitset< _WordT, _Alloc > & operator&=(dynamic_bitset< _WordT, _Alloc > &&__rhs)
Operations on dynamic_bitsets.
bool test(size_type __pos) const
Tests the value of a bit.
enable_if< ::__array_traits< _Tp, _Nm >::_Is_swappable::value >::type noexcept(noexcept(__one.swap(__two)))
swap
The standard allocator, as per [20.4].
dynamic_bitset< _WordT, _Alloc > & reset(size_type __pos)
Sets a given bit to false.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
static constexpr _Tp max() noexcept
bool all() const
Tests whether all the bits are on.
void push_back(const value_type &__x)
Add data to the end of the vector.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
dynamic_bitset< _WordT, _Alloc > & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
bitset< _Nb > operator^(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
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.
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.
bitset< _Nb > operator|(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
bool any() const
Tests whether any of the bits are on.
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).
size_type find_first() const
Finds the index of the first "on" bit.
void append(block_type __block)
Append a block.
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
dynamic_bitset< _WordT, _Alloc > operator>>(size_type __pos) const
Self-explanatory.
void clear()
Clear the bitset.
size_type size() const noexcept
Returns the total number of bits.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
char_type widen(char __c) const
Widen char to char_type.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
Managing sequences of characters and character-like objects.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
void swap(dynamic_bitset &__b)
Swap with another bitset.
dynamic_bitset & operator=(dynamic_bitset &&__b)
Move assignment.
The dynamic_bitset class represents a sequence of bits.
dynamic_bitset< _WordT, _Alloc > & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
Basis for explicit traits specializations.
dynamic_bitset & operator=(const dynamic_bitset &__b)
Assignment.
dynamic_bitset< _WordT, _Alloc > & set()
Sets every bit to true.
dynamic_bitset< _WordT, _Alloc > & operator^=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
size_type num_blocks() const noexcept
Returns the total number of blocks.
void swap(vector &__x) noexcept
Swaps data with another vector.
_GLIBCXX_NODISCARD bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
dynamic_bitset< _WordT, _Alloc > & operator>>=(size_type __pos)
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.