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