libstdc++
|
00001 // TR2 <dynamic_bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2009-2013 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file tr2/dynamic_bitset 00026 * This is a TR2 C++ Library header. 00027 */ 00028 00029 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET 00030 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1 00031 00032 #pragma GCC system_header 00033 00034 #include <limits> 00035 #include <vector> 00036 #include <string> 00037 #include <memory> // For std::allocator 00038 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 00039 // overflow_error 00040 #include <iosfwd> 00041 #include <bits/cxxabi_forced.h> 00042 00043 namespace std _GLIBCXX_VISIBILITY(default) 00044 { 00045 namespace tr2 00046 { 00047 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00048 00049 /** 00050 * Dynamic Bitset. 00051 * 00052 * See N2050, 00053 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 00054 */ 00055 namespace __detail 00056 { 00057 00058 template<typename T> 00059 class _Bool2UChar 00060 { 00061 typedef T type; 00062 }; 00063 00064 template<> 00065 class _Bool2UChar<bool> 00066 { 00067 public: 00068 typedef unsigned char type; 00069 }; 00070 00071 } 00072 00073 /** 00074 * Base class, general case. 00075 * 00076 * See documentation for dynamic_bitset. 00077 */ 00078 template<typename _WordT = unsigned long long, 00079 typename _Alloc = std::allocator<_WordT>> 00080 struct __dynamic_bitset_base 00081 { 00082 static_assert(std::is_unsigned<_WordT>::value, "template argument " 00083 "_WordT not an unsigned integral type"); 00084 00085 typedef _WordT block_type; 00086 typedef _Alloc allocator_type; 00087 typedef size_t size_type; 00088 00089 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 00090 static const size_type npos = static_cast<size_type>(-1); 00091 00092 /// 0 is the least significant word. 00093 std::vector<block_type, allocator_type> _M_w; 00094 00095 explicit 00096 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type()) 00097 : _M_w(__alloc) 00098 { } 00099 00100 explicit 00101 __dynamic_bitset_base(__dynamic_bitset_base&& __b) 00102 { this->_M_w.swap(__b._M_w); } 00103 00104 explicit 00105 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 00106 const allocator_type& __alloc = allocator_type()) 00107 : _M_w(__nbits / _S_bits_per_block 00108 + (__nbits % _S_bits_per_block > 0), 00109 __val, __alloc) 00110 { 00111 unsigned long long __mask = ~static_cast<block_type>(0); 00112 size_t __n = std::min(this->_M_w.size(), 00113 sizeof(unsigned long long) / sizeof(block_type)); 00114 for (size_t __i = 0; __i < __n; ++__i) 00115 { 00116 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block); 00117 __mask <<= _S_bits_per_block; 00118 } 00119 } 00120 00121 void 00122 _M_assign(const __dynamic_bitset_base& __b) 00123 { this->_M_w = __b._M_w; } 00124 00125 void 00126 _M_swap(__dynamic_bitset_base& __b) 00127 { this->_M_w.swap(__b._M_w); } 00128 00129 void 00130 _M_clear() 00131 { this->_M_w.clear(); } 00132 00133 void 00134 _M_resize(size_t __nbits, bool __value) 00135 { 00136 size_t __sz = __nbits / _S_bits_per_block; 00137 if (__nbits % _S_bits_per_block > 0) 00138 ++__sz; 00139 if (__sz != this->_M_w.size()) 00140 this->_M_w.resize(__sz); 00141 } 00142 00143 allocator_type 00144 _M_get_allocator() const 00145 { return this->_M_w.get_allocator(); } 00146 00147 static size_type 00148 _S_whichword(size_type __pos) noexcept 00149 { return __pos / _S_bits_per_block; } 00150 00151 static size_type 00152 _S_whichbyte(size_type __pos) noexcept 00153 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 00154 00155 static size_type 00156 _S_whichbit(size_type __pos) noexcept 00157 { return __pos % _S_bits_per_block; } 00158 00159 static block_type 00160 _S_maskbit(size_type __pos) noexcept 00161 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 00162 00163 block_type& 00164 _M_getword(size_type __pos) 00165 { return this->_M_w[_S_whichword(__pos)]; } 00166 00167 block_type 00168 _M_getword(size_type __pos) const 00169 { return this->_M_w[_S_whichword(__pos)]; } 00170 00171 block_type& 00172 _M_hiword() 00173 { return this->_M_w[_M_w.size() - 1]; } 00174 00175 block_type 00176 _M_hiword() const 00177 { return this->_M_w[_M_w.size() - 1]; } 00178 00179 void 00180 _M_do_and(const __dynamic_bitset_base& __x) 00181 { 00182 if (__x._M_w.size() == this->_M_w.size()) 00183 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00184 this->_M_w[__i] &= __x._M_w[__i]; 00185 else 00186 return; 00187 } 00188 00189 void 00190 _M_do_or(const __dynamic_bitset_base& __x) 00191 { 00192 if (__x._M_w.size() == this->_M_w.size()) 00193 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00194 this->_M_w[__i] |= __x._M_w[__i]; 00195 else 00196 return; 00197 } 00198 00199 void 00200 _M_do_xor(const __dynamic_bitset_base& __x) 00201 { 00202 if (__x._M_w.size() == this->_M_w.size()) 00203 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00204 this->_M_w[__i] ^= __x._M_w[__i]; 00205 else 00206 return; 00207 } 00208 00209 void 00210 _M_do_dif(const __dynamic_bitset_base& __x) 00211 { 00212 if (__x._M_w.size() == this->_M_w.size()) 00213 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00214 this->_M_w[__i] &= ~__x._M_w[__i]; 00215 else 00216 return; 00217 } 00218 00219 void 00220 _M_do_left_shift(size_t __shift); 00221 00222 void 00223 _M_do_right_shift(size_t __shift); 00224 00225 void 00226 _M_do_flip() 00227 { 00228 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00229 this->_M_w[__i] = ~this->_M_w[__i]; 00230 } 00231 00232 void 00233 _M_do_set() 00234 { 00235 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00236 this->_M_w[__i] = ~static_cast<block_type>(0); 00237 } 00238 00239 void 00240 _M_do_reset() 00241 { 00242 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00243 this->_M_w[__i] = static_cast<block_type>(0); 00244 } 00245 00246 bool 00247 _M_is_equal(const __dynamic_bitset_base& __x) const 00248 { 00249 if (__x.size() == this->size()) 00250 { 00251 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00252 if (this->_M_w[__i] != __x._M_w[__i]) 00253 return false; 00254 return true; 00255 } 00256 else 00257 return false; 00258 } 00259 00260 bool 00261 _M_is_less(const __dynamic_bitset_base& __x) const 00262 { 00263 if (__x.size() == this->size()) 00264 { 00265 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 00266 { 00267 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 00268 return true; 00269 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 00270 return false; 00271 } 00272 return false; 00273 } 00274 else 00275 return false; 00276 } 00277 00278 size_t 00279 _M_are_all_aux() const 00280 { 00281 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 00282 if (_M_w[__i] != ~static_cast<block_type>(0)) 00283 return 0; 00284 return ((this->_M_w.size() - 1) * _S_bits_per_block 00285 + __builtin_popcountl(this->_M_hiword())); 00286 } 00287 00288 bool 00289 _M_is_any() const 00290 { 00291 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00292 if (this->_M_w[__i] != static_cast<block_type>(0)) 00293 return true; 00294 return false; 00295 } 00296 00297 bool 00298 _M_is_subset_of(const __dynamic_bitset_base& __b) 00299 { 00300 if (__b.size() == this->size()) 00301 { 00302 for (size_t __i = 0; __i < _M_w.size(); ++__i) 00303 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 00304 return false; 00305 return true; 00306 } 00307 else 00308 return false; 00309 } 00310 00311 bool 00312 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const 00313 { 00314 if (this->is_subset_of(__b)) 00315 { 00316 if (*this == __b) 00317 return false; 00318 else 00319 return true; 00320 } 00321 else 00322 return false; 00323 } 00324 00325 size_t 00326 _M_do_count() const 00327 { 00328 size_t __result = 0; 00329 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00330 __result += __builtin_popcountl(this->_M_w[__i]); 00331 return __result; 00332 } 00333 00334 size_type 00335 _M_size() const noexcept 00336 { return this->_M_w.size(); } 00337 00338 unsigned long 00339 _M_do_to_ulong() const; 00340 00341 unsigned long long 00342 _M_do_to_ullong() const; 00343 00344 // find first "on" bit 00345 size_type 00346 _M_do_find_first(size_t __not_found) const; 00347 00348 // find the next "on" bit that follows "prev" 00349 size_type 00350 _M_do_find_next(size_t __prev, size_t __not_found) const; 00351 00352 // do append of block 00353 void 00354 _M_do_append_block(block_type __block, size_type __pos) 00355 { 00356 size_t __offset = __pos % _S_bits_per_block; 00357 if (__offset == 0) 00358 this->_M_w.push_back(__block); 00359 else 00360 { 00361 this->_M_hiword() |= (__block << __offset); 00362 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 00363 } 00364 } 00365 }; 00366 00367 // Definitions of non-inline functions from __dynamic_bitset_base. 00368 template<typename _WordT, typename _Alloc> 00369 void 00370 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) 00371 { 00372 if (__builtin_expect(__shift != 0, 1)) 00373 { 00374 const size_t __wshift = __shift / _S_bits_per_block; 00375 const size_t __offset = __shift % _S_bits_per_block; 00376 00377 if (__offset == 0) 00378 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) 00379 this->_M_w[__n] = this->_M_w[__n - __wshift]; 00380 else 00381 { 00382 const size_t __sub_offset = _S_bits_per_block - __offset; 00383 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) 00384 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) 00385 | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); 00386 this->_M_w[__wshift] = this->_M_w[0] << __offset; 00387 } 00388 00389 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, 00390 //// static_cast<_WordT>(0)); 00391 } 00392 } 00393 00394 template<typename _WordT, typename _Alloc> 00395 void 00396 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) 00397 { 00398 if (__builtin_expect(__shift != 0, 1)) 00399 { 00400 const size_t __wshift = __shift / _S_bits_per_block; 00401 const size_t __offset = __shift % _S_bits_per_block; 00402 const size_t __limit = this->_M_w.size() - __wshift - 1; 00403 00404 if (__offset == 0) 00405 for (size_t __n = 0; __n <= __limit; ++__n) 00406 this->_M_w[__n] = this->_M_w[__n + __wshift]; 00407 else 00408 { 00409 const size_t __sub_offset = (_S_bits_per_block 00410 - __offset); 00411 for (size_t __n = 0; __n < __limit; ++__n) 00412 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) 00413 | (this->_M_w[__n + __wshift + 1] << __sub_offset)); 00414 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; 00415 } 00416 00417 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), 00418 //// static_cast<_WordT>(0)); 00419 } 00420 } 00421 00422 template<typename _WordT, typename _Alloc> 00423 unsigned long 00424 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const 00425 { 00426 size_t __n = sizeof(unsigned long) / sizeof(block_type); 00427 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00428 if (this->_M_w[__i]) 00429 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); 00430 unsigned long __res = 0UL; 00431 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00432 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00433 return __res; 00434 } 00435 00436 template<typename _WordT, typename _Alloc> 00437 unsigned long long 00438 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const 00439 { 00440 size_t __n = sizeof(unsigned long long) / sizeof(block_type); 00441 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00442 if (this->_M_w[__i]) 00443 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); 00444 unsigned long long __res = 0ULL; 00445 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00446 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00447 return __res; 00448 } 00449 00450 template<typename _WordT, typename _Alloc> 00451 size_t 00452 __dynamic_bitset_base<_WordT, _Alloc> 00453 ::_M_do_find_first(size_t __not_found) const 00454 { 00455 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00456 { 00457 _WordT __thisword = this->_M_w[__i]; 00458 if (__thisword != static_cast<_WordT>(0)) 00459 return (__i * _S_bits_per_block 00460 + __builtin_ctzl(__thisword)); 00461 } 00462 // not found, so return an indication of failure. 00463 return __not_found; 00464 } 00465 00466 template<typename _WordT, typename _Alloc> 00467 size_t 00468 __dynamic_bitset_base<_WordT, _Alloc> 00469 ::_M_do_find_next(size_t __prev, size_t __not_found) const 00470 { 00471 // make bound inclusive 00472 ++__prev; 00473 00474 // check out of bounds 00475 if (__prev >= this->_M_w.size() * _S_bits_per_block) 00476 return __not_found; 00477 00478 // search first word 00479 size_t __i = _S_whichword(__prev); 00480 _WordT __thisword = this->_M_w[__i]; 00481 00482 // mask off bits below bound 00483 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00484 00485 if (__thisword != static_cast<_WordT>(0)) 00486 return (__i * _S_bits_per_block 00487 + __builtin_ctzl(__thisword)); 00488 00489 // check subsequent words 00490 for (++__i; __i < this->_M_w.size(); ++__i) 00491 { 00492 __thisword = this->_M_w[__i]; 00493 if (__thisword != static_cast<_WordT>(0)) 00494 return (__i * _S_bits_per_block 00495 + __builtin_ctzl(__thisword)); 00496 } 00497 // not found, so return an indication of failure. 00498 return __not_found; 00499 } // end _M_do_find_next 00500 00501 /** 00502 * @brief The %dynamic_bitset class represents a sequence of bits. 00503 * 00504 * @ingroup containers 00505 * 00506 * (Note that %dynamic_bitset does @e not meet the formal 00507 * requirements of a <a href="tables.html#65">container</a>. 00508 * Mainly, it lacks iterators.) 00509 * 00510 * The template argument, @a Nb, may be any non-negative number, 00511 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00512 * 00513 * In the general unoptimized case, storage is allocated in 00514 * word-sized blocks. Let B be the number of bits in a word, then 00515 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 00516 * unused. (They are the high-order bits in the highest word.) It 00517 * is a class invariant that those unused bits are always zero. 00518 * 00519 * If you think of %dynamic_bitset as "a simple array of bits," be 00520 * aware that your mental picture is reversed: a %dynamic_bitset 00521 * behaves the same way as bits in integers do, with the bit at 00522 * index 0 in the "least significant / right-hand" position, and 00523 * the bit at index Nb-1 in the "most significant / left-hand" 00524 * position. Thus, unlike other containers, a %dynamic_bitset's 00525 * index "counts from right to left," to put it very loosely. 00526 * 00527 * This behavior is preserved when translating to and from strings. 00528 * For example, the first line of the following program probably 00529 * prints "b('a') is 0001100001" on a modern ASCII system. 00530 * 00531 * @code 00532 * #include <dynamic_bitset> 00533 * #include <iostream> 00534 * #include <sstream> 00535 * 00536 * using namespace std; 00537 * 00538 * int main() 00539 * { 00540 * long a = 'a'; 00541 * dynamic_bitset b(a); 00542 * 00543 * cout << "b('a') is " << b << endl; 00544 * 00545 * ostringstream s; 00546 * s << b; 00547 * string str = s.str(); 00548 * cout << "index 3 in the string is " << str[3] << " but\n" 00549 * << "index 3 in the bitset is " << b[3] << endl; 00550 * } 00551 * @endcode 00552 * 00553 * Also see: 00554 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 00555 * for a description of extensions. 00556 * 00557 * Most of the actual code isn't contained in %dynamic_bitset<> 00558 * itself, but in the base class __dynamic_bitset_base. The base 00559 * class works with whole words, not with individual bits. This 00560 * allows us to specialize __dynamic_bitset_base for the important 00561 * special case where the %dynamic_bitset is only a single word. 00562 * 00563 * Extra confusion can result due to the fact that the storage for 00564 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 00565 * carefully encapsulated. 00566 */ 00567 template<typename _WordT = unsigned long long, 00568 typename _Alloc = std::allocator<_WordT>> 00569 class dynamic_bitset 00570 : private __dynamic_bitset_base<_WordT, _Alloc> 00571 { 00572 static_assert(std::is_unsigned<_WordT>::value, "template argument " 00573 "_WordT not an unsigned integral type"); 00574 00575 public: 00576 00577 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 00578 typedef _WordT block_type; 00579 typedef _Alloc allocator_type; 00580 typedef size_t size_type; 00581 00582 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 00583 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 00584 static const size_type npos = static_cast<size_type>(-1); 00585 00586 private: 00587 00588 // Clear the unused bits in the uppermost word. 00589 void 00590 _M_do_sanitize() 00591 { 00592 size_type __shift = this->_M_Nb % bits_per_block; 00593 if (__shift > 0) 00594 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift); 00595 } 00596 00597 /** 00598 * These versions of single-bit set, reset, flip, and test 00599 * do no range checking. 00600 */ 00601 dynamic_bitset<_WordT, _Alloc>& 00602 _M_unchecked_set(size_type __pos) 00603 { 00604 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00605 return *this; 00606 } 00607 00608 dynamic_bitset<_WordT, _Alloc>& 00609 _M_unchecked_set(size_type __pos, int __val) 00610 { 00611 if (__val) 00612 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00613 else 00614 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00615 return *this; 00616 } 00617 00618 dynamic_bitset<_WordT, _Alloc>& 00619 _M_unchecked_reset(size_type __pos) 00620 { 00621 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00622 return *this; 00623 } 00624 00625 dynamic_bitset<_WordT, _Alloc>& 00626 _M_unchecked_flip(size_type __pos) 00627 { 00628 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 00629 return *this; 00630 } 00631 00632 bool 00633 _M_unchecked_test(size_type __pos) const 00634 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 00635 != static_cast<_WordT>(0)); } 00636 00637 size_type _M_Nb; 00638 00639 public: 00640 /** 00641 * This encapsulates the concept of a single bit. An instance 00642 * of this class is a proxy for an actual bit; this way the 00643 * individual bit operations are done as faster word-size 00644 * bitwise instructions. 00645 * 00646 * Most users will never need to use this class directly; 00647 * conversions to and from bool are automatic and should be 00648 * transparent. Overloaded operators help to preserve the 00649 * illusion. 00650 * 00651 * (On a typical system, this "bit %reference" is 64 times the 00652 * size of an actual bit. Ha.) 00653 */ 00654 class reference 00655 { 00656 friend class dynamic_bitset; 00657 00658 block_type *_M_wp; 00659 size_type _M_bpos; 00660 00661 // left undefined 00662 reference(); 00663 00664 public: 00665 reference(dynamic_bitset& __b, size_type __pos) 00666 { 00667 this->_M_wp = &__b._M_getword(__pos); 00668 this->_M_bpos = _Base::_S_whichbit(__pos); 00669 } 00670 00671 ~reference() 00672 { } 00673 00674 // For b[i] = __x; 00675 reference& 00676 operator=(bool __x) 00677 { 00678 if (__x) 00679 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 00680 else 00681 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 00682 return *this; 00683 } 00684 00685 // For b[i] = b[__j]; 00686 reference& 00687 operator=(const reference& __j) 00688 { 00689 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 00690 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 00691 else 00692 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 00693 return *this; 00694 } 00695 00696 // Flips the bit 00697 bool 00698 operator~() const 00699 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 00700 00701 // For __x = b[i]; 00702 operator bool() const 00703 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 00704 00705 // For b[i].flip(); 00706 reference& 00707 flip() 00708 { 00709 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 00710 return *this; 00711 } 00712 }; 00713 00714 friend class reference; 00715 00716 typedef bool const_reference; 00717 00718 // 23.3.5.1 constructors: 00719 /// All bits set to zero. 00720 explicit 00721 dynamic_bitset(const allocator_type& __alloc = allocator_type()) 00722 : _Base(__alloc), _M_Nb(0) 00723 { } 00724 00725 /// Initial bits bitwise-copied from a single word (others set to zero). 00726 explicit 00727 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 00728 const allocator_type& __alloc = allocator_type()) 00729 : _Base(__nbits, __val, __alloc), 00730 _M_Nb(__nbits) 00731 { } 00732 00733 dynamic_bitset(initializer_list<block_type> __il, 00734 const allocator_type& __alloc = allocator_type()) 00735 : _Base(__alloc), _M_Nb(0) 00736 { this->append(__il); } 00737 00738 /** 00739 * @brief Use a subset of a string. 00740 * @param __str A string of '0' and '1' characters. 00741 * @param __pos Index of the first character in @p __str to use. 00742 * @param __n The number of characters to copy. 00743 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 00744 * @throw std::invalid_argument If a character appears in the string 00745 * which is neither '0' nor '1'. 00746 */ 00747 template<typename _CharT, typename _Traits, typename _Alloc1> 00748 explicit 00749 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 00750 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00751 __pos = 0, 00752 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00753 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 00754 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 00755 const allocator_type& __alloc = allocator_type()) 00756 : _Base(__alloc), 00757 _M_Nb(0) // Watch for npos. 00758 { 00759 if (__pos > __str.size()) 00760 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 00761 "not valid")); 00762 00763 // Watch for npos. 00764 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 00765 this->resize(this->_M_Nb); 00766 this->_M_copy_from_string(__str, __pos, __n, 00767 _CharT('0'), _CharT('1')); 00768 } 00769 00770 /** 00771 * @brief Construct from a string. 00772 * @param __str A string of '0' and '1' characters. 00773 * @throw std::invalid_argument If a character appears in the string 00774 * which is neither '0' nor '1'. 00775 */ 00776 explicit 00777 dynamic_bitset(const char* __str, 00778 const allocator_type& __alloc = allocator_type()) 00779 : _Base(__alloc) 00780 { 00781 size_t __len = 0; 00782 if (__str) 00783 while (__str[__len] != '\0') 00784 ++__len; 00785 this->resize(__len); 00786 this->_M_copy_from_ptr<char,std::char_traits<char>> 00787 (__str, __len, 0, __len, '0', '1'); 00788 } 00789 00790 /** 00791 * @brief Copy constructor. 00792 */ 00793 dynamic_bitset(const dynamic_bitset& __b) 00794 : _Base(__b), _M_Nb(__b.size()) 00795 { } 00796 00797 /** 00798 * @brief Move constructor. 00799 */ 00800 dynamic_bitset(dynamic_bitset&& __b) 00801 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) 00802 { } 00803 00804 /** 00805 * @brief Swap with another bitset. 00806 */ 00807 void 00808 swap(dynamic_bitset& __b) 00809 { 00810 this->_M_swap(__b); 00811 std::swap(this->_M_Nb, __b._M_Nb); 00812 } 00813 00814 /** 00815 * @brief Assignment. 00816 */ 00817 dynamic_bitset& 00818 operator=(const dynamic_bitset& __b) 00819 { 00820 if (&__b != this) 00821 { 00822 this->_M_assign(__b); 00823 this->_M_Nb = __b._M_Nb; 00824 } 00825 } 00826 00827 /** 00828 * @brief Move assignment. 00829 */ 00830 dynamic_bitset& 00831 operator=(dynamic_bitset&& __b) 00832 { 00833 this->swap(__b); 00834 return *this; 00835 } 00836 00837 /** 00838 * @brief Return the allocator for the bitset. 00839 */ 00840 allocator_type 00841 get_allocator() const 00842 { return this->_M_get_allocator(); } 00843 00844 /** 00845 * @brief Resize the bitset. 00846 */ 00847 void 00848 resize(size_type __nbits, bool __value = false) 00849 { 00850 this->_M_resize(__nbits, __value); 00851 this->_M_Nb = __nbits; 00852 this->_M_do_sanitize(); 00853 } 00854 00855 /** 00856 * @brief Clear the bitset. 00857 */ 00858 void 00859 clear() 00860 { 00861 this->_M_clear(); 00862 this->_M_Nb = 0; 00863 } 00864 00865 /** 00866 * @brief Push a bit onto the high end of the bitset. 00867 */ 00868 void 00869 push_back(bool __bit) 00870 { 00871 if (size_t __offset = this->size() % bits_per_block == 0) 00872 this->_M_do_append_block(block_type(0), this->_M_Nb); 00873 ++this->_M_Nb; 00874 this->_M_unchecked_set(this->_M_Nb, __bit); 00875 } 00876 00877 /** 00878 * @brief Append a block. 00879 */ 00880 void 00881 append(block_type __block) 00882 { 00883 this->_M_do_append_block(__block, this->_M_Nb); 00884 this->_M_Nb += bits_per_block; 00885 } 00886 00887 /** 00888 * @brief 00889 */ 00890 void 00891 append(initializer_list<block_type> __il) 00892 { this->append(__il.begin(), __il.end()); } 00893 00894 /** 00895 * @brief Append an iterator range of blocks. 00896 */ 00897 template <typename _BlockInputIterator> 00898 void 00899 append(_BlockInputIterator __first, _BlockInputIterator __last) 00900 { 00901 for (; __first != __last; ++__first) 00902 this->append(*__first); 00903 } 00904 00905 // 23.3.5.2 dynamic_bitset operations: 00906 //@{ 00907 /** 00908 * @brief Operations on dynamic_bitsets. 00909 * @param __rhs A same-sized dynamic_bitset. 00910 * 00911 * These should be self-explanatory. 00912 */ 00913 dynamic_bitset<_WordT, _Alloc>& 00914 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00915 { 00916 this->_M_do_and(__rhs); 00917 return *this; 00918 } 00919 00920 dynamic_bitset<_WordT, _Alloc>& 00921 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 00922 { 00923 this->_M_do_and(std::move(__rhs)); 00924 return *this; 00925 } 00926 00927 dynamic_bitset<_WordT, _Alloc>& 00928 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00929 { 00930 this->_M_do_or(__rhs); 00931 return *this; 00932 } 00933 00934 dynamic_bitset<_WordT, _Alloc>& 00935 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00936 { 00937 this->_M_do_xor(__rhs); 00938 return *this; 00939 } 00940 00941 dynamic_bitset<_WordT, _Alloc>& 00942 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00943 { 00944 this->_M_do_dif(__rhs); 00945 return *this; 00946 } 00947 //@} 00948 00949 //@{ 00950 /** 00951 * @brief Operations on dynamic_bitsets. 00952 * @param __pos The number of places to shift. 00953 * 00954 * These should be self-explanatory. 00955 */ 00956 dynamic_bitset<_WordT, _Alloc>& 00957 operator<<=(size_type __pos) 00958 { 00959 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00960 { 00961 this->_M_do_left_shift(__pos); 00962 this->_M_do_sanitize(); 00963 } 00964 else 00965 this->_M_do_reset(); 00966 return *this; 00967 } 00968 00969 dynamic_bitset<_WordT, _Alloc>& 00970 operator>>=(size_type __pos) 00971 { 00972 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00973 { 00974 this->_M_do_right_shift(__pos); 00975 this->_M_do_sanitize(); 00976 } 00977 else 00978 this->_M_do_reset(); 00979 return *this; 00980 } 00981 //@} 00982 00983 // Set, reset, and flip. 00984 /** 00985 * @brief Sets every bit to true. 00986 */ 00987 dynamic_bitset<_WordT, _Alloc>& 00988 set() 00989 { 00990 this->_M_do_set(); 00991 this->_M_do_sanitize(); 00992 return *this; 00993 } 00994 00995 /** 00996 * @brief Sets a given bit to a particular value. 00997 * @param __pos The index of the bit. 00998 * @param __val Either true or false, defaults to true. 00999 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01000 */ 01001 dynamic_bitset<_WordT, _Alloc>& 01002 set(size_type __pos, bool __val = true) 01003 { 01004 if (__pos >= _M_Nb) 01005 __throw_out_of_range(__N("dynamic_bitset::set")); 01006 return this->_M_unchecked_set(__pos, __val); 01007 } 01008 01009 /** 01010 * @brief Sets every bit to false. 01011 */ 01012 dynamic_bitset<_WordT, _Alloc>& 01013 reset() 01014 { 01015 this->_M_do_reset(); 01016 return *this; 01017 } 01018 01019 /** 01020 * @brief Sets a given bit to false. 01021 * @param __pos The index of the bit. 01022 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01023 * 01024 * Same as writing @c set(__pos, false). 01025 */ 01026 dynamic_bitset<_WordT, _Alloc>& 01027 reset(size_type __pos) 01028 { 01029 if (__pos >= _M_Nb) 01030 __throw_out_of_range(__N("dynamic_bitset::reset")); 01031 return this->_M_unchecked_reset(__pos); 01032 } 01033 01034 /** 01035 * @brief Toggles every bit to its opposite value. 01036 */ 01037 dynamic_bitset<_WordT, _Alloc>& 01038 flip() 01039 { 01040 this->_M_do_flip(); 01041 this->_M_do_sanitize(); 01042 return *this; 01043 } 01044 01045 /** 01046 * @brief Toggles a given bit to its opposite value. 01047 * @param __pos The index of the bit. 01048 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01049 */ 01050 dynamic_bitset<_WordT, _Alloc>& 01051 flip(size_type __pos) 01052 { 01053 if (__pos >= _M_Nb) 01054 __throw_out_of_range(__N("dynamic_bitset::flip")); 01055 return this->_M_unchecked_flip(__pos); 01056 } 01057 01058 /// See the no-argument flip(). 01059 dynamic_bitset<_WordT, _Alloc> 01060 operator~() const 01061 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 01062 01063 //@{ 01064 /** 01065 * @brief Array-indexing support. 01066 * @param __pos Index into the %dynamic_bitset. 01067 * @return A bool for a 'const %dynamic_bitset'. For non-const 01068 * bitsets, an instance of the reference proxy class. 01069 * @note These operators do no range checking and throw no 01070 * exceptions, as required by DR 11 to the standard. 01071 */ 01072 reference 01073 operator[](size_type __pos) 01074 { return reference(*this,__pos); } 01075 01076 const_reference 01077 operator[](size_type __pos) const 01078 { return _M_unchecked_test(__pos); } 01079 //@} 01080 01081 /** 01082 * @brief Returns a numerical interpretation of the %dynamic_bitset. 01083 * @return The integral equivalent of the bits. 01084 * @throw std::overflow_error If there are too many bits to be 01085 * represented in an @c unsigned @c long. 01086 */ 01087 unsigned long 01088 to_ulong() const 01089 { return this->_M_do_to_ulong(); } 01090 01091 /** 01092 * @brief Returns a numerical interpretation of the %dynamic_bitset. 01093 * @return The integral equivalent of the bits. 01094 * @throw std::overflow_error If there are too many bits to be 01095 * represented in an @c unsigned @c long. 01096 */ 01097 unsigned long long 01098 to_ullong() const 01099 { return this->_M_do_to_ullong(); } 01100 01101 /** 01102 * @brief Returns a character interpretation of the %dynamic_bitset. 01103 * @return The string equivalent of the bits. 01104 * 01105 * Note the ordering of the bits: decreasing character positions 01106 * correspond to increasing bit positions (see the main class notes for 01107 * an example). 01108 */ 01109 template<typename _CharT = char, 01110 typename _Traits = std::char_traits<_CharT>, 01111 typename _Alloc1 = std::allocator<_CharT>> 01112 std::basic_string<_CharT, _Traits, _Alloc1> 01113 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 01114 { 01115 std::basic_string<_CharT, _Traits, _Alloc1> __result; 01116 _M_copy_to_string(__result, __zero, __one); 01117 return __result; 01118 } 01119 01120 // Helper functions for string operations. 01121 template<typename _CharT, typename _Traits> 01122 void 01123 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 01124 _CharT, _CharT); 01125 01126 template<typename _CharT, typename _Traits, typename _Alloc1> 01127 void 01128 _M_copy_from_string(const std::basic_string<_CharT, 01129 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 01130 _CharT __zero = _CharT('0'), 01131 _CharT __one = _CharT('1')) 01132 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 01133 __pos, __n, __zero, __one); } 01134 01135 template<typename _CharT, typename _Traits, typename _Alloc1> 01136 void 01137 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 01138 _CharT __zero = _CharT('0'), 01139 _CharT __one = _CharT('1')) const; 01140 01141 /// Returns the number of bits which are set. 01142 size_type 01143 count() const noexcept 01144 { return this->_M_do_count(); } 01145 01146 /// Returns the total number of bits. 01147 size_type 01148 size() const noexcept 01149 { return this->_M_Nb; } 01150 01151 /// Returns the total number of blocks. 01152 size_type 01153 num_blocks() const noexcept 01154 { return this->_M_size(); } 01155 01156 /// Returns true if the dynamic_bitset is empty. 01157 bool 01158 empty() const noexcept 01159 { return (this->_M_Nb == 0); } 01160 01161 /// Returns the maximum size of a dynamic_bitset object having the same 01162 /// type as *this. 01163 /// The real answer is max() * bits_per_block but is likely to overflow. 01164 constexpr size_type 01165 max_size() noexcept 01166 { return std::numeric_limits<block_type>::max(); } 01167 01168 /** 01169 * @brief Tests the value of a bit. 01170 * @param __pos The index of a bit. 01171 * @return The value at @a __pos. 01172 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01173 */ 01174 bool 01175 test(size_type __pos) const 01176 { 01177 if (__pos >= _M_Nb) 01178 __throw_out_of_range(__N("dynamic_bitset::test")); 01179 return _M_unchecked_test(__pos); 01180 } 01181 01182 /** 01183 * @brief Tests whether all the bits are on. 01184 * @return True if all the bits are set. 01185 */ 01186 bool 01187 all() const 01188 { return this->_M_are_all_aux() == _M_Nb; } 01189 01190 /** 01191 * @brief Tests whether any of the bits are on. 01192 * @return True if at least one bit is set. 01193 */ 01194 bool 01195 any() const 01196 { return this->_M_is_any(); } 01197 01198 /** 01199 * @brief Tests whether any of the bits are on. 01200 * @return True if none of the bits are set. 01201 */ 01202 bool 01203 none() const 01204 { return !this->_M_is_any(); } 01205 01206 //@{ 01207 /// Self-explanatory. 01208 dynamic_bitset<_WordT, _Alloc> 01209 operator<<(size_type __pos) const 01210 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; } 01211 01212 dynamic_bitset<_WordT, _Alloc> 01213 operator>>(size_type __pos) const 01214 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; } 01215 //@} 01216 01217 /** 01218 * @brief Finds the index of the first "on" bit. 01219 * @return The index of the first bit set, or size() if not found. 01220 * @sa find_next 01221 */ 01222 size_type 01223 find_first() const 01224 { return this->_M_do_find_first(this->_M_Nb); } 01225 01226 /** 01227 * @brief Finds the index of the next "on" bit after prev. 01228 * @return The index of the next bit set, or size() if not found. 01229 * @param __prev Where to start searching. 01230 * @sa find_first 01231 */ 01232 size_type 01233 find_next(size_t __prev) const 01234 { return this->_M_do_find_next(__prev, this->_M_Nb); } 01235 01236 bool 01237 is_subset_of(const dynamic_bitset& __b) const 01238 { return this->_M_is_subset_of(__b); } 01239 01240 bool 01241 is_proper_subset_of(const dynamic_bitset& __b) const 01242 { return this->_M_is_proper_subset_of(__b); } 01243 }; 01244 01245 // Definitions of non-inline member functions. 01246 template<typename _WordT, typename _Alloc> 01247 template<typename _CharT, typename _Traits> 01248 void 01249 dynamic_bitset<_WordT, _Alloc>:: 01250 _M_copy_from_ptr(const _CharT* __str, size_t __len, 01251 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 01252 { 01253 reset(); 01254 const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos)); 01255 for (size_t __i = __nbits; __i > 0; --__i) 01256 { 01257 const _CharT __c = __str[__pos + __nbits - __i]; 01258 if (_Traits::eq(__c, __zero)) 01259 ; 01260 else if (_Traits::eq(__c, __one)) 01261 _M_unchecked_set(__i - 1); 01262 else 01263 __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr")); 01264 } 01265 } 01266 01267 template<typename _WordT, typename _Alloc> 01268 template<typename _CharT, typename _Traits, typename _Alloc1> 01269 void 01270 dynamic_bitset<_WordT, _Alloc>:: 01271 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 01272 _CharT __zero, _CharT __one) const 01273 { 01274 __str.assign(_M_Nb, __zero); 01275 for (size_t __i = _M_Nb; __i > 0; --__i) 01276 if (_M_unchecked_test(__i - 1)) 01277 _Traits::assign(__str[_M_Nb - __i], __one); 01278 } 01279 01280 01281 //@{ 01282 /// These comparisons for equality/inequality are, well, @e bitwise. 01283 template<typename _WordT, typename _Alloc> 01284 bool 01285 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01286 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01287 { return __lhs._M_is_equal(__rhs); } 01288 01289 template<typename _WordT, typename _Alloc> 01290 bool 01291 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01292 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01293 { return !__lhs._M_is_equal(__rhs); } 01294 01295 template<typename _WordT, typename _Alloc> 01296 bool 01297 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01298 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01299 { return __lhs._M_is_less(__rhs); } 01300 01301 template<typename _WordT, typename _Alloc> 01302 bool 01303 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01304 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01305 { return !(__lhs > __rhs); } 01306 01307 template<typename _WordT, typename _Alloc> 01308 bool 01309 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01310 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01311 { return __rhs < __lhs; } 01312 01313 template<typename _WordT, typename _Alloc> 01314 bool 01315 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01316 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01317 { return !(__lhs < __rhs); } 01318 //@} 01319 01320 // 23.3.5.3 bitset operations: 01321 //@{ 01322 /** 01323 * @brief Global bitwise operations on bitsets. 01324 * @param __x A bitset. 01325 * @param __y A bitset of the same size as @a __x. 01326 * @return A new bitset. 01327 * 01328 * These should be self-explanatory. 01329 */ 01330 template<typename _WordT, typename _Alloc> 01331 inline dynamic_bitset<_WordT, _Alloc> 01332 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 01333 const dynamic_bitset<_WordT, _Alloc>& __y) 01334 { 01335 dynamic_bitset<_WordT, _Alloc> __result(__x); 01336 __result &= __y; 01337 return __result; 01338 } 01339 01340 template<typename _WordT, typename _Alloc> 01341 inline dynamic_bitset<_WordT, _Alloc> 01342 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 01343 const dynamic_bitset<_WordT, _Alloc>& __y) 01344 { 01345 dynamic_bitset<_WordT, _Alloc> __result(__x); 01346 __result |= __y; 01347 return __result; 01348 } 01349 01350 template <typename _WordT, typename _Alloc> 01351 inline dynamic_bitset<_WordT, _Alloc> 01352 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 01353 const dynamic_bitset<_WordT, _Alloc>& __y) 01354 { 01355 dynamic_bitset<_WordT, _Alloc> __result(__x); 01356 __result ^= __y; 01357 return __result; 01358 } 01359 01360 template <typename _WordT, typename _Alloc> 01361 inline dynamic_bitset<_WordT, _Alloc> 01362 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 01363 const dynamic_bitset<_WordT, _Alloc>& __y) 01364 { 01365 dynamic_bitset<_WordT, _Alloc> __result(__x); 01366 __result -= __y; 01367 return __result; 01368 } 01369 //@} 01370 01371 //@{ 01372 /** 01373 * @brief Global I/O operators for bitsets. 01374 * 01375 * Direct I/O between streams and bitsets is supported. Output is 01376 * straightforward. Input will skip whitespace and only accept '0' 01377 * and '1' characters. The %dynamic_bitset will grow as necessary 01378 * to hold the string of bits. 01379 */ 01380 template<typename _CharT, typename _Traits, 01381 typename _WordT, typename _Alloc> 01382 std::basic_istream<_CharT, _Traits>& 01383 operator>>(std::basic_istream<_CharT, _Traits>& __is, 01384 dynamic_bitset<_WordT, _Alloc>& __x) 01385 { 01386 typedef typename _Traits::char_type char_type; 01387 typedef std::basic_istream<_CharT, _Traits> __istream_type; 01388 typedef typename __istream_type::ios_base __ios_base; 01389 01390 std::basic_string<_CharT, _Traits> __tmp; 01391 __tmp.reserve(__x.size()); 01392 01393 const char_type __zero = __is.widen('0'); 01394 const char_type __one = __is.widen('1'); 01395 01396 typename __ios_base::iostate __state = __ios_base::goodbit; 01397 typename __istream_type::sentry __sentry(__is); 01398 if (__sentry) 01399 { 01400 __try 01401 { 01402 while (1) 01403 { 01404 static typename _Traits::int_type __eof = _Traits::eof(); 01405 01406 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 01407 if (_Traits::eq_int_type(__c1, __eof)) 01408 { 01409 __state |= __ios_base::eofbit; 01410 break; 01411 } 01412 else 01413 { 01414 const char_type __c2 = _Traits::to_char_type(__c1); 01415 if (_Traits::eq(__c2, __zero)) 01416 __tmp.push_back(__zero); 01417 else if (_Traits::eq(__c2, __one)) 01418 __tmp.push_back(__one); 01419 else if (_Traits:: 01420 eq_int_type(__is.rdbuf()->sputbackc(__c2), 01421 __eof)) 01422 { 01423 __state |= __ios_base::failbit; 01424 break; 01425 } 01426 else 01427 break; 01428 } 01429 } 01430 } 01431 __catch(__cxxabiv1::__forced_unwind&) 01432 { 01433 __is._M_setstate(__ios_base::badbit); 01434 __throw_exception_again; 01435 } 01436 __catch(...) 01437 { __is._M_setstate(__ios_base::badbit); } 01438 } 01439 01440 __x.resize(__tmp.size()); 01441 01442 if (__tmp.empty() && __x.size()) 01443 __state |= __ios_base::failbit; 01444 else 01445 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(), 01446 __zero, __one); 01447 if (__state) 01448 __is.setstate(__state); 01449 return __is; 01450 } 01451 01452 template <typename _CharT, typename _Traits, 01453 typename _WordT, typename _Alloc> 01454 std::basic_ostream<_CharT, _Traits>& 01455 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01456 const dynamic_bitset<_WordT, _Alloc>& __x) 01457 { 01458 std::basic_string<_CharT, _Traits> __tmp; 01459 01460 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 01461 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01462 return __os << __tmp; 01463 } 01464 //@} 01465 01466 _GLIBCXX_END_NAMESPACE_VERSION 01467 } // tr2 01468 } // std 01469 01470 #undef _GLIBCXX_BITSET_BITS_PER_WORD 01471 01472 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */