// TR2 <dynamic_bitset> -*- C++ -*-
// Copyright (C) 2009-2013 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 <string>
#include <memory> // For std::allocator
#include <bits/functexcept.h> // For invalid_argument, out_of_range,
// overflow_error
#include <iosfwd>
#include <bits/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) noexcept
{ return __pos / _S_bits_per_block; }
static size_type
_S_whichbyte(size_type __pos) noexcept
{ return (__pos % _S_bits_per_block) / __CHAR_BIT__; }
static size_type
_S_whichbit(size_type __pos) noexcept
{ return __pos % _S_bits_per_block; }
static block_type
_S_maskbit(size_type __pos) noexcept
{ 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 noexcept
{ 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 noexcept
{ return this->_M_do_count(); }
/// Returns the total number of bits.
size_type
size() const noexcept
{ return this->_M_Nb; }
/// Returns the total number of blocks.
size_type
num_blocks() const noexcept
{ return this->_M_size(); }
/// Returns true if the dynamic_bitset is empty.
bool
empty() const noexcept
{ 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() noexcept
{ 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 */