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