libstdc++
|
00001 // <bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /* 00027 * Copyright (c) 1998 00028 * Silicon Graphics Computer Systems, Inc. 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Silicon Graphics makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 */ 00038 00039 /** @file include/bitset 00040 * This is a Standard C++ Library header. 00041 */ 00042 00043 #ifndef _GLIBCXX_BITSET 00044 #define _GLIBCXX_BITSET 1 00045 00046 #pragma GCC system_header 00047 00048 #include <cstddef> // For size_t 00049 #include <string> 00050 #include <bits/functexcept.h> // For invalid_argument, out_of_range, 00051 // overflow_error 00052 #include <iosfwd> 00053 #include <cxxabi-forced.h> 00054 00055 #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * sizeof(unsigned long)) 00056 #define _GLIBCXX_BITSET_WORDS(__n) \ 00057 ((__n) < 1 ? 0 : ((__n) + _GLIBCXX_BITSET_BITS_PER_WORD - 1) \ 00058 / _GLIBCXX_BITSET_BITS_PER_WORD) 00059 00060 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D) 00061 00062 /** 00063 * Base class, general case. It is a class invariant that _Nw will be 00064 * nonnegative. 00065 * 00066 * See documentation for bitset. 00067 */ 00068 template<size_t _Nw> 00069 struct _Base_bitset 00070 { 00071 typedef unsigned long _WordT; 00072 00073 /// 0 is the least significant word. 00074 _WordT _M_w[_Nw]; 00075 00076 _Base_bitset() 00077 { _M_do_reset(); } 00078 00079 _Base_bitset(unsigned long __val) 00080 { 00081 _M_do_reset(); 00082 _M_w[0] = __val; 00083 } 00084 00085 static size_t 00086 _S_whichword(size_t __pos ) 00087 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00088 00089 static size_t 00090 _S_whichbyte(size_t __pos ) 00091 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00092 00093 static size_t 00094 _S_whichbit(size_t __pos ) 00095 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00096 00097 static _WordT 00098 _S_maskbit(size_t __pos ) 00099 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00100 00101 _WordT& 00102 _M_getword(size_t __pos) 00103 { return _M_w[_S_whichword(__pos)]; } 00104 00105 _WordT 00106 _M_getword(size_t __pos) const 00107 { return _M_w[_S_whichword(__pos)]; } 00108 00109 _WordT& 00110 _M_hiword() 00111 { return _M_w[_Nw - 1]; } 00112 00113 _WordT 00114 _M_hiword() const 00115 { return _M_w[_Nw - 1]; } 00116 00117 void 00118 _M_do_and(const _Base_bitset<_Nw>& __x) 00119 { 00120 for (size_t __i = 0; __i < _Nw; __i++) 00121 _M_w[__i] &= __x._M_w[__i]; 00122 } 00123 00124 void 00125 _M_do_or(const _Base_bitset<_Nw>& __x) 00126 { 00127 for (size_t __i = 0; __i < _Nw; __i++) 00128 _M_w[__i] |= __x._M_w[__i]; 00129 } 00130 00131 void 00132 _M_do_xor(const _Base_bitset<_Nw>& __x) 00133 { 00134 for (size_t __i = 0; __i < _Nw; __i++) 00135 _M_w[__i] ^= __x._M_w[__i]; 00136 } 00137 00138 void 00139 _M_do_left_shift(size_t __shift); 00140 00141 void 00142 _M_do_right_shift(size_t __shift); 00143 00144 void 00145 _M_do_flip() 00146 { 00147 for (size_t __i = 0; __i < _Nw; __i++) 00148 _M_w[__i] = ~_M_w[__i]; 00149 } 00150 00151 void 00152 _M_do_set() 00153 { 00154 for (size_t __i = 0; __i < _Nw; __i++) 00155 _M_w[__i] = ~static_cast<_WordT>(0); 00156 } 00157 00158 void 00159 _M_do_reset() 00160 { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); } 00161 00162 bool 00163 _M_is_equal(const _Base_bitset<_Nw>& __x) const 00164 { 00165 for (size_t __i = 0; __i < _Nw; ++__i) 00166 if (_M_w[__i] != __x._M_w[__i]) 00167 return false; 00168 return true; 00169 } 00170 00171 size_t 00172 _M_are_all_aux() const 00173 { 00174 for (size_t __i = 0; __i < _Nw - 1; __i++) 00175 if (_M_w[__i] != ~static_cast<_WordT>(0)) 00176 return 0; 00177 return ((_Nw - 1) * _GLIBCXX_BITSET_BITS_PER_WORD 00178 + __builtin_popcountl(_M_hiword())); 00179 } 00180 00181 bool 00182 _M_is_any() const 00183 { 00184 for (size_t __i = 0; __i < _Nw; __i++) 00185 if (_M_w[__i] != static_cast<_WordT>(0)) 00186 return true; 00187 return false; 00188 } 00189 00190 size_t 00191 _M_do_count() const 00192 { 00193 size_t __result = 0; 00194 for (size_t __i = 0; __i < _Nw; __i++) 00195 __result += __builtin_popcountl(_M_w[__i]); 00196 return __result; 00197 } 00198 00199 unsigned long 00200 _M_do_to_ulong() const; 00201 00202 // find first "on" bit 00203 size_t 00204 _M_do_find_first(size_t __not_found) const; 00205 00206 // find the next "on" bit that follows "prev" 00207 size_t 00208 _M_do_find_next(size_t __prev, size_t __not_found) const; 00209 }; 00210 00211 // Definitions of non-inline functions from _Base_bitset. 00212 template<size_t _Nw> 00213 void 00214 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 00215 { 00216 if (__builtin_expect(__shift != 0, 1)) 00217 { 00218 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00219 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00220 00221 if (__offset == 0) 00222 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 00223 _M_w[__n] = _M_w[__n - __wshift]; 00224 else 00225 { 00226 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00227 - __offset); 00228 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 00229 _M_w[__n] = ((_M_w[__n - __wshift] << __offset) 00230 | (_M_w[__n - __wshift - 1] >> __sub_offset)); 00231 _M_w[__wshift] = _M_w[0] << __offset; 00232 } 00233 00234 std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 00235 } 00236 } 00237 00238 template<size_t _Nw> 00239 void 00240 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 00241 { 00242 if (__builtin_expect(__shift != 0, 1)) 00243 { 00244 const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; 00245 const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; 00246 const size_t __limit = _Nw - __wshift - 1; 00247 00248 if (__offset == 0) 00249 for (size_t __n = 0; __n <= __limit; ++__n) 00250 _M_w[__n] = _M_w[__n + __wshift]; 00251 else 00252 { 00253 const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD 00254 - __offset); 00255 for (size_t __n = 0; __n < __limit; ++__n) 00256 _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) 00257 | (_M_w[__n + __wshift + 1] << __sub_offset)); 00258 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 00259 } 00260 00261 std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 00262 } 00263 } 00264 00265 template<size_t _Nw> 00266 unsigned long 00267 _Base_bitset<_Nw>::_M_do_to_ulong() const 00268 { 00269 for (size_t __i = 1; __i < _Nw; ++__i) 00270 if (_M_w[__i]) 00271 __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong")); 00272 return _M_w[0]; 00273 } 00274 00275 template<size_t _Nw> 00276 size_t 00277 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 00278 { 00279 for (size_t __i = 0; __i < _Nw; __i++) 00280 { 00281 _WordT __thisword = _M_w[__i]; 00282 if (__thisword != static_cast<_WordT>(0)) 00283 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00284 + __builtin_ctzl(__thisword)); 00285 } 00286 // not found, so return an indication of failure. 00287 return __not_found; 00288 } 00289 00290 template<size_t _Nw> 00291 size_t 00292 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 00293 { 00294 // make bound inclusive 00295 ++__prev; 00296 00297 // check out of bounds 00298 if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) 00299 return __not_found; 00300 00301 // search first word 00302 size_t __i = _S_whichword(__prev); 00303 _WordT __thisword = _M_w[__i]; 00304 00305 // mask off bits below bound 00306 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00307 00308 if (__thisword != static_cast<_WordT>(0)) 00309 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00310 + __builtin_ctzl(__thisword)); 00311 00312 // check subsequent words 00313 __i++; 00314 for (; __i < _Nw; __i++) 00315 { 00316 __thisword = _M_w[__i]; 00317 if (__thisword != static_cast<_WordT>(0)) 00318 return (__i * _GLIBCXX_BITSET_BITS_PER_WORD 00319 + __builtin_ctzl(__thisword)); 00320 } 00321 // not found, so return an indication of failure. 00322 return __not_found; 00323 } // end _M_do_find_next 00324 00325 /** 00326 * Base class, specialization for a single word. 00327 * 00328 * See documentation for bitset. 00329 */ 00330 template<> 00331 struct _Base_bitset<1> 00332 { 00333 typedef unsigned long _WordT; 00334 _WordT _M_w; 00335 00336 _Base_bitset(void) 00337 : _M_w(0) 00338 { } 00339 00340 _Base_bitset(unsigned long __val) 00341 : _M_w(__val) 00342 { } 00343 00344 static size_t 00345 _S_whichword(size_t __pos ) 00346 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00347 00348 static size_t 00349 _S_whichbyte(size_t __pos ) 00350 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00351 00352 static size_t 00353 _S_whichbit(size_t __pos ) 00354 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00355 00356 static _WordT 00357 _S_maskbit(size_t __pos ) 00358 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00359 00360 _WordT& 00361 _M_getword(size_t) 00362 { return _M_w; } 00363 00364 _WordT 00365 _M_getword(size_t) const 00366 { return _M_w; } 00367 00368 _WordT& 00369 _M_hiword() 00370 { return _M_w; } 00371 00372 _WordT 00373 _M_hiword() const 00374 { return _M_w; } 00375 00376 void 00377 _M_do_and(const _Base_bitset<1>& __x) 00378 { _M_w &= __x._M_w; } 00379 00380 void 00381 _M_do_or(const _Base_bitset<1>& __x) 00382 { _M_w |= __x._M_w; } 00383 00384 void 00385 _M_do_xor(const _Base_bitset<1>& __x) 00386 { _M_w ^= __x._M_w; } 00387 00388 void 00389 _M_do_left_shift(size_t __shift) 00390 { _M_w <<= __shift; } 00391 00392 void 00393 _M_do_right_shift(size_t __shift) 00394 { _M_w >>= __shift; } 00395 00396 void 00397 _M_do_flip() 00398 { _M_w = ~_M_w; } 00399 00400 void 00401 _M_do_set() 00402 { _M_w = ~static_cast<_WordT>(0); } 00403 00404 void 00405 _M_do_reset() 00406 { _M_w = 0; } 00407 00408 bool 00409 _M_is_equal(const _Base_bitset<1>& __x) const 00410 { return _M_w == __x._M_w; } 00411 00412 size_t 00413 _M_are_all_aux() const 00414 { return __builtin_popcountl(_M_w); } 00415 00416 bool 00417 _M_is_any() const 00418 { return _M_w != 0; } 00419 00420 size_t 00421 _M_do_count() const 00422 { return __builtin_popcountl(_M_w); } 00423 00424 unsigned long 00425 _M_do_to_ulong() const 00426 { return _M_w; } 00427 00428 size_t 00429 _M_do_find_first(size_t __not_found) const 00430 { 00431 if (_M_w != 0) 00432 return __builtin_ctzl(_M_w); 00433 else 00434 return __not_found; 00435 } 00436 00437 // find the next "on" bit that follows "prev" 00438 size_t 00439 _M_do_find_next(size_t __prev, size_t __not_found) const 00440 { 00441 ++__prev; 00442 if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) 00443 return __not_found; 00444 00445 _WordT __x = _M_w >> __prev; 00446 if (__x != 0) 00447 return __builtin_ctzl(__x) + __prev; 00448 else 00449 return __not_found; 00450 } 00451 }; 00452 00453 /** 00454 * Base class, specialization for no storage (zero-length %bitset). 00455 * 00456 * See documentation for bitset. 00457 */ 00458 template<> 00459 struct _Base_bitset<0> 00460 { 00461 typedef unsigned long _WordT; 00462 00463 _Base_bitset() 00464 { } 00465 00466 _Base_bitset(unsigned long) 00467 { } 00468 00469 static size_t 00470 _S_whichword(size_t __pos ) 00471 { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } 00472 00473 static size_t 00474 _S_whichbyte(size_t __pos ) 00475 { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } 00476 00477 static size_t 00478 _S_whichbit(size_t __pos ) 00479 { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } 00480 00481 static _WordT 00482 _S_maskbit(size_t __pos ) 00483 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00484 00485 // This would normally give access to the data. The bounds-checking 00486 // in the bitset class will prevent the user from getting this far, 00487 // but (1) it must still return an lvalue to compile, and (2) the 00488 // user might call _Unchecked_set directly, in which case this /needs/ 00489 // to fail. Let's not penalize zero-length users unless they actually 00490 // make an unchecked call; all the memory ugliness is therefore 00491 // localized to this single should-never-get-this-far function. 00492 _WordT& 00493 _M_getword(size_t) const 00494 { 00495 __throw_out_of_range(__N("_Base_bitset::_M_getword")); 00496 return *new _WordT; 00497 } 00498 00499 _WordT 00500 _M_hiword() const 00501 { return 0; } 00502 00503 void 00504 _M_do_and(const _Base_bitset<0>&) 00505 { } 00506 00507 void 00508 _M_do_or(const _Base_bitset<0>&) 00509 { } 00510 00511 void 00512 _M_do_xor(const _Base_bitset<0>&) 00513 { } 00514 00515 void 00516 _M_do_left_shift(size_t) 00517 { } 00518 00519 void 00520 _M_do_right_shift(size_t) 00521 { } 00522 00523 void 00524 _M_do_flip() 00525 { } 00526 00527 void 00528 _M_do_set() 00529 { } 00530 00531 void 00532 _M_do_reset() 00533 { } 00534 00535 // Are all empty bitsets equal to each other? Are they equal to 00536 // themselves? How to compare a thing which has no state? What is 00537 // the sound of one zero-length bitset clapping? 00538 bool 00539 _M_is_equal(const _Base_bitset<0>&) const 00540 { return true; } 00541 00542 size_t 00543 _M_are_all_aux() const 00544 { return 0; } 00545 00546 bool 00547 _M_is_any() const 00548 { return false; } 00549 00550 size_t 00551 _M_do_count() const 00552 { return 0; } 00553 00554 unsigned long 00555 _M_do_to_ulong() const 00556 { return 0; } 00557 00558 // Normally "not found" is the size, but that could also be 00559 // misinterpreted as an index in this corner case. Oh well. 00560 size_t 00561 _M_do_find_first(size_t) const 00562 { return 0; } 00563 00564 size_t 00565 _M_do_find_next(size_t, size_t) const 00566 { return 0; } 00567 }; 00568 00569 00570 // Helper class to zero out the unused high-order bits in the highest word. 00571 template<size_t _Extrabits> 00572 struct _Sanitize 00573 { 00574 static void _S_do_sanitize(unsigned long& __val) 00575 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 00576 }; 00577 00578 template<> 00579 struct _Sanitize<0> 00580 { static void _S_do_sanitize(unsigned long) {} }; 00581 00582 /** 00583 * @brief The %bitset class represents a @e fixed-size sequence of bits. 00584 * 00585 * @ingroup containers 00586 * 00587 * (Note that %bitset does @e not meet the formal requirements of a 00588 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 00589 * 00590 * The template argument, @a Nb, may be any non-negative number, 00591 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00592 * 00593 * In the general unoptimized case, storage is allocated in word-sized 00594 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 00595 * words will be used for storage. B - Nb%B bits are unused. (They are 00596 * the high-order bits in the highest word.) It is a class invariant 00597 * that those unused bits are always zero. 00598 * 00599 * If you think of %bitset as "a simple array of bits," be aware that 00600 * your mental picture is reversed: a %bitset behaves the same way as 00601 * bits in integers do, with the bit at index 0 in the "least significant 00602 * / right-hand" position, and the bit at index Nb-1 in the "most 00603 * significant / left-hand" position. Thus, unlike other containers, a 00604 * %bitset's index "counts from right to left," to put it very loosely. 00605 * 00606 * This behavior is preserved when translating to and from strings. For 00607 * example, the first line of the following program probably prints 00608 * "b('a') is 0001100001" on a modern ASCII system. 00609 * 00610 * @code 00611 * #include <bitset> 00612 * #include <iostream> 00613 * #include <sstream> 00614 * 00615 * using namespace std; 00616 * 00617 * int main() 00618 * { 00619 * long a = 'a'; 00620 * bitset<10> b(a); 00621 * 00622 * cout << "b('a') is " << b << endl; 00623 * 00624 * ostringstream s; 00625 * s << b; 00626 * string str = s.str(); 00627 * cout << "index 3 in the string is " << str[3] << " but\n" 00628 * << "index 3 in the bitset is " << b[3] << endl; 00629 * } 00630 * @endcode 00631 * 00632 * Also see: 00633 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html 00634 * for a description of extensions. 00635 * 00636 * Most of the actual code isn't contained in %bitset<> itself, but in the 00637 * base class _Base_bitset. The base class works with whole words, not with 00638 * individual bits. This allows us to specialize _Base_bitset for the 00639 * important special case where the %bitset is only a single word. 00640 * 00641 * Extra confusion can result due to the fact that the storage for 00642 * _Base_bitset @e is a regular array, and is indexed as such. This is 00643 * carefully encapsulated. 00644 */ 00645 template<size_t _Nb> 00646 class bitset 00647 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 00648 { 00649 private: 00650 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 00651 typedef unsigned long _WordT; 00652 00653 void 00654 _M_do_sanitize() 00655 { 00656 _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD>:: 00657 _S_do_sanitize(this->_M_hiword()); 00658 } 00659 00660 public: 00661 /** 00662 * This encapsulates the concept of a single bit. An instance of this 00663 * class is a proxy for an actual bit; this way the individual bit 00664 * operations are done as faster word-size bitwise instructions. 00665 * 00666 * Most users will never need to use this class directly; conversions 00667 * to and from bool are automatic and should be transparent. Overloaded 00668 * operators help to preserve the illusion. 00669 * 00670 * (On a typical system, this "bit %reference" is 64 times the size of 00671 * an actual bit. Ha.) 00672 */ 00673 class reference 00674 { 00675 friend class bitset; 00676 00677 _WordT *_M_wp; 00678 size_t _M_bpos; 00679 00680 // left undefined 00681 reference(); 00682 00683 public: 00684 reference(bitset& __b, size_t __pos) 00685 { 00686 _M_wp = &__b._M_getword(__pos); 00687 _M_bpos = _Base::_S_whichbit(__pos); 00688 } 00689 00690 ~reference() 00691 { } 00692 00693 // For b[i] = __x; 00694 reference& 00695 operator=(bool __x) 00696 { 00697 if (__x) 00698 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00699 else 00700 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00701 return *this; 00702 } 00703 00704 // For b[i] = b[__j]; 00705 reference& 00706 operator=(const reference& __j) 00707 { 00708 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 00709 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00710 else 00711 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00712 return *this; 00713 } 00714 00715 // Flips the bit 00716 bool 00717 operator~() const 00718 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 00719 00720 // For __x = b[i]; 00721 operator bool() const 00722 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 00723 00724 // For b[i].flip(); 00725 reference& 00726 flip() 00727 { 00728 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 00729 return *this; 00730 } 00731 }; 00732 friend class reference; 00733 00734 // 23.3.5.1 constructors: 00735 /// All bits set to zero. 00736 bitset() 00737 { } 00738 00739 /// Initial bits bitwise-copied from a single word (others set to zero). 00740 bitset(unsigned long __val) 00741 : _Base(__val) 00742 { _M_do_sanitize(); } 00743 00744 /** 00745 * @brief Use a subset of a string. 00746 * @param s A string of '0' and '1' characters. 00747 * @param position Index of the first character in @a s to use; 00748 * defaults to zero. 00749 * @throw std::out_of_range If @a pos is bigger the size of @a s. 00750 * @throw std::invalid_argument If a character appears in the string 00751 * which is neither '0' nor '1'. 00752 */ 00753 template<class _CharT, class _Traits, class _Alloc> 00754 explicit 00755 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00756 size_t __position = 0) 00757 : _Base() 00758 { 00759 if (__position > __s.size()) 00760 __throw_out_of_range(__N("bitset::bitset initial position " 00761 "not valid")); 00762 _M_copy_from_string(__s, __position, 00763 std::basic_string<_CharT, _Traits, _Alloc>::npos, 00764 _CharT('0'), _CharT('1')); 00765 } 00766 00767 /** 00768 * @brief Use a subset of a string. 00769 * @param s A string of '0' and '1' characters. 00770 * @param position Index of the first character in @a s to use. 00771 * @param n The number of characters to copy. 00772 * @throw std::out_of_range If @a pos is bigger the size of @a s. 00773 * @throw std::invalid_argument If a character appears in the string 00774 * which is neither '0' nor '1'. 00775 */ 00776 template<class _CharT, class _Traits, class _Alloc> 00777 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00778 size_t __position, size_t __n) 00779 : _Base() 00780 { 00781 if (__position > __s.size()) 00782 __throw_out_of_range(__N("bitset::bitset initial position " 00783 "not valid")); 00784 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 00785 } 00786 00787 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00788 // 396. what are characters zero and one. 00789 template<class _CharT, class _Traits, class _Alloc> 00790 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 00791 size_t __position, size_t __n, 00792 _CharT __zero, _CharT __one = _CharT('1')) 00793 : _Base() 00794 { 00795 if (__position > __s.size()) 00796 __throw_out_of_range(__N("bitset::bitset initial position " 00797 "not valid")); 00798 _M_copy_from_string(__s, __position, __n, __zero, __one); 00799 } 00800 00801 // 23.3.5.2 bitset operations: 00802 //@{ 00803 /** 00804 * @brief Operations on bitsets. 00805 * @param rhs A same-sized bitset. 00806 * 00807 * These should be self-explanatory. 00808 */ 00809 bitset<_Nb>& 00810 operator&=(const bitset<_Nb>& __rhs) 00811 { 00812 this->_M_do_and(__rhs); 00813 return *this; 00814 } 00815 00816 bitset<_Nb>& 00817 operator|=(const bitset<_Nb>& __rhs) 00818 { 00819 this->_M_do_or(__rhs); 00820 return *this; 00821 } 00822 00823 bitset<_Nb>& 00824 operator^=(const bitset<_Nb>& __rhs) 00825 { 00826 this->_M_do_xor(__rhs); 00827 return *this; 00828 } 00829 //@} 00830 00831 //@{ 00832 /** 00833 * @brief Operations on bitsets. 00834 * @param position The number of places to shift. 00835 * 00836 * These should be self-explanatory. 00837 */ 00838 bitset<_Nb>& 00839 operator<<=(size_t __position) 00840 { 00841 if (__builtin_expect(__position < _Nb, 1)) 00842 { 00843 this->_M_do_left_shift(__position); 00844 this->_M_do_sanitize(); 00845 } 00846 else 00847 this->_M_do_reset(); 00848 return *this; 00849 } 00850 00851 bitset<_Nb>& 00852 operator>>=(size_t __position) 00853 { 00854 if (__builtin_expect(__position < _Nb, 1)) 00855 { 00856 this->_M_do_right_shift(__position); 00857 this->_M_do_sanitize(); 00858 } 00859 else 00860 this->_M_do_reset(); 00861 return *this; 00862 } 00863 //@} 00864 00865 //@{ 00866 /** 00867 * These versions of single-bit set, reset, flip, and test are 00868 * extensions from the SGI version. They do no range checking. 00869 * @ingroup SGIextensions 00870 */ 00871 bitset<_Nb>& 00872 _Unchecked_set(size_t __pos) 00873 { 00874 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00875 return *this; 00876 } 00877 00878 bitset<_Nb>& 00879 _Unchecked_set(size_t __pos, int __val) 00880 { 00881 if (__val) 00882 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00883 else 00884 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00885 return *this; 00886 } 00887 00888 bitset<_Nb>& 00889 _Unchecked_reset(size_t __pos) 00890 { 00891 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00892 return *this; 00893 } 00894 00895 bitset<_Nb>& 00896 _Unchecked_flip(size_t __pos) 00897 { 00898 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 00899 return *this; 00900 } 00901 00902 bool 00903 _Unchecked_test(size_t __pos) const 00904 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 00905 != static_cast<_WordT>(0)); } 00906 //@} 00907 00908 // Set, reset, and flip. 00909 /** 00910 * @brief Sets every bit to true. 00911 */ 00912 bitset<_Nb>& 00913 set() 00914 { 00915 this->_M_do_set(); 00916 this->_M_do_sanitize(); 00917 return *this; 00918 } 00919 00920 /** 00921 * @brief Sets a given bit to a particular value. 00922 * @param position The index of the bit. 00923 * @param val Either true or false, defaults to true. 00924 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00925 */ 00926 bitset<_Nb>& 00927 set(size_t __position, bool __val = true) 00928 { 00929 if (__position >= _Nb) 00930 __throw_out_of_range(__N("bitset::set")); 00931 return _Unchecked_set(__position, __val); 00932 } 00933 00934 /** 00935 * @brief Sets every bit to false. 00936 */ 00937 bitset<_Nb>& 00938 reset() 00939 { 00940 this->_M_do_reset(); 00941 return *this; 00942 } 00943 00944 /** 00945 * @brief Sets a given bit to false. 00946 * @param position The index of the bit. 00947 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00948 * 00949 * Same as writing @c set(pos,false). 00950 */ 00951 bitset<_Nb>& 00952 reset(size_t __position) 00953 { 00954 if (__position >= _Nb) 00955 __throw_out_of_range(__N("bitset::reset")); 00956 return _Unchecked_reset(__position); 00957 } 00958 00959 /** 00960 * @brief Toggles every bit to its opposite value. 00961 */ 00962 bitset<_Nb>& 00963 flip() 00964 { 00965 this->_M_do_flip(); 00966 this->_M_do_sanitize(); 00967 return *this; 00968 } 00969 00970 /** 00971 * @brief Toggles a given bit to its opposite value. 00972 * @param position The index of the bit. 00973 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00974 */ 00975 bitset<_Nb>& 00976 flip(size_t __position) 00977 { 00978 if (__position >= _Nb) 00979 __throw_out_of_range(__N("bitset::flip")); 00980 return _Unchecked_flip(__position); 00981 } 00982 00983 /// See the no-argument flip(). 00984 bitset<_Nb> 00985 operator~() const 00986 { return bitset<_Nb>(*this).flip(); } 00987 00988 //@{ 00989 /** 00990 * @brief Array-indexing support. 00991 * @param position Index into the %bitset. 00992 * @return A bool for a 'const %bitset'. For non-const bitsets, an 00993 * instance of the reference proxy class. 00994 * @note These operators do no range checking and throw no exceptions, 00995 * as required by DR 11 to the standard. 00996 * 00997 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 00998 * resolves DR 11 (items 1 and 2), but does not do the range-checking 00999 * required by that DR's resolution. -pme 01000 * The DR has since been changed: range-checking is a precondition 01001 * (users' responsibility), and these functions must not throw. -pme 01002 */ 01003 reference 01004 operator[](size_t __position) 01005 { return reference(*this,__position); } 01006 01007 bool 01008 operator[](size_t __position) const 01009 { return _Unchecked_test(__position); } 01010 //@} 01011 01012 /** 01013 * @brief Returns a numerical interpretation of the %bitset. 01014 * @return The integral equivalent of the bits. 01015 * @throw std::overflow_error If there are too many bits to be 01016 * represented in an @c unsigned @c long. 01017 */ 01018 unsigned long 01019 to_ulong() const 01020 { return this->_M_do_to_ulong(); } 01021 01022 /** 01023 * @brief Returns a character interpretation of the %bitset. 01024 * @return The string equivalent of the bits. 01025 * 01026 * Note the ordering of the bits: decreasing character positions 01027 * correspond to increasing bit positions (see the main class notes for 01028 * an example). 01029 */ 01030 template<class _CharT, class _Traits, class _Alloc> 01031 std::basic_string<_CharT, _Traits, _Alloc> 01032 to_string() const 01033 { 01034 std::basic_string<_CharT, _Traits, _Alloc> __result; 01035 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 01036 return __result; 01037 } 01038 01039 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01040 // 396. what are characters zero and one. 01041 template<class _CharT, class _Traits, class _Alloc> 01042 std::basic_string<_CharT, _Traits, _Alloc> 01043 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01044 { 01045 std::basic_string<_CharT, _Traits, _Alloc> __result; 01046 _M_copy_to_string(__result, __zero, __one); 01047 return __result; 01048 } 01049 01050 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01051 // 434. bitset::to_string() hard to use. 01052 template<class _CharT, class _Traits> 01053 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01054 to_string() const 01055 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 01056 01057 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01058 // 853. to_string needs updating with zero and one. 01059 template<class _CharT, class _Traits> 01060 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 01061 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01062 { return to_string<_CharT, _Traits, 01063 std::allocator<_CharT> >(__zero, __one); } 01064 01065 template<class _CharT> 01066 std::basic_string<_CharT, std::char_traits<_CharT>, 01067 std::allocator<_CharT> > 01068 to_string() const 01069 { 01070 return to_string<_CharT, std::char_traits<_CharT>, 01071 std::allocator<_CharT> >(); 01072 } 01073 01074 template<class _CharT> 01075 std::basic_string<_CharT, std::char_traits<_CharT>, 01076 std::allocator<_CharT> > 01077 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 01078 { 01079 return to_string<_CharT, std::char_traits<_CharT>, 01080 std::allocator<_CharT> >(__zero, __one); 01081 } 01082 01083 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01084 to_string() const 01085 { 01086 return to_string<char, std::char_traits<char>, 01087 std::allocator<char> >(); 01088 } 01089 01090 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 01091 to_string(char __zero, char __one = '1') const 01092 { 01093 return to_string<char, std::char_traits<char>, 01094 std::allocator<char> >(__zero, __one); 01095 } 01096 01097 // Helper functions for string operations. 01098 template<class _CharT, class _Traits> 01099 void 01100 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 01101 _CharT, _CharT); 01102 01103 template<class _CharT, class _Traits, class _Alloc> 01104 void 01105 _M_copy_from_string(const std::basic_string<_CharT, 01106 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 01107 _CharT __zero, _CharT __one) 01108 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 01109 __zero, __one); } 01110 01111 template<class _CharT, class _Traits, class _Alloc> 01112 void 01113 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 01114 _CharT, _CharT) const; 01115 01116 // NB: Backward compat. 01117 template<class _CharT, class _Traits, class _Alloc> 01118 void 01119 _M_copy_from_string(const std::basic_string<_CharT, 01120 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 01121 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 01122 01123 template<class _CharT, class _Traits, class _Alloc> 01124 void 01125 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 01126 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 01127 01128 /// Returns the number of bits which are set. 01129 size_t 01130 count() const 01131 { return this->_M_do_count(); } 01132 01133 /// Returns the total number of bits. 01134 size_t 01135 size() const 01136 { return _Nb; } 01137 01138 //@{ 01139 /// These comparisons for equality/inequality are, well, @e bitwise. 01140 bool 01141 operator==(const bitset<_Nb>& __rhs) const 01142 { return this->_M_is_equal(__rhs); } 01143 01144 bool 01145 operator!=(const bitset<_Nb>& __rhs) const 01146 { return !this->_M_is_equal(__rhs); } 01147 //@} 01148 01149 /** 01150 * @brief Tests the value of a bit. 01151 * @param position The index of a bit. 01152 * @return The value at @a pos. 01153 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01154 */ 01155 bool 01156 test(size_t __position) const 01157 { 01158 if (__position >= _Nb) 01159 __throw_out_of_range(__N("bitset::test")); 01160 return _Unchecked_test(__position); 01161 } 01162 01163 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01164 // DR 693. std::bitset::all() missing. 01165 /** 01166 * @brief Tests whether all the bits are on. 01167 * @return True if all the bits are set. 01168 */ 01169 bool 01170 all() const 01171 { return this->_M_are_all_aux() == _Nb; } 01172 01173 /** 01174 * @brief Tests whether any of the bits are on. 01175 * @return True if at least one bit is set. 01176 */ 01177 bool 01178 any() const 01179 { return this->_M_is_any(); } 01180 01181 /** 01182 * @brief Tests whether any of the bits are on. 01183 * @return True if none of the bits are set. 01184 */ 01185 bool 01186 none() const 01187 { return !this->_M_is_any(); } 01188 01189 //@{ 01190 /// Self-explanatory. 01191 bitset<_Nb> 01192 operator<<(size_t __position) const 01193 { return bitset<_Nb>(*this) <<= __position; } 01194 01195 bitset<_Nb> 01196 operator>>(size_t __position) const 01197 { return bitset<_Nb>(*this) >>= __position; } 01198 //@} 01199 01200 /** 01201 * @brief Finds the index of the first "on" bit. 01202 * @return The index of the first bit set, or size() if not found. 01203 * @ingroup SGIextensions 01204 * @sa _Find_next 01205 */ 01206 size_t 01207 _Find_first() const 01208 { return this->_M_do_find_first(_Nb); } 01209 01210 /** 01211 * @brief Finds the index of the next "on" bit after prev. 01212 * @return The index of the next bit set, or size() if not found. 01213 * @param prev Where to start searching. 01214 * @ingroup SGIextensions 01215 * @sa _Find_first 01216 */ 01217 size_t 01218 _Find_next(size_t __prev ) const 01219 { return this->_M_do_find_next(__prev, _Nb); } 01220 }; 01221 01222 // Definitions of non-inline member functions. 01223 template<size_t _Nb> 01224 template<class _CharT, class _Traits> 01225 void 01226 bitset<_Nb>:: 01227 _M_copy_from_ptr(const _CharT* __s, size_t __len, 01228 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 01229 { 01230 reset(); 01231 const size_t __nbits = std::min(_Nb, std::min(__n, __len - __pos)); 01232 for (size_t __i = __nbits; __i > 0; --__i) 01233 { 01234 const _CharT __c = __s[__pos + __nbits - __i]; 01235 if (_Traits::eq(__c, __zero)) 01236 ; 01237 else if (_Traits::eq(__c, __one)) 01238 _Unchecked_set(__i - 1); 01239 else 01240 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 01241 } 01242 } 01243 01244 template<size_t _Nb> 01245 template<class _CharT, class _Traits, class _Alloc> 01246 void 01247 bitset<_Nb>:: 01248 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 01249 _CharT __zero, _CharT __one) const 01250 { 01251 __s.assign(_Nb, __zero); 01252 for (size_t __i = _Nb; __i > 0; --__i) 01253 if (_Unchecked_test(__i - 1)) 01254 _Traits::assign(__s[_Nb - __i], __one); 01255 } 01256 01257 // 23.3.5.3 bitset operations: 01258 //@{ 01259 /** 01260 * @brief Global bitwise operations on bitsets. 01261 * @param x A bitset. 01262 * @param y A bitset of the same size as @a x. 01263 * @return A new bitset. 01264 * 01265 * These should be self-explanatory. 01266 */ 01267 template<size_t _Nb> 01268 inline bitset<_Nb> 01269 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01270 { 01271 bitset<_Nb> __result(__x); 01272 __result &= __y; 01273 return __result; 01274 } 01275 01276 template<size_t _Nb> 01277 inline bitset<_Nb> 01278 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01279 { 01280 bitset<_Nb> __result(__x); 01281 __result |= __y; 01282 return __result; 01283 } 01284 01285 template <size_t _Nb> 01286 inline bitset<_Nb> 01287 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01288 { 01289 bitset<_Nb> __result(__x); 01290 __result ^= __y; 01291 return __result; 01292 } 01293 //@} 01294 01295 //@{ 01296 /** 01297 * @brief Global I/O operators for bitsets. 01298 * 01299 * Direct I/O between streams and bitsets is supported. Output is 01300 * straightforward. Input will skip whitespace, only accept '0' and '1' 01301 * characters, and will only extract as many digits as the %bitset will 01302 * hold. 01303 */ 01304 template<class _CharT, class _Traits, size_t _Nb> 01305 std::basic_istream<_CharT, _Traits>& 01306 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 01307 { 01308 typedef typename _Traits::char_type char_type; 01309 typedef std::basic_istream<_CharT, _Traits> __istream_type; 01310 typedef typename __istream_type::ios_base __ios_base; 01311 01312 std::basic_string<_CharT, _Traits> __tmp; 01313 __tmp.reserve(_Nb); 01314 01315 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01316 // 303. Bitset input operator underspecified 01317 const char_type __zero = __is.widen('0'); 01318 const char_type __one = __is.widen('1'); 01319 01320 typename __ios_base::iostate __state = __ios_base::goodbit; 01321 typename __istream_type::sentry __sentry(__is); 01322 if (__sentry) 01323 { 01324 __try 01325 { 01326 for (size_t __i = _Nb; __i > 0; --__i) 01327 { 01328 static typename _Traits::int_type __eof = _Traits::eof(); 01329 01330 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 01331 if (_Traits::eq_int_type(__c1, __eof)) 01332 { 01333 __state |= __ios_base::eofbit; 01334 break; 01335 } 01336 else 01337 { 01338 const char_type __c2 = _Traits::to_char_type(__c1); 01339 if (_Traits::eq(__c2, __zero)) 01340 __tmp.push_back(__zero); 01341 else if (_Traits::eq(__c2, __one)) 01342 __tmp.push_back(__one); 01343 else if (_Traits:: 01344 eq_int_type(__is.rdbuf()->sputbackc(__c2), 01345 __eof)) 01346 { 01347 __state |= __ios_base::failbit; 01348 break; 01349 } 01350 } 01351 } 01352 } 01353 __catch(__cxxabiv1::__forced_unwind&) 01354 { 01355 __is._M_setstate(__ios_base::badbit); 01356 __throw_exception_again; 01357 } 01358 __catch(...) 01359 { __is._M_setstate(__ios_base::badbit); } 01360 } 01361 01362 if (__tmp.empty() && _Nb) 01363 __state |= __ios_base::failbit; 01364 else 01365 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 01366 __zero, __one); 01367 if (__state) 01368 __is.setstate(__state); 01369 return __is; 01370 } 01371 01372 template <class _CharT, class _Traits, size_t _Nb> 01373 std::basic_ostream<_CharT, _Traits>& 01374 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 01375 const bitset<_Nb>& __x) 01376 { 01377 std::basic_string<_CharT, _Traits> __tmp; 01378 01379 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01380 // 396. what are characters zero and one. 01381 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 01382 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 01383 return __os << __tmp; 01384 } 01385 //@} 01386 01387 _GLIBCXX_END_NESTED_NAMESPACE 01388 01389 #undef _GLIBCXX_BITSET_WORDS 01390 #undef _GLIBCXX_BITSET_BITS_PER_WORD 01391 01392 #ifdef _GLIBCXX_DEBUG 01393 # include <debug/bitset> 01394 #endif 01395 01396 #endif /* _GLIBCXX_BITSET */