29#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30#define _GLIBCXX_TR2_DYNAMIC_BITSET 1
32#pragma GCC system_header
42namespace std _GLIBCXX_VISIBILITY(default)
44_GLIBCXX_BEGIN_NAMESPACE_VERSION
60 template<
typename _WordT =
unsigned long long,
65 "_WordT not an unsigned integral type");
67 typedef _WordT block_type;
68 typedef _Alloc allocator_type;
69 typedef size_t size_type;
71 static const size_type _S_bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
72 static const size_type npos =
static_cast<size_type
>(-1);
91 const allocator_type& __alloc = allocator_type())
92 :
_M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0),
93 block_type(0), __alloc)
96 __val &= ~(-1ULL << __nbits);
100 if _GLIBCXX17_CONSTEXPR (
sizeof(__val) ==
sizeof(block_type))
106 for (
size_t __i = 0; __val && __i < __n; ++__i)
108 _M_w[__i] =
static_cast<block_type
>(__val);
109 __val >>= _S_bits_per_block;
115 _M_swap(__dynamic_bitset_base& __b)
noexcept
116 { this->_M_w.
swap(__b._M_w); }
120 { this->_M_w.
clear(); }
123 _M_resize(
size_t __nbits,
bool __value)
125 size_t __sz = __nbits / _S_bits_per_block;
126 if (__nbits % _S_bits_per_block > 0)
128 if (__sz != this->_M_w.
size())
130 block_type __val = 0;
133 this->_M_w.
resize(__sz, __val);
138 _M_get_allocator() const noexcept
142 _S_whichword(size_type __pos)
noexcept
143 {
return __pos / _S_bits_per_block; }
146 _S_whichbyte(size_type __pos)
noexcept
147 {
return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
150 _S_whichbit(size_type __pos)
noexcept
151 {
return __pos % _S_bits_per_block; }
154 _S_maskbit(size_type __pos)
noexcept
155 {
return (
static_cast<block_type
>(1)) << _S_whichbit(__pos); }
158 _M_getword(size_type __pos)
noexcept
159 {
return this->_M_w[_S_whichword(__pos)]; }
162 _M_getword(size_type __pos)
const noexcept
163 {
return this->_M_w[_S_whichword(__pos)]; }
167 {
return this->_M_w[
_M_w.
size() - 1]; }
170 _M_hiword() const noexcept
171 {
return this->_M_w[
_M_w.
size() - 1]; }
174 _M_do_and(
const __dynamic_bitset_base& __x)
noexcept
176 if (__x._M_w.size() == this->_M_w.size())
177 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
178 this->_M_w[__i] &= __x._M_w[__i];
184 _M_do_or(
const __dynamic_bitset_base& __x)
noexcept
186 if (__x._M_w.size() == this->_M_w.size())
187 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
188 this->_M_w[__i] |= __x._M_w[__i];
194 _M_do_xor(
const __dynamic_bitset_base& __x)
noexcept
196 if (__x._M_w.size() == this->_M_w.size())
197 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
198 this->_M_w[__i] ^= __x._M_w[__i];
204 _M_do_dif(
const __dynamic_bitset_base& __x)
noexcept
206 if (__x._M_w.size() == this->_M_w.size())
207 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
208 this->_M_w[__i] &= ~__x._M_w[__i];
214 _M_do_left_shift(
size_t __shift);
217 _M_do_right_shift(
size_t __shift);
220 _M_do_flip() noexcept
222 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
223 this->_M_w[__i] = ~this->_M_w[__i];
229 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
230 this->_M_w[__i] =
static_cast<block_type
>(-1);
234 _M_do_reset() noexcept
240 _M_is_equal(
const __dynamic_bitset_base& __x)
const noexcept
242 if (__x._M_w.size() == this->_M_w.size())
244 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
245 if (this->_M_w[__i] != __x._M_w[__i])
254 _M_is_less(
const __dynamic_bitset_base& __x)
const noexcept
256 if (__x._M_w.size() == this->_M_w.size())
258 for (
size_t __i = this->_M_w.
size(); __i > 0; --__i)
260 if (this->_M_w[__i-1] < __x._M_w[__i-1])
262 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
272 _M_are_all_aux() const noexcept
274 for (
size_t __i = 0; __i < this->_M_w.
size() - 1; ++__i)
275 if (
_M_w[__i] !=
static_cast<block_type
>(-1))
277 return ((this->_M_w.
size() - 1) * _S_bits_per_block
278 + __builtin_popcountll(this->_M_hiword()));
282 _M_is_any() const noexcept
284 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
285 if (this->_M_w[__i] !=
static_cast<block_type
>(0))
291 _M_is_subset_of(
const __dynamic_bitset_base& __b)
noexcept
293 if (__b._M_w.size() == this->_M_w.size())
295 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
296 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
305 _M_is_proper_subset_of(
const __dynamic_bitset_base& __b)
const noexcept
307 if (this->is_subset_of(__b))
319 _M_do_count() const noexcept
322 for (
size_t __i = 0; __i < this->_M_w.
size(); ++__i)
323 __result += __builtin_popcountll(this->_M_w[__i]);
328 _M_size() const noexcept
329 {
return this->_M_w.
size(); }
332 _M_do_to_ulong()
const;
335 _M_do_to_ullong()
const;
339 _M_do_find_first(
size_t __not_found)
const;
343 _M_do_find_next(
size_t __prev,
size_t __not_found)
const;
347 _M_do_append_block(block_type __block, size_type __pos)
349 size_t __offset = __pos % _S_bits_per_block;
354 this->_M_hiword() |= (__block << __offset);
355 this->_M_w.
push_back(__block >> (_S_bits_per_block - __offset));
417 template<
typename _WordT =
unsigned long long,
423 "_WordT not an unsigned integral type");
428 typedef _WordT block_type;
429 typedef _Alloc allocator_type;
430 typedef size_t size_type;
432 static const size_type bits_per_block = __CHAR_BIT__ *
sizeof(block_type);
434 static const size_type npos =
static_cast<size_type
>(-1);
442 size_type __shift = this->_M_Nb % bits_per_block;
444 this->_M_hiword() &= block_type(~(block_type(-1) << __shift));
451 size_type __shift = this->_M_Nb % bits_per_block;
453 this->_M_hiword() |= block_type(block_type(-1) << __shift);
461 _M_unchecked_set(size_type __pos)
noexcept
463 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
468 _M_unchecked_set(size_type __pos,
int __val)
noexcept
471 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
473 this->_M_getword(__pos) &=
~_Base::_S_maskbit(__pos);
478 _M_unchecked_reset(size_type __pos)
noexcept
480 this->_M_getword(__pos) &=
~_Base::_S_maskbit(__pos);
485 _M_unchecked_flip(size_type __pos)
noexcept
487 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
492 _M_unchecked_test(size_type __pos)
const noexcept
493 {
return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
494 !=
static_cast<_WordT
>(0)); }
523 this->_M_wp = &__b._M_getword(__pos);
524 this->_M_bpos = _Base::_S_whichbit(__pos);
529 operator=(
bool __x)
noexcept
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);
551 operator~()
const noexcept
552 {
return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
555 operator bool()
const noexcept
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;
585 const allocator_type& __alloc = allocator_type())
586 :
_Base(__nbits, __val, __alloc),
591 const allocator_type& __alloc = allocator_type())
607 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
610 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
614 _CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'),
615 const allocator_type& __alloc = allocator_type())
618 if (__pos > __str.
size())
619 __throw_out_of_range(__N(
"dynamic_bitset::bitset initial position "
623 this->_M_Nb = (__n > __str.
size() ? __str.
size() - __pos : __n);
624 this->
resize(this->_M_Nb);
625 this->_M_copy_from_string(__str, __pos, __n);
637 const allocator_type& __alloc = allocator_type())
638 :
_Base(__builtin_strlen(__str), 0ULL, __alloc),
639 _M_Nb(__builtin_strlen(__str))
641 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb);
668 static_cast<_Base&
>(*this) =
static_cast<_Base&&
>(__b);
682 {
return this->_M_get_allocator(); }
688 resize(size_type __nbits,
bool __value =
false)
692 this->_M_resize(__nbits, __value);
693 this->_M_Nb = __nbits;
694 this->_M_do_sanitize();
713 if (this->
size() % bits_per_block == 0)
714 this->_M_do_append_block(block_type(__bit), this->_M_Nb);
716 this->_M_unchecked_set(this->_M_Nb, __bit);
728 this->_M_do_append_block(__block, this->_M_Nb);
729 this->_M_Nb += bits_per_block;
737 { this->
append(__il.begin(), __il.end()); }
742 template <
typename _BlockInputIterator>
744 append(_BlockInputIterator __first, _BlockInputIterator __last)
746 for (; __first != __last; ++__first)
761 this->_M_do_and(__rhs);
775 this->_M_do_or(__rhs);
782 this->_M_do_xor(__rhs);
789 this->_M_do_dif(__rhs);
804 if (__builtin_expect(__pos < this->_M_Nb, 1))
806 this->_M_do_left_shift(__pos);
807 this->_M_do_sanitize();
817 if (__builtin_expect(__pos < this->_M_Nb, 1))
819 this->_M_do_right_shift(__pos);
820 this->_M_do_sanitize();
836 this->_M_do_sanitize();
847 set(size_type __pos,
bool __val =
true)
850 __throw_out_of_range(__N(
"dynamic_bitset::set"));
851 return this->_M_unchecked_set(__pos, __val);
875 __throw_out_of_range(__N(
"dynamic_bitset::reset"));
876 return this->_M_unchecked_reset(__pos);
886 this->_M_do_sanitize();
899 __throw_out_of_range(__N(
"dynamic_bitset::flip"));
900 return this->_M_unchecked_flip(__pos);
923 {
return _M_unchecked_test(__pos); }
934 {
return this->_M_do_to_ulong(); }
944 {
return this->_M_do_to_ullong(); }
954 template<
typename _CharT = char,
958 to_string(_CharT __zero = _CharT(
'0'), _CharT __one = _CharT(
'1'))
const
961 _M_copy_to_string(__result, __zero, __one);
966 template<
typename _Traits = std::
char_traits<
char>,
967 typename _CharT =
typename _Traits::
char_type>
969 _M_copy_from_ptr(
const _CharT*,
size_t,
size_t,
size_t,
970 _CharT __zero = _CharT(
'0'),
971 _CharT __one = _CharT(
'1'));
973 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
976 size_t __pos,
size_t __n,
977 _CharT __zero = _CharT(
'0'),
978 _CharT __one = _CharT(
'1'))
980 _M_copy_from_ptr<_Traits>(__str.
data(), __str.
size(), __pos, __n,
984 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
987 _CharT __zero = _CharT(
'0'),
988 _CharT __one = _CharT(
'1'))
const;
993 {
return this->_M_do_count(); }
998 {
return this->_M_Nb; }
1003 {
return this->_M_size(); }
1006 _GLIBCXX_NODISCARD
bool
1008 {
return (this->_M_Nb == 0); }
1027 __throw_out_of_range(__N(
"dynamic_bitset::test"));
1028 return _M_unchecked_test(__pos);
1037 {
return this->_M_are_all_aux() == _M_Nb; }
1045 {
return this->_M_is_any(); }
1053 {
return !this->_M_is_any(); }
1073 {
return this->_M_do_find_first(this->_M_Nb); }
1083 {
return this->_M_do_find_next(__prev, this->_M_Nb); }
1087 {
return this->_M_is_subset_of(__b); }
1091 {
return this->_M_is_proper_subset_of(__b); }
1096 {
return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); }
1101 {
return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; }
1104 template<
typename _WordT,
typename _Alloc>
1105 template<
typename _CharT,
typename _Traits,
typename _Alloc1>
1107 dynamic_bitset<_WordT, _Alloc>::
1109 _CharT __zero, _CharT __one)
const
1111 __str.
assign(_M_Nb, __zero);
1112 for (
size_t __i = _M_Nb; __i > 0; --__i)
1113 if (_M_unchecked_test(__i - 1))
1114 _Traits::assign(__str[_M_Nb - __i], __one);
1121 template<
typename _WordT,
typename _Alloc>
1125 {
return !(__lhs == __rhs); }
1127 template<
typename _WordT,
typename _Alloc>
1131 {
return !(__lhs > __rhs); }
1133 template<
typename _WordT,
typename _Alloc>
1137 {
return __rhs < __lhs; }
1139 template<
typename _WordT,
typename _Alloc>
1143 {
return !(__lhs < __rhs); }
1156 template<
typename _WordT,
typename _Alloc>
1157 inline dynamic_bitset<_WordT, _Alloc>
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>
1198 template <
typename _CharT,
typename _Traits,
1199 typename _WordT,
typename _Alloc>
1202 const dynamic_bitset<_WordT, _Alloc>& __x)
1207 __x._M_copy_to_string(__tmp, __ct.
widen(
'0'), __ct.
widen(
'1'));
1208 return __os << __tmp;
1215_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
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.
dynamic_bitset< _WordT, _Alloc > operator&(const dynamic_bitset< _WordT, _Alloc > &__x, const dynamic_bitset< _WordT, _Alloc > &__y)
Global bitwise operations on bitsets.
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.
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.
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].
Basis for explicit traits specializations.
Managing sequences of characters and character-like objects.
const _CharT * data() const noexcept
Return const pointer to contents.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
locale getloc() const
Locale access.
char_type widen(char __c) const
Widen char to char_type.
Primary class template ctype facet.
constexpr void push_back(const value_type &__x)
Add data to the end of the vector.
constexpr iterator end() noexcept
constexpr iterator begin() noexcept
constexpr void swap(vector &__x) noexcept
Swaps data with another vector.
constexpr void resize(size_type __new_size)
Resizes the vector to the specified number of elements.
constexpr void clear() noexcept
constexpr allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
constexpr size_type size() const noexcept
std::vector< block_type, allocator_type > _M_w
0 is the least significant word.
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.