1 // <bitset> -*- C++ -*- 2 3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * Copyright (c) 1998 32 * Silicon Graphics Computer Systems, Inc. 33 * 34 * Permission to use, copy, modify, distribute and sell this software 35 * and its documentation for any purpose is hereby granted without fee, 36 * provided that the above copyright notice appear in all copies and 37 * that both that copyright notice and this permission notice appear 38 * in supporting documentation. Silicon Graphics makes no 39 * representations about the suitability of this software for any 40 * purpose. It is provided "as is" without express or implied warranty. 41 */ 42 43 /** @file bitset 44 * This is a Standard C++ Library header. You should @c #include this header 45 * in your programs, rather than any of the "st[dl]_*.h" implementation files. 46 */ 47 48 #ifndef _GLIBCPP_BITSET_H 49 #define _GLIBCPP_BITSET_H 50 51 #pragma GCC system_header 52 53 #include <cstddef> // for size_t 54 #include <cstring> // for memset 55 #include <string> 56 #include <bits/functexcept.h> // for invalid_argument, out_of_range, 57 // overflow_error 58 #include <ostream> // for ostream (operator<<) 59 #include <istream> // for istream (operator>>) 60 61 62 #define _GLIBCPP_BITSET_BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) 63 #define _GLIBCPP_BITSET_WORDS(__n) \ 64 ((__n) < 1 ? 1 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD) 65 66 namespace std 67 { 68 extern unsigned char _S_bit_count[256]; 69 extern unsigned char _S_first_one[256]; 70 71 /** 72 * @if maint 73 * Base class, general case. It is a class inveriant that _Nw will be 74 * nonnegative. 75 * 76 * See documentation for bitset. 77 * @endif 78 */ 79 template<size_t _Nw> 80 struct _Base_bitset 81 { 82 typedef unsigned long _WordT; 83 84 /// 0 is the least significant word. 85 _WordT _M_w[_Nw]; 86 87 _Base_bitset() { _M_do_reset(); } 88 _Base_bitset(unsigned long __val) 89 { 90 _M_do_reset(); 91 _M_w[0] = __val; 92 } 93 94 static size_t 95 _S_whichword(size_t __pos ) 96 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 97 98 static size_t 99 _S_whichbyte(size_t __pos ) 100 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 101 102 static size_t 103 _S_whichbit(size_t __pos ) 104 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 105 106 static _WordT 107 _S_maskbit(size_t __pos ) 108 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 109 110 _WordT& 111 _M_getword(size_t __pos) 112 { return _M_w[_S_whichword(__pos)]; } 113 114 _WordT 115 _M_getword(size_t __pos) const 116 { return _M_w[_S_whichword(__pos)]; } 117 118 _WordT& 119 _M_hiword() { return _M_w[_Nw - 1]; } 120 121 _WordT 122 _M_hiword() const { return _M_w[_Nw - 1]; } 123 124 void 125 _M_do_and(const _Base_bitset<_Nw>& __x) 126 { 127 for (size_t __i = 0; __i < _Nw; __i++) 128 _M_w[__i] &= __x._M_w[__i]; 129 } 130 131 void 132 _M_do_or(const _Base_bitset<_Nw>& __x) 133 { 134 for (size_t __i = 0; __i < _Nw; __i++) 135 _M_w[__i] |= __x._M_w[__i]; 136 } 137 138 void 139 _M_do_xor(const _Base_bitset<_Nw>& __x) 140 { 141 for (size_t __i = 0; __i < _Nw; __i++) 142 _M_w[__i] ^= __x._M_w[__i]; 143 } 144 145 void 146 _M_do_left_shift(size_t __shift); 147 148 void 149 _M_do_right_shift(size_t __shift); 150 151 void 152 _M_do_flip() 153 { 154 for (size_t __i = 0; __i < _Nw; __i++) 155 _M_w[__i] = ~_M_w[__i]; 156 } 157 158 void 159 _M_do_set() 160 { 161 for (size_t __i = 0; __i < _Nw; __i++) 162 _M_w[__i] = ~static_cast<_WordT>(0); 163 } 164 165 void 166 _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } 167 168 bool 169 _M_is_equal(const _Base_bitset<_Nw>& __x) const 170 { 171 for (size_t __i = 0; __i < _Nw; ++__i) 172 { 173 if (_M_w[__i] != __x._M_w[__i]) 174 return false; 175 } 176 return true; 177 } 178 179 bool 180 _M_is_any() const 181 { 182 for (size_t __i = 0; __i < _Nw; __i++) 183 { 184 if (_M_w[__i] != static_cast<_WordT>(0)) 185 return true; 186 } 187 return false; 188 } 189 190 size_t 191 _M_do_count() const 192 { 193 size_t __result = 0; 194 const unsigned char* __byte_ptr = (const unsigned char*)_M_w; 195 const unsigned char* __end_ptr = (const unsigned char*)(_M_w + _Nw); 196 197 while ( __byte_ptr < __end_ptr ) 198 { 199 __result += _S_bit_count[*__byte_ptr]; 200 __byte_ptr++; 201 } 202 return __result; 203 } 204 205 unsigned long 206 _M_do_to_ulong() const; 207 208 // find first "on" bit 209 size_t 210 _M_do_find_first(size_t __not_found) const; 211 212 // find the next "on" bit that follows "prev" 213 size_t 214 _M_do_find_next(size_t __prev, size_t __not_found) const; 215 }; 216 217 // Definitions of non-inline functions from _Base_bitset. 218 template<size_t _Nw> 219 void 220 _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 221 { 222 if (__shift != 0) 223 { 224 const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 225 const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 226 227 if (__offset == 0) 228 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 229 _M_w[__n] = _M_w[__n - __wshift]; 230 else 231 { 232 const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 233 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 234 _M_w[__n] = (_M_w[__n - __wshift] << __offset) | 235 (_M_w[__n - __wshift - 1] >> __sub_offset); 236 _M_w[__wshift] = _M_w[0] << __offset; 237 } 238 239 fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 240 } 241 } 242 243 template<size_t _Nw> 244 void 245 _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 246 { 247 if (__shift != 0) 248 { 249 const size_t __wshift = __shift / _GLIBCPP_BITSET_BITS_PER_WORD; 250 const size_t __offset = __shift % _GLIBCPP_BITSET_BITS_PER_WORD; 251 const size_t __limit = _Nw - __wshift - 1; 252 253 if (__offset == 0) 254 for (size_t __n = 0; __n <= __limit; ++__n) 255 _M_w[__n] = _M_w[__n + __wshift]; 256 else 257 { 258 const size_t __sub_offset = _GLIBCPP_BITSET_BITS_PER_WORD - __offset; 259 for (size_t __n = 0; __n < __limit; ++__n) 260 _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | 261 (_M_w[__n + __wshift + 1] << __sub_offset); 262 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 263 } 264 265 fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 266 } 267 } 268 269 template<size_t _Nw> 270 unsigned long 271 _Base_bitset<_Nw>::_M_do_to_ulong() const 272 { 273 for (size_t __i = 1; __i < _Nw; ++__i) 274 if (_M_w[__i]) 275 __throw_overflow_error("bitset -- too large to fit in unsigned long"); 276 return _M_w[0]; 277 } 278 279 template<size_t _Nw> 280 size_t 281 _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 282 { 283 for (size_t __i = 0; __i < _Nw; __i++ ) 284 { 285 _WordT __thisword = _M_w[__i]; 286 if ( __thisword != static_cast<_WordT>(0) ) 287 { 288 // find byte within word 289 for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 290 { 291 unsigned char __this_byte 292 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 293 if (__this_byte) 294 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 295 _S_first_one[__this_byte]; 296 297 __thisword >>= CHAR_BIT; 298 } 299 } 300 } 301 // not found, so return an indication of failure. 302 return __not_found; 303 } 304 305 template<size_t _Nw> 306 size_t 307 _Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 308 { 309 // make bound inclusive 310 ++__prev; 311 312 // check out of bounds 313 if ( __prev >= _Nw * _GLIBCPP_BITSET_BITS_PER_WORD ) 314 return __not_found; 315 316 // search first word 317 size_t __i = _S_whichword(__prev); 318 _WordT __thisword = _M_w[__i]; 319 320 // mask off bits below bound 321 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 322 323 if ( __thisword != static_cast<_WordT>(0) ) 324 { 325 // find byte within word 326 // get first byte into place 327 __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; 328 for (size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++) 329 { 330 unsigned char __this_byte 331 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 332 if ( __this_byte ) 333 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 334 _S_first_one[__this_byte]; 335 336 __thisword >>= CHAR_BIT; 337 } 338 } 339 340 // check subsequent words 341 __i++; 342 for ( ; __i < _Nw; __i++ ) 343 { 344 __thisword = _M_w[__i]; 345 if ( __thisword != static_cast<_WordT>(0) ) 346 { 347 // find byte within word 348 for (size_t __j = 0; __j < sizeof(_WordT); __j++ ) 349 { 350 unsigned char __this_byte 351 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 352 if ( __this_byte ) 353 return __i*_GLIBCPP_BITSET_BITS_PER_WORD + __j*CHAR_BIT + 354 _S_first_one[__this_byte]; 355 356 __thisword >>= CHAR_BIT; 357 } 358 } 359 } 360 // not found, so return an indication of failure. 361 return __not_found; 362 } // end _M_do_find_next 363 364 365 /** 366 * @if maint 367 * Base class, specialization for a single word. 368 * 369 * See documentation for bitset. 370 * @endif 371 */ 372 template<> 373 struct _Base_bitset<1> 374 { 375 typedef unsigned long _WordT; 376 _WordT _M_w; 377 378 _Base_bitset( void ) : _M_w(0) {} 379 _Base_bitset(unsigned long __val) : _M_w(__val) {} 380 381 static size_t 382 _S_whichword(size_t __pos ) 383 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 384 385 static size_t 386 _S_whichbyte(size_t __pos ) 387 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 388 389 static size_t 390 _S_whichbit(size_t __pos ) 391 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 392 393 static _WordT 394 _S_maskbit(size_t __pos ) 395 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 396 397 _WordT& 398 _M_getword(size_t) { return _M_w; } 399 400 _WordT 401 _M_getword(size_t) const { return _M_w; } 402 403 _WordT& 404 _M_hiword() { return _M_w; } 405 406 _WordT 407 _M_hiword() const { return _M_w; } 408 409 void 410 _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } 411 412 void 413 _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } 414 415 void 416 _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } 417 418 void 419 _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } 420 421 void 422 _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } 423 424 void 425 _M_do_flip() { _M_w = ~_M_w; } 426 427 void 428 _M_do_set() { _M_w = ~static_cast<_WordT>(0); } 429 430 void 431 _M_do_reset() { _M_w = 0; } 432 433 bool 434 _M_is_equal(const _Base_bitset<1>& __x) const 435 { return _M_w == __x._M_w; } 436 437 bool 438 _M_is_any() const { return _M_w != 0; } 439 440 size_t 441 _M_do_count() const 442 { 443 size_t __result = 0; 444 const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; 445 const unsigned char* __end_ptr 446 = ((const unsigned char*)&_M_w)+sizeof(_M_w); 447 while ( __byte_ptr < __end_ptr ) 448 { 449 __result += _S_bit_count[*__byte_ptr]; 450 __byte_ptr++; 451 } 452 return __result; 453 } 454 455 unsigned long 456 _M_do_to_ulong() const { return _M_w; } 457 458 size_t 459 _M_do_find_first(size_t __not_found) const; 460 461 // find the next "on" bit that follows "prev" 462 size_t 463 _M_do_find_next(size_t __prev, size_t __not_found) const; 464 }; 465 466 // Helper class to zero out the unused high-order bits in the highest word. 467 template<size_t _Extrabits> 468 struct _Sanitize 469 { 470 static void _S_do_sanitize(unsigned long& __val) 471 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 472 }; 473 474 template<> 475 struct _Sanitize<0> 476 { static void _S_do_sanitize(unsigned long) { } }; 477 478 /** 479 * @brief The %bitset class represents a @e fixed-size sequence of bits. 480 * 481 * @ingroup Containers 482 * 483 * (Note that %bitset does @e not meet the formal requirements of a 484 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 485 * 486 * The template argument, @a _Nb, may be any nonzero number of type 487 * size_t. 488 * 489 * A %bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused 490 * bits. (They are the high-order bits in the highest word.) It is 491 * a class invariant that those unused bits are always zero. 492 * 493 * If you think of %bitset as "a simple array of bits," be aware that 494 * your mental picture is reversed: a %bitset behaves the same way as 495 * bits in integers do, with the bit at index 0 in the "least significant 496 * / right-hand" position, and the bit at index N-1 in the "most 497 * significant / left-hand" position. Thus, unlike other containers, a 498 * %bitset's index "counts from right to left," to put it very loosely. 499 * 500 * This behavior is preserved when translating to and from strings. For 501 * example, the first line of the following program probably prints 502 * "b('a') is 0001100001" on a modern ASCII system. 503 * 504 * @code 505 * #include <bitset> 506 * #include <iostream> 507 * #include <sstream> 508 * 509 * using namespace std; 510 * 511 * int main() 512 * { 513 * long a = 'a'; 514 * bitset<10> b(a); 515 * 516 * cout << "b('a') is " << b << endl; 517 * 518 * ostringstream s; 519 * s << b; 520 * string str = s.str(); 521 * cout << "index 3 in the string is " << str[3] << " but\n" 522 * << "index 3 in the bitset is " << b[3] << endl; 523 * } 524 * @endcode 525 * 526 * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 527 * 528 * @if maint 529 * Most of the actual code isn't contained in %bitset<> itself, but in the 530 * base class _Base_bitset. The base class works with whole words, not with 531 * individual bits. This allows us to specialize _Base_bitset for the 532 * important special case where the %bitset is only a single word. 533 * 534 * Extra confusion can result due to the fact that the storage for 535 * _Base_bitset @e is a regular array, and is indexed as such. This is 536 * carefully encapsulated. 537 * @endif 538 */ 539 template<size_t _Nb> 540 class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 541 { 542 private: 543 typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 544 typedef unsigned long _WordT; 545 546 void 547 _M_do_sanitize() 548 { 549 _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 550 _S_do_sanitize(this->_M_hiword()); 551 } 552 553 public: 554 /** 555 * This encapsulates the concept of a single bit. An instance of this 556 * class is a proxy for an actual bit; this way the individual bit 557 * operations are done as faster word-size bitwise instructions. 558 * 559 * Most users will never need to use this class directly; conversions 560 * to and from bool are automatic and should be transparent. Overloaded 561 * operators help to preserve the illusion. 562 * 563 * (On a typical system, this "bit %reference" is 64 times the size of 564 * an actual bit. Ha.) 565 */ 566 class reference 567 { 568 friend class bitset; 569 570 _WordT *_M_wp; 571 size_t _M_bpos; 572 573 // left undefined 574 reference(); 575 576 public: 577 reference(bitset& __b, size_t __pos) 578 { 579 _M_wp = &__b._M_getword(__pos); 580 _M_bpos = _Base::_S_whichbit(__pos); 581 } 582 583 ~reference() { } 584 585 // for b[i] = __x; 586 reference& 587 operator=(bool __x) 588 { 589 if ( __x ) 590 *_M_wp |= _Base::_S_maskbit(_M_bpos); 591 else 592 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 593 return *this; 594 } 595 596 // for b[i] = b[__j]; 597 reference& 598 operator=(const reference& __j) 599 { 600 if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 601 *_M_wp |= _Base::_S_maskbit(_M_bpos); 602 else 603 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 604 return *this; 605 } 606 607 // flips the bit 608 bool 609 operator~() const 610 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 611 612 // for __x = b[i]; 613 operator bool() const 614 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 615 616 // for b[i].flip(); 617 reference& 618 flip() 619 { 620 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 621 return *this; 622 } 623 }; 624 friend class reference; 625 626 // 23.3.5.1 constructors: 627 /// All bits set to zero. 628 bitset() { } 629 630 /// Initial bits bitwise-copied from a single word (others set to zero). 631 bitset(unsigned long __val) : _Base(__val) 632 { _M_do_sanitize(); } 633 634 /** 635 * @brief Use a subset of a string. 636 * @param s A string of '0' and '1' characters. 637 * @param pos Index of the first character in @a s to use; defaults 638 * to zero. 639 * @throw std::out_of_range If @a pos is bigger the size of @a s. 640 * @throw std::invalid_argument If a character appears in the string 641 * which is neither '0' nor '1'. 642 */ 643 template<class _CharT, class _Traits, class _Alloc> 644 explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 645 size_t __pos = 0) : _Base() 646 { 647 if (__pos > __s.size()) 648 __throw_out_of_range("bitset -- initial position is larger than " 649 "the string itself"); 650 _M_copy_from_string(__s, __pos, 651 basic_string<_CharT, _Traits, _Alloc>::npos); 652 } 653 654 /** 655 * @brief Use a subset of a string. 656 * @param s A string of '0' and '1' characters. 657 * @param pos Index of the first character in @a s to use. 658 * @param n The number of characters to copy. 659 * @throw std::out_of_range If @a pos is bigger the size of @a s. 660 * @throw std::invalid_argument If a character appears in the string 661 * which is neither '0' nor '1'. 662 */ 663 template<class _CharT, class _Traits, class _Alloc> 664 bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 665 size_t __pos, size_t __n) : _Base() 666 { 667 if (__pos > __s.size()) 668 __throw_out_of_range("bitset -- initial position is larger than " 669 "the string itself"); 670 _M_copy_from_string(__s, __pos, __n); 671 } 672 673 // 23.3.5.2 bitset operations: 674 //@{ 675 /** 676 * @brief Operations on bitsets. 677 * @param rhs A same-sized bitset. 678 * 679 * These should be self-explanatory. 680 */ 681 bitset<_Nb>& 682 operator&=(const bitset<_Nb>& __rhs) 683 { 684 this->_M_do_and(__rhs); 685 return *this; 686 } 687 688 bitset<_Nb>& 689 operator|=(const bitset<_Nb>& __rhs) 690 { 691 this->_M_do_or(__rhs); 692 return *this; 693 } 694 695 bitset<_Nb>& 696 operator^=(const bitset<_Nb>& __rhs) 697 { 698 this->_M_do_xor(__rhs); 699 return *this; 700 } 701 //@} 702 703 //@{ 704 /** 705 * @brief Operations on bitsets. 706 * @param pos The number of places to shift. 707 * 708 * These should be self-explanatory. 709 */ 710 bitset<_Nb>& 711 operator<<=(size_t __pos) 712 { 713 this->_M_do_left_shift(__pos); 714 this->_M_do_sanitize(); 715 return *this; 716 } 717 718 bitset<_Nb>& 719 operator>>=(size_t __pos) 720 { 721 this->_M_do_right_shift(__pos); 722 this->_M_do_sanitize(); 723 return *this; 724 } 725 //@} 726 727 //@{ 728 /** 729 * These versions of single-bit set, reset, flip, and test are 730 * extensions from the SGI version. They do no range checking. 731 * @ingroup SGIextensions 732 */ 733 bitset<_Nb>& 734 _Unchecked_set(size_t __pos) 735 { 736 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 737 return *this; 738 } 739 740 bitset<_Nb>& 741 _Unchecked_set(size_t __pos, int __val) 742 { 743 if (__val) 744 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 745 else 746 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 747 return *this; 748 } 749 750 bitset<_Nb>& 751 _Unchecked_reset(size_t __pos) 752 { 753 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 754 return *this; 755 } 756 757 bitset<_Nb>& 758 _Unchecked_flip(size_t __pos) 759 { 760 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 761 return *this; 762 } 763 764 bool 765 _Unchecked_test(size_t __pos) const 766 { 767 return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 768 != static_cast<_WordT>(0); 769 } 770 //@} 771 772 // Set, reset, and flip. 773 /** 774 * @brief Sets every bit to true. 775 */ 776 bitset<_Nb>& 777 set() 778 { 779 this->_M_do_set(); 780 this->_M_do_sanitize(); 781 return *this; 782 } 783 784 /** 785 * @brief Sets a given bit to a particular value. 786 * @param pos The index of the bit. 787 * @param val Either true or false, defaults to true. 788 * @throw std::out_of_range If @a pos is bigger the size of the %set. 789 */ 790 bitset<_Nb>& 791 set(size_t __pos, bool __val = true) 792 { 793 if (__pos >= _Nb) 794 __throw_out_of_range("bitset -- set() argument too large"); 795 return _Unchecked_set(__pos, __val); 796 } 797 798 /** 799 * @brief Sets every bit to false. 800 */ 801 bitset<_Nb>& 802 reset() 803 { 804 this->_M_do_reset(); 805 return *this; 806 } 807 808 /** 809 * @brief Sets a given bit to false. 810 * @param pos The index of the bit. 811 * @throw std::out_of_range If @a pos is bigger the size of the %set. 812 * 813 * Same as writing @c set(pos,false). 814 */ 815 bitset<_Nb>& 816 reset(size_t __pos) 817 { 818 if (__pos >= _Nb) 819 __throw_out_of_range("bitset -- reset() argument too large"); 820 return _Unchecked_reset(__pos); 821 } 822 823 /** 824 * @brief Toggles every bit to its opposite value. 825 */ 826 bitset<_Nb>& 827 flip() 828 { 829 this->_M_do_flip(); 830 this->_M_do_sanitize(); 831 return *this; 832 } 833 834 /** 835 * @brief Toggles a given bit to its opposite value. 836 * @param pos The index of the bit. 837 * @throw std::out_of_range If @a pos is bigger the size of the %set. 838 */ 839 bitset<_Nb>& 840 flip(size_t __pos) 841 { 842 if (__pos >= _Nb) 843 __throw_out_of_range("bitset -- flip() argument too large"); 844 return _Unchecked_flip(__pos); 845 } 846 847 /// See the no-argument flip(). 848 bitset<_Nb> 849 operator~() const { return bitset<_Nb>(*this).flip(); } 850 851 //@{ 852 /** 853 * @brief Array-indexing support. 854 * @param pos Index into the %bitset. 855 * @return A bool for a 'const %bitset'. For non-const bitsets, an 856 * instance of the reference proxy class. 857 * @note These operators do no range checking and throw no exceptions, 858 * as required by DR 11 to the standard. 859 * 860 * @if maint 861 * _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already 862 * resolves DR 11 (items 1 and 2), but does not do the range-checking 863 * required by that DR's resolution. -pme 864 * The DR has since been changed: range-checking is a precondition 865 * (users' responsibility), and these functions must not throw. -pme 866 * @endif 867 */ 868 reference 869 operator[](size_t __pos) { return reference(*this,__pos); } 870 871 bool 872 operator[](size_t __pos) const { return _Unchecked_test(__pos); } 873 //@} 874 875 /** 876 * @brief Retuns a numerical interpretation of the %bitset. 877 * @return The integral equivalent of the bits. 878 * @throw std::overflow_error If there are too many bits to be 879 * represented in an @c unsigned @c long. 880 */ 881 unsigned long 882 to_ulong() const { return this->_M_do_to_ulong(); } 883 884 /** 885 * @brief Retuns a character interpretation of the %bitset. 886 * @return The string equivalent of the bits. 887 * 888 * Note the ordering of the bits: decreasing character positions 889 * correspond to increasing bit positions (see the main class notes for 890 * an example). 891 * 892 * Also note that you must specify the string's template parameters 893 * explicitly. Given a bitset @c bs and a string @s: 894 * @code 895 * s = bs.to_string<char,char_traits<char>,allocator<char> >(); 896 * @endcode 897 */ 898 template<class _CharT, class _Traits, class _Alloc> 899 basic_string<_CharT, _Traits, _Alloc> 900 to_string() const 901 { 902 basic_string<_CharT, _Traits, _Alloc> __result; 903 _M_copy_to_string(__result); 904 return __result; 905 } 906 907 // Helper functions for string operations. 908 template<class _CharT, class _Traits, class _Alloc> 909 void 910 _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 911 size_t, size_t); 912 913 template<class _CharT, class _Traits, class _Alloc> 914 void 915 _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 916 917 /// Returns the number of bits which are set. 918 size_t 919 count() const { return this->_M_do_count(); } 920 921 /// Returns the total number of bits. 922 size_t 923 size() const { return _Nb; } 924 925 //@{ 926 /// These comparisons for equality/inequality are, well, @e bitwise. 927 bool 928 operator==(const bitset<_Nb>& __rhs) const 929 { return this->_M_is_equal(__rhs); } 930 931 bool 932 operator!=(const bitset<_Nb>& __rhs) const 933 { return !this->_M_is_equal(__rhs); } 934 //@} 935 936 /** 937 * @brief Tests the value of a bit. 938 * @param pos The index of a bit. 939 * @return The value at @a pos. 940 * @throw std::out_of_range If @a pos is bigger the size of the %set. 941 */ 942 bool 943 test(size_t __pos) const 944 { 945 if (__pos >= _Nb) 946 __throw_out_of_range("bitset -- test() argument too large"); 947 return _Unchecked_test(__pos); 948 } 949 950 /** 951 * @brief Tests whether any of the bits are on. 952 * @return True if at least one bit is set. 953 */ 954 bool 955 any() const { return this->_M_is_any(); } 956 957 /** 958 * @brief Tests whether any of the bits are on. 959 * @return True if none of the bits are set. 960 */ 961 bool 962 none() const { return !this->_M_is_any(); } 963 964 //@{ 965 /// Self-explanatory. 966 bitset<_Nb> 967 operator<<(size_t __pos) const 968 { return bitset<_Nb>(*this) <<= __pos; } 969 970 bitset<_Nb> 971 operator>>(size_t __pos) const 972 { return bitset<_Nb>(*this) >>= __pos; } 973 //@} 974 975 /** 976 * @brief Finds the index of the first "on" bit. 977 * @return The index of the first bit set, or size() if not found. 978 * @ingroup SGIextensions 979 * @sa _Find_next 980 */ 981 size_t 982 _Find_first() const 983 { return this->_M_do_find_first(_Nb); } 984 985 /** 986 * @brief Finds the index of the next "on" bit after prev. 987 * @return The index of the next bit set, or size() if not found. 988 * @param prev Where to start searching. 989 * @ingroup SGIextensions 990 * @sa _Find_first 991 */ 992 size_t 993 _Find_next(size_t __prev ) const 994 { return this->_M_do_find_next(__prev, _Nb); } 995 }; 996 997 // Definitions of non-inline member functions. 998 template<size_t _Nb> 999 template<class _CharT, class _Traits, class _Alloc> 1000 void 1001 bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 1002 { 1003 reset(); 1004 const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 1005 for (size_t __i = 0; __i < __nbits; ++__i) 1006 { 1007 switch(__s[__pos + __nbits - __i - 1]) 1008 { 1009 case '0': 1010 break; 1011 case '1': 1012 set(__i); 1013 break; 1014 default: 1015 __throw_invalid_argument("bitset -- string contains characters " 1016 "which are neither 0 nor 1"); 1017 } 1018 } 1019 } 1020 1021 template<size_t _Nb> 1022 template<class _CharT, class _Traits, class _Alloc> 1023 void 1024 bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 1025 { 1026 __s.assign(_Nb, '0'); 1027 for (size_t __i = 0; __i < _Nb; ++__i) 1028 if (_Unchecked_test(__i)) 1029 __s[_Nb - 1 - __i] = '1'; 1030 } 1031 1032 // 23.3.5.3 bitset operations: 1033 //@{ 1034 /** 1035 * @brief Global bitwise operations on bitsets. 1036 * @param x A bitset. 1037 * @param y A bitset of the same size as @a x. 1038 * @return A new bitset. 1039 * 1040 * These should be self-explanatory. 1041 */ 1042 template<size_t _Nb> 1043 inline bitset<_Nb> 1044 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1045 { 1046 bitset<_Nb> __result(__x); 1047 __result &= __y; 1048 return __result; 1049 } 1050 1051 template<size_t _Nb> 1052 inline bitset<_Nb> 1053 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1054 { 1055 bitset<_Nb> __result(__x); 1056 __result |= __y; 1057 return __result; 1058 } 1059 1060 template <size_t _Nb> 1061 inline bitset<_Nb> 1062 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1063 { 1064 bitset<_Nb> __result(__x); 1065 __result ^= __y; 1066 return __result; 1067 } 1068 //@} 1069 1070 //@{ 1071 /** 1072 * @brief Global I/O operators for bitsets. 1073 * 1074 * Direct I/O between streams and bitsets is supported. Output is 1075 * straightforward. Input will skip whitespace, only accept '0' and '1' 1076 * characters, and will only extract as many digits as the %bitset will 1077 * hold. 1078 */ 1079 template<class _CharT, class _Traits, size_t _Nb> 1080 basic_istream<_CharT, _Traits>& 1081 operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1082 { 1083 typedef typename _Traits::char_type char_type; 1084 basic_string<_CharT, _Traits> __tmp; 1085 __tmp.reserve(_Nb); 1086 1087 // Skip whitespace 1088 typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 1089 if (__sentry) 1090 { 1091 basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 1092 for (size_t __i = 0; __i < _Nb; ++__i) 1093 { 1094 static typename _Traits::int_type __eof = _Traits::eof(); 1095 1096 typename _Traits::int_type __c1 = __buf->sbumpc(); 1097 if (_Traits::eq_int_type(__c1, __eof)) 1098 { 1099 __is.setstate(ios_base::eofbit); 1100 break; 1101 } 1102 else 1103 { 1104 char_type __c2 = _Traits::to_char_type(__c1); 1105 char_type __c = __is.narrow(__c2, '*'); 1106 1107 if (__c == '0' || __c == '1') 1108 __tmp.push_back(__c); 1109 else if (_Traits::eq_int_type(__buf->sputbackc(__c2), 1110 __eof)) 1111 { 1112 __is.setstate(ios_base::failbit); 1113 break; 1114 } 1115 } 1116 } 1117 1118 if (__tmp.empty()) 1119 __is.setstate(ios_base::failbit); 1120 else 1121 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 1122 } 1123 1124 return __is; 1125 } 1126 1127 template <class _CharT, class _Traits, size_t _Nb> 1128 basic_ostream<_CharT, _Traits>& 1129 operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 1130 { 1131 basic_string<_CharT, _Traits> __tmp; 1132 __x._M_copy_to_string(__tmp); 1133 return __os << __tmp; 1134 } 1135 //@} 1136 } // namespace std 1137 1138 #undef _GLIBCPP_BITSET_WORDS 1139 1140 #endif /* _GLIBCPP_BITSET_H */ 1141