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