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