libstdc++
|
00001 // TR2 <dynamic_bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2009-2019 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00046 00047 namespace tr2 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 (this->size() % bits_per_block == 0) 00731 this->_M_do_append_block(block_type(__bit), this->_M_Nb); 00732 else 00733 this->_M_unchecked_set(this->_M_Nb, __bit); 00734 ++this->_M_Nb; 00735 } 00736 00737 /** 00738 * @brief Append a block. 00739 */ 00740 void 00741 append(block_type __block) 00742 { 00743 this->_M_do_append_block(__block, this->_M_Nb); 00744 this->_M_Nb += bits_per_block; 00745 } 00746 00747 /** 00748 * @brief 00749 */ 00750 void 00751 append(initializer_list<block_type> __il) 00752 { this->append(__il.begin(), __il.end()); } 00753 00754 /** 00755 * @brief Append an iterator range of blocks. 00756 */ 00757 template <typename _BlockInputIterator> 00758 void 00759 append(_BlockInputIterator __first, _BlockInputIterator __last) 00760 { 00761 for (; __first != __last; ++__first) 00762 this->append(*__first); 00763 } 00764 00765 // 23.3.5.2 dynamic_bitset operations: 00766 //@{ 00767 /** 00768 * @brief Operations on dynamic_bitsets. 00769 * @param __rhs A same-sized dynamic_bitset. 00770 * 00771 * These should be self-explanatory. 00772 */ 00773 dynamic_bitset<_WordT, _Alloc>& 00774 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00775 { 00776 this->_M_do_and(__rhs); 00777 return *this; 00778 } 00779 00780 dynamic_bitset<_WordT, _Alloc>& 00781 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 00782 { 00783 this->_M_do_and(std::move(__rhs)); 00784 return *this; 00785 } 00786 00787 dynamic_bitset<_WordT, _Alloc>& 00788 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00789 { 00790 this->_M_do_or(__rhs); 00791 return *this; 00792 } 00793 00794 dynamic_bitset<_WordT, _Alloc>& 00795 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00796 { 00797 this->_M_do_xor(__rhs); 00798 return *this; 00799 } 00800 00801 dynamic_bitset<_WordT, _Alloc>& 00802 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00803 { 00804 this->_M_do_dif(__rhs); 00805 return *this; 00806 } 00807 //@} 00808 00809 //@{ 00810 /** 00811 * @brief Operations on dynamic_bitsets. 00812 * @param __pos The number of places to shift. 00813 * 00814 * These should be self-explanatory. 00815 */ 00816 dynamic_bitset<_WordT, _Alloc>& 00817 operator<<=(size_type __pos) 00818 { 00819 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00820 { 00821 this->_M_do_left_shift(__pos); 00822 this->_M_do_sanitize(); 00823 } 00824 else 00825 this->_M_do_reset(); 00826 return *this; 00827 } 00828 00829 dynamic_bitset<_WordT, _Alloc>& 00830 operator>>=(size_type __pos) 00831 { 00832 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00833 { 00834 this->_M_do_right_shift(__pos); 00835 this->_M_do_sanitize(); 00836 } 00837 else 00838 this->_M_do_reset(); 00839 return *this; 00840 } 00841 //@} 00842 00843 // Set, reset, and flip. 00844 /** 00845 * @brief Sets every bit to true. 00846 */ 00847 dynamic_bitset<_WordT, _Alloc>& 00848 set() 00849 { 00850 this->_M_do_set(); 00851 this->_M_do_sanitize(); 00852 return *this; 00853 } 00854 00855 /** 00856 * @brief Sets a given bit to a particular value. 00857 * @param __pos The index of the bit. 00858 * @param __val Either true or false, defaults to true. 00859 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00860 */ 00861 dynamic_bitset<_WordT, _Alloc>& 00862 set(size_type __pos, bool __val = true) 00863 { 00864 if (__pos >= _M_Nb) 00865 __throw_out_of_range(__N("dynamic_bitset::set")); 00866 return this->_M_unchecked_set(__pos, __val); 00867 } 00868 00869 /** 00870 * @brief Sets every bit to false. 00871 */ 00872 dynamic_bitset<_WordT, _Alloc>& 00873 reset() 00874 { 00875 this->_M_do_reset(); 00876 return *this; 00877 } 00878 00879 /** 00880 * @brief Sets a given bit to false. 00881 * @param __pos The index of the bit. 00882 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00883 * 00884 * Same as writing @c set(__pos, false). 00885 */ 00886 dynamic_bitset<_WordT, _Alloc>& 00887 reset(size_type __pos) 00888 { 00889 if (__pos >= _M_Nb) 00890 __throw_out_of_range(__N("dynamic_bitset::reset")); 00891 return this->_M_unchecked_reset(__pos); 00892 } 00893 00894 /** 00895 * @brief Toggles every bit to its opposite value. 00896 */ 00897 dynamic_bitset<_WordT, _Alloc>& 00898 flip() 00899 { 00900 this->_M_do_flip(); 00901 this->_M_do_sanitize(); 00902 return *this; 00903 } 00904 00905 /** 00906 * @brief Toggles a given bit to its opposite value. 00907 * @param __pos The index of the bit. 00908 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00909 */ 00910 dynamic_bitset<_WordT, _Alloc>& 00911 flip(size_type __pos) 00912 { 00913 if (__pos >= _M_Nb) 00914 __throw_out_of_range(__N("dynamic_bitset::flip")); 00915 return this->_M_unchecked_flip(__pos); 00916 } 00917 00918 /// See the no-argument flip(). 00919 dynamic_bitset<_WordT, _Alloc> 00920 operator~() const 00921 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 00922 00923 //@{ 00924 /** 00925 * @brief Array-indexing support. 00926 * @param __pos Index into the %dynamic_bitset. 00927 * @return A bool for a 'const %dynamic_bitset'. For non-const 00928 * bitsets, an instance of the reference proxy class. 00929 * @note These operators do no range checking and throw no 00930 * exceptions, as required by DR 11 to the standard. 00931 */ 00932 reference 00933 operator[](size_type __pos) 00934 { return reference(*this,__pos); } 00935 00936 const_reference 00937 operator[](size_type __pos) const 00938 { return _M_unchecked_test(__pos); } 00939 //@} 00940 00941 /** 00942 * @brief Returns a numerical interpretation of the %dynamic_bitset. 00943 * @return The integral equivalent of the bits. 00944 * @throw std::overflow_error If there are too many bits to be 00945 * represented in an @c unsigned @c long. 00946 */ 00947 unsigned long 00948 to_ulong() const 00949 { return this->_M_do_to_ulong(); } 00950 00951 /** 00952 * @brief Returns a numerical interpretation of the %dynamic_bitset. 00953 * @return The integral equivalent of the bits. 00954 * @throw std::overflow_error If there are too many bits to be 00955 * represented in an @c unsigned @c long. 00956 */ 00957 unsigned long long 00958 to_ullong() const 00959 { return this->_M_do_to_ullong(); } 00960 00961 /** 00962 * @brief Returns a character interpretation of the %dynamic_bitset. 00963 * @return The string equivalent of the bits. 00964 * 00965 * Note the ordering of the bits: decreasing character positions 00966 * correspond to increasing bit positions (see the main class notes for 00967 * an example). 00968 */ 00969 template<typename _CharT = char, 00970 typename _Traits = std::char_traits<_CharT>, 00971 typename _Alloc1 = std::allocator<_CharT>> 00972 std::basic_string<_CharT, _Traits, _Alloc1> 00973 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 00974 { 00975 std::basic_string<_CharT, _Traits, _Alloc1> __result; 00976 _M_copy_to_string(__result, __zero, __one); 00977 return __result; 00978 } 00979 00980 // Helper functions for string operations. 00981 template<typename _CharT, typename _Traits> 00982 void 00983 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 00984 _CharT, _CharT); 00985 00986 template<typename _CharT, typename _Traits, typename _Alloc1> 00987 void 00988 _M_copy_from_string(const std::basic_string<_CharT, 00989 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 00990 _CharT __zero = _CharT('0'), 00991 _CharT __one = _CharT('1')) 00992 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 00993 __pos, __n, __zero, __one); } 00994 00995 template<typename _CharT, typename _Traits, typename _Alloc1> 00996 void 00997 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 00998 _CharT __zero = _CharT('0'), 00999 _CharT __one = _CharT('1')) const; 01000 01001 /// Returns the number of bits which are set. 01002 size_type 01003 count() const noexcept 01004 { return this->_M_do_count(); } 01005 01006 /// Returns the total number of bits. 01007 size_type 01008 size() const noexcept 01009 { return this->_M_Nb; } 01010 01011 /// Returns the total number of blocks. 01012 size_type 01013 num_blocks() const noexcept 01014 { return this->_M_size(); } 01015 01016 /// Returns true if the dynamic_bitset is empty. 01017 _GLIBCXX_NODISCARD bool 01018 empty() const noexcept 01019 { return (this->_M_Nb == 0); } 01020 01021 /// Returns the maximum size of a dynamic_bitset object having the same 01022 /// type as *this. 01023 /// The real answer is max() * bits_per_block but is likely to overflow. 01024 constexpr size_type 01025 max_size() noexcept 01026 { return std::numeric_limits<block_type>::max(); } 01027 01028 /** 01029 * @brief Tests the value of a bit. 01030 * @param __pos The index of a bit. 01031 * @return The value at @a __pos. 01032 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01033 */ 01034 bool 01035 test(size_type __pos) const 01036 { 01037 if (__pos >= _M_Nb) 01038 __throw_out_of_range(__N("dynamic_bitset::test")); 01039 return _M_unchecked_test(__pos); 01040 } 01041 01042 /** 01043 * @brief Tests whether all the bits are on. 01044 * @return True if all the bits are set. 01045 */ 01046 bool 01047 all() const 01048 { return this->_M_are_all_aux() == _M_Nb; } 01049 01050 /** 01051 * @brief Tests whether any of the bits are on. 01052 * @return True if at least one bit is set. 01053 */ 01054 bool 01055 any() const 01056 { return this->_M_is_any(); } 01057 01058 /** 01059 * @brief Tests whether any of the bits are on. 01060 * @return True if none of the bits are set. 01061 */ 01062 bool 01063 none() const 01064 { return !this->_M_is_any(); } 01065 01066 //@{ 01067 /// Self-explanatory. 01068 dynamic_bitset<_WordT, _Alloc> 01069 operator<<(size_type __pos) const 01070 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; } 01071 01072 dynamic_bitset<_WordT, _Alloc> 01073 operator>>(size_type __pos) const 01074 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; } 01075 //@} 01076 01077 /** 01078 * @brief Finds the index of the first "on" bit. 01079 * @return The index of the first bit set, or size() if not found. 01080 * @sa find_next 01081 */ 01082 size_type 01083 find_first() const 01084 { return this->_M_do_find_first(this->_M_Nb); } 01085 01086 /** 01087 * @brief Finds the index of the next "on" bit after prev. 01088 * @return The index of the next bit set, or size() if not found. 01089 * @param __prev Where to start searching. 01090 * @sa find_first 01091 */ 01092 size_type 01093 find_next(size_t __prev) const 01094 { return this->_M_do_find_next(__prev, this->_M_Nb); } 01095 01096 bool 01097 is_subset_of(const dynamic_bitset& __b) const 01098 { return this->_M_is_subset_of(__b); } 01099 01100 bool 01101 is_proper_subset_of(const dynamic_bitset& __b) const 01102 { return this->_M_is_proper_subset_of(__b); } 01103 01104 friend bool 01105 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01106 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01107 { return __lhs._M_is_equal(__rhs); } 01108 01109 friend bool 01110 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01111 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01112 { return __lhs._M_is_less(__rhs); } 01113 }; 01114 01115 template<typename _WordT, typename _Alloc> 01116 template<typename _CharT, typename _Traits, typename _Alloc1> 01117 inline void 01118 dynamic_bitset<_WordT, _Alloc>:: 01119 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 01120 _CharT __zero, _CharT __one) const 01121 { 01122 __str.assign(_M_Nb, __zero); 01123 for (size_t __i = _M_Nb; __i > 0; --__i) 01124 if (_M_unchecked_test(__i - 1)) 01125 _Traits::assign(__str[_M_Nb - __i], __one); 01126 } 01127 01128 01129 //@{ 01130 /// These comparisons for equality/inequality are, well, @e bitwise. 01131 01132 template<typename _WordT, typename _Alloc> 01133 inline bool 01134 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01135 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01136 { return !(__lhs == __rhs); } 01137 01138 template<typename _WordT, typename _Alloc> 01139 inline bool 01140 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01141 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01142 { return !(__lhs > __rhs); } 01143 01144 template<typename _WordT, typename _Alloc> 01145 inline bool 01146 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01147 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01148 { return __rhs < __lhs; } 01149 01150 template<typename _WordT, typename _Alloc> 01151 inline bool 01152 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01153 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01154 { return !(__lhs < __rhs); } 01155 //@} 01156 01157 // 23.3.5.3 bitset operations: 01158 //@{ 01159 /** 01160 * @brief Global bitwise operations on bitsets. 01161 * @param __x A bitset. 01162 * @param __y A bitset of the same size as @a __x. 01163 * @return A new bitset. 01164 * 01165 * These should be self-explanatory. 01166 */ 01167 template<typename _WordT, typename _Alloc> 01168 inline dynamic_bitset<_WordT, _Alloc> 01169 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 01170 const dynamic_bitset<_WordT, _Alloc>& __y) 01171 { 01172 dynamic_bitset<_WordT, _Alloc> __result(__x); 01173 __result &= __y; 01174 return __result; 01175 } 01176 01177 template<typename _WordT, typename _Alloc> 01178 inline dynamic_bitset<_WordT, _Alloc> 01179 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 01180 const dynamic_bitset<_WordT, _Alloc>& __y) 01181 { 01182 dynamic_bitset<_WordT, _Alloc> __result(__x); 01183 __result |= __y; 01184 return __result; 01185 } 01186 01187 template <typename _WordT, typename _Alloc> 01188 inline dynamic_bitset<_WordT, _Alloc> 01189 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 01190 const dynamic_bitset<_WordT, _Alloc>& __y) 01191 { 01192 dynamic_bitset<_WordT, _Alloc> __result(__x); 01193 __result ^= __y; 01194 return __result; 01195 } 01196 01197 template <typename _WordT, typename _Alloc> 01198 inline dynamic_bitset<_WordT, _Alloc> 01199 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 01200 const dynamic_bitset<_WordT, _Alloc>& __y) 01201 { 01202 dynamic_bitset<_WordT, _Alloc> __result(__x); 01203 __result -= __y; 01204 return __result; 01205 } 01206 //@} 01207 01208 /// Stream output operator for dynamic_bitset. 01209 template <typename _CharT, typename _Traits, 01210 typename _WordT, typename _Alloc> 01211 inline std::basic_ostream<_CharT, _Traits>& 01212 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01213 const dynamic_bitset<_WordT, _Alloc>& __x) 01214 { 01215 std::basic_string<_CharT, _Traits> __tmp; 01216 01217 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 01218 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01219 return __os << __tmp; 01220 } 01221 /** 01222 * @} 01223 */ 01224 } // tr2 01225 01226 _GLIBCXX_END_NAMESPACE_VERSION 01227 } // std 01228 01229 #include <tr2/dynamic_bitset.tcc> 01230 01231 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */