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