std_bitset.h revision 102782
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 ? 0 : ((__n) + _GLIBCPP_BITSET_BITS_PER_WORD - 1)/_GLIBCPP_BITSET_BITS_PER_WORD) 65 66namespace 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 467 /** 468 * @if maint 469 * Base class, specialization for no storage (zero-length %bitset). 470 * 471 * See documentation for bitset. 472 * @endif 473 */ 474 template<> 475 struct _Base_bitset<0> 476 { 477 typedef unsigned long _WordT; 478 479 _Base_bitset() {} 480 _Base_bitset(unsigned long) {} 481 482 static size_t 483 _S_whichword(size_t __pos ) 484 { return __pos / _GLIBCPP_BITSET_BITS_PER_WORD; } 485 486 static size_t 487 _S_whichbyte(size_t __pos ) 488 { return (__pos % _GLIBCPP_BITSET_BITS_PER_WORD) / CHAR_BIT; } 489 490 static size_t 491 _S_whichbit(size_t __pos ) 492 { return __pos % _GLIBCPP_BITSET_BITS_PER_WORD; } 493 494 static _WordT 495 _S_maskbit(size_t __pos ) 496 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 497 498 // This would normally give access to the data. The bounds-checking 499 // in the bitset class will prevent the user from getting this far, 500 // but (1) it must still return an lvalue to compile, and (2) the 501 // user might call _Unchecked_set directly, in which case this /needs/ 502 // to fail. Let's not penalize zero-length users unless they actually 503 // make an unchecked call; all the memory ugliness is therefore 504 // localized to this single should-never-get-this-far function. 505 _WordT& 506 _M_getword(size_t) const 507 { __throw_out_of_range("bitset -- zero-length"); return *new _WordT; } 508 509 _WordT 510 _M_hiword() const { return 0; } 511 512 void 513 _M_do_and(const _Base_bitset<0>&) { } 514 515 void 516 _M_do_or(const _Base_bitset<0>&) { } 517 518 void 519 _M_do_xor(const _Base_bitset<0>&) { } 520 521 void 522 _M_do_left_shift(size_t) { } 523 524 void 525 _M_do_right_shift(size_t) { } 526 527 void 528 _M_do_flip() { } 529 530 void 531 _M_do_set() { } 532 533 void 534 _M_do_reset() { } 535 536 // Are all empty bitsets equal to each other? Are they equal to 537 // themselves? How to compare a thing which has no state? What is 538 // the sound of one zero-length bitset clapping? 539 bool 540 _M_is_equal(const _Base_bitset<0>&) const { return true; } 541 542 bool 543 _M_is_any() const { return false; } 544 545 size_t 546 _M_do_count() const { return 0; } 547 548 unsigned long 549 _M_do_to_ulong() const { return 0; } 550 551 // Normally "not found" is the size, but that could also be 552 // misinterpreted as an index in this corner case. Oh well. 553 size_t 554 _M_do_find_first(size_t) const { return 0; } 555 556 size_t 557 _M_do_find_next(size_t, size_t) const { return 0; } 558 }; 559 560 561 // Helper class to zero out the unused high-order bits in the highest word. 562 template<size_t _Extrabits> 563 struct _Sanitize 564 { 565 static void _S_do_sanitize(unsigned long& __val) 566 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 567 }; 568 569 template<> 570 struct _Sanitize<0> 571 { static void _S_do_sanitize(unsigned long) { } }; 572 573 /** 574 * @brief The %bitset class represents a @e fixed-size sequence of bits. 575 * 576 * @ingroup Containers 577 * 578 * (Note that %bitset does @e not meet the formal requirements of a 579 * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) 580 * 581 * The template argument, @a _Nb, may be any nonzero number of type 582 * size_t. 583 * 584 * A %bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused 585 * bits. (They are the high-order bits in the highest word.) It is 586 * a class invariant that those unused bits are always zero. 587 * 588 * If you think of %bitset as "a simple array of bits," be aware that 589 * your mental picture is reversed: a %bitset behaves the same way as 590 * bits in integers do, with the bit at index 0 in the "least significant 591 * / right-hand" position, and the bit at index N-1 in the "most 592 * significant / left-hand" position. Thus, unlike other containers, a 593 * %bitset's index "counts from right to left," to put it very loosely. 594 * 595 * This behavior is preserved when translating to and from strings. For 596 * example, the first line of the following program probably prints 597 * "b('a') is 0001100001" on a modern ASCII system. 598 * 599 * @code 600 * #include <bitset> 601 * #include <iostream> 602 * #include <sstream> 603 * 604 * using namespace std; 605 * 606 * int main() 607 * { 608 * long a = 'a'; 609 * bitset<10> b(a); 610 * 611 * cout << "b('a') is " << b << endl; 612 * 613 * ostringstream s; 614 * s << b; 615 * string str = s.str(); 616 * cout << "index 3 in the string is " << str[3] << " but\n" 617 * << "index 3 in the bitset is " << b[3] << endl; 618 * } 619 * @endcode 620 * 621 * Also see http://gcc.gnu.org/onlinedocs/libstdc++/ext/sgiexts.html#ch23 622 * 623 * @if maint 624 * Most of the actual code isn't contained in %bitset<> itself, but in the 625 * base class _Base_bitset. The base class works with whole words, not with 626 * individual bits. This allows us to specialize _Base_bitset for the 627 * important special case where the %bitset is only a single word. 628 * 629 * Extra confusion can result due to the fact that the storage for 630 * _Base_bitset @e is a regular array, and is indexed as such. This is 631 * carefully encapsulated. 632 * @endif 633 */ 634 template<size_t _Nb> 635 class bitset : private _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> 636 { 637 private: 638 typedef _Base_bitset<_GLIBCPP_BITSET_WORDS(_Nb)> _Base; 639 typedef unsigned long _WordT; 640 641 void 642 _M_do_sanitize() 643 { 644 _Sanitize<_Nb%_GLIBCPP_BITSET_BITS_PER_WORD>:: 645 _S_do_sanitize(this->_M_hiword()); 646 } 647 648 public: 649 /** 650 * This encapsulates the concept of a single bit. An instance of this 651 * class is a proxy for an actual bit; this way the individual bit 652 * operations are done as faster word-size bitwise instructions. 653 * 654 * Most users will never need to use this class directly; conversions 655 * to and from bool are automatic and should be transparent. Overloaded 656 * operators help to preserve the illusion. 657 * 658 * (On a typical system, this "bit %reference" is 64 times the size of 659 * an actual bit. Ha.) 660 */ 661 class reference 662 { 663 friend class bitset; 664 665 _WordT *_M_wp; 666 size_t _M_bpos; 667 668 // left undefined 669 reference(); 670 671 public: 672 reference(bitset& __b, size_t __pos) 673 { 674 _M_wp = &__b._M_getword(__pos); 675 _M_bpos = _Base::_S_whichbit(__pos); 676 } 677 678 ~reference() { } 679 680 // for b[i] = __x; 681 reference& 682 operator=(bool __x) 683 { 684 if ( __x ) 685 *_M_wp |= _Base::_S_maskbit(_M_bpos); 686 else 687 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 688 return *this; 689 } 690 691 // for b[i] = b[__j]; 692 reference& 693 operator=(const reference& __j) 694 { 695 if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 696 *_M_wp |= _Base::_S_maskbit(_M_bpos); 697 else 698 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 699 return *this; 700 } 701 702 // flips the bit 703 bool 704 operator~() const 705 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 706 707 // for __x = b[i]; 708 operator bool() const 709 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 710 711 // for b[i].flip(); 712 reference& 713 flip() 714 { 715 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 716 return *this; 717 } 718 }; 719 friend class reference; 720 721 // 23.3.5.1 constructors: 722 /// All bits set to zero. 723 bitset() { } 724 725 /// Initial bits bitwise-copied from a single word (others set to zero). 726 bitset(unsigned long __val) : _Base(__val) 727 { _M_do_sanitize(); } 728 729 /** 730 * @brief Use a subset of a string. 731 * @param s A string of '0' and '1' characters. 732 * @param pos Index of the first character in @a s to use; defaults 733 * to zero. 734 * @throw std::out_of_range If @a pos is bigger the size of @a s. 735 * @throw std::invalid_argument If a character appears in the string 736 * which is neither '0' nor '1'. 737 */ 738 template<class _CharT, class _Traits, class _Alloc> 739 explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 740 size_t __pos = 0) : _Base() 741 { 742 if (__pos > __s.size()) 743 __throw_out_of_range("bitset -- initial position is larger than " 744 "the string itself"); 745 _M_copy_from_string(__s, __pos, 746 basic_string<_CharT, _Traits, _Alloc>::npos); 747 } 748 749 /** 750 * @brief Use a subset of a string. 751 * @param s A string of '0' and '1' characters. 752 * @param pos Index of the first character in @a s to use. 753 * @param n The number of characters to copy. 754 * @throw std::out_of_range If @a pos is bigger the size of @a s. 755 * @throw std::invalid_argument If a character appears in the string 756 * which is neither '0' nor '1'. 757 */ 758 template<class _CharT, class _Traits, class _Alloc> 759 bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 760 size_t __pos, size_t __n) : _Base() 761 { 762 if (__pos > __s.size()) 763 __throw_out_of_range("bitset -- initial position is larger than " 764 "the string itself"); 765 _M_copy_from_string(__s, __pos, __n); 766 } 767 768 // 23.3.5.2 bitset operations: 769 //@{ 770 /** 771 * @brief Operations on bitsets. 772 * @param rhs A same-sized bitset. 773 * 774 * These should be self-explanatory. 775 */ 776 bitset<_Nb>& 777 operator&=(const bitset<_Nb>& __rhs) 778 { 779 this->_M_do_and(__rhs); 780 return *this; 781 } 782 783 bitset<_Nb>& 784 operator|=(const bitset<_Nb>& __rhs) 785 { 786 this->_M_do_or(__rhs); 787 return *this; 788 } 789 790 bitset<_Nb>& 791 operator^=(const bitset<_Nb>& __rhs) 792 { 793 this->_M_do_xor(__rhs); 794 return *this; 795 } 796 //@} 797 798 //@{ 799 /** 800 * @brief Operations on bitsets. 801 * @param pos The number of places to shift. 802 * 803 * These should be self-explanatory. 804 */ 805 bitset<_Nb>& 806 operator<<=(size_t __pos) 807 { 808 this->_M_do_left_shift(__pos); 809 this->_M_do_sanitize(); 810 return *this; 811 } 812 813 bitset<_Nb>& 814 operator>>=(size_t __pos) 815 { 816 this->_M_do_right_shift(__pos); 817 this->_M_do_sanitize(); 818 return *this; 819 } 820 //@} 821 822 //@{ 823 /** 824 * These versions of single-bit set, reset, flip, and test are 825 * extensions from the SGI version. They do no range checking. 826 * @ingroup SGIextensions 827 */ 828 bitset<_Nb>& 829 _Unchecked_set(size_t __pos) 830 { 831 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 832 return *this; 833 } 834 835 bitset<_Nb>& 836 _Unchecked_set(size_t __pos, int __val) 837 { 838 if (__val) 839 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 840 else 841 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 842 return *this; 843 } 844 845 bitset<_Nb>& 846 _Unchecked_reset(size_t __pos) 847 { 848 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 849 return *this; 850 } 851 852 bitset<_Nb>& 853 _Unchecked_flip(size_t __pos) 854 { 855 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 856 return *this; 857 } 858 859 bool 860 _Unchecked_test(size_t __pos) const 861 { 862 return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 863 != static_cast<_WordT>(0); 864 } 865 //@} 866 867 // Set, reset, and flip. 868 /** 869 * @brief Sets every bit to true. 870 */ 871 bitset<_Nb>& 872 set() 873 { 874 this->_M_do_set(); 875 this->_M_do_sanitize(); 876 return *this; 877 } 878 879 /** 880 * @brief Sets a given bit to a particular value. 881 * @param pos The index of the bit. 882 * @param val Either true or false, defaults to true. 883 * @throw std::out_of_range If @a pos is bigger the size of the %set. 884 */ 885 bitset<_Nb>& 886 set(size_t __pos, bool __val = true) 887 { 888 if (__pos >= _Nb) 889 __throw_out_of_range("bitset -- set() argument too large"); 890 return _Unchecked_set(__pos, __val); 891 } 892 893 /** 894 * @brief Sets every bit to false. 895 */ 896 bitset<_Nb>& 897 reset() 898 { 899 this->_M_do_reset(); 900 return *this; 901 } 902 903 /** 904 * @brief Sets a given bit to false. 905 * @param pos The index of the bit. 906 * @throw std::out_of_range If @a pos is bigger the size of the %set. 907 * 908 * Same as writing @c set(pos,false). 909 */ 910 bitset<_Nb>& 911 reset(size_t __pos) 912 { 913 if (__pos >= _Nb) 914 __throw_out_of_range("bitset -- reset() argument too large"); 915 return _Unchecked_reset(__pos); 916 } 917 918 /** 919 * @brief Toggles every bit to its opposite value. 920 */ 921 bitset<_Nb>& 922 flip() 923 { 924 this->_M_do_flip(); 925 this->_M_do_sanitize(); 926 return *this; 927 } 928 929 /** 930 * @brief Toggles a given bit to its opposite value. 931 * @param pos The index of the bit. 932 * @throw std::out_of_range If @a pos is bigger the size of the %set. 933 */ 934 bitset<_Nb>& 935 flip(size_t __pos) 936 { 937 if (__pos >= _Nb) 938 __throw_out_of_range("bitset -- flip() argument too large"); 939 return _Unchecked_flip(__pos); 940 } 941 942 /// See the no-argument flip(). 943 bitset<_Nb> 944 operator~() const { return bitset<_Nb>(*this).flip(); } 945 946 //@{ 947 /** 948 * @brief Array-indexing support. 949 * @param pos Index into the %bitset. 950 * @return A bool for a 'const %bitset'. For non-const bitsets, an 951 * instance of the reference proxy class. 952 * @note These operators do no range checking and throw no exceptions, 953 * as required by DR 11 to the standard. 954 * 955 * @if maint 956 * _GLIBCPP_RESOLVE_LIB_DEFECTS Note that this implementation already 957 * resolves DR 11 (items 1 and 2), but does not do the range-checking 958 * required by that DR's resolution. -pme 959 * The DR has since been changed: range-checking is a precondition 960 * (users' responsibility), and these functions must not throw. -pme 961 * @endif 962 */ 963 reference 964 operator[](size_t __pos) { return reference(*this,__pos); } 965 966 bool 967 operator[](size_t __pos) const { return _Unchecked_test(__pos); } 968 //@} 969 970 /** 971 * @brief Retuns a numerical interpretation of the %bitset. 972 * @return The integral equivalent of the bits. 973 * @throw std::overflow_error If there are too many bits to be 974 * represented in an @c unsigned @c long. 975 */ 976 unsigned long 977 to_ulong() const { return this->_M_do_to_ulong(); } 978 979 /** 980 * @brief Retuns a character interpretation of the %bitset. 981 * @return The string equivalent of the bits. 982 * 983 * Note the ordering of the bits: decreasing character positions 984 * correspond to increasing bit positions (see the main class notes for 985 * an example). 986 * 987 * Also note that you must specify the string's template parameters 988 * explicitly. Given a bitset @c bs and a string @s: 989 * @code 990 * s = bs.to_string<char,char_traits<char>,allocator<char> >(); 991 * @endcode 992 */ 993 template<class _CharT, class _Traits, class _Alloc> 994 basic_string<_CharT, _Traits, _Alloc> 995 to_string() const 996 { 997 basic_string<_CharT, _Traits, _Alloc> __result; 998 _M_copy_to_string(__result); 999 return __result; 1000 } 1001 1002 // Helper functions for string operations. 1003 template<class _CharT, class _Traits, class _Alloc> 1004 void 1005 _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 1006 size_t, size_t); 1007 1008 template<class _CharT, class _Traits, class _Alloc> 1009 void 1010 _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 1011 1012 /// Returns the number of bits which are set. 1013 size_t 1014 count() const { return this->_M_do_count(); } 1015 1016 /// Returns the total number of bits. 1017 size_t 1018 size() const { return _Nb; } 1019 1020 //@{ 1021 /// These comparisons for equality/inequality are, well, @e bitwise. 1022 bool 1023 operator==(const bitset<_Nb>& __rhs) const 1024 { return this->_M_is_equal(__rhs); } 1025 1026 bool 1027 operator!=(const bitset<_Nb>& __rhs) const 1028 { return !this->_M_is_equal(__rhs); } 1029 //@} 1030 1031 /** 1032 * @brief Tests the value of a bit. 1033 * @param pos The index of a bit. 1034 * @return The value at @a pos. 1035 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1036 */ 1037 bool 1038 test(size_t __pos) const 1039 { 1040 if (__pos >= _Nb) 1041 __throw_out_of_range("bitset -- test() argument too large"); 1042 return _Unchecked_test(__pos); 1043 } 1044 1045 /** 1046 * @brief Tests whether any of the bits are on. 1047 * @return True if at least one bit is set. 1048 */ 1049 bool 1050 any() const { return this->_M_is_any(); } 1051 1052 /** 1053 * @brief Tests whether any of the bits are on. 1054 * @return True if none of the bits are set. 1055 */ 1056 bool 1057 none() const { return !this->_M_is_any(); } 1058 1059 //@{ 1060 /// Self-explanatory. 1061 bitset<_Nb> 1062 operator<<(size_t __pos) const 1063 { return bitset<_Nb>(*this) <<= __pos; } 1064 1065 bitset<_Nb> 1066 operator>>(size_t __pos) const 1067 { return bitset<_Nb>(*this) >>= __pos; } 1068 //@} 1069 1070 /** 1071 * @brief Finds the index of the first "on" bit. 1072 * @return The index of the first bit set, or size() if not found. 1073 * @ingroup SGIextensions 1074 * @sa _Find_next 1075 */ 1076 size_t 1077 _Find_first() const 1078 { return this->_M_do_find_first(_Nb); } 1079 1080 /** 1081 * @brief Finds the index of the next "on" bit after prev. 1082 * @return The index of the next bit set, or size() if not found. 1083 * @param prev Where to start searching. 1084 * @ingroup SGIextensions 1085 * @sa _Find_first 1086 */ 1087 size_t 1088 _Find_next(size_t __prev ) const 1089 { return this->_M_do_find_next(__prev, _Nb); } 1090 }; 1091 1092 // Definitions of non-inline member functions. 1093 template<size_t _Nb> 1094 template<class _CharT, class _Traits, class _Alloc> 1095 void 1096 bitset<_Nb>::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, size_t __pos, size_t __n) 1097 { 1098 reset(); 1099 const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 1100 for (size_t __i = 0; __i < __nbits; ++__i) 1101 { 1102 switch(__s[__pos + __nbits - __i - 1]) 1103 { 1104 case '0': 1105 break; 1106 case '1': 1107 set(__i); 1108 break; 1109 default: 1110 __throw_invalid_argument("bitset -- string contains characters " 1111 "which are neither 0 nor 1"); 1112 } 1113 } 1114 } 1115 1116 template<size_t _Nb> 1117 template<class _CharT, class _Traits, class _Alloc> 1118 void 1119 bitset<_Nb>::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 1120 { 1121 __s.assign(_Nb, '0'); 1122 for (size_t __i = 0; __i < _Nb; ++__i) 1123 if (_Unchecked_test(__i)) 1124 __s[_Nb - 1 - __i] = '1'; 1125 } 1126 1127 // 23.3.5.3 bitset operations: 1128 //@{ 1129 /** 1130 * @brief Global bitwise operations on bitsets. 1131 * @param x A bitset. 1132 * @param y A bitset of the same size as @a x. 1133 * @return A new bitset. 1134 * 1135 * These should be self-explanatory. 1136 */ 1137 template<size_t _Nb> 1138 inline bitset<_Nb> 1139 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1140 { 1141 bitset<_Nb> __result(__x); 1142 __result &= __y; 1143 return __result; 1144 } 1145 1146 template<size_t _Nb> 1147 inline bitset<_Nb> 1148 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1149 { 1150 bitset<_Nb> __result(__x); 1151 __result |= __y; 1152 return __result; 1153 } 1154 1155 template <size_t _Nb> 1156 inline bitset<_Nb> 1157 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) 1158 { 1159 bitset<_Nb> __result(__x); 1160 __result ^= __y; 1161 return __result; 1162 } 1163 //@} 1164 1165 //@{ 1166 /** 1167 * @brief Global I/O operators for bitsets. 1168 * 1169 * Direct I/O between streams and bitsets is supported. Output is 1170 * straightforward. Input will skip whitespace, only accept '0' and '1' 1171 * characters, and will only extract as many digits as the %bitset will 1172 * hold. 1173 */ 1174 template<class _CharT, class _Traits, size_t _Nb> 1175 basic_istream<_CharT, _Traits>& 1176 operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1177 { 1178 typedef typename _Traits::char_type char_type; 1179 basic_string<_CharT, _Traits> __tmp; 1180 __tmp.reserve(_Nb); 1181 1182 // Skip whitespace 1183 typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 1184 if (__sentry) 1185 { 1186 basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 1187 for (size_t __i = 0; __i < _Nb; ++__i) 1188 { 1189 static typename _Traits::int_type __eof = _Traits::eof(); 1190 1191 typename _Traits::int_type __c1 = __buf->sbumpc(); 1192 if (_Traits::eq_int_type(__c1, __eof)) 1193 { 1194 __is.setstate(ios_base::eofbit); 1195 break; 1196 } 1197 else 1198 { 1199 char_type __c2 = _Traits::to_char_type(__c1); 1200 char_type __c = __is.narrow(__c2, '*'); 1201 1202 if (__c == '0' || __c == '1') 1203 __tmp.push_back(__c); 1204 else if (_Traits::eq_int_type(__buf->sputbackc(__c2), 1205 __eof)) 1206 { 1207 __is.setstate(ios_base::failbit); 1208 break; 1209 } 1210 } 1211 } 1212 1213 if (__tmp.empty() && !_Nb) 1214 __is.setstate(ios_base::failbit); 1215 else 1216 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 1217 } 1218 1219 return __is; 1220 } 1221 1222 template <class _CharT, class _Traits, size_t _Nb> 1223 basic_ostream<_CharT, _Traits>& 1224 operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 1225 { 1226 basic_string<_CharT, _Traits> __tmp; 1227 __x._M_copy_to_string(__tmp); 1228 return __os << __tmp; 1229 } 1230 //@} 1231} // namespace std 1232 1233#undef _GLIBCPP_BITSET_WORDS 1234 1235#endif /* _GLIBCPP_BITSET_H */ 1236