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