--- /dev/null
+// TR2 <dynamic_bitset> -*- C++ -*-
+
+// Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file tr2/dynamic_bitset
+ * This is a TR2 C++ Library header.
+ */
+
+#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET
+#define _GLIBCXX_TR2_DYNAMIC_BITSET 1
+
+#pragma GCC system_header
+
+#include <limits>
+#include <vector>
+#include <cstddef> // For size_t
+#include <string>
+#include <memory> // For std::allocator
+#include <bits/functexcept.h> // For invalid_argument, out_of_range,
+ // overflow_error
+#include <iosfwd>
+#include <cxxabi_forced.h>
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+namespace tr2
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ /**
+ * Dynamic Bitset.
+ *
+ * See N2050,
+ * Proposal to Add a Dynamically Sizeable Bitset to the Standard Library.
+ */
+namespace __detail
+{
+
+template<typename T>
+class _Bool2UChar
+{
+ typedef T type;
+};
+
+template<>
+class _Bool2UChar<bool>
+{
+public:
+ typedef unsigned char type;
+};
+
+}
+
+ /**
+ * Base class, general case.
+ *
+ * See documentation for dynamic_bitset.
+ */
+ template<typename _WordT = unsigned long long,
+ typename _Alloc = std::allocator<_WordT>>
+ struct __dynamic_bitset_base
+ {
+ static_assert(std::is_unsigned<_WordT>::value, "template argument "
+ "_WordT not an unsigned integral type");
+
+ typedef _WordT block_type;
+ typedef _Alloc allocator_type;
+ typedef size_t size_type;
+
+ static const size_type _S_bits_per_block = __CHAR_BIT__ * sizeof(block_type);
+ static const size_type npos = static_cast<size_type>(-1);
+
+ /// 0 is the least significant word.
+ std::vector<block_type, allocator_type> _M_w;
+
+ explicit
+ __dynamic_bitset_base(const allocator_type& __alloc = allocator_type())
+ : _M_w(__alloc)
+ { }
+
+ explicit
+ __dynamic_bitset_base(__dynamic_bitset_base&& __b)
+ { this->_M_w.swap(__b._M_w); }
+
+ explicit
+ __dynamic_bitset_base(size_type __nbits, unsigned long long __val = 0ULL,
+ const allocator_type& __alloc = allocator_type())
+ : _M_w(__nbits / _S_bits_per_block
+ + (__nbits % _S_bits_per_block > 0),
+ __val, __alloc)
+ {
+ unsigned long long __mask = ~static_cast<block_type>(0);
+ size_t __n = std::min(this->_M_w.size(),
+ sizeof(unsigned long long) / sizeof(block_type));
+ for (size_t __i = 0; __i < __n; ++__i)
+ {
+ this->_M_w[__i] = (__val & __mask) >> (__i * _S_bits_per_block);
+ __mask <<= _S_bits_per_block;
+ }
+ }
+
+ void
+ _M_assign(const __dynamic_bitset_base& __b)
+ { this->_M_w = __b._M_w; }
+
+ void
+ _M_swap(__dynamic_bitset_base& __b)
+ { this->_M_w.swap(__b._M_w); }
+
+ void
+ _M_clear()
+ { this->_M_w.clear(); }
+
+ void
+ _M_resize(size_t __nbits, bool __value)
+ {
+ size_t __sz = __nbits / _S_bits_per_block;
+ if (__nbits % _S_bits_per_block > 0)
+ ++__sz;
+ if (__sz != this->_M_w.size())
+ this->_M_w.resize(__sz);
+ }
+
+ allocator_type
+ _M_get_allocator() const
+ { return this->_M_w.get_allocator(); }
+
+ static size_type
+ _S_whichword(size_type __pos)
+ { return __pos / _S_bits_per_block; }
+
+ static size_type
+ _S_whichbyte(size_type __pos)
+ { return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
+
+ static size_type
+ _S_whichbit(size_type __pos)
+ { return __pos % _S_bits_per_block; }
+
+ static block_type
+ _S_maskbit(size_type __pos)
+ { return (static_cast<block_type>(1)) << _S_whichbit(__pos); }
+
+ block_type&
+ _M_getword(size_type __pos)
+ { return this->_M_w[_S_whichword(__pos)]; }
+
+ block_type
+ _M_getword(size_type __pos) const
+ { return this->_M_w[_S_whichword(__pos)]; }
+
+ block_type&
+ _M_hiword()
+ { return this->_M_w[_M_w.size() - 1]; }
+
+ block_type
+ _M_hiword() const
+ { return this->_M_w[_M_w.size() - 1]; }
+
+ void
+ _M_do_and(const __dynamic_bitset_base& __x)
+ {
+ if (__x._M_w.size() == this->_M_w.size())
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] &= __x._M_w[__i];
+ else
+ return;
+ }
+
+ void
+ _M_do_or(const __dynamic_bitset_base& __x)
+ {
+ if (__x._M_w.size() == this->_M_w.size())
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] |= __x._M_w[__i];
+ else
+ return;
+ }
+
+ void
+ _M_do_xor(const __dynamic_bitset_base& __x)
+ {
+ if (__x._M_w.size() == this->_M_w.size())
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] ^= __x._M_w[__i];
+ else
+ return;
+ }
+
+ void
+ _M_do_dif(const __dynamic_bitset_base& __x)
+ {
+ if (__x._M_w.size() == this->_M_w.size())
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] &= ~__x._M_w[__i];
+ else
+ return;
+ }
+
+ void
+ _M_do_left_shift(size_t __shift);
+
+ void
+ _M_do_right_shift(size_t __shift);
+
+ void
+ _M_do_flip()
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] = ~this->_M_w[__i];
+ }
+
+ void
+ _M_do_set()
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] = ~static_cast<block_type>(0);
+ }
+
+ void
+ _M_do_reset()
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ this->_M_w[__i] = static_cast<block_type>(0);
+ }
+
+ bool
+ _M_is_equal(const __dynamic_bitset_base& __x) const
+ {
+ if (__x.size() == this->size())
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ if (this->_M_w[__i] != __x._M_w[__i])
+ return false;
+ return true;
+ }
+ else
+ return false;
+ }
+
+ bool
+ _M_is_less(const __dynamic_bitset_base& __x) const
+ {
+ if (__x.size() == this->size())
+ {
+ for (size_t __i = this->_M_w.size(); __i > 0; --__i)
+ {
+ if (this->_M_w[__i-1] < __x._M_w[__i-1])
+ return true;
+ else if (this->_M_w[__i-1] > __x._M_w[__i-1])
+ return false;
+ }
+ return false;
+ }
+ else
+ return false;
+ }
+
+ size_t
+ _M_are_all_aux() const
+ {
+ for (size_t __i = 0; __i < this->_M_w.size() - 1; ++__i)
+ if (_M_w[__i] != ~static_cast<block_type>(0))
+ return 0;
+ return ((this->_M_w.size() - 1) * _S_bits_per_block
+ + __builtin_popcountl(this->_M_hiword()));
+ }
+
+ bool
+ _M_is_any() const
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ if (this->_M_w[__i] != static_cast<block_type>(0))
+ return true;
+ return false;
+ }
+
+ bool
+ _M_is_subset_of(const __dynamic_bitset_base& __b)
+ {
+ if (__b.size() == this->size())
+ {
+ for (size_t __i = 0; __i < _M_w.size(); ++__i)
+ if (this->_M_w[__i] != (this->_M_w[__i] | __b._M_w[__i]))
+ return false;
+ return true;
+ }
+ else
+ return false;
+ }
+
+ bool
+ _M_is_proper_subset_of(const __dynamic_bitset_base& __b) const
+ {
+ if (this->is_subset_of(__b))
+ {
+ if (*this == __b)
+ return false;
+ else
+ return true;
+ }
+ else
+ return false;
+ }
+
+ size_t
+ _M_do_count() const
+ {
+ size_t __result = 0;
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ __result += __builtin_popcountl(this->_M_w[__i]);
+ return __result;
+ }
+
+ size_type
+ _M_size() const
+ { return this->_M_w.size(); }
+
+ unsigned long
+ _M_do_to_ulong() const;
+
+ unsigned long long
+ _M_do_to_ullong() const;
+
+ // find first "on" bit
+ size_type
+ _M_do_find_first(size_t __not_found) const;
+
+ // find the next "on" bit that follows "prev"
+ size_type
+ _M_do_find_next(size_t __prev, size_t __not_found) const;
+
+ // do append of block
+ void
+ _M_do_append_block(block_type __block, size_type __pos)
+ {
+ size_t __offset = __pos % _S_bits_per_block;
+ if (__offset == 0)
+ this->_M_w.push_back(__block);
+ else
+ {
+ this->_M_hiword() |= (__block << __offset);
+ this->_M_w.push_back(__block >> (_S_bits_per_block - __offset));
+ }
+ }
+ };
+
+ // Definitions of non-inline functions from __dynamic_bitset_base.
+ template<typename _WordT, typename _Alloc>
+ void
+ __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
+ {
+ if (__builtin_expect(__shift != 0, 1))
+ {
+ const size_t __wshift = __shift / _S_bits_per_block;
+ const size_t __offset = __shift % _S_bits_per_block;
+
+ if (__offset == 0)
+ for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
+ this->_M_w[__n] = this->_M_w[__n - __wshift];
+ else
+ {
+ const size_t __sub_offset = _S_bits_per_block - __offset;
+ for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
+ this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
+ | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
+ this->_M_w[__wshift] = this->_M_w[0] << __offset;
+ }
+
+ //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
+ //// static_cast<_WordT>(0));
+ }
+ }
+
+ template<typename _WordT, typename _Alloc>
+ void
+ __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
+ {
+ if (__builtin_expect(__shift != 0, 1))
+ {
+ const size_t __wshift = __shift / _S_bits_per_block;
+ const size_t __offset = __shift % _S_bits_per_block;
+ const size_t __limit = this->_M_w.size() - __wshift - 1;
+
+ if (__offset == 0)
+ for (size_t __n = 0; __n <= __limit; ++__n)
+ this->_M_w[__n] = this->_M_w[__n + __wshift];
+ else
+ {
+ const size_t __sub_offset = (_S_bits_per_block
+ - __offset);
+ for (size_t __n = 0; __n < __limit; ++__n)
+ this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
+ | (this->_M_w[__n + __wshift + 1] << __sub_offset));
+ this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
+ }
+
+ ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
+ //// static_cast<_WordT>(0));
+ }
+ }
+
+ template<typename _WordT, typename _Alloc>
+ unsigned long
+ __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
+ {
+ size_t __n = sizeof(unsigned long) / sizeof(block_type);
+ for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
+ if (this->_M_w[__i])
+ __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
+ unsigned long __res = 0UL;
+ for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
+ __res += this->_M_w[__i] << (__i * _S_bits_per_block);
+ return __res;
+ }
+
+ template<typename _WordT, typename _Alloc>
+ unsigned long long
+ __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
+ {
+ size_t __n = sizeof(unsigned long long) / sizeof(block_type);
+ for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
+ if (this->_M_w[__i])
+ __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
+ unsigned long long __res = 0ULL;
+ for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
+ __res += this->_M_w[__i] << (__i * _S_bits_per_block);
+ return __res;
+ }
+
+ template<typename _WordT, typename _Alloc>
+ size_t
+ __dynamic_bitset_base<_WordT, _Alloc>
+ ::_M_do_find_first(size_t __not_found) const
+ {
+ for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
+ {
+ _WordT __thisword = this->_M_w[__i];
+ if (__thisword != static_cast<_WordT>(0))
+ return (__i * _S_bits_per_block
+ + __builtin_ctzl(__thisword));
+ }
+ // not found, so return an indication of failure.
+ return __not_found;
+ }
+
+ template<typename _WordT, typename _Alloc>
+ size_t
+ __dynamic_bitset_base<_WordT, _Alloc>
+ ::_M_do_find_next(size_t __prev, size_t __not_found) const
+ {
+ // make bound inclusive
+ ++__prev;
+
+ // check out of bounds
+ if (__prev >= this->_M_w.size() * _S_bits_per_block)
+ return __not_found;
+
+ // search first word
+ size_t __i = _S_whichword(__prev);
+ _WordT __thisword = this->_M_w[__i];
+
+ // mask off bits below bound
+ __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
+
+ if (__thisword != static_cast<_WordT>(0))
+ return (__i * _S_bits_per_block
+ + __builtin_ctzl(__thisword));
+
+ // check subsequent words
+ for (++__i; __i < this->_M_w.size(); ++__i)
+ {
+ __thisword = this->_M_w[__i];
+ if (__thisword != static_cast<_WordT>(0))
+ return (__i * _S_bits_per_block
+ + __builtin_ctzl(__thisword));
+ }
+ // not found, so return an indication of failure.
+ return __not_found;
+ } // end _M_do_find_next
+
+ /**
+ * @brief The %dynamic_bitset class represents a sequence of bits.
+ *
+ * @ingroup containers
+ *
+ * (Note that %dynamic_bitset does @e not meet the formal
+ * requirements of a <a href="tables.html#65">container</a>.
+ * Mainly, it lacks iterators.)
+ *
+ * The template argument, @a Nb, may be any non-negative number,
+ * specifying the number of bits (e.g., "0", "12", "1024*1024").
+ *
+ * In the general unoptimized case, storage is allocated in
+ * word-sized blocks. Let B be the number of bits in a word, then
+ * (Nb+(B-1))/B words will be used for storage. B - Nb%B bits are
+ * unused. (They are the high-order bits in the highest word.) It
+ * is a class invariant that those unused bits are always zero.
+ *
+ * If you think of %dynamic_bitset as "a simple array of bits," be
+ * aware that your mental picture is reversed: a %dynamic_bitset
+ * behaves the same way as bits in integers do, with the bit at
+ * index 0 in the "least significant / right-hand" position, and
+ * the bit at index Nb-1 in the "most significant / left-hand"
+ * position. Thus, unlike other containers, a %dynamic_bitset's
+ * index "counts from right to left," to put it very loosely.
+ *
+ * This behavior is preserved when translating to and from strings.
+ * For example, the first line of the following program probably
+ * prints "b('a') is 0001100001" on a modern ASCII system.
+ *
+ * @code
+ * #include <dynamic_bitset>
+ * #include <iostream>
+ * #include <sstream>
+ *
+ * using namespace std;
+ *
+ * int main()
+ * {
+ * long a = 'a';
+ * dynamic_bitset b(a);
+ *
+ * cout << "b('a') is " << b << endl;
+ *
+ * ostringstream s;
+ * s << b;
+ * string str = s.str();
+ * cout << "index 3 in the string is " << str[3] << " but\n"
+ * << "index 3 in the bitset is " << b[3] << endl;
+ * }
+ * @endcode
+ *
+ * Also see:
+ * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
+ * for a description of extensions.
+ *
+ * Most of the actual code isn't contained in %dynamic_bitset<>
+ * itself, but in the base class __dynamic_bitset_base. The base
+ * class works with whole words, not with individual bits. This
+ * allows us to specialize __dynamic_bitset_base for the important
+ * special case where the %dynamic_bitset is only a single word.
+ *
+ * Extra confusion can result due to the fact that the storage for
+ * __dynamic_bitset_base @e is a vector, and is indexed as such. This is
+ * carefully encapsulated.
+ */
+ template<typename _WordT = unsigned long long,
+ typename _Alloc = std::allocator<_WordT>>
+ class dynamic_bitset
+ : private __dynamic_bitset_base<_WordT, _Alloc>
+ {
+ static_assert(std::is_unsigned<_WordT>::value, "template argument "
+ "_WordT not an unsigned integral type");
+
+ public:
+
+ typedef __dynamic_bitset_base<_WordT, _Alloc> _Base;
+ typedef _WordT block_type;
+ typedef _Alloc allocator_type;
+ typedef size_t size_type;
+
+ static const size_type bits_per_block = __CHAR_BIT__ * sizeof(block_type);
+ // Use this: constexpr size_type std::numeric_limits<size_type>::max().
+ static const size_type npos = static_cast<size_type>(-1);
+
+ private:
+
+ // Clear the unused bits in the uppermost word.
+ void
+ _M_do_sanitize()
+ {
+ size_type __shift = this->_M_Nb % bits_per_block;
+ if (__shift > 0)
+ this->_M_hiword() &= ~((~static_cast<block_type>(0)) << __shift);
+ }
+
+ /**
+ * These versions of single-bit set, reset, flip, and test
+ * do no range checking.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ _M_unchecked_set(size_type __pos)
+ {
+ this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ _M_unchecked_set(size_type __pos, int __val)
+ {
+ if (__val)
+ this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
+ else
+ this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ _M_unchecked_reset(size_type __pos)
+ {
+ this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ _M_unchecked_flip(size_type __pos)
+ {
+ this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
+ return *this;
+ }
+
+ bool
+ _M_unchecked_test(size_type __pos) const
+ { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
+ != static_cast<_WordT>(0)); }
+
+ size_type _M_Nb;
+
+ public:
+ /**
+ * This encapsulates the concept of a single bit. An instance
+ * of this class is a proxy for an actual bit; this way the
+ * individual bit operations are done as faster word-size
+ * bitwise instructions.
+ *
+ * Most users will never need to use this class directly;
+ * conversions to and from bool are automatic and should be
+ * transparent. Overloaded operators help to preserve the
+ * illusion.
+ *
+ * (On a typical system, this "bit %reference" is 64 times the
+ * size of an actual bit. Ha.)
+ */
+ class reference
+ {
+ friend class dynamic_bitset;
+
+ block_type *_M_wp;
+ size_type _M_bpos;
+
+ // left undefined
+ reference();
+
+ public:
+ reference(dynamic_bitset& __b, size_type __pos)
+ {
+ this->_M_wp = &__b._M_getword(__pos);
+ this->_M_bpos = _Base::_S_whichbit(__pos);
+ }
+
+ ~reference()
+ { }
+
+ // For b[i] = __x;
+ reference&
+ operator=(bool __x)
+ {
+ if (__x)
+ *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
+ else
+ *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
+ return *this;
+ }
+
+ // For b[i] = b[__j];
+ reference&
+ operator=(const reference& __j)
+ {
+ if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
+ *this->_M_wp |= _Base::_S_maskbit(this->_M_bpos);
+ else
+ *this->_M_wp &= ~_Base::_S_maskbit(this->_M_bpos);
+ return *this;
+ }
+
+ // Flips the bit
+ bool
+ operator~() const
+ { return (*(_M_wp) & _Base::_S_maskbit(this->_M_bpos)) == 0; }
+
+ // For __x = b[i];
+ operator bool() const
+ { return (*(this->_M_wp) & _Base::_S_maskbit(this->_M_bpos)) != 0; }
+
+ // For b[i].flip();
+ reference&
+ flip()
+ {
+ *this->_M_wp ^= _Base::_S_maskbit(this->_M_bpos);
+ return *this;
+ }
+ };
+
+ friend class reference;
+
+ typedef bool const_reference;
+
+ // 23.3.5.1 constructors:
+ /// All bits set to zero.
+ explicit
+ dynamic_bitset(const allocator_type& __alloc = allocator_type())
+ : _Base(__alloc), _M_Nb(0)
+ { }
+
+ /// Initial bits bitwise-copied from a single word (others set to zero).
+ explicit
+ dynamic_bitset(size_type __nbits, unsigned long long __val = 0ULL,
+ const allocator_type& __alloc = allocator_type())
+ : _Base(__nbits, __val, __alloc),
+ _M_Nb(__nbits)
+ { }
+
+ dynamic_bitset(initializer_list<block_type> __il,
+ const allocator_type& __alloc = allocator_type())
+ : _Base(__alloc), _M_Nb(0)
+ { this->append(__il); }
+
+ /**
+ * @brief Use a subset of a string.
+ * @param __str A string of '0' and '1' characters.
+ * @param __pos Index of the first character in @p __str to use.
+ * @param __n The number of characters to copy.
+ * @throw std::out_of_range If @p __pos is bigger the size of @p __str.
+ * @throw std::invalid_argument If a character appears in the string
+ * which is neither '0' nor '1'.
+ */
+ template<typename _CharT, typename _Traits, typename _Alloc1>
+ explicit
+ dynamic_bitset(const std::basic_string<_CharT, _Traits, _Alloc1>& __str,
+ typename basic_string<_CharT,_Traits,_Alloc1>::size_type
+ __pos = 0,
+ typename basic_string<_CharT,_Traits,_Alloc1>::size_type
+ __n = std::basic_string<_CharT, _Traits, _Alloc1>::npos,
+ _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'),
+ const allocator_type& __alloc = allocator_type())
+ : _Base(__alloc),
+ _M_Nb(0) // Watch for npos.
+ {
+ if (__pos > __str.size())
+ __throw_out_of_range(__N("dynamic_bitset::bitset initial position "
+ "not valid"));
+
+ // Watch for npos.
+ this->_M_Nb = (__n > __str.size() ? __str.size() - __pos : __n);
+ this->resize(this->_M_Nb);
+ this->_M_copy_from_string(__str, __pos, __n,
+ _CharT('0'), _CharT('1'));
+ }
+
+ /**
+ * @brief Construct from a string.
+ * @param __str A string of '0' and '1' characters.
+ * @throw std::invalid_argument If a character appears in the string
+ * which is neither '0' nor '1'.
+ */
+ explicit
+ dynamic_bitset(const char* __str,
+ const allocator_type& __alloc = allocator_type())
+ : _Base(__alloc)
+ {
+ size_t __len = 0;
+ if (__str)
+ while (__str[__len] != '\0')
+ ++__len;
+ this->resize(__len);
+ this->_M_copy_from_ptr<char,std::char_traits<char>>
+ (__str, __len, 0, __len, '0', '1');
+ }
+
+ /**
+ * @brief Copy constructor.
+ */
+ dynamic_bitset(const dynamic_bitset& __b)
+ : _Base(__b), _M_Nb(__b.size())
+ { }
+
+ /**
+ * @brief Move constructor.
+ */
+ dynamic_bitset(dynamic_bitset&& __b)
+ : _Base(std::forward<_Base>(__b)), _M_Nb(__b.size())
+ { }
+
+ /**
+ * @brief Swap with another bitset.
+ */
+ void
+ swap(dynamic_bitset& __b)
+ {
+ this->_M_swap(__b);
+ std::swap(this->_M_Nb, __b._M_Nb);
+ }
+
+ /**
+ * @brief Assignment.
+ */
+ dynamic_bitset&
+ operator=(const dynamic_bitset& __b)
+ {
+ if (&__b != this)
+ {
+ this->_M_assign(__b);
+ this->_M_Nb = __b._M_Nb;
+ }
+ }
+
+ /**
+ * @brief Move assignment.
+ */
+ dynamic_bitset&
+ operator=(dynamic_bitset&& __b)
+ {
+ this->swap(__b);
+ return *this;
+ }
+
+ /**
+ * @brief Return the allocator for the bitset.
+ */
+ allocator_type
+ get_allocator() const
+ { return this->_M_get_allocator(); }
+
+ /**
+ * @brief Resize the bitset.
+ */
+ void
+ resize(size_type __nbits, bool __value = false)
+ {
+ this->_M_resize(__nbits, __value);
+ this->_M_Nb = __nbits;
+ this->_M_do_sanitize();
+ }
+
+ /**
+ * @brief Clear the bitset.
+ */
+ void
+ clear()
+ {
+ this->_M_clear();
+ this->_M_Nb = 0;
+ }
+
+ /**
+ * @brief Push a bit onto the high end of the bitset.
+ */
+ void
+ push_back(bool __bit)
+ {
+ if (size_t __offset = this->size() % bits_per_block == 0)
+ this->_M_do_append_block(block_type(0), this->_M_Nb);
+ ++this->_M_Nb;
+ this->_M_unchecked_set(this->_M_Nb, __bit);
+ }
+
+ /**
+ * @brief Append a block.
+ */
+ void
+ append(block_type __block)
+ {
+ this->_M_do_append_block(__block, this->_M_Nb);
+ this->_M_Nb += bits_per_block;
+ }
+
+ /**
+ * @brief
+ */
+ void
+ append(initializer_list<block_type> __il)
+ { this->append(__il.begin(), __il.end()); }
+
+ /**
+ * @brief Append an iterator range of blocks.
+ */
+ template <typename _BlockInputIterator>
+ void
+ append(_BlockInputIterator __first, _BlockInputIterator __last)
+ {
+ for (; __first != __last; ++__first)
+ this->append(*__first);
+ }
+
+ // 23.3.5.2 dynamic_bitset operations:
+ //@{
+ /**
+ * @brief Operations on dynamic_bitsets.
+ * @param __rhs A same-sized dynamic_bitset.
+ *
+ * These should be self-explanatory.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ operator&=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ {
+ this->_M_do_and(__rhs);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ operator&=(dynamic_bitset<_WordT, _Alloc>&& __rhs)
+ {
+ this->_M_do_and(std::move(__rhs));
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ operator|=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ {
+ this->_M_do_or(__rhs);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ operator^=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ {
+ this->_M_do_xor(__rhs);
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ operator-=(const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ {
+ this->_M_do_dif(__rhs);
+ return *this;
+ }
+ //@}
+
+ //@{
+ /**
+ * @brief Operations on dynamic_bitsets.
+ * @param __pos The number of places to shift.
+ *
+ * These should be self-explanatory.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ operator<<=(size_type __pos)
+ {
+ if (__builtin_expect(__pos < this->_M_Nb, 1))
+ {
+ this->_M_do_left_shift(__pos);
+ this->_M_do_sanitize();
+ }
+ else
+ this->_M_do_reset();
+ return *this;
+ }
+
+ dynamic_bitset<_WordT, _Alloc>&
+ operator>>=(size_type __pos)
+ {
+ if (__builtin_expect(__pos < this->_M_Nb, 1))
+ {
+ this->_M_do_right_shift(__pos);
+ this->_M_do_sanitize();
+ }
+ else
+ this->_M_do_reset();
+ return *this;
+ }
+ //@}
+
+ // Set, reset, and flip.
+ /**
+ * @brief Sets every bit to true.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ set()
+ {
+ this->_M_do_set();
+ this->_M_do_sanitize();
+ return *this;
+ }
+
+ /**
+ * @brief Sets a given bit to a particular value.
+ * @param __pos The index of the bit.
+ * @param __val Either true or false, defaults to true.
+ * @throw std::out_of_range If @a __pos is bigger the size of the %set.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ set(size_type __pos, bool __val = true)
+ {
+ if (__pos >= _M_Nb)
+ __throw_out_of_range(__N("dynamic_bitset::set"));
+ return this->_M_unchecked_set(__pos, __val);
+ }
+
+ /**
+ * @brief Sets every bit to false.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ reset()
+ {
+ this->_M_do_reset();
+ return *this;
+ }
+
+ /**
+ * @brief Sets a given bit to false.
+ * @param __pos The index of the bit.
+ * @throw std::out_of_range If @a __pos is bigger the size of the %set.
+ *
+ * Same as writing @c set(__pos, false).
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ reset(size_type __pos)
+ {
+ if (__pos >= _M_Nb)
+ __throw_out_of_range(__N("dynamic_bitset::reset"));
+ return this->_M_unchecked_reset(__pos);
+ }
+
+ /**
+ * @brief Toggles every bit to its opposite value.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ flip()
+ {
+ this->_M_do_flip();
+ this->_M_do_sanitize();
+ return *this;
+ }
+
+ /**
+ * @brief Toggles a given bit to its opposite value.
+ * @param __pos The index of the bit.
+ * @throw std::out_of_range If @a __pos is bigger the size of the %set.
+ */
+ dynamic_bitset<_WordT, _Alloc>&
+ flip(size_type __pos)
+ {
+ if (__pos >= _M_Nb)
+ __throw_out_of_range(__N("dynamic_bitset::flip"));
+ return this->_M_unchecked_flip(__pos);
+ }
+
+ /// See the no-argument flip().
+ dynamic_bitset<_WordT, _Alloc>
+ operator~() const
+ { return dynamic_bitset<_WordT, _Alloc>(*this).flip(); }
+
+ //@{
+ /**
+ * @brief Array-indexing support.
+ * @param __pos Index into the %dynamic_bitset.
+ * @return A bool for a 'const %dynamic_bitset'. For non-const
+ * bitsets, an instance of the reference proxy class.
+ * @note These operators do no range checking and throw no
+ * exceptions, as required by DR 11 to the standard.
+ */
+ reference
+ operator[](size_type __pos)
+ { return reference(*this,__pos); }
+
+ const_reference
+ operator[](size_type __pos) const
+ { return _M_unchecked_test(__pos); }
+ //@}
+
+ /**
+ * @brief Returns a numerical interpretation of the %dynamic_bitset.
+ * @return The integral equivalent of the bits.
+ * @throw std::overflow_error If there are too many bits to be
+ * represented in an @c unsigned @c long.
+ */
+ unsigned long
+ to_ulong() const
+ { return this->_M_do_to_ulong(); }
+
+ /**
+ * @brief Returns a numerical interpretation of the %dynamic_bitset.
+ * @return The integral equivalent of the bits.
+ * @throw std::overflow_error If there are too many bits to be
+ * represented in an @c unsigned @c long.
+ */
+ unsigned long long
+ to_ullong() const
+ { return this->_M_do_to_ullong(); }
+
+ /**
+ * @brief Returns a character interpretation of the %dynamic_bitset.
+ * @return The string equivalent of the bits.
+ *
+ * Note the ordering of the bits: decreasing character positions
+ * correspond to increasing bit positions (see the main class notes for
+ * an example).
+ */
+ template<typename _CharT = char,
+ typename _Traits = std::char_traits<_CharT>,
+ typename _Alloc1 = std::allocator<_CharT>>
+ std::basic_string<_CharT, _Traits, _Alloc1>
+ to_string(_CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) const
+ {
+ std::basic_string<_CharT, _Traits, _Alloc1> __result;
+ _M_copy_to_string(__result, __zero, __one);
+ return __result;
+ }
+
+ // Helper functions for string operations.
+ template<typename _CharT, typename _Traits>
+ void
+ _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
+ _CharT, _CharT);
+
+ template<typename _CharT, typename _Traits, typename _Alloc1>
+ void
+ _M_copy_from_string(const std::basic_string<_CharT,
+ _Traits, _Alloc1>& __str, size_t __pos, size_t __n,
+ _CharT __zero = _CharT('0'),
+ _CharT __one = _CharT('1'))
+ { _M_copy_from_ptr<_CharT, _Traits>(__str.data(), __str.size(),
+ __pos, __n, __zero, __one); }
+
+ template<typename _CharT, typename _Traits, typename _Alloc1>
+ void
+ _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
+ _CharT __zero = _CharT('0'),
+ _CharT __one = _CharT('1')) const;
+
+ /// Returns the number of bits which are set.
+ size_type
+ count() const
+ { return this->_M_do_count(); }
+
+ /// Returns the total number of bits.
+ size_type
+ size() const
+ { return this->_M_Nb; }
+
+ /// Returns the total number of blocks.
+ size_type num_blocks() const
+ { return this->_M_size(); }
+
+ /// Returns true if the dynamic_bitset is empty.
+ bool
+ empty() const
+ { return (this->_M_Nb == 0); }
+
+ /// Returns the maximum size of a dynamic_bitset object having the same
+ /// type as *this.
+ /// The real answer is max() * bits_per_block but is likely to overflow.
+ /*constexpr*/ size_type
+ max_size() const
+ { return std::numeric_limits<block_type>::max(); }
+
+ /**
+ * @brief Tests the value of a bit.
+ * @param __pos The index of a bit.
+ * @return The value at @a __pos.
+ * @throw std::out_of_range If @a __pos is bigger the size of the %set.
+ */
+ bool
+ test(size_type __pos) const
+ {
+ if (__pos >= _M_Nb)
+ __throw_out_of_range(__N("dynamic_bitset::test"));
+ return _M_unchecked_test(__pos);
+ }
+
+ /**
+ * @brief Tests whether all the bits are on.
+ * @return True if all the bits are set.
+ */
+ bool
+ all() const
+ { return this->_M_are_all_aux() == _M_Nb; }
+
+ /**
+ * @brief Tests whether any of the bits are on.
+ * @return True if at least one bit is set.
+ */
+ bool
+ any() const
+ { return this->_M_is_any(); }
+
+ /**
+ * @brief Tests whether any of the bits are on.
+ * @return True if none of the bits are set.
+ */
+ bool
+ none() const
+ { return !this->_M_is_any(); }
+
+ //@{
+ /// Self-explanatory.
+ dynamic_bitset<_WordT, _Alloc>
+ operator<<(size_type __pos) const
+ { return dynamic_bitset<_WordT, _Alloc>(*this) <<= __pos; }
+
+ dynamic_bitset<_WordT, _Alloc>
+ operator>>(size_type __pos) const
+ { return dynamic_bitset<_WordT, _Alloc>(*this) >>= __pos; }
+ //@}
+
+ /**
+ * @brief Finds the index of the first "on" bit.
+ * @return The index of the first bit set, or size() if not found.
+ * @sa find_next
+ */
+ size_type
+ find_first() const
+ { return this->_M_do_find_first(this->_M_Nb); }
+
+ /**
+ * @brief Finds the index of the next "on" bit after prev.
+ * @return The index of the next bit set, or size() if not found.
+ * @param __prev Where to start searching.
+ * @sa find_first
+ */
+ size_type
+ find_next(size_t __prev) const
+ { return this->_M_do_find_next(__prev, this->_M_Nb); }
+
+ bool
+ is_subset_of(const dynamic_bitset& __b) const
+ { return this->_M_is_subset_of(__b); }
+
+ bool
+ is_proper_subset_of(const dynamic_bitset& __b) const
+ { return this->_M_is_proper_subset_of(__b); }
+ };
+
+ // Definitions of non-inline member functions.
+ template<typename _WordT, typename _Alloc>
+ template<typename _CharT, typename _Traits>
+ void
+ dynamic_bitset<_WordT, _Alloc>::
+ _M_copy_from_ptr(const _CharT* __str, size_t __len,
+ size_t __pos, size_t __n, _CharT __zero, _CharT __one)
+ {
+ reset();
+ const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
+ for (size_t __i = __nbits; __i > 0; --__i)
+ {
+ const _CharT __c = __str[__pos + __nbits - __i];
+ if (_Traits::eq(__c, __zero))
+ ;
+ else if (_Traits::eq(__c, __one))
+ _M_unchecked_set(__i - 1);
+ else
+ __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
+ }
+ }
+
+ template<typename _WordT, typename _Alloc>
+ template<typename _CharT, typename _Traits, typename _Alloc1>
+ void
+ dynamic_bitset<_WordT, _Alloc>::
+ _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc1>& __str,
+ _CharT __zero, _CharT __one) const
+ {
+ __str.assign(_M_Nb, __zero);
+ for (size_t __i = _M_Nb; __i > 0; --__i)
+ if (_M_unchecked_test(__i - 1))
+ _Traits::assign(__str[_M_Nb - __i], __one);
+ }
+
+
+ //@{
+ /// These comparisons for equality/inequality are, well, @e bitwise.
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator==(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return __lhs._M_is_equal(__rhs); }
+
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator!=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return !__lhs._M_is_equal(__rhs); }
+
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator<(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return __lhs._M_is_less(__rhs); }
+
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator<=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return !(__lhs > __rhs); }
+
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator>(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return __rhs < __lhs; }
+
+ template<typename _WordT, typename _Alloc>
+ bool
+ operator>=(const dynamic_bitset<_WordT, _Alloc>& __lhs,
+ const dynamic_bitset<_WordT, _Alloc>& __rhs)
+ { return !(__lhs < __rhs); }
+ //@}
+
+ // 23.3.5.3 bitset operations:
+ //@{
+ /**
+ * @brief Global bitwise operations on bitsets.
+ * @param __x A bitset.
+ * @param __y A bitset of the same size as @a __x.
+ * @return A new bitset.
+ *
+ * These should be self-explanatory.
+ */
+ template<typename _WordT, typename _Alloc>
+ inline dynamic_bitset<_WordT, _Alloc>
+ operator&(const dynamic_bitset<_WordT, _Alloc>& __x,
+ const dynamic_bitset<_WordT, _Alloc>& __y)
+ {
+ dynamic_bitset<_WordT, _Alloc> __result(__x);
+ __result &= __y;
+ return __result;
+ }
+
+ template<typename _WordT, typename _Alloc>
+ inline dynamic_bitset<_WordT, _Alloc>
+ operator|(const dynamic_bitset<_WordT, _Alloc>& __x,
+ const dynamic_bitset<_WordT, _Alloc>& __y)
+ {
+ dynamic_bitset<_WordT, _Alloc> __result(__x);
+ __result |= __y;
+ return __result;
+ }
+
+ template <typename _WordT, typename _Alloc>
+ inline dynamic_bitset<_WordT, _Alloc>
+ operator^(const dynamic_bitset<_WordT, _Alloc>& __x,
+ const dynamic_bitset<_WordT, _Alloc>& __y)
+ {
+ dynamic_bitset<_WordT, _Alloc> __result(__x);
+ __result ^= __y;
+ return __result;
+ }
+
+ template <typename _WordT, typename _Alloc>
+ inline dynamic_bitset<_WordT, _Alloc>
+ operator-(const dynamic_bitset<_WordT, _Alloc>& __x,
+ const dynamic_bitset<_WordT, _Alloc>& __y)
+ {
+ dynamic_bitset<_WordT, _Alloc> __result(__x);
+ __result -= __y;
+ return __result;
+ }
+ //@}
+
+ //@{
+ /**
+ * @brief Global I/O operators for bitsets.
+ *
+ * Direct I/O between streams and bitsets is supported. Output is
+ * straightforward. Input will skip whitespace and only accept '0'
+ * and '1' characters. The %dynamic_bitset will grow as necessary
+ * to hold the string of bits.
+ */
+ template<typename _CharT, typename _Traits,
+ typename _WordT, typename _Alloc>
+ std::basic_istream<_CharT, _Traits>&
+ operator>>(std::basic_istream<_CharT, _Traits>& __is,
+ dynamic_bitset<_WordT, _Alloc>& __x)
+ {
+ typedef typename _Traits::char_type char_type;
+ typedef std::basic_istream<_CharT, _Traits> __istream_type;
+ typedef typename __istream_type::ios_base __ios_base;
+
+ std::basic_string<_CharT, _Traits> __tmp;
+ __tmp.reserve(__x.size());
+
+ const char_type __zero = __is.widen('0');
+ const char_type __one = __is.widen('1');
+
+ typename __ios_base::iostate __state = __ios_base::goodbit;
+ typename __istream_type::sentry __sentry(__is);
+ if (__sentry)
+ {
+ __try
+ {
+ while (1)
+ {
+ static typename _Traits::int_type __eof = _Traits::eof();
+
+ typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
+ if (_Traits::eq_int_type(__c1, __eof))
+ {
+ __state |= __ios_base::eofbit;
+ break;
+ }
+ else
+ {
+ const char_type __c2 = _Traits::to_char_type(__c1);
+ if (_Traits::eq(__c2, __zero))
+ __tmp.push_back(__zero);
+ else if (_Traits::eq(__c2, __one))
+ __tmp.push_back(__one);
+ else if (_Traits::
+ eq_int_type(__is.rdbuf()->sputbackc(__c2),
+ __eof))
+ {
+ __state |= __ios_base::failbit;
+ break;
+ }
+ else
+ break;
+ }
+ }
+ }
+ __catch(__cxxabiv1::__forced_unwind&)
+ {
+ __is._M_setstate(__ios_base::badbit);
+ __throw_exception_again;
+ }
+ __catch(...)
+ { __is._M_setstate(__ios_base::badbit); }
+ }
+
+ __x.resize(__tmp.size());
+
+ if (__tmp.empty() && __x.size())
+ __state |= __ios_base::failbit;
+ else
+ __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
+ __zero, __one);
+ if (__state)
+ __is.setstate(__state);
+ return __is;
+ }
+
+ template <typename _CharT, typename _Traits,
+ typename _WordT, typename _Alloc>
+ std::basic_ostream<_CharT, _Traits>&
+ operator<<(std::basic_ostream<_CharT, _Traits>& __os,
+ const dynamic_bitset<_WordT, _Alloc>& __x)
+ {
+ std::basic_string<_CharT, _Traits> __tmp;
+
+ const ctype<_CharT>& __ct = use_facet<ctype<_CharT>>(__os.getloc());
+ __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
+ return __os << __tmp;
+ }
+ //@}
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // tr2
+} // std
+
+#undef _GLIBCXX_BITSET_BITS_PER_WORD
+
+#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET */
projects / cross.git / blobdiff