1 // TR2 <dynamic_bitset> -*- C++ -*-
3 // Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file tr2/dynamic_bitset
26 * This is a TR2 C++ Library header.
29 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
30 #define _GLIBCXX_TR2_DYNAMIC_BITSET 1
32 #pragma GCC system_header
36 #include <cstddef> // For size_t
38 #include <memory> // For std::allocator
39 #include <bits/functexcept.h> // For invalid_argument, out_of_range,
42 #include <cxxabi_forced.h>
44 namespace std _GLIBCXX_VISIBILITY(default)
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
54 * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
66 class _Bool2UChar<bool>
69 typedef unsigned char type;
75 * Base class, general case.
77 * See documentation for dynamic_bitset.
79 template<typename _WordT = unsigned long long,
80 typename _Alloc = std::allocator<_WordT>>
81 struct __dynamic_bitset_base
83 static_assert(std::is_unsigned<_WordT>::value, "template argument "
84 "_WordT not an unsigned integral type");
86 typedef _WordT block_type;
87 typedef _Alloc allocator_type;
88 typedef size_t size_type;
90 static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
91 static const size_type npos = static_cast<size_type>(-1);
93 /// 0 is the least significant word.
94 std::vector<block_type, allocator_type> _M_w;
97 __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
102 __dynamic_bitset_base(__dynamic_bitset_base&& __b)
103 { this->_M_w.swap(__b._M_w); }
106 __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
107 const allocator_type& __alloc = allocator_type())
108 : _M_w(__nbits / _S_bits_per_block
109 + (__nbits % _S_bits_per_block > 0),
112 unsigned long long __mask = ~static_cast<block_type>(0);
113 size_t __n = std::min(this->_M_w.size(),
114 sizeof(unsigned long long) / sizeof(block_type));
115 for (size_t __i = 0; __i < __n; ++__i)
117 this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
118 __mask <<= _S_bits_per_block;
123 _M_assign(const __dynamic_bitset_base& __b)
124 { this->_M_w = __b._M_w; }
127 _M_swap(__dynamic_bitset_base& __b)
128 { this->_M_w.swap(__b._M_w); }
132 { this->_M_w.clear(); }
135 _M_resize(size_t __nbits, bool __value)
137 size_t __sz = __nbits / _S_bits_per_block;
138 if (__nbits % _S_bits_per_block > 0)
140 if (__sz != this->_M_w.size())
141 this->_M_w.resize(__sz);
145 _M_get_allocator() const
146 { return this->_M_w.get_allocator(); }
149 _S_whichword(size_type __pos)
150 { return __pos / _S_bits_per_block; }
153 _S_whichbyte(size_type __pos)
154 { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
157 _S_whichbit(size_type __pos)
158 { return __pos % _S_bits_per_block; }
161 _S_maskbit(size_type __pos)
162 { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
165 _M_getword(size_type __pos)
166 { return this->_M_w[_S_whichword(__pos)]; }
169 _M_getword(size_type __pos) const
170 { return this->_M_w[_S_whichword(__pos)]; }
174 { return this->_M_w[_M_w.size() - 1]; }
178 { return this->_M_w[_M_w.size() - 1]; }
181 _M_do_and(const __dynamic_bitset_base& __x)
183 if (__x._M_w.size() == this->_M_w.size())
184 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
185 this->_M_w[__i] &= __x._M_w[__i];
191 _M_do_or(const __dynamic_bitset_base& __x)
193 if (__x._M_w.size() == this->_M_w.size())
194 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
195 this->_M_w[__i] |= __x._M_w[__i];
201 _M_do_xor(const __dynamic_bitset_base& __x)
203 if (__x._M_w.size() == this->_M_w.size())
204 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
205 this->_M_w[__i] ^= __x._M_w[__i];
211 _M_do_dif(const __dynamic_bitset_base& __x)
213 if (__x._M_w.size() == this->_M_w.size())
214 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
215 this->_M_w[__i] &= ~__x._M_w[__i];
221 _M_do_left_shift(size_t __shift);
224 _M_do_right_shift(size_t __shift);
229 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
230 this->_M_w[__i] = ~this->_M_w[__i];
236 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
237 this->_M_w[__i] = ~static_cast<block_type>(0);
243 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
244 this->_M_w[__i] = static_cast<block_type>(0);
248 _M_is_equal(const __dynamic_bitset_base& __x) const
250 if (__x.size() == this->size())
252 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
253 if (this->_M_w[__i] != __x._M_w[__i])
262 _M_is_less(const __dynamic_bitset_base& __x) const
264 if (__x.size() == this->size())
266 for (size_t __i = this->_M_w.size(); __i > 0; --__i)
268 if (this->_M_w[__i-1] < __x._M_w[__i-1])
270 else if (this->_M_w[__i-1] > __x._M_w[__i-1])
280 _M_are_all_aux() const
282 for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
283 if (_M_w[__i] != ~static_cast<block_type>(0))
285 return ((this->_M_w.size() - 1) * _S_bits_per_block
286 + __builtin_popcountl(this->_M_hiword()));
292 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
293 if (this->_M_w[__i] != static_cast<block_type>(0))
299 _M_is_subset_of(const __dynamic_bitset_base& __b)
301 if (__b.size() == this->size())
303 for (size_t __i = 0; __i < _M_w.size(); ++__i)
304 if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
313 _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
315 if (this->is_subset_of(__b))
330 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
331 __result += __builtin_popcountl(this->_M_w[__i]);
337 { return this->_M_w.size(); }
340 _M_do_to_ulong() const;
343 _M_do_to_ullong() const;
345 // find first "on" bit
347 _M_do_find_first(size_t __not_found) const;
349 // find the next "on" bit that follows "prev"
351 _M_do_find_next(size_t __prev, size_t __not_found) const;
353 // do append of block
355 _M_do_append_block(block_type __block, size_type __pos)
357 size_t __offset = __pos % _S_bits_per_block;
359 this->_M_w.push_back(__block);
362 this->_M_hiword() |= (__block << __offset);
363 this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
368 // Definitions of non-inline functions from __dynamic_bitset_base.
369 template<typename _WordT, typename _Alloc>
371 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
373 if (__builtin_expect(__shift != 0, 1))
375 const size_t __wshift = __shift / _S_bits_per_block;
376 const size_t __offset = __shift % _S_bits_per_block;
379 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
380 this->_M_w[__n] = this->_M_w[__n - __wshift];
383 const size_t __sub_offset = _S_bits_per_block - __offset;
384 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
385 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
386 | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
387 this->_M_w[__wshift] = this->_M_w[0] << __offset;
390 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
391 //// static_cast<_WordT>(0));
395 template<typename _WordT, typename _Alloc>
397 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
399 if (__builtin_expect(__shift != 0, 1))
401 const size_t __wshift = __shift / _S_bits_per_block;
402 const size_t __offset = __shift % _S_bits_per_block;
403 const size_t __limit = this->_M_w.size() - __wshift - 1;
406 for (size_t __n = 0; __n <= __limit; ++__n)
407 this->_M_w[__n] = this->_M_w[__n + __wshift];
410 const size_t __sub_offset = (_S_bits_per_block
412 for (size_t __n = 0; __n < __limit; ++__n)
413 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
414 | (this->_M_w[__n + __wshift + 1] << __sub_offset));
415 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
418 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
419 //// static_cast<_WordT>(0));
423 template<typename _WordT, typename _Alloc>
425 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
427 size_t __n = sizeof(unsigned long) / sizeof(block_type);
428 for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
430 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
431 unsigned long __res = 0UL;
432 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
433 __res += this->_M_w[__i] << (__i * _S_bits_per_block);
437 template<typename _WordT, typename _Alloc>
439 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
441 size_t __n = sizeof(unsigned long long) / sizeof(block_type);
442 for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
444 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
445 unsigned long long __res = 0ULL;
446 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
447 __res += this->_M_w[__i] << (__i * _S_bits_per_block);
451 template<typename _WordT, typename _Alloc>
453 __dynamic_bitset_base<_WordT, _Alloc>
454 ::_M_do_find_first(size_t __not_found) const
456 for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
458 _WordT __thisword = this->_M_w[__i];
459 if (__thisword != static_cast<_WordT>(0))
460 return (__i * _S_bits_per_block
461 + __builtin_ctzl(__thisword));
463 // not found, so return an indication of failure.
467 template<typename _WordT, typename _Alloc>
469 __dynamic_bitset_base<_WordT, _Alloc>
470 ::_M_do_find_next(size_t __prev, size_t __not_found) const
472 // make bound inclusive
475 // check out of bounds
476 if (__prev >= this->_M_w.size() * _S_bits_per_block)
480 size_t __i = _S_whichword(__prev);
481 _WordT __thisword = this->_M_w[__i];
483 // mask off bits below bound
484 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
486 if (__thisword != static_cast<_WordT>(0))
487 return (__i * _S_bits_per_block
488 + __builtin_ctzl(__thisword));
490 // check subsequent words
491 for (++__i; __i < this->_M_w.size(); ++__i)
493 __thisword = this->_M_w[__i];
494 if (__thisword != static_cast<_WordT>(0))
495 return (__i * _S_bits_per_block
496 + __builtin_ctzl(__thisword));
498 // not found, so return an indication of failure.
500 } // end _M_do_find_next
503 * @brief The %dynamic_bitset class represents a sequence of bits.
505 * @ingroup containers
507 * (Note that %dynamic_bitset does @e not meet the formal
508 * requirements of a <a href="tables.html#65">container</a>.
509 * Mainly, it lacks iterators.)
511 * The template argument, @a Nb, may be any non-negative number,
512 * specifying the number of bits (e.g., "0", "12", "1024*1024").
514 * In the general unoptimized case, storage is allocated in
515 * word-sized blocks. Let B be the number of bits in a word, then
516 * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are
517 * unused. (They are the high-order bits in the highest word.) It
518 * is a class invariant that those unused bits are always zero.
520 * If you think of %dynamic_bitset as "a simple array of bits," be
521 * aware that your mental picture is reversed: a %dynamic_bitset
522 * behaves the same way as bits in integers do, with the bit at
523 * index 0 in the "least significant / right-hand" position, and
524 * the bit at index Nb-1 in the "most significant / left-hand"
525 * position. Thus, unlike other containers, a %dynamic_bitset's
526 * index "counts from right to left," to put it very loosely.
528 * This behavior is preserved when translating to and from strings.
529 * For example, the first line of the following program probably
530 * prints "b('a') is 0001100001" on a modern ASCII system.
533 * #include <dynamic_bitset>
534 * #include <iostream>
537 * using namespace std;
542 * dynamic_bitset b(a);
544 * cout << "b('a') is " << b << endl;
548 * string str = s.str();
549 * cout << "index 3 in the string is " << str[3] << " but\n"
550 * << "index 3 in the bitset is " << b[3] << endl;
555 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
556 * for a description of extensions.
558 * Most of the actual code isn't contained in %dynamic_bitset<>
559 * itself, but in the base class __dynamic_bitset_base. The base
560 * class works with whole words, not with individual bits. This
561 * allows us to specialize __dynamic_bitset_base for the important
562 * special case where the %dynamic_bitset is only a single word.
564 * Extra confusion can result due to the fact that the storage for
565 * __dynamic_bitset_base @e is a vector, and is indexed as such. This is
566 * carefully encapsulated.
568 template<typename _WordT = unsigned long long,
569 typename _Alloc = std::allocator<_WordT>>
571 : private __dynamic_bitset_base<_WordT, _Alloc>
573 static_assert(std::is_unsigned<_WordT>::value, "template argument "
574 "_WordT not an unsigned integral type");
578 typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
579 typedef _WordT block_type;
580 typedef _Alloc allocator_type;
581 typedef size_t size_type;
583 static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
584 // Use this: constexpr size_type std::numeric_limits<size_type>::max().
585 static const size_type npos = static_cast<size_type>(-1);
589 // Clear the unused bits in the uppermost word.
593 size_type __shift = this->_M_Nb % bits_per_block;
595 this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
599 * These versions of single-bit set, reset, flip, and test
600 * do no range checking.
602 dynamic_bitset<_WordT, _Alloc>&
603 _M_unchecked_set(size_type __pos)
605 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
609 dynamic_bitset<_WordT, _Alloc>&
610 _M_unchecked_set(size_type __pos, int __val)
613 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
615 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
619 dynamic_bitset<_WordT, _Alloc>&
620 _M_unchecked_reset(size_type __pos)
622 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
626 dynamic_bitset<_WordT, _Alloc>&
627 _M_unchecked_flip(size_type __pos)
629 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
634 _M_unchecked_test(size_type __pos) const
635 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
636 != static_cast<_WordT>(0)); }
642 * This encapsulates the concept of a single bit. An instance
643 * of this class is a proxy for an actual bit; this way the
644 * individual bit operations are done as faster word-size
645 * bitwise instructions.
647 * Most users will never need to use this class directly;
648 * conversions to and from bool are automatic and should be
649 * transparent. Overloaded operators help to preserve the
652 * (On a typical system, this "bit %reference" is 64 times the
653 * size of an actual bit. Ha.)
657 friend class dynamic_bitset;
666 reference(dynamic_bitset& __b, size_type __pos)
668 this->_M_wp = &__b._M_getword(__pos);
669 this->_M_bpos = _Base::_S_whichbit(__pos);
680 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
682 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
686 // For b[i] = b[__j];
688 operator=(const reference& __j)
690 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
691 *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
693 *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
700 { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
703 operator bool() const
704 { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
710 *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
715 friend class reference;
717 typedef bool const_reference;
719 // 23.3.5.1 constructors:
720 /// All bits set to zero.
722 dynamic_bitset(const allocator_type& __alloc = allocator_type())
723 : _Base(__alloc), _M_Nb(0)
726 /// Initial bits bitwise-copied from a single word (others set to zero).
728 dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
729 const allocator_type& __alloc = allocator_type())
730 : _Base(__nbits, __val, __alloc),
734 dynamic_bitset(initializer_list<block_type> __il,
735 const allocator_type& __alloc = allocator_type())
736 : _Base(__alloc), _M_Nb(0)
737 { this->append(__il); }
740 * @brief Use a subset of a string.
741 * @param __str A string of '0' and '1' characters.
742 * @param __pos Index of the first character in @p __str to use.
743 * @param __n The number of characters to copy.
744 * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
745 * @throw std::invalid_argument If a character appears in the string
746 * which is neither '0' nor '1'.
748 template<typename _CharT, typename _Traits, typename _Alloc1>
750 dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
751 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
753 typename basic_string<_CharT,_Traits,_Alloc1>::size_type
754 __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
755 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
756 const allocator_type& __alloc = allocator_type())
758 _M_Nb(0) // Watch for npos.
760 if (__pos > __str.size())
761 __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
765 this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
766 this->resize(this->_M_Nb);
767 this->_M_copy_from_string(__str, __pos, __n,
768 _CharT('0'), _CharT('1'));
772 * @brief Construct from a string.
773 * @param __str A string of '0' and '1' characters.
774 * @throw std::invalid_argument If a character appears in the string
775 * which is neither '0' nor '1'.
778 dynamic_bitset(const char* __str,
779 const allocator_type& __alloc = allocator_type())
784 while (__str[__len] != '\0')
787 this->_M_copy_from_ptr<char,std::char_traits<char>>
788 (__str, __len, 0, __len, '0', '1');
792 * @brief Copy constructor.
794 dynamic_bitset(const dynamic_bitset& __b)
795 : _Base(__b), _M_Nb(__b.size())
799 * @brief Move constructor.
801 dynamic_bitset(dynamic_bitset&& __b)
802 : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
806 * @brief Swap with another bitset.
809 swap(dynamic_bitset& __b)
812 std::swap(this->_M_Nb, __b._M_Nb);
819 operator=(const dynamic_bitset& __b)
823 this->_M_assign(__b);
824 this->_M_Nb = __b._M_Nb;
829 * @brief Move assignment.
832 operator=(dynamic_bitset&& __b)
839 * @brief Return the allocator for the bitset.
842 get_allocator() const
843 { return this->_M_get_allocator(); }
846 * @brief Resize the bitset.
849 resize(size_type __nbits, bool __value = false)
851 this->_M_resize(__nbits, __value);
852 this->_M_Nb = __nbits;
853 this->_M_do_sanitize();
857 * @brief Clear the bitset.
867 * @brief Push a bit onto the high end of the bitset.
870 push_back(bool __bit)
872 if (size_t __offset = this->size() % bits_per_block == 0)
873 this->_M_do_append_block(block_type(0), this->_M_Nb);
875 this->_M_unchecked_set(this->_M_Nb, __bit);
879 * @brief Append a block.
882 append(block_type __block)
884 this->_M_do_append_block(__block, this->_M_Nb);
885 this->_M_Nb += bits_per_block;
892 append(initializer_list<block_type> __il)
893 { this->append(__il.begin(), __il.end()); }
896 * @brief Append an iterator range of blocks.
898 template <typename _BlockInputIterator>
900 append(_BlockInputIterator __first, _BlockInputIterator __last)
902 for (; __first != __last; ++__first)
903 this->append(*__first);
906 // 23.3.5.2 dynamic_bitset operations:
909 * @brief Operations on dynamic_bitsets.
910 * @param __rhs A same-sized dynamic_bitset.
912 * These should be self-explanatory.
914 dynamic_bitset<_WordT, _Alloc>&
915 operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
917 this->_M_do_and(__rhs);
921 dynamic_bitset<_WordT, _Alloc>&
922 operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
924 this->_M_do_and(std::move(__rhs));
928 dynamic_bitset<_WordT, _Alloc>&
929 operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
931 this->_M_do_or(__rhs);
935 dynamic_bitset<_WordT, _Alloc>&
936 operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
938 this->_M_do_xor(__rhs);
942 dynamic_bitset<_WordT, _Alloc>&
943 operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
945 this->_M_do_dif(__rhs);
952 * @brief Operations on dynamic_bitsets.
953 * @param __pos The number of places to shift.
955 * These should be self-explanatory.
957 dynamic_bitset<_WordT, _Alloc>&
958 operator<<=(size_type __pos)
960 if (__builtin_expect(__pos < this->_M_Nb, 1))
962 this->_M_do_left_shift(__pos);
963 this->_M_do_sanitize();
970 dynamic_bitset<_WordT, _Alloc>&
971 operator>>=(size_type __pos)
973 if (__builtin_expect(__pos < this->_M_Nb, 1))
975 this->_M_do_right_shift(__pos);
976 this->_M_do_sanitize();
984 // Set, reset, and flip.
986 * @brief Sets every bit to true.
988 dynamic_bitset<_WordT, _Alloc>&
992 this->_M_do_sanitize();
997 * @brief Sets a given bit to a particular value.
998 * @param __pos The index of the bit.
999 * @param __val Either true or false, defaults to true.
1000 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1002 dynamic_bitset<_WordT, _Alloc>&
1003 set(size_type __pos, bool __val = true)
1006 __throw_out_of_range(__N("dynamic_bitset::set"));
1007 return this->_M_unchecked_set(__pos, __val);
1011 * @brief Sets every bit to false.
1013 dynamic_bitset<_WordT, _Alloc>&
1016 this->_M_do_reset();
1021 * @brief Sets a given bit to false.
1022 * @param __pos The index of the bit.
1023 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1025 * Same as writing @c set(__pos, false).
1027 dynamic_bitset<_WordT, _Alloc>&
1028 reset(size_type __pos)
1031 __throw_out_of_range(__N("dynamic_bitset::reset"));
1032 return this->_M_unchecked_reset(__pos);
1036 * @brief Toggles every bit to its opposite value.
1038 dynamic_bitset<_WordT, _Alloc>&
1042 this->_M_do_sanitize();
1047 * @brief Toggles a given bit to its opposite value.
1048 * @param __pos The index of the bit.
1049 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1051 dynamic_bitset<_WordT, _Alloc>&
1052 flip(size_type __pos)
1055 __throw_out_of_range(__N("dynamic_bitset::flip"));
1056 return this->_M_unchecked_flip(__pos);
1059 /// See the no-argument flip().
1060 dynamic_bitset<_WordT, _Alloc>
1062 { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
1066 * @brief Array-indexing support.
1067 * @param __pos Index into the %dynamic_bitset.
1068 * @return A bool for a 'const %dynamic_bitset'. For non-const
1069 * bitsets, an instance of the reference proxy class.
1070 * @note These operators do no range checking and throw no
1071 * exceptions, as required by DR 11 to the standard.
1074 operator[](size_type __pos)
1075 { return reference(*this,__pos); }
1078 operator[](size_type __pos) const
1079 { return _M_unchecked_test(__pos); }
1083 * @brief Returns a numerical interpretation of the %dynamic_bitset.
1084 * @return The integral equivalent of the bits.
1085 * @throw std::overflow_error If there are too many bits to be
1086 * represented in an @c unsigned @c long.
1090 { return this->_M_do_to_ulong(); }
1093 * @brief Returns a numerical interpretation of the %dynamic_bitset.
1094 * @return The integral equivalent of the bits.
1095 * @throw std::overflow_error If there are too many bits to be
1096 * represented in an @c unsigned @c long.
1100 { return this->_M_do_to_ullong(); }
1103 * @brief Returns a character interpretation of the %dynamic_bitset.
1104 * @return The string equivalent of the bits.
1106 * Note the ordering of the bits: decreasing character positions
1107 * correspond to increasing bit positions (see the main class notes for
1110 template<typename _CharT = char,
1111 typename _Traits = std::char_traits<_CharT>,
1112 typename _Alloc1 = std::allocator<_CharT>>
1113 std::basic_string<_CharT, _Traits, _Alloc1>
1114 to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
1116 std::basic_string<_CharT, _Traits, _Alloc1> __result;
1117 _M_copy_to_string(__result, __zero, __one);
1121 // Helper functions for string operations.
1122 template<typename _CharT, typename _Traits>
1124 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
1127 template<typename _CharT, typename _Traits, typename _Alloc1>
1129 _M_copy_from_string(const std::basic_string<_CharT,
1130 _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
1131 _CharT __zero = _CharT('0'),
1132 _CharT __one = _CharT('1'))
1133 { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
1134 __pos, __n, __zero, __one); }
1136 template<typename _CharT, typename _Traits, typename _Alloc1>
1138 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1139 _CharT __zero = _CharT('0'),
1140 _CharT __one = _CharT('1')) const;
1142 /// Returns the number of bits which are set.
1145 { return this->_M_do_count(); }
1147 /// Returns the total number of bits.
1150 { return this->_M_Nb; }
1152 /// Returns the total number of blocks.
1153 size_type num_blocks() const
1154 { return this->_M_size(); }
1156 /// Returns true if the dynamic_bitset is empty.
1159 { return (this->_M_Nb == 0); }
1161 /// Returns the maximum size of a dynamic_bitset object having the same
1163 /// The real answer is max() * bits_per_block but is likely to overflow.
1164 /*constexpr*/ size_type
1166 { return std::numeric_limits<block_type>::max(); }
1169 * @brief Tests the value of a bit.
1170 * @param __pos The index of a bit.
1171 * @return The value at @a __pos.
1172 * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1175 test(size_type __pos) const
1178 __throw_out_of_range(__N("dynamic_bitset::test"));
1179 return _M_unchecked_test(__pos);
1183 * @brief Tests whether all the bits are on.
1184 * @return True if all the bits are set.
1188 { return this->_M_are_all_aux() == _M_Nb; }
1191 * @brief Tests whether any of the bits are on.
1192 * @return True if at least one bit is set.
1196 { return this->_M_is_any(); }
1199 * @brief Tests whether any of the bits are on.
1200 * @return True if none of the bits are set.
1204 { return !this->_M_is_any(); }
1207 /// Self-explanatory.
1208 dynamic_bitset<_WordT, _Alloc>
1209 operator<<(size_type __pos) const
1210 { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1212 dynamic_bitset<_WordT, _Alloc>
1213 operator>>(size_type __pos) const
1214 { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1218 * @brief Finds the index of the first "on" bit.
1219 * @return The index of the first bit set, or size() if not found.
1224 { return this->_M_do_find_first(this->_M_Nb); }
1227 * @brief Finds the index of the next "on" bit after prev.
1228 * @return The index of the next bit set, or size() if not found.
1229 * @param __prev Where to start searching.
1233 find_next(size_t __prev) const
1234 { return this->_M_do_find_next(__prev, this->_M_Nb); }
1237 is_subset_of(const dynamic_bitset& __b) const
1238 { return this->_M_is_subset_of(__b); }
1241 is_proper_subset_of(const dynamic_bitset& __b) const
1242 { return this->_M_is_proper_subset_of(__b); }
1245 // Definitions of non-inline member functions.
1246 template<typename _WordT, typename _Alloc>
1247 template<typename _CharT, typename _Traits>
1249 dynamic_bitset<_WordT, _Alloc>::
1250 _M_copy_from_ptr(const _CharT* __str, size_t __len,
1251 size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1254 const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
1255 for (size_t __i = __nbits; __i > 0; --__i)
1257 const _CharT __c = __str[__pos + __nbits - __i];
1258 if (_Traits::eq(__c, __zero))
1260 else if (_Traits::eq(__c, __one))
1261 _M_unchecked_set(__i - 1);
1263 __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
1267 template<typename _WordT, typename _Alloc>
1268 template<typename _CharT, typename _Traits, typename _Alloc1>
1270 dynamic_bitset<_WordT, _Alloc>::
1271 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1272 _CharT __zero, _CharT __one) const
1274 __str.assign(_M_Nb, __zero);
1275 for (size_t __i = _M_Nb; __i > 0; --__i)
1276 if (_M_unchecked_test(__i - 1))
1277 _Traits::assign(__str[_M_Nb - __i], __one);
1282 /// These comparisons for equality/inequality are, well, @e bitwise.
1283 template<typename _WordT, typename _Alloc>
1285 operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1286 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1287 { return __lhs._M_is_equal(__rhs); }
1289 template<typename _WordT, typename _Alloc>
1291 operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1292 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1293 { return !__lhs._M_is_equal(__rhs); }
1295 template<typename _WordT, typename _Alloc>
1297 operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1298 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1299 { return __lhs._M_is_less(__rhs); }
1301 template<typename _WordT, typename _Alloc>
1303 operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1304 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1305 { return !(__lhs > __rhs); }
1307 template<typename _WordT, typename _Alloc>
1309 operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1310 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1311 { return __rhs < __lhs; }
1313 template<typename _WordT, typename _Alloc>
1315 operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1316 const dynamic_bitset<_WordT, _Alloc>& __rhs)
1317 { return !(__lhs < __rhs); }
1320 // 23.3.5.3 bitset operations:
1323 * @brief Global bitwise operations on bitsets.
1324 * @param __x A bitset.
1325 * @param __y A bitset of the same size as @a __x.
1326 * @return A new bitset.
1328 * These should be self-explanatory.
1330 template<typename _WordT, typename _Alloc>
1331 inline dynamic_bitset<_WordT, _Alloc>
1332 operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1333 const dynamic_bitset<_WordT, _Alloc>& __y)
1335 dynamic_bitset<_WordT, _Alloc> __result(__x);
1340 template<typename _WordT, typename _Alloc>
1341 inline dynamic_bitset<_WordT, _Alloc>
1342 operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1343 const dynamic_bitset<_WordT, _Alloc>& __y)
1345 dynamic_bitset<_WordT, _Alloc> __result(__x);
1350 template <typename _WordT, typename _Alloc>
1351 inline dynamic_bitset<_WordT, _Alloc>
1352 operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1353 const dynamic_bitset<_WordT, _Alloc>& __y)
1355 dynamic_bitset<_WordT, _Alloc> __result(__x);
1360 template <typename _WordT, typename _Alloc>
1361 inline dynamic_bitset<_WordT, _Alloc>
1362 operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1363 const dynamic_bitset<_WordT, _Alloc>& __y)
1365 dynamic_bitset<_WordT, _Alloc> __result(__x);
1373 * @brief Global I/O operators for bitsets.
1375 * Direct I/O between streams and bitsets is supported. Output is
1376 * straightforward. Input will skip whitespace and only accept '0'
1377 * and '1' characters. The %dynamic_bitset will grow as necessary
1378 * to hold the string of bits.
1380 template<typename _CharT, typename _Traits,
1381 typename _WordT, typename _Alloc>
1382 std::basic_istream<_CharT, _Traits>&
1383 operator>>(std::basic_istream<_CharT, _Traits>& __is,
1384 dynamic_bitset<_WordT, _Alloc>& __x)
1386 typedef typename _Traits::char_type char_type;
1387 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1388 typedef typename __istream_type::ios_base __ios_base;
1390 std::basic_string<_CharT, _Traits> __tmp;
1391 __tmp.reserve(__x.size());
1393 const char_type __zero = __is.widen('0');
1394 const char_type __one = __is.widen('1');
1396 typename __ios_base::iostate __state = __ios_base::goodbit;
1397 typename __istream_type::sentry __sentry(__is);
1404 static typename _Traits::int_type __eof = _Traits::eof();
1406 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1407 if (_Traits::eq_int_type(__c1, __eof))
1409 __state |= __ios_base::eofbit;
1414 const char_type __c2 = _Traits::to_char_type(__c1);
1415 if (_Traits::eq(__c2, __zero))
1416 __tmp.push_back(__zero);
1417 else if (_Traits::eq(__c2, __one))
1418 __tmp.push_back(__one);
1420 eq_int_type(__is.rdbuf()->sputbackc(__c2),
1423 __state |= __ios_base::failbit;
1431 __catch(__cxxabiv1::__forced_unwind&)
1433 __is._M_setstate(__ios_base::badbit);
1434 __throw_exception_again;
1437 { __is._M_setstate(__ios_base::badbit); }
1440 __x.resize(__tmp.size());
1442 if (__tmp.empty() && __x.size())
1443 __state |= __ios_base::failbit;
1445 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
1448 __is.setstate(__state);
1452 template <typename _CharT, typename _Traits,
1453 typename _WordT, typename _Alloc>
1454 std::basic_ostream<_CharT, _Traits>&
1455 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1456 const dynamic_bitset<_WordT, _Alloc>& __x)
1458 std::basic_string<_CharT, _Traits> __tmp;
1460 const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1461 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1462 return __os << __tmp;
1466 _GLIBCXX_END_NAMESPACE_VERSION
1470 #undef _GLIBCXX_BITSET_BITS_PER_WORD
1472 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */