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