29#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30#define _GLIBCXX_TR2_DYNAMIC_BITSET 1
33#pragma GCC system_header
44namespace std _GLIBCXX_VISIBILITY(default)
46_GLIBCXX_BEGIN_NAMESPACE_VERSION
62 template<
typename _WordT =
unsigned long long,
63 typename _Alloc = std::allocator<_WordT>>
64 struct __dynamic_bitset_base
67 "_WordT not an unsigned integral type");
69 typedef _WordT block_type;
70 typedef _Alloc allocator_type;
71 typedef size_t size_type;
73 static const size_type _S_bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
74 static const size_type npos =
static_cast<size_type
>(-1);
80 __dynamic_bitset_base(
const allocator_type& __alloc)
93 const allocator_type& __alloc = allocator_type())
94 :
_M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0),
95 block_type(0), __alloc)
98 __val &= ~(-1ULL << __nbits);
102 if _GLIBCXX17_CONSTEXPR (
sizeof(__val) ==
sizeof(block_type))
108 for (
size_t __i = 0; __val && __i < __n; ++__i)
110 _M_w[__i] =
static_cast<block_type
>(__val);
111 __val >>= _S_bits_per_block;
117 _M_swap(__dynamic_bitset_base& __b)
noexcept
118 { this->
_M_w.swap(__b._M_w); }
122 { this->
_M_w.clear(); }
125 _M_resize(
size_t __nbits,
bool __value)
127 size_t __sz = __nbits / _S_bits_per_block;
128 if (__nbits % _S_bits_per_block > 0)
130 if (__sz != this->
_M_w.size())
132 block_type __val = 0;
135 this->
_M_w.resize(__sz, __val);
140 _M_get_allocator() const noexcept
141 {
return this->
_M_w.get_allocator(); }
144 _S_whichword(size_type __pos)
noexcept
145 {
return __pos / _S_bits_per_block; }
148 _S_whichbyte(size_type __pos)
noexcept
149 {
return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
152 _S_whichbit(size_type __pos)
noexcept
153 {
return __pos % _S_bits_per_block; }
156 _S_maskbit(size_type __pos)
noexcept
157 {
return (
static_cast<block_type
>(1)) << _S_whichbit(__pos); }
160 _M_getword(size_type __pos)
noexcept
161 {
return this->
_M_w[_S_whichword(__pos)]; }
164 _M_getword(size_type __pos)
const noexcept
165 {
return this->
_M_w[_S_whichword(__pos)]; }
169 {
return this->
_M_w[
_M_w.size() - 1]; }
172 _M_hiword() const noexcept
173 {
return this->
_M_w[
_M_w.size() - 1]; }
176 _M_do_and(
const __dynamic_bitset_base& __x)
noexcept
178 if (__x._M_w.size() == this->_M_w.size())
179 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
180 this->
_M_w[__i] &= __x._M_w[__i];
186 _M_do_or(
const __dynamic_bitset_base& __x)
noexcept
188 if (__x._M_w.size() == this->_M_w.size())
189 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
190 this->
_M_w[__i] |= __x._M_w[__i];
196 _M_do_xor(
const __dynamic_bitset_base& __x)
noexcept
198 if (__x._M_w.size() == this->_M_w.size())
199 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
200 this->
_M_w[__i] ^= __x._M_w[__i];
206 _M_do_dif(
const __dynamic_bitset_base& __x)
noexcept
208 if (__x._M_w.size() == this->_M_w.size())
209 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
210 this->
_M_w[__i] &= ~__x._M_w[__i];
216 _M_do_left_shift(
size_t __shift);
219 _M_do_right_shift(
size_t __shift);
222 _M_do_flip() noexcept
224 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
231 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
232 this->
_M_w[__i] =
static_cast<block_type
>(-1);
236 _M_do_reset() noexcept
238 std::fill(
_M_w.begin(),
_M_w.end(),
static_cast<block_type
>(0));
242 _M_is_equal(
const __dynamic_bitset_base& __x)
const noexcept
244 if (__x._M_w.size() == this->_M_w.size())
246 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
247 if (this->
_M_w[__i] != __x._M_w[__i])
256 _M_is_less(
const __dynamic_bitset_base& __x)
const noexcept
258 if (__x._M_w.size() == this->_M_w.size())
260 for (
size_t __i = this->
_M_w.size(); __i > 0; --__i)
262 if (this->
_M_w[__i-1] < __x._M_w[__i-1])
264 else if (this->
_M_w[__i-1] > __x._M_w[__i-1])
274 _M_are_all_aux() const noexcept
276 for (
size_t __i = 0; __i < this->
_M_w.size() - 1; ++__i)
277 if (
_M_w[__i] !=
static_cast<block_type
>(-1))
279 return ((this->
_M_w.size() - 1) * _S_bits_per_block
280 + __builtin_popcountll(this->_M_hiword()));
284 _M_is_any() const noexcept
286 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
287 if (this->
_M_w[__i] !=
static_cast<block_type
>(0))
293 _M_is_subset_of(
const __dynamic_bitset_base& __b)
noexcept
295 if (__b._M_w.size() == this->_M_w.size())
297 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
298 if (this->
_M_w[__i] != (this->
_M_w[__i] | __b._M_w[__i]))
307 _M_is_proper_subset_of(
const __dynamic_bitset_base& __b)
const noexcept
309 if (this->_M_is_subset_of(__b))
321 _M_do_count() const noexcept
324 for (
size_t __i = 0; __i < this->
_M_w.size(); ++__i)
325 __result += __builtin_popcountll(this->
_M_w[__i]);
330 _M_size() const noexcept
331 {
return this->
_M_w.size(); }
334 _M_do_to_ulong()
const;
337 _M_do_to_ullong()
const;
341 _M_do_find_first(
size_t __not_found)
const;
345 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
349 _M_do_append_block(block_type __block, size_type __pos)
351 size_t __offset = __pos % _S_bits_per_block;
353 this->
_M_w.push_back(__block);
356 this->_M_hiword() |= (__block << __offset);
357 this->
_M_w.push_back(__block >> (_S_bits_per_block - __offset));
419 template<
typename _WordT =
unsigned long long,
420 typename _Alloc = std::allocator<_WordT>>
422 :
private __dynamic_bitset_base<_WordT, _Alloc>
425 "_WordT not an unsigned integral type");
429 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
430 typedef _WordT block_type;
431 typedef _Alloc allocator_type;
432 typedef size_t size_type;
434 static const size_type bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
436 static const size_type npos =
static_cast<size_type
>(-1);
444 size_type __shift = this->_M_Nb % bits_per_block;
446 this->_M_hiword() &= block_type(~(block_type(-1) << __shift));
453 size_type __shift = this->_M_Nb % bits_per_block;
455 this->_M_hiword() |= block_type(block_type(-1) << __shift);
463 _M_unchecked_set(size_type __pos)
noexcept
465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
470 _M_unchecked_set(size_type __pos,
int __val)
noexcept
473 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
475 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
480 _M_unchecked_reset(size_type __pos)
noexcept
482 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
487 _M_unchecked_flip(size_type __pos)
noexcept
489 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
494 _M_unchecked_test(size_type __pos)
const noexcept
495 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
496 !=
static_cast<_WordT
>(0)); }
517 friend class dynamic_bitset;
523 reference(dynamic_bitset& __b, size_type __pos)
noexcept
525 this->_M_wp = &__b._M_getword(__pos);
526 this->_M_bpos = _Base::_S_whichbit(__pos);
531 operator=(
bool __x)
noexcept
534 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
536 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
542 operator=(
const reference& __j)
noexcept
544 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
545 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
547 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
554 {
return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
557 operator bool()
const noexcept
558 {
return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
564 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
571 typedef bool const_reference;
587 const allocator_type& __alloc = allocator_type())
588 : _Base(__nbits, __val, __alloc),
593 const allocator_type& __alloc = allocator_type())
609 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
614 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
616 _CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'),
617 const allocator_type& __alloc = allocator_type())
620 if (__pos > __str.
size())
621 __throw_out_of_range(__N(
"dynamic_bitset::bitset initial position "
625 this->_M_Nb = (__n > __str.
size() ? __str.
size() - __pos : __n);
626 this->resize(this->_M_Nb);
627 this->_M_copy_from_string(__str, __pos, __n, __zero, __one);
639 const allocator_type& __alloc = allocator_type())
640 : _Base(__builtin_strlen(__str), 0ULL, __alloc),
641 _M_Nb(__builtin_strlen(__str))
643 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
651 : _Base(
std::move(__b)), _M_Nb(__b._M_Nb)
659 std::swap(this->_M_Nb, __b._M_Nb);
670 static_cast<_Base&
>(*this) =
static_cast<_Base&&
>(__b);
684 {
return this->_M_get_allocator(); }
690 resize(size_type __nbits,
bool __value =
false)
694 this->_M_resize(__nbits, __value);
695 this->_M_Nb = __nbits;
696 this->_M_do_sanitize();
715 if (this->
size() % bits_per_block == 0)
716 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
718 this->_M_unchecked_set(this->_M_Nb, __bit);
730 this->_M_do_append_block(__block, this->_M_Nb);
731 this->_M_Nb += bits_per_block;
739 { this->
append(__il.begin(), __il.end()); }
744 template <
typename _BlockInputIterator>
746 append(_BlockInputIterator __first, _BlockInputIterator __last)
748 for (; __first != __last; ++__first)
763 this->_M_do_and(__rhs);
777 this->_M_do_or(__rhs);
784 this->_M_do_xor(__rhs);
791 this->_M_do_dif(__rhs);
806 if (__builtin_expect(__pos < this->_M_Nb, 1))
808 this->_M_do_left_shift(__pos);
809 this->_M_do_sanitize();
819 if (__builtin_expect(__pos < this->_M_Nb, 1))
820 this->_M_do_right_shift(__pos);
835 this->_M_do_sanitize();
846 set(size_type __pos,
bool __val =
true)
849 __throw_out_of_range(__N(
"dynamic_bitset::set"));
850 return this->_M_unchecked_set(__pos, __val);
874 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
875 return this->_M_unchecked_reset(__pos);
885 this->_M_do_sanitize();
898 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
899 return this->_M_unchecked_flip(__pos);
922 {
return _M_unchecked_test(__pos); }
933 {
return this->_M_do_to_ulong(); }
943 {
return this->_M_do_to_ullong(); }
953 template<
typename _CharT = char,
957 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
960 _M_copy_to_string(__result, __zero, __one);
965 template<
typename _Traits = std::
char_traits<
char>,
966 typename _CharT =
typename _Traits::
char_type>
968 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
969 _CharT __zero = _CharT(
'0'),
970 _CharT __one = _CharT(
'1'));
972 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
975 size_t __pos,
size_t __n,
976 _CharT __zero = _CharT(
'0'),
977 _CharT __one = _CharT(
'1'))
979 _M_copy_from_ptr<_Traits>(__str.
data(), __str.
size(), __pos, __n,
983 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
986 _CharT __zero = _CharT(
'0'),
987 _CharT __one = _CharT(
'1'))
const;
992 {
return this->_M_do_count(); }
997 {
return this->_M_Nb; }
1002 {
return this->_M_size(); }
1005 _GLIBCXX_NODISCARD
bool
1007 {
return (this->_M_Nb == 0); }
1026 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1027 return _M_unchecked_test(__pos);
1036 {
return this->_M_are_all_aux() == _M_Nb; }
1044 {
return this->_M_is_any(); }
1052 {
return !this->_M_is_any(); }
1072 {
return this->_M_do_find_first(this->_M_Nb); }
1082 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1086 {
return this->_M_is_subset_of(__b); }
1090 {
return this->_M_is_proper_subset_of(__b); }
1095 {
return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); }
1100 {
return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; }
1103 template<
typename _WordT,
typename _Alloc>
1104 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1108 _CharT __zero, _CharT __one)
const
1110 __str.
assign(_M_Nb, __zero);
1111 for (
size_t __i = _M_Nb; __i > 0; --__i)
1112 if (_M_unchecked_test(__i - 1))
1113 _Traits::assign(__str[_M_Nb - __i], __one);
1120 template<
typename _WordT,
typename _Alloc>
1124 {
return !(__lhs == __rhs); }
1126 template<
typename _WordT,
typename _Alloc>
1130 {
return !(__lhs > __rhs); }
1132 template<
typename _WordT,
typename _Alloc>
1136 {
return __rhs < __lhs; }
1138 template<
typename _WordT,
typename _Alloc>
1142 {
return !(__lhs < __rhs); }
1155 template<
typename _WordT,
typename _Alloc>
1156 inline dynamic_bitset<_WordT, _Alloc>
1165 template<
typename _WordT,
typename _Alloc>
1166 inline dynamic_bitset<_WordT, _Alloc>
1175 template <
typename _WordT,
typename _Alloc>
1176 inline dynamic_bitset<_WordT, _Alloc>
1185 template <
typename _WordT,
typename _Alloc>
1186 inline dynamic_bitset<_WordT, _Alloc>
1197 template <
typename _CharT,
typename _Traits,
1198 typename _WordT,
typename _Alloc>
1201 const dynamic_bitset<_WordT, _Alloc>& __x)
1206 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1207 return __os << __tmp;
1214_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
const _Facet & use_facet(const locale &__loc)
Return a facet.
bool operator>=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const dynamic_bitset< _WordT, _Alloc > &__x)
Stream output operator for dynamic_bitset.
bool operator>(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
bool operator<=(const dynamic_bitset< _WordT, _Alloc > &__lhs, const dynamic_bitset< _WordT, _Alloc > &__rhs)
These comparisons for equality/inequality are, well, bitwise.
dynamic_bitset< _WordT, _Alloc > operator-(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
ISO C++ entities toplevel namespace is std.
Namespace for non-standard "TR2" extensions.
Template class basic_ostream.
Properties of fundamental types.
static constexpr _Tp max() noexcept
is_nothrow_move_assignable
The standard allocator, as per C++03 [20.4.1].
Managing sequences of characters and character-like objects.
constexpr size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
constexpr const _CharT * data() const noexcept
Return const pointer to contents.
constexpr basic_string & assign(const basic_string &__str)
Set value to contents of another string.
static const size_type npos
Value returned by various member functions when they fail.
Basis for explicit traits specializations.
locale getloc() const
Locale access.
char_type widen(char __c) const
Widen char to char_type.
Primary class template ctype facet.
A standard container which offers fixed time access to individual elements in any order.
constexpr size_type size() const noexcept
std::vector< block_type, allocator_type > _M_w
The dynamic_bitset class represents a sequence of bits.
size_type find_next(size_t __prev) const
Finds the index of the next "on" bit after prev.
dynamic_bitset & reset()
Sets every bit to false.
dynamic_bitset & operator>>=(size_type __pos)
Operations on dynamic_bitsets.
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(const dynamic_bitset &)=default
Copy constructor.
dynamic_bitset & operator<<=(size_type __pos)
Operations on dynamic_bitsets.
dynamic_bitset(const allocator_type &__alloc)
All bits set to zero.
void append(block_type __block)
Append a block.
unsigned long to_ulong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset & set()
Sets every bit to true.
dynamic_bitset & flip(size_type __pos)
Toggles a given bit to its opposite value.
dynamic_bitset & operator=(dynamic_bitset &&__b) noexcept(std::is_nothrow_move_assignable< _Base >::value)
Move assignment operator.
void swap(dynamic_bitset &__b) noexcept
Swap with another bitset.
dynamic_bitset & operator-=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
void push_back(bool __bit)
Push a bit onto the high end of the bitset.
dynamic_bitset()=default
All bits set to zero.
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
dynamic_bitset operator<<(size_type __pos) const
Self-explanatory.
dynamic_bitset(const char *__str, const allocator_type &__alloc=allocator_type())
Construct from a string.
bool none() const
Tests whether any of the bits are on.
allocator_type get_allocator() const noexcept
Return the allocator for the bitset.
constexpr size_type max_size() noexcept
Returns the maximum size of a dynamic_bitset object having the same type as *this....
const_reference operator[](size_type __pos) const
Array-indexing support.
reference operator[](size_type __pos)
Array-indexing support.
dynamic_bitset & operator|=(const dynamic_bitset &__rhs)
Operations on dynamic_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.
size_type num_blocks() const noexcept
Returns the total number of blocks.
dynamic_bitset & operator&=(dynamic_bitset &&__rhs)
Operations on dynamic_bitsets.
dynamic_bitset & operator&=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
size_type find_first() const
Finds the index of the first "on" bit.
size_type count() const noexcept
Returns the number of bits which are set.
size_type size() const noexcept
Returns the total number of bits.
dynamic_bitset(dynamic_bitset &&__b) noexcept
Move constructor.
void append(_BlockInputIterator __first, _BlockInputIterator __last)
Append an iterator range of blocks.
dynamic_bitset & reset(size_type __pos)
Sets a given bit to false.
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.
unsigned long long to_ullong() const
Returns a numerical interpretation of the dynamic_bitset.
dynamic_bitset & flip()
Toggles every bit to its opposite value.
bool any() const
Tests whether any of the bits are on.
bool test(size_type __pos) const
Tests the value of a bit.
bool empty() const noexcept
Returns true if the dynamic_bitset is empty.
dynamic_bitset & set(size_type __pos, bool __val=true)
Sets a given bit to a particular value.
dynamic_bitset & operator^=(const dynamic_bitset &__rhs)
Operations on dynamic_bitsets.
dynamic_bitset operator>>(size_type __pos) const
Self-explanatory.
void clear()
Clear the bitset.
dynamic_bitset operator~() const
See the no-argument flip().
dynamic_bitset & operator=(const dynamic_bitset &)=default
Copy assignment operator.
bool all() const
Tests whether all the bits are on.