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

Generated on Wed Jun 9 11:18:16 2004 for libstdc++-v3 Source by doxygen 1.3.7