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