// ----------------------------------------------------------- | |
// | |
// Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek | |
// Copyright (c) 2003-2006, 2008 Gennaro Prota | |
// | |
// Distributed under the Boost Software License, Version 1.0. | |
// (See accompanying file LICENSE_1_0.txt or copy at | |
// http://www.boost.org/LICENSE_1_0.txt) | |
// | |
// ----------------------------------------------------------- | |
#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP | |
#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP | |
#include <assert.h> | |
#include <string> | |
#include <stdexcept> | |
#include <algorithm> | |
#include <vector> | |
#include <climits> // for CHAR_BIT | |
#include "boost/dynamic_bitset/config.hpp" | |
#ifndef BOOST_NO_STD_LOCALE | |
# include <locale> | |
#endif | |
#if defined(BOOST_OLD_IOSTREAMS) | |
# include <iostream.h> | |
# include <ctype.h> // for isspace | |
#else | |
# include <istream> | |
# include <ostream> | |
#endif | |
#include "boost/dynamic_bitset_fwd.hpp" | |
#include "boost/detail/dynamic_bitset.hpp" | |
#include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter) | |
#include "boost/static_assert.hpp" | |
#include "boost/limits.hpp" | |
#include "boost/pending/lowest_bit.hpp" | |
namespace boost { | |
template <typename Block, typename Allocator> | |
class dynamic_bitset | |
{ | |
// Portability note: member function templates are defined inside | |
// this class definition to avoid problems with VC++. Similarly, | |
// with the member functions of nested classes. | |
// | |
// [October 2008: the note above is mostly historical; new versions | |
// of VC++ are likely able to digest a more drinking form of the | |
// code; but changing it now is probably not worth the risks...] | |
BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value); | |
public: | |
typedef Block block_type; | |
typedef Allocator allocator_type; | |
typedef std::size_t size_type; | |
typedef block_type block_width_type; | |
BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits)); | |
BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1)); | |
public: | |
// A proxy class to simulate lvalues of bit type. | |
// | |
class reference | |
{ | |
friend class dynamic_bitset<Block, Allocator>; | |
// the one and only non-copy ctor | |
reference(block_type & b, block_type pos) | |
:m_block(b), | |
m_mask( (assert(pos < bits_per_block), | |
block_type(1) << pos ) | |
) | |
{ } | |
void operator&(); // left undefined | |
public: | |
// copy constructor: compiler generated | |
operator bool() const { return (m_block & m_mask) != 0; } | |
bool operator~() const { return (m_block & m_mask) == 0; } | |
reference& flip() { do_flip(); return *this; } | |
reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x | |
reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j] | |
reference& operator|=(bool x) { if (x) do_set(); return *this; } | |
reference& operator&=(bool x) { if (!x) do_reset(); return *this; } | |
reference& operator^=(bool x) { if (x) do_flip(); return *this; } | |
reference& operator-=(bool x) { if (x) do_reset(); return *this; } | |
private: | |
block_type & m_block; | |
const block_type m_mask; | |
void do_set() { m_block |= m_mask; } | |
void do_reset() { m_block &= ~m_mask; } | |
void do_flip() { m_block ^= m_mask; } | |
void do_assign(bool x) { x? do_set() : do_reset(); } | |
}; | |
typedef bool const_reference; | |
// constructors, etc. | |
explicit | |
dynamic_bitset(const Allocator& alloc = Allocator()); | |
explicit | |
dynamic_bitset(size_type num_bits, unsigned long value = 0, | |
const Allocator& alloc = Allocator()); | |
// WARNING: you should avoid using this constructor. | |
// | |
// A conversion from string is, in most cases, formatting, | |
// and should be performed by using operator>>. | |
// | |
// NOTE: | |
// Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos. | |
// g++ 3.2 requires them and probably the standard will - see core issue 325 | |
// NOTE 2: | |
// split into two constructors because of bugs in MSVC 6.0sp5 with STLport | |
template <typename CharT, typename Traits, typename Alloc> | |
dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s, | |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos, | |
typename std::basic_string<CharT, Traits, Alloc>::size_type n, | |
size_type num_bits = npos, | |
const Allocator& alloc = Allocator()) | |
:m_bits(alloc), | |
m_num_bits(0) | |
{ | |
init_from_string(s, pos, n, num_bits); | |
} | |
template <typename CharT, typename Traits, typename Alloc> | |
explicit | |
dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s, | |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0) | |
:m_bits(Allocator()), | |
m_num_bits(0) | |
{ | |
init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos), | |
npos); | |
} | |
// The first bit in *first is the least significant bit, and the | |
// last bit in the block just before *last is the most significant bit. | |
template <typename BlockInputIterator> | |
dynamic_bitset(BlockInputIterator first, BlockInputIterator last, | |
const Allocator& alloc = Allocator()) | |
:m_bits(alloc), | |
m_num_bits(0) | |
{ | |
using boost::detail::dynamic_bitset_impl::value_to_type; | |
using boost::detail::dynamic_bitset_impl::is_numeric; | |
const value_to_type< | |
is_numeric<BlockInputIterator>::value> selector; | |
dispatch_init(first, last, selector); | |
} | |
template <typename T> | |
void dispatch_init(T num_bits, unsigned long value, | |
detail::dynamic_bitset_impl::value_to_type<true>) | |
{ | |
init_from_unsigned_long(static_cast<size_type>(num_bits), value); | |
} | |
template <typename T> | |
void dispatch_init(T first, T last, | |
detail::dynamic_bitset_impl::value_to_type<false>) | |
{ | |
init_from_block_range(first, last); | |
} | |
template <typename BlockIter> | |
void init_from_block_range(BlockIter first, BlockIter last) | |
{ | |
assert(m_bits.size() == 0); | |
m_bits.insert(m_bits.end(), first, last); | |
m_num_bits = m_bits.size() * bits_per_block; | |
} | |
// copy constructor | |
dynamic_bitset(const dynamic_bitset& b); | |
~dynamic_bitset(); | |
void swap(dynamic_bitset& b); | |
dynamic_bitset& operator=(const dynamic_bitset& b); | |
allocator_type get_allocator() const; | |
// size changing operations | |
void resize(size_type num_bits, bool value = false); | |
void clear(); | |
void push_back(bool bit); | |
void append(Block block); | |
template <typename BlockInputIterator> | |
void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag) | |
{ | |
std::vector<Block, Allocator> v(first, last); | |
m_append(v.begin(), v.end(), std::random_access_iterator_tag()); | |
} | |
template <typename BlockInputIterator> | |
void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag) | |
{ | |
assert(first != last); | |
block_width_type r = count_extra_bits(); | |
std::size_t d = boost::detail::distance(first, last); | |
m_bits.reserve(num_blocks() + d); | |
if (r == 0) { | |
for( ; first != last; ++first) | |
m_bits.push_back(*first); // could use vector<>::insert() | |
} | |
else { | |
m_highest_block() |= (*first << r); | |
do { | |
Block b = *first >> (bits_per_block - r); | |
++first; | |
m_bits.push_back(b | (first==last? 0 : *first << r)); | |
} while (first != last); | |
} | |
m_num_bits += bits_per_block * d; | |
} | |
template <typename BlockInputIterator> | |
void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee | |
{ | |
if (first != last) { | |
typename detail::iterator_traits<BlockInputIterator>::iterator_category cat; | |
m_append(first, last, cat); | |
} | |
} | |
// bitset operations | |
dynamic_bitset& operator&=(const dynamic_bitset& b); | |
dynamic_bitset& operator|=(const dynamic_bitset& b); | |
dynamic_bitset& operator^=(const dynamic_bitset& b); | |
dynamic_bitset& operator-=(const dynamic_bitset& b); | |
dynamic_bitset& operator<<=(size_type n); | |
dynamic_bitset& operator>>=(size_type n); | |
dynamic_bitset operator<<(size_type n) const; | |
dynamic_bitset operator>>(size_type n) const; | |
// basic bit operations | |
dynamic_bitset& set(size_type n, bool val = true); | |
dynamic_bitset& set(); | |
dynamic_bitset& reset(size_type n); | |
dynamic_bitset& reset(); | |
dynamic_bitset& flip(size_type n); | |
dynamic_bitset& flip(); | |
bool test(size_type n) const; | |
bool any() const; | |
bool none() const; | |
dynamic_bitset operator~() const; | |
size_type count() const; | |
// subscript | |
reference operator[](size_type pos) { | |
return reference(m_bits[block_index(pos)], bit_index(pos)); | |
} | |
bool operator[](size_type pos) const { return test(pos); } | |
unsigned long to_ulong() const; | |
size_type size() const; | |
size_type num_blocks() const; | |
size_type max_size() const; | |
bool empty() const; | |
bool is_subset_of(const dynamic_bitset& a) const; | |
bool is_proper_subset_of(const dynamic_bitset& a) const; | |
bool intersects(const dynamic_bitset & a) const; | |
// lookup | |
size_type find_first() const; | |
size_type find_next(size_type pos) const; | |
#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS | |
// lexicographical comparison | |
template <typename B, typename A> | |
friend bool operator==(const dynamic_bitset<B, A>& a, | |
const dynamic_bitset<B, A>& b); | |
template <typename B, typename A> | |
friend bool operator<(const dynamic_bitset<B, A>& a, | |
const dynamic_bitset<B, A>& b); | |
template <typename B, typename A, typename BlockOutputIterator> | |
friend void to_block_range(const dynamic_bitset<B, A>& b, | |
BlockOutputIterator result); | |
template <typename BlockIterator, typename B, typename A> | |
friend void from_block_range(BlockIterator first, BlockIterator last, | |
dynamic_bitset<B, A>& result); | |
template <typename CharT, typename Traits, typename B, typename A> | |
friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, | |
dynamic_bitset<B, A>& b); | |
template <typename B, typename A, typename stringT> | |
friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all); | |
#endif | |
private: | |
BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits); | |
typedef std::vector<block_type, allocator_type> buffer_type; | |
void m_zero_unused_bits(); | |
bool m_check_invariants() const; | |
size_type m_do_find_from(size_type first_block) const; | |
block_width_type count_extra_bits() const { return bit_index(size()); } | |
static size_type block_index(size_type pos) { return pos / bits_per_block; } | |
static block_width_type bit_index(size_type pos) { return static_cast<block_width_type>(pos % bits_per_block); } | |
static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); } | |
template <typename CharT, typename Traits, typename Alloc> | |
void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s, | |
typename std::basic_string<CharT, Traits, Alloc>::size_type pos, | |
typename std::basic_string<CharT, Traits, Alloc>::size_type n, | |
size_type num_bits) | |
{ | |
assert(pos <= s.size()); | |
typedef typename std::basic_string<CharT, Traits, Alloc> StrT; | |
typedef typename StrT::traits_type Tr; | |
const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); | |
const size_type sz = ( num_bits != npos? num_bits : rlen); | |
m_bits.resize(calc_num_blocks(sz)); | |
m_num_bits = sz; | |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale()); | |
const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); | |
const size_type m = num_bits < rlen ? num_bits : rlen; | |
typename StrT::size_type i = 0; | |
for( ; i < m; ++i) { | |
const CharT c = s[(pos + m - 1) - i]; | |
assert( Tr::eq(c, one) | |
|| Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) ); | |
if (Tr::eq(c, one)) | |
set(i); | |
} | |
} | |
void init_from_unsigned_long(size_type num_bits, | |
unsigned long value/*, | |
const Allocator& alloc*/) | |
{ | |
assert(m_bits.size() == 0); | |
m_bits.resize(calc_num_blocks(num_bits)); | |
m_num_bits = num_bits; | |
typedef unsigned long num_type; | |
typedef boost::detail::dynamic_bitset_impl | |
::shifter<num_type, bits_per_block, ulong_width> shifter; | |
//if (num_bits == 0) | |
// return; | |
// zero out all bits at pos >= num_bits, if any; | |
// note that: num_bits == 0 implies value == 0 | |
if (num_bits < static_cast<size_type>(ulong_width)) { | |
const num_type mask = (num_type(1) << num_bits) - 1; | |
value &= mask; | |
} | |
typename buffer_type::iterator it = m_bits.begin(); | |
for( ; value; shifter::left_shift(value), ++it) { | |
*it = static_cast<block_type>(value); | |
} | |
} | |
BOOST_DYNAMIC_BITSET_PRIVATE: | |
bool m_unchecked_test(size_type pos) const; | |
static size_type calc_num_blocks(size_type num_bits); | |
Block& m_highest_block(); | |
const Block& m_highest_block() const; | |
buffer_type m_bits; | |
size_type m_num_bits; | |
class bit_appender; | |
friend class bit_appender; | |
class bit_appender { | |
// helper for stream >> | |
// Supplies to the lack of an efficient append at the less | |
// significant end: bits are actually appended "at left" but | |
// rearranged in the destructor. From the perspective of | |
// client code everything works *as if* dynamic_bitset<> had | |
// an append_at_right() function (eventually throwing the same | |
// exceptions as push_back) except that the function is in fact | |
// called bit_appender::do_append(). | |
// | |
dynamic_bitset & bs; | |
size_type n; | |
Block mask; | |
Block * current; | |
// not implemented | |
bit_appender(const bit_appender &); | |
bit_appender & operator=(const bit_appender &); | |
public: | |
bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {} | |
~bit_appender() { | |
// reverse the order of blocks, shift | |
// if needed, and then resize | |
// | |
std::reverse(bs.m_bits.begin(), bs.m_bits.end()); | |
const block_width_type offs = bit_index(n); | |
if (offs) | |
bs >>= (bits_per_block - offs); | |
bs.resize(n); // doesn't enlarge, so can't throw | |
assert(bs.m_check_invariants()); | |
} | |
inline void do_append(bool value) { | |
if (mask == 0) { | |
bs.append(Block(0)); | |
current = &bs.m_highest_block(); | |
mask = Block(1) << (bits_per_block - 1); | |
} | |
if(value) | |
*current |= mask; | |
mask /= 2; | |
++n; | |
} | |
size_type get_count() const { return n; } | |
}; | |
}; | |
#if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION | |
template <typename Block, typename Allocator> | |
const typename dynamic_bitset<Block, Allocator>::block_width_type | |
dynamic_bitset<Block, Allocator>::bits_per_block; | |
template <typename Block, typename Allocator> | |
const typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::npos; | |
template <typename Block, typename Allocator> | |
const typename dynamic_bitset<Block, Allocator>::block_width_type | |
dynamic_bitset<Block, Allocator>::ulong_width; | |
#endif | |
// Global Functions: | |
// comparison | |
template <typename Block, typename Allocator> | |
bool operator!=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b); | |
template <typename Block, typename Allocator> | |
bool operator<=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b); | |
template <typename Block, typename Allocator> | |
bool operator>(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b); | |
template <typename Block, typename Allocator> | |
bool operator>=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b); | |
// stream operators | |
#ifdef BOOST_OLD_IOSTREAMS | |
template <typename Block, typename Allocator> | |
std::ostream& operator<<(std::ostream& os, | |
const dynamic_bitset<Block, Allocator>& b); | |
template <typename Block, typename Allocator> | |
std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b); | |
#else | |
template <typename CharT, typename Traits, typename Block, typename Allocator> | |
std::basic_ostream<CharT, Traits>& | |
operator<<(std::basic_ostream<CharT, Traits>& os, | |
const dynamic_bitset<Block, Allocator>& b); | |
template <typename CharT, typename Traits, typename Block, typename Allocator> | |
std::basic_istream<CharT, Traits>& | |
operator>>(std::basic_istream<CharT, Traits>& is, | |
dynamic_bitset<Block, Allocator>& b); | |
#endif | |
// bitset operations | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator&(const dynamic_bitset<Block, Allocator>& b1, | |
const dynamic_bitset<Block, Allocator>& b2); | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator|(const dynamic_bitset<Block, Allocator>& b1, | |
const dynamic_bitset<Block, Allocator>& b2); | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator^(const dynamic_bitset<Block, Allocator>& b1, | |
const dynamic_bitset<Block, Allocator>& b2); | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator-(const dynamic_bitset<Block, Allocator>& b1, | |
const dynamic_bitset<Block, Allocator>& b2); | |
// namespace scope swap | |
template<typename Block, typename Allocator> | |
void swap(dynamic_bitset<Block, Allocator>& b1, | |
dynamic_bitset<Block, Allocator>& b2); | |
template <typename Block, typename Allocator, typename stringT> | |
void | |
to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); | |
template <typename Block, typename Allocator, typename BlockOutputIterator> | |
void | |
to_block_range(const dynamic_bitset<Block, Allocator>& b, | |
BlockOutputIterator result); | |
template <typename BlockIterator, typename B, typename A> | |
inline void | |
from_block_range(BlockIterator first, BlockIterator last, | |
dynamic_bitset<B, A>& result) | |
{ | |
// PRE: distance(first, last) <= numblocks() | |
std::copy (first, last, result.m_bits.begin()); | |
} | |
//============================================================================= | |
// dynamic_bitset implementation | |
//----------------------------------------------------------------------------- | |
// constructors, etc. | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc) | |
: m_bits(alloc), m_num_bits(0) | |
{ | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>:: | |
dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc) | |
: m_bits(alloc), | |
m_num_bits(0) | |
{ | |
init_from_unsigned_long(num_bits, value); | |
} | |
// copy constructor | |
template <typename Block, typename Allocator> | |
inline dynamic_bitset<Block, Allocator>:: | |
dynamic_bitset(const dynamic_bitset& b) | |
: m_bits(b.m_bits), m_num_bits(b.m_num_bits) | |
{ | |
} | |
template <typename Block, typename Allocator> | |
inline dynamic_bitset<Block, Allocator>:: | |
~dynamic_bitset() | |
{ | |
assert(m_check_invariants()); | |
} | |
template <typename Block, typename Allocator> | |
inline void dynamic_bitset<Block, Allocator>:: | |
swap(dynamic_bitset<Block, Allocator>& b) // no throw | |
{ | |
std::swap(m_bits, b.m_bits); | |
std::swap(m_num_bits, b.m_num_bits); | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>:: | |
operator=(const dynamic_bitset<Block, Allocator>& b) | |
{ | |
m_bits = b.m_bits; | |
m_num_bits = b.m_num_bits; | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
inline typename dynamic_bitset<Block, Allocator>::allocator_type | |
dynamic_bitset<Block, Allocator>::get_allocator() const | |
{ | |
return m_bits.get_allocator(); | |
} | |
//----------------------------------------------------------------------------- | |
// size changing operations | |
template <typename Block, typename Allocator> | |
void dynamic_bitset<Block, Allocator>:: | |
resize(size_type num_bits, bool value) // strong guarantee | |
{ | |
const size_type old_num_blocks = num_blocks(); | |
const size_type required_blocks = calc_num_blocks(num_bits); | |
const block_type v = value? ~Block(0) : Block(0); | |
if (required_blocks != old_num_blocks) { | |
m_bits.resize(required_blocks, v); // s.g. (copy) | |
} | |
// At this point: | |
// | |
// - if the buffer was shrunk, we have nothing more to do, | |
// except a call to m_zero_unused_bits() | |
// | |
// - if it was enlarged, all the (used) bits in the new blocks have | |
// the correct value, but we have not yet touched those bits, if | |
// any, that were 'unused bits' before enlarging: if value == true, | |
// they must be set. | |
if (value && (num_bits > m_num_bits)) { | |
const block_width_type extra_bits = count_extra_bits(); | |
if (extra_bits) { | |
assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size()); | |
// Set them. | |
m_bits[old_num_blocks - 1] |= (v << extra_bits); | |
} | |
} | |
m_num_bits = num_bits; | |
m_zero_unused_bits(); | |
} | |
template <typename Block, typename Allocator> | |
void dynamic_bitset<Block, Allocator>:: | |
clear() // no throw | |
{ | |
m_bits.clear(); | |
m_num_bits = 0; | |
} | |
template <typename Block, typename Allocator> | |
void dynamic_bitset<Block, Allocator>:: | |
push_back(bool bit) | |
{ | |
const size_type sz = size(); | |
resize(sz + 1); | |
set(sz, bit); | |
} | |
template <typename Block, typename Allocator> | |
void dynamic_bitset<Block, Allocator>:: | |
append(Block value) // strong guarantee | |
{ | |
const block_width_type r = count_extra_bits(); | |
if (r == 0) { | |
// the buffer is empty, or all blocks are filled | |
m_bits.push_back(value); | |
} | |
else { | |
m_bits.push_back(value >> (bits_per_block - r)); | |
m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2 | |
} | |
m_num_bits += bits_per_block; | |
assert(m_check_invariants()); | |
} | |
//----------------------------------------------------------------------------- | |
// bitset operations | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs) | |
{ | |
assert(size() == rhs.size()); | |
for (size_type i = 0; i < num_blocks(); ++i) | |
m_bits[i] &= rhs.m_bits[i]; | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs) | |
{ | |
assert(size() == rhs.size()); | |
for (size_type i = 0; i < num_blocks(); ++i) | |
m_bits[i] |= rhs.m_bits[i]; | |
//m_zero_unused_bits(); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs) | |
{ | |
assert(size() == rhs.size()); | |
for (size_type i = 0; i < this->num_blocks(); ++i) | |
m_bits[i] ^= rhs.m_bits[i]; | |
//m_zero_unused_bits(); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs) | |
{ | |
assert(size() == rhs.size()); | |
for (size_type i = 0; i < num_blocks(); ++i) | |
m_bits[i] &= ~rhs.m_bits[i]; | |
//m_zero_unused_bits(); | |
return *this; | |
} | |
// | |
// NOTE: | |
// Note that the 'if (r != 0)' is crucial to avoid undefined | |
// behavior when the left hand operand of >> isn't promoted to a | |
// wider type (because rs would be too large). | |
// | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::operator<<=(size_type n) | |
{ | |
if (n >= m_num_bits) | |
return reset(); | |
//else | |
if (n > 0) { | |
size_type const last = num_blocks() - 1; // num_blocks() is >= 1 | |
size_type const div = n / bits_per_block; // div is <= last | |
block_width_type const r = bit_index(n); | |
block_type * const b = &m_bits[0]; | |
if (r != 0) { | |
block_width_type const rs = bits_per_block - r; | |
for (size_type i = last-div; i>0; --i) { | |
b[i+div] = (b[i] << r) | (b[i-1] >> rs); | |
} | |
b[div] = b[0] << r; | |
} | |
else { | |
for (size_type i = last-div; i>0; --i) { | |
b[i+div] = b[i]; | |
} | |
b[div] = b[0]; | |
} | |
// zero out div blocks at the less significant end | |
std::fill_n(b, div, static_cast<block_type>(0)); | |
// zero out any 1 bit that flowed into the unused part | |
m_zero_unused_bits(); // thanks to Lester Gong | |
} | |
return *this; | |
} | |
// | |
// NOTE: | |
// see the comments to operator <<= | |
// | |
template <typename B, typename A> | |
dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) { | |
if (n >= m_num_bits) { | |
return reset(); | |
} | |
//else | |
if (n>0) { | |
size_type const last = num_blocks() - 1; // num_blocks() is >= 1 | |
size_type const div = n / bits_per_block; // div is <= last | |
block_width_type const r = bit_index(n); | |
block_type * const b = &m_bits[0]; | |
if (r != 0) { | |
block_width_type const ls = bits_per_block - r; | |
for (size_type i = div; i < last; ++i) { | |
b[i-div] = (b[i] >> r) | (b[i+1] << ls); | |
} | |
// r bits go to zero | |
b[last-div] = b[last] >> r; | |
} | |
else { | |
for (size_type i = div; i <= last; ++i) { | |
b[i-div] = b[i]; | |
} | |
// note the '<=': the last iteration 'absorbs' | |
// b[last-div] = b[last] >> 0; | |
} | |
// div blocks are zero filled at the most significant end | |
std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0)); | |
} | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
dynamic_bitset<Block, Allocator>::operator<<(size_type n) const | |
{ | |
dynamic_bitset r(*this); | |
return r <<= n; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
dynamic_bitset<Block, Allocator>::operator>>(size_type n) const | |
{ | |
dynamic_bitset r(*this); | |
return r >>= n; | |
} | |
//----------------------------------------------------------------------------- | |
// basic bit operations | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::set(size_type pos, bool val) | |
{ | |
assert(pos < m_num_bits); | |
if (val) | |
m_bits[block_index(pos)] |= bit_mask(pos); | |
else | |
reset(pos); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::set() | |
{ | |
std::fill(m_bits.begin(), m_bits.end(), ~Block(0)); | |
m_zero_unused_bits(); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::reset(size_type pos) | |
{ | |
assert(pos < m_num_bits); | |
#if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x | |
// CodeWarrior 8 generates incorrect code when the &=~ is compiled, | |
// use the |^ variation instead.. <grafik> | |
m_bits[block_index(pos)] |= bit_mask(pos); | |
m_bits[block_index(pos)] ^= bit_mask(pos); | |
#else | |
m_bits[block_index(pos)] &= ~bit_mask(pos); | |
#endif | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::reset() | |
{ | |
std::fill(m_bits.begin(), m_bits.end(), Block(0)); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::flip(size_type pos) | |
{ | |
assert(pos < m_num_bits); | |
m_bits[block_index(pos)] ^= bit_mask(pos); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator>& | |
dynamic_bitset<Block, Allocator>::flip() | |
{ | |
for (size_type i = 0; i < num_blocks(); ++i) | |
m_bits[i] = ~m_bits[i]; | |
m_zero_unused_bits(); | |
return *this; | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const | |
{ | |
return (m_bits[block_index(pos)] & bit_mask(pos)) != 0; | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>::test(size_type pos) const | |
{ | |
assert(pos < m_num_bits); | |
return m_unchecked_test(pos); | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>::any() const | |
{ | |
for (size_type i = 0; i < num_blocks(); ++i) | |
if (m_bits[i]) | |
return true; | |
return false; | |
} | |
template <typename Block, typename Allocator> | |
inline bool dynamic_bitset<Block, Allocator>::none() const | |
{ | |
return !any(); | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
dynamic_bitset<Block, Allocator>::operator~() const | |
{ | |
dynamic_bitset b(*this); | |
b.flip(); | |
return b; | |
} | |
template <typename Block, typename Allocator> | |
typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::count() const | |
{ | |
using detail::dynamic_bitset_impl::table_width; | |
using detail::dynamic_bitset_impl::access_by_bytes; | |
using detail::dynamic_bitset_impl::access_by_blocks; | |
using detail::dynamic_bitset_impl::value_to_type; | |
#if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3) | |
// NOTE: Explicit qualification of "bits_per_block" | |
// breaks compilation on gcc 4.3.3 | |
enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) }; | |
#else | |
// NOTE: Explicitly qualifying "bits_per_block" to workaround | |
// regressions of gcc 3.4.x | |
enum { no_padding = | |
dynamic_bitset<Block, Allocator>::bits_per_block | |
== CHAR_BIT * sizeof(Block) }; | |
#endif | |
enum { enough_table_width = table_width >= CHAR_BIT }; | |
enum { mode = (no_padding && enough_table_width) | |
? access_by_bytes | |
: access_by_blocks }; | |
return do_count(m_bits.begin(), num_blocks(), Block(0), | |
static_cast<value_to_type<(bool)mode> *>(0)); | |
} | |
//----------------------------------------------------------------------------- | |
// conversions | |
template <typename B, typename A, typename stringT> | |
void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, | |
bool dump_all) | |
{ | |
typedef typename stringT::traits_type Tr; | |
typedef typename stringT::value_type Ch; | |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale()); | |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); | |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); | |
// Note that this function may access (when | |
// dump_all == true) bits beyond position size() - 1 | |
typedef typename dynamic_bitset<B, A>::size_type size_type; | |
const size_type len = dump_all? | |
dynamic_bitset<B, A>::bits_per_block * b.num_blocks(): | |
b.size(); | |
s.assign (len, zero); | |
for (size_type i = 0; i < len; ++i) { | |
if (b.m_unchecked_test(i)) | |
Tr::assign(s[len - 1 - i], one); | |
} | |
} | |
// A comment similar to the one about the constructor from | |
// basic_string can be done here. Thanks to James Kanze for | |
// making me (Gennaro) realize this important separation of | |
// concerns issue, as well as many things about i18n. | |
// | |
template <typename Block, typename Allocator, typename stringT> | |
inline void | |
to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s) | |
{ | |
to_string_helper(b, s, false); | |
} | |
// Differently from to_string this function dumps out | |
// every bit of the internal representation (may be | |
// useful for debugging purposes) | |
// | |
template <typename B, typename A, typename stringT> | |
inline void | |
dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) | |
{ | |
to_string_helper(b, s, true /* =dump_all*/); | |
} | |
template <typename Block, typename Allocator, typename BlockOutputIterator> | |
inline void | |
to_block_range(const dynamic_bitset<Block, Allocator>& b, | |
BlockOutputIterator result) | |
{ | |
// note how this copies *all* bits, including the | |
// unused ones in the last block (which are zero) | |
std::copy(b.m_bits.begin(), b.m_bits.end(), result); | |
} | |
template <typename Block, typename Allocator> | |
unsigned long dynamic_bitset<Block, Allocator>:: | |
to_ulong() const | |
{ | |
if (m_num_bits == 0) | |
return 0; // convention | |
// Check for overflows. This may be a performance burden on very | |
// large bitsets but is required by the specification, sorry | |
if (find_next(ulong_width - 1) != npos) | |
throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow"); | |
// Ok, from now on we can be sure there's no "on" bit | |
// beyond the "allowed" positions | |
typedef unsigned long result_type; | |
const size_type max_size = | |
(std::min)(m_num_bits, static_cast<size_type>(ulong_width)); | |
const size_type last_block = block_index( max_size - 1 ); | |
assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width)); | |
result_type result = 0; | |
for (size_type i = 0; i <= last_block; ++i) { | |
const size_type offset = i * bits_per_block; | |
result |= (static_cast<result_type>(m_bits[i]) << offset); | |
} | |
return result; | |
} | |
template <typename Block, typename Allocator> | |
inline typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::size() const | |
{ | |
return m_num_bits; | |
} | |
template <typename Block, typename Allocator> | |
inline typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::num_blocks() const | |
{ | |
return m_bits.size(); | |
} | |
template <typename Block, typename Allocator> | |
inline typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::max_size() const | |
{ | |
// Semantics of vector<>::max_size() aren't very clear | |
// (see lib issue 197) and many library implementations | |
// simply return dummy values, _unrelated_ to the underlying | |
// allocator. | |
// | |
// Given these problems, I was tempted to not provide this | |
// function at all but the user could need it if he provides | |
// his own allocator. | |
// | |
const size_type m = detail::dynamic_bitset_impl:: | |
vector_max_size_workaround(m_bits); | |
return m <= (size_type(-1)/bits_per_block) ? | |
m * bits_per_block : | |
size_type(-1); | |
} | |
template <typename Block, typename Allocator> | |
inline bool dynamic_bitset<Block, Allocator>::empty() const | |
{ | |
return size() == 0; | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>:: | |
is_subset_of(const dynamic_bitset<Block, Allocator>& a) const | |
{ | |
assert(size() == a.size()); | |
for (size_type i = 0; i < num_blocks(); ++i) | |
if (m_bits[i] & ~a.m_bits[i]) | |
return false; | |
return true; | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>:: | |
is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const | |
{ | |
assert(size() == a.size()); | |
assert(num_blocks() == a.num_blocks()); | |
bool proper = false; | |
for (size_type i = 0; i < num_blocks(); ++i) { | |
const Block & bt = m_bits[i]; | |
const Block & ba = a.m_bits[i]; | |
if (bt & ~ba) | |
return false; // not a subset at all | |
if (ba & ~bt) | |
proper = true; | |
} | |
return proper; | |
} | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const | |
{ | |
size_type common_blocks = num_blocks() < b.num_blocks() | |
? num_blocks() : b.num_blocks(); | |
for(size_type i = 0; i < common_blocks; ++i) { | |
if(m_bits[i] & b.m_bits[i]) | |
return true; | |
} | |
return false; | |
} | |
// -------------------------------- | |
// lookup | |
// look for the first bit "on", starting | |
// from the block with index first_block | |
// | |
template <typename Block, typename Allocator> | |
typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const | |
{ | |
size_type i = first_block; | |
// skip null blocks | |
while (i < num_blocks() && m_bits[i] == 0) | |
++i; | |
if (i >= num_blocks()) | |
return npos; // not found | |
return i * bits_per_block + boost::lowest_bit(m_bits[i]); | |
} | |
template <typename Block, typename Allocator> | |
typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::find_first() const | |
{ | |
return m_do_find_from(0); | |
} | |
template <typename Block, typename Allocator> | |
typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::find_next(size_type pos) const | |
{ | |
const size_type sz = size(); | |
if (pos >= (sz-1) || sz == 0) | |
return npos; | |
++pos; | |
const size_type blk = block_index(pos); | |
const block_width_type ind = bit_index(pos); | |
// mask out bits before pos | |
const Block fore = m_bits[blk] & ( ~Block(0) << ind ); | |
return fore? | |
blk * bits_per_block + lowest_bit(fore) | |
: | |
m_do_find_from(blk + 1); | |
} | |
//----------------------------------------------------------------------------- | |
// comparison | |
template <typename Block, typename Allocator> | |
bool operator==(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
return (a.m_num_bits == b.m_num_bits) | |
&& (a.m_bits == b.m_bits); | |
} | |
template <typename Block, typename Allocator> | |
inline bool operator!=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
return !(a == b); | |
} | |
template <typename Block, typename Allocator> | |
bool operator<(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
assert(a.size() == b.size()); | |
typedef typename dynamic_bitset<Block, Allocator>::size_type size_type; | |
//if (a.size() == 0) | |
// return false; | |
// Since we are storing the most significant bit | |
// at pos == size() - 1, we need to do the comparisons in reverse. | |
// | |
for (size_type ii = a.num_blocks(); ii > 0; --ii) { | |
size_type i = ii-1; | |
if (a.m_bits[i] < b.m_bits[i]) | |
return true; | |
else if (a.m_bits[i] > b.m_bits[i]) | |
return false; | |
} | |
return false; | |
} | |
template <typename Block, typename Allocator> | |
inline bool operator<=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
return !(a > b); | |
} | |
template <typename Block, typename Allocator> | |
inline bool operator>(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
return b < a; | |
} | |
template <typename Block, typename Allocator> | |
inline bool operator>=(const dynamic_bitset<Block, Allocator>& a, | |
const dynamic_bitset<Block, Allocator>& b) | |
{ | |
return !(a < b); | |
} | |
//----------------------------------------------------------------------------- | |
// stream operations | |
#ifdef BOOST_OLD_IOSTREAMS | |
template < typename Block, typename Alloc> | |
std::ostream& | |
operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b) | |
{ | |
// NOTE: since this is aimed at "classic" iostreams, exception | |
// masks on the stream are not supported. The library that | |
// ships with gcc 2.95 has an exceptions() member function but | |
// nothing is actually implemented; not even the class ios::failure. | |
using namespace std; | |
const ios::iostate ok = ios::goodbit; | |
ios::iostate err = ok; | |
if (os.opfx()) { | |
//try | |
typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type; | |
const bitsetsize_type sz = b.size(); | |
std::streambuf * buf = os.rdbuf(); | |
size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0) | |
|| (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; | |
const char fill_char = os.fill(); | |
const ios::fmtflags adjustfield = os.flags() & ios::adjustfield; | |
// if needed fill at left; pad is decresed along the way | |
if (adjustfield != ios::left) { | |
for (; 0 < npad; --npad) | |
if (fill_char != buf->sputc(fill_char)) { | |
err |= ios::failbit; | |
break; | |
} | |
} | |
if (err == ok) { | |
// output the bitset | |
for (bitsetsize_type i = b.size(); 0 < i; --i) { | |
const char dig = b.test(i-1)? '1' : '0'; | |
if (EOF == buf->sputc(dig)) { | |
err |= ios::failbit; | |
break; | |
} | |
} | |
} | |
if (err == ok) { | |
// if needed fill at right | |
for (; 0 < npad; --npad) { | |
if (fill_char != buf->sputc(fill_char)) { | |
err |= ios::failbit; | |
break; | |
} | |
} | |
} | |
os.osfx(); | |
os.width(0); | |
} // if opfx | |
if(err != ok) | |
os.setstate(err); // assume this does NOT throw | |
return os; | |
} | |
#else | |
template <typename Ch, typename Tr, typename Block, typename Alloc> | |
std::basic_ostream<Ch, Tr>& | |
operator<<(std::basic_ostream<Ch, Tr>& os, | |
const dynamic_bitset<Block, Alloc>& b) | |
{ | |
using namespace std; | |
const ios_base::iostate ok = ios_base::goodbit; | |
ios_base::iostate err = ok; | |
typename basic_ostream<Ch, Tr>::sentry cerberos(os); | |
if (cerberos) { | |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc()); | |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); | |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); | |
try { | |
typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type; | |
typedef basic_streambuf<Ch, Tr> buffer_type; | |
buffer_type * buf = os.rdbuf(); | |
size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0) | |
|| (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); | |
const Ch fill_char = os.fill(); | |
const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield; | |
// if needed fill at left; pad is decresed along the way | |
if (adjustfield != ios_base::left) { | |
for (; 0 < npad; --npad) | |
if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) { | |
err |= ios_base::failbit; | |
break; | |
} | |
} | |
if (err == ok) { | |
// output the bitset | |
for (bitsetsize_type i = b.size(); 0 < i; --i) { | |
typename buffer_type::int_type | |
ret = buf->sputc(b.test(i-1)? one : zero); | |
if (Tr::eq_int_type(Tr::eof(), ret)) { | |
err |= ios_base::failbit; | |
break; | |
} | |
} | |
} | |
if (err == ok) { | |
// if needed fill at right | |
for (; 0 < npad; --npad) { | |
if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) { | |
err |= ios_base::failbit; | |
break; | |
} | |
} | |
} | |
os.width(0); | |
} catch (...) { // see std 27.6.1.1/4 | |
bool rethrow = false; | |
try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; } | |
if (rethrow) | |
throw; | |
} | |
} | |
if(err != ok) | |
os.setstate(err); // may throw exception | |
return os; | |
} | |
#endif | |
#ifdef BOOST_OLD_IOSTREAMS | |
// A sentry-like class that calls isfx in its destructor. | |
// "Necessary" because bit_appender::do_append may throw. | |
class pseudo_sentry { | |
std::istream & m_r; | |
const bool m_ok; | |
public: | |
explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { } | |
~pseudo_sentry() { m_r.isfx(); } | |
operator bool() const { return m_ok; } | |
}; | |
template <typename Block, typename Alloc> | |
std::istream& | |
operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b) | |
{ | |
// Extractor for classic IO streams (libstdc++ < 3.0) | |
// ----------------------------------------------------// | |
// It's assumed that the stream buffer functions, and | |
// the stream's setstate() _cannot_ throw. | |
typedef dynamic_bitset<Block, Alloc> bitset_type; | |
typedef typename bitset_type::size_type size_type; | |
std::ios::iostate err = std::ios::goodbit; | |
pseudo_sentry cerberos(is); // skips whitespaces | |
if(cerberos) { | |
b.clear(); | |
const std::streamsize w = is.width(); | |
const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size() | |
? w : b.max_size(); | |
typename bitset_type::bit_appender appender(b); | |
std::streambuf * buf = is.rdbuf(); | |
for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) { | |
if (c == EOF) { | |
err |= std::ios::eofbit; | |
break; | |
} | |
else if (char(c) != '0' && char(c) != '1') | |
break; // non digit character | |
else { | |
try { | |
appender.do_append(char(c) == '1'); | |
} | |
catch(...) { | |
is.setstate(std::ios::failbit); // assume this can't throw | |
throw; | |
} | |
} | |
} // for | |
} | |
is.width(0); | |
if (b.size() == 0) | |
err |= std::ios::failbit; | |
if (err != std::ios::goodbit) | |
is.setstate (err); // may throw | |
return is; | |
} | |
#else // BOOST_OLD_IOSTREAMS | |
template <typename Ch, typename Tr, typename Block, typename Alloc> | |
std::basic_istream<Ch, Tr>& | |
operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b) | |
{ | |
using namespace std; | |
typedef dynamic_bitset<Block, Alloc> bitset_type; | |
typedef typename bitset_type::size_type size_type; | |
const streamsize w = is.width(); | |
const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? | |
w : b.max_size(); | |
ios_base::iostate err = ios_base::goodbit; | |
typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces | |
if(cerberos) { | |
// in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004] | |
BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc()); | |
const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0'); | |
const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1'); | |
b.clear(); | |
try { | |
typename bitset_type::bit_appender appender(b); | |
basic_streambuf <Ch, Tr> * buf = is.rdbuf(); | |
typename Tr::int_type c = buf->sgetc(); | |
for( ; appender.get_count() < limit; c = buf->snextc() ) { | |
if (Tr::eq_int_type(Tr::eof(), c)) { | |
err |= ios_base::eofbit; | |
break; | |
} | |
else { | |
const Ch to_c = Tr::to_char_type(c); | |
const bool is_one = Tr::eq(to_c, one); | |
if (!is_one && !Tr::eq(to_c, zero)) | |
break; // non digit character | |
appender.do_append(is_one); | |
} | |
} // for | |
} | |
catch (...) { | |
// catches from stream buf, or from vector: | |
// | |
// bits_stored bits have been extracted and stored, and | |
// either no further character is extractable or we can't | |
// append to the underlying vector (out of memory) | |
bool rethrow = false; // see std 27.6.1.1/4 | |
try { is.setstate(ios_base::badbit); } | |
catch(...) { rethrow = true; } | |
if (rethrow) | |
throw; | |
} | |
} | |
is.width(0); | |
if (b.size() == 0 /*|| !cerberos*/) | |
err |= ios_base::failbit; | |
if (err != ios_base::goodbit) | |
is.setstate (err); // may throw | |
return is; | |
} | |
#endif | |
//----------------------------------------------------------------------------- | |
// bitset operations | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator&(const dynamic_bitset<Block, Allocator>& x, | |
const dynamic_bitset<Block, Allocator>& y) | |
{ | |
dynamic_bitset<Block, Allocator> b(x); | |
return b &= y; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator|(const dynamic_bitset<Block, Allocator>& x, | |
const dynamic_bitset<Block, Allocator>& y) | |
{ | |
dynamic_bitset<Block, Allocator> b(x); | |
return b |= y; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator^(const dynamic_bitset<Block, Allocator>& x, | |
const dynamic_bitset<Block, Allocator>& y) | |
{ | |
dynamic_bitset<Block, Allocator> b(x); | |
return b ^= y; | |
} | |
template <typename Block, typename Allocator> | |
dynamic_bitset<Block, Allocator> | |
operator-(const dynamic_bitset<Block, Allocator>& x, | |
const dynamic_bitset<Block, Allocator>& y) | |
{ | |
dynamic_bitset<Block, Allocator> b(x); | |
return b -= y; | |
} | |
//----------------------------------------------------------------------------- | |
// namespace scope swap | |
template<typename Block, typename Allocator> | |
inline void | |
swap(dynamic_bitset<Block, Allocator>& left, | |
dynamic_bitset<Block, Allocator>& right) // no throw | |
{ | |
left.swap(right); | |
} | |
//----------------------------------------------------------------------------- | |
// private (on conforming compilers) member functions | |
template <typename Block, typename Allocator> | |
inline typename dynamic_bitset<Block, Allocator>::size_type | |
dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits) | |
{ | |
return num_bits / bits_per_block | |
+ static_cast<int>( num_bits % bits_per_block != 0 ); | |
} | |
// gives a reference to the highest block | |
// | |
template <typename Block, typename Allocator> | |
inline Block& dynamic_bitset<Block, Allocator>::m_highest_block() | |
{ | |
return const_cast<Block &> | |
(static_cast<const dynamic_bitset *>(this)->m_highest_block()); | |
} | |
// gives a const-reference to the highest block | |
// | |
template <typename Block, typename Allocator> | |
inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const | |
{ | |
assert(size() > 0 && num_blocks() > 0); | |
return m_bits.back(); | |
} | |
// If size() is not a multiple of bits_per_block | |
// then not all the bits in the last block are used. | |
// This function resets the unused bits (convenient | |
// for the implementation of many member functions) | |
// | |
template <typename Block, typename Allocator> | |
inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits() | |
{ | |
assert (num_blocks() == calc_num_blocks(m_num_bits)); | |
// if != 0 this is the number of bits used in the last block | |
const block_width_type extra_bits = count_extra_bits(); | |
if (extra_bits != 0) | |
m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits); | |
} | |
// check class invariants | |
template <typename Block, typename Allocator> | |
bool dynamic_bitset<Block, Allocator>::m_check_invariants() const | |
{ | |
const block_width_type extra_bits = count_extra_bits(); | |
if (extra_bits > 0) { | |
block_type const mask = (~static_cast<Block>(0) << extra_bits); | |
if ((m_highest_block() & mask) != 0) | |
return false; | |
} | |
if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size())) | |
return false; | |
return true; | |
} | |
} // namespace boost | |
#undef BOOST_BITSET_CHAR | |
#endif // include guard | |