bitset

Go to the documentation of this file.
00001 // <bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002 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 2, 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 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * Copyright (c) 1998 00032 * Silicon Graphics Computer Systems, Inc. 00033 * 00034 * Permission to use, copy, modify, distribute and sell this software 00035 * and its documentation for any purpose is hereby granted without fee, 00036 * provided that the above copyright notice appear in all copies and 00037 * that both that copyright notice and this permission notice appear 00038 * in supporting documentation. Silicon Graphics makes no 00039 * representations about the suitability of this software for any 00040 * purpose. It is provided "as is" without express or implied warranty. 00041 */ 00042 00048 #ifndef _GLIBCPP_BITSET_H 00049 #define _GLIBCPP_BITSET_H 00050 00051 #pragma GCC system_header 00052 00053 #include <cstddef> // for size_t 00054 #include <cstring> // for memset 00055 #include <string> 00056 #include <bits/functexcept.h> // for invalid_argument, out_of_range, 00057 // overflow_error 00058 #include <ostream> // for ostream (operator<<) 00059 #include <istream> // for istream (operator>>) 00060 00061 00062 #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) 00063 #define _GLIBCPP_BITSET_WORDS(__n) \ 00064 ((__n) < 1 ? 0 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD) 00065 00066 namespace std 00067 { 00068 extern unsigned char _S_bit_count[256]; 00069 extern unsigned char _S_first_one[256]; 00070 00079 template<size_t _Nw> 00080 struct _Base_bitset 00081 { 00082 typedef unsigned long _WordT; 00083 00085 _WordT _M_w[_Nw]; 00086 00087 _Base_bitset() { _M_do_reset(); } 00088 _Base_bitset(unsigned long __val) 00089 { 00090 _M_do_reset(); 00091 _M_w[0] = __val; 00092 } 00093 00094 static size_t 00095 _S_whichword(size_t __pos ) 00096 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 00097 00098 static size_t 00099 _S_whichbyte(size_t __pos ) 00100 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 00101 00102 static size_t 00103 _S_whichbit(size_t __pos ) 00104 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 00105 00106 static _WordT 00107 _S_maskbit(size_t __pos ) 00108 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00109 00110 _WordT& 00111 _M_getword(size_t __pos) 00112 { return _M_w[_S_whichword(__pos)]; } 00113 00114 _WordT 00115 _M_getword(size_t __pos) const 00116 { return _M_w[_S_whichword(__pos)]; } 00117 00118 _WordT& 00119 _M_hiword() { return _M_w[_Nw - 1]; } 00120 00121 _WordT 00122 _M_hiword() const { return _M_w[_Nw - 1]; } 00123 00124 void 00125 _M_do_and(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_or(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_xor(const _Base_bitset<_Nw>& __x) 00140 { 00141 for (size_t __i = 0; __i < _Nw; __i++) 00142 _M_w[__i] ^= __x._M_w[__i]; 00143 } 00144 00145 void 00146 _M_do_left_shift(size_t __shift); 00147 00148 void 00149 _M_do_right_shift(size_t __shift); 00150 00151 void 00152 _M_do_flip() 00153 { 00154 for (size_t __i = 0; __i < _Nw; __i++) 00155 _M_w[__i] = ~_M_w[__i]; 00156 } 00157 00158 void 00159 _M_do_set() 00160 { 00161 for (size_t __i = 0; __i < _Nw; __i++) 00162 _M_w[__i] = ~static_cast<_WordT>(0); 00163 } 00164 00165 void 00166 _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } 00167 00168 bool 00169 _M_is_equal(const _Base_bitset<_Nw>& __x) const 00170 { 00171 for (size_t __i = 0; __i < _Nw; ++__i) 00172 { 00173 if (_M_w[__i] != __x._M_w[__i]) 00174 return false; 00175 } 00176 return true; 00177 } 00178 00179 bool 00180 _M_is_any() const 00181 { 00182 for (size_t __i = 0; __i < _Nw; __i++) 00183 { 00184 if (_M_w[__i] != static_cast<_WordT>(0)) 00185 return true; 00186 } 00187 return false; 00188 } 00189 00190 size_t 00191 _M_do_count() const 00192 { 00193 size_t __result = 0; 00194 const unsigned char* __byte_ptr = (const unsigned char*)_M_w; 00195 const unsigned char* __end_ptr = (const unsigned char*)(_M_w + _Nw); 00196 00197 while ( __byte_ptr < __end_ptr ) 00198 { 00199 __result += _S_bit_count[*__byte_ptr]; 00200 __byte_ptr++; 00201 } 00202 return __result; 00203 } 00204 00205 unsigned long 00206 _M_do_to_ulong() const; 00207 00208 // find first "on" bit 00209 size_t 00210 _M_do_find_first(size_t __not_found) const; 00211 00212 // find the next "on" bit that follows "prev" 00213 size_t 00214 _M_do_find_next(size_t __prev, size_t __not_found) const; 00215 }; 00216 00217 // Definitions of non-inline functions from _Base_bitset. 00218 template<size_t _Nw> 00219 void 00220 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 00221 { 00222 if (__shift != 0) 00223 { 00224 const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 00225 const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 00226 00227 if (__offset == 0) 00228 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 00229 _M_w[__n] = _M_w[__n - __wshift]; 00230 else 00231 { 00232 const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 00233 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 00234 _M_w[__n] = (_M_w[__n - __wshift] << __offset) | 00235 (_M_w[__n - __wshift - 1] >> __sub_offset); 00236 _M_w[__wshift] = _M_w[0] << __offset; 00237 } 00238 00239 fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 00240 } 00241 } 00242 00243 template<size_t _Nw> 00244 void 00245 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 00246 { 00247 if (__shift != 0) 00248 { 00249 const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 00250 const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 00251 const size_t __limit = _Nw - __wshift - 1; 00252 00253 if (__offset == 0) 00254 for (size_t __n = 0; __n <= __limit; ++__n) 00255 _M_w[__n] = _M_w[__n + __wshift]; 00256 else 00257 { 00258 const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 00259 for (size_t __n = 0; __n < __limit; ++__n) 00260 _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | 00261 (_M_w[__n + __wshift + 1] << __sub_offset); 00262 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 00263 } 00264 00265 fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 00266 } 00267 } 00268 00269 template<size_t _Nw> 00270 unsigned long 00271 _Base_bitset<_Nw>::_M_do_to_ulong() const 00272 { 00273 for (size_t __i = 1; __i < _Nw; ++__i) 00274 if (_M_w[__i]) 00275 __throw_overflow_error("bitset -- too large to fit in unsigned long"); 00276 return _M_w[0]; 00277 } 00278 00279 template<size_t _Nw> 00280 size_t 00281 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 00282 { 00283 for (size_t __i = 0; __i < _Nw; __i++ ) 00284 { 00285 _WordT __thisword = _M_w[__i]; 00286 if ( __thisword != static_cast<_WordT>(0) ) 00287 { 00288 // find byte within word 00289 for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 00290 { 00291 unsigned char __this_byte 00292 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 00293 if (__this_byte) 00294 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 00295 _S_first_one[__this_byte]; 00296 00297 __thisword >>= CHAR_BIT; 00298 } 00299 } 00300 } 00301 // not found, so return an indication of failure. 00302 return __not_found; 00303 } 00304 00305 template<size_t _Nw> 00306 size_t 00307 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 00308 { 00309 // make bound inclusive 00310 ++__prev; 00311 00312 // check out of bounds 00313 if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD ) 00314 return __not_found; 00315 00316 // search first word 00317 size_t __i = _S_whichword(__prev); 00318 _WordT __thisword = _M_w[__i]; 00319 00320 // mask off bits below bound 00321 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00322 00323 if ( __thisword != static_cast<_WordT>(0) ) 00324 { 00325 // find byte within word 00326 // get first byte into place 00327 __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; 00328 for (size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++) 00329 { 00330 unsigned char __this_byte 00331 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 00332 if ( __this_byte ) 00333 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 00334 _S_first_one[__this_byte]; 00335 00336 __thisword >>= CHAR_BIT; 00337 } 00338 } 00339 00340 // check subsequent words 00341 __i++; 00342 for ( ; __i < _Nw; __i++ ) 00343 { 00344 __thisword = _M_w[__i]; 00345 if ( __thisword != static_cast<_WordT>(0) ) 00346 { 00347 // find byte within word 00348 for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 00349 { 00350 unsigned char __this_byte 00351 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 00352 if ( __this_byte ) 00353 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 00354 _S_first_one[__this_byte]; 00355 00356 __thisword >>= CHAR_BIT; 00357 } 00358 } 00359 } 00360 // not found, so return an indication of failure. 00361 return __not_found; 00362 } // end _M_do_find_next 00363 00364 00372 template<> 00373 struct _Base_bitset<1> 00374 { 00375 typedef unsigned long _WordT; 00376 _WordT _M_w; 00377 00378 _Base_bitset( void ) : _M_w(0) {} 00379 _Base_bitset(unsigned long __val) : _M_w(__val) {} 00380 00381 static size_t 00382 _S_whichword(size_t __pos ) 00383 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 00384 00385 static size_t 00386 _S_whichbyte(size_t __pos ) 00387 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 00388 00389 static size_t 00390 _S_whichbit(size_t __pos ) 00391 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 00392 00393 static _WordT 00394 _S_maskbit(size_t __pos ) 00395 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00396 00397 _WordT& 00398 _M_getword(size_t) { return _M_w; } 00399 00400 _WordT 00401 _M_getword(size_t) const { return _M_w; } 00402 00403 _WordT& 00404 _M_hiword() { return _M_w; } 00405 00406 _WordT 00407 _M_hiword() const { return _M_w; } 00408 00409 void 00410 _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } 00411 00412 void 00413 _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } 00414 00415 void 00416 _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } 00417 00418 void 00419 _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } 00420 00421 void 00422 _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } 00423 00424 void 00425 _M_do_flip() { _M_w = ~_M_w; } 00426 00427 void 00428 _M_do_set() { _M_w = ~static_cast<_WordT>(0); } 00429 00430 void 00431 _M_do_reset() { _M_w = 0; } 00432 00433 bool 00434 _M_is_equal(const _Base_bitset<1>& __x) const 00435 { return _M_w == __x._M_w; } 00436 00437 bool 00438 _M_is_any() const { return _M_w != 0; } 00439 00440 size_t 00441 _M_do_count() const 00442 { 00443 size_t __result = 0; 00444 const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; 00445 const unsigned char* __end_ptr 00446 = ((const unsigned char*)&_M_w)+sizeof(_M_w); 00447 while ( __byte_ptr < __end_ptr ) 00448 { 00449 __result += _S_bit_count[*__byte_ptr]; 00450 __byte_ptr++; 00451 } 00452 return __result; 00453 } 00454 00455 unsigned long 00456 _M_do_to_ulong() const { return _M_w; } 00457 00458 size_t 00459 _M_do_find_first(size_t __not_found) const; 00460 00461 // find the next "on" bit that follows "prev" 00462 size_t 00463 _M_do_find_next(size_t __prev, size_t __not_found) const; 00464 }; 00465 00466 00474 template<> 00475 struct _Base_bitset<0> 00476 { 00477 typedef unsigned long _WordT; 00478 00479 _Base_bitset() {} 00480 _Base_bitset(unsigned long) {} 00481 00482 static size_t 00483 _S_whichword(size_t __pos ) 00484 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 00485 00486 static size_t 00487 _S_whichbyte(size_t __pos ) 00488 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 00489 00490 static size_t 00491 _S_whichbit(size_t __pos ) 00492 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 00493 00494 static _WordT 00495 _S_maskbit(size_t __pos ) 00496 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 00497 00498 // This would normally give access to the data. The bounds-checking 00499 // in the bitset class will prevent the user from getting this far, 00500 // but (1) it must still return an lvalue to compile, and (2) the 00501 // user might call _Unchecked_set directly, in which case this /needs/ 00502 // to fail. Let's not penalize zero-length users unless they actually 00503 // make an unchecked call; all the memory ugliness is therefore 00504 // localized to this single should-never-get-this-far function. 00505 _WordT& 00506 _M_getword(size_t) const 00507 { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; } 00508 00509 _WordT 00510 _M_hiword() const { return 0; } 00511 00512 void 00513 _M_do_and(const _Base_bitset<0>&) { } 00514 00515 void 00516 _M_do_or(const _Base_bitset<0>&) { } 00517 00518 void 00519 _M_do_xor(const _Base_bitset<0>&) { } 00520 00521 void 00522 _M_do_left_shift(size_t) { } 00523 00524 void 00525 _M_do_right_shift(size_t) { } 00526 00527 void 00528 _M_do_flip() { } 00529 00530 void 00531 _M_do_set() { } 00532 00533 void 00534 _M_do_reset() { } 00535 00536 // Are all empty bitsets equal to each other? Are they equal to 00537 // themselves? How to compare a thing which has no state? What is 00538 // the sound of one zero-length bitset clapping? 00539 bool 00540 _M_is_equal(const _Base_bitset<0>&) const { return true; } 00541 00542 bool 00543 _M_is_any() const { return false; } 00544 00545 size_t 00546 _M_do_count() const { return 0; } 00547 00548 unsigned long 00549 _M_do_to_ulong() const { return 0; } 00550 00551 // Normally "not found" is the size, but that could also be 00552 // misinterpreted as an index in this corner case. Oh well. 00553 size_t 00554 _M_do_find_first(size_t) const { return 0; } 00555 00556 size_t 00557 _M_do_find_next(size_t, size_t) const { return 0; } 00558 }; 00559 00560 00561 // Helper class to zero out the unused high-order bits in the highest word. 00562 template<size_t _Extrabits> 00563 struct _Sanitize 00564 { 00565 static void _S_do_sanitize(unsigned long& __val) 00566 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 00567 }; 00568 00569 template<> 00570 struct _Sanitize<0> 00571 { static void _S_do_sanitize(unsigned long) { } }; 00572 00634 template<size_t _Nb> 00635 class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 00636 { 00637 private: 00638 typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 00639 typedef unsigned long _WordT; 00640 00641 void 00642 _M_do_sanitize() 00643 { 00644 _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 00645 _S_do_sanitize(this->_M_hiword()); 00646 } 00647 00648 public: 00661 class reference 00662 { 00663 friend class bitset; 00664 00665 _WordT *_M_wp; 00666 size_t _M_bpos; 00667 00668 // left undefined 00669 reference(); 00670 00671 public: 00672 reference(bitset& __b, size_t __pos) 00673 { 00674 _M_wp = &__b._M_getword(__pos); 00675 _M_bpos = _Base::_S_whichbit(__pos); 00676 } 00677 00678 ~reference() { } 00679 00680 // for b[i] = __x; 00681 reference& 00682 operator=(bool __x) 00683 { 00684 if ( __x ) 00685 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00686 else 00687 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00688 return *this; 00689 } 00690 00691 // for b[i] = b[__j]; 00692 reference& 00693 operator=(const reference& __j) 00694 { 00695 if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 00696 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00697 else 00698 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00699 return *this; 00700 } 00701 00702 // flips the bit 00703 bool 00704 operator~() const 00705 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 00706 00707 // for __x = b[i]; 00708 operator bool() const 00709 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 00710 00711 // for b[i].flip(); 00712 reference& 00713 flip() 00714 { 00715 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 00716 return *this; 00717 } 00718 }; 00719 friend class reference; 00720 00721 // 23.3.5.1 constructors: 00723 bitset() { } 00724 00726 bitset(unsigned long __val) : _Base(__val) 00727 { _M_do_sanitize(); } 00728 00738 template<class _CharT, class _Traits, class _Alloc> 00739 explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 00740 size_t __pos = 0) : _Base() 00741 { 00742 if (__pos > __s.size()) 00743 __throw_out_of_range("bitset -- initial position is larger than " 00744 "the string itself"); 00745 _M_copy_from_string(__s, __pos, 00746 basic_string<_CharT, _Traits, _Alloc>::npos); 00747 } 00748 00758 template<class _CharT, class _Traits, class _Alloc> 00759 bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 00760 size_t __pos, size_t __n) : _Base() 00761 { 00762 if (__pos > __s.size()) 00763 __throw_out_of_range("bitset -- initial position is larger than " 00764 "the string itself"); 00765 _M_copy_from_string(__s, __pos, __n); 00766 } 00767 00768 // 23.3.5.2 bitset operations: 00770 00776 bitset<_Nb>& 00777 operator&=(const bitset<_Nb>& __rhs) 00778 { 00779 this->_M_do_and(__rhs); 00780 return *this; 00781 } 00782 00783 bitset<_Nb>& 00784 operator|=(const bitset<_Nb>& __rhs) 00785 { 00786 this->_M_do_or(__rhs); 00787 return *this; 00788 } 00789 00790 bitset<_Nb>& 00791 operator^=(const bitset<_Nb>& __rhs) 00792 { 00793 this->_M_do_xor(__rhs); 00794 return *this; 00795 } 00797 00799 00805 bitset<_Nb>& 00806 operator<<=(size_t __pos) 00807 { 00808 this->_M_do_left_shift(__pos); 00809 this->_M_do_sanitize(); 00810 return *this; 00811 } 00812 00813 bitset<_Nb>& 00814 operator>>=(size_t __pos) 00815 { 00816 this->_M_do_right_shift(__pos); 00817 this->_M_do_sanitize(); 00818 return *this; 00819 } 00821 00823 00828 bitset<_Nb>& 00829 _Unchecked_set(size_t __pos) 00830 { 00831 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00832 return *this; 00833 } 00834 00835 bitset<_Nb>& 00836 _Unchecked_set(size_t __pos, int __val) 00837 { 00838 if (__val) 00839 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00840 else 00841 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00842 return *this; 00843 } 00844 00845 bitset<_Nb>& 00846 _Unchecked_reset(size_t __pos) 00847 { 00848 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00849 return *this; 00850 } 00851 00852 bitset<_Nb>& 00853 _Unchecked_flip(size_t __pos) 00854 { 00855 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 00856 return *this; 00857 } 00858 00859 bool 00860 _Unchecked_test(size_t __pos) const 00861 { 00862 return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 00863 != static_cast<_WordT>(0); 00864 } 00866 00867 // Set, reset, and flip. 00871 bitset<_Nb>& 00872 set() 00873 { 00874 this->_M_do_set(); 00875 this->_M_do_sanitize(); 00876 return *this; 00877 } 00878 00885 bitset<_Nb>& 00886 set(size_t __pos, bool __val = true) 00887 { 00888 if (__pos >= _Nb) 00889 __throw_out_of_range("bitset -- set() argument too large"); 00890 return _Unchecked_set(__pos, __val); 00891 } 00892 00896 bitset<_Nb>& 00897 reset() 00898 { 00899 this->_M_do_reset(); 00900 return *this; 00901 } 00902 00910 bitset<_Nb>& 00911 reset(size_t __pos) 00912 { 00913 if (__pos >= _Nb) 00914 __throw_out_of_range("bitset -- reset() argument too large"); 00915 return _Unchecked_reset(__pos); 00916 } 00917 00921 bitset<_Nb>& 00922 flip() 00923 { 00924 this->_M_do_flip(); 00925 this->_M_do_sanitize(); 00926 return *this; 00927 } 00928 00934 bitset<_Nb>& 00935 flip(size_t __pos) 00936 { 00937 if (__pos >= _Nb) 00938 __throw_out_of_range("bitset -- flip() argument too large"); 00939 return _Unchecked_flip(__pos); 00940 } 00941 00943 bitset<_Nb> 00944 operator~() const { return bitset<_Nb>(*this).flip(); } 00945 00947 00963 reference 00964 operator[](size_t __pos) { return reference(*this,__pos); } 00965 00966 bool 00967 operator[](size_t __pos) const { return _Unchecked_test(__pos); } 00969 00976 unsigned long 00977 to_ulong() const { return this->_M_do_to_ulong(); } 00978 00993 template<class _CharT, class _Traits, class _Alloc> 00994 basic_string<_CharT, _Traits, _Alloc> 00995 to_string() const 00996 { 00997 basic_string<_CharT, _Traits, _Alloc> __result; 00998 _M_copy_to_string(__result); 00999 return __result; 01000 } 01001 01002 // Helper functions for string operations. 01003 template<class _CharT, class _Traits, class _Alloc> 01004 void 01005 _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 01006 size_t, size_t); 01007 01008 template<class _CharT, class _Traits, class _Alloc> 01009 void 01010 _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 01011 01013 size_t 01014 count() const { return this->_M_do_count(); } 01015 01017 size_t 01018 size() const { return _Nb; } 01019 01021 01022 bool 01023 operator==(const bitset<_Nb>& __rhs) const 01024 { return this->_M_is_equal(__rhs); } 01025 01026 bool 01027 operator!=(const bitset<_Nb>& __rhs) const 01028 { return !this->_M_is_equal(__rhs); } 01030 01037 bool 01038 test(size_t __pos) const 01039 { 01040 if (__pos >= _Nb) 01041 __throw_out_of_range("bitset -- test() argument too large"); 01042 return _Unchecked_test(__pos); 01043 } 01044 01049 bool 01050 any() const { return this->_M_is_any(); } 01051 01056 bool 01057 none() const { return !this->_M_is_any(); } 01058 01060 01061 bitset<_Nb> 01062 operator<<(size_t __pos) const 01063 { return bitset<_Nb>(*this) <<= __pos; } 01064 01065 bitset<_Nb> 01066 operator>>(size_t __pos) const 01067 { return bitset<_Nb>(*this) >>= __pos; } 01069 01076 size_t 01077 _Find_first() const 01078 { return this->_M_do_find_first(_Nb); } 01079 01087 size_t 01088 _Find_next(size_t __prev ) const 01089 { return this->_M_do_find_next(__prev, _Nb); } 01090 }; 01091 01092 // Definitions of non-inline member functions. 01093 template<size_t _Nb> 01094 template<class _CharT, class _Traits, class _Alloc> 01095 void 01096 bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 01097 { 01098 reset(); 01099 const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 01100 for (size_t __i = 0; __i < __nbits; ++__i) 01101 { 01102 switch(__s[__pos + __nbits - __i - 1]) 01103 { 01104 case '0': 01105 break; 01106 case '1': 01107 set(__i); 01108 break; 01109 default: 01110 __throw_invalid_argument("bitset -- string contains characters " 01111 "which are neither 0 nor 1"); 01112 } 01113 } 01114 } 01115 01116 template<size_t _Nb> 01117 template<class _CharT, class _Traits, class _Alloc> 01118 void 01119 bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 01120 { 01121 __s.assign(_Nb, '0'); 01122 for (size_t __i = 0; __i < _Nb; ++__i) 01123 if (_Unchecked_test(__i)) 01124 __s[_Nb - 1 - __i] = '1'; 01125 } 01126 01127 // 23.3.5.3 bitset operations: 01129 01137 template<size_t _Nb> 01138 inline bitset<_Nb> 01139 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01140 { 01141 bitset<_Nb> __result(__x); 01142 __result &= __y; 01143 return __result; 01144 } 01145 01146 template<size_t _Nb> 01147 inline bitset<_Nb> 01148 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01149 { 01150 bitset<_Nb> __result(__x); 01151 __result |= __y; 01152 return __result; 01153 } 01154 01155 template <size_t _Nb> 01156 inline bitset<_Nb> 01157 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01158 { 01159 bitset<_Nb> __result(__x); 01160 __result ^= __y; 01161 return __result; 01162 } 01164 01166 01174 template<class _CharT, class _Traits, size_t _Nb> 01175 basic_istream<_CharT, _Traits>& 01176 operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 01177 { 01178 typedef typename _Traits::char_type char_type; 01179 basic_string<_CharT, _Traits> __tmp; 01180 __tmp.reserve(_Nb); 01181 01182 // Skip whitespace 01183 typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 01184 if (__sentry) 01185 { 01186 basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 01187 for (size_t __i = 0; __i < _Nb; ++__i) 01188 { 01189 static typename _Traits::int_type __eof = _Traits::eof(); 01190 01191 typename _Traits::int_type __c1 = __buf->sbumpc(); 01192 if (_Traits::eq_int_type(__c1, __eof)) 01193 { 01194 __is.setstate(ios_base::eofbit); 01195 break; 01196 } 01197 else 01198 { 01199 char_type __c2 = _Traits::to_char_type(__c1); 01200 char_type __c = __is.narrow(__c2, '*'); 01201 01202 if (__c == '0' || __c == '1') 01203 __tmp.push_back(__c); 01204 else if (_Traits::eq_int_type(__buf->sputbackc(__c2), 01205 __eof)) 01206 { 01207 __is.setstate(ios_base::failbit); 01208 break; 01209 } 01210 } 01211 } 01212 01213 if (__tmp.empty() && !_Nb) 01214 __is.setstate(ios_base::failbit); 01215 else 01216 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 01217 } 01218 01219 return __is; 01220 } 01221 01222 template <class _CharT, class _Traits, size_t _Nb> 01223 basic_ostream<_CharT, _Traits>& 01224 operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 01225 { 01226 basic_string<_CharT, _Traits> __tmp; 01227 __x._M_copy_to_string(__tmp); 01228 return __os << __tmp; 01229 } 01231 } // namespace std 01232 01233 #undef _GLIBCPP_BITSET_WORDS 01234 01235 #endif /* _GLIBCPP_BITSET_H */

Generated on Wed Sep 29 13:54:47 2004 for libstdc++-v3 Source by doxygen 1.3.7