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