Google

Edit File: dynamic_bitset

// TR2 <dynamic_bitset> -*- C++ -*- // Copyright (C) 2009-2013 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 3, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // <http://www.gnu.org/licenses/>. /** @file tr2/dynamic_bitset * This is a TR2 C++ Library header. */ #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET #define _GLIBCXX_TR2_DYNAMIC_BITSET 1 #pragma GCC system_header #include <limits> #include <vector> #include <string> #include <memory> // For std::allocator #include <bits/functexcept.h> // For invalid_argument, out_of_range, // overflow_error #include <iosfwd> #include <bits/cxxabi_forced.h> namespace std _GLIBCXX_VISIBILITY(default) { namespace tr2 { _GLIBCXX_BEGIN_NAMESPACE_VERSION /** * Dynamic Bitset. * * See N2050, * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. */ namespace __detail { template<typename T> class _Bool2UChar { typedef T type; }; template<> class _Bool2UChar<bool> { public: typedef unsigned char type; }; } /** * Base class, general case. * * See documentation for dynamic_bitset. */ template<typename _WordT = unsigned long long, typename _Alloc = std::allocator<_WordT>> struct __dynamic_bitset_base { static_assert(std::is_unsigned<_WordT>::value, "template argument " "_WordT not an unsigned integral type"); typedef _WordT block_type; typedef _Alloc allocator_type; typedef size_t size_type; static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); static const size_type npos = static_cast<size_type>(-1); /// 0 is the least significant word. std::vector<block_type, allocator_type> _M_w; explicit __dynamic_bitset_base(const allocator_type& __alloc = allocator_type()) : _M_w(__alloc) { } explicit __dynamic_bitset_base(__dynamic_bitset_base&& __b) { this->_M_w.swap(__b._M_w); } explicit __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, const allocator_type& __alloc = allocator_type()) : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0), __val, __alloc) { unsigned long long __mask = ~static_cast<block_type>(0); size_t __n = std::min(this->_M_w.size(), sizeof(unsigned long long) / sizeof(block_type)); for (size_t __i = 0; __i < __n; ++__i) { this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block); __mask <<= _S_bits_per_block; } } void _M_assign(const __dynamic_bitset_base& __b) { this->_M_w = __b._M_w; } void _M_swap(__dynamic_bitset_base& __b) { this->_M_w.swap(__b._M_w); } void _M_clear() { this->_M_w.clear(); } void _M_resize(size_t __nbits, bool __value) { size_t __sz = __nbits / _S_bits_per_block; if (__nbits % _S_bits_per_block > 0) ++__sz; if (__sz != this->_M_w.size()) this->_M_w.resize(__sz); } allocator_type _M_get_allocator() const { return this->_M_w.get_allocator(); } static size_type _S_whichword(size_type __pos) noexcept { return __pos / _S_bits_per_block; } static size_type _S_whichbyte(size_type __pos) noexcept { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } static size_type _S_whichbit(size_type __pos) noexcept { return __pos % _S_bits_per_block; } static block_type _S_maskbit(size_type __pos) noexcept { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } block_type& _M_getword(size_type __pos) { return this->_M_w[_S_whichword(__pos)]; } block_type _M_getword(size_type __pos) const { return this->_M_w[_S_whichword(__pos)]; } block_type& _M_hiword() { return this->_M_w[_M_w.size() - 1]; } block_type _M_hiword() const { return this->_M_w[_M_w.size() - 1]; } void _M_do_and(const __dynamic_bitset_base& __x) { if (__x._M_w.size() == this->_M_w.size()) for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] &= __x._M_w[__i]; else return; } void _M_do_or(const __dynamic_bitset_base& __x) { if (__x._M_w.size() == this->_M_w.size()) for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] |= __x._M_w[__i]; else return; } void _M_do_xor(const __dynamic_bitset_base& __x) { if (__x._M_w.size() == this->_M_w.size()) for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] ^= __x._M_w[__i]; else return; } void _M_do_dif(const __dynamic_bitset_base& __x) { if (__x._M_w.size() == this->_M_w.size()) for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] &= ~__x._M_w[__i]; else return; } void _M_do_left_shift(size_t __shift); void _M_do_right_shift(size_t __shift); void _M_do_flip() { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] = ~this->_M_w[__i]; } void _M_do_set() { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] = ~static_cast<block_type>(0); } void _M_do_reset() { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) this->_M_w[__i] = static_cast<block_type>(0); } bool _M_is_equal(const __dynamic_bitset_base& __x) const { if (__x.size() == this->size()) { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) if (this->_M_w[__i] != __x._M_w[__i]) return false; return true; } else return false; } bool _M_is_less(const __dynamic_bitset_base& __x) const { if (__x.size() == this->size()) { for (size_t __i = this->_M_w.size(); __i > 0; --__i) { if (this->_M_w[__i-1] < __x._M_w[__i-1]) return true; else if (this->_M_w[__i-1] > __x._M_w[__i-1]) return false; } return false; } else return false; } size_t _M_are_all_aux() const { for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) if (_M_w[__i] != ~static_cast<block_type>(0)) return 0; return ((this->_M_w.size() - 1) * _S_bits_per_block + __builtin_popcountl(this->_M_hiword())); } bool _M_is_any() const { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) if (this->_M_w[__i] != static_cast<block_type>(0)) return true; return false; } bool _M_is_subset_of(const __dynamic_bitset_base& __b) { if (__b.size() == this->size()) { for (size_t __i = 0; __i < _M_w.size(); ++__i) if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) return false; return true; } else return false; } bool _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const { if (this->is_subset_of(__b)) { if (*this == __b) return false; else return true; } else return false; } size_t _M_do_count() const { size_t __result = 0; for (size_t __i = 0; __i < this->_M_w.size(); ++__i) __result += __builtin_popcountl(this->_M_w[__i]); return __result; } size_type _M_size() const noexcept { return this->_M_w.size(); } unsigned long _M_do_to_ulong() const; unsigned long long _M_do_to_ullong() const; // find first "on" bit size_type _M_do_find_first(size_t __not_found) const; // find the next "on" bit that follows "prev" size_type _M_do_find_next(size_t __prev, size_t __not_found) const; // do append of block void _M_do_append_block(block_type __block, size_type __pos) { size_t __offset = __pos % _S_bits_per_block; if (__offset == 0) this->_M_w.push_back(__block); else { this->_M_hiword() |= (__block << __offset); this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); } } }; // Definitions of non-inline functions from __dynamic_bitset_base. template<typename _WordT, typename _Alloc> void __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) { if (__builtin_expect(__shift != 0, 1)) { const size_t __wshift = __shift / _S_bits_per_block; const size_t __offset = __shift % _S_bits_per_block; if (__offset == 0) for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) this->_M_w[__n] = this->_M_w[__n - __wshift]; else { const size_t __sub_offset = _S_bits_per_block - __offset; for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); this->_M_w[__wshift] = this->_M_w[0] << __offset; } //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, //// static_cast<_WordT>(0)); } } template<typename _WordT, typename _Alloc> void __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) { if (__builtin_expect(__shift != 0, 1)) { const size_t __wshift = __shift / _S_bits_per_block; const size_t __offset = __shift % _S_bits_per_block; const size_t __limit = this->_M_w.size() - __wshift - 1; if (__offset == 0) for (size_t __n = 0; __n <= __limit; ++__n) this->_M_w[__n] = this->_M_w[__n + __wshift]; else { const size_t __sub_offset = (_S_bits_per_block - __offset); for (size_t __n = 0; __n < __limit; ++__n) this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) | (this->_M_w[__n + __wshift + 1] << __sub_offset)); this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; } ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), //// static_cast<_WordT>(0)); } } template<typename _WordT, typename _Alloc> unsigned long __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const { size_t __n = sizeof(unsigned long) / sizeof(block_type); for (size_t __i = __n; __i < this->_M_w.size(); ++__i) if (this->_M_w[__i]) __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); unsigned long __res = 0UL; for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) __res += this->_M_w[__i] << (__i * _S_bits_per_block); return __res; } template<typename _WordT, typename _Alloc> unsigned long long __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const { size_t __n = sizeof(unsigned long long) / sizeof(block_type); for (size_t __i = __n; __i < this->_M_w.size(); ++__i) if (this->_M_w[__i]) __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); unsigned long long __res = 0ULL; for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) __res += this->_M_w[__i] << (__i * _S_bits_per_block); return __res; } template<typename _WordT, typename _Alloc> size_t __dynamic_bitset_base<_WordT, _Alloc> ::_M_do_find_first(size_t __not_found) const { for (size_t __i = 0; __i < this->_M_w.size(); ++__i) { _WordT __thisword = this->_M_w[__i]; if (__thisword != static_cast<_WordT>(0)) return (__i * _S_bits_per_block + __builtin_ctzl(__thisword)); } // not found, so return an indication of failure. return __not_found; } template<typename _WordT, typename _Alloc> size_t __dynamic_bitset_base<_WordT, _Alloc> ::_M_do_find_next(size_t __prev, size_t __not_found) const { // make bound inclusive ++__prev; // check out of bounds if (__prev >= this->_M_w.size() * _S_bits_per_block) return __not_found; // search first word size_t __i = _S_whichword(__prev); _WordT __thisword = this->_M_w[__i]; // mask off bits below bound __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); if (__thisword != static_cast<_WordT>(0)) return (__i * _S_bits_per_block + __builtin_ctzl(__thisword)); // check subsequent words for (++__i; __i < this->_M_w.size(); ++__i) { __thisword = this->_M_w[__i]; if (__thisword != static_cast<_WordT>(0)) return (__i * _S_bits_per_block + __builtin_ctzl(__thisword)); } // not found, so return an indication of failure. return __not_found; } // end _M_do_find_next /** * @brief The %dynamic_bitset class represents a sequence of bits. * * @ingroup containers * * (Note that %dynamic_bitset does @e not meet the formal * requirements of a <a href="tables.html#65">container</a>. * Mainly, it lacks iterators.) * * The template argument, @a Nb, may be any non-negative number, * specifying the number of bits (e.g., "0", "12", "1024*1024"). * * In the general unoptimized case, storage is allocated in * word-sized blocks. Let B be the number of bits in a word, then * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are * unused. (They are the high-order bits in the highest word.) It * is a class invariant that those unused bits are always zero. * * If you think of %dynamic_bitset as "a simple array of bits," be * aware that your mental picture is reversed: a %dynamic_bitset * behaves the same way as bits in integers do, with the bit at * index 0 in the "least significant / right-hand" position, and * the bit at index Nb-1 in the "most significant / left-hand" * position. Thus, unlike other containers, a %dynamic_bitset's * index "counts from right to left," to put it very loosely. * * This behavior is preserved when translating to and from strings. * For example, the first line of the following program probably * prints "b('a') is 0001100001" on a modern ASCII system. * * @code * #include <dynamic_bitset> * #include <iostream> * #include <sstream> * * using namespace std; * * int main() * { * long a = 'a'; * dynamic_bitset b(a); * * cout << "b('a') is " << b << endl; * * ostringstream s; * s << b; * string str = s.str(); * cout << "index 3 in the string is " << str[3] << " but\n" * << "index 3 in the bitset is " << b[3] << endl; * } * @endcode * * Also see: * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html * for a description of extensions. * * Most of the actual code isn't contained in %dynamic_bitset<> * itself, but in the base class __dynamic_bitset_base. The base * class works with whole words, not with individual bits. This * allows us to specialize __dynamic_bitset_base for the important * special case where the %dynamic_bitset is only a single word. * * Extra confusion can result due to the fact that the storage for * __dynamic_bitset_base @e is a vector, and is indexed as such. This is * carefully encapsulated. */ template<typename _WordT = unsigned long long, typename _Alloc = std::allocator<_WordT>> class dynamic_bitset : private __dynamic_bitset_base<_WordT, _Alloc> { static_assert(std::is_unsigned<_WordT>::value, "template argument " "_WordT not an unsigned integral type"); public: typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; typedef _WordT block_type; typedef _Alloc allocator_type; typedef size_t size_type; static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); // Use this: constexpr size_type std::numeric_limits<size_type>::max(). static const size_type npos = static_cast<size_type>(-1); private: // Clear the unused bits in the uppermost word. void _M_do_sanitize() { size_type __shift = this->_M_Nb % bits_per_block; if (__shift > 0) this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift); } /** * These versions of single-bit set, reset, flip, and test * do no range checking. */ dynamic_bitset<_WordT, _Alloc>& _M_unchecked_set(size_type __pos) { this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); return *this; } dynamic_bitset<_WordT, _Alloc>& _M_unchecked_set(size_type __pos, int __val) { if (__val) this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); else this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); return *this; } dynamic_bitset<_WordT, _Alloc>& _M_unchecked_reset(size_type __pos) { this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); return *this; } dynamic_bitset<_WordT, _Alloc>& _M_unchecked_flip(size_type __pos) { this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); return *this; } bool _M_unchecked_test(size_type __pos) const { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) != static_cast<_WordT>(0)); } size_type _M_Nb; public: /** * This encapsulates the concept of a single bit. An instance * of this class is a proxy for an actual bit; this way the * individual bit operations are done as faster word-size * bitwise instructions. * * Most users will never need to use this class directly; * conversions to and from bool are automatic and should be * transparent. Overloaded operators help to preserve the * illusion. * * (On a typical system, this "bit %reference" is 64 times the * size of an actual bit. Ha.) */ class reference { friend class dynamic_bitset; block_type *_M_wp; size_type _M_bpos; // left undefined reference(); public: reference(dynamic_bitset& __b, size_type __pos) { this->_M_wp = &__b._M_getword(__pos); this->_M_bpos = _Base::_S_whichbit(__pos); } ~reference() { } // For b[i] = __x; reference& operator=(bool __x) { if (__x) *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); else *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); return *this; } // For b[i] = b[__j]; reference& operator=(const reference& __j) { if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); else *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); return *this; } // Flips the bit bool operator~() const { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } // For __x = b[i]; operator bool() const { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } // For b[i].flip(); reference& flip() { *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); return *this; } }; friend class reference; typedef bool const_reference; // 23.3.5.1 constructors: /// All bits set to zero. explicit dynamic_bitset(const allocator_type& __alloc = allocator_type()) : _Base(__alloc), _M_Nb(0) { } /// Initial bits bitwise-copied from a single word (others set to zero). explicit dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, const allocator_type& __alloc = allocator_type()) : _Base(__nbits, __val, __alloc), _M_Nb(__nbits) { } dynamic_bitset(initializer_list<block_type> __il, const allocator_type& __alloc = allocator_type()) : _Base(__alloc), _M_Nb(0) { this->append(__il); } /** * @brief Use a subset of a string. * @param __str A string of '0' and '1' characters. * @param __pos Index of the first character in @p __str to use. * @param __n The number of characters to copy. * @throw std::out_of_range If @p __pos is bigger the size of @p __str. * @throw std::invalid_argument If a character appears in the string * which is neither '0' nor '1'. */ template<typename _CharT, typename _Traits, typename _Alloc1> explicit 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()) : _Base(__alloc), _M_Nb(0) // Watch for npos. { if (__pos > __str.size()) __throw_out_of_range(__N("dynamic_bitset::bitset initial position " "not valid")); // Watch for npos. this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); this->resize(this->_M_Nb); this->_M_copy_from_string(__str, __pos, __n, _CharT('0'), _CharT('1')); } /** * @brief Construct from a string. * @param __str A string of '0' and '1' characters. * @throw std::invalid_argument If a character appears in the string * which is neither '0' nor '1'. */ explicit dynamic_bitset(const char* __str, const allocator_type& __alloc = allocator_type()) : _Base(__alloc) { size_t __len = 0; if (__str) while (__str[__len] != '\0') ++__len; this->resize(__len); this->_M_copy_from_ptr<char,std::char_traits<char>> (__str, __len, 0, __len, '0', '1'); } /** * @brief Copy constructor. */ dynamic_bitset(const dynamic_bitset& __b) : _Base(__b), _M_Nb(__b.size()) { } /** * @brief Move constructor. */ dynamic_bitset(dynamic_bitset&& __b) : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) { } /** * @brief Swap with another bitset. */ void swap(dynamic_bitset& __b) { this->_M_swap(__b); std::swap(this->_M_Nb, __b._M_Nb); } /** * @brief Assignment. */ dynamic_bitset& operator=(const dynamic_bitset& __b) { if (&__b != this) { this->_M_assign(__b); this->_M_Nb = __b._M_Nb; } } /** * @brief Move assignment. */ dynamic_bitset& operator=(dynamic_bitset&& __b) { this->swap(__b); return *this; } /** * @brief Return the allocator for the bitset. */ allocator_type get_allocator() const { return this->_M_get_allocator(); } /** * @brief Resize the bitset. */ void resize(size_type __nbits, bool __value = false) { this->_M_resize(__nbits, __value); this->_M_Nb = __nbits; this->_M_do_sanitize(); } /** * @brief Clear the bitset. */ void clear() { this->_M_clear(); this->_M_Nb = 0; } /** * @brief Push a bit onto the high end of the bitset. */ void push_back(bool __bit) { if (size_t __offset = this->size() % bits_per_block == 0) this->_M_do_append_block(block_type(0), this->_M_Nb); ++this->_M_Nb; this->_M_unchecked_set(this->_M_Nb, __bit); } /** * @brief Append a block. */ void append(block_type __block) { this->_M_do_append_block(__block, this->_M_Nb); this->_M_Nb += bits_per_block; } /** * @brief */ void append(initializer_list<block_type> __il) { this->append(__il.begin(), __il.end()); } /** * @brief Append an iterator range of blocks. */ template <typename _BlockInputIterator> void append(_BlockInputIterator __first, _BlockInputIterator __last) { for (; __first != __last; ++__first) this->append(*__first); } // 23.3.5.2 dynamic_bitset operations: //@{ /** * @brief Operations on dynamic_bitsets. * @param __rhs A same-sized dynamic_bitset. * * These should be self-explanatory. */ dynamic_bitset<_WordT, _Alloc>& operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) { this->_M_do_and(__rhs); return *this; } dynamic_bitset<_WordT, _Alloc>& operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) { this->_M_do_and(std::move(__rhs)); return *this; } dynamic_bitset<_WordT, _Alloc>& operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) { this->_M_do_or(__rhs); return *this; } dynamic_bitset<_WordT, _Alloc>& operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) { this->_M_do_xor(__rhs); return *this; } dynamic_bitset<_WordT, _Alloc>& operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) { this->_M_do_dif(__rhs); return *this; } //@} //@{ /** * @brief Operations on dynamic_bitsets. * @param __pos The number of places to shift. * * These should be self-explanatory. */ dynamic_bitset<_WordT, _Alloc>& operator<<=(size_type __pos) { if (__builtin_expect(__pos < this->_M_Nb, 1)) { this->_M_do_left_shift(__pos); this->_M_do_sanitize(); } else this->_M_do_reset(); return *this; } dynamic_bitset<_WordT, _Alloc>& operator>>=(size_type __pos) { if (__builtin_expect(__pos < this->_M_Nb, 1)) { this->_M_do_right_shift(__pos); this->_M_do_sanitize(); } else this->_M_do_reset(); return *this; } //@} // Set, reset, and flip. /** * @brief Sets every bit to true. */ dynamic_bitset<_WordT, _Alloc>& set() { this->_M_do_set(); this->_M_do_sanitize(); return *this; } /** * @brief Sets a given bit to a particular value. * @param __pos The index of the bit. * @param __val Either true or false, defaults to true. * @throw std::out_of_range If @a __pos is bigger the size of the %set. */ dynamic_bitset<_WordT, _Alloc>& set(size_type __pos, bool __val = true) { if (__pos >= _M_Nb) __throw_out_of_range(__N("dynamic_bitset::set")); return this->_M_unchecked_set(__pos, __val); } /** * @brief Sets every bit to false. */ dynamic_bitset<_WordT, _Alloc>& reset() { this->_M_do_reset(); return *this; } /** * @brief Sets a given bit to false. * @param __pos The index of the bit. * @throw std::out_of_range If @a __pos is bigger the size of the %set. * * Same as writing @c set(__pos, false). */ dynamic_bitset<_WordT, _Alloc>& reset(size_type __pos) { if (__pos >= _M_Nb) __throw_out_of_range(__N("dynamic_bitset::reset")); return this->_M_unchecked_reset(__pos); } /** * @brief Toggles every bit to its opposite value. */ dynamic_bitset<_WordT, _Alloc>& flip() { this->_M_do_flip(); this->_M_do_sanitize(); return *this; } /** * @brief Toggles a given bit to its opposite value. * @param __pos The index of the bit. * @throw std::out_of_range If @a __pos is bigger the size of the %set. */ dynamic_bitset<_WordT, _Alloc>& flip(size_type __pos) { if (__pos >= _M_Nb) __throw_out_of_range(__N("dynamic_bitset::flip")); return this->_M_unchecked_flip(__pos); } /// See the no-argument flip(). dynamic_bitset<_WordT, _Alloc> operator~() const { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } //@{ /** * @brief Array-indexing support. * @param __pos Index into the %dynamic_bitset. * @return A bool for a 'const %dynamic_bitset'. For non-const * bitsets, an instance of the reference proxy class. * @note These operators do no range checking and throw no * exceptions, as required by DR 11 to the standard. */ reference operator[](size_type __pos) { return reference(*this,__pos); } const_reference operator[](size_type __pos) const { return _M_unchecked_test(__pos); } //@} /** * @brief Returns a numerical interpretation of the %dynamic_bitset. * @return The integral equivalent of the bits. * @throw std::overflow_error If there are too many bits to be * represented in an @c unsigned @c long. */ unsigned long to_ulong() const { return this->_M_do_to_ulong(); } /** * @brief Returns a numerical interpretation of the %dynamic_bitset. * @return The integral equivalent of the bits. * @throw std::overflow_error If there are too many bits to be * represented in an @c unsigned @c long. */ unsigned long long to_ullong() const { return this->_M_do_to_ullong(); } /** * @brief Returns a character interpretation of the %dynamic_bitset. * @return The string equivalent of the bits. * * Note the ordering of the bits: decreasing character positions * correspond to increasing bit positions (see the main class notes for * an example). */ template<typename _CharT = char, typename _Traits = std::char_traits<_CharT>, typename _Alloc1 = std::allocator<_CharT>> std::basic_string<_CharT, _Traits, _Alloc1> to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const { std::basic_string<_CharT, _Traits, _Alloc1> __result; _M_copy_to_string(__result, __zero, __one); return __result; } // Helper functions for string operations. template<typename _CharT, typename _Traits> void _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, _CharT, _CharT); template<typename _CharT, typename _Traits, typename _Alloc1> void _M_copy_from_string(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, size_t __pos, size_t __n, _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), __pos, __n, __zero, __one); } template<typename _CharT, typename _Traits, typename _Alloc1> void _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const; /// Returns the number of bits which are set. size_type count() const noexcept { return this->_M_do_count(); } /// Returns the total number of bits. size_type size() const noexcept { return this->_M_Nb; } /// Returns the total number of blocks. size_type num_blocks() const noexcept { return this->_M_size(); } /// Returns true if the dynamic_bitset is empty. bool empty() const noexcept { return (this->_M_Nb == 0); } /// 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 size_type max_size() noexcept { return std::numeric_limits<block_type>::max(); } /** * @brief Tests the value of a bit. * @param __pos The index of a bit. * @return The value at @a __pos. * @throw std::out_of_range If @a __pos is bigger the size of the %set. */ bool test(size_type __pos) const { if (__pos >= _M_Nb) __throw_out_of_range(__N("dynamic_bitset::test")); return _M_unchecked_test(__pos); } /** * @brief Tests whether all the bits are on. * @return True if all the bits are set. */ bool all() const { return this->_M_are_all_aux() == _M_Nb; } /** * @brief Tests whether any of the bits are on. * @return True if at least one bit is set. */ bool any() const { return this->_M_is_any(); } /** * @brief Tests whether any of the bits are on. * @return True if none of the bits are set. */ bool none() const { return !this->_M_is_any(); } //@{ /// Self-explanatory. dynamic_bitset<_WordT, _Alloc> operator<<(size_type __pos) const { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; } dynamic_bitset<_WordT, _Alloc> operator>>(size_type __pos) const { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; } //@} /** * @brief Finds the index of the first "on" bit. * @return The index of the first bit set, or size() if not found. * @sa find_next */ size_type find_first() const { return this->_M_do_find_first(this->_M_Nb); } /** * @brief Finds the index of the next "on" bit after prev. * @return The index of the next bit set, or size() if not found. * @param __prev Where to start searching. * @sa find_first */ size_type find_next(size_t __prev) const { return this->_M_do_find_next(__prev, this->_M_Nb); } bool is_subset_of(const dynamic_bitset& __b) const { return this->_M_is_subset_of(__b); } bool is_proper_subset_of(const dynamic_bitset& __b) const { return this->_M_is_proper_subset_of(__b); } }; // Definitions of non-inline member functions. template<typename _WordT, typename _Alloc> template<typename _CharT, typename _Traits> void dynamic_bitset<_WordT, _Alloc>:: _M_copy_from_ptr(const _CharT* __str, size_t __len, size_t __pos, size_t __n, _CharT __zero, _CharT __one) { reset(); const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos)); for (size_t __i = __nbits; __i > 0; --__i) { const _CharT __c = __str[__pos + __nbits - __i]; if (_Traits::eq(__c, __zero)) ; else if (_Traits::eq(__c, __one)) _M_unchecked_set(__i - 1); else __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr")); } } template<typename _WordT, typename _Alloc> template<typename _CharT, typename _Traits, typename _Alloc1> void dynamic_bitset<_WordT, _Alloc>:: _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, _CharT __zero, _CharT __one) const { __str.assign(_M_Nb, __zero); for (size_t __i = _M_Nb; __i > 0; --__i) if (_M_unchecked_test(__i - 1)) _Traits::assign(__str[_M_Nb - __i], __one); } //@{ /// These comparisons for equality/inequality are, well, @e bitwise. template<typename _WordT, typename _Alloc> bool operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return __lhs._M_is_equal(__rhs); } template<typename _WordT, typename _Alloc> bool operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return !__lhs._M_is_equal(__rhs); } template<typename _WordT, typename _Alloc> bool operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return __lhs._M_is_less(__rhs); } template<typename _WordT, typename _Alloc> bool operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return !(__lhs > __rhs); } template<typename _WordT, typename _Alloc> bool operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return __rhs < __lhs; } template<typename _WordT, typename _Alloc> bool operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, const dynamic_bitset<_WordT, _Alloc>& __rhs) { return !(__lhs < __rhs); } //@} // 23.3.5.3 bitset operations: //@{ /** * @brief Global bitwise operations on bitsets. * @param __x A bitset. * @param __y A bitset of the same size as @a __x. * @return A new bitset. * * These should be self-explanatory. */ template<typename _WordT, typename _Alloc> inline dynamic_bitset<_WordT, _Alloc> operator&(const dynamic_bitset<_WordT, _Alloc>& __x, const dynamic_bitset<_WordT, _Alloc>& __y) { dynamic_bitset<_WordT, _Alloc> __result(__x); __result &= __y; return __result; } template<typename _WordT, typename _Alloc> inline dynamic_bitset<_WordT, _Alloc> operator|(const dynamic_bitset<_WordT, _Alloc>& __x, const dynamic_bitset<_WordT, _Alloc>& __y) { dynamic_bitset<_WordT, _Alloc> __result(__x); __result |= __y; return __result; } template <typename _WordT, typename _Alloc> inline dynamic_bitset<_WordT, _Alloc> operator^(const dynamic_bitset<_WordT, _Alloc>& __x, const dynamic_bitset<_WordT, _Alloc>& __y) { dynamic_bitset<_WordT, _Alloc> __result(__x); __result ^= __y; return __result; } template <typename _WordT, typename _Alloc> inline dynamic_bitset<_WordT, _Alloc> operator-(const dynamic_bitset<_WordT, _Alloc>& __x, const dynamic_bitset<_WordT, _Alloc>& __y) { dynamic_bitset<_WordT, _Alloc> __result(__x); __result -= __y; return __result; } //@} //@{ /** * @brief Global I/O operators for bitsets. * * Direct I/O between streams and bitsets is supported. Output is * straightforward. Input will skip whitespace and only accept '0' * and '1' characters. The %dynamic_bitset will grow as necessary * to hold the string of bits. */ template<typename _CharT, typename _Traits, typename _WordT, typename _Alloc> std::basic_istream<_CharT, _Traits>& operator>>(std::basic_istream<_CharT, _Traits>& __is, dynamic_bitset<_WordT, _Alloc>& __x) { typedef typename _Traits::char_type char_type; typedef std::basic_istream<_CharT, _Traits> __istream_type; typedef typename __istream_type::ios_base __ios_base; std::basic_string<_CharT, _Traits> __tmp; __tmp.reserve(__x.size()); const char_type __zero = __is.widen('0'); const char_type __one = __is.widen('1'); typename __ios_base::iostate __state = __ios_base::goodbit; typename __istream_type::sentry __sentry(__is); if (__sentry) { __try { while (1) { static typename _Traits::int_type __eof = _Traits::eof(); typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); if (_Traits::eq_int_type(__c1, __eof)) { __state |= __ios_base::eofbit; break; } else { const char_type __c2 = _Traits::to_char_type(__c1); if (_Traits::eq(__c2, __zero)) __tmp.push_back(__zero); else if (_Traits::eq(__c2, __one)) __tmp.push_back(__one); else if (_Traits:: eq_int_type(__is.rdbuf()->sputbackc(__c2), __eof)) { __state |= __ios_base::failbit; break; } else break; } } } __catch(__cxxabiv1::__forced_unwind&) { __is._M_setstate(__ios_base::badbit); __throw_exception_again; } __catch(...) { __is._M_setstate(__ios_base::badbit); } } __x.resize(__tmp.size()); if (__tmp.empty() && __x.size()) __state |= __ios_base::failbit; else __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(), __zero, __one); if (__state) __is.setstate(__state); return __is; } template <typename _CharT, typename _Traits, typename _WordT, typename _Alloc> std::basic_ostream<_CharT, _Traits>& operator<<(std::basic_ostream<_CharT, _Traits>& __os, const dynamic_bitset<_WordT, _Alloc>& __x) { std::basic_string<_CharT, _Traits> __tmp; const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); return __os << __tmp; } //@} _GLIBCXX_END_NAMESPACE_VERSION } // tr2 } // std #undef _GLIBCXX_BITSET_BITS_PER_WORD #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */