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