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 00043 /** @file bitset 00044 * This is a Standard C++ Library header. You should @c #include this header 00045 * in your programs, rather than any of the "st[dl]_*.h" implementation files. 00046 */ 00047 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 00071 /** 00072 * @if maint 00073 * Base class, general case. It is a class inveriant that _Nw will be 00074 * nonnegative. 00075 * 00076 * See documentation for bitset. 00077 * @endif 00078 */ 00079 template<size_t _Nw> 00080 struct _Base_bitset 00081 { 00082 typedef unsigned long _WordT; 00083 00084 /// 0 is the least significant word. 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 (__builtin_expect(__shift != 0, 1)) 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 (__builtin_expect(__shift != 0, 1)) 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 00365 /** 00366 * @if maint 00367 * Base class, specialization for a single word. 00368 * 00369 * See documentation for bitset. 00370 * @endif 00371 */ 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 00467 /** 00468 * @if maint 00469 * Base class, specialization for no storage (zero-length %bitset). 00470 * 00471 * See documentation for bitset. 00472 * @endif 00473 */ 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 00573 00574 /** 00575 * @brief The %bitset class represents a @e fixed-size sequence of bits. 00576 * 00577 * @ingroup Containers 00578 * 00579 * (Note that %bitset does @e not meet the formal requirements of a 00580 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 00581 * 00582 * The template argument, @a Nb, may be any non-negative number, 00583 * specifying the number of bits (e.g., "0", "12", "1024*1024"). 00584 * 00585 * In the general unoptimized case, storage is allocated in word-sized 00586 * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B 00587 * words will be used for storage. B - Nb%B bits are unused. (They are 00588 * the high-order bits in the highest word.) It is a class invariant 00589 * that those unused bits are always zero. 00590 * 00591 * If you think of %bitset as "a simple array of bits," be aware that 00592 * your mental picture is reversed: a %bitset behaves the same way as 00593 * bits in integers do, with the bit at index 0 in the "least significant 00594 * / right-hand" position, and the bit at index Nb-1 in the "most 00595 * significant / left-hand" position. Thus, unlike other containers, a 00596 * %bitset's index "counts from right to left," to put it very loosely. 00597 * 00598 * This behavior is preserved when translating to and from strings. For 00599 * example, the first line of the following program probably prints 00600 * "b('a') is 0001100001" on a modern ASCII system. 00601 * 00602 * @code 00603 * #include <bitset> 00604 * #include <iostream> 00605 * #include <sstream> 00606 * 00607 * using namespace std; 00608 * 00609 * int main() 00610 * { 00611 * long a = 'a'; 00612 * bitset<10> b(a); 00613 * 00614 * cout << "b('a') is " << b << endl; 00615 * 00616 * ostringstream s; 00617 * s << b; 00618 * string str = s.str(); 00619 * cout << "index 3 in the string is " << str[3] << " but\n" 00620 * << "index 3 in the bitset is " << b[3] << endl; 00621 * } 00622 * @endcode 00623 * 00624 * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 00625 * for a description of extensions. 00626 * 00627 * @if maint 00628 * Most of the actual code isn't contained in %bitset<> itself, but in the 00629 * base class _Base_bitset. The base class works with whole words, not with 00630 * individual bits. This allows us to specialize _Base_bitset for the 00631 * important special case where the %bitset is only a single word. 00632 * 00633 * Extra confusion can result due to the fact that the storage for 00634 * _Base_bitset @e is a regular array, and is indexed as such. This is 00635 * carefully encapsulated. 00636 * @endif 00637 */ 00638 template<size_t _Nb> 00639 class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 00640 { 00641 private: 00642 typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 00643 typedef unsigned long _WordT; 00644 00645 void 00646 _M_do_sanitize() 00647 { 00648 _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 00649 _S_do_sanitize(this->_M_hiword()); 00650 } 00651 00652 public: 00653 /** 00654 * This encapsulates the concept of a single bit. An instance of this 00655 * class is a proxy for an actual bit; this way the individual bit 00656 * operations are done as faster word-size bitwise instructions. 00657 * 00658 * Most users will never need to use this class directly; conversions 00659 * to and from bool are automatic and should be transparent. Overloaded 00660 * operators help to preserve the illusion. 00661 * 00662 * (On a typical system, this "bit %reference" is 64 times the size of 00663 * an actual bit. Ha.) 00664 */ 00665 class reference 00666 { 00667 friend class bitset; 00668 00669 _WordT *_M_wp; 00670 size_t _M_bpos; 00671 00672 // left undefined 00673 reference(); 00674 00675 public: 00676 reference(bitset& __b, size_t __pos) 00677 { 00678 _M_wp = &__b._M_getword(__pos); 00679 _M_bpos = _Base::_S_whichbit(__pos); 00680 } 00681 00682 ~reference() { } 00683 00684 // for b[i] = __x; 00685 reference& 00686 operator=(bool __x) 00687 { 00688 if ( __x ) 00689 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00690 else 00691 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00692 return *this; 00693 } 00694 00695 // for b[i] = b[__j]; 00696 reference& 00697 operator=(const reference& __j) 00698 { 00699 if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 00700 *_M_wp |= _Base::_S_maskbit(_M_bpos); 00701 else 00702 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 00703 return *this; 00704 } 00705 00706 // flips the bit 00707 bool 00708 operator~() const 00709 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 00710 00711 // for __x = b[i]; 00712 operator bool() const 00713 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 00714 00715 // for b[i].flip(); 00716 reference& 00717 flip() 00718 { 00719 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 00720 return *this; 00721 } 00722 }; 00723 friend class reference; 00724 00725 // 23.3.5.1 constructors: 00726 /// All bits set to zero. 00727 bitset() { } 00728 00729 /// Initial bits bitwise-copied from a single word (others set to zero). 00730 bitset(unsigned long __val) : _Base(__val) 00731 { _M_do_sanitize(); } 00732 00733 /** 00734 * @brief Use a subset of a string. 00735 * @param s A string of '0' and '1' characters. 00736 * @param pos Index of the first character in @a s to use; defaults 00737 * to zero. 00738 * @throw std::out_of_range If @a pos is bigger the size of @a s. 00739 * @throw std::invalid_argument If a character appears in the string 00740 * which is neither '0' nor '1'. 00741 */ 00742 template<class _CharT, class _Traits, class _Alloc> 00743 explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 00744 size_t __pos = 0) : _Base() 00745 { 00746 if (__pos > __s.size()) 00747 __throw_out_of_range("bitset -- initial position is larger than " 00748 "the string itself"); 00749 _M_copy_from_string(__s, __pos, 00750 basic_string<_CharT, _Traits, _Alloc>::npos); 00751 } 00752 00753 /** 00754 * @brief Use a subset of a string. 00755 * @param s A string of '0' and '1' characters. 00756 * @param pos Index of the first character in @a s to use. 00757 * @param n The number of characters to copy. 00758 * @throw std::out_of_range If @a pos is bigger the size of @a s. 00759 * @throw std::invalid_argument If a character appears in the string 00760 * which is neither '0' nor '1'. 00761 */ 00762 template<class _CharT, class _Traits, class _Alloc> 00763 bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 00764 size_t __pos, size_t __n) : _Base() 00765 { 00766 if (__pos > __s.size()) 00767 __throw_out_of_range("bitset -- initial position is larger than " 00768 "the string itself"); 00769 _M_copy_from_string(__s, __pos, __n); 00770 } 00771 00772 // 23.3.5.2 bitset operations: 00773 //@{ 00774 /** 00775 * @brief Operations on bitsets. 00776 * @param rhs A same-sized bitset. 00777 * 00778 * These should be self-explanatory. 00779 */ 00780 bitset<_Nb>& 00781 operator&=(const bitset<_Nb>& __rhs) 00782 { 00783 this->_M_do_and(__rhs); 00784 return *this; 00785 } 00786 00787 bitset<_Nb>& 00788 operator|=(const bitset<_Nb>& __rhs) 00789 { 00790 this->_M_do_or(__rhs); 00791 return *this; 00792 } 00793 00794 bitset<_Nb>& 00795 operator^=(const bitset<_Nb>& __rhs) 00796 { 00797 this->_M_do_xor(__rhs); 00798 return *this; 00799 } 00800 //@} 00801 00802 //@{ 00803 /** 00804 * @brief Operations on bitsets. 00805 * @param pos The number of places to shift. 00806 * 00807 * These should be self-explanatory. 00808 */ 00809 bitset<_Nb>& 00810 operator<<=(size_t __pos) 00811 { 00812 if (__builtin_expect(__pos < _Nb, 1)) 00813 { 00814 this->_M_do_left_shift(__pos); 00815 this->_M_do_sanitize(); 00816 } 00817 else 00818 this->_M_do_reset(); 00819 return *this; 00820 } 00821 00822 bitset<_Nb>& 00823 operator>>=(size_t __pos) 00824 { 00825 if (__builtin_expect(__pos < _Nb, 1)) 00826 { 00827 this->_M_do_right_shift(__pos); 00828 this->_M_do_sanitize(); 00829 } 00830 else 00831 this->_M_do_reset(); 00832 return *this; 00833 } 00834 //@} 00835 00836 //@{ 00837 /** 00838 * These versions of single-bit set, reset, flip, and test are 00839 * extensions from the SGI version. They do no range checking. 00840 * @ingroup SGIextensions 00841 */ 00842 bitset<_Nb>& 00843 _Unchecked_set(size_t __pos) 00844 { 00845 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00846 return *this; 00847 } 00848 00849 bitset<_Nb>& 00850 _Unchecked_set(size_t __pos, int __val) 00851 { 00852 if (__val) 00853 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 00854 else 00855 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00856 return *this; 00857 } 00858 00859 bitset<_Nb>& 00860 _Unchecked_reset(size_t __pos) 00861 { 00862 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 00863 return *this; 00864 } 00865 00866 bitset<_Nb>& 00867 _Unchecked_flip(size_t __pos) 00868 { 00869 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 00870 return *this; 00871 } 00872 00873 bool 00874 _Unchecked_test(size_t __pos) const 00875 { 00876 return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 00877 != static_cast<_WordT>(0); 00878 } 00879 //@} 00880 00881 // Set, reset, and flip. 00882 /** 00883 * @brief Sets every bit to true. 00884 */ 00885 bitset<_Nb>& 00886 set() 00887 { 00888 this->_M_do_set(); 00889 this->_M_do_sanitize(); 00890 return *this; 00891 } 00892 00893 /** 00894 * @brief Sets a given bit to a particular value. 00895 * @param pos The index of the bit. 00896 * @param val Either true or false, defaults to true. 00897 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00898 */ 00899 bitset<_Nb>& 00900 set(size_t __pos, bool __val = true) 00901 { 00902 if (__pos >= _Nb) 00903 __throw_out_of_range("bitset -- set() argument too large"); 00904 return _Unchecked_set(__pos, __val); 00905 } 00906 00907 /** 00908 * @brief Sets every bit to false. 00909 */ 00910 bitset<_Nb>& 00911 reset() 00912 { 00913 this->_M_do_reset(); 00914 return *this; 00915 } 00916 00917 /** 00918 * @brief Sets a given bit to false. 00919 * @param pos The index of the bit. 00920 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00921 * 00922 * Same as writing @c set(pos,false). 00923 */ 00924 bitset<_Nb>& 00925 reset(size_t __pos) 00926 { 00927 if (__pos >= _Nb) 00928 __throw_out_of_range("bitset -- reset() argument too large"); 00929 return _Unchecked_reset(__pos); 00930 } 00931 00932 /** 00933 * @brief Toggles every bit to its opposite value. 00934 */ 00935 bitset<_Nb>& 00936 flip() 00937 { 00938 this->_M_do_flip(); 00939 this->_M_do_sanitize(); 00940 return *this; 00941 } 00942 00943 /** 00944 * @brief Toggles a given bit to its opposite value. 00945 * @param pos The index of the bit. 00946 * @throw std::out_of_range If @a pos is bigger the size of the %set. 00947 */ 00948 bitset<_Nb>& 00949 flip(size_t __pos) 00950 { 00951 if (__pos >= _Nb) 00952 __throw_out_of_range("bitset -- flip() argument too large"); 00953 return _Unchecked_flip(__pos); 00954 } 00955 00956 /// See the no-argument flip(). 00957 bitset<_Nb> 00958 operator~() const { return bitset<_Nb>(*this).flip(); } 00959 00960 //@{ 00961 /** 00962 * @brief Array-indexing support. 00963 * @param pos Index into the %bitset. 00964 * @return A bool for a 'const %bitset'. For non-const bitsets, an 00965 * instance of the reference proxy class. 00966 * @note These operators do no range checking and throw no exceptions, 00967 * as required by DR 11 to the standard. 00968 * 00969 * @if maint 00970 * _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already 00971 * resolves DR 11 (items 1 and 2), but does not do the range-checking 00972 * required by that DR's resolution. -pme 00973 * The DR has since been changed: range-checking is a precondition 00974 * (users' responsibility), and these functions must not throw. -pme 00975 * @endif 00976 */ 00977 reference 00978 operator[](size_t __pos) { return reference(*this,__pos); } 00979 00980 bool 00981 operator[](size_t __pos) const { return _Unchecked_test(__pos); } 00982 //@} 00983 00984 /** 00985 * @brief Retuns a numerical interpretation of the %bitset. 00986 * @return The integral equivalent of the bits. 00987 * @throw std::overflow_error If there are too many bits to be 00988 * represented in an @c unsigned @c long. 00989 */ 00990 unsigned long 00991 to_ulong() const { return this->_M_do_to_ulong(); } 00992 00993 /** 00994 * @brief Retuns a character interpretation of the %bitset. 00995 * @return The string equivalent of the bits. 00996 * 00997 * Note the ordering of the bits: decreasing character positions 00998 * correspond to increasing bit positions (see the main class notes for 00999 * an example). 01000 * 01001 * Also note that you must specify the string's template parameters 01002 * explicitly. Given a bitset @c bs and a string @s: 01003 * @code 01004 * s = bs.to_string<char,char_traits<char>,allocator<char> >(); 01005 * @endcode 01006 */ 01007 template<class _CharT, class _Traits, class _Alloc> 01008 basic_string<_CharT, _Traits, _Alloc> 01009 to_string() const 01010 { 01011 basic_string<_CharT, _Traits, _Alloc> __result; 01012 _M_copy_to_string(__result); 01013 return __result; 01014 } 01015 01016 // Helper functions for string operations. 01017 template<class _CharT, class _Traits, class _Alloc> 01018 void 01019 _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 01020 size_t, size_t); 01021 01022 template<class _CharT, class _Traits, class _Alloc> 01023 void 01024 _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 01025 01026 /// Returns the number of bits which are set. 01027 size_t 01028 count() const { return this->_M_do_count(); } 01029 01030 /// Returns the total number of bits. 01031 size_t 01032 size() const { return _Nb; } 01033 01034 //@{ 01035 /// These comparisons for equality/inequality are, well, @e bitwise. 01036 bool 01037 operator==(const bitset<_Nb>& __rhs) const 01038 { return this->_M_is_equal(__rhs); } 01039 01040 bool 01041 operator!=(const bitset<_Nb>& __rhs) const 01042 { return !this->_M_is_equal(__rhs); } 01043 //@} 01044 01045 /** 01046 * @brief Tests the value of a bit. 01047 * @param pos The index of a bit. 01048 * @return The value at @a pos. 01049 * @throw std::out_of_range If @a pos is bigger the size of the %set. 01050 */ 01051 bool 01052 test(size_t __pos) const 01053 { 01054 if (__pos >= _Nb) 01055 __throw_out_of_range("bitset -- test() argument too large"); 01056 return _Unchecked_test(__pos); 01057 } 01058 01059 /** 01060 * @brief Tests whether any of the bits are on. 01061 * @return True if at least one bit is set. 01062 */ 01063 bool 01064 any() const { return this->_M_is_any(); } 01065 01066 /** 01067 * @brief Tests whether any of the bits are on. 01068 * @return True if none of the bits are set. 01069 */ 01070 bool 01071 none() const { return !this->_M_is_any(); } 01072 01073 //@{ 01074 /// Self-explanatory. 01075 bitset<_Nb> 01076 operator<<(size_t __pos) const 01077 { return bitset<_Nb>(*this) <<= __pos; } 01078 01079 bitset<_Nb> 01080 operator>>(size_t __pos) const 01081 { return bitset<_Nb>(*this) >>= __pos; } 01082 //@} 01083 01084 /** 01085 * @brief Finds the index of the first "on" bit. 01086 * @return The index of the first bit set, or size() if not found. 01087 * @ingroup SGIextensions 01088 * @sa _Find_next 01089 */ 01090 size_t 01091 _Find_first() const 01092 { return this->_M_do_find_first(_Nb); } 01093 01094 /** 01095 * @brief Finds the index of the next "on" bit after prev. 01096 * @return The index of the next bit set, or size() if not found. 01097 * @param prev Where to start searching. 01098 * @ingroup SGIextensions 01099 * @sa _Find_first 01100 */ 01101 size_t 01102 _Find_next(size_t __prev ) const 01103 { return this->_M_do_find_next(__prev, _Nb); } 01104 }; 01105 01106 // Definitions of non-inline member functions. 01107 template<size_t _Nb> 01108 template<class _CharT, class _Traits, class _Alloc> 01109 void 01110 bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 01111 { 01112 reset(); 01113 const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 01114 for (size_t __i = 0; __i < __nbits; ++__i) 01115 { 01116 switch(__s[__pos + __nbits - __i - 1]) 01117 { 01118 case '0': 01119 break; 01120 case '1': 01121 set(__i); 01122 break; 01123 default: 01124 __throw_invalid_argument("bitset -- string contains characters " 01125 "which are neither 0 nor 1"); 01126 } 01127 } 01128 } 01129 01130 template<size_t _Nb> 01131 template<class _CharT, class _Traits, class _Alloc> 01132 void 01133 bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 01134 { 01135 __s.assign(_Nb, '0'); 01136 for (size_t __i = 0; __i < _Nb; ++__i) 01137 if (_Unchecked_test(__i)) 01138 __s[_Nb - 1 - __i] = '1'; 01139 } 01140 01141 // 23.3.5.3 bitset operations: 01142 //@{ 01143 /** 01144 * @brief Global bitwise operations on bitsets. 01145 * @param x A bitset. 01146 * @param y A bitset of the same size as @a x. 01147 * @return A new bitset. 01148 * 01149 * These should be self-explanatory. 01150 */ 01151 template<size_t _Nb> 01152 inline bitset<_Nb> 01153 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01154 { 01155 bitset<_Nb> __result(__x); 01156 __result &= __y; 01157 return __result; 01158 } 01159 01160 template<size_t _Nb> 01161 inline bitset<_Nb> 01162 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01163 { 01164 bitset<_Nb> __result(__x); 01165 __result |= __y; 01166 return __result; 01167 } 01168 01169 template <size_t _Nb> 01170 inline bitset<_Nb> 01171 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 01172 { 01173 bitset<_Nb> __result(__x); 01174 __result ^= __y; 01175 return __result; 01176 } 01177 //@} 01178 01179 //@{ 01180 /** 01181 * @brief Global I/O operators for bitsets. 01182 * 01183 * Direct I/O between streams and bitsets is supported. Output is 01184 * straightforward. Input will skip whitespace, only accept '0' and '1' 01185 * characters, and will only extract as many digits as the %bitset will 01186 * hold. 01187 */ 01188 template<class _CharT, class _Traits, size_t _Nb> 01189 basic_istream<_CharT, _Traits>& 01190 operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 01191 { 01192 typedef typename _Traits::char_type char_type; 01193 basic_string<_CharT, _Traits> __tmp; 01194 __tmp.reserve(_Nb); 01195 01196 // Skip whitespace 01197 typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 01198 if (__sentry) 01199 { 01200 ios_base::iostate __state = ios_base::goodbit; 01201 basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 01202 for (size_t __i = 0; __i < _Nb; ++__i) 01203 { 01204 static typename _Traits::int_type __eof = _Traits::eof(); 01205 01206 typename _Traits::int_type __c1 = __buf->sbumpc(); 01207 if (_Traits::eq_int_type(__c1, __eof)) 01208 { 01209 __state |= ios_base::eofbit; 01210 break; 01211 } 01212 else 01213 { 01214 char_type __c2 = _Traits::to_char_type(__c1); 01215 char_type __c = __is.narrow(__c2, '*'); 01216 01217 if (__c == '0' || __c == '1') 01218 __tmp.push_back(__c); 01219 else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) 01220 { 01221 __state |= ios_base::failbit; 01222 break; 01223 } 01224 } 01225 } 01226 01227 if (__tmp.empty() && !_Nb) 01228 __state |= ios_base::failbit; 01229 else 01230 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 01231 01232 if (__state != ios_base::goodbit) 01233 __is.setstate(__state); // may throw an exception 01234 } 01235 01236 return __is; 01237 } 01238 01239 template <class _CharT, class _Traits, size_t _Nb> 01240 basic_ostream<_CharT, _Traits>& 01241 operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 01242 { 01243 basic_string<_CharT, _Traits> __tmp; 01244 __x._M_copy_to_string(__tmp); 01245 return __os << __tmp; 01246 } 01247 //@} 01248 } // namespace std 01249 01250 #undef _GLIBCPP_BITSET_WORDS 01251 01252 #endif /* _GLIBCPP_BITSET_H */

Generated on Sun Sep 19 16:33:44 2004 for libstdc++-v3 Source by doxygen 1.3.8