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)
600 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
603 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
605 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
607 _CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'),
608 const allocator_type& __alloc = allocator_type())
612 if (__pos > __str.
size())
613 __throw_out_of_range(__N(
"dynamic_bitset::bitset initial position "
617 this->_M_Nb = (__n > __str.
size() ? __str.
size() - __pos : __n);
618 this->
resize(this->_M_Nb);
619 this->_M_copy_from_string(__str, __pos, __n,
620 _CharT(
'0'), _CharT(
'1'));
632 const allocator_type& __alloc = allocator_type())
637 while (__str[__len] !=
'\0')
640 this->_M_copy_from_ptr<char,std::char_traits<char>>
641 (__str, __len, 0, __len,
'0',
'1');
676 this->_M_assign(__b);
677 this->_M_Nb = __b._M_Nb;
696 {
return this->_M_get_allocator(); }
702 resize(size_type __nbits,
bool __value =
false)
706 this->_M_resize(__nbits, __value);
707 this->_M_Nb = __nbits;
708 this->_M_do_sanitize();
727 if (
size_t __offset = this->
size() % bits_per_block == 0)
728 this->_M_do_append_block(block_type(0), this->_M_Nb);
730 this->_M_unchecked_set(this->_M_Nb, __bit);
739 this->_M_do_append_block(__block, this->_M_Nb);
740 this->_M_Nb += bits_per_block;
748 { this->
append(__il.begin(), __il.end()); }
753 template <
typename _BlockInputIterator>
755 append(_BlockInputIterator __first, _BlockInputIterator __last)
757 for (; __first != __last; ++__first)
772 this->_M_do_and(__rhs);
779 this->_M_do_and(std::move(__rhs));
786 this->_M_do_or(__rhs);
793 this->_M_do_xor(__rhs);
800 this->_M_do_dif(__rhs);
815 if (__builtin_expect(__pos < this->_M_Nb, 1))
817 this->_M_do_left_shift(__pos);
818 this->_M_do_sanitize();
828 if (__builtin_expect(__pos < this->_M_Nb, 1))
830 this->_M_do_right_shift(__pos);
831 this->_M_do_sanitize();
847 this->_M_do_sanitize();
858 set(size_type __pos,
bool __val =
true)
861 __throw_out_of_range(__N(
"dynamic_bitset::set"));
862 return this->_M_unchecked_set(__pos, __val);
886 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
887 return this->_M_unchecked_reset(__pos);
897 this->_M_do_sanitize();
910 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
911 return this->_M_unchecked_flip(__pos);
934 {
return _M_unchecked_test(__pos); }
945 {
return this->_M_do_to_ulong(); }
955 {
return this->_M_do_to_ullong(); }
965 template<
typename _CharT = char,
969 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
972 _M_copy_to_string(__result, __zero, __one);
977 template<
typename _CharT,
typename _Traits>
979 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
982 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
985 _Traits, _Alloc1>& __str,
size_t __pos,
size_t __n,
986 _CharT __zero = _CharT(
'0'),
987 _CharT __one = _CharT(
'1'))
988 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
989 __pos, __n, __zero, __one); }
991 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
994 _CharT __zero = _CharT(
'0'),
995 _CharT __one = _CharT(
'1'))
const;
1000 {
return this->_M_do_count(); }
1005 {
return this->_M_Nb; }
1010 {
return this->_M_size(); }
1015 {
return (this->_M_Nb == 0); }
1034 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1035 return _M_unchecked_test(__pos);
1044 {
return this->_M_are_all_aux() == _M_Nb; }
1052 {
return this->_M_is_any(); }
1060 {
return !this->_M_is_any(); }
1080 {
return this->_M_do_find_first(this->_M_Nb); }
1090 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1094 {
return this->_M_is_subset_of(__b); }
1098 {
return this->_M_is_proper_subset_of(__b); }
1101 operator==(
const dynamic_bitset<_WordT, _Alloc>& __lhs,
1102 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1103 {
return __lhs._M_is_equal(__rhs); }
1106 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1107 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1108 {
return __lhs._M_is_less(__rhs); }
1111 template<
typename _WordT,
typename _Alloc>
1112 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1114 dynamic_bitset<_WordT, _Alloc>::
1116 _CharT __zero, _CharT __one)
const
1118 __str.
assign(_M_Nb, __zero);
1119 for (
size_t __i = _M_Nb; __i > 0; --__i)
1120 if (_M_unchecked_test(__i - 1))
1121 _Traits::assign(__str[_M_Nb - __i], __one);
1128 template<
typename _WordT,
typename _Alloc>
1132 {
return !(__lhs == __rhs); }
1134 template<
typename _WordT,
typename _Alloc>
1136 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1138 {
return !(__lhs > __rhs); }
1140 template<
typename _WordT,
typename _Alloc>
1144 {
return __rhs < __lhs; }
1146 template<
typename _WordT,
typename _Alloc>
1150 {
return !(__lhs < __rhs); }
1163 template<
typename _WordT,
typename _Alloc>
1164 inline dynamic_bitset<_WordT, _Alloc>
1173 template<
typename _WordT,
typename _Alloc>
1174 inline dynamic_bitset<_WordT, _Alloc>
1183 template <
typename _WordT,
typename _Alloc>
1184 inline dynamic_bitset<_WordT, _Alloc>
1193 template <
typename _WordT,
typename _Alloc>
1194 inline dynamic_bitset<_WordT, _Alloc>
1205 template <
typename _CharT,
typename _Traits,
1206 typename _WordT,
typename _Alloc>
1208 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1213 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1214 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1215 return __os << __tmp;
1221 _GLIBCXX_END_NAMESPACE_VERSION
bitset< _Nb > & flip() noexcept
Toggles every bit to its opposite value.
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
bool test(size_type __pos) const
Tests the value of a bit.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
dynamic_bitset< _WordT, _Alloc > & set()
Sets every bit to true.
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.
dynamic_bitset< _WordT, _Alloc > & operator&=(dynamic_bitset< _WordT, _Alloc > &&__rhs)
Operations on dynamic_bitsets.
Primary class template ctype facet.This template class defines classification and conversion function...
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
dynamic_bitset & operator=(const dynamic_bitset &__b)
Assignment.
The standard allocator, as per [20.4].
size_type num_blocks() const noexcept
Returns the total number of blocks.
void swap(dynamic_bitset &__b)
Swap with another bitset.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
size_type size() const noexcept
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).
dynamic_bitset< _WordT, _Alloc > & reset(size_type __pos)
Sets a given bit to false.
allocator_type get_allocator() const
Return the allocator for the bitset.
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
Template class basic_ostream.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
dynamic_bitset< _WordT, _Alloc > & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
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.
bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
char_type widen(char __c) const
Widen char to char_type.
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset(dynamic_bitset &&__b)
Move constructor.
dynamic_bitset(const dynamic_bitset &__b)
Copy constructor.
const_reference operator[](size_type __pos) const
Array-indexing support.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
dynamic_bitset< _WordT, _Alloc > & flip()
Toggles every bit to its opposite value.
reference operator[](size_type __pos)
Array-indexing support.
size_type size() const noexcept
Returns the total number of bits.
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 > & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
static constexpr _Tp max() noexcept
dynamic_bitset & operator=(dynamic_bitset &&__b)
Move assignment.
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
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.
dynamic_bitset< _WordT, _Alloc > & operator|=(const dynamic_bitset< _WordT, _Alloc > &__rhs)
Operations on dynamic_bitsets.
The dynamic_bitset class represents a sequence of bits.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
Basis for explicit traits specializations.
Managing sequences of characters and character-like objects.
size_type count() const noexcept
Returns the number of bits which are set.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
dynamic_bitset< _WordT, _Alloc > operator<<(size_type __pos) const
Self-explanatory.
bitset< _Nb > operator~() const noexcept
See the no-argument flip().
dynamic_bitset< _WordT, _Alloc > & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
dynamic_bitset< _WordT, _Alloc > & reset()
Sets every bit to false.
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~() const
See the no-argument flip().
bool any() const
Tests whether any of the bits are on.
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
bool all() const
Tests whether all the bits are on.
dynamic_bitset< _WordT, _Alloc > operator>>(size_type __pos) const
Self-explanatory.
bool none() const
Tests whether any of the bits are on.
void push_back(const value_type &__x)
Add data to the end of the vector.
dynamic_bitset< _WordT, _Alloc > & flip(size_type __pos)
Toggles a given bit to its opposite value.
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.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
void append(block_type __block)
Append a block.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
void clear()
Clear the bitset.
size_type find_first() const
Finds the index of the first "on" bit.