1/* 2 * Copyright (c) 1998 3 * Silicon Graphics Computer Systems, Inc. 4 * 5 * Permission to use, copy, modify, distribute and sell this software 6 * and its documentation for any purpose is hereby granted without fee, 7 * provided that the above copyright notice appear in all copies and 8 * that both that copyright notice and this permission notice appear 9 * in supporting documentation. Silicon Graphics makes no 10 * representations about the suitability of this software for any 11 * purpose. It is provided "as is" without express or implied warranty. 12 */ 13 14#ifndef __SGI_STL_BITSET 15#define __SGI_STL_BITSET 16 17// A bitset of size N has N % (sizeof(unsigned long) * CHAR_BIT) unused 18// bits. (They are the high- order bits in the highest word.) It is 19// a class invariant of class bitset<> that those unused bits are 20// always zero. 21 22// Most of the actual code isn't contained in bitset<> itself, but in the 23// base class _Base_bitset. The base class works with whole words, not with 24// individual bits. This allows us to specialize _Base_bitset for the 25// important special case where the bitset is only a single word. 26 27// The C++ standard does not define the precise semantics of operator[]. 28// In this implementation the const version of operator[] is equivalent 29// to test(), except that it does no range checking. The non-const version 30// returns a reference to a bit, again without doing any range checking. 31 32 33#include <stddef.h> // for size_t 34#include <string.h> // for memset 35#include <string> 36#include <stdexcept> // for invalid_argument, out_of_range, overflow_error 37 38#ifdef __STL_USE_NEW_IOSTREAMS 39#include <iostream> 40#else 41#include <iostream.h> // for istream, ostream 42#endif 43 44#define __BITS_PER_WORD (CHAR_BIT*sizeof(unsigned long)) 45#define __BITSET_WORDS(__n) \ 46 ((__n) < 1 ? 1 : ((__n) + __BITS_PER_WORD - 1)/__BITS_PER_WORD) 47 48__STL_BEGIN_NAMESPACE 49 50#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 51#pragma set woff 1209 52#endif 53 54// structure to aid in counting bits 55template<bool __dummy> 56struct _Bit_count { 57 static unsigned char _S_bit_count[256]; 58}; 59 60// Mapping from 8 bit unsigned integers to the index of the first one 61// bit: 62template<bool __dummy> 63struct _First_one { 64 static unsigned char _S_first_one[256]; 65}; 66 67// 68// Base class: general case. 69// 70 71template<size_t _Nw> 72struct _Base_bitset { 73 typedef unsigned long _WordT; 74 75 _WordT _M_w[_Nw]; // 0 is the least significant word. 76 77 _Base_bitset( void ) { _M_do_reset(); } 78 _Base_bitset(unsigned long __val) { 79 _M_do_reset(); 80 _M_w[0] = __val; 81 } 82 83 static size_t _S_whichword( size_t __pos ) 84 { return __pos / __BITS_PER_WORD; } 85 static size_t _S_whichbyte( size_t __pos ) 86 { return (__pos % __BITS_PER_WORD) / CHAR_BIT; } 87 static size_t _S_whichbit( size_t __pos ) 88 { return __pos % __BITS_PER_WORD; } 89 static _WordT _S_maskbit( size_t __pos ) 90 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 91 92 _WordT& _M_getword(size_t __pos) { return _M_w[_S_whichword(__pos)]; } 93 _WordT _M_getword(size_t __pos) const { return _M_w[_S_whichword(__pos)]; } 94 95 _WordT& _M_hiword() { return _M_w[_Nw - 1]; } 96 _WordT _M_hiword() const { return _M_w[_Nw - 1]; } 97 98 void _M_do_and(const _Base_bitset<_Nw>& __x) { 99 for ( size_t __i = 0; __i < _Nw; __i++ ) { 100 _M_w[__i] &= __x._M_w[__i]; 101 } 102 } 103 104 void _M_do_or(const _Base_bitset<_Nw>& __x) { 105 for ( size_t __i = 0; __i < _Nw; __i++ ) { 106 _M_w[__i] |= __x._M_w[__i]; 107 } 108 } 109 110 void _M_do_xor(const _Base_bitset<_Nw>& __x) { 111 for ( size_t __i = 0; __i < _Nw; __i++ ) { 112 _M_w[__i] ^= __x._M_w[__i]; 113 } 114 } 115 116 void _M_do_left_shift(size_t __shift); 117 void _M_do_right_shift(size_t __shift); 118 119 void _M_do_flip() { 120 for ( size_t __i = 0; __i < _Nw; __i++ ) { 121 _M_w[__i] = ~_M_w[__i]; 122 } 123 } 124 125 void _M_do_set() { 126 for ( size_t __i = 0; __i < _Nw; __i++ ) { 127 _M_w[__i] = ~static_cast<_WordT>(0); 128 } 129 } 130 131 void _M_do_reset() { memset(_M_w, 0, _Nw * sizeof(_WordT)); } 132 133 bool _M_is_equal(const _Base_bitset<_Nw>& __x) const { 134 for (size_t __i = 0; __i < _Nw; ++__i) { 135 if (_M_w[__i] != __x._M_w[__i]) 136 return false; 137 } 138 return true; 139 } 140 141 bool _M_is_any() const { 142 for ( size_t __i = 0; __i < _Nw; __i++ ) { 143 if ( _M_w[__i] != static_cast<_WordT>(0) ) 144 return true; 145 } 146 return false; 147 } 148 149 size_t _M_do_count() const { 150 size_t __result = 0; 151 const unsigned char* __byte_ptr = (const unsigned char*)_M_w; 152 const unsigned char* __end_ptr = (const unsigned char*)(_M_w+_Nw); 153 154 while ( __byte_ptr < __end_ptr ) { 155 __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; 156 __byte_ptr++; 157 } 158 return __result; 159 } 160 161 unsigned long _M_do_to_ulong() const; 162 163 // find first "on" bit 164 size_t _M_do_find_first(size_t __not_found) const; 165 166 // find the next "on" bit that follows "prev" 167 size_t _M_do_find_next(size_t __prev, size_t __not_found) const; 168}; 169 170// 171// Definitions of non-inline functions from _Base_bitset. 172// 173 174template<size_t _Nw> 175void _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) 176{ 177 if (__shift != 0) { 178 const size_t __wshift = __shift / __BITS_PER_WORD; 179 const size_t __offset = __shift % __BITS_PER_WORD; 180 181 if (__offset == 0) 182 for (size_t __n = _Nw - 1; __n >= __wshift; --__n) 183 _M_w[__n] = _M_w[__n - __wshift]; 184 185 else { 186 const size_t __sub_offset = __BITS_PER_WORD - __offset; 187 for (size_t __n = _Nw - 1; __n > __wshift; --__n) 188 _M_w[__n] = (_M_w[__n - __wshift] << __offset) | 189 (_M_w[__n - __wshift - 1] >> __sub_offset); 190 _M_w[__wshift] = _M_w[0] << __offset; 191 } 192 193 fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); 194 } 195} 196 197template<size_t _Nw> 198void _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) 199{ 200 if (__shift != 0) { 201 const size_t __wshift = __shift / __BITS_PER_WORD; 202 const size_t __offset = __shift % __BITS_PER_WORD; 203 const size_t __limit = _Nw - __wshift - 1; 204 205 if (__offset == 0) 206 for (size_t __n = 0; __n <= __limit; ++__n) 207 _M_w[__n] = _M_w[__n + __wshift]; 208 209 else { 210 const size_t __sub_offset = __BITS_PER_WORD - __offset; 211 for (size_t __n = 0; __n < __limit; ++__n) 212 _M_w[__n] = (_M_w[__n + __wshift] >> __offset) | 213 (_M_w[__n + __wshift + 1] << __sub_offset); 214 _M_w[__limit] = _M_w[_Nw-1] >> __offset; 215 } 216 217 fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); 218 } 219} 220 221template<size_t _Nw> 222unsigned long _Base_bitset<_Nw>::_M_do_to_ulong() const 223{ 224 for (size_t __i = 1; __i < _Nw; ++__i) 225 if (_M_w[__i]) 226 __STL_THROW(overflow_error("bitset")); 227 228 return _M_w[0]; 229} 230 231template<size_t _Nw> 232size_t _Base_bitset<_Nw>::_M_do_find_first(size_t __not_found) const 233{ 234 for ( size_t __i = 0; __i < _Nw; __i++ ) { 235 _WordT __thisword = _M_w[__i]; 236 if ( __thisword != static_cast<_WordT>(0) ) { 237 // find byte within word 238 for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { 239 unsigned char __this_byte 240 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 241 if ( __this_byte ) 242 return __i*__BITS_PER_WORD + __j*CHAR_BIT + 243 _First_one<true>::_S_first_one[__this_byte]; 244 245 __thisword >>= CHAR_BIT; 246 } 247 } 248 } 249 // not found, so return an indication of failure. 250 return __not_found; 251} 252 253template<size_t _Nw> 254size_t 255_Base_bitset<_Nw>::_M_do_find_next(size_t __prev, size_t __not_found) const 256{ 257 // make bound inclusive 258 ++__prev; 259 260 // check out of bounds 261 if ( __prev >= _Nw * __BITS_PER_WORD ) 262 return __not_found; 263 264 // search first word 265 size_t __i = _S_whichword(__prev); 266 _WordT __thisword = _M_w[__i]; 267 268 // mask off bits below bound 269 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 270 271 if ( __thisword != static_cast<_WordT>(0) ) { 272 // find byte within word 273 // get first byte into place 274 __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; 275 for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { 276 unsigned char __this_byte 277 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 278 if ( __this_byte ) 279 return __i*__BITS_PER_WORD + __j*CHAR_BIT + 280 _First_one<true>::_S_first_one[__this_byte]; 281 282 __thisword >>= CHAR_BIT; 283 } 284 } 285 286 // check subsequent words 287 __i++; 288 for ( ; __i < _Nw; __i++ ) { 289 _WordT __thisword = _M_w[__i]; 290 if ( __thisword != static_cast<_WordT>(0) ) { 291 // find byte within word 292 for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { 293 unsigned char __this_byte 294 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 295 if ( __this_byte ) 296 return __i*__BITS_PER_WORD + __j*CHAR_BIT + 297 _First_one<true>::_S_first_one[__this_byte]; 298 299 __thisword >>= CHAR_BIT; 300 } 301 } 302 } 303 304 // not found, so return an indication of failure. 305 return __not_found; 306} // end _M_do_find_next 307 308 309// ------------------------------------------------------------ 310 311// 312// Base class: specialization for a single word. 313// 314 315__STL_TEMPLATE_NULL struct _Base_bitset<1> { 316 typedef unsigned long _WordT; 317 _WordT _M_w; 318 319 _Base_bitset( void ) : _M_w(0) {} 320 _Base_bitset(unsigned long __val) : _M_w(__val) {} 321 322 static size_t _S_whichword( size_t __pos ) 323 { return __pos / __BITS_PER_WORD; } 324 static size_t _S_whichbyte( size_t __pos ) 325 { return (__pos % __BITS_PER_WORD) / CHAR_BIT; } 326 static size_t _S_whichbit( size_t __pos ) 327 { return __pos % __BITS_PER_WORD; } 328 static _WordT _S_maskbit( size_t __pos ) 329 { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } 330 331 _WordT& _M_getword(size_t) { return _M_w; } 332 _WordT _M_getword(size_t) const { return _M_w; } 333 334 _WordT& _M_hiword() { return _M_w; } 335 _WordT _M_hiword() const { return _M_w; } 336 337 void _M_do_and(const _Base_bitset<1>& __x) { _M_w &= __x._M_w; } 338 void _M_do_or(const _Base_bitset<1>& __x) { _M_w |= __x._M_w; } 339 void _M_do_xor(const _Base_bitset<1>& __x) { _M_w ^= __x._M_w; } 340 void _M_do_left_shift(size_t __shift) { _M_w <<= __shift; } 341 void _M_do_right_shift(size_t __shift) { _M_w >>= __shift; } 342 void _M_do_flip() { _M_w = ~_M_w; } 343 void _M_do_set() { _M_w = ~static_cast<_WordT>(0); } 344 void _M_do_reset() { _M_w = 0; } 345 346 bool _M_is_equal(const _Base_bitset<1>& __x) const 347 { return _M_w == __x._M_w; } 348 bool _M_is_any() const 349 { return _M_w != 0; } 350 351 size_t _M_do_count() const { 352 size_t __result = 0; 353 const unsigned char* __byte_ptr = (const unsigned char*)&_M_w; 354 const unsigned char* __end_ptr 355 = ((const unsigned char*)&_M_w)+sizeof(_M_w); 356 while ( __byte_ptr < __end_ptr ) { 357 __result += _Bit_count<true>::_S_bit_count[*__byte_ptr]; 358 __byte_ptr++; 359 } 360 return __result; 361 } 362 363 unsigned long _M_do_to_ulong() const { return _M_w; } 364 365 size_t _M_do_find_first(size_t __not_found) const; 366 367 // find the next "on" bit that follows "prev" 368 size_t _M_do_find_next(size_t __prev, size_t __not_found) const; 369 370}; 371 372// 373// Definitions of non-inline functions from the single-word version of 374// _Base_bitset. 375// 376 377size_t _Base_bitset<1>::_M_do_find_first(size_t __not_found) const 378{ 379 _WordT __thisword = _M_w; 380 381 if ( __thisword != static_cast<_WordT>(0) ) { 382 // find byte within word 383 for ( size_t __j = 0; __j < sizeof(_WordT); __j++ ) { 384 unsigned char __this_byte 385 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 386 if ( __this_byte ) 387 return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; 388 389 __thisword >>= CHAR_BIT; 390 } 391 } 392 // not found, so return a value that indicates failure. 393 return __not_found; 394} 395 396size_t _Base_bitset<1>::_M_do_find_next(size_t __prev, size_t __not_found ) const 397{ 398 // make bound inclusive 399 ++__prev; 400 401 // check out of bounds 402 if ( __prev >= __BITS_PER_WORD ) 403 return __not_found; 404 405 // search first (and only) word 406 _WordT __thisword = _M_w; 407 408 // mask off bits below bound 409 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 410 411 if ( __thisword != static_cast<_WordT>(0) ) { 412 // find byte within word 413 // get first byte into place 414 __thisword >>= _S_whichbyte(__prev) * CHAR_BIT; 415 for ( size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) { 416 unsigned char __this_byte 417 = static_cast<unsigned char>(__thisword & (~(unsigned char)0)); 418 if ( __this_byte ) 419 return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte]; 420 421 __thisword >>= CHAR_BIT; 422 } 423 } 424 425 // not found, so return a value that indicates failure. 426 return __not_found; 427} // end _M_do_find_next 428 429 430// ------------------------------------------------------------ 431// Helper class to zero out the unused high-order bits in the highest word. 432 433template <size_t _Extrabits> struct _Sanitize { 434 static void _M_do_sanitize(unsigned long& __val) 435 { __val &= ~((~static_cast<unsigned long>(0)) << _Extrabits); } 436}; 437 438__STL_TEMPLATE_NULL struct _Sanitize<0> { 439 static void _M_do_sanitize(unsigned long) {} 440}; 441 442 443 444// ------------------------------------------------------------ 445// Class bitset. 446// _Nb may be any nonzero number of type size_t. 447 448template<size_t _Nb> 449class bitset : private _Base_bitset<__BITSET_WORDS(_Nb)> 450{ 451private: 452 typedef _Base_bitset<__BITSET_WORDS(_Nb)> _Base; 453 typedef unsigned long _WordT; 454 455private: 456 void _M_do_sanitize() { 457 _Sanitize<_Nb%__BITS_PER_WORD>::_M_do_sanitize(this->_M_hiword()); 458 } 459 460public: 461 462 // bit reference: 463 class reference; 464 friend class reference; 465 466 class reference { 467 friend class bitset; 468 469 _WordT *_M_wp; 470 size_t _M_bpos; 471 472 // left undefined 473 reference(); 474 475 public: 476 reference( bitset& __b, size_t __pos ) { 477 _M_wp = &__b._M_getword(__pos); 478 _M_bpos = _Base::_S_whichbit(__pos); 479 } 480 481 ~reference() {} 482 483 // for b[i] = __x; 484 reference& operator=(bool __x) { 485 if ( __x ) 486 *_M_wp |= _Base::_S_maskbit(_M_bpos); 487 else 488 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 489 490 return *this; 491 } 492 493 // for b[i] = b[__j]; 494 reference& operator=(const reference& __j) { 495 if ( (*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)) ) 496 *_M_wp |= _Base::_S_maskbit(_M_bpos); 497 else 498 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 499 500 return *this; 501 } 502 503 // flips the bit 504 bool operator~() const 505 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 506 507 // for __x = b[i]; 508 operator bool() const 509 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 510 511 // for b[i].flip(); 512 reference& flip() { 513 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 514 return *this; 515 } 516 }; 517 518 // 23.3.5.1 constructors: 519 bitset() {} 520 bitset(unsigned long __val) : _Base_bitset<__BITSET_WORDS(_Nb)>(__val) 521 { _M_do_sanitize(); } 522 523#ifdef __STL_MEMBER_TEMPLATES 524 template<class _CharT, class _Traits, class _Alloc> 525 explicit bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 526 size_t __pos = 0) 527 : _Base() 528 { 529 if (__pos > __s.size()) 530 __STL_THROW(out_of_range("bitset")); 531 _M_copy_from_string(__s, __pos, 532 basic_string<_CharT, _Traits, _Alloc>::npos); 533 } 534 template<class _CharT, class _Traits, class _Alloc> 535 bitset(const basic_string<_CharT, _Traits, _Alloc>& __s, 536 size_t __pos, 537 size_t __n) 538 : _Base() 539 { 540 if (__pos > __s.size()) 541 __STL_THROW(out_of_range("bitset")); 542 _M_copy_from_string(__s, __pos, __n); 543 } 544#else /* __STL_MEMBER_TEMPLATES */ 545 explicit bitset(const basic_string<char>& __s, 546 size_t __pos = 0, 547 size_t __n = basic_string<char>::npos) 548 : _Base() 549 { 550 if (__pos > __s.size()) 551 __STL_THROW(out_of_range("bitset")); 552 _M_copy_from_string(__s, __pos, __n); 553 } 554#endif /* __STL_MEMBER_TEMPLATES */ 555 556 // 23.3.5.2 bitset operations: 557 bitset<_Nb>& operator&=(const bitset<_Nb>& __rhs) { 558 this->_M_do_and(__rhs); 559 return *this; 560 } 561 562 bitset<_Nb>& operator|=(const bitset<_Nb>& __rhs) { 563 this->_M_do_or(__rhs); 564 return *this; 565 } 566 567 bitset<_Nb>& operator^=(const bitset<_Nb>& __rhs) { 568 this->_M_do_xor(__rhs); 569 return *this; 570 } 571 572 bitset<_Nb>& operator<<=(size_t __pos) { 573 this->_M_do_left_shift(__pos); 574 this->_M_do_sanitize(); 575 return *this; 576 } 577 578 bitset<_Nb>& operator>>=(size_t __pos) { 579 this->_M_do_right_shift(__pos); 580 this->_M_do_sanitize(); 581 return *this; 582 } 583 584 // 585 // Extension: 586 // Versions of single-bit set, reset, flip, test with no range checking. 587 // 588 589 bitset<_Nb>& _Unchecked_set(size_t __pos) { 590 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 591 return *this; 592 } 593 594 bitset<_Nb>& _Unchecked_set(size_t __pos, int __val) { 595 if (__val) 596 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 597 else 598 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 599 600 return *this; 601 } 602 603 bitset<_Nb>& _Unchecked_reset(size_t __pos) { 604 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 605 return *this; 606 } 607 608 bitset<_Nb>& _Unchecked_flip(size_t __pos) { 609 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 610 return *this; 611 } 612 613 bool _Unchecked_test(size_t __pos) const { 614 return (this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 615 != static_cast<_WordT>(0); 616 } 617 618 // Set, reset, and flip. 619 620 bitset<_Nb>& set() { 621 this->_M_do_set(); 622 this->_M_do_sanitize(); 623 return *this; 624 } 625 626 bitset<_Nb>& set(size_t __pos) { 627 if (__pos >= _Nb) 628 __STL_THROW(out_of_range("bitset")); 629 630 return _Unchecked_set(__pos); 631 } 632 633 bitset<_Nb>& set(size_t __pos, int __val) { 634 if (__pos >= _Nb) 635 __STL_THROW(out_of_range("bitset")); 636 637 return _Unchecked_set(__pos, __val); 638 } 639 640 bitset<_Nb>& reset() { 641 this->_M_do_reset(); 642 return *this; 643 } 644 645 bitset<_Nb>& reset(size_t __pos) { 646 if (__pos >= _Nb) 647 __STL_THROW(out_of_range("bitset")); 648 649 return _Unchecked_reset(__pos); 650 } 651 652 bitset<_Nb>& flip() { 653 this->_M_do_flip(); 654 this->_M_do_sanitize(); 655 return *this; 656 } 657 658 bitset<_Nb>& flip(size_t __pos) { 659 if (__pos >= _Nb) 660 __STL_THROW(out_of_range("bitset")); 661 662 return _Unchecked_flip(__pos); 663 } 664 665 bitset<_Nb> operator~() const { 666 return bitset<_Nb>(*this).flip(); 667 } 668 669 // element access: 670 //for b[i]; 671 reference operator[](size_t __pos) { return reference(*this,__pos); } 672 bool operator[](size_t __pos) const { return _Unchecked_test(__pos); } 673 674 unsigned long to_ulong() const { return this->_M_do_to_ulong(); } 675 676#if defined(__STL_MEMBER_TEMPLATES) && \ 677 defined(__STL_EXPLICIT_FUNCTION_TMPL_ARGS) 678 template <class _CharT, class _Traits, class _Alloc> 679 basic_string<_CharT, _Traits, _Alloc> to_string() const { 680 basic_string<_CharT, _Traits, _Alloc> __result; 681 _M_copy_to_string(__result); 682 return __result; 683 } 684#endif /* member templates and explicit function template args */ 685 686 // Helper functions for string operations. 687#ifdef __STL_MEMBER_TEMPLATES 688 template<class _CharT, class _Traits, class _Alloc> 689 void _M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 690 size_t, 691 size_t); 692 693 template<class _CharT, class _Traits, class _Alloc> 694 void _M_copy_to_string(basic_string<_CharT,_Traits,_Alloc>&) const; 695#else /* __STL_MEMBER_TEMPLATES */ 696 void _M_copy_from_string(const basic_string<char>&, size_t, size_t); 697 void _M_copy_to_string(basic_string<char>&) const; 698#endif /* __STL_MEMBER_TEMPLATES */ 699 700 size_t count() const { return this->_M_do_count(); } 701 702 size_t size() const { return _Nb; } 703 704 bool operator==(const bitset<_Nb>& __rhs) const { 705 return this->_M_is_equal(__rhs); 706 } 707 bool operator!=(const bitset<_Nb>& __rhs) const { 708 return !this->_M_is_equal(__rhs); 709 } 710 711 bool test(size_t __pos) const { 712 if (__pos > _Nb) 713 __STL_THROW(out_of_range("bitset")); 714 715 return _Unchecked_test(__pos); 716 } 717 718 bool any() const { return this->_M_is_any(); } 719 bool none() const { return !this->_M_is_any(); } 720 721 bitset<_Nb> operator<<(size_t __pos) const 722 { return bitset<_Nb>(*this) <<= __pos; } 723 bitset<_Nb> operator>>(size_t __pos) const 724 { return bitset<_Nb>(*this) >>= __pos; } 725 726 // 727 // EXTENSIONS: bit-find operations. These operations are 728 // experimental, and are subject to change or removal in future 729 // versions. 730 // 731 732 // find the index of the first "on" bit 733 size_t _Find_first() const 734 { return this->_M_do_find_first(_Nb); } 735 736 // find the index of the next "on" bit after prev 737 size_t _Find_next( size_t __prev ) const 738 { return this->_M_do_find_next(__prev, _Nb); } 739 740}; 741 742// 743// Definitions of non-inline member functions. 744// 745 746#ifdef __STL_MEMBER_TEMPLATES 747 748template <size_t _Nb> 749template<class _CharT, class _Traits, class _Alloc> 750void bitset<_Nb> 751 ::_M_copy_from_string(const basic_string<_CharT,_Traits,_Alloc>& __s, 752 size_t __pos, 753 size_t __n) 754{ 755 reset(); 756 const size_t __nbits = min(_Nb, min(__n, __s.size() - __pos)); 757 for (size_t __i = 0; __i < __nbits; ++__i) { 758 switch(__s[__pos + __nbits - __i - 1]) { 759 case '0': 760 break; 761 case '1': 762 set(__i); 763 break; 764 default: 765 __STL_THROW(invalid_argument("bitset")); 766 } 767 } 768} 769 770template <size_t _Nb> 771template <class _CharT, class _Traits, class _Alloc> 772void bitset<_Nb> 773 ::_M_copy_to_string(basic_string<_CharT, _Traits, _Alloc>& __s) const 774{ 775 __s.assign(_Nb, '0'); 776 777 for (size_t __i = 0; __i < _Nb; ++__i) 778 if (_Unchecked_test(__i)) 779 __s[_Nb - 1 - __i] = '1'; 780} 781 782#else /* __STL_MEMBER_TEMPLATES */ 783 784template <size_t _Nb> 785void bitset<_Nb>::_M_copy_from_string(const basic_string<char>& __s, 786 size_t __pos, size_t __n) 787{ 788 reset(); 789 size_t __tmp = _Nb; 790 const size_t __nbits = min(__tmp, min(__n, __s.size() - __pos)); 791 for (size_t __i = 0; __i < __nbits; ++__i) { 792 switch(__s[__pos + __nbits - __i - 1]) { 793 case '0': 794 break; 795 case '1': 796 set(__i); 797 break; 798 default: 799 __STL_THROW(invalid_argument("bitset")); 800 } 801 } 802} 803 804template <size_t _Nb> 805void bitset<_Nb>::_M_copy_to_string(basic_string<char>& __s) const 806{ 807 __s.assign(_Nb, '0'); 808 809 for (size_t __i = 0; __i < _Nb; ++__i) 810 if (_Unchecked_test(__i)) 811 __s[_Nb - 1 - __i] = '1'; 812} 813 814#endif /* __STL_MEMBER_TEMPLATES */ 815 816// ------------------------------------------------------------ 817 818// 819// 23.3.5.3 bitset operations: 820// 821 822template <size_t _Nb> 823inline bitset<_Nb> operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { 824 bitset<_Nb> __result(__x); 825 __result &= __y; 826 return __result; 827} 828 829 830template <size_t _Nb> 831inline bitset<_Nb> operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { 832 bitset<_Nb> __result(__x); 833 __result |= __y; 834 return __result; 835} 836 837template <size_t _Nb> 838inline bitset<_Nb> operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) { 839 bitset<_Nb> __result(__x); 840 __result ^= __y; 841 return __result; 842} 843 844#ifdef __STL_USE_NEW_IOSTREAMS 845 846template <class _CharT, class _Traits, size_t _Nb> 847basic_istream<_CharT, _Traits>& 848operator>>(basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 849{ 850 basic_string<_CharT, _Traits> __tmp; 851 __tmp.reserve(_Nb); 852 853 // Skip whitespace 854 typename basic_istream<_CharT, _Traits>::sentry __sentry(__is); 855 if (__sentry) { 856 basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf(); 857 for (size_t __i = 0; __i < _Nb; ++__i) { 858 static _Traits::int_type __eof = _Traits::eof(); 859 860 typename _Traits::int_type __c1 = __buf->sbumpc(); 861 if (_Traits::eq_int_type(__c1, __eof)) { 862 __is.setstate(ios_base::eofbit); 863 break; 864 } 865 else { 866 char __c2 = _Traits::to_char_type(__c1); 867 char __c = __is.narrow(__c2, '*'); 868 869 if (__c == '0' || __c == '1') 870 __tmp.push_back(__c); 871 else if (_Traits::eq_int_type(__buf->sputbackc(__c2), __eof)) { 872 __is.setstate(ios_base::failbit); 873 break; 874 } 875 } 876 } 877 878 if (__tmp.empty()) 879 __is.setstate(ios_base::failbit); 880 else 881 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 882 } 883 884 return __is; 885} 886 887template <class _CharT, class _Traits, size_t _Nb> 888basic_ostream<_CharT, _Traits>& 889operator<<(basic_ostream<_CharT, _Traits>& __os, const bitset<_Nb>& __x) 890{ 891 basic_string<_CharT, _Traits> __tmp; 892 __x._M_copy_to_string(__tmp); 893 return __os << __tmp; 894} 895 896#else /* __STL_USE_NEW_IOSTREAMS */ 897 898template <size_t _Nb> 899istream& operator>>(istream& __is, bitset<_Nb>& __x) { 900 string __tmp; 901 __tmp.reserve(_Nb); 902 903 if (__is.flags() & ios::skipws) { 904 char __c; 905 do 906 __is.get(__c); 907 while (__is && isspace(__c)); 908 if (__is) 909 __is.putback(__c); 910 } 911 912 for (size_t __i = 0; __i < _Nb; ++__i) { 913 char __c; 914 __is.get(__c); 915 916 if (!__is) 917 break; 918 else if (__c != '0' && __c != '1') { 919 __is.putback(__c); 920 break; 921 } 922 else 923 __tmp.push_back(__c); 924 } 925 926 if (__tmp.empty()) 927 __is.clear(__is.rdstate() | ios::failbit); 928 else 929 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb); 930 931 return __is; 932} 933 934template <size_t _Nb> 935ostream& operator<<(ostream& __os, const bitset<_Nb>& __x) { 936 string __tmp; 937 __x._M_copy_to_string(__tmp); 938 return __os << __tmp; 939} 940 941#endif /* __STL_USE_NEW_IOSTREAMS */ 942 943// ------------------------------------------------------------ 944// Lookup tables for find and count operations. 945 946template<bool __dummy> 947unsigned char _Bit_count<__dummy>::_S_bit_count[] = { 948 0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */ 949 2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */ 950 2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */ 951 4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */ 952 2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */ 953 3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */ 954 4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */ 955 3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */ 956 2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */ 957 4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */ 958 3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */ 959 5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */ 960 4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */ 961 2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */ 962 3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */ 963 4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */ 964 2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */ 965 4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */ 966 4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */ 967 6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */ 968 3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */ 969 4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */ 970 5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */ 971 5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */ 972 4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */ 973 6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */ 974 2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */ 975 4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */ 976 3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */ 977 3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */ 978 4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */ 979 5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */ 980 2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */ 981 4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */ 982 4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */ 983 6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */ 984 4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */ 985 5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */ 986 6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */ 987 4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */ 988 3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */ 989 5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */ 990 4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */ 991 6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */ 992 5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */ 993 4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */ 994 5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */ 995 6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */ 996 4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */ 997 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */ 998 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */ 999 8 /* 255 */ 1000}; // end _Bit_count 1001 1002template<bool __dummy> 1003unsigned char _First_one<__dummy>::_S_first_one[] = { 1004 0, /* 0 */ 0, /* 1 */ 1, /* 2 */ 0, /* 3 */ 2, /* 4 */ 1005 0, /* 5 */ 1, /* 6 */ 0, /* 7 */ 3, /* 8 */ 0, /* 9 */ 1006 1, /* 10 */ 0, /* 11 */ 2, /* 12 */ 0, /* 13 */ 1, /* 14 */ 1007 0, /* 15 */ 4, /* 16 */ 0, /* 17 */ 1, /* 18 */ 0, /* 19 */ 1008 2, /* 20 */ 0, /* 21 */ 1, /* 22 */ 0, /* 23 */ 3, /* 24 */ 1009 0, /* 25 */ 1, /* 26 */ 0, /* 27 */ 2, /* 28 */ 0, /* 29 */ 1010 1, /* 30 */ 0, /* 31 */ 5, /* 32 */ 0, /* 33 */ 1, /* 34 */ 1011 0, /* 35 */ 2, /* 36 */ 0, /* 37 */ 1, /* 38 */ 0, /* 39 */ 1012 3, /* 40 */ 0, /* 41 */ 1, /* 42 */ 0, /* 43 */ 2, /* 44 */ 1013 0, /* 45 */ 1, /* 46 */ 0, /* 47 */ 4, /* 48 */ 0, /* 49 */ 1014 1, /* 50 */ 0, /* 51 */ 2, /* 52 */ 0, /* 53 */ 1, /* 54 */ 1015 0, /* 55 */ 3, /* 56 */ 0, /* 57 */ 1, /* 58 */ 0, /* 59 */ 1016 2, /* 60 */ 0, /* 61 */ 1, /* 62 */ 0, /* 63 */ 6, /* 64 */ 1017 0, /* 65 */ 1, /* 66 */ 0, /* 67 */ 2, /* 68 */ 0, /* 69 */ 1018 1, /* 70 */ 0, /* 71 */ 3, /* 72 */ 0, /* 73 */ 1, /* 74 */ 1019 0, /* 75 */ 2, /* 76 */ 0, /* 77 */ 1, /* 78 */ 0, /* 79 */ 1020 4, /* 80 */ 0, /* 81 */ 1, /* 82 */ 0, /* 83 */ 2, /* 84 */ 1021 0, /* 85 */ 1, /* 86 */ 0, /* 87 */ 3, /* 88 */ 0, /* 89 */ 1022 1, /* 90 */ 0, /* 91 */ 2, /* 92 */ 0, /* 93 */ 1, /* 94 */ 1023 0, /* 95 */ 5, /* 96 */ 0, /* 97 */ 1, /* 98 */ 0, /* 99 */ 1024 2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */ 1025 0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */ 1026 1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */ 1027 0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */ 1028 3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */ 1029 0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */ 1030 1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */ 1031 0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */ 1032 2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */ 1033 0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */ 1034 1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */ 1035 0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */ 1036 5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */ 1037 0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */ 1038 1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */ 1039 0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */ 1040 2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */ 1041 0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */ 1042 1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */ 1043 0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */ 1044 3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */ 1045 0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */ 1046 1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */ 1047 0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */ 1048 2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */ 1049 0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */ 1050 1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */ 1051 0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */ 1052 4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */ 1053 0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */ 1054 1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */ 1055 0, /* 255 */ 1056}; // end _First_one 1057 1058#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) 1059#pragma reset woff 1209 1060#endif 1061 1062__STL_END_NAMESPACE 1063 1064 1065#undef __BITS_PER_WORD 1066#undef __BITSET_WORDS 1067 1068#endif /* __SGI_STL_BITSET */ 1069 1070 1071// Local Variables: 1072// mode:C++ 1073// End: 1074 1075