libstdc++
|
00001 // TR2 <dynamic_bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2009, 2010, 2011 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 <cstddef> // For size_t 00037 #include <string> 00038 #include <memory> // For std::allocator 00039 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 00040 // overflow_error 00041 #include <iosfwd> 00042 #include <cxxabi_forced.h> 00043 00044 namespace std _GLIBCXX_VISIBILITY(default) 00045 { 00046 namespace tr2 00047 { 00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00049 00050 /** 00051 * Dynamic Bitset. 00052 * 00053 * See N2050, 00054 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 00055 */ 00056 namespace __detail 00057 { 00058 00059 template<typename T> 00060 class _Bool2UChar 00061 { 00062 typedef T type; 00063 }; 00064 00065 template<> 00066 class _Bool2UChar<bool> 00067 { 00068 public: 00069 typedef unsigned char type; 00070 }; 00071 00072 } 00073 00074 /** 00075 * Base class, general case. 00076 * 00077 * See documentation for dynamic_bitset. 00078 */ 00079 template<typename _WordT = unsigned long long, 00080 typename _Alloc = std::allocator<_WordT>> 00081 struct __dynamic_bitset_base 00082 { 00083 static_assert(std::is_unsigned<_WordT>::value, "template argument " 00084 "_WordT not an unsigned integral type"); 00085 00086 typedef _WordT block_type; 00087 typedef _Alloc allocator_type; 00088 typedef size_t size_type; 00089 00090 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 00091 static const size_type npos = static_cast<size_type>(-1); 00092 00093 /// 0 is the least significant word. 00094 std::vector<block_type, allocator_type> _M_w; 00095 00096 explicit 00097 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type()) 00098 : _M_w(__alloc) 00099 { } 00100 00101 explicit 00102 __dynamic_bitset_base(__dynamic_bitset_base&& __b) 00103 { this->_M_w.swap(__b._M_w); } 00104 00105 explicit 00106 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 00107 const allocator_type& __alloc = allocator_type()) 00108 : _M_w(__nbits / _S_bits_per_block 00109 + (__nbits % _S_bits_per_block > 0), 00110 __val, __alloc) 00111 { 00112 unsigned long long __mask = ~static_cast<block_type>(0); 00113 size_t __n = std::min(this->_M_w.size(), 00114 sizeof(unsigned long long) / sizeof(block_type)); 00115 for (size_t __i = 0; __i < __n; ++__i) 00116 { 00117 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block); 00118 __mask <<= _S_bits_per_block; 00119 } 00120 } 00121 00122 void 00123 _M_assign(const __dynamic_bitset_base& __b) 00124 { this->_M_w = __b._M_w; } 00125 00126 void 00127 _M_swap(__dynamic_bitset_base& __b) 00128 { this->_M_w.swap(__b._M_w); } 00129 00130 void 00131 _M_clear() 00132 { this->_M_w.clear(); } 00133 00134 void 00135 _M_resize(size_t __nbits, bool __value) 00136 { 00137 size_t __sz = __nbits / _S_bits_per_block; 00138 if (__nbits % _S_bits_per_block > 0) 00139 ++__sz; 00140 if (__sz != this->_M_w.size()) 00141 this->_M_w.resize(__sz); 00142 } 00143 00144 allocator_type 00145 _M_get_allocator() const 00146 { return this->_M_w.get_allocator(); } 00147 00148 static size_type 00149 _S_whichword(size_type __pos) 00150 { return __pos / _S_bits_per_block; } 00151 00152 static size_type 00153 _S_whichbyte(size_type __pos) 00154 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 00155 00156 static size_type 00157 _S_whichbit(size_type __pos) 00158 { return __pos % _S_bits_per_block; } 00159 00160 static block_type 00161 _S_maskbit(size_type __pos) 00162 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 00163 00164 block_type& 00165 _M_getword(size_type __pos) 00166 { return this->_M_w[_S_whichword(__pos)]; } 00167 00168 block_type 00169 _M_getword(size_type __pos) const 00170 { return this->_M_w[_S_whichword(__pos)]; } 00171 00172 block_type& 00173 _M_hiword() 00174 { return this->_M_w[_M_w.size() - 1]; } 00175 00176 block_type 00177 _M_hiword() const 00178 { return this->_M_w[_M_w.size() - 1]; } 00179 00180 void 00181 _M_do_and(const __dynamic_bitset_base& __x) 00182 { 00183 if (__x._M_w.size() == this->_M_w.size()) 00184 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00185 this->_M_w[__i] &= __x._M_w[__i]; 00186 else 00187 return; 00188 } 00189 00190 void 00191 _M_do_or(const __dynamic_bitset_base& __x) 00192 { 00193 if (__x._M_w.size() == this->_M_w.size()) 00194 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00195 this->_M_w[__i] |= __x._M_w[__i]; 00196 else 00197 return; 00198 } 00199 00200 void 00201 _M_do_xor(const __dynamic_bitset_base& __x) 00202 { 00203 if (__x._M_w.size() == this->_M_w.size()) 00204 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00205 this->_M_w[__i] ^= __x._M_w[__i]; 00206 else 00207 return; 00208 } 00209 00210 void 00211 _M_do_dif(const __dynamic_bitset_base& __x) 00212 { 00213 if (__x._M_w.size() == this->_M_w.size()) 00214 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00215 this->_M_w[__i] &= ~__x._M_w[__i]; 00216 else 00217 return; 00218 } 00219 00220 void 00221 _M_do_left_shift(size_t __shift); 00222 00223 void 00224 _M_do_right_shift(size_t __shift); 00225 00226 void 00227 _M_do_flip() 00228 { 00229 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00230 this->_M_w[__i] = ~this->_M_w[__i]; 00231 } 00232 00233 void 00234 _M_do_set() 00235 { 00236 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00237 this->_M_w[__i] = ~static_cast<block_type>(0); 00238 } 00239 00240 void 00241 _M_do_reset() 00242 { 00243 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00244 this->_M_w[__i] = static_cast<block_type>(0); 00245 } 00246 00247 bool 00248 _M_is_equal(const __dynamic_bitset_base& __x) const 00249 { 00250 if (__x.size() == this->size()) 00251 { 00252 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00253 if (this->_M_w[__i] != __x._M_w[__i]) 00254 return false; 00255 return true; 00256 } 00257 else 00258 return false; 00259 } 00260 00261 bool 00262 _M_is_less(const __dynamic_bitset_base& __x) const 00263 { 00264 if (__x.size() == this->size()) 00265 { 00266 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 00267 { 00268 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 00269 return true; 00270 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 00271 return false; 00272 } 00273 return false; 00274 } 00275 else 00276 return false; 00277 } 00278 00279 size_t 00280 _M_are_all_aux() const 00281 { 00282 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 00283 if (_M_w[__i] != ~static_cast<block_type>(0)) 00284 return 0; 00285 return ((this->_M_w.size() - 1) * _S_bits_per_block 00286 + __builtin_popcountl(this->_M_hiword())); 00287 } 00288 00289 bool 00290 _M_is_any() const 00291 { 00292 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00293 if (this->_M_w[__i] != static_cast<block_type>(0)) 00294 return true; 00295 return false; 00296 } 00297 00298 bool 00299 _M_is_subset_of(const __dynamic_bitset_base& __b) 00300 { 00301 if (__b.size() == this->size()) 00302 { 00303 for (size_t __i = 0; __i < _M_w.size(); ++__i) 00304 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 00305 return false; 00306 return true; 00307 } 00308 else 00309 return false; 00310 } 00311 00312 bool 00313 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const 00314 { 00315 if (this->is_subset_of(__b)) 00316 { 00317 if (*this == __b) 00318 return false; 00319 else 00320 return true; 00321 } 00322 else 00323 return false; 00324 } 00325 00326 size_t 00327 _M_do_count() const 00328 { 00329 size_t __result = 0; 00330 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00331 __result += __builtin_popcountl(this->_M_w[__i]); 00332 return __result; 00333 } 00334 00335 size_type 00336 _M_size() const 00337 { return this->_M_w.size(); } 00338 00339 unsigned long 00340 _M_do_to_ulong() const; 00341 00342 unsigned long long 00343 _M_do_to_ullong() const; 00344 00345 // find first "on" bit 00346 size_type 00347 _M_do_find_first(size_t __not_found) const; 00348 00349 // find the next "on" bit that follows "prev" 00350 size_type 00351 _M_do_find_next(size_t __prev, size_t __not_found) const; 00352 00353 // do append of block 00354 void 00355 _M_do_append_block(block_type __block, size_type __pos) 00356 { 00357 size_t __offset = __pos % _S_bits_per_block; 00358 if (__offset == 0) 00359 this->_M_w.push_back(__block); 00360 else 00361 { 00362 this->_M_hiword() |= (__block << __offset); 00363 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 00364 } 00365 } 00366 }; 00367 00368 // Definitions of non-inline functions from __dynamic_bitset_base. 00369 template<typename _WordT, typename _Alloc> 00370 void 00371 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) 00372 { 00373 if (__builtin_expect(__shift != 0, 1)) 00374 { 00375 const size_t __wshift = __shift / _S_bits_per_block; 00376 const size_t __offset = __shift % _S_bits_per_block; 00377 00378 if (__offset == 0) 00379 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) 00380 this->_M_w[__n] = this->_M_w[__n - __wshift]; 00381 else 00382 { 00383 const size_t __sub_offset = _S_bits_per_block - __offset; 00384 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) 00385 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) 00386 | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); 00387 this->_M_w[__wshift] = this->_M_w[0] << __offset; 00388 } 00389 00390 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, 00391 //// static_cast<_WordT>(0)); 00392 } 00393 } 00394 00395 template<typename _WordT, typename _Alloc> 00396 void 00397 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) 00398 { 00399 if (__builtin_expect(__shift != 0, 1)) 00400 { 00401 const size_t __wshift = __shift / _S_bits_per_block; 00402 const size_t __offset = __shift % _S_bits_per_block; 00403 const size_t __limit = this->_M_w.size() - __wshift - 1; 00404 00405 if (__offset == 0) 00406 for (size_t __n = 0; __n <= __limit; ++__n) 00407 this->_M_w[__n] = this->_M_w[__n + __wshift]; 00408 else 00409 { 00410 const size_t __sub_offset = (_S_bits_per_block 00411 - __offset); 00412 for (size_t __n = 0; __n < __limit; ++__n) 00413 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) 00414 | (this->_M_w[__n + __wshift + 1] << __sub_offset)); 00415 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; 00416 } 00417 00418 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), 00419 //// static_cast<_WordT>(0)); 00420 } 00421 } 00422 00423 template<typename _WordT, typename _Alloc> 00424 unsigned long 00425 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const 00426 { 00427 size_t __n = sizeof(unsigned long) / sizeof(block_type); 00428 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00429 if (this->_M_w[__i]) 00430 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); 00431 unsigned long __res = 0UL; 00432 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00433 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00434 return __res; 00435 } 00436 00437 template<typename _WordT, typename _Alloc> 00438 unsigned long long 00439 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const 00440 { 00441 size_t __n = sizeof(unsigned long long) / sizeof(block_type); 00442 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00443 if (this->_M_w[__i]) 00444 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); 00445 unsigned long long __res = 0ULL; 00446 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00447 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00448 return __res; 00449 } 00450 00451 template<typename _WordT, typename _Alloc> 00452 size_t 00453 __dynamic_bitset_base<_WordT, _Alloc> 00454 ::_M_do_find_first(size_t __not_found) const 00455 { 00456 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00457 { 00458 _WordT __thisword = this->_M_w[__i]; 00459 if (__thisword != static_cast<_WordT>(0)) 00460 return (__i * _S_bits_per_block 00461 + __builtin_ctzl(__thisword)); 00462 } 00463 // not found, so return an indication of failure. 00464 return __not_found; 00465 } 00466 00467 template<typename _WordT, typename _Alloc> 00468 size_t 00469 __dynamic_bitset_base<_WordT, _Alloc> 00470 ::_M_do_find_next(size_t __prev, size_t __not_found) const 00471 { 00472 // make bound inclusive 00473 ++__prev; 00474 00475 // check out of bounds 00476 if (__prev >= this->_M_w.size() * _S_bits_per_block) 00477 return __not_found; 00478 00479 // search first word 00480 size_t __i = _S_whichword(__prev); 00481 _WordT __thisword = this->_M_w[__i]; 00482 00483 // mask off bits below bound 00484 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00485 00486 if (__thisword != static_cast<_WordT>(0)) 00487 return (__i * _S_bits_per_block 00488 + __builtin_ctzl(__thisword)); 00489 00490 // check subsequent words 00491 for (++__i; __i < this->_M_w.size(); ++__i) 00492 { 00493 __thisword = this->_M_w[__i]; 00494 if (__thisword != static_cast<_WordT>(0)) 00495 return (__i * _S_bits_per_block 00496 + __builtin_ctzl(__thisword)); 00497 } 00498 // not found, so return an indication of failure. 00499 return __not_found; 00500 } // end _M_do_find_next 00501 00502 /** 00503 * @brief The %dynamic_bitset class represents a sequence of bits. 00504 * 00505 * @ingroup containers 00506 * 00507 * (Note that %dynamic_bitset does @e not meet the formal 00508 * requirements of a <a href="tables.html#65">container</a>. 00509 * Mainly, it lacks iterators.) 00510 * 00511 * The template argument, @a Nb, may be any non-negative number, 00512 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00513 * 00514 * In the general unoptimized case, storage is allocated in 00515 * word-sized blocks. Let B be the number of bits in a word, then 00516 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 00517 * unused. (They are the high-order bits in the highest word.) It 00518 * is a class invariant that those unused bits are always zero. 00519 * 00520 * If you think of %dynamic_bitset as "a simple array of bits," be 00521 * aware that your mental picture is reversed: a %dynamic_bitset 00522 * behaves the same way as bits in integers do, with the bit at 00523 * index 0 in the "least significant / right-hand" position, and 00524 * the bit at index Nb-1 in the "most significant / left-hand" 00525 * position. Thus, unlike other containers, a %dynamic_bitset's 00526 * index "counts from right to left," to put it very loosely. 00527 * 00528 * This behavior is preserved when translating to and from strings. 00529 * For example, the first line of the following program probably 00530 * prints "b('a') is 0001100001" on a modern ASCII system. 00531 * 00532 * @code 00533 * #include <dynamic_bitset> 00534 * #include <iostream> 00535 * #include <sstream> 00536 * 00537 * using namespace std; 00538 * 00539 * int main() 00540 * { 00541 * long a = 'a'; 00542 * dynamic_bitset b(a); 00543 * 00544 * cout << "b('a') is " << b << endl; 00545 * 00546 * ostringstream s; 00547 * s << b; 00548 * string str = s.str(); 00549 * cout << "index 3 in the string is " << str[3] << " but\n" 00550 * << "index 3 in the bitset is " << b[3] << endl; 00551 * } 00552 * @endcode 00553 * 00554 * Also see: 00555 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 00556 * for a description of extensions. 00557 * 00558 * Most of the actual code isn't contained in %dynamic_bitset<> 00559 * itself, but in the base class __dynamic_bitset_base. The base 00560 * class works with whole words, not with individual bits. This 00561 * allows us to specialize __dynamic_bitset_base for the important 00562 * special case where the %dynamic_bitset is only a single word. 00563 * 00564 * Extra confusion can result due to the fact that the storage for 00565 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 00566 * carefully encapsulated. 00567 */ 00568 template<typename _WordT = unsigned long long, 00569 typename _Alloc = std::allocator<_WordT>> 00570 class dynamic_bitset 00571 : private __dynamic_bitset_base<_WordT, _Alloc> 00572 { 00573 static_assert(std::is_unsigned<_WordT>::value, "template argument " 00574 "_WordT not an unsigned integral type"); 00575 00576 public: 00577 00578 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 00579 typedef _WordT block_type; 00580 typedef _Alloc allocator_type; 00581 typedef size_t size_type; 00582 00583 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 00584 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 00585 static const size_type npos = static_cast<size_type>(-1); 00586 00587 private: 00588 00589 // Clear the unused bits in the uppermost word. 00590 void 00591 _M_do_sanitize() 00592 { 00593 size_type __shift = this->_M_Nb % bits_per_block; 00594 if (__shift > 0) 00595 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift); 00596 } 00597 00598 /** 00599 * These versions of single-bit set, reset, flip, and test 00600 * do no range checking. 00601 */ 00602 dynamic_bitset<_WordT, _Alloc>& 00603 _M_unchecked_set(size_type __pos) 00604 { 00605 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00606 return *this; 00607 } 00608 00609 dynamic_bitset<_WordT, _Alloc>& 00610 _M_unchecked_set(size_type __pos, int __val) 00611 { 00612 if (__val) 00613 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00614 else 00615 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00616 return *this; 00617 } 00618 00619 dynamic_bitset<_WordT, _Alloc>& 00620 _M_unchecked_reset(size_type __pos) 00621 { 00622 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00623 return *this; 00624 } 00625 00626 dynamic_bitset<_WordT, _Alloc>& 00627 _M_unchecked_flip(size_type __pos) 00628 { 00629 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 00630 return *this; 00631 } 00632 00633 bool 00634 _M_unchecked_test(size_type __pos) const 00635 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 00636 != static_cast<_WordT>(0)); } 00637 00638 size_type _M_Nb; 00639 00640 public: 00641 /** 00642 * This encapsulates the concept of a single bit. An instance 00643 * of this class is a proxy for an actual bit; this way the 00644 * individual bit operations are done as faster word-size 00645 * bitwise instructions. 00646 * 00647 * Most users will never need to use this class directly; 00648 * conversions to and from bool are automatic and should be 00649 * transparent. Overloaded operators help to preserve the 00650 * illusion. 00651 * 00652 * (On a typical system, this "bit %reference" is 64 times the 00653 * size of an actual bit. Ha.) 00654 */ 00655 class reference 00656 { 00657 friend class dynamic_bitset; 00658 00659 block_type *_M_wp; 00660 size_type _M_bpos; 00661 00662 // left undefined 00663 reference(); 00664 00665 public: 00666 reference(dynamic_bitset& __b, size_type __pos) 00667 { 00668 this->_M_wp = &__b._M_getword(__pos); 00669 this->_M_bpos = _Base::_S_whichbit(__pos); 00670 } 00671 00672 ~reference() 00673 { } 00674 00675 // For b[i] = __x; 00676 reference& 00677 operator=(bool __x) 00678 { 00679 if (__x) 00680 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 00681 else 00682 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 00683 return *this; 00684 } 00685 00686 // For b[i] = b[__j]; 00687 reference& 00688 operator=(const reference& __j) 00689 { 00690 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 00691 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 00692 else 00693 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 00694 return *this; 00695 } 00696 00697 // Flips the bit 00698 bool 00699 operator~() const 00700 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 00701 00702 // For __x = b[i]; 00703 operator bool() const 00704 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 00705 00706 // For b[i].flip(); 00707 reference& 00708 flip() 00709 { 00710 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 00711 return *this; 00712 } 00713 }; 00714 00715 friend class reference; 00716 00717 typedef bool const_reference; 00718 00719 // 23.3.5.1 constructors: 00720 /// All bits set to zero. 00721 explicit 00722 dynamic_bitset(const allocator_type& __alloc = allocator_type()) 00723 : _Base(__alloc), _M_Nb(0) 00724 { } 00725 00726 /// Initial bits bitwise-copied from a single word (others set to zero). 00727 explicit 00728 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 00729 const allocator_type& __alloc = allocator_type()) 00730 : _Base(__nbits, __val, __alloc), 00731 _M_Nb(__nbits) 00732 { } 00733 00734 dynamic_bitset(initializer_list<block_type> __il, 00735 const allocator_type& __alloc = allocator_type()) 00736 : _Base(__alloc), _M_Nb(0) 00737 { this->append(__il); } 00738 00739 /** 00740 * @brief Use a subset of a string. 00741 * @param __str A string of '0' and '1' characters. 00742 * @param __pos Index of the first character in @p __str to use. 00743 * @param __n The number of characters to copy. 00744 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 00745 * @throw std::invalid_argument If a character appears in the string 00746 * which is neither '0' nor '1'. 00747 */ 00748 template<typename _CharT, typename _Traits, typename _Alloc1> 00749 explicit 00750 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 00751 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00752 __pos = 0, 00753 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00754 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 00755 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 00756 const allocator_type& __alloc = allocator_type()) 00757 : _Base(__alloc), 00758 _M_Nb(0) // Watch for npos. 00759 { 00760 if (__pos > __str.size()) 00761 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 00762 "not valid")); 00763 00764 // Watch for npos. 00765 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 00766 this->resize(this->_M_Nb); 00767 this->_M_copy_from_string(__str, __pos, __n, 00768 _CharT('0'), _CharT('1')); 00769 } 00770 00771 /** 00772 * @brief Construct from a string. 00773 * @param __str A string of '0' and '1' characters. 00774 * @throw std::invalid_argument If a character appears in the string 00775 * which is neither '0' nor '1'. 00776 */ 00777 explicit 00778 dynamic_bitset(const char* __str, 00779 const allocator_type& __alloc = allocator_type()) 00780 : _Base(__alloc) 00781 { 00782 size_t __len = 0; 00783 if (__str) 00784 while (__str[__len] != '\0') 00785 ++__len; 00786 this->resize(__len); 00787 this->_M_copy_from_ptr<char,std::char_traits<char>> 00788 (__str, __len, 0, __len, '0', '1'); 00789 } 00790 00791 /** 00792 * @brief Copy constructor. 00793 */ 00794 dynamic_bitset(const dynamic_bitset& __b) 00795 : _Base(__b), _M_Nb(__b.size()) 00796 { } 00797 00798 /** 00799 * @brief Move constructor. 00800 */ 00801 dynamic_bitset(dynamic_bitset&& __b) 00802 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) 00803 { } 00804 00805 /** 00806 * @brief Swap with another bitset. 00807 */ 00808 void 00809 swap(dynamic_bitset& __b) 00810 { 00811 this->_M_swap(__b); 00812 std::swap(this->_M_Nb, __b._M_Nb); 00813 } 00814 00815 /** 00816 * @brief Assignment. 00817 */ 00818 dynamic_bitset& 00819 operator=(const dynamic_bitset& __b) 00820 { 00821 if (&__b != this) 00822 { 00823 this->_M_assign(__b); 00824 this->_M_Nb = __b._M_Nb; 00825 } 00826 } 00827 00828 /** 00829 * @brief Move assignment. 00830 */ 00831 dynamic_bitset& 00832 operator=(dynamic_bitset&& __b) 00833 { 00834 this->swap(__b); 00835 return *this; 00836 } 00837 00838 /** 00839 * @brief Return the allocator for the bitset. 00840 */ 00841 allocator_type 00842 get_allocator() const 00843 { return this->_M_get_allocator(); } 00844 00845 /** 00846 * @brief Resize the bitset. 00847 */ 00848 void 00849 resize(size_type __nbits, bool __value = false) 00850 { 00851 this->_M_resize(__nbits, __value); 00852 this->_M_Nb = __nbits; 00853 this->_M_do_sanitize(); 00854 } 00855 00856 /** 00857 * @brief Clear the bitset. 00858 */ 00859 void 00860 clear() 00861 { 00862 this->_M_clear(); 00863 this->_M_Nb = 0; 00864 } 00865 00866 /** 00867 * @brief Push a bit onto the high end of the bitset. 00868 */ 00869 void 00870 push_back(bool __bit) 00871 { 00872 if (size_t __offset = this->size() % bits_per_block == 0) 00873 this->_M_do_append_block(block_type(0), this->_M_Nb); 00874 ++this->_M_Nb; 00875 this->_M_unchecked_set(this->_M_Nb, __bit); 00876 } 00877 00878 /** 00879 * @brief Append a block. 00880 */ 00881 void 00882 append(block_type __block) 00883 { 00884 this->_M_do_append_block(__block, this->_M_Nb); 00885 this->_M_Nb += bits_per_block; 00886 } 00887 00888 /** 00889 * @brief 00890 */ 00891 void 00892 append(initializer_list<block_type> __il) 00893 { this->append(__il.begin(), __il.end()); } 00894 00895 /** 00896 * @brief Append an iterator range of blocks. 00897 */ 00898 template <typename _BlockInputIterator> 00899 void 00900 append(_BlockInputIterator __first, _BlockInputIterator __last) 00901 { 00902 for (; __first != __last; ++__first) 00903 this->append(*__first); 00904 } 00905 00906 // 23.3.5.2 dynamic_bitset operations: 00907 //@{ 00908 /** 00909 * @brief Operations on dynamic_bitsets. 00910 * @param __rhs A same-sized dynamic_bitset. 00911 * 00912 * These should be self-explanatory. 00913 */ 00914 dynamic_bitset<_WordT, _Alloc>& 00915 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00916 { 00917 this->_M_do_and(__rhs); 00918 return *this; 00919 } 00920 00921 dynamic_bitset<_WordT, _Alloc>& 00922 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 00923 { 00924 this->_M_do_and(std::move(__rhs)); 00925 return *this; 00926 } 00927 00928 dynamic_bitset<_WordT, _Alloc>& 00929 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00930 { 00931 this->_M_do_or(__rhs); 00932 return *this; 00933 } 00934 00935 dynamic_bitset<_WordT, _Alloc>& 00936 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00937 { 00938 this->_M_do_xor(__rhs); 00939 return *this; 00940 } 00941 00942 dynamic_bitset<_WordT, _Alloc>& 00943 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00944 { 00945 this->_M_do_dif(__rhs); 00946 return *this; 00947 } 00948 //@} 00949 00950 //@{ 00951 /** 00952 * @brief Operations on dynamic_bitsets. 00953 * @param __pos The number of places to shift. 00954 * 00955 * These should be self-explanatory. 00956 */ 00957 dynamic_bitset<_WordT, _Alloc>& 00958 operator<<=(size_type __pos) 00959 { 00960 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00961 { 00962 this->_M_do_left_shift(__pos); 00963 this->_M_do_sanitize(); 00964 } 00965 else 00966 this->_M_do_reset(); 00967 return *this; 00968 } 00969 00970 dynamic_bitset<_WordT, _Alloc>& 00971 operator>>=(size_type __pos) 00972 { 00973 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00974 { 00975 this->_M_do_right_shift(__pos); 00976 this->_M_do_sanitize(); 00977 } 00978 else 00979 this->_M_do_reset(); 00980 return *this; 00981 } 00982 //@} 00983 00984 // Set, reset, and flip. 00985 /** 00986 * @brief Sets every bit to true. 00987 */ 00988 dynamic_bitset<_WordT, _Alloc>& 00989 set() 00990 { 00991 this->_M_do_set(); 00992 this->_M_do_sanitize(); 00993 return *this; 00994 } 00995 00996 /** 00997 * @brief Sets a given bit to a particular value. 00998 * @param __pos The index of the bit. 00999 * @param __val Either true or false, defaults to true. 01000 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01001 */ 01002 dynamic_bitset<_WordT, _Alloc>& 01003 set(size_type __pos, bool __val = true) 01004 { 01005 if (__pos >= _M_Nb) 01006 __throw_out_of_range(__N("dynamic_bitset::set")); 01007 return this->_M_unchecked_set(__pos, __val); 01008 } 01009 01010 /** 01011 * @brief Sets every bit to false. 01012 */ 01013 dynamic_bitset<_WordT, _Alloc>& 01014 reset() 01015 { 01016 this->_M_do_reset(); 01017 return *this; 01018 } 01019 01020 /** 01021 * @brief Sets a given bit to false. 01022 * @param __pos The index of the bit. 01023 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01024 * 01025 * Same as writing @c set(__pos, false). 01026 */ 01027 dynamic_bitset<_WordT, _Alloc>& 01028 reset(size_type __pos) 01029 { 01030 if (__pos >= _M_Nb) 01031 __throw_out_of_range(__N("dynamic_bitset::reset")); 01032 return this->_M_unchecked_reset(__pos); 01033 } 01034 01035 /** 01036 * @brief Toggles every bit to its opposite value. 01037 */ 01038 dynamic_bitset<_WordT, _Alloc>& 01039 flip() 01040 { 01041 this->_M_do_flip(); 01042 this->_M_do_sanitize(); 01043 return *this; 01044 } 01045 01046 /** 01047 * @brief Toggles a given bit to its opposite value. 01048 * @param __pos The index of the bit. 01049 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01050 */ 01051 dynamic_bitset<_WordT, _Alloc>& 01052 flip(size_type __pos) 01053 { 01054 if (__pos >= _M_Nb) 01055 __throw_out_of_range(__N("dynamic_bitset::flip")); 01056 return this->_M_unchecked_flip(__pos); 01057 } 01058 01059 /// See the no-argument flip(). 01060 dynamic_bitset<_WordT, _Alloc> 01061 operator~() const 01062 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 01063 01064 //@{ 01065 /** 01066 * @brief Array-indexing support. 01067 * @param __pos Index into the %dynamic_bitset. 01068 * @return A bool for a 'const %dynamic_bitset'. For non-const 01069 * bitsets, an instance of the reference proxy class. 01070 * @note These operators do no range checking and throw no 01071 * exceptions, as required by DR 11 to the standard. 01072 */ 01073 reference 01074 operator[](size_type __pos) 01075 { return reference(*this,__pos); } 01076 01077 const_reference 01078 operator[](size_type __pos) const 01079 { return _M_unchecked_test(__pos); } 01080 //@} 01081 01082 /** 01083 * @brief Returns a numerical interpretation of the %dynamic_bitset. 01084 * @return The integral equivalent of the bits. 01085 * @throw std::overflow_error If there are too many bits to be 01086 * represented in an @c unsigned @c long. 01087 */ 01088 unsigned long 01089 to_ulong() const 01090 { return this->_M_do_to_ulong(); } 01091 01092 /** 01093 * @brief Returns a numerical interpretation of the %dynamic_bitset. 01094 * @return The integral equivalent of the bits. 01095 * @throw std::overflow_error If there are too many bits to be 01096 * represented in an @c unsigned @c long. 01097 */ 01098 unsigned long long 01099 to_ullong() const 01100 { return this->_M_do_to_ullong(); } 01101 01102 /** 01103 * @brief Returns a character interpretation of the %dynamic_bitset. 01104 * @return The string equivalent of the bits. 01105 * 01106 * Note the ordering of the bits: decreasing character positions 01107 * correspond to increasing bit positions (see the main class notes for 01108 * an example). 01109 */ 01110 template<typename _CharT = char, 01111 typename _Traits = std::char_traits<_CharT>, 01112 typename _Alloc1 = std::allocator<_CharT>> 01113 std::basic_string<_CharT, _Traits, _Alloc1> 01114 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 01115 { 01116 std::basic_string<_CharT, _Traits, _Alloc1> __result; 01117 _M_copy_to_string(__result, __zero, __one); 01118 return __result; 01119 } 01120 01121 // Helper functions for string operations. 01122 template<typename _CharT, typename _Traits> 01123 void 01124 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 01125 _CharT, _CharT); 01126 01127 template<typename _CharT, typename _Traits, typename _Alloc1> 01128 void 01129 _M_copy_from_string(const std::basic_string<_CharT, 01130 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 01131 _CharT __zero = _CharT('0'), 01132 _CharT __one = _CharT('1')) 01133 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 01134 __pos, __n, __zero, __one); } 01135 01136 template<typename _CharT, typename _Traits, typename _Alloc1> 01137 void 01138 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 01139 _CharT __zero = _CharT('0'), 01140 _CharT __one = _CharT('1')) const; 01141 01142 /// Returns the number of bits which are set. 01143 size_type 01144 count() const 01145 { return this->_M_do_count(); } 01146 01147 /// Returns the total number of bits. 01148 size_type 01149 size() const 01150 { return this->_M_Nb; } 01151 01152 /// Returns the total number of blocks. 01153 size_type num_blocks() const 01154 { return this->_M_size(); } 01155 01156 /// Returns true if the dynamic_bitset is empty. 01157 bool 01158 empty() const 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() const 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 */