Boost-Graph
view release on metacpan or search on metacpan
include/boost/dynamic_bitset/dynamic_bitset.hpp view on Meta::CPAN
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<int>(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,
const Allocator& alloc)
{
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); // gps
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; // [gps]
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);
}
}
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; // [gps] to be renamed
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. Everything works just as if
// dynamic_bitset<> had an append_at_right() function (which
// threw, in case, the same exceptions as push_back) except
// that the function is actually called bit_appender::do_append().
//
dynamic_bitset & bs;
size_type n;
Block mask;
Block * current;
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) {
include/boost/dynamic_bitset/dynamic_bitset.hpp view on Meta::CPAN
dynamic_bitset<Block, Allocator>::count() const
{
size_type sum = 0;
for (size_type i = 0; i != this->m_num_bits; ++i)
if (test(i))
++sum;
return sum;
}
The actual algorithm uses a lookup table.
The basic idea of the method is to pick up X bits at a time
from the internal array of blocks and consider those bits as
the binary representation of a number N. Then, to use a table
of 1<<X elements where table[N] is the number of '1' digits
in the binary representation of N (i.e. in our X bits).
In this implementation X is 8 (but can be easily changed: you
just have to modify the definition of table_width and shrink/enlarge
the table accordingly - it could be useful, for instance, to expand
the table to 512 elements on an implementation with 9-bit bytes) and
the internal array of blocks is seen, if possible, as an array of bytes.
In practice the "reinterpretation" as array of bytes is possible if and
only if X >= CHAR_BIT and Block has no padding bits (that would be counted
together with the "real ones" if we saw the array as array of bytes).
Otherwise we simply 'extract' X bits at a time from each Block.
*/
template <typename Block, typename Allocator>
typename dynamic_bitset<Block, Allocator>::size_type
dynamic_bitset<Block, Allocator>::count() const
{
using namespace detail::dynamic_bitset_count_impl;
const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);
const bool enough_table_width = table_width >= CHAR_BIT;
typedef mode_to_type< (no_padding && enough_table_width ?
access_by_bytes : access_by_blocks) > m;
return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(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> // G.P.S.
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) // G.P.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); // [gps]
}
template <typename Block, typename Allocator>
unsigned long dynamic_bitset<Block, Allocator>::
to_ulong() const
{
include/boost/dynamic_bitset/dynamic_bitset.hpp view on Meta::CPAN
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; // gps
break;
}
}
if (err == ok) {
// output the bitset
for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
const char dig = b.test(i-1)? '1' : '0';
if (EOF == buf->sputc(dig)) { // ok?? gps
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 - gps
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; // G.P.S.
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(); //- G.P.S.
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; // G.P.S.
break;
}
}
if (err == ok) {
// output the bitset
for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
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
include/boost/dynamic_bitset/dynamic_bitset.hpp view on Meta::CPAN
b.clear();
const std::streamsize w = is.width();
const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
? 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; // G.P.S.
break;
}
else if (char(c) != '0' && char(c) != '1')
break; // non digit character
else {
try {
//throw std::bad_alloc(); // gps
appender.do_append(char(c) == '1');
}
catch(...) {
is.setstate(std::ios::failbit); // assume this can't throw
throw;
}
}
} // for
}
is.width(0); // gps
if (b.size() == 0)
err |= std::ios::failbit;
if (err != std::ios::goodbit) // gps
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()? // gps
w : b.max_size();
ios_base::iostate err = ios_base::goodbit; // gps
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(); // G.P.S.
for( ; appender.get_count() < limit; c = buf->snextc() ) {
if (Tr::eq_int_type(Tr::eof(), c)) {
err |= ios_base::eofbit; // G.P.S.
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) gps
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); // gps
if (b.size() == 0 /*|| !cerberos*/)
err |= ios_base::failbit;
if (err != ios_base::goodbit) // gps
is.setstate (err); // may throw
return is;
}
#endif
//-----------------------------------------------------------------------------
// bitset operations
( run in 0.926 second using v1.01-cache-2.11-cpan-39bf76dae61 )