X-Git-Url: http://wagnertech.de/git?a=blobdiff_plain;f=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Ftr2%2Fdynamic_bitset;fp=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Ftr2%2Fdynamic_bitset;h=4c06b84c2a5014cfe9ee0c38a415c67ce42660c2;hb=94df942c2c7bd3457276fe5b7367623cbb8c1302;hp=0000000000000000000000000000000000000000;hpb=4dd7d9155a920895ff7b1cb6b9c9c676aa62000a;p=cross.git diff --git a/i686-linux-gnu-4.7/usr/include/c++/4.7/tr2/dynamic_bitset b/i686-linux-gnu-4.7/usr/include/c++/4.7/tr2/dynamic_bitset new file mode 100644 index 0000000..4c06b84 --- /dev/null +++ b/i686-linux-gnu-4.7/usr/include/c++/4.7/tr2/dynamic_bitset @@ -0,0 +1,1472 @@ +// TR2 -*- C++ -*- + +// Copyright (C) 2009, 2010, 2011 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 +// . + +/** @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 +#include +#include // For size_t +#include +#include // For std::allocator +#include // For invalid_argument, out_of_range, + // overflow_error +#include +#include + +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 +class _Bool2UChar +{ + typedef T type; +}; + +template<> +class _Bool2UChar +{ +public: + typedef unsigned char type; +}; + +} + + /** + * Base class, general case. + * + * See documentation for dynamic_bitset. + */ + template> + 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(-1); + + /// 0 is the least significant word. + std::vector _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(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) + { return __pos / _S_bits_per_block; } + + static size_type + _S_whichbyte(size_type __pos) + { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } + + static size_type + _S_whichbit(size_type __pos) + { return __pos % _S_bits_per_block; } + + static block_type + _S_maskbit(size_type __pos) + { return (static_cast(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(0); + } + + void + _M_do_reset() + { + for (size_t __i = 0; __i < this->_M_w.size(); ++__i) + this->_M_w[__i] = static_cast(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(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(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 + { 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 + 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 + 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 + 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 + 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 + 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 + 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 container. + * 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 + * #include + * #include + * + * 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> + 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::max(). + static const size_type npos = static_cast(-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(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 __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 + 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> + (__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 __il) + { this->append(__il.begin(), __il.end()); } + + /** + * @brief Append an iterator range of blocks. + */ + template + 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 _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 + void + _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, + _CharT, _CharT); + + template + 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 + 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 + { return this->_M_do_count(); } + + /// Returns the total number of bits. + size_type + size() const + { return this->_M_Nb; } + + /// Returns the total number of blocks. + size_type num_blocks() const + { return this->_M_size(); } + + /// Returns true if the dynamic_bitset is empty. + bool + empty() const + { 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() const + { return std::numeric_limits::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 + template + 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 + template + 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 + bool + operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, + const dynamic_bitset<_WordT, _Alloc>& __rhs) + { return __lhs._M_is_equal(__rhs); } + + template + bool + operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, + const dynamic_bitset<_WordT, _Alloc>& __rhs) + { return !__lhs._M_is_equal(__rhs); } + + template + bool + operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, + const dynamic_bitset<_WordT, _Alloc>& __rhs) + { return __lhs._M_is_less(__rhs); } + + template + bool + operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, + const dynamic_bitset<_WordT, _Alloc>& __rhs) + { return !(__lhs > __rhs); } + + template + bool + operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, + const dynamic_bitset<_WordT, _Alloc>& __rhs) + { return __rhs < __lhs; } + + template + 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 + 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 + 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 + 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 + 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 + 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(0), __x.size(), + __zero, __one); + if (__state) + __is.setstate(__state); + return __is; + } + + template + 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>(__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 */