Where Online Learning is simpler!
The C and C++ Include Header Files
cat -n /usr/include/c++/15/tr2/dynamic_bitset
1 // TR2 <dynamic_bitset> -*- C++ -*- 2 3 // Copyright (C) 2009-2025 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file tr2/dynamic_bitset 26 * This is a TR2 C++ Library header. 27 */ 28 29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET 30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1 31 32 #ifdef _GLIBCXX_SYSHDR 33 #pragma GCC system_header 34 #endif 35 36 #include <limits> 37 #include <vector> 38 #include <string> 39 #include <istream> 40 #include <bits/functexcept.h> 41 #include <bits/stl_algo.h> // For fill 42 #include <bits/cxxabi_forced.h> 43 44 namespace std _GLIBCXX_VISIBILITY(default) 45 { 46 _GLIBCXX_BEGIN_NAMESPACE_VERSION 47 48 namespace tr2 49 { 50 /** 51 * @defgroup dynamic_bitset Dynamic Bitset. 52 * @ingroup extensions 53 * 54 * @{ 55 */ 56 57 /** 58 * Base class, general case. 59 * 60 * See documentation for dynamic_bitset. 61 */ 62 template<typename _WordT = unsigned long long, 63 typename _Alloc = std::allocator<_WordT>> 64 struct __dynamic_bitset_base 65 { 66 static_assert(std::is_unsigned<_WordT>::value, "template argument " 67 "_WordT not an unsigned integral type"); 68 69 typedef _WordT block_type; 70 typedef _Alloc allocator_type; 71 typedef size_t size_type; 72 73 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type); 74 static const size_type npos = static_cast<size_type>(-1); 75 76 /// 0 is the least significant word. 77 std::vector<block_type, allocator_type> _M_w; 78 79 explicit 80 __dynamic_bitset_base(const allocator_type& __alloc) 81 : _M_w(__alloc) 82 { } 83 84 __dynamic_bitset_base() = default; 85 __dynamic_bitset_base(const __dynamic_bitset_base&) = default; 86 __dynamic_bitset_base(__dynamic_bitset_base&& __b) = default; 87 __dynamic_bitset_base& operator=(const __dynamic_bitset_base&) = default; 88 __dynamic_bitset_base& operator=(__dynamic_bitset_base&&) = default; 89 ~__dynamic_bitset_base() = default; 90 91 explicit 92 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL, 93 const allocator_type& __alloc = allocator_type()) 94 : _M_w(__nbits / _S_bits_per_block + (__nbits % _S_bits_per_block > 0), 95 block_type(0), __alloc) 96 { 97 if (__nbits < std::numeric_limits<decltype(__val)>::digits) 98 __val &= ~(-1ULL << __nbits); 99 if (__val == 0) 100 return; 101 102 if _GLIBCXX17_CONSTEXPR (sizeof(__val) == sizeof(block_type)) 103 _M_w[0] = __val; 104 else 105 { 106 const size_t __n 107 = std::min(_M_w.size(), sizeof(__val) / sizeof(block_type)); 108 for (size_t __i = 0; __val && __i < __n; ++__i) 109 { 110 _M_w[__i] = static_cast<block_type>(__val); 111 __val >>= _S_bits_per_block; 112 } 113 } 114 } 115 116 void 117 _M_swap(__dynamic_bitset_base& __b) noexcept 118 { this->_M_w.swap(__b._M_w); } 119 120 void 121 _M_clear() noexcept 122 { this->_M_w.clear(); } 123 124 void 125 _M_resize(size_t __nbits, bool __value) 126 { 127 size_t __sz = __nbits / _S_bits_per_block; 128 if (__nbits % _S_bits_per_block > 0) 129 ++__sz; 130 if (__sz != this->_M_w.size()) 131 { 132 block_type __val = 0; 133 if (__value) 134 __val = std::numeric_limits<block_type>::max(); 135 this->_M_w.resize(__sz, __val); 136 } 137 } 138 139 allocator_type 140 _M_get_allocator() const noexcept 141 { return this->_M_w.get_allocator(); } 142 143 static size_type 144 _S_whichword(size_type __pos) noexcept 145 { return __pos / _S_bits_per_block; } 146 147 static size_type 148 _S_whichbyte(size_type __pos) noexcept 149 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; } 150 151 static size_type 152 _S_whichbit(size_type __pos) noexcept 153 { return __pos % _S_bits_per_block; } 154 155 static block_type 156 _S_maskbit(size_type __pos) noexcept 157 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); } 158 159 block_type& 160 _M_getword(size_type __pos) noexcept 161 { return this->_M_w[_S_whichword(__pos)]; } 162 163 block_type 164 _M_getword(size_type __pos) const noexcept 165 { return this->_M_w[_S_whichword(__pos)]; } 166 167 block_type& 168 _M_hiword() noexcept 169 { return this->_M_w[_M_w.size() - 1]; } 170 171 block_type 172 _M_hiword() const noexcept 173 { return this->_M_w[_M_w.size() - 1]; } 174 175 void 176 _M_do_and(const __dynamic_bitset_base& __x) noexcept 177 { 178 if (__x._M_w.size() == this->_M_w.size()) 179 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 180 this->_M_w[__i] &= __x._M_w[__i]; 181 else 182 return; 183 } 184 185 void 186 _M_do_or(const __dynamic_bitset_base& __x) noexcept 187 { 188 if (__x._M_w.size() == this->_M_w.size()) 189 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 190 this->_M_w[__i] |= __x._M_w[__i]; 191 else 192 return; 193 } 194 195 void 196 _M_do_xor(const __dynamic_bitset_base& __x) noexcept 197 { 198 if (__x._M_w.size() == this->_M_w.size()) 199 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 200 this->_M_w[__i] ^= __x._M_w[__i]; 201 else 202 return; 203 } 204 205 void 206 _M_do_dif(const __dynamic_bitset_base& __x) noexcept 207 { 208 if (__x._M_w.size() == this->_M_w.size()) 209 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 210 this->_M_w[__i] &= ~__x._M_w[__i]; 211 else 212 return; 213 } 214 215 void 216 _M_do_left_shift(size_t __shift); 217 218 void 219 _M_do_right_shift(size_t __shift); 220 221 void 222 _M_do_flip() noexcept 223 { 224 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 225 this->_M_w[__i] = ~this->_M_w[__i]; 226 } 227 228 void 229 _M_do_set() noexcept 230 { 231 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 232 this->_M_w[__i] = static_cast<block_type>(-1); 233 } 234 235 void 236 _M_do_reset() noexcept 237 { 238 std::fill(_M_w.begin(), _M_w.end(), static_cast<block_type>(0)); 239 } 240 241 bool 242 _M_is_equal(const __dynamic_bitset_base& __x) const noexcept 243 { 244 if (__x._M_w.size() == this->_M_w.size()) 245 { 246 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 247 if (this->_M_w[__i] != __x._M_w[__i]) 248 return false; 249 return true; 250 } 251 else 252 return false; 253 } 254 255 bool 256 _M_is_less(const __dynamic_bitset_base& __x) const noexcept 257 { 258 if (__x._M_w.size() == this->_M_w.size()) 259 { 260 for (size_t __i = this->_M_w.size(); __i > 0; --__i) 261 { 262 if (this->_M_w[__i-1] < __x._M_w[__i-1]) 263 return true; 264 else if (this->_M_w[__i-1] > __x._M_w[__i-1]) 265 return false; 266 } 267 return false; 268 } 269 else 270 return false; 271 } 272 273 size_t 274 _M_are_all_aux() const noexcept 275 { 276 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i) 277 if (_M_w[__i] != static_cast<block_type>(-1)) 278 return 0; 279 return ((this->_M_w.size() - 1) * _S_bits_per_block 280 + __builtin_popcountll(this->_M_hiword())); 281 } 282 283 bool 284 _M_is_any() const noexcept 285 { 286 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 287 if (this->_M_w[__i] != static_cast<block_type>(0)) 288 return true; 289 return false; 290 } 291 292 bool 293 _M_is_subset_of(const __dynamic_bitset_base& __b) noexcept 294 { 295 if (__b._M_w.size() == this->_M_w.size()) 296 { 297 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 298 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i])) 299 return false; 300 return true; 301 } 302 else 303 return false; 304 } 305 306 bool 307 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const noexcept 308 { 309 if (this->_M_is_subset_of(__b)) 310 { 311 if (*this == __b) 312 return false; 313 else 314 return true; 315 } 316 else 317 return false; 318 } 319 320 size_t 321 _M_do_count() const noexcept 322 { 323 size_t __result = 0; 324 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 325 __result += __builtin_popcountll(this->_M_w[__i]); 326 return __result; 327 } 328 329 size_type 330 _M_size() const noexcept 331 { return this->_M_w.size(); } 332 333 unsigned long 334 _M_do_to_ulong() const; 335 336 unsigned long long 337 _M_do_to_ullong() const; 338 339 // find first "on" bit 340 size_type 341 _M_do_find_first(size_t __not_found) const; 342 343 // find the next "on" bit that follows "prev" 344 size_type 345 _M_do_find_next(size_t __prev, size_t __not_found) const; 346 347 // do append of block 348 void 349 _M_do_append_block(block_type __block, size_type __pos) 350 { 351 size_t __offset = __pos % _S_bits_per_block; 352 if (__offset == 0) 353 this->_M_w.push_back(__block); 354 else 355 { 356 this->_M_hiword() |= (__block << __offset); 357 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset)); 358 } 359 } 360 }; 361 362 /** 363 * @brief The %dynamic_bitset class represents a sequence of bits. 364 * 365 * See N2050, 366 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library. 367 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2050.pdf 368 * 369 * In the general unoptimized case, storage is allocated in 370 * word-sized blocks. Let B be the number of bits in a word, then 371 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are 372 * unused. (They are the high-order bits in the highest word.) It 373 * is a class invariant that those unused bits are always zero. 374 * 375 * If you think of %dynamic_bitset as "a simple array of bits," be 376 * aware that your mental picture is reversed: a %dynamic_bitset 377 * behaves the same way as bits in integers do, with the bit at 378 * index 0 in the "least significant / right-hand" position, and 379 * the bit at index Nb-1 in the "most significant / left-hand" 380 * position. Thus, unlike other containers, a %dynamic_bitset's 381 * index "counts from right to left," to put it very loosely. 382 * 383 * This behavior is preserved when translating to and from strings. 384 * For example, the first line of the following program probably 385 * prints "b('a') is 0001100001" on a modern ASCII system. 386 * 387 * @code 388 * #include <dynamic_bitset> 389 * #include <iostream> 390 * #include <sstream> 391 * 392 * using namespace std; 393 * 394 * int main() 395 * { 396 * long a = 'a'; 397 * dynamic_bitset<> b(a); 398 * 399 * cout << "b('a') is " << b << endl; 400 * 401 * ostringstream s; 402 * s << b; 403 * string str = s.str(); 404 * cout << "index 3 in the string is " << str[3] << " but\n" 405 * << "index 3 in the bitset is " << b[3] << endl; 406 * } 407 * @endcode 408 * 409 * Most of the actual code isn't contained in %dynamic_bitset<> 410 * itself, but in the base class __dynamic_bitset_base. The base 411 * class works with whole words, not with individual bits. This 412 * allows us to specialize __dynamic_bitset_base for the important 413 * special case where the %dynamic_bitset is only a single word. 414 * 415 * Extra confusion can result due to the fact that the storage for 416 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is 417 * carefully encapsulated. 418 */ 419 template<typename _WordT = unsigned long long, 420 typename _Alloc = std::allocator<_WordT>> 421 class dynamic_bitset 422 : private __dynamic_bitset_base<_WordT, _Alloc> 423 { 424 static_assert(std::is_unsigned<_WordT>::value, "template argument " 425 "_WordT not an unsigned integral type"); 426 427 public: 428 429 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base; 430 typedef _WordT block_type; 431 typedef _Alloc allocator_type; 432 typedef size_t size_type; 433 434 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type); 435 // Use this: constexpr size_type std::numeric_limits<size_type>::max(). 436 static const size_type npos = static_cast<size_type>(-1); 437 438 private: 439 440 // Clear the unused bits in the uppermost word. 441 void 442 _M_do_sanitize() 443 { 444 size_type __shift = this->_M_Nb % bits_per_block; 445 if (__shift > 0) 446 this->_M_hiword() &= block_type(~(block_type(-1) << __shift)); 447 } 448 449 // Set the unused bits in the uppermost word. 450 void 451 _M_do_fill() 452 { 453 size_type __shift = this->_M_Nb % bits_per_block; 454 if (__shift > 0) 455 this->_M_hiword() |= block_type(block_type(-1) << __shift); 456 } 457 458 /** 459 * These versions of single-bit set, reset, flip, and test 460 * do no range checking. 461 */ 462 dynamic_bitset& 463 _M_unchecked_set(size_type __pos) noexcept 464 { 465 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 466 return *this; 467 } 468 469 dynamic_bitset& 470 _M_unchecked_set(size_type __pos, int __val) noexcept 471 { 472 if (__val) 473 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 474 else 475 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 476 return *this; 477 } 478 479 dynamic_bitset& 480 _M_unchecked_reset(size_type __pos) noexcept 481 { 482 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 483 return *this; 484 } 485 486 dynamic_bitset& 487 _M_unchecked_flip(size_type __pos) noexcept 488 { 489 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 490 return *this; 491 } 492 493 bool 494 _M_unchecked_test(size_type __pos) const noexcept 495 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 496 != static_cast<_WordT>(0)); } 497 498 size_type _M_Nb = 0; 499 500 public: 501 /** 502 * This encapsulates the concept of a single bit. An instance 503 * of this class is a proxy for an actual bit; this way the 504 * individual bit operations are done as faster word-size 505 * bitwise instructions. 506 * 507 * Most users will never need to use this class directly; 508 * conversions to and from bool are automatic and should be 509 * transparent. Overloaded operators help to preserve the 510 * illusion. 511 * 512 * (On a typical system, this "bit %reference" is 64 times the 513 * size of an actual bit. Ha.) 514 */ 515 class reference 516 { 517 friend class dynamic_bitset; 518 519 block_type *_M_wp; 520 size_type _M_bpos; 521 522 public: 523 reference(dynamic_bitset& __b, size_type __pos) noexcept 524 { 525 this->_M_wp = &__b._M_getword(__pos); 526 this->_M_bpos = _Base::_S_whichbit(__pos); 527 } 528 529 // For b[i] = __x; 530 reference& 531 operator=(bool __x) noexcept 532 { 533 if (__x) 534 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 535 else 536 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 537 return *this; 538 } 539 540 // For b[i] = b[__j]; 541 reference& 542 operator=(const reference& __j) noexcept 543 { 544 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 545 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos); 546 else 547 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos); 548 return *this; 549 } 550 551 // Flips the bit 552 bool 553 operator~() const noexcept 554 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; } 555 556 // For __x = b[i]; 557 operator bool() const noexcept 558 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; } 559 560 // For b[i].flip(); 561 reference& 562 flip() noexcept 563 { 564 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos); 565 return *this; 566 } 567 }; 568 569 friend class reference; 570 571 typedef bool const_reference; 572 573 // 23.3.5.1 constructors: 574 575 /// All bits set to zero. 576 dynamic_bitset() = default; 577 578 /// All bits set to zero. 579 explicit 580 dynamic_bitset(const allocator_type& __alloc) 581 : _Base(__alloc) 582 { } 583 584 /// Initial bits bitwise-copied from a single word (others set to zero). 585 explicit 586 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL, 587 const allocator_type& __alloc = allocator_type()) 588 : _Base(__nbits, __val, __alloc), 589 _M_Nb(__nbits) 590 { } 591 592 dynamic_bitset(initializer_list<block_type> __il, 593 const allocator_type& __alloc = allocator_type()) 594 : _Base(__alloc) 595 { this->append(__il); } 596 597 /** 598 * @brief Use a subset of a string. 599 * @param __str A string of '0' and '1' characters. 600 * @param __pos Index of the first character in @p __str to use. 601 * @param __n The number of characters to copy. 602 * @param __zero The character to use for unset bits. 603 * @param __one The character to use for set bits. 604 * @param __alloc An allocator. 605 * @throw std::out_of_range If @p __pos is bigger the size of @p __str. 606 * @throw std::invalid_argument If a character appears in the string 607 * which is neither '0' nor '1'. 608 */ 609 template<typename _CharT, typename _Traits, typename _Alloc1> 610 explicit 611 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str, 612 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 613 __pos = 0, 614 typename basic_string<_CharT,_Traits,_Alloc1>::size_type 615 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos, 616 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'), 617 const allocator_type& __alloc = allocator_type()) 618 : _Base(__alloc) 619 { 620 if (__pos > __str.size()) 621 __throw_out_of_range(__N("dynamic_bitset::bitset initial position " 622 "not valid")); 623 624 // Watch for npos. 625 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n); 626 this->resize(this->_M_Nb); 627 this->_M_copy_from_string(__str, __pos, __n, __zero, __one); 628 } 629 630 /** 631 * @brief Construct from a string. 632 * @param __str A string of '0' and '1' characters. 633 * @param __alloc An allocator. 634 * @throw std::invalid_argument If a character appears in the string 635 * which is neither '0' nor '1'. 636 */ 637 explicit 638 dynamic_bitset(const char* __str, 639 const allocator_type& __alloc = allocator_type()) 640 : _Base(__builtin_strlen(__str), 0ULL, __alloc), 641 _M_Nb(__builtin_strlen(__str)) 642 { 643 this->_M_copy_from_ptr(__str, _M_Nb, 0, _M_Nb); 644 } 645 646 /// Copy constructor. 647 dynamic_bitset(const dynamic_bitset&) = default; 648 649 /// Move constructor. 650 dynamic_bitset(dynamic_bitset&& __b) noexcept 651 : _Base(std::move(__b)), _M_Nb(__b._M_Nb) 652 { __b.clear(); } 653 654 /// Swap with another bitset. 655 void 656 swap(dynamic_bitset& __b) noexcept 657 { 658 this->_M_swap(__b); 659 std::swap(this->_M_Nb, __b._M_Nb); 660 } 661 662 /// Copy assignment operator. 663 dynamic_bitset& operator=(const dynamic_bitset&) = default; 664 665 /// Move assignment operator. 666 dynamic_bitset& 667 operator=(dynamic_bitset&& __b) 668 noexcept(std::is_nothrow_move_assignable<_Base>::value) 669 { 670 static_cast<_Base&>(*this) = static_cast<_Base&&>(__b); 671 _M_Nb = __b._M_Nb; 672 if _GLIBCXX17_CONSTEXPR (std::is_nothrow_move_assignable<_Base>::value) 673 __b._M_Nb = 0; 674 else if (get_allocator() == __b.get_allocator()) 675 __b._M_Nb = 0; 676 return *this; 677 } 678 679 /** 680 * @brief Return the allocator for the bitset. 681 */ 682 allocator_type 683 get_allocator() const noexcept 684 { return this->_M_get_allocator(); } 685 686 /** 687 * @brief Resize the bitset. 688 */ 689 void 690 resize(size_type __nbits, bool __value = false) 691 { 692 if (__value) 693 this->_M_do_fill(); 694 this->_M_resize(__nbits, __value); 695 this->_M_Nb = __nbits; 696 this->_M_do_sanitize(); 697 } 698 699 /** 700 * @brief Clear the bitset. 701 */ 702 void 703 clear() 704 { 705 this->_M_clear(); 706 this->_M_Nb = 0; 707 } 708 709 /** 710 * @brief Push a bit onto the high end of the bitset. 711 */ 712 void 713 push_back(bool __bit) 714 { 715 if (this->size() % bits_per_block == 0) 716 this->_M_do_append_block(block_type(__bit), this->_M_Nb); 717 else 718 this->_M_unchecked_set(this->_M_Nb, __bit); 719 ++this->_M_Nb; 720 } 721 722 // XXX why is there no pop_back() member in the proposal? 723 724 /** 725 * @brief Append a block. 726 */ 727 void 728 append(block_type __block) 729 { 730 this->_M_do_append_block(__block, this->_M_Nb); 731 this->_M_Nb += bits_per_block; 732 } 733 734 /** 735 * @brief 736 */ 737 void 738 append(initializer_list<block_type> __il) 739 { this->append(__il.begin(), __il.end()); } 740 741 /** 742 * @brief Append an iterator range of blocks. 743 */ 744 template <typename _BlockInputIterator> 745 void 746 append(_BlockInputIterator __first, _BlockInputIterator __last) 747 { 748 for (; __first != __last; ++__first) 749 this->append(*__first); 750 } 751 752 // 23.3.5.2 dynamic_bitset operations: 753 ///@{ 754 /** 755 * @brief Operations on dynamic_bitsets. 756 * @param __rhs A same-sized dynamic_bitset. 757 * 758 * These should be self-explanatory. 759 */ 760 dynamic_bitset& 761 operator&=(const dynamic_bitset& __rhs) 762 { 763 this->_M_do_and(__rhs); 764 return *this; 765 } 766 767 dynamic_bitset& 768 operator&=(dynamic_bitset&& __rhs) 769 { 770 this->_M_do_and(std::move(__rhs)); 771 return *this; 772 } 773 774 dynamic_bitset& 775 operator|=(const dynamic_bitset& __rhs) 776 { 777 this->_M_do_or(__rhs); 778 return *this; 779 } 780 781 dynamic_bitset& 782 operator^=(const dynamic_bitset& __rhs) 783 { 784 this->_M_do_xor(__rhs); 785 return *this; 786 } 787 788 dynamic_bitset& 789 operator-=(const dynamic_bitset& __rhs) 790 { 791 this->_M_do_dif(__rhs); 792 return *this; 793 } 794 ///@} 795 796 ///@{ 797 /** 798 * @brief Operations on dynamic_bitsets. 799 * @param __pos The number of places to shift. 800 * 801 * These should be self-explanatory. 802 */ 803 dynamic_bitset& 804 operator<<=(size_type __pos) 805 { 806 if (__builtin_expect(__pos < this->_M_Nb, 1)) 807 { 808 this->_M_do_left_shift(__pos); 809 this->_M_do_sanitize(); 810 } 811 else 812 this->_M_do_reset(); 813 return *this; 814 } 815 816 dynamic_bitset& 817 operator>>=(size_type __pos) 818 { 819 if (__builtin_expect(__pos < this->_M_Nb, 1)) 820 this->_M_do_right_shift(__pos); 821 else 822 this->_M_do_reset(); 823 return *this; 824 } 825 ///@} 826 827 // Set, reset, and flip. 828 /** 829 * @brief Sets every bit to true. 830 */ 831 dynamic_bitset& 832 set() 833 { 834 this->_M_do_set(); 835 this->_M_do_sanitize(); 836 return *this; 837 } 838 839 /** 840 * @brief Sets a given bit to a particular value. 841 * @param __pos The index of the bit. 842 * @param __val Either true or false, defaults to true. 843 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 844 */ 845 dynamic_bitset& 846 set(size_type __pos, bool __val = true) 847 { 848 if (__pos >= _M_Nb) 849 __throw_out_of_range(__N("dynamic_bitset::set")); 850 return this->_M_unchecked_set(__pos, __val); 851 } 852 853 /** 854 * @brief Sets every bit to false. 855 */ 856 dynamic_bitset& 857 reset() 858 { 859 this->_M_do_reset(); 860 return *this; 861 } 862 863 /** 864 * @brief Sets a given bit to false. 865 * @param __pos The index of the bit. 866 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 867 * 868 * Same as writing @c set(__pos, false). 869 */ 870 dynamic_bitset& 871 reset(size_type __pos) 872 { 873 if (__pos >= _M_Nb) 874 __throw_out_of_range(__N("dynamic_bitset::reset")); 875 return this->_M_unchecked_reset(__pos); 876 } 877 878 /** 879 * @brief Toggles every bit to its opposite value. 880 */ 881 dynamic_bitset& 882 flip() 883 { 884 this->_M_do_flip(); 885 this->_M_do_sanitize(); 886 return *this; 887 } 888 889 /** 890 * @brief Toggles a given bit to its opposite value. 891 * @param __pos The index of the bit. 892 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 893 */ 894 dynamic_bitset& 895 flip(size_type __pos) 896 { 897 if (__pos >= _M_Nb) 898 __throw_out_of_range(__N("dynamic_bitset::flip")); 899 return this->_M_unchecked_flip(__pos); 900 } 901 902 /// See the no-argument flip(). 903 dynamic_bitset 904 operator~() const 905 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); } 906 907 ///@{ 908 /** 909 * @brief Array-indexing support. 910 * @param __pos Index into the %dynamic_bitset. 911 * @return A bool for a 'const %dynamic_bitset'. For non-const 912 * bitsets, an instance of the reference proxy class. 913 * @note These operators do no range checking and throw no 914 * exceptions, as required by DR 11 to the standard. 915 */ 916 reference 917 operator[](size_type __pos) 918 { return reference(*this,__pos); } 919 920 const_reference 921 operator[](size_type __pos) const 922 { return _M_unchecked_test(__pos); } 923 ///@} 924 925 /** 926 * @brief Returns a numerical interpretation of the %dynamic_bitset. 927 * @return The integral equivalent of the bits. 928 * @throw std::overflow_error If there are too many bits to be 929 * represented in an @c unsigned @c long. 930 */ 931 unsigned long 932 to_ulong() const 933 { return this->_M_do_to_ulong(); } 934 935 /** 936 * @brief Returns a numerical interpretation of the %dynamic_bitset. 937 * @return The integral equivalent of the bits. 938 * @throw std::overflow_error If there are too many bits to be 939 * represented in an @c unsigned @c long. 940 */ 941 unsigned long long 942 to_ullong() const 943 { return this->_M_do_to_ullong(); } 944 945 /** 946 * @brief Returns a character interpretation of the %dynamic_bitset. 947 * @return The string equivalent of the bits. 948 * 949 * Note the ordering of the bits: decreasing character positions 950 * correspond to increasing bit positions (see the main class notes for 951 * an example). 952 */ 953 template<typename _CharT = char, 954 typename _Traits = std::char_traits<_CharT>, 955 typename _Alloc1 = std::allocator<_CharT>> 956 std::basic_string<_CharT, _Traits, _Alloc1> 957 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const 958 { 959 std::basic_string<_CharT, _Traits, _Alloc1> __result; 960 _M_copy_to_string(__result, __zero, __one); 961 return __result; 962 } 963 964 // Helper functions for string operations. 965 template<typename _Traits = std::char_traits<char>, 966 typename _CharT = typename _Traits::char_type> 967 void 968 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 969 _CharT __zero = _CharT('0'), 970 _CharT __one = _CharT('1')); 971 972 template<typename _CharT, typename _Traits, typename _Alloc1> 973 void 974 _M_copy_from_string(const basic_string<_CharT, _Traits, _Alloc1>& __str, 975 size_t __pos, size_t __n, 976 _CharT __zero = _CharT('0'), 977 _CharT __one = _CharT('1')) 978 { 979 _M_copy_from_ptr<_Traits>(__str.data(), __str.size(), __pos, __n, 980 __zero, __one); 981 } 982 983 template<typename _CharT, typename _Traits, typename _Alloc1> 984 void 985 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 986 _CharT __zero = _CharT('0'), 987 _CharT __one = _CharT('1')) const; 988 989 /// Returns the number of bits which are set. 990 size_type 991 count() const noexcept 992 { return this->_M_do_count(); } 993 994 /// Returns the total number of bits. 995 size_type 996 size() const noexcept 997 { return this->_M_Nb; } 998 999 /// Returns the total number of blocks. 1000 size_type 1001 num_blocks() const noexcept 1002 { return this->_M_size(); } 1003 1004 /// Returns true if the dynamic_bitset is empty. 1005 _GLIBCXX_NODISCARD bool 1006 empty() const noexcept 1007 { return (this->_M_Nb == 0); } 1008 1009 /// Returns the maximum size of a dynamic_bitset object having the same 1010 /// type as *this. 1011 /// The real answer is max() * bits_per_block but is likely to overflow. 1012 constexpr size_type 1013 max_size() noexcept 1014 { return std::numeric_limits<block_type>::max(); } 1015 1016 /** 1017 * @brief Tests the value of a bit. 1018 * @param __pos The index of a bit. 1019 * @return The value at @a __pos. 1020 * @throw std::out_of_range If @a __pos is bigger the size of the %set. 1021 */ 1022 bool 1023 test(size_type __pos) const 1024 { 1025 if (__pos >= _M_Nb) 1026 __throw_out_of_range(__N("dynamic_bitset::test")); 1027 return _M_unchecked_test(__pos); 1028 } 1029 1030 /** 1031 * @brief Tests whether all the bits are on. 1032 * @return True if all the bits are set. 1033 */ 1034 bool 1035 all() const 1036 { return this->_M_are_all_aux() == _M_Nb; } 1037 1038 /** 1039 * @brief Tests whether any of the bits are on. 1040 * @return True if at least one bit is set. 1041 */ 1042 bool 1043 any() const 1044 { return this->_M_is_any(); } 1045 1046 /** 1047 * @brief Tests whether any of the bits are on. 1048 * @return True if none of the bits are set. 1049 */ 1050 bool 1051 none() const 1052 { return !this->_M_is_any(); } 1053 1054 ///@{ 1055 /// Self-explanatory. 1056 dynamic_bitset 1057 operator<<(size_type __pos) const 1058 { return dynamic_bitset(*this) <<= __pos; } 1059 1060 dynamic_bitset 1061 operator>>(size_type __pos) const 1062 { return dynamic_bitset(*this) >>= __pos; } 1063 ///@} 1064 1065 /** 1066 * @brief Finds the index of the first "on" bit. 1067 * @return The index of the first bit set, or size() if not found. 1068 * @sa find_next 1069 */ 1070 size_type 1071 find_first() const 1072 { return this->_M_do_find_first(this->_M_Nb); } 1073 1074 /** 1075 * @brief Finds the index of the next "on" bit after prev. 1076 * @return The index of the next bit set, or size() if not found. 1077 * @param __prev Where to start searching. 1078 * @sa find_first 1079 */ 1080 size_type 1081 find_next(size_t __prev) const 1082 { return this->_M_do_find_next(__prev, this->_M_Nb); } 1083 1084 bool 1085 is_subset_of(const dynamic_bitset& __b) const 1086 { return this->_M_is_subset_of(__b); } 1087 1088 bool 1089 is_proper_subset_of(const dynamic_bitset& __b) const 1090 { return this->_M_is_proper_subset_of(__b); } 1091 1092 friend bool 1093 operator==(const dynamic_bitset& __lhs, 1094 const dynamic_bitset& __rhs) noexcept 1095 { return __lhs._M_Nb == __rhs._M_Nb && __lhs._M_is_equal(__rhs); } 1096 1097 friend bool 1098 operator<(const dynamic_bitset& __lhs, 1099 const dynamic_bitset& __rhs) noexcept 1100 { return __lhs._M_is_less(__rhs) || __lhs._M_Nb < __rhs._M_Nb; } 1101 }; 1102 1103 template<typename _WordT, typename _Alloc> 1104 template<typename _CharT, typename _Traits, typename _Alloc1> 1105 inline void 1106 dynamic_bitset<_WordT, _Alloc>:: 1107 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str, 1108 _CharT __zero, _CharT __one) const 1109 { 1110 __str.assign(_M_Nb, __zero); 1111 for (size_t __i = _M_Nb; __i > 0; --__i) 1112 if (_M_unchecked_test(__i - 1)) 1113 _Traits::assign(__str[_M_Nb - __i], __one); 1114 } 1115 1116 1117 ///@{ 1118 /// These comparisons for equality/inequality are, well, @e bitwise. 1119 1120 template<typename _WordT, typename _Alloc> 1121 inline bool 1122 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1123 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1124 { return !(__lhs == __rhs); } 1125 1126 template<typename _WordT, typename _Alloc> 1127 inline bool 1128 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1129 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1130 { return !(__lhs > __rhs); } 1131 1132 template<typename _WordT, typename _Alloc> 1133 inline bool 1134 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1135 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1136 { return __rhs < __lhs; } 1137 1138 template<typename _WordT, typename _Alloc> 1139 inline bool 1140 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs, 1141 const dynamic_bitset<_WordT, _Alloc>& __rhs) 1142 { return !(__lhs < __rhs); } 1143 ///@} 1144 1145 // 23.3.5.3 bitset operations: 1146 ///@{ 1147 /** 1148 * @brief Global bitwise operations on bitsets. 1149 * @param __x A bitset. 1150 * @param __y A bitset of the same size as @a __x. 1151 * @return A new bitset. 1152 * 1153 * These should be self-explanatory. 1154 */ 1155 template<typename _WordT, typename _Alloc> 1156 inline dynamic_bitset<_WordT, _Alloc> 1157 operator&(const dynamic_bitset<_WordT, _Alloc>& __x, 1158 const dynamic_bitset<_WordT, _Alloc>& __y) 1159 { 1160 dynamic_bitset<_WordT, _Alloc> __result(__x); 1161 __result &= __y; 1162 return __result; 1163 } 1164 1165 template<typename _WordT, typename _Alloc> 1166 inline dynamic_bitset<_WordT, _Alloc> 1167 operator|(const dynamic_bitset<_WordT, _Alloc>& __x, 1168 const dynamic_bitset<_WordT, _Alloc>& __y) 1169 { 1170 dynamic_bitset<_WordT, _Alloc> __result(__x); 1171 __result |= __y; 1172 return __result; 1173 } 1174 1175 template <typename _WordT, typename _Alloc> 1176 inline dynamic_bitset<_WordT, _Alloc> 1177 operator^(const dynamic_bitset<_WordT, _Alloc>& __x, 1178 const dynamic_bitset<_WordT, _Alloc>& __y) 1179 { 1180 dynamic_bitset<_WordT, _Alloc> __result(__x); 1181 __result ^= __y; 1182 return __result; 1183 } 1184 1185 template <typename _WordT, typename _Alloc> 1186 inline dynamic_bitset<_WordT, _Alloc> 1187 operator-(const dynamic_bitset<_WordT, _Alloc>& __x, 1188 const dynamic_bitset<_WordT, _Alloc>& __y) 1189 { 1190 dynamic_bitset<_WordT, _Alloc> __result(__x); 1191 __result -= __y; 1192 return __result; 1193 } 1194 ///@} 1195 1196 /// Stream output operator for dynamic_bitset. 1197 template <typename _CharT, typename _Traits, 1198 typename _WordT, typename _Alloc> 1199 inline std::basic_ostream<_CharT, _Traits>& 1200 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1201 const dynamic_bitset<_WordT, _Alloc>& __x) 1202 { 1203 std::basic_string<_CharT, _Traits> __tmp; 1204 1205 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc()); 1206 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1207 return __os << __tmp; 1208 } 1209 /** 1210 * @} 1211 */ 1212 } // tr2 1213 1214 _GLIBCXX_END_NAMESPACE_VERSION 1215 } // std 1216 1217 #include <tr2/dynamic_bitset.tcc> 1218 1219 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
