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 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 00597 * @throw std::invalid_argument If a character appears in the string 00598 * which is neither '0' nor '1'. 00599 */ 00600 template<typename _CharT, typename _Traits, typename _Alloc1> 00601 explicit 00602 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 00603 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00604 __pos = 0, 00605 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 00606 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 00607 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 00608 const allocator_type& __alloc = allocator_type()) 00609 : _Base(__alloc), 00610 _M_Nb(0) // Watch for npos. 00611 { 00612 if (__pos > __str.size()) 00613 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 00614 "not valid")); 00615 00616 // Watch for npos. 00617 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 00618 this->resize(this->_M_Nb); 00619 this->_M_copy_from_string(__str, __pos, __n, 00620 _CharT('0'), _CharT('1')); 00621 } 00622 00623 /** 00624 * @brief Construct from a string. 00625 * @param __str A string of '0' and '1' characters. 00626 * @param __alloc An allocator. 00627 * @throw std::invalid_argument If a character appears in the string 00628 * which is neither '0' nor '1'. 00629 */ 00630 explicit 00631 dynamic_bitset(const char* __str, 00632 const allocator_type& __alloc = allocator_type()) 00633 : _Base(__alloc) 00634 { 00635 size_t __len = 0; 00636 if (__str) 00637 while (__str[__len] != '\0') 00638 ++__len; 00639 this->resize(__len); 00640 this->_M_copy_from_ptr<char,std::char_traits<char>> 00641 (__str, __len, 0, __len, '0', '1'); 00642 } 00643 00644 /** 00645 * @brief Copy constructor. 00646 */ 00647 dynamic_bitset(const dynamic_bitset& __b) 00648 : _Base(__b), _M_Nb(__b.size()) 00649 { } 00650 00651 /** 00652 * @brief Move constructor. 00653 */ 00654 dynamic_bitset(dynamic_bitset&& __b) 00655 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size()) 00656 { } 00657 00658 /** 00659 * @brief Swap with another bitset. 00660 */ 00661 void 00662 swap(dynamic_bitset& __b) 00663 { 00664 this->_M_swap(__b); 00665 std::swap(this->_M_Nb, __b._M_Nb); 00666 } 00667 00668 /** 00669 * @brief Assignment. 00670 */ 00671 dynamic_bitset& 00672 operator=(const dynamic_bitset& __b) 00673 { 00674 if (&__b != this) 00675 { 00676 this->_M_assign(__b); 00677 this->_M_Nb = __b._M_Nb; 00678 } 00679 } 00680 00681 /** 00682 * @brief Move assignment. 00683 */ 00684 dynamic_bitset& 00685 operator=(dynamic_bitset&& __b) 00686 { 00687 this->swap(__b); 00688 return *this; 00689 } 00690 00691 /** 00692 * @brief Return the allocator for the bitset. 00693 */ 00694 allocator_type 00695 get_allocator() const 00696 { return this->_M_get_allocator(); } 00697 00698 /** 00699 * @brief Resize the bitset. 00700 */ 00701 void 00702 resize(size_type __nbits, bool __value = false) 00703 { 00704 if (__value) 00705 this->_M_do_fill(); 00706 this->_M_resize(__nbits, __value); 00707 this->_M_Nb = __nbits; 00708 this->_M_do_sanitize(); 00709 } 00710 00711 /** 00712 * @brief Clear the bitset. 00713 */ 00714 void 00715 clear() 00716 { 00717 this->_M_clear(); 00718 this->_M_Nb = 0; 00719 } 00720 00721 /** 00722 * @brief Push a bit onto the high end of the bitset. 00723 */ 00724 void 00725 push_back(bool __bit) 00726 { 00727 if (size_t __offset = this->size() % bits_per_block == 0) 00728 this->_M_do_append_block(block_type(0), this->_M_Nb); 00729 ++this->_M_Nb; 00730 this->_M_unchecked_set(this->_M_Nb, __bit); 00731 } 00732 00733 /** 00734 * @brief Append a block. 00735 */ 00736 void 00737 append(block_type __block) 00738 { 00739 this->_M_do_append_block(__block, this->_M_Nb); 00740 this->_M_Nb += bits_per_block; 00741 } 00742 00743 /** 00744 * @brief 00745 */ 00746 void 00747 append(initializer_list<block_type> __il) 00748 { this->append(__il.begin(), __il.end()); } 00749 00750 /** 00751 * @brief Append an iterator range of blocks. 00752 */ 00753 template <typename _BlockInputIterator> 00754 void 00755 append(_BlockInputIterator __first, _BlockInputIterator __last) 00756 { 00757 for (; __first != __last; ++__first) 00758 this->append(*__first); 00759 } 00760 00761 // 23.3.5.2 dynamic_bitset operations: 00762 //@{ 00763 /** 00764 * @brief Operations on dynamic_bitsets. 00765 * @param __rhs A same-sized dynamic_bitset. 00766 * 00767 * These should be self-explanatory. 00768 */ 00769 dynamic_bitset<_WordT, _Alloc>& 00770 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00771 { 00772 this->_M_do_and(__rhs); 00773 return *this; 00774 } 00775 00776 dynamic_bitset<_WordT, _Alloc>& 00777 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs) 00778 { 00779 this->_M_do_and(std::move(__rhs)); 00780 return *this; 00781 } 00782 00783 dynamic_bitset<_WordT, _Alloc>& 00784 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00785 { 00786 this->_M_do_or(__rhs); 00787 return *this; 00788 } 00789 00790 dynamic_bitset<_WordT, _Alloc>& 00791 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00792 { 00793 this->_M_do_xor(__rhs); 00794 return *this; 00795 } 00796 00797 dynamic_bitset<_WordT, _Alloc>& 00798 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs) 00799 { 00800 this->_M_do_dif(__rhs); 00801 return *this; 00802 } 00803 //@} 00804 00805 //@{ 00806 /** 00807 * @brief Operations on dynamic_bitsets. 00808 * @param __pos The number of places to shift. 00809 * 00810 * These should be self-explanatory. 00811 */ 00812 dynamic_bitset<_WordT, _Alloc>& 00813 operator<<=(size_type __pos) 00814 { 00815 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00816 { 00817 this->_M_do_left_shift(__pos); 00818 this->_M_do_sanitize(); 00819 } 00820 else 00821 this->_M_do_reset(); 00822 return *this; 00823 } 00824 00825 dynamic_bitset<_WordT, _Alloc>& 00826 operator>>=(size_type __pos) 00827 { 00828 if (__builtin_expect(__pos < this->_M_Nb, 1)) 00829 { 00830 this->_M_do_right_shift(__pos); 00831 this->_M_do_sanitize(); 00832 } 00833 else 00834 this->_M_do_reset(); 00835 return *this; 00836 } 00837 //@} 00838 00839 // Set, reset, and flip. 00840 /** 00841 * @brief Sets every bit to true. 00842 */ 00843 dynamic_bitset<_WordT, _Alloc>& 00844 set() 00845 { 00846 this->_M_do_set(); 00847 this->_M_do_sanitize(); 00848 return *this; 00849 } 00850 00851 /** 00852 * @brief Sets a given bit to a particular value. 00853 * @param __pos The index of the bit. 00854 * @param __val Either true or false, defaults to true. 00855 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00856 */ 00857 dynamic_bitset<_WordT, _Alloc>& 00858 set(size_type __pos, bool __val = true) 00859 { 00860 if (__pos >= _M_Nb) 00861 __throw_out_of_range(__N("dynamic_bitset::set")); 00862 return this->_M_unchecked_set(__pos, __val); 00863 } 00864 00865 /** 00866 * @brief Sets every bit to false. 00867 */ 00868 dynamic_bitset<_WordT, _Alloc>& 00869 reset() 00870 { 00871 this->_M_do_reset(); 00872 return *this; 00873 } 00874 00875 /** 00876 * @brief Sets a given bit to false. 00877 * @param __pos The index of the bit. 00878 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00879 * 00880 * Same as writing @c set(__pos, false). 00881 */ 00882 dynamic_bitset<_WordT, _Alloc>& 00883 reset(size_type __pos) 00884 { 00885 if (__pos >= _M_Nb) 00886 __throw_out_of_range(__N("dynamic_bitset::reset")); 00887 return this->_M_unchecked_reset(__pos); 00888 } 00889 00890 /** 00891 * @brief Toggles every bit to its opposite value. 00892 */ 00893 dynamic_bitset<_WordT, _Alloc>& 00894 flip() 00895 { 00896 this->_M_do_flip(); 00897 this->_M_do_sanitize(); 00898 return *this; 00899 } 00900 00901 /** 00902 * @brief Toggles a given bit to its opposite value. 00903 * @param __pos The index of the bit. 00904 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 00905 */ 00906 dynamic_bitset<_WordT, _Alloc>& 00907 flip(size_type __pos) 00908 { 00909 if (__pos >= _M_Nb) 00910 __throw_out_of_range(__N("dynamic_bitset::flip")); 00911 return this->_M_unchecked_flip(__pos); 00912 } 00913 00914 /// See the no-argument flip(). 00915 dynamic_bitset<_WordT, _Alloc> 00916 operator~() const 00917 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 00918 00919 //@{ 00920 /** 00921 * @brief Array-indexing support. 00922 * @param __pos Index into the %dynamic_bitset. 00923 * @return A bool for a 'const %dynamic_bitset'. For non-const 00924 * bitsets, an instance of the reference proxy class. 00925 * @note These operators do no range checking and throw no 00926 * exceptions, as required by DR 11 to the standard. 00927 */ 00928 reference 00929 operator[](size_type __pos) 00930 { return reference(*this,__pos); } 00931 00932 const_reference 00933 operator[](size_type __pos) const 00934 { return _M_unchecked_test(__pos); } 00935 //@} 00936 00937 /** 00938 * @brief Returns a numerical interpretation of the %dynamic_bitset. 00939 * @return The integral equivalent of the bits. 00940 * @throw std::overflow_error If there are too many bits to be 00941 * represented in an @c unsigned @c long. 00942 */ 00943 unsigned long 00944 to_ulong() const 00945 { return this->_M_do_to_ulong(); } 00946 00947 /** 00948 * @brief Returns a numerical interpretation of the %dynamic_bitset. 00949 * @return The integral equivalent of the bits. 00950 * @throw std::overflow_error If there are too many bits to be 00951 * represented in an @c unsigned @c long. 00952 */ 00953 unsigned long long 00954 to_ullong() const 00955 { return this->_M_do_to_ullong(); } 00956 00957 /** 00958 * @brief Returns a character interpretation of the %dynamic_bitset. 00959 * @return The string equivalent of the bits. 00960 * 00961 * Note the ordering of the bits: decreasing character positions 00962 * correspond to increasing bit positions (see the main class notes for 00963 * an example). 00964 */ 00965 template<typename _CharT = char, 00966 typename _Traits = std::char_traits<_CharT>, 00967 typename _Alloc1 = std::allocator<_CharT>> 00968 std::basic_string<_CharT, _Traits, _Alloc1> 00969 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 00970 { 00971 std::basic_string<_CharT, _Traits, _Alloc1> __result; 00972 _M_copy_to_string(__result, __zero, __one); 00973 return __result; 00974 } 00975 00976 // Helper functions for string operations. 00977 template<typename _CharT, typename _Traits> 00978 void 00979 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 00980 _CharT, _CharT); 00981 00982 template<typename _CharT, typename _Traits, typename _Alloc1> 00983 void 00984 _M_copy_from_string(const std::basic_string<_CharT, 00985 _Traits, _Alloc1>& __str, size_t __pos, size_t __n, 00986 _CharT __zero = _CharT('0'), 00987 _CharT __one = _CharT('1')) 00988 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(), 00989 __pos, __n, __zero, __one); } 00990 00991 template<typename _CharT, typename _Traits, typename _Alloc1> 00992 void 00993 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 00994 _CharT __zero = _CharT('0'), 00995 _CharT __one = _CharT('1')) const; 00996 00997 /// Returns the number of bits which are set. 00998 size_type 00999 count() const noexcept 01000 { return this->_M_do_count(); } 01001 01002 /// Returns the total number of bits. 01003 size_type 01004 size() const noexcept 01005 { return this->_M_Nb; } 01006 01007 /// Returns the total number of blocks. 01008 size_type 01009 num_blocks() const noexcept 01010 { return this->_M_size(); } 01011 01012 /// Returns true if the dynamic_bitset is empty. 01013 bool 01014 empty() const noexcept 01015 { return (this->_M_Nb == 0); } 01016 01017 /// Returns the maximum size of a dynamic_bitset object having the same 01018 /// type as *this. 01019 /// The real answer is max() * bits_per_block but is likely to overflow. 01020 constexpr size_type 01021 max_size() noexcept 01022 { return std::numeric_limits<block_type>::max(); } 01023 01024 /** 01025 * @brief Tests the value of a bit. 01026 * @param __pos The index of a bit. 01027 * @return The value at @a __pos. 01028 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 01029 */ 01030 bool 01031 test(size_type __pos) const 01032 { 01033 if (__pos >= _M_Nb) 01034 __throw_out_of_range(__N("dynamic_bitset::test")); 01035 return _M_unchecked_test(__pos); 01036 } 01037 01038 /** 01039 * @brief Tests whether all the bits are on. 01040 * @return True if all the bits are set. 01041 */ 01042 bool 01043 all() const 01044 { return this->_M_are_all_aux() == _M_Nb; } 01045 01046 /** 01047 * @brief Tests whether any of the bits are on. 01048 * @return True if at least one bit is set. 01049 */ 01050 bool 01051 any() const 01052 { return this->_M_is_any(); } 01053 01054 /** 01055 * @brief Tests whether any of the bits are on. 01056 * @return True if none of the bits are set. 01057 */ 01058 bool 01059 none() const 01060 { return !this->_M_is_any(); } 01061 01062 //@{ 01063 /// Self-explanatory. 01064 dynamic_bitset<_WordT, _Alloc> 01065 operator<<(size_type __pos) const 01066 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; } 01067 01068 dynamic_bitset<_WordT, _Alloc> 01069 operator>>(size_type __pos) const 01070 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; } 01071 //@} 01072 01073 /** 01074 * @brief Finds the index of the first "on" bit. 01075 * @return The index of the first bit set, or size() if not found. 01076 * @sa find_next 01077 */ 01078 size_type 01079 find_first() const 01080 { return this->_M_do_find_first(this->_M_Nb); } 01081 01082 /** 01083 * @brief Finds the index of the next "on" bit after prev. 01084 * @return The index of the next bit set, or size() if not found. 01085 * @param __prev Where to start searching. 01086 * @sa find_first 01087 */ 01088 size_type 01089 find_next(size_t __prev) const 01090 { return this->_M_do_find_next(__prev, this->_M_Nb); } 01091 01092 bool 01093 is_subset_of(const dynamic_bitset& __b) const 01094 { return this->_M_is_subset_of(__b); } 01095 01096 bool 01097 is_proper_subset_of(const dynamic_bitset& __b) const 01098 { return this->_M_is_proper_subset_of(__b); } 01099 01100 friend bool 01101 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01102 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01103 { return __lhs._M_is_equal(__rhs); } 01104 01105 friend bool 01106 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01107 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01108 { return __lhs._M_is_less(__rhs); } 01109 }; 01110 01111 template<typename _WordT, typename _Alloc> 01112 template<typename _CharT, typename _Traits, typename _Alloc1> 01113 inline void 01114 dynamic_bitset<_WordT, _Alloc>:: 01115 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 01116 _CharT __zero, _CharT __one) const 01117 { 01118 __str.assign(_M_Nb, __zero); 01119 for (size_t __i = _M_Nb; __i > 0; --__i) 01120 if (_M_unchecked_test(__i - 1)) 01121 _Traits::assign(__str[_M_Nb - __i], __one); 01122 } 01123 01124 01125 //@{ 01126 /// These comparisons for equality/inequality are, well, @e bitwise. 01127 01128 template<typename _WordT, typename _Alloc> 01129 inline bool 01130 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01131 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01132 { return !(__lhs == __rhs); } 01133 01134 template<typename _WordT, typename _Alloc> 01135 inline bool 01136 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01137 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01138 { return !(__lhs > __rhs); } 01139 01140 template<typename _WordT, typename _Alloc> 01141 inline bool 01142 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01143 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01144 { return __rhs < __lhs; } 01145 01146 template<typename _WordT, typename _Alloc> 01147 inline bool 01148 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 01149 const dynamic_bitset<_WordT, _Alloc>& __rhs) 01150 { return !(__lhs < __rhs); } 01151 //@} 01152 01153 // 23.3.5.3 bitset operations: 01154 //@{ 01155 /** 01156 * @brief Global bitwise operations on bitsets. 01157 * @param __x A bitset. 01158 * @param __y A bitset of the same size as @a __x. 01159 * @return A new bitset. 01160 * 01161 * These should be self-explanatory. 01162 */ 01163 template<typename _WordT, typename _Alloc> 01164 inline dynamic_bitset<_WordT, _Alloc> 01165 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 01166 const dynamic_bitset<_WordT, _Alloc>& __y) 01167 { 01168 dynamic_bitset<_WordT, _Alloc> __result(__x); 01169 __result &= __y; 01170 return __result; 01171 } 01172 01173 template<typename _WordT, typename _Alloc> 01174 inline dynamic_bitset<_WordT, _Alloc> 01175 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 01176 const dynamic_bitset<_WordT, _Alloc>& __y) 01177 { 01178 dynamic_bitset<_WordT, _Alloc> __result(__x); 01179 __result |= __y; 01180 return __result; 01181 } 01182 01183 template <typename _WordT, typename _Alloc> 01184 inline dynamic_bitset<_WordT, _Alloc> 01185 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 01186 const dynamic_bitset<_WordT, _Alloc>& __y) 01187 { 01188 dynamic_bitset<_WordT, _Alloc> __result(__x); 01189 __result ^= __y; 01190 return __result; 01191 } 01192 01193 template <typename _WordT, typename _Alloc> 01194 inline dynamic_bitset<_WordT, _Alloc> 01195 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 01196 const dynamic_bitset<_WordT, _Alloc>& __y) 01197 { 01198 dynamic_bitset<_WordT, _Alloc> __result(__x); 01199 __result -= __y; 01200 return __result; 01201 } 01202 //@} 01203 01204 /// Stream output operator for dynamic_bitset. 01205 template <typename _CharT, typename _Traits, 01206 typename _WordT, typename _Alloc> 01207 inline std::basic_ostream<_CharT, _Traits>& 01208 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01209 const dynamic_bitset<_WordT, _Alloc>& __x) 01210 { 01211 std::basic_string<_CharT, _Traits> __tmp; 01212 01213 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 01214 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01215 return __os << __tmp; 01216 } 01217 /** 01218 * @} 01219 */ 01220 01221 _GLIBCXX_END_NAMESPACE_VERSION 01222 } // tr2 01223 } // std 01224 01225 #include <tr2/dynamic_bitset.tcc> 01226 01227 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */