libstdc++
dynamic_bitset
Go to the documentation of this file.
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  * @param __zero The character to use for unset bits.
597  * @param __one The character to use for set bits.
598  * @param __alloc An allocator.
599  * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
600  * @throw std::invalid_argument If a character appears in the string
601  * which is neither '0' nor '1'.
602  */
603  template<typename _CharT, typename _Traits, typename _Alloc1>
604  explicit
605  dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
606  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
607  __pos = 0,
608  typename basic_string<_CharT,_Traits,_Alloc1>::size_type
609  __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
610  _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
611  const allocator_type& __alloc = allocator_type())
612  : _Base(__alloc),
613  _M_Nb(0) // Watch for npos.
614  {
615  if (__pos > __str.size())
616  __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
617  "not valid"));
618 
619  // Watch for npos.
620  this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
621  this->resize(this->_M_Nb);
622  this->_M_copy_from_string(__str, __pos, __n,
623  _CharT('0'), _CharT('1'));
624  }
625 
626  /**
627  * @brief Construct from a string.
628  * @param __str A string of '0' and '1' characters.
629  * @param __alloc An allocator.
630  * @throw std::invalid_argument If a character appears in the string
631  * which is neither '0' nor '1'.
632  */
633  explicit
634  dynamic_bitset(const char* __str,
635  const allocator_type& __alloc = allocator_type())
636  : _Base(__alloc)
637  {
638  size_t __len = 0;
639  if (__str)
640  while (__str[__len] != '\0')
641  ++__len;
642  this->resize(__len);
643  this->_M_copy_from_ptr<char,std::char_traits<char>>
644  (__str, __len, 0, __len, '0', '1');
645  }
646 
647  /**
648  * @brief Copy constructor.
649  */
650  dynamic_bitset(const dynamic_bitset& __b)
651  : _Base(__b), _M_Nb(__b.size())
652  { }
653 
654  /**
655  * @brief Move constructor.
656  */
657  dynamic_bitset(dynamic_bitset&& __b)
658  : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
659  { }
660 
661  /**
662  * @brief Swap with another bitset.
663  */
664  void
665  swap(dynamic_bitset& __b)
666  {
667  this->_M_swap(__b);
668  std::swap(this->_M_Nb, __b._M_Nb);
669  }
670 
671  /**
672  * @brief Assignment.
673  */
674  dynamic_bitset&
675  operator=(const dynamic_bitset& __b)
676  {
677  if (&__b != this)
678  {
679  this->_M_assign(__b);
680  this->_M_Nb = __b._M_Nb;
681  }
682  }
683 
684  /**
685  * @brief Move assignment.
686  */
687  dynamic_bitset&
688  operator=(dynamic_bitset&& __b)
689  {
690  this->swap(__b);
691  return *this;
692  }
693 
694  /**
695  * @brief Return the allocator for the bitset.
696  */
697  allocator_type
698  get_allocator() const
699  { return this->_M_get_allocator(); }
700 
701  /**
702  * @brief Resize the bitset.
703  */
704  void
705  resize(size_type __nbits, bool __value = false)
706  {
707  if (__value)
708  this->_M_do_fill();
709  this->_M_resize(__nbits, __value);
710  this->_M_Nb = __nbits;
711  this->_M_do_sanitize();
712  }
713 
714  /**
715  * @brief Clear the bitset.
716  */
717  void
718  clear()
719  {
720  this->_M_clear();
721  this->_M_Nb = 0;
722  }
723 
724  /**
725  * @brief Push a bit onto the high end of the bitset.
726  */
727  void
728  push_back(bool __bit)
729  {
730  if (size_t __offset = this->size() % bits_per_block == 0)
731  this->_M_do_append_block(block_type(0), this->_M_Nb);
732  ++this->_M_Nb;
733  this->_M_unchecked_set(this->_M_Nb, __bit);
734  }
735 
736  /**
737  * @brief Append a block.
738  */
739  void
740  append(block_type __block)
741  {
742  this->_M_do_append_block(__block, this->_M_Nb);
743  this->_M_Nb += bits_per_block;
744  }
745 
746  /**
747  * @brief
748  */
749  void
750  append(initializer_list<block_type> __il)
751  { this->append(__il.begin(), __il.end()); }
752 
753  /**
754  * @brief Append an iterator range of blocks.
755  */
756  template <typename _BlockInputIterator>
757  void
758  append(_BlockInputIterator __first, _BlockInputIterator __last)
759  {
760  for (; __first != __last; ++__first)
761  this->append(*__first);
762  }
763 
764  // 23.3.5.2 dynamic_bitset operations:
765  //@{
766  /**
767  * @brief Operations on dynamic_bitsets.
768  * @param __rhs A same-sized dynamic_bitset.
769  *
770  * These should be self-explanatory.
771  */
772  dynamic_bitset<_WordT, _Alloc>&
773  operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
774  {
775  this->_M_do_and(__rhs);
776  return *this;
777  }
778 
779  dynamic_bitset<_WordT, _Alloc>&
780  operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
781  {
782  this->_M_do_and(std::move(__rhs));
783  return *this;
784  }
785 
786  dynamic_bitset<_WordT, _Alloc>&
787  operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
788  {
789  this->_M_do_or(__rhs);
790  return *this;
791  }
792 
793  dynamic_bitset<_WordT, _Alloc>&
794  operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
795  {
796  this->_M_do_xor(__rhs);
797  return *this;
798  }
799 
800  dynamic_bitset<_WordT, _Alloc>&
801  operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
802  {
803  this->_M_do_dif(__rhs);
804  return *this;
805  }
806  //@}
807 
808  //@{
809  /**
810  * @brief Operations on dynamic_bitsets.
811  * @param __pos The number of places to shift.
812  *
813  * These should be self-explanatory.
814  */
815  dynamic_bitset<_WordT, _Alloc>&
816  operator<<=(size_type __pos)
817  {
818  if (__builtin_expect(__pos < this->_M_Nb, 1))
819  {
820  this->_M_do_left_shift(__pos);
821  this->_M_do_sanitize();
822  }
823  else
824  this->_M_do_reset();
825  return *this;
826  }
827 
828  dynamic_bitset<_WordT, _Alloc>&
829  operator>>=(size_type __pos)
830  {
831  if (__builtin_expect(__pos < this->_M_Nb, 1))
832  {
833  this->_M_do_right_shift(__pos);
834  this->_M_do_sanitize();
835  }
836  else
837  this->_M_do_reset();
838  return *this;
839  }
840  //@}
841 
842  // Set, reset, and flip.
843  /**
844  * @brief Sets every bit to true.
845  */
846  dynamic_bitset<_WordT, _Alloc>&
847  set()
848  {
849  this->_M_do_set();
850  this->_M_do_sanitize();
851  return *this;
852  }
853 
854  /**
855  * @brief Sets a given bit to a particular value.
856  * @param __pos The index of the bit.
857  * @param __val Either true or false, defaults to true.
858  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
859  */
860  dynamic_bitset<_WordT, _Alloc>&
861  set(size_type __pos, bool __val = true)
862  {
863  if (__pos >= _M_Nb)
864  __throw_out_of_range(__N("dynamic_bitset::set"));
865  return this->_M_unchecked_set(__pos, __val);
866  }
867 
868  /**
869  * @brief Sets every bit to false.
870  */
871  dynamic_bitset<_WordT, _Alloc>&
872  reset()
873  {
874  this->_M_do_reset();
875  return *this;
876  }
877 
878  /**
879  * @brief Sets a given bit to false.
880  * @param __pos The index of the bit.
881  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
882  *
883  * Same as writing @c set(__pos, false).
884  */
885  dynamic_bitset<_WordT, _Alloc>&
886  reset(size_type __pos)
887  {
888  if (__pos >= _M_Nb)
889  __throw_out_of_range(__N("dynamic_bitset::reset"));
890  return this->_M_unchecked_reset(__pos);
891  }
892 
893  /**
894  * @brief Toggles every bit to its opposite value.
895  */
896  dynamic_bitset<_WordT, _Alloc>&
897  flip()
898  {
899  this->_M_do_flip();
900  this->_M_do_sanitize();
901  return *this;
902  }
903 
904  /**
905  * @brief Toggles a given bit to its opposite value.
906  * @param __pos The index of the bit.
907  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
908  */
909  dynamic_bitset<_WordT, _Alloc>&
910  flip(size_type __pos)
911  {
912  if (__pos >= _M_Nb)
913  __throw_out_of_range(__N("dynamic_bitset::flip"));
914  return this->_M_unchecked_flip(__pos);
915  }
916 
917  /// See the no-argument flip().
918  dynamic_bitset<_WordT, _Alloc>
919  operator~() const
920  { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
921 
922  //@{
923  /**
924  * @brief Array-indexing support.
925  * @param __pos Index into the %dynamic_bitset.
926  * @return A bool for a 'const %dynamic_bitset'. For non-const
927  * bitsets, an instance of the reference proxy class.
928  * @note These operators do no range checking and throw no
929  * exceptions, as required by DR 11 to the standard.
930  */
931  reference
932  operator[](size_type __pos)
933  { return reference(*this,__pos); }
934 
935  const_reference
936  operator[](size_type __pos) const
937  { return _M_unchecked_test(__pos); }
938  //@}
939 
940  /**
941  * @brief Returns a numerical interpretation of the %dynamic_bitset.
942  * @return The integral equivalent of the bits.
943  * @throw std::overflow_error If there are too many bits to be
944  * represented in an @c unsigned @c long.
945  */
946  unsigned long
947  to_ulong() const
948  { return this->_M_do_to_ulong(); }
949 
950  /**
951  * @brief Returns a numerical interpretation of the %dynamic_bitset.
952  * @return The integral equivalent of the bits.
953  * @throw std::overflow_error If there are too many bits to be
954  * represented in an @c unsigned @c long.
955  */
956  unsigned long long
957  to_ullong() const
958  { return this->_M_do_to_ullong(); }
959 
960  /**
961  * @brief Returns a character interpretation of the %dynamic_bitset.
962  * @return The string equivalent of the bits.
963  *
964  * Note the ordering of the bits: decreasing character positions
965  * correspond to increasing bit positions (see the main class notes for
966  * an example).
967  */
968  template<typename _CharT = char,
969  typename _Traits = std::char_traits<_CharT>,
970  typename _Alloc1 = std::allocator<_CharT>>
971  std::basic_string<_CharT, _Traits, _Alloc1>
972  to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
973  {
974  std::basic_string<_CharT, _Traits, _Alloc1> __result;
975  _M_copy_to_string(__result, __zero, __one);
976  return __result;
977  }
978 
979  // Helper functions for string operations.
980  template<typename _CharT, typename _Traits>
981  void
982  _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
983  _CharT, _CharT);
984 
985  template<typename _CharT, typename _Traits, typename _Alloc1>
986  void
987  _M_copy_from_string(const std::basic_string<_CharT,
988  _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
989  _CharT __zero = _CharT('0'),
990  _CharT __one = _CharT('1'))
991  { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
992  __pos, __n, __zero, __one); }
993 
994  template<typename _CharT, typename _Traits, typename _Alloc1>
995  void
996  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
997  _CharT __zero = _CharT('0'),
998  _CharT __one = _CharT('1')) const;
999 
1000  /// Returns the number of bits which are set.
1001  size_type
1002  count() const noexcept
1003  { return this->_M_do_count(); }
1004 
1005  /// Returns the total number of bits.
1006  size_type
1007  size() const noexcept
1008  { return this->_M_Nb; }
1009 
1010  /// Returns the total number of blocks.
1011  size_type
1012  num_blocks() const noexcept
1013  { return this->_M_size(); }
1014 
1015  /// Returns true if the dynamic_bitset is empty.
1016  bool
1017  empty() const noexcept
1018  { return (this->_M_Nb == 0); }
1019 
1020  /// Returns the maximum size of a dynamic_bitset object having the same
1021  /// type as *this.
1022  /// The real answer is max() * bits_per_block but is likely to overflow.
1023  constexpr size_type
1024  max_size() noexcept
1025  { return std::numeric_limits<block_type>::max(); }
1026 
1027  /**
1028  * @brief Tests the value of a bit.
1029  * @param __pos The index of a bit.
1030  * @return The value at @a __pos.
1031  * @throw std::out_of_range If @a __pos is bigger the size of the %set.
1032  */
1033  bool
1034  test(size_type __pos) const
1035  {
1036  if (__pos >= _M_Nb)
1037  __throw_out_of_range(__N("dynamic_bitset::test"));
1038  return _M_unchecked_test(__pos);
1039  }
1040 
1041  /**
1042  * @brief Tests whether all the bits are on.
1043  * @return True if all the bits are set.
1044  */
1045  bool
1046  all() const
1047  { return this->_M_are_all_aux() == _M_Nb; }
1048 
1049  /**
1050  * @brief Tests whether any of the bits are on.
1051  * @return True if at least one bit is set.
1052  */
1053  bool
1054  any() const
1055  { return this->_M_is_any(); }
1056 
1057  /**
1058  * @brief Tests whether any of the bits are on.
1059  * @return True if none of the bits are set.
1060  */
1061  bool
1062  none() const
1063  { return !this->_M_is_any(); }
1064 
1065  //@{
1066  /// Self-explanatory.
1067  dynamic_bitset<_WordT, _Alloc>
1068  operator<<(size_type __pos) const
1069  { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
1070 
1071  dynamic_bitset<_WordT, _Alloc>
1072  operator>>(size_type __pos) const
1073  { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
1074  //@}
1075 
1076  /**
1077  * @brief Finds the index of the first "on" bit.
1078  * @return The index of the first bit set, or size() if not found.
1079  * @sa find_next
1080  */
1081  size_type
1082  find_first() const
1083  { return this->_M_do_find_first(this->_M_Nb); }
1084 
1085  /**
1086  * @brief Finds the index of the next "on" bit after prev.
1087  * @return The index of the next bit set, or size() if not found.
1088  * @param __prev Where to start searching.
1089  * @sa find_first
1090  */
1091  size_type
1092  find_next(size_t __prev) const
1093  { return this->_M_do_find_next(__prev, this->_M_Nb); }
1094 
1095  bool
1096  is_subset_of(const dynamic_bitset& __b) const
1097  { return this->_M_is_subset_of(__b); }
1098 
1099  bool
1100  is_proper_subset_of(const dynamic_bitset& __b) const
1101  { return this->_M_is_proper_subset_of(__b); }
1102 
1103  friend bool
1104  operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1105  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1106  { return __lhs._M_is_equal(__rhs); }
1107 
1108  friend bool
1109  operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1110  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1111  { return __lhs._M_is_less(__rhs); }
1112  };
1113 
1114  template<typename _WordT, typename _Alloc>
1115  template<typename _CharT, typename _Traits, typename _Alloc1>
1116  inline void
1117  dynamic_bitset<_WordT, _Alloc>::
1118  _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
1119  _CharT __zero, _CharT __one) const
1120  {
1121  __str.assign(_M_Nb, __zero);
1122  for (size_t __i = _M_Nb; __i > 0; --__i)
1123  if (_M_unchecked_test(__i - 1))
1124  _Traits::assign(__str[_M_Nb - __i], __one);
1125  }
1126 
1127 
1128  //@{
1129  /// These comparisons for equality/inequality are, well, @e bitwise.
1130 
1131  template<typename _WordT, typename _Alloc>
1132  inline bool
1133  operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1134  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1135  { return !(__lhs == __rhs); }
1136 
1137  template<typename _WordT, typename _Alloc>
1138  inline bool
1139  operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1140  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1141  { return !(__lhs > __rhs); }
1142 
1143  template<typename _WordT, typename _Alloc>
1144  inline bool
1145  operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1146  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1147  { return __rhs < __lhs; }
1148 
1149  template<typename _WordT, typename _Alloc>
1150  inline bool
1151  operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
1152  const dynamic_bitset<_WordT, _Alloc>& __rhs)
1153  { return !(__lhs < __rhs); }
1154  //@}
1155 
1156  // 23.3.5.3 bitset operations:
1157  //@{
1158  /**
1159  * @brief Global bitwise operations on bitsets.
1160  * @param __x A bitset.
1161  * @param __y A bitset of the same size as @a __x.
1162  * @return A new bitset.
1163  *
1164  * These should be self-explanatory.
1165  */
1166  template<typename _WordT, typename _Alloc>
1167  inline dynamic_bitset<_WordT, _Alloc>
1168  operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
1169  const dynamic_bitset<_WordT, _Alloc>& __y)
1170  {
1171  dynamic_bitset<_WordT, _Alloc> __result(__x);
1172  __result &= __y;
1173  return __result;
1174  }
1175 
1176  template<typename _WordT, typename _Alloc>
1177  inline dynamic_bitset<_WordT, _Alloc>
1178  operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
1179  const dynamic_bitset<_WordT, _Alloc>& __y)
1180  {
1181  dynamic_bitset<_WordT, _Alloc> __result(__x);
1182  __result |= __y;
1183  return __result;
1184  }
1185 
1186  template <typename _WordT, typename _Alloc>
1187  inline dynamic_bitset<_WordT, _Alloc>
1188  operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
1189  const dynamic_bitset<_WordT, _Alloc>& __y)
1190  {
1191  dynamic_bitset<_WordT, _Alloc> __result(__x);
1192  __result ^= __y;
1193  return __result;
1194  }
1195 
1196  template <typename _WordT, typename _Alloc>
1197  inline dynamic_bitset<_WordT, _Alloc>
1198  operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
1199  const dynamic_bitset<_WordT, _Alloc>& __y)
1200  {
1201  dynamic_bitset<_WordT, _Alloc> __result(__x);
1202  __result -= __y;
1203  return __result;
1204  }
1205  //@}
1206 
1207  /// Stream output operator for dynamic_bitset.
1208  template <typename _CharT, typename _Traits,
1209  typename _WordT, typename _Alloc>
1210  inline std::basic_ostream<_CharT, _Traits>&
1211  operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1212  const dynamic_bitset<_WordT, _Alloc>& __x)
1213  {
1214  std::basic_string<_CharT, _Traits> __tmp;
1215 
1216  const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
1217  __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1218  return __os << __tmp;
1219  }
1220  /**
1221  * @}
1222  */
1223 
1224 _GLIBCXX_END_NAMESPACE_VERSION
1225 } // tr2
1226 } // std
1227 
1228 #include <tr2/dynamic_bitset.tcc>
1229 
1230 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */