1// -*- C++ -*- 2//===---------------------------- bitset ----------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_BITSET 12#define _LIBCPP_BITSET 13 14/* 15 bitset synopsis 16 17namespace std 18{ 19 20namespace std { 21 22template <size_t N> 23class bitset 24{ 25public: 26 // bit reference: 27 class reference 28 { 29 friend class bitset; 30 reference(); 31 public: 32 ~reference(); 33 reference& operator=(bool x); // for b[i] = x; 34 reference& operator=(const reference&); // for b[i] = b[j]; 35 bool operator~() const; // flips the bit 36 operator bool() const; // for x = b[i]; 37 reference& flip(); // for b[i].flip(); 38 }; 39 40 // 23.3.5.1 constructors: 41 constexpr bitset(); 42 constexpr bitset(unsigned long long val); 43 template <class charT> 44 explicit bitset(const charT* str, 45 typename basic_string<charT>::size_type n = basic_string<charT>::npos, 46 charT zero = charT('0'), charT one = charT('1')); 47 template<class charT, class traits, class Allocator> 48 explicit bitset(const basic_string<charT,traits,Allocator>& str, 49 typename basic_string<charT,traits,Allocator>::size_type pos = 0, 50 typename basic_string<charT,traits,Allocator>::size_type n = 51 basic_string<charT,traits,Allocator>::npos, 52 charT zero = charT('0'), charT one = charT('1')); 53 54 // 23.3.5.2 bitset operations: 55 bitset& operator&=(const bitset& rhs); 56 bitset& operator|=(const bitset& rhs); 57 bitset& operator^=(const bitset& rhs); 58 bitset& operator<<=(size_t pos); 59 bitset& operator>>=(size_t pos); 60 bitset& set(); 61 bitset& set(size_t pos, bool val = true); 62 bitset& reset(); 63 bitset& reset(size_t pos); 64 bitset operator~() const; 65 bitset& flip(); 66 bitset& flip(size_t pos); 67 68 // element access: 69 constexpr bool operator[](size_t pos) const; // for b[i]; 70 reference operator[](size_t pos); // for b[i]; 71 unsigned long to_ulong() const; 72 unsigned long long to_ullong() const; 73 template <class charT, class traits, class Allocator> 74 basic_string<charT, traits, Allocator> to_string(charT zero = charT('0'), charT one = charT('1')) const; 75 template <class charT, class traits> 76 basic_string<charT, traits, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const; 77 template <class charT> 78 basic_string<charT, char_traits<charT>, allocator<charT> > to_string(charT zero = charT('0'), charT one = charT('1')) const; 79 basic_string<char, char_traits<char>, allocator<char> > to_string(char zero = '0', char one = '1') const; 80 size_t count() const; 81 constexpr size_t size() const; 82 bool operator==(const bitset& rhs) const; 83 bool operator!=(const bitset& rhs) const; 84 bool test(size_t pos) const; 85 bool all() const; 86 bool any() const; 87 bool none() const; 88 bitset operator<<(size_t pos) const; 89 bitset operator>>(size_t pos) const; 90}; 91 92// 23.3.5.3 bitset operators: 93template <size_t N> 94bitset<N> operator&(const bitset<N>&, const bitset<N>&); 95 96template <size_t N> 97bitset<N> operator|(const bitset<N>&, const bitset<N>&); 98 99template <size_t N> 100bitset<N> operator^(const bitset<N>&, const bitset<N>&); 101 102template <class charT, class traits, size_t N> 103basic_istream<charT, traits>& 104operator>>(basic_istream<charT, traits>& is, bitset<N>& x); 105 106template <class charT, class traits, size_t N> 107basic_ostream<charT, traits>& 108operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x); 109 110template <size_t N> struct hash<std::bitset<N>>; 111 112} // std 113 114*/ 115 116#pragma GCC system_header 117 118#include <__config> 119#include <__bit_reference> 120#include <cstddef> 121#include <climits> 122#include <string> 123#include <stdexcept> 124#include <iosfwd> 125#include <__functional_base> 126#if defined(_LIBCPP_NO_EXCEPTIONS) 127 #include <cassert> 128#endif 129 130_LIBCPP_BEGIN_NAMESPACE_STD 131 132template <size_t _N_words, size_t _Size> 133class __bitset 134{ 135public: 136 typedef ptrdiff_t difference_type; 137 typedef size_t size_type; 138protected: 139 typedef __bitset __self; 140 typedef size_type __storage_type; 141 typedef __storage_type* __storage_pointer; 142 typedef const __storage_type* __const_storage_pointer; 143 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 144 145 friend class __bit_reference<__bitset>; 146 friend class __bit_const_reference<__bitset>; 147 friend class __bit_iterator<__bitset, false>; 148 friend class __bit_iterator<__bitset, true>; 149 friend class __bit_array<__bitset>; 150 151 __storage_type __first_[_N_words]; 152 153 typedef __bit_reference<__bitset> reference; 154 typedef __bit_const_reference<__bitset> const_reference; 155 typedef __bit_iterator<__bitset, false> iterator; 156 typedef __bit_iterator<__bitset, true> const_iterator; 157 158 __bitset(); 159 explicit __bitset(unsigned long long __v); 160 161 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) 162 {return reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 163 _LIBCPP_INLINE_VISIBILITY const_reference __make_ref(size_t __pos) const 164 {return const_reference(__first_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 165 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) 166 {return iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} 167 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const 168 {return const_iterator(__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} 169 170 void operator&=(const __bitset& __v); 171 void operator|=(const __bitset& __v); 172 void operator^=(const __bitset& __v); 173 174 void flip(); 175 _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const 176 {return to_ulong(integral_constant<bool, _Size < sizeof(unsigned long) * CHAR_BIT>());} 177 _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const 178 {return to_ullong(integral_constant<bool, _Size < sizeof(unsigned long long) * CHAR_BIT>());} 179 180 bool all() const; 181 bool any() const; 182 size_t __hash_code() const; 183private: 184 void __init(unsigned long long __v, false_type); 185 void __init(unsigned long long __v, true_type); 186 unsigned long to_ulong(false_type) const; 187 unsigned long to_ulong(true_type) const; 188 unsigned long long to_ullong(false_type) const; 189 unsigned long long to_ullong(true_type) const; 190 unsigned long long to_ullong(true_type, false_type) const; 191 unsigned long long to_ullong(true_type, true_type) const; 192}; 193 194template <size_t _N_words, size_t _Size> 195inline _LIBCPP_INLINE_VISIBILITY 196__bitset<_N_words, _Size>::__bitset() 197{ 198 _STD::fill_n(__first_, _N_words, __storage_type(0)); 199} 200 201template <size_t _N_words, size_t _Size> 202void 203__bitset<_N_words, _Size>::__init(unsigned long long __v, false_type) 204{ 205 __storage_type __t[sizeof(unsigned long long) / sizeof(__storage_type)]; 206 for (size_t __i = 0; __i < sizeof(__t)/sizeof(__t[0]); ++__i, __v >>= __bits_per_word) 207 __t[__i] = static_cast<__storage_type>(__v); 208 _STD::copy(__t, __t + sizeof(__t)/sizeof(__t[0]), __first_); 209 _STD::fill(__first_ + sizeof(__t)/sizeof(__t[0]), __first_ + sizeof(__first_)/sizeof(__first_[0]), 210 __storage_type(0)); 211} 212 213template <size_t _N_words, size_t _Size> 214inline _LIBCPP_INLINE_VISIBILITY 215void 216__bitset<_N_words, _Size>::__init(unsigned long long __v, true_type) 217{ 218 __first_[0] = __v; 219 _STD::fill(__first_ + 1, __first_ + sizeof(__first_)/sizeof(__first_[0]), __storage_type(0)); 220} 221 222template <size_t _N_words, size_t _Size> 223inline _LIBCPP_INLINE_VISIBILITY 224__bitset<_N_words, _Size>::__bitset(unsigned long long __v) 225{ 226 __init(__v, integral_constant<bool, sizeof(unsigned long long) == sizeof(__storage_type)>()); 227} 228 229template <size_t _N_words, size_t _Size> 230inline _LIBCPP_INLINE_VISIBILITY 231void 232__bitset<_N_words, _Size>::operator&=(const __bitset& __v) 233{ 234 for (size_type __i = 0; __i < _N_words; ++__i) 235 __first_[__i] &= __v.__first_[__i]; 236} 237 238template <size_t _N_words, size_t _Size> 239inline _LIBCPP_INLINE_VISIBILITY 240void 241__bitset<_N_words, _Size>::operator|=(const __bitset& __v) 242{ 243 for (size_type __i = 0; __i < _N_words; ++__i) 244 __first_[__i] |= __v.__first_[__i]; 245} 246 247template <size_t _N_words, size_t _Size> 248inline _LIBCPP_INLINE_VISIBILITY 249void 250__bitset<_N_words, _Size>::operator^=(const __bitset& __v) 251{ 252 for (size_type __i = 0; __i < _N_words; ++__i) 253 __first_[__i] ^= __v.__first_[__i]; 254} 255 256template <size_t _N_words, size_t _Size> 257void 258__bitset<_N_words, _Size>::flip() 259{ 260 // do middle whole words 261 size_type __n = _Size; 262 __storage_pointer __p = __first_; 263 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 264 *__p = ~*__p; 265 // do last partial word 266 if (__n > 0) 267 { 268 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 269 __storage_type __b = *__p & __m; 270 *__p &= ~__m; 271 *__p |= ~__b & __m; 272 } 273} 274 275template <size_t _N_words, size_t _Size> 276unsigned long 277__bitset<_N_words, _Size>::to_ulong(false_type) const 278{ 279 const_iterator __e = __make_iter(_Size); 280 const_iterator __i = _STD::find(__make_iter(sizeof(unsigned long) * CHAR_BIT), __e, true); 281 if (__i != __e) 282#ifndef _LIBCPP_NO_EXCEPTIONS 283 throw overflow_error("bitset to_ulong overflow error"); 284#else 285 assert(!"bitset to_ulong overflow error"); 286#endif 287 return __first_[0]; 288} 289 290template <size_t _N_words, size_t _Size> 291inline _LIBCPP_INLINE_VISIBILITY 292unsigned long 293__bitset<_N_words, _Size>::to_ulong(true_type) const 294{ 295 return __first_[0]; 296} 297 298template <size_t _N_words, size_t _Size> 299unsigned long long 300__bitset<_N_words, _Size>::to_ullong(false_type) const 301{ 302 const_iterator __e = __make_iter(_Size); 303 const_iterator __i = _STD::find(__make_iter(sizeof(unsigned long long) * CHAR_BIT), __e, true); 304 if (__i != __e) 305#ifndef _LIBCPP_NO_EXCEPTIONS 306 throw overflow_error("bitset to_ullong overflow error"); 307#else 308 assert(!"bitset to_ullong overflow error"); 309#endif 310 return to_ullong(true_type()); 311} 312 313template <size_t _N_words, size_t _Size> 314inline _LIBCPP_INLINE_VISIBILITY 315unsigned long long 316__bitset<_N_words, _Size>::to_ullong(true_type) const 317{ 318 return to_ullong(true_type(), integral_constant<bool, sizeof(__storage_type) < sizeof(unsigned long long)>()); 319} 320 321template <size_t _N_words, size_t _Size> 322inline _LIBCPP_INLINE_VISIBILITY 323unsigned long long 324__bitset<_N_words, _Size>::to_ullong(true_type, false_type) const 325{ 326 return __first_[0]; 327} 328 329template <size_t _N_words, size_t _Size> 330unsigned long long 331__bitset<_N_words, _Size>::to_ullong(true_type, true_type) const 332{ 333 unsigned long long __r = __first_[0]; 334 for (std::size_t __i = 1; __i < sizeof(unsigned long long) / sizeof(__storage_type); ++__i) 335 __r |= static_cast<unsigned long long>(__first_[__i]) << (sizeof(__storage_type) * CHAR_BIT); 336 return __r; 337} 338 339template <size_t _N_words, size_t _Size> 340bool 341__bitset<_N_words, _Size>::all() const 342{ 343 // do middle whole words 344 size_type __n = _Size; 345 __const_storage_pointer __p = __first_; 346 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 347 if (~*__p) 348 return false; 349 // do last partial word 350 if (__n > 0) 351 { 352 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 353 if (~*__p & __m) 354 return false; 355 } 356 return true; 357} 358 359template <size_t _N_words, size_t _Size> 360bool 361__bitset<_N_words, _Size>::any() const 362{ 363 // do middle whole words 364 size_type __n = _Size; 365 __const_storage_pointer __p = __first_; 366 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 367 if (*__p) 368 return true; 369 // do last partial word 370 if (__n > 0) 371 { 372 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 373 if (*__p & __m) 374 return true; 375 } 376 return false; 377} 378 379template <size_t _N_words, size_t _Size> 380inline _LIBCPP_INLINE_VISIBILITY 381size_t 382__bitset<_N_words, _Size>::__hash_code() const 383{ 384 size_t __h = 0; 385 for (size_type __i = 0; __i < _N_words; ++__i) 386 __h ^= __first_[__i]; 387 return __h; 388} 389 390template <size_t _Size> 391class __bitset<1, _Size> 392{ 393public: 394 typedef ptrdiff_t difference_type; 395 typedef size_t size_type; 396protected: 397 typedef __bitset __self; 398 typedef size_type __storage_type; 399 typedef __storage_type* __storage_pointer; 400 typedef const __storage_type* __const_storage_pointer; 401 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 402 403 friend class __bit_reference<__bitset>; 404 friend class __bit_const_reference<__bitset>; 405 friend class __bit_iterator<__bitset, false>; 406 friend class __bit_iterator<__bitset, true>; 407 friend class __bit_array<__bitset>; 408 409 __storage_type __first_; 410 411 typedef __bit_reference<__bitset> reference; 412 typedef __bit_const_reference<__bitset> const_reference; 413 typedef __bit_iterator<__bitset, false> iterator; 414 typedef __bit_iterator<__bitset, true> const_iterator; 415 416 __bitset(); 417 explicit __bitset(unsigned long long __v); 418 419 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t __pos) 420 {return reference(&__first_, __storage_type(1) << __pos);} 421 _LIBCPP_INLINE_VISIBILITY const_reference __make_ref(size_t __pos) const 422 {return const_reference(&__first_, __storage_type(1) << __pos);} 423 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) 424 {return iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} 425 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const 426 {return const_iterator(&__first_ + __pos / __bits_per_word, __pos % __bits_per_word);} 427 428 void operator&=(const __bitset& __v); 429 void operator|=(const __bitset& __v); 430 void operator^=(const __bitset& __v); 431 432 void flip(); 433 434 unsigned long to_ulong() const; 435 unsigned long long to_ullong() const; 436 437 bool all() const; 438 bool any() const; 439 440 size_t __hash_code() const; 441}; 442 443template <size_t _Size> 444inline _LIBCPP_INLINE_VISIBILITY 445__bitset<1, _Size>::__bitset() 446 : __first_(0) 447{ 448} 449 450template <size_t _Size> 451inline _LIBCPP_INLINE_VISIBILITY 452__bitset<1, _Size>::__bitset(unsigned long long __v) 453 : __first_(static_cast<__storage_type>(__v)) 454{ 455} 456 457template <size_t _Size> 458inline _LIBCPP_INLINE_VISIBILITY 459void 460__bitset<1, _Size>::operator&=(const __bitset& __v) 461{ 462 __first_ &= __v.__first_; 463} 464 465template <size_t _Size> 466inline _LIBCPP_INLINE_VISIBILITY 467void 468__bitset<1, _Size>::operator|=(const __bitset& __v) 469{ 470 __first_ |= __v.__first_; 471} 472 473template <size_t _Size> 474inline _LIBCPP_INLINE_VISIBILITY 475void 476__bitset<1, _Size>::operator^=(const __bitset& __v) 477{ 478 __first_ ^= __v.__first_; 479} 480 481template <size_t _Size> 482inline _LIBCPP_INLINE_VISIBILITY 483void 484__bitset<1, _Size>::flip() 485{ 486 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); 487 __first_ = ~__first_; 488 __first_ &= __m; 489} 490 491template <size_t _Size> 492inline _LIBCPP_INLINE_VISIBILITY 493unsigned long 494__bitset<1, _Size>::to_ulong() const 495{ 496 return __first_; 497} 498 499template <size_t _Size> 500inline _LIBCPP_INLINE_VISIBILITY 501unsigned long long 502__bitset<1, _Size>::to_ullong() const 503{ 504 return __first_; 505} 506 507template <size_t _Size> 508inline _LIBCPP_INLINE_VISIBILITY 509bool 510__bitset<1, _Size>::all() const 511{ 512 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); 513 return !(~__first_ & __m); 514} 515 516template <size_t _Size> 517inline _LIBCPP_INLINE_VISIBILITY 518bool 519__bitset<1, _Size>::any() const 520{ 521 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - _Size); 522 return __first_ & __m; 523} 524 525template <size_t _Size> 526inline _LIBCPP_INLINE_VISIBILITY 527size_t 528__bitset<1, _Size>::__hash_code() const 529{ 530 return __first_; 531} 532 533template <> 534class __bitset<0, 0> 535{ 536public: 537 typedef ptrdiff_t difference_type; 538 typedef size_t size_type; 539protected: 540 typedef __bitset __self; 541 typedef size_type __storage_type; 542 typedef __storage_type* __storage_pointer; 543 typedef const __storage_type* __const_storage_pointer; 544 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 545 546 friend class __bit_reference<__bitset>; 547 friend class __bit_const_reference<__bitset>; 548 friend class __bit_iterator<__bitset, false>; 549 friend class __bit_iterator<__bitset, true>; 550 friend class __bit_array<__bitset>; 551 552 typedef __bit_reference<__bitset> reference; 553 typedef __bit_const_reference<__bitset> const_reference; 554 typedef __bit_iterator<__bitset, false> iterator; 555 typedef __bit_iterator<__bitset, true> const_iterator; 556 557 __bitset(); 558 explicit __bitset(unsigned long long); 559 560 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_t) 561 {return reference(0, 1);} 562 _LIBCPP_INLINE_VISIBILITY const_reference __make_ref(size_t) const 563 {return const_reference(0, 1);} 564 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_t __pos) 565 {return iterator(0, 0);} 566 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_t __pos) const 567 {return const_iterator(0, 0);} 568 569 _LIBCPP_INLINE_VISIBILITY void operator&=(const __bitset&) {} 570 _LIBCPP_INLINE_VISIBILITY void operator|=(const __bitset&) {} 571 _LIBCPP_INLINE_VISIBILITY void operator^=(const __bitset&) {} 572 573 _LIBCPP_INLINE_VISIBILITY void flip() {} 574 575 _LIBCPP_INLINE_VISIBILITY unsigned long to_ulong() const {return 0;} 576 _LIBCPP_INLINE_VISIBILITY unsigned long long to_ullong() const {return 0;} 577 578 _LIBCPP_INLINE_VISIBILITY bool all() const {return true;} 579 _LIBCPP_INLINE_VISIBILITY bool any() const {return false;} 580 581 _LIBCPP_INLINE_VISIBILITY size_t __hash_code() const {return 0;} 582}; 583 584inline _LIBCPP_INLINE_VISIBILITY 585__bitset<0, 0>::__bitset() 586{ 587} 588 589inline _LIBCPP_INLINE_VISIBILITY 590__bitset<0, 0>::__bitset(unsigned long long) 591{ 592} 593 594template <size_t _Size> class bitset; 595template <size_t _Size> struct hash<bitset<_Size> >; 596 597template <size_t _Size> 598class _LIBCPP_VISIBLE bitset 599 : private __bitset<_Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1, _Size> 600{ 601 static const unsigned __n_words = _Size == 0 ? 0 : (_Size - 1) / (sizeof(size_t) * CHAR_BIT) + 1; 602 typedef __bitset<__n_words, _Size> base; 603 604public: 605 typedef typename base::reference reference; 606 typedef typename base::const_reference const_reference; 607 608 // 23.3.5.1 constructors: 609 /*constexpr*/ _LIBCPP_INLINE_VISIBILITY bitset() {} 610 /*constexpr*/ _LIBCPP_INLINE_VISIBILITY bitset(unsigned long long __v) : base(__v) {} 611 template<class _CharT> 612 explicit bitset(const _CharT* __str, 613 typename basic_string<_CharT>::size_type __n = basic_string<_CharT>::npos, 614 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')); 615 template<class _CharT, class _Traits, class _Allocator> 616 explicit bitset(const basic_string<_CharT,_Traits,_Allocator>& __str, 617 typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos = 0, 618 typename basic_string<_CharT,_Traits,_Allocator>::size_type __n = 619 (basic_string<_CharT,_Traits,_Allocator>::npos), 620 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')); 621 622 // 23.3.5.2 bitset operations: 623 bitset& operator&=(const bitset& __rhs); 624 bitset& operator|=(const bitset& __rhs); 625 bitset& operator^=(const bitset& __rhs); 626 bitset& operator<<=(size_t __pos); 627 bitset& operator>>=(size_t __pos); 628 bitset& set(); 629 bitset& set(size_t __pos, bool __val = true); 630 bitset& reset(); 631 bitset& reset(size_t __pos); 632 bitset operator~() const; 633 bitset& flip(); 634 bitset& flip(size_t __pos); 635 636 // element access: 637 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_t __p) const {return base::__make_ref(__p);} 638 _LIBCPP_INLINE_VISIBILITY reference operator[](size_t __p) {return base::__make_ref(__p);} 639 unsigned long to_ulong() const; 640 unsigned long long to_ullong() const; 641 template <class _CharT, class _Traits, class _Allocator> 642 basic_string<_CharT, _Traits, _Allocator> to_string(_CharT __zero = _CharT('0'), 643 _CharT __one = _CharT('1')) const; 644 template <class _CharT, class _Traits> 645 basic_string<_CharT, _Traits, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'), 646 _CharT __one = _CharT('1')) const; 647 template <class _CharT> 648 basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> > to_string(_CharT __zero = _CharT('0'), 649 _CharT __one = _CharT('1')) const; 650 basic_string<char, char_traits<char>, allocator<char> > to_string(char __zero = '0', 651 char __one = '1') const; 652 size_t count() const; 653 /*constexpr*/ _LIBCPP_INLINE_VISIBILITY size_t size() const {return _Size;} 654 bool operator==(const bitset& __rhs) const; 655 bool operator!=(const bitset& __rhs) const; 656 bool test(size_t __pos) const; 657 bool all() const; 658 bool any() const; 659 _LIBCPP_INLINE_VISIBILITY bool none() const {return !any();} 660 bitset operator<<(size_t __pos) const; 661 bitset operator>>(size_t __pos) const; 662 663private: 664 665 _LIBCPP_INLINE_VISIBILITY 666 size_t __hash_code() const {return base::__hash_code();} 667 668 friend struct hash<bitset>; 669}; 670 671template <size_t _Size> 672template<class _CharT> 673bitset<_Size>::bitset(const _CharT* __str, 674 typename basic_string<_CharT>::size_type __n, 675 _CharT __zero, _CharT __one) 676{ 677 size_t __rlen = _STD::min(__n, char_traits<_CharT>::length(__str)); 678 for (size_t __i = 0; __i < __rlen; ++__i) 679 if (__str[__i] != __zero && __str[__i] != __one) 680#ifndef _LIBCPP_NO_EXCEPTIONS 681 throw invalid_argument("bitset string ctor has invalid argument"); 682#else 683 assert(!"bitset string ctor has invalid argument"); 684#endif 685 size_t _M = _STD::min(__rlen, _Size); 686 size_t __i = 0; 687 for (; __i < _M; ++__i) 688 { 689 _CharT __c = __str[_M - 1 - __i]; 690 if (__c == __zero) 691 (*this)[__i] = false; 692 else 693 (*this)[__i] = true; 694 } 695 _STD::fill(base::__make_iter(__i), base::__make_iter(_Size), false); 696} 697 698template <size_t _Size> 699template<class _CharT, class _Traits, class _Allocator> 700bitset<_Size>::bitset(const basic_string<_CharT,_Traits,_Allocator>& __str, 701 typename basic_string<_CharT,_Traits,_Allocator>::size_type __pos, 702 typename basic_string<_CharT,_Traits,_Allocator>::size_type __n, 703 _CharT __zero, _CharT __one) 704{ 705 if (__pos > __str.size()) 706#ifndef _LIBCPP_NO_EXCEPTIONS 707 throw out_of_range("bitset string pos out of range"); 708#else 709 assert(!"bitset string pos out of range"); 710#endif 711 size_t __rlen = _STD::min(__n, __str.size() - __pos); 712 for (size_t __i = __pos; __i < __pos + __rlen; ++__i) 713 if (!_Traits::eq(__str[__i], __zero) && !_Traits::eq(__str[__i], __one)) 714#ifndef _LIBCPP_NO_EXCEPTIONS 715 throw invalid_argument("bitset string ctor has invalid argument"); 716#else 717 assert(!"bitset string ctor has invalid argument"); 718#endif 719 size_t _M = _STD::min(__rlen, _Size); 720 size_t __i = 0; 721 for (; __i < _M; ++__i) 722 { 723 _CharT __c = __str[__pos + _M - 1 - __i]; 724 if (_Traits::eq(__c, __zero)) 725 (*this)[__i] = false; 726 else 727 (*this)[__i] = true; 728 } 729 _STD::fill(base::__make_iter(__i), base::__make_iter(_Size), false); 730} 731 732template <size_t _Size> 733inline _LIBCPP_INLINE_VISIBILITY 734bitset<_Size>& 735bitset<_Size>::operator&=(const bitset& __rhs) 736{ 737 base::operator&=(__rhs); 738 return *this; 739} 740 741template <size_t _Size> 742inline _LIBCPP_INLINE_VISIBILITY 743bitset<_Size>& 744bitset<_Size>::operator|=(const bitset& __rhs) 745{ 746 base::operator|=(__rhs); 747 return *this; 748} 749 750template <size_t _Size> 751inline _LIBCPP_INLINE_VISIBILITY 752bitset<_Size>& 753bitset<_Size>::operator^=(const bitset& __rhs) 754{ 755 base::operator^=(__rhs); 756 return *this; 757} 758 759template <size_t _Size> 760bitset<_Size>& 761bitset<_Size>::operator<<=(size_t __pos) 762{ 763 __pos = _STD::min(__pos, _Size); 764 _STD::copy_backward(base::__make_iter(0), base::__make_iter(_Size - __pos), base::__make_iter(_Size)); 765 _STD::fill_n(base::__make_iter(0), __pos, false); 766 return *this; 767} 768 769template <size_t _Size> 770bitset<_Size>& 771bitset<_Size>::operator>>=(size_t __pos) 772{ 773 __pos = _STD::min(__pos, _Size); 774 _STD::copy(base::__make_iter(__pos), base::__make_iter(_Size), base::__make_iter(0)); 775 _STD::fill_n(base::__make_iter(_Size - __pos), __pos, false); 776 return *this; 777} 778 779template <size_t _Size> 780inline _LIBCPP_INLINE_VISIBILITY 781bitset<_Size>& 782bitset<_Size>::set() 783{ 784 _STD::fill_n(base::__make_iter(0), _Size, true); 785 return *this; 786} 787 788template <size_t _Size> 789bitset<_Size>& 790bitset<_Size>::set(size_t __pos, bool __val) 791{ 792 if (__pos >= _Size) 793#ifndef _LIBCPP_NO_EXCEPTIONS 794 throw out_of_range("bitset set argument out of range"); 795#else 796 assert(!"bitset set argument out of range"); 797#endif 798 (*this)[__pos] = __val; 799 return *this; 800} 801 802template <size_t _Size> 803inline _LIBCPP_INLINE_VISIBILITY 804bitset<_Size>& 805bitset<_Size>::reset() 806{ 807 _STD::fill_n(base::__make_iter(0), _Size, false); 808 return *this; 809} 810 811template <size_t _Size> 812bitset<_Size>& 813bitset<_Size>::reset(size_t __pos) 814{ 815 if (__pos >= _Size) 816#ifndef _LIBCPP_NO_EXCEPTIONS 817 throw out_of_range("bitset reset argument out of range"); 818#else 819 assert(!"bitset reset argument out of range"); 820#endif 821 (*this)[__pos] = false; 822 return *this; 823} 824 825template <size_t _Size> 826inline _LIBCPP_INLINE_VISIBILITY 827bitset<_Size> 828bitset<_Size>::operator~() const 829{ 830 bitset __x(*this); 831 __x.flip(); 832 return __x; 833} 834 835template <size_t _Size> 836inline _LIBCPP_INLINE_VISIBILITY 837bitset<_Size>& 838bitset<_Size>::flip() 839{ 840 base::flip(); 841 return *this; 842} 843 844template <size_t _Size> 845bitset<_Size>& 846bitset<_Size>::flip(size_t __pos) 847{ 848 if (__pos >= _Size) 849#ifndef _LIBCPP_NO_EXCEPTIONS 850 throw out_of_range("bitset flip argument out of range"); 851#else 852 assert(!"bitset flip argument out of range"); 853#endif 854 reference r = base::__make_ref(__pos); 855 r = ~r; 856 return *this; 857} 858 859template <size_t _Size> 860inline _LIBCPP_INLINE_VISIBILITY 861unsigned long 862bitset<_Size>::to_ulong() const 863{ 864 return base::to_ulong(); 865} 866 867template <size_t _Size> 868inline _LIBCPP_INLINE_VISIBILITY 869unsigned long long 870bitset<_Size>::to_ullong() const 871{ 872 return base::to_ullong(); 873} 874 875template <size_t _Size> 876template <class _CharT, class _Traits, class _Allocator> 877basic_string<_CharT, _Traits, _Allocator> 878bitset<_Size>::to_string(_CharT __zero, _CharT __one) const 879{ 880 basic_string<_CharT, _Traits, _Allocator> __r(_Size, __zero); 881 for (size_t __i = 0; __i < _Size; ++__i) 882 { 883 if ((*this)[__i]) 884 __r[_Size - 1 - __i] = __one; 885 } 886 return __r; 887} 888 889template <size_t _Size> 890template <class _CharT, class _Traits> 891inline _LIBCPP_INLINE_VISIBILITY 892basic_string<_CharT, _Traits, allocator<_CharT> > 893bitset<_Size>::to_string(_CharT __zero, _CharT __one) const 894{ 895 return to_string<_CharT, _Traits, allocator<_CharT> >(__zero, __one); 896} 897 898template <size_t _Size> 899template <class _CharT> 900inline _LIBCPP_INLINE_VISIBILITY 901basic_string<_CharT, char_traits<_CharT>, allocator<_CharT> > 902bitset<_Size>::to_string(_CharT __zero, _CharT __one) const 903{ 904 return to_string<_CharT, char_traits<_CharT>, allocator<_CharT> >(__zero, __one); 905} 906 907template <size_t _Size> 908inline _LIBCPP_INLINE_VISIBILITY 909basic_string<char, char_traits<char>, allocator<char> > 910bitset<_Size>::to_string(char __zero, char __one) const 911{ 912 return to_string<char, char_traits<char>, allocator<char> >(__zero, __one); 913} 914 915template <size_t _Size> 916inline _LIBCPP_INLINE_VISIBILITY 917size_t 918bitset<_Size>::count() const 919{ 920 return static_cast<size_t>(_STD::count(base::__make_iter(0), base::__make_iter(_Size), true)); 921} 922 923template <size_t _Size> 924inline _LIBCPP_INLINE_VISIBILITY 925bool 926bitset<_Size>::operator==(const bitset& __rhs) const 927{ 928 return _STD::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0)); 929} 930 931template <size_t _Size> 932inline _LIBCPP_INLINE_VISIBILITY 933bool 934bitset<_Size>::operator!=(const bitset& __rhs) const 935{ 936 return !(*this == __rhs); 937} 938 939template <size_t _Size> 940bool 941bitset<_Size>::test(size_t __pos) const 942{ 943 if (__pos >= _Size) 944#ifndef _LIBCPP_NO_EXCEPTIONS 945 throw out_of_range("bitset test argument out of range"); 946#else 947 assert(!"bitset test argument out of range"); 948#endif 949 return (*this)[__pos]; 950} 951 952template <size_t _Size> 953inline _LIBCPP_INLINE_VISIBILITY 954bool 955bitset<_Size>::all() const 956{ 957 return base::all(); 958} 959 960template <size_t _Size> 961inline _LIBCPP_INLINE_VISIBILITY 962bool 963bitset<_Size>::any() const 964{ 965 return base::any(); 966} 967 968template <size_t _Size> 969inline _LIBCPP_INLINE_VISIBILITY 970bitset<_Size> 971bitset<_Size>::operator<<(size_t __pos) const 972{ 973 bitset __r = *this; 974 __r <<= __pos; 975 return __r; 976} 977 978template <size_t _Size> 979inline _LIBCPP_INLINE_VISIBILITY 980bitset<_Size> 981bitset<_Size>::operator>>(size_t __pos) const 982{ 983 bitset __r = *this; 984 __r >>= __pos; 985 return __r; 986} 987 988template <size_t _Size> 989inline _LIBCPP_INLINE_VISIBILITY 990bitset<_Size> 991operator&(const bitset<_Size>& __x, const bitset<_Size>& __y) 992{ 993 bitset<_Size> __r = __x; 994 __r &= __y; 995 return __r; 996} 997 998template <size_t _Size> 999inline _LIBCPP_INLINE_VISIBILITY 1000bitset<_Size> 1001operator|(const bitset<_Size>& __x, const bitset<_Size>& __y) 1002{ 1003 bitset<_Size> __r = __x; 1004 __r |= __y; 1005 return __r; 1006} 1007 1008template <size_t _Size> 1009inline _LIBCPP_INLINE_VISIBILITY 1010bitset<_Size> 1011operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) 1012{ 1013 bitset<_Size> __r = __x; 1014 __r ^= __y; 1015 return __r; 1016} 1017 1018template <size_t _Size> 1019struct _LIBCPP_VISIBLE hash<bitset<_Size> > 1020 : public unary_function<bitset<_Size>, size_t> 1021{ 1022 _LIBCPP_INLINE_VISIBILITY 1023 size_t operator()(const bitset<_Size>& __bs) const 1024 {return __bs.__hash_code();} 1025}; 1026 1027_LIBCPP_END_NAMESPACE_STD 1028 1029#endif // _LIBCPP_BITSET 1030