bitset

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

Generated on Tue Sep 7 10:05:01 2004 for libstdc++-v3 Source by doxygen 1.3.8