annotate DEPENDENCIES/generic/include/boost/dynamic_bitset/dynamic_bitset.hpp @ 133:4acb5d8d80b6 tip

Don't fail environmental check if README.md exists (but .txt and no-suffix don't)
author Chris Cannam
date Tue, 30 Jul 2019 12:25:44 +0100
parents c530137014c0
children
rev   line source
Chris@16 1 // -----------------------------------------------------------
Chris@16 2 //
Chris@16 3 // Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
Chris@16 4 // Copyright (c) 2003-2006, 2008 Gennaro Prota
Chris@101 5 // Copyright (c) 2014 Ahmed Charles
Chris@101 6 //
Chris@101 7 // Copyright (c) 2014 Glen Joseph Fernandes
Chris@101 8 // glenfe at live dot com
Chris@101 9 // Copyright (c) 2014 Riccardo Marcangelo
Chris@16 10 //
Chris@16 11 // Distributed under the Boost Software License, Version 1.0.
Chris@16 12 // (See accompanying file LICENSE_1_0.txt or copy at
Chris@16 13 // http://www.boost.org/LICENSE_1_0.txt)
Chris@16 14 //
Chris@16 15 // -----------------------------------------------------------
Chris@16 16
Chris@16 17 #ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
Chris@16 18 #define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP
Chris@16 19
Chris@16 20 #include <assert.h>
Chris@16 21 #include <string>
Chris@16 22 #include <stdexcept>
Chris@16 23 #include <algorithm>
Chris@16 24 #include <vector>
Chris@16 25 #include <climits> // for CHAR_BIT
Chris@16 26
Chris@16 27 #include "boost/dynamic_bitset/config.hpp"
Chris@16 28
Chris@16 29 #ifndef BOOST_NO_STD_LOCALE
Chris@16 30 # include <locale>
Chris@16 31 #endif
Chris@16 32
Chris@16 33 #if defined(BOOST_OLD_IOSTREAMS)
Chris@16 34 # include <iostream.h>
Chris@16 35 # include <ctype.h> // for isspace
Chris@16 36 #else
Chris@16 37 # include <istream>
Chris@16 38 # include <ostream>
Chris@16 39 #endif
Chris@16 40
Chris@16 41 #include "boost/dynamic_bitset_fwd.hpp"
Chris@16 42 #include "boost/detail/dynamic_bitset.hpp"
Chris@16 43 #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
Chris@101 44 #include "boost/move/move.hpp"
Chris@16 45 #include "boost/limits.hpp"
Chris@16 46 #include "boost/pending/lowest_bit.hpp"
Chris@101 47 #include "boost/static_assert.hpp"
Chris@101 48 #include "boost/utility/addressof.hpp"
Chris@101 49 #include "boost/detail/no_exceptions_support.hpp"
Chris@101 50 #include "boost/throw_exception.hpp"
Chris@16 51
Chris@16 52
Chris@16 53 namespace boost {
Chris@16 54
Chris@16 55 template <typename Block, typename Allocator>
Chris@16 56 class dynamic_bitset
Chris@16 57 {
Chris@101 58 // Portability note: member function templates are defined inside
Chris@101 59 // this class definition to avoid problems with VC++. Similarly,
Chris@101 60 // with the member functions of nested classes.
Chris@101 61 //
Chris@101 62 // [October 2008: the note above is mostly historical; new versions
Chris@101 63 // of VC++ are likely able to digest a more drinking form of the
Chris@101 64 // code; but changing it now is probably not worth the risks...]
Chris@16 65
Chris@101 66 BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
Chris@101 67 typedef std::vector<Block, Allocator> buffer_type;
Chris@16 68
Chris@16 69 public:
Chris@16 70 typedef Block block_type;
Chris@16 71 typedef Allocator allocator_type;
Chris@16 72 typedef std::size_t size_type;
Chris@101 73 typedef typename buffer_type::size_type block_width_type;
Chris@16 74
Chris@16 75 BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
Chris@16 76 BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
Chris@16 77
Chris@16 78
Chris@16 79 public:
Chris@16 80
Chris@16 81 // A proxy class to simulate lvalues of bit type.
Chris@16 82 //
Chris@16 83 class reference
Chris@16 84 {
Chris@16 85 friend class dynamic_bitset<Block, Allocator>;
Chris@16 86
Chris@16 87
Chris@16 88 // the one and only non-copy ctor
Chris@16 89 reference(block_type & b, block_type pos)
Chris@16 90 :m_block(b),
Chris@16 91 m_mask( (assert(pos < bits_per_block),
Chris@16 92 block_type(1) << pos )
Chris@16 93 )
Chris@16 94 { }
Chris@16 95
Chris@16 96 void operator&(); // left undefined
Chris@16 97
Chris@16 98 public:
Chris@16 99
Chris@16 100 // copy constructor: compiler generated
Chris@16 101
Chris@16 102 operator bool() const { return (m_block & m_mask) != 0; }
Chris@16 103 bool operator~() const { return (m_block & m_mask) == 0; }
Chris@16 104
Chris@16 105 reference& flip() { do_flip(); return *this; }
Chris@16 106
Chris@16 107 reference& operator=(bool x) { do_assign(x); return *this; } // for b[i] = x
Chris@16 108 reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]
Chris@16 109
Chris@16 110 reference& operator|=(bool x) { if (x) do_set(); return *this; }
Chris@16 111 reference& operator&=(bool x) { if (!x) do_reset(); return *this; }
Chris@16 112 reference& operator^=(bool x) { if (x) do_flip(); return *this; }
Chris@16 113 reference& operator-=(bool x) { if (x) do_reset(); return *this; }
Chris@16 114
Chris@16 115 private:
Chris@16 116 block_type & m_block;
Chris@16 117 const block_type m_mask;
Chris@16 118
Chris@16 119 void do_set() { m_block |= m_mask; }
Chris@16 120 void do_reset() { m_block &= ~m_mask; }
Chris@16 121 void do_flip() { m_block ^= m_mask; }
Chris@16 122 void do_assign(bool x) { x? do_set() : do_reset(); }
Chris@16 123 };
Chris@16 124
Chris@16 125 typedef bool const_reference;
Chris@16 126
Chris@16 127 // constructors, etc.
Chris@16 128 explicit
Chris@16 129 dynamic_bitset(const Allocator& alloc = Allocator());
Chris@16 130
Chris@16 131 explicit
Chris@16 132 dynamic_bitset(size_type num_bits, unsigned long value = 0,
Chris@16 133 const Allocator& alloc = Allocator());
Chris@16 134
Chris@16 135
Chris@16 136 // WARNING: you should avoid using this constructor.
Chris@16 137 //
Chris@16 138 // A conversion from string is, in most cases, formatting,
Chris@16 139 // and should be performed by using operator>>.
Chris@16 140 //
Chris@16 141 // NOTE:
Chris@16 142 // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.
Chris@16 143 // g++ 3.2 requires them and probably the standard will - see core issue 325
Chris@16 144 // NOTE 2:
Chris@16 145 // split into two constructors because of bugs in MSVC 6.0sp5 with STLport
Chris@16 146
Chris@16 147 template <typename CharT, typename Traits, typename Alloc>
Chris@16 148 dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16 149 typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
Chris@16 150 typename std::basic_string<CharT, Traits, Alloc>::size_type n,
Chris@16 151 size_type num_bits = npos,
Chris@16 152 const Allocator& alloc = Allocator())
Chris@16 153
Chris@16 154 :m_bits(alloc),
Chris@16 155 m_num_bits(0)
Chris@16 156 {
Chris@16 157 init_from_string(s, pos, n, num_bits);
Chris@16 158 }
Chris@16 159
Chris@16 160 template <typename CharT, typename Traits, typename Alloc>
Chris@16 161 explicit
Chris@16 162 dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16 163 typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)
Chris@16 164
Chris@16 165 :m_bits(Allocator()),
Chris@16 166 m_num_bits(0)
Chris@16 167 {
Chris@16 168 init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),
Chris@16 169 npos);
Chris@16 170 }
Chris@16 171
Chris@16 172 // The first bit in *first is the least significant bit, and the
Chris@16 173 // last bit in the block just before *last is the most significant bit.
Chris@16 174 template <typename BlockInputIterator>
Chris@16 175 dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
Chris@16 176 const Allocator& alloc = Allocator())
Chris@16 177
Chris@16 178 :m_bits(alloc),
Chris@16 179 m_num_bits(0)
Chris@16 180 {
Chris@16 181 using boost::detail::dynamic_bitset_impl::value_to_type;
Chris@16 182 using boost::detail::dynamic_bitset_impl::is_numeric;
Chris@16 183
Chris@16 184 const value_to_type<
Chris@16 185 is_numeric<BlockInputIterator>::value> selector;
Chris@16 186
Chris@16 187 dispatch_init(first, last, selector);
Chris@16 188 }
Chris@16 189
Chris@16 190 template <typename T>
Chris@16 191 void dispatch_init(T num_bits, unsigned long value,
Chris@16 192 detail::dynamic_bitset_impl::value_to_type<true>)
Chris@16 193 {
Chris@16 194 init_from_unsigned_long(static_cast<size_type>(num_bits), value);
Chris@16 195 }
Chris@16 196
Chris@16 197 template <typename T>
Chris@16 198 void dispatch_init(T first, T last,
Chris@16 199 detail::dynamic_bitset_impl::value_to_type<false>)
Chris@16 200 {
Chris@16 201 init_from_block_range(first, last);
Chris@16 202 }
Chris@16 203
Chris@16 204 template <typename BlockIter>
Chris@16 205 void init_from_block_range(BlockIter first, BlockIter last)
Chris@16 206 {
Chris@16 207 assert(m_bits.size() == 0);
Chris@16 208 m_bits.insert(m_bits.end(), first, last);
Chris@16 209 m_num_bits = m_bits.size() * bits_per_block;
Chris@16 210 }
Chris@16 211
Chris@16 212 // copy constructor
Chris@16 213 dynamic_bitset(const dynamic_bitset& b);
Chris@16 214
Chris@16 215 ~dynamic_bitset();
Chris@16 216
Chris@16 217 void swap(dynamic_bitset& b);
Chris@16 218 dynamic_bitset& operator=(const dynamic_bitset& b);
Chris@16 219
Chris@101 220 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101 221 dynamic_bitset(dynamic_bitset&& src);
Chris@101 222 dynamic_bitset& operator=(dynamic_bitset&& src);
Chris@101 223 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101 224
Chris@16 225 allocator_type get_allocator() const;
Chris@16 226
Chris@16 227 // size changing operations
Chris@16 228 void resize(size_type num_bits, bool value = false);
Chris@16 229 void clear();
Chris@16 230 void push_back(bool bit);
Chris@101 231 void pop_back();
Chris@16 232 void append(Block block);
Chris@16 233
Chris@16 234 template <typename BlockInputIterator>
Chris@16 235 void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
Chris@16 236 {
Chris@16 237 std::vector<Block, Allocator> v(first, last);
Chris@16 238 m_append(v.begin(), v.end(), std::random_access_iterator_tag());
Chris@16 239 }
Chris@16 240 template <typename BlockInputIterator>
Chris@16 241 void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)
Chris@16 242 {
Chris@16 243 assert(first != last);
Chris@16 244 block_width_type r = count_extra_bits();
Chris@16 245 std::size_t d = boost::detail::distance(first, last);
Chris@16 246 m_bits.reserve(num_blocks() + d);
Chris@16 247 if (r == 0) {
Chris@16 248 for( ; first != last; ++first)
Chris@16 249 m_bits.push_back(*first); // could use vector<>::insert()
Chris@16 250 }
Chris@16 251 else {
Chris@16 252 m_highest_block() |= (*first << r);
Chris@16 253 do {
Chris@16 254 Block b = *first >> (bits_per_block - r);
Chris@16 255 ++first;
Chris@16 256 m_bits.push_back(b | (first==last? 0 : *first << r));
Chris@16 257 } while (first != last);
Chris@16 258 }
Chris@16 259 m_num_bits += bits_per_block * d;
Chris@16 260 }
Chris@16 261 template <typename BlockInputIterator>
Chris@16 262 void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee
Chris@16 263 {
Chris@16 264 if (first != last) {
Chris@16 265 typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;
Chris@16 266 m_append(first, last, cat);
Chris@16 267 }
Chris@16 268 }
Chris@16 269
Chris@16 270
Chris@16 271 // bitset operations
Chris@16 272 dynamic_bitset& operator&=(const dynamic_bitset& b);
Chris@16 273 dynamic_bitset& operator|=(const dynamic_bitset& b);
Chris@16 274 dynamic_bitset& operator^=(const dynamic_bitset& b);
Chris@16 275 dynamic_bitset& operator-=(const dynamic_bitset& b);
Chris@16 276 dynamic_bitset& operator<<=(size_type n);
Chris@16 277 dynamic_bitset& operator>>=(size_type n);
Chris@16 278 dynamic_bitset operator<<(size_type n) const;
Chris@16 279 dynamic_bitset operator>>(size_type n) const;
Chris@16 280
Chris@16 281 // basic bit operations
Chris@16 282 dynamic_bitset& set(size_type n, bool val = true);
Chris@16 283 dynamic_bitset& set();
Chris@16 284 dynamic_bitset& reset(size_type n);
Chris@16 285 dynamic_bitset& reset();
Chris@16 286 dynamic_bitset& flip(size_type n);
Chris@16 287 dynamic_bitset& flip();
Chris@16 288 bool test(size_type n) const;
Chris@101 289 bool test_set(size_type n, bool val = true);
Chris@101 290 bool all() const;
Chris@16 291 bool any() const;
Chris@16 292 bool none() const;
Chris@16 293 dynamic_bitset operator~() const;
Chris@101 294 size_type count() const BOOST_NOEXCEPT;
Chris@16 295
Chris@16 296 // subscript
Chris@16 297 reference operator[](size_type pos) {
Chris@16 298 return reference(m_bits[block_index(pos)], bit_index(pos));
Chris@16 299 }
Chris@16 300 bool operator[](size_type pos) const { return test(pos); }
Chris@16 301
Chris@16 302 unsigned long to_ulong() const;
Chris@16 303
Chris@101 304 size_type size() const BOOST_NOEXCEPT;
Chris@101 305 size_type num_blocks() const BOOST_NOEXCEPT;
Chris@101 306 size_type max_size() const BOOST_NOEXCEPT;
Chris@101 307 bool empty() const BOOST_NOEXCEPT;
Chris@16 308
Chris@16 309 bool is_subset_of(const dynamic_bitset& a) const;
Chris@16 310 bool is_proper_subset_of(const dynamic_bitset& a) const;
Chris@16 311 bool intersects(const dynamic_bitset & a) const;
Chris@16 312
Chris@16 313 // lookup
Chris@16 314 size_type find_first() const;
Chris@16 315 size_type find_next(size_type pos) const;
Chris@16 316
Chris@16 317
Chris@16 318 #if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS
Chris@16 319 // lexicographical comparison
Chris@16 320 template <typename B, typename A>
Chris@16 321 friend bool operator==(const dynamic_bitset<B, A>& a,
Chris@16 322 const dynamic_bitset<B, A>& b);
Chris@16 323
Chris@16 324 template <typename B, typename A>
Chris@16 325 friend bool operator<(const dynamic_bitset<B, A>& a,
Chris@16 326 const dynamic_bitset<B, A>& b);
Chris@16 327
Chris@16 328
Chris@16 329 template <typename B, typename A, typename BlockOutputIterator>
Chris@16 330 friend void to_block_range(const dynamic_bitset<B, A>& b,
Chris@16 331 BlockOutputIterator result);
Chris@16 332
Chris@16 333 template <typename BlockIterator, typename B, typename A>
Chris@16 334 friend void from_block_range(BlockIterator first, BlockIterator last,
Chris@16 335 dynamic_bitset<B, A>& result);
Chris@16 336
Chris@16 337
Chris@16 338 template <typename CharT, typename Traits, typename B, typename A>
Chris@16 339 friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
Chris@16 340 dynamic_bitset<B, A>& b);
Chris@16 341
Chris@16 342 template <typename B, typename A, typename stringT>
Chris@16 343 friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
Chris@16 344
Chris@16 345
Chris@16 346 #endif
Chris@16 347
Chris@16 348
Chris@16 349 private:
Chris@16 350 BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
Chris@16 351
Chris@16 352 void m_zero_unused_bits();
Chris@16 353 bool m_check_invariants() const;
Chris@16 354
Chris@16 355 size_type m_do_find_from(size_type first_block) const;
Chris@16 356
Chris@101 357 block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); }
Chris@101 358 static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
Chris@101 359 static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
Chris@101 360 static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
Chris@16 361
Chris@16 362 template <typename CharT, typename Traits, typename Alloc>
Chris@16 363 void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
Chris@16 364 typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
Chris@16 365 typename std::basic_string<CharT, Traits, Alloc>::size_type n,
Chris@16 366 size_type num_bits)
Chris@16 367 {
Chris@16 368 assert(pos <= s.size());
Chris@16 369
Chris@16 370 typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
Chris@16 371 typedef typename StrT::traits_type Tr;
Chris@16 372
Chris@16 373 const typename StrT::size_type rlen = (std::min)(n, s.size() - pos);
Chris@16 374 const size_type sz = ( num_bits != npos? num_bits : rlen);
Chris@16 375 m_bits.resize(calc_num_blocks(sz));
Chris@16 376 m_num_bits = sz;
Chris@16 377
Chris@16 378
Chris@16 379 BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
Chris@16 380 const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16 381
Chris@16 382 const size_type m = num_bits < rlen ? num_bits : rlen;
Chris@16 383 typename StrT::size_type i = 0;
Chris@16 384 for( ; i < m; ++i) {
Chris@16 385
Chris@16 386 const CharT c = s[(pos + m - 1) - i];
Chris@16 387
Chris@16 388 assert( Tr::eq(c, one)
Chris@16 389 || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
Chris@16 390
Chris@16 391 if (Tr::eq(c, one))
Chris@16 392 set(i);
Chris@16 393
Chris@16 394 }
Chris@16 395
Chris@16 396 }
Chris@16 397
Chris@16 398 void init_from_unsigned_long(size_type num_bits,
Chris@16 399 unsigned long value/*,
Chris@16 400 const Allocator& alloc*/)
Chris@16 401 {
Chris@16 402
Chris@16 403 assert(m_bits.size() == 0);
Chris@16 404
Chris@16 405 m_bits.resize(calc_num_blocks(num_bits));
Chris@16 406 m_num_bits = num_bits;
Chris@16 407
Chris@16 408 typedef unsigned long num_type;
Chris@16 409 typedef boost::detail::dynamic_bitset_impl
Chris@16 410 ::shifter<num_type, bits_per_block, ulong_width> shifter;
Chris@16 411
Chris@16 412 //if (num_bits == 0)
Chris@16 413 // return;
Chris@16 414
Chris@16 415 // zero out all bits at pos >= num_bits, if any;
Chris@16 416 // note that: num_bits == 0 implies value == 0
Chris@16 417 if (num_bits < static_cast<size_type>(ulong_width)) {
Chris@16 418 const num_type mask = (num_type(1) << num_bits) - 1;
Chris@16 419 value &= mask;
Chris@16 420 }
Chris@16 421
Chris@16 422 typename buffer_type::iterator it = m_bits.begin();
Chris@16 423 for( ; value; shifter::left_shift(value), ++it) {
Chris@16 424 *it = static_cast<block_type>(value);
Chris@16 425 }
Chris@16 426
Chris@16 427 }
Chris@16 428
Chris@16 429
Chris@16 430
Chris@16 431 BOOST_DYNAMIC_BITSET_PRIVATE:
Chris@16 432
Chris@16 433 bool m_unchecked_test(size_type pos) const;
Chris@16 434 static size_type calc_num_blocks(size_type num_bits);
Chris@16 435
Chris@16 436 Block& m_highest_block();
Chris@16 437 const Block& m_highest_block() const;
Chris@16 438
Chris@16 439 buffer_type m_bits;
Chris@16 440 size_type m_num_bits;
Chris@16 441
Chris@16 442
Chris@16 443 class bit_appender;
Chris@16 444 friend class bit_appender;
Chris@16 445 class bit_appender {
Chris@16 446 // helper for stream >>
Chris@16 447 // Supplies to the lack of an efficient append at the less
Chris@16 448 // significant end: bits are actually appended "at left" but
Chris@16 449 // rearranged in the destructor. From the perspective of
Chris@16 450 // client code everything works *as if* dynamic_bitset<> had
Chris@16 451 // an append_at_right() function (eventually throwing the same
Chris@16 452 // exceptions as push_back) except that the function is in fact
Chris@16 453 // called bit_appender::do_append().
Chris@16 454 //
Chris@16 455 dynamic_bitset & bs;
Chris@16 456 size_type n;
Chris@16 457 Block mask;
Chris@16 458 Block * current;
Chris@16 459
Chris@16 460 // not implemented
Chris@16 461 bit_appender(const bit_appender &);
Chris@16 462 bit_appender & operator=(const bit_appender &);
Chris@16 463
Chris@16 464 public:
Chris@16 465 bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
Chris@16 466 ~bit_appender() {
Chris@16 467 // reverse the order of blocks, shift
Chris@16 468 // if needed, and then resize
Chris@16 469 //
Chris@16 470 std::reverse(bs.m_bits.begin(), bs.m_bits.end());
Chris@16 471 const block_width_type offs = bit_index(n);
Chris@16 472 if (offs)
Chris@16 473 bs >>= (bits_per_block - offs);
Chris@16 474 bs.resize(n); // doesn't enlarge, so can't throw
Chris@16 475 assert(bs.m_check_invariants());
Chris@16 476 }
Chris@16 477 inline void do_append(bool value) {
Chris@16 478
Chris@16 479 if (mask == 0) {
Chris@16 480 bs.append(Block(0));
Chris@16 481 current = &bs.m_highest_block();
Chris@16 482 mask = Block(1) << (bits_per_block - 1);
Chris@16 483 }
Chris@16 484
Chris@16 485 if(value)
Chris@16 486 *current |= mask;
Chris@16 487
Chris@16 488 mask /= 2;
Chris@16 489 ++n;
Chris@16 490 }
Chris@16 491 size_type get_count() const { return n; }
Chris@16 492 };
Chris@16 493
Chris@16 494 };
Chris@16 495
Chris@16 496 #if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION
Chris@16 497
Chris@16 498 template <typename Block, typename Allocator>
Chris@16 499 const typename dynamic_bitset<Block, Allocator>::block_width_type
Chris@16 500 dynamic_bitset<Block, Allocator>::bits_per_block;
Chris@16 501
Chris@16 502 template <typename Block, typename Allocator>
Chris@16 503 const typename dynamic_bitset<Block, Allocator>::size_type
Chris@16 504 dynamic_bitset<Block, Allocator>::npos;
Chris@16 505
Chris@16 506 template <typename Block, typename Allocator>
Chris@16 507 const typename dynamic_bitset<Block, Allocator>::block_width_type
Chris@16 508 dynamic_bitset<Block, Allocator>::ulong_width;
Chris@16 509
Chris@16 510 #endif
Chris@16 511
Chris@16 512 // Global Functions:
Chris@16 513
Chris@16 514 // comparison
Chris@16 515 template <typename Block, typename Allocator>
Chris@16 516 bool operator!=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 517 const dynamic_bitset<Block, Allocator>& b);
Chris@16 518
Chris@16 519 template <typename Block, typename Allocator>
Chris@16 520 bool operator<=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 521 const dynamic_bitset<Block, Allocator>& b);
Chris@16 522
Chris@16 523 template <typename Block, typename Allocator>
Chris@16 524 bool operator>(const dynamic_bitset<Block, Allocator>& a,
Chris@16 525 const dynamic_bitset<Block, Allocator>& b);
Chris@16 526
Chris@16 527 template <typename Block, typename Allocator>
Chris@16 528 bool operator>=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 529 const dynamic_bitset<Block, Allocator>& b);
Chris@16 530
Chris@16 531 // stream operators
Chris@16 532 #ifdef BOOST_OLD_IOSTREAMS
Chris@16 533 template <typename Block, typename Allocator>
Chris@16 534 std::ostream& operator<<(std::ostream& os,
Chris@16 535 const dynamic_bitset<Block, Allocator>& b);
Chris@16 536
Chris@16 537 template <typename Block, typename Allocator>
Chris@16 538 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
Chris@16 539 #else
Chris@16 540 template <typename CharT, typename Traits, typename Block, typename Allocator>
Chris@16 541 std::basic_ostream<CharT, Traits>&
Chris@16 542 operator<<(std::basic_ostream<CharT, Traits>& os,
Chris@16 543 const dynamic_bitset<Block, Allocator>& b);
Chris@16 544
Chris@16 545 template <typename CharT, typename Traits, typename Block, typename Allocator>
Chris@16 546 std::basic_istream<CharT, Traits>&
Chris@16 547 operator>>(std::basic_istream<CharT, Traits>& is,
Chris@16 548 dynamic_bitset<Block, Allocator>& b);
Chris@16 549 #endif
Chris@16 550
Chris@16 551 // bitset operations
Chris@16 552 template <typename Block, typename Allocator>
Chris@16 553 dynamic_bitset<Block, Allocator>
Chris@16 554 operator&(const dynamic_bitset<Block, Allocator>& b1,
Chris@16 555 const dynamic_bitset<Block, Allocator>& b2);
Chris@16 556
Chris@16 557 template <typename Block, typename Allocator>
Chris@16 558 dynamic_bitset<Block, Allocator>
Chris@16 559 operator|(const dynamic_bitset<Block, Allocator>& b1,
Chris@16 560 const dynamic_bitset<Block, Allocator>& b2);
Chris@16 561
Chris@16 562 template <typename Block, typename Allocator>
Chris@16 563 dynamic_bitset<Block, Allocator>
Chris@16 564 operator^(const dynamic_bitset<Block, Allocator>& b1,
Chris@16 565 const dynamic_bitset<Block, Allocator>& b2);
Chris@16 566
Chris@16 567 template <typename Block, typename Allocator>
Chris@16 568 dynamic_bitset<Block, Allocator>
Chris@16 569 operator-(const dynamic_bitset<Block, Allocator>& b1,
Chris@16 570 const dynamic_bitset<Block, Allocator>& b2);
Chris@16 571
Chris@16 572 // namespace scope swap
Chris@16 573 template<typename Block, typename Allocator>
Chris@16 574 void swap(dynamic_bitset<Block, Allocator>& b1,
Chris@16 575 dynamic_bitset<Block, Allocator>& b2);
Chris@16 576
Chris@16 577
Chris@16 578 template <typename Block, typename Allocator, typename stringT>
Chris@16 579 void
Chris@16 580 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s);
Chris@16 581
Chris@16 582 template <typename Block, typename Allocator, typename BlockOutputIterator>
Chris@16 583 void
Chris@16 584 to_block_range(const dynamic_bitset<Block, Allocator>& b,
Chris@16 585 BlockOutputIterator result);
Chris@16 586
Chris@16 587
Chris@16 588 template <typename BlockIterator, typename B, typename A>
Chris@16 589 inline void
Chris@16 590 from_block_range(BlockIterator first, BlockIterator last,
Chris@16 591 dynamic_bitset<B, A>& result)
Chris@16 592 {
Chris@16 593 // PRE: distance(first, last) <= numblocks()
Chris@16 594 std::copy (first, last, result.m_bits.begin());
Chris@16 595 }
Chris@16 596
Chris@16 597 //=============================================================================
Chris@16 598 // dynamic_bitset implementation
Chris@16 599
Chris@16 600
Chris@16 601 //-----------------------------------------------------------------------------
Chris@16 602 // constructors, etc.
Chris@16 603
Chris@16 604 template <typename Block, typename Allocator>
Chris@16 605 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
Chris@16 606 : m_bits(alloc), m_num_bits(0)
Chris@16 607 {
Chris@16 608
Chris@16 609 }
Chris@16 610
Chris@16 611 template <typename Block, typename Allocator>
Chris@16 612 dynamic_bitset<Block, Allocator>::
Chris@16 613 dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
Chris@16 614 : m_bits(alloc),
Chris@16 615 m_num_bits(0)
Chris@16 616 {
Chris@16 617 init_from_unsigned_long(num_bits, value);
Chris@16 618 }
Chris@16 619
Chris@16 620 // copy constructor
Chris@16 621 template <typename Block, typename Allocator>
Chris@16 622 inline dynamic_bitset<Block, Allocator>::
Chris@16 623 dynamic_bitset(const dynamic_bitset& b)
Chris@16 624 : m_bits(b.m_bits), m_num_bits(b.m_num_bits)
Chris@16 625 {
Chris@16 626
Chris@16 627 }
Chris@16 628
Chris@16 629 template <typename Block, typename Allocator>
Chris@16 630 inline dynamic_bitset<Block, Allocator>::
Chris@16 631 ~dynamic_bitset()
Chris@16 632 {
Chris@16 633 assert(m_check_invariants());
Chris@16 634 }
Chris@16 635
Chris@16 636 template <typename Block, typename Allocator>
Chris@16 637 inline void dynamic_bitset<Block, Allocator>::
Chris@16 638 swap(dynamic_bitset<Block, Allocator>& b) // no throw
Chris@16 639 {
Chris@16 640 std::swap(m_bits, b.m_bits);
Chris@16 641 std::swap(m_num_bits, b.m_num_bits);
Chris@16 642 }
Chris@16 643
Chris@16 644 template <typename Block, typename Allocator>
Chris@16 645 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
Chris@16 646 operator=(const dynamic_bitset<Block, Allocator>& b)
Chris@16 647 {
Chris@16 648 m_bits = b.m_bits;
Chris@16 649 m_num_bits = b.m_num_bits;
Chris@16 650 return *this;
Chris@16 651 }
Chris@16 652
Chris@101 653 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101 654
Chris@101 655 template <typename Block, typename Allocator>
Chris@101 656 inline dynamic_bitset<Block, Allocator>::
Chris@101 657 dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
Chris@101 658 : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
Chris@101 659 {
Chris@101 660 // Required so that assert(m_check_invariants()); works.
Chris@101 661 assert((b.m_bits = buffer_type()).empty());
Chris@101 662 b.m_num_bits = 0;
Chris@101 663 }
Chris@101 664
Chris@101 665 template <typename Block, typename Allocator>
Chris@101 666 inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
Chris@101 667 operator=(dynamic_bitset<Block, Allocator>&& b)
Chris@101 668 {
Chris@101 669 if (boost::addressof(b) == this) { return *this; }
Chris@101 670
Chris@101 671 m_bits = boost::move(b.m_bits);
Chris@101 672 m_num_bits = boost::move(b.m_num_bits);
Chris@101 673 // Required so that assert(m_check_invariants()); works.
Chris@101 674 assert((b.m_bits = buffer_type()).empty());
Chris@101 675 b.m_num_bits = 0;
Chris@101 676 return *this;
Chris@101 677 }
Chris@101 678
Chris@101 679 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
Chris@101 680
Chris@16 681 template <typename Block, typename Allocator>
Chris@16 682 inline typename dynamic_bitset<Block, Allocator>::allocator_type
Chris@16 683 dynamic_bitset<Block, Allocator>::get_allocator() const
Chris@16 684 {
Chris@16 685 return m_bits.get_allocator();
Chris@16 686 }
Chris@16 687
Chris@16 688 //-----------------------------------------------------------------------------
Chris@16 689 // size changing operations
Chris@16 690
Chris@16 691 template <typename Block, typename Allocator>
Chris@16 692 void dynamic_bitset<Block, Allocator>::
Chris@16 693 resize(size_type num_bits, bool value) // strong guarantee
Chris@16 694 {
Chris@16 695
Chris@16 696 const size_type old_num_blocks = num_blocks();
Chris@16 697 const size_type required_blocks = calc_num_blocks(num_bits);
Chris@16 698
Chris@16 699 const block_type v = value? ~Block(0) : Block(0);
Chris@16 700
Chris@16 701 if (required_blocks != old_num_blocks) {
Chris@16 702 m_bits.resize(required_blocks, v); // s.g. (copy)
Chris@16 703 }
Chris@16 704
Chris@16 705
Chris@16 706 // At this point:
Chris@16 707 //
Chris@16 708 // - if the buffer was shrunk, we have nothing more to do,
Chris@16 709 // except a call to m_zero_unused_bits()
Chris@16 710 //
Chris@16 711 // - if it was enlarged, all the (used) bits in the new blocks have
Chris@16 712 // the correct value, but we have not yet touched those bits, if
Chris@16 713 // any, that were 'unused bits' before enlarging: if value == true,
Chris@16 714 // they must be set.
Chris@16 715
Chris@16 716 if (value && (num_bits > m_num_bits)) {
Chris@16 717
Chris@16 718 const block_width_type extra_bits = count_extra_bits();
Chris@16 719 if (extra_bits) {
Chris@16 720 assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
Chris@16 721
Chris@16 722 // Set them.
Chris@16 723 m_bits[old_num_blocks - 1] |= (v << extra_bits);
Chris@16 724 }
Chris@16 725
Chris@16 726 }
Chris@16 727
Chris@16 728 m_num_bits = num_bits;
Chris@16 729 m_zero_unused_bits();
Chris@16 730
Chris@16 731 }
Chris@16 732
Chris@16 733 template <typename Block, typename Allocator>
Chris@16 734 void dynamic_bitset<Block, Allocator>::
Chris@16 735 clear() // no throw
Chris@16 736 {
Chris@16 737 m_bits.clear();
Chris@16 738 m_num_bits = 0;
Chris@16 739 }
Chris@16 740
Chris@16 741
Chris@16 742 template <typename Block, typename Allocator>
Chris@16 743 void dynamic_bitset<Block, Allocator>::
Chris@16 744 push_back(bool bit)
Chris@16 745 {
Chris@16 746 const size_type sz = size();
Chris@16 747 resize(sz + 1);
Chris@16 748 set(sz, bit);
Chris@16 749 }
Chris@16 750
Chris@16 751 template <typename Block, typename Allocator>
Chris@16 752 void dynamic_bitset<Block, Allocator>::
Chris@101 753 pop_back()
Chris@101 754 {
Chris@101 755 const size_type old_num_blocks = num_blocks();
Chris@101 756 const size_type required_blocks = calc_num_blocks(m_num_bits - 1);
Chris@101 757
Chris@101 758 if (required_blocks != old_num_blocks) {
Chris@101 759 m_bits.pop_back();
Chris@101 760 }
Chris@101 761
Chris@101 762 --m_num_bits;
Chris@101 763 m_zero_unused_bits();
Chris@101 764 }
Chris@101 765
Chris@101 766
Chris@101 767 template <typename Block, typename Allocator>
Chris@101 768 void dynamic_bitset<Block, Allocator>::
Chris@16 769 append(Block value) // strong guarantee
Chris@16 770 {
Chris@16 771 const block_width_type r = count_extra_bits();
Chris@16 772
Chris@16 773 if (r == 0) {
Chris@16 774 // the buffer is empty, or all blocks are filled
Chris@16 775 m_bits.push_back(value);
Chris@16 776 }
Chris@16 777 else {
Chris@16 778 m_bits.push_back(value >> (bits_per_block - r));
Chris@16 779 m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
Chris@16 780 }
Chris@16 781
Chris@16 782 m_num_bits += bits_per_block;
Chris@16 783 assert(m_check_invariants());
Chris@16 784
Chris@16 785 }
Chris@16 786
Chris@16 787
Chris@16 788 //-----------------------------------------------------------------------------
Chris@16 789 // bitset operations
Chris@16 790 template <typename Block, typename Allocator>
Chris@16 791 dynamic_bitset<Block, Allocator>&
Chris@16 792 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
Chris@16 793 {
Chris@16 794 assert(size() == rhs.size());
Chris@16 795 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 796 m_bits[i] &= rhs.m_bits[i];
Chris@16 797 return *this;
Chris@16 798 }
Chris@16 799
Chris@16 800 template <typename Block, typename Allocator>
Chris@16 801 dynamic_bitset<Block, Allocator>&
Chris@16 802 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
Chris@16 803 {
Chris@16 804 assert(size() == rhs.size());
Chris@16 805 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 806 m_bits[i] |= rhs.m_bits[i];
Chris@16 807 //m_zero_unused_bits();
Chris@16 808 return *this;
Chris@16 809 }
Chris@16 810
Chris@16 811 template <typename Block, typename Allocator>
Chris@16 812 dynamic_bitset<Block, Allocator>&
Chris@16 813 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
Chris@16 814 {
Chris@16 815 assert(size() == rhs.size());
Chris@16 816 for (size_type i = 0; i < this->num_blocks(); ++i)
Chris@16 817 m_bits[i] ^= rhs.m_bits[i];
Chris@16 818 //m_zero_unused_bits();
Chris@16 819 return *this;
Chris@16 820 }
Chris@16 821
Chris@16 822 template <typename Block, typename Allocator>
Chris@16 823 dynamic_bitset<Block, Allocator>&
Chris@16 824 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
Chris@16 825 {
Chris@16 826 assert(size() == rhs.size());
Chris@16 827 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 828 m_bits[i] &= ~rhs.m_bits[i];
Chris@16 829 //m_zero_unused_bits();
Chris@16 830 return *this;
Chris@16 831 }
Chris@16 832
Chris@16 833 //
Chris@16 834 // NOTE:
Chris@16 835 // Note that the 'if (r != 0)' is crucial to avoid undefined
Chris@16 836 // behavior when the left hand operand of >> isn't promoted to a
Chris@16 837 // wider type (because rs would be too large).
Chris@16 838 //
Chris@16 839 template <typename Block, typename Allocator>
Chris@16 840 dynamic_bitset<Block, Allocator>&
Chris@16 841 dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
Chris@16 842 {
Chris@16 843 if (n >= m_num_bits)
Chris@16 844 return reset();
Chris@16 845 //else
Chris@16 846 if (n > 0) {
Chris@16 847
Chris@16 848 size_type const last = num_blocks() - 1; // num_blocks() is >= 1
Chris@16 849 size_type const div = n / bits_per_block; // div is <= last
Chris@16 850 block_width_type const r = bit_index(n);
Chris@16 851 block_type * const b = &m_bits[0];
Chris@16 852
Chris@16 853 if (r != 0) {
Chris@16 854
Chris@16 855 block_width_type const rs = bits_per_block - r;
Chris@16 856
Chris@16 857 for (size_type i = last-div; i>0; --i) {
Chris@16 858 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
Chris@16 859 }
Chris@16 860 b[div] = b[0] << r;
Chris@16 861
Chris@16 862 }
Chris@16 863 else {
Chris@16 864 for (size_type i = last-div; i>0; --i) {
Chris@16 865 b[i+div] = b[i];
Chris@16 866 }
Chris@16 867 b[div] = b[0];
Chris@16 868 }
Chris@16 869
Chris@16 870 // zero out div blocks at the less significant end
Chris@101 871 std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
Chris@16 872
Chris@16 873 // zero out any 1 bit that flowed into the unused part
Chris@16 874 m_zero_unused_bits(); // thanks to Lester Gong
Chris@16 875
Chris@16 876 }
Chris@16 877
Chris@16 878 return *this;
Chris@16 879
Chris@16 880
Chris@16 881 }
Chris@16 882
Chris@16 883
Chris@16 884 //
Chris@16 885 // NOTE:
Chris@16 886 // see the comments to operator <<=
Chris@16 887 //
Chris@16 888 template <typename B, typename A>
Chris@16 889 dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
Chris@16 890 if (n >= m_num_bits) {
Chris@16 891 return reset();
Chris@16 892 }
Chris@16 893 //else
Chris@16 894 if (n>0) {
Chris@16 895
Chris@16 896 size_type const last = num_blocks() - 1; // num_blocks() is >= 1
Chris@16 897 size_type const div = n / bits_per_block; // div is <= last
Chris@16 898 block_width_type const r = bit_index(n);
Chris@16 899 block_type * const b = &m_bits[0];
Chris@16 900
Chris@16 901
Chris@16 902 if (r != 0) {
Chris@16 903
Chris@16 904 block_width_type const ls = bits_per_block - r;
Chris@16 905
Chris@16 906 for (size_type i = div; i < last; ++i) {
Chris@16 907 b[i-div] = (b[i] >> r) | (b[i+1] << ls);
Chris@16 908 }
Chris@16 909 // r bits go to zero
Chris@16 910 b[last-div] = b[last] >> r;
Chris@16 911 }
Chris@16 912
Chris@16 913 else {
Chris@16 914 for (size_type i = div; i <= last; ++i) {
Chris@16 915 b[i-div] = b[i];
Chris@16 916 }
Chris@16 917 // note the '<=': the last iteration 'absorbs'
Chris@16 918 // b[last-div] = b[last] >> 0;
Chris@16 919 }
Chris@16 920
Chris@16 921
Chris@16 922
Chris@16 923 // div blocks are zero filled at the most significant end
Chris@101 924 std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
Chris@16 925 }
Chris@16 926
Chris@16 927 return *this;
Chris@16 928 }
Chris@16 929
Chris@16 930
Chris@16 931 template <typename Block, typename Allocator>
Chris@16 932 dynamic_bitset<Block, Allocator>
Chris@16 933 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
Chris@16 934 {
Chris@16 935 dynamic_bitset r(*this);
Chris@16 936 return r <<= n;
Chris@16 937 }
Chris@16 938
Chris@16 939 template <typename Block, typename Allocator>
Chris@16 940 dynamic_bitset<Block, Allocator>
Chris@16 941 dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
Chris@16 942 {
Chris@16 943 dynamic_bitset r(*this);
Chris@16 944 return r >>= n;
Chris@16 945 }
Chris@16 946
Chris@16 947
Chris@16 948 //-----------------------------------------------------------------------------
Chris@16 949 // basic bit operations
Chris@16 950
Chris@16 951 template <typename Block, typename Allocator>
Chris@16 952 dynamic_bitset<Block, Allocator>&
Chris@16 953 dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
Chris@16 954 {
Chris@16 955 assert(pos < m_num_bits);
Chris@16 956
Chris@16 957 if (val)
Chris@16 958 m_bits[block_index(pos)] |= bit_mask(pos);
Chris@16 959 else
Chris@16 960 reset(pos);
Chris@16 961
Chris@16 962 return *this;
Chris@16 963 }
Chris@16 964
Chris@16 965 template <typename Block, typename Allocator>
Chris@16 966 dynamic_bitset<Block, Allocator>&
Chris@16 967 dynamic_bitset<Block, Allocator>::set()
Chris@16 968 {
Chris@16 969 std::fill(m_bits.begin(), m_bits.end(), ~Block(0));
Chris@16 970 m_zero_unused_bits();
Chris@16 971 return *this;
Chris@16 972 }
Chris@16 973
Chris@16 974 template <typename Block, typename Allocator>
Chris@16 975 dynamic_bitset<Block, Allocator>&
Chris@16 976 dynamic_bitset<Block, Allocator>::reset(size_type pos)
Chris@16 977 {
Chris@16 978 assert(pos < m_num_bits);
Chris@16 979 #if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
Chris@16 980 // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
Chris@16 981 // use the |^ variation instead.. <grafik>
Chris@16 982 m_bits[block_index(pos)] |= bit_mask(pos);
Chris@16 983 m_bits[block_index(pos)] ^= bit_mask(pos);
Chris@16 984 #else
Chris@16 985 m_bits[block_index(pos)] &= ~bit_mask(pos);
Chris@16 986 #endif
Chris@16 987 return *this;
Chris@16 988 }
Chris@16 989
Chris@16 990 template <typename Block, typename Allocator>
Chris@16 991 dynamic_bitset<Block, Allocator>&
Chris@16 992 dynamic_bitset<Block, Allocator>::reset()
Chris@16 993 {
Chris@16 994 std::fill(m_bits.begin(), m_bits.end(), Block(0));
Chris@16 995 return *this;
Chris@16 996 }
Chris@16 997
Chris@16 998 template <typename Block, typename Allocator>
Chris@16 999 dynamic_bitset<Block, Allocator>&
Chris@16 1000 dynamic_bitset<Block, Allocator>::flip(size_type pos)
Chris@16 1001 {
Chris@16 1002 assert(pos < m_num_bits);
Chris@16 1003 m_bits[block_index(pos)] ^= bit_mask(pos);
Chris@16 1004 return *this;
Chris@16 1005 }
Chris@16 1006
Chris@16 1007 template <typename Block, typename Allocator>
Chris@16 1008 dynamic_bitset<Block, Allocator>&
Chris@16 1009 dynamic_bitset<Block, Allocator>::flip()
Chris@16 1010 {
Chris@16 1011 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 1012 m_bits[i] = ~m_bits[i];
Chris@16 1013 m_zero_unused_bits();
Chris@16 1014 return *this;
Chris@16 1015 }
Chris@16 1016
Chris@16 1017 template <typename Block, typename Allocator>
Chris@16 1018 bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
Chris@16 1019 {
Chris@16 1020 return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
Chris@16 1021 }
Chris@16 1022
Chris@16 1023 template <typename Block, typename Allocator>
Chris@16 1024 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
Chris@16 1025 {
Chris@16 1026 assert(pos < m_num_bits);
Chris@16 1027 return m_unchecked_test(pos);
Chris@16 1028 }
Chris@16 1029
Chris@16 1030 template <typename Block, typename Allocator>
Chris@101 1031 bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
Chris@101 1032 {
Chris@101 1033 bool const b = test(pos);
Chris@101 1034 if (b != val) {
Chris@101 1035 set(pos, val);
Chris@101 1036 }
Chris@101 1037 return b;
Chris@101 1038 }
Chris@101 1039
Chris@101 1040 template <typename Block, typename Allocator>
Chris@101 1041 bool dynamic_bitset<Block, Allocator>::all() const
Chris@101 1042 {
Chris@101 1043 if (empty()) {
Chris@101 1044 return true;
Chris@101 1045 }
Chris@101 1046
Chris@101 1047 const block_width_type extra_bits = count_extra_bits();
Chris@101 1048 block_type const all_ones = ~static_cast<Block>(0);
Chris@101 1049
Chris@101 1050 if (extra_bits == 0) {
Chris@101 1051 for (size_type i = 0, e = num_blocks(); i < e; ++i) {
Chris@101 1052 if (m_bits[i] != all_ones) {
Chris@101 1053 return false;
Chris@101 1054 }
Chris@101 1055 }
Chris@101 1056 } else {
Chris@101 1057 for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
Chris@101 1058 if (m_bits[i] != all_ones) {
Chris@101 1059 return false;
Chris@101 1060 }
Chris@101 1061 }
Chris@101 1062 block_type const mask = ~(~static_cast<Block>(0) << extra_bits);
Chris@101 1063 if (m_highest_block() != mask) {
Chris@101 1064 return false;
Chris@101 1065 }
Chris@101 1066 }
Chris@101 1067 return true;
Chris@101 1068 }
Chris@101 1069
Chris@101 1070 template <typename Block, typename Allocator>
Chris@16 1071 bool dynamic_bitset<Block, Allocator>::any() const
Chris@16 1072 {
Chris@16 1073 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 1074 if (m_bits[i])
Chris@16 1075 return true;
Chris@16 1076 return false;
Chris@16 1077 }
Chris@16 1078
Chris@16 1079 template <typename Block, typename Allocator>
Chris@16 1080 inline bool dynamic_bitset<Block, Allocator>::none() const
Chris@16 1081 {
Chris@16 1082 return !any();
Chris@16 1083 }
Chris@16 1084
Chris@16 1085 template <typename Block, typename Allocator>
Chris@16 1086 dynamic_bitset<Block, Allocator>
Chris@16 1087 dynamic_bitset<Block, Allocator>::operator~() const
Chris@16 1088 {
Chris@16 1089 dynamic_bitset b(*this);
Chris@16 1090 b.flip();
Chris@16 1091 return b;
Chris@16 1092 }
Chris@16 1093
Chris@16 1094 template <typename Block, typename Allocator>
Chris@16 1095 typename dynamic_bitset<Block, Allocator>::size_type
Chris@101 1096 dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
Chris@16 1097 {
Chris@16 1098 using detail::dynamic_bitset_impl::table_width;
Chris@16 1099 using detail::dynamic_bitset_impl::access_by_bytes;
Chris@16 1100 using detail::dynamic_bitset_impl::access_by_blocks;
Chris@16 1101 using detail::dynamic_bitset_impl::value_to_type;
Chris@16 1102
Chris@16 1103 #if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3)
Chris@16 1104 // NOTE: Explicit qualification of "bits_per_block"
Chris@16 1105 // breaks compilation on gcc 4.3.3
Chris@16 1106 enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) };
Chris@16 1107 #else
Chris@16 1108 // NOTE: Explicitly qualifying "bits_per_block" to workaround
Chris@16 1109 // regressions of gcc 3.4.x
Chris@16 1110 enum { no_padding =
Chris@16 1111 dynamic_bitset<Block, Allocator>::bits_per_block
Chris@16 1112 == CHAR_BIT * sizeof(Block) };
Chris@16 1113 #endif
Chris@16 1114
Chris@16 1115 enum { enough_table_width = table_width >= CHAR_BIT };
Chris@16 1116
Chris@16 1117 enum { mode = (no_padding && enough_table_width)
Chris@16 1118 ? access_by_bytes
Chris@16 1119 : access_by_blocks };
Chris@16 1120
Chris@16 1121 return do_count(m_bits.begin(), num_blocks(), Block(0),
Chris@16 1122 static_cast<value_to_type<(bool)mode> *>(0));
Chris@16 1123 }
Chris@16 1124
Chris@16 1125
Chris@16 1126 //-----------------------------------------------------------------------------
Chris@16 1127 // conversions
Chris@16 1128
Chris@16 1129
Chris@16 1130 template <typename B, typename A, typename stringT>
Chris@16 1131 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
Chris@16 1132 bool dump_all)
Chris@16 1133 {
Chris@16 1134 typedef typename stringT::traits_type Tr;
Chris@16 1135 typedef typename stringT::value_type Ch;
Chris@16 1136
Chris@16 1137 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
Chris@16 1138 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16 1139 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16 1140
Chris@16 1141 // Note that this function may access (when
Chris@16 1142 // dump_all == true) bits beyond position size() - 1
Chris@16 1143
Chris@16 1144 typedef typename dynamic_bitset<B, A>::size_type size_type;
Chris@16 1145
Chris@16 1146 const size_type len = dump_all?
Chris@16 1147 dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
Chris@16 1148 b.size();
Chris@16 1149 s.assign (len, zero);
Chris@16 1150
Chris@16 1151 for (size_type i = 0; i < len; ++i) {
Chris@16 1152 if (b.m_unchecked_test(i))
Chris@16 1153 Tr::assign(s[len - 1 - i], one);
Chris@16 1154
Chris@16 1155 }
Chris@16 1156
Chris@16 1157 }
Chris@16 1158
Chris@16 1159
Chris@16 1160 // A comment similar to the one about the constructor from
Chris@16 1161 // basic_string can be done here. Thanks to James Kanze for
Chris@16 1162 // making me (Gennaro) realize this important separation of
Chris@16 1163 // concerns issue, as well as many things about i18n.
Chris@16 1164 //
Chris@16 1165 template <typename Block, typename Allocator, typename stringT>
Chris@16 1166 inline void
Chris@16 1167 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
Chris@16 1168 {
Chris@16 1169 to_string_helper(b, s, false);
Chris@16 1170 }
Chris@16 1171
Chris@16 1172
Chris@16 1173 // Differently from to_string this function dumps out
Chris@16 1174 // every bit of the internal representation (may be
Chris@16 1175 // useful for debugging purposes)
Chris@16 1176 //
Chris@16 1177 template <typename B, typename A, typename stringT>
Chris@16 1178 inline void
Chris@16 1179 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s)
Chris@16 1180 {
Chris@16 1181 to_string_helper(b, s, true /* =dump_all*/);
Chris@16 1182 }
Chris@16 1183
Chris@16 1184 template <typename Block, typename Allocator, typename BlockOutputIterator>
Chris@16 1185 inline void
Chris@16 1186 to_block_range(const dynamic_bitset<Block, Allocator>& b,
Chris@16 1187 BlockOutputIterator result)
Chris@16 1188 {
Chris@16 1189 // note how this copies *all* bits, including the
Chris@16 1190 // unused ones in the last block (which are zero)
Chris@16 1191 std::copy(b.m_bits.begin(), b.m_bits.end(), result);
Chris@16 1192 }
Chris@16 1193
Chris@16 1194 template <typename Block, typename Allocator>
Chris@16 1195 unsigned long dynamic_bitset<Block, Allocator>::
Chris@16 1196 to_ulong() const
Chris@16 1197 {
Chris@16 1198
Chris@16 1199 if (m_num_bits == 0)
Chris@16 1200 return 0; // convention
Chris@16 1201
Chris@16 1202 // Check for overflows. This may be a performance burden on very
Chris@16 1203 // large bitsets but is required by the specification, sorry
Chris@16 1204 if (find_next(ulong_width - 1) != npos)
Chris@101 1205 BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
Chris@16 1206
Chris@16 1207
Chris@16 1208 // Ok, from now on we can be sure there's no "on" bit
Chris@16 1209 // beyond the "allowed" positions
Chris@16 1210 typedef unsigned long result_type;
Chris@16 1211
Chris@16 1212 const size_type maximum_size =
Chris@16 1213 (std::min)(m_num_bits, static_cast<size_type>(ulong_width));
Chris@16 1214
Chris@16 1215 const size_type last_block = block_index( maximum_size - 1 );
Chris@16 1216
Chris@16 1217 assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width));
Chris@16 1218
Chris@16 1219 result_type result = 0;
Chris@16 1220 for (size_type i = 0; i <= last_block; ++i) {
Chris@16 1221 const size_type offset = i * bits_per_block;
Chris@16 1222 result |= (static_cast<result_type>(m_bits[i]) << offset);
Chris@16 1223 }
Chris@16 1224
Chris@16 1225 return result;
Chris@16 1226 }
Chris@16 1227
Chris@16 1228 template <typename Block, typename Allocator>
Chris@16 1229 inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101 1230 dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
Chris@16 1231 {
Chris@16 1232 return m_num_bits;
Chris@16 1233 }
Chris@16 1234
Chris@16 1235 template <typename Block, typename Allocator>
Chris@16 1236 inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101 1237 dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
Chris@16 1238 {
Chris@16 1239 return m_bits.size();
Chris@16 1240 }
Chris@16 1241
Chris@16 1242 template <typename Block, typename Allocator>
Chris@16 1243 inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@101 1244 dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
Chris@16 1245 {
Chris@16 1246 // Semantics of vector<>::max_size() aren't very clear
Chris@16 1247 // (see lib issue 197) and many library implementations
Chris@16 1248 // simply return dummy values, _unrelated_ to the underlying
Chris@16 1249 // allocator.
Chris@16 1250 //
Chris@16 1251 // Given these problems, I was tempted to not provide this
Chris@16 1252 // function at all but the user could need it if he provides
Chris@16 1253 // his own allocator.
Chris@16 1254 //
Chris@16 1255
Chris@16 1256 const size_type m = detail::dynamic_bitset_impl::
Chris@16 1257 vector_max_size_workaround(m_bits);
Chris@16 1258
Chris@16 1259 return m <= (size_type(-1)/bits_per_block) ?
Chris@16 1260 m * bits_per_block :
Chris@16 1261 size_type(-1);
Chris@16 1262 }
Chris@16 1263
Chris@16 1264 template <typename Block, typename Allocator>
Chris@101 1265 inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
Chris@16 1266 {
Chris@16 1267 return size() == 0;
Chris@16 1268 }
Chris@16 1269
Chris@16 1270 template <typename Block, typename Allocator>
Chris@16 1271 bool dynamic_bitset<Block, Allocator>::
Chris@16 1272 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
Chris@16 1273 {
Chris@16 1274 assert(size() == a.size());
Chris@16 1275 for (size_type i = 0; i < num_blocks(); ++i)
Chris@16 1276 if (m_bits[i] & ~a.m_bits[i])
Chris@16 1277 return false;
Chris@16 1278 return true;
Chris@16 1279 }
Chris@16 1280
Chris@16 1281 template <typename Block, typename Allocator>
Chris@16 1282 bool dynamic_bitset<Block, Allocator>::
Chris@16 1283 is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
Chris@16 1284 {
Chris@16 1285 assert(size() == a.size());
Chris@16 1286 assert(num_blocks() == a.num_blocks());
Chris@16 1287
Chris@16 1288 bool proper = false;
Chris@16 1289 for (size_type i = 0; i < num_blocks(); ++i) {
Chris@16 1290 const Block & bt = m_bits[i];
Chris@16 1291 const Block & ba = a.m_bits[i];
Chris@16 1292
Chris@16 1293 if (bt & ~ba)
Chris@16 1294 return false; // not a subset at all
Chris@16 1295 if (ba & ~bt)
Chris@16 1296 proper = true;
Chris@16 1297 }
Chris@16 1298 return proper;
Chris@16 1299 }
Chris@16 1300
Chris@16 1301 template <typename Block, typename Allocator>
Chris@16 1302 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
Chris@16 1303 {
Chris@16 1304 size_type common_blocks = num_blocks() < b.num_blocks()
Chris@16 1305 ? num_blocks() : b.num_blocks();
Chris@16 1306
Chris@16 1307 for(size_type i = 0; i < common_blocks; ++i) {
Chris@16 1308 if(m_bits[i] & b.m_bits[i])
Chris@16 1309 return true;
Chris@16 1310 }
Chris@16 1311 return false;
Chris@16 1312 }
Chris@16 1313
Chris@16 1314 // --------------------------------
Chris@16 1315 // lookup
Chris@16 1316
Chris@16 1317
Chris@16 1318 // look for the first bit "on", starting
Chris@16 1319 // from the block with index first_block
Chris@16 1320 //
Chris@16 1321 template <typename Block, typename Allocator>
Chris@16 1322 typename dynamic_bitset<Block, Allocator>::size_type
Chris@16 1323 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
Chris@16 1324 {
Chris@16 1325 size_type i = first_block;
Chris@16 1326
Chris@16 1327 // skip null blocks
Chris@16 1328 while (i < num_blocks() && m_bits[i] == 0)
Chris@16 1329 ++i;
Chris@16 1330
Chris@16 1331 if (i >= num_blocks())
Chris@16 1332 return npos; // not found
Chris@16 1333
Chris@101 1334 return i * bits_per_block + static_cast<size_type>(boost::lowest_bit(m_bits[i]));
Chris@16 1335
Chris@16 1336 }
Chris@16 1337
Chris@16 1338
Chris@16 1339 template <typename Block, typename Allocator>
Chris@16 1340 typename dynamic_bitset<Block, Allocator>::size_type
Chris@16 1341 dynamic_bitset<Block, Allocator>::find_first() const
Chris@16 1342 {
Chris@16 1343 return m_do_find_from(0);
Chris@16 1344 }
Chris@16 1345
Chris@16 1346
Chris@16 1347 template <typename Block, typename Allocator>
Chris@16 1348 typename dynamic_bitset<Block, Allocator>::size_type
Chris@16 1349 dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
Chris@16 1350 {
Chris@16 1351
Chris@16 1352 const size_type sz = size();
Chris@16 1353 if (pos >= (sz-1) || sz == 0)
Chris@16 1354 return npos;
Chris@16 1355
Chris@16 1356 ++pos;
Chris@16 1357
Chris@16 1358 const size_type blk = block_index(pos);
Chris@16 1359 const block_width_type ind = bit_index(pos);
Chris@16 1360
Chris@101 1361 // shift bits upto one immediately after current
Chris@101 1362 const Block fore = m_bits[blk] >> ind;
Chris@16 1363
Chris@16 1364 return fore?
Chris@101 1365 pos + static_cast<size_type>(lowest_bit(fore))
Chris@16 1366 :
Chris@16 1367 m_do_find_from(blk + 1);
Chris@16 1368
Chris@16 1369 }
Chris@16 1370
Chris@16 1371
Chris@16 1372
Chris@16 1373 //-----------------------------------------------------------------------------
Chris@16 1374 // comparison
Chris@16 1375
Chris@16 1376 template <typename Block, typename Allocator>
Chris@16 1377 bool operator==(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1378 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1379 {
Chris@16 1380 return (a.m_num_bits == b.m_num_bits)
Chris@16 1381 && (a.m_bits == b.m_bits);
Chris@16 1382 }
Chris@16 1383
Chris@16 1384 template <typename Block, typename Allocator>
Chris@16 1385 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1386 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1387 {
Chris@16 1388 return !(a == b);
Chris@16 1389 }
Chris@16 1390
Chris@16 1391 template <typename Block, typename Allocator>
Chris@16 1392 bool operator<(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1393 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1394 {
Chris@16 1395 assert(a.size() == b.size());
Chris@16 1396 typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
Chris@16 1397
Chris@16 1398 //if (a.size() == 0)
Chris@16 1399 // return false;
Chris@16 1400
Chris@16 1401 // Since we are storing the most significant bit
Chris@16 1402 // at pos == size() - 1, we need to do the comparisons in reverse.
Chris@16 1403 //
Chris@16 1404 for (size_type ii = a.num_blocks(); ii > 0; --ii) {
Chris@16 1405 size_type i = ii-1;
Chris@16 1406 if (a.m_bits[i] < b.m_bits[i])
Chris@16 1407 return true;
Chris@16 1408 else if (a.m_bits[i] > b.m_bits[i])
Chris@16 1409 return false;
Chris@16 1410 }
Chris@16 1411 return false;
Chris@16 1412 }
Chris@16 1413
Chris@16 1414 template <typename Block, typename Allocator>
Chris@16 1415 inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1416 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1417 {
Chris@16 1418 return !(a > b);
Chris@16 1419 }
Chris@16 1420
Chris@16 1421 template <typename Block, typename Allocator>
Chris@16 1422 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1423 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1424 {
Chris@16 1425 return b < a;
Chris@16 1426 }
Chris@16 1427
Chris@16 1428 template <typename Block, typename Allocator>
Chris@16 1429 inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
Chris@16 1430 const dynamic_bitset<Block, Allocator>& b)
Chris@16 1431 {
Chris@16 1432 return !(a < b);
Chris@16 1433 }
Chris@16 1434
Chris@16 1435 //-----------------------------------------------------------------------------
Chris@16 1436 // stream operations
Chris@16 1437
Chris@16 1438 #ifdef BOOST_OLD_IOSTREAMS
Chris@16 1439 template < typename Block, typename Alloc>
Chris@16 1440 std::ostream&
Chris@16 1441 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
Chris@16 1442 {
Chris@16 1443 // NOTE: since this is aimed at "classic" iostreams, exception
Chris@16 1444 // masks on the stream are not supported. The library that
Chris@16 1445 // ships with gcc 2.95 has an exceptions() member function but
Chris@16 1446 // nothing is actually implemented; not even the class ios::failure.
Chris@16 1447
Chris@16 1448 using namespace std;
Chris@16 1449
Chris@16 1450 const ios::iostate ok = ios::goodbit;
Chris@16 1451 ios::iostate err = ok;
Chris@16 1452
Chris@16 1453 if (os.opfx()) {
Chris@16 1454
Chris@16 1455 //try
Chris@16 1456 typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
Chris@16 1457
Chris@16 1458 const bitsetsize_type sz = b.size();
Chris@16 1459 std::streambuf * buf = os.rdbuf();
Chris@16 1460 size_t npad = os.width() <= 0 // careful: os.width() is signed (and can be < 0)
Chris@16 1461 || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz;
Chris@16 1462
Chris@16 1463 const char fill_char = os.fill();
Chris@16 1464 const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
Chris@16 1465
Chris@16 1466 // if needed fill at left; pad is decresed along the way
Chris@16 1467 if (adjustfield != ios::left) {
Chris@16 1468 for (; 0 < npad; --npad)
Chris@16 1469 if (fill_char != buf->sputc(fill_char)) {
Chris@16 1470 err |= ios::failbit;
Chris@16 1471 break;
Chris@16 1472 }
Chris@16 1473 }
Chris@16 1474
Chris@16 1475 if (err == ok) {
Chris@16 1476 // output the bitset
Chris@16 1477 for (bitsetsize_type i = b.size(); 0 < i; --i) {
Chris@16 1478 const char dig = b.test(i-1)? '1' : '0';
Chris@16 1479 if (EOF == buf->sputc(dig)) {
Chris@16 1480 err |= ios::failbit;
Chris@16 1481 break;
Chris@16 1482 }
Chris@16 1483 }
Chris@16 1484 }
Chris@16 1485
Chris@16 1486 if (err == ok) {
Chris@16 1487 // if needed fill at right
Chris@16 1488 for (; 0 < npad; --npad) {
Chris@16 1489 if (fill_char != buf->sputc(fill_char)) {
Chris@16 1490 err |= ios::failbit;
Chris@16 1491 break;
Chris@16 1492 }
Chris@16 1493 }
Chris@16 1494 }
Chris@16 1495
Chris@16 1496 os.osfx();
Chris@16 1497 os.width(0);
Chris@16 1498
Chris@16 1499 } // if opfx
Chris@16 1500
Chris@16 1501 if(err != ok)
Chris@16 1502 os.setstate(err); // assume this does NOT throw
Chris@16 1503 return os;
Chris@16 1504
Chris@16 1505 }
Chris@16 1506 #else
Chris@16 1507
Chris@16 1508 template <typename Ch, typename Tr, typename Block, typename Alloc>
Chris@16 1509 std::basic_ostream<Ch, Tr>&
Chris@16 1510 operator<<(std::basic_ostream<Ch, Tr>& os,
Chris@16 1511 const dynamic_bitset<Block, Alloc>& b)
Chris@16 1512 {
Chris@16 1513
Chris@16 1514 using namespace std;
Chris@16 1515
Chris@16 1516 const ios_base::iostate ok = ios_base::goodbit;
Chris@16 1517 ios_base::iostate err = ok;
Chris@16 1518
Chris@16 1519 typename basic_ostream<Ch, Tr>::sentry cerberos(os);
Chris@16 1520 if (cerberos) {
Chris@16 1521
Chris@16 1522 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
Chris@16 1523 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16 1524 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16 1525
Chris@101 1526 BOOST_TRY {
Chris@16 1527
Chris@101 1528 typedef typename dynamic_bitset<Block, Alloc>::size_type bitset_size_type;
Chris@16 1529 typedef basic_streambuf<Ch, Tr> buffer_type;
Chris@16 1530
Chris@16 1531 buffer_type * buf = os.rdbuf();
Chris@101 1532 // careful: os.width() is signed (and can be < 0)
Chris@101 1533 const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast<bitset_size_type>(os.width());
Chris@101 1534 streamsize npad = (width <= b.size()) ? 0 : width - b.size();
Chris@16 1535
Chris@16 1536 const Ch fill_char = os.fill();
Chris@16 1537 const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
Chris@16 1538
Chris@101 1539 // if needed fill at left; pad is decreased along the way
Chris@16 1540 if (adjustfield != ios_base::left) {
Chris@16 1541 for (; 0 < npad; --npad)
Chris@16 1542 if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
Chris@16 1543 err |= ios_base::failbit;
Chris@16 1544 break;
Chris@16 1545 }
Chris@16 1546 }
Chris@16 1547
Chris@16 1548 if (err == ok) {
Chris@16 1549 // output the bitset
Chris@101 1550 for (bitset_size_type i = b.size(); 0 < i; --i) {
Chris@16 1551 typename buffer_type::int_type
Chris@16 1552 ret = buf->sputc(b.test(i-1)? one : zero);
Chris@16 1553 if (Tr::eq_int_type(Tr::eof(), ret)) {
Chris@16 1554 err |= ios_base::failbit;
Chris@16 1555 break;
Chris@16 1556 }
Chris@16 1557 }
Chris@16 1558 }
Chris@16 1559
Chris@16 1560 if (err == ok) {
Chris@16 1561 // if needed fill at right
Chris@16 1562 for (; 0 < npad; --npad) {
Chris@16 1563 if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
Chris@16 1564 err |= ios_base::failbit;
Chris@16 1565 break;
Chris@16 1566 }
Chris@16 1567 }
Chris@16 1568 }
Chris@16 1569
Chris@16 1570
Chris@16 1571 os.width(0);
Chris@16 1572
Chris@101 1573 } BOOST_CATCH (...) { // see std 27.6.1.1/4
Chris@16 1574 bool rethrow = false;
Chris@101 1575 BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END
Chris@16 1576
Chris@16 1577 if (rethrow)
Chris@101 1578 BOOST_RETHROW;
Chris@16 1579 }
Chris@101 1580 BOOST_CATCH_END
Chris@16 1581 }
Chris@16 1582
Chris@16 1583 if(err != ok)
Chris@16 1584 os.setstate(err); // may throw exception
Chris@16 1585 return os;
Chris@16 1586
Chris@16 1587 }
Chris@16 1588 #endif
Chris@16 1589
Chris@16 1590
Chris@16 1591 #ifdef BOOST_OLD_IOSTREAMS
Chris@16 1592
Chris@16 1593 // A sentry-like class that calls isfx in its destructor.
Chris@16 1594 // "Necessary" because bit_appender::do_append may throw.
Chris@16 1595 class pseudo_sentry {
Chris@16 1596 std::istream & m_r;
Chris@16 1597 const bool m_ok;
Chris@16 1598 public:
Chris@16 1599 explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
Chris@16 1600 ~pseudo_sentry() { m_r.isfx(); }
Chris@16 1601 operator bool() const { return m_ok; }
Chris@16 1602 };
Chris@16 1603
Chris@16 1604 template <typename Block, typename Alloc>
Chris@16 1605 std::istream&
Chris@16 1606 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
Chris@16 1607 {
Chris@16 1608
Chris@16 1609 // Extractor for classic IO streams (libstdc++ < 3.0)
Chris@16 1610 // ----------------------------------------------------//
Chris@16 1611 // It's assumed that the stream buffer functions, and
Chris@16 1612 // the stream's setstate() _cannot_ throw.
Chris@16 1613
Chris@16 1614
Chris@16 1615 typedef dynamic_bitset<Block, Alloc> bitset_type;
Chris@16 1616 typedef typename bitset_type::size_type size_type;
Chris@16 1617
Chris@16 1618 std::ios::iostate err = std::ios::goodbit;
Chris@16 1619 pseudo_sentry cerberos(is); // skips whitespaces
Chris@16 1620 if(cerberos) {
Chris@16 1621
Chris@16 1622 b.clear();
Chris@16 1623
Chris@16 1624 const std::streamsize w = is.width();
Chris@16 1625 const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
Chris@101 1626 ? static_cast<size_type>(w) : b.max_size();
Chris@16 1627 typename bitset_type::bit_appender appender(b);
Chris@16 1628 std::streambuf * buf = is.rdbuf();
Chris@16 1629 for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
Chris@16 1630
Chris@16 1631 if (c == EOF) {
Chris@16 1632 err |= std::ios::eofbit;
Chris@16 1633 break;
Chris@16 1634 }
Chris@16 1635 else if (char(c) != '0' && char(c) != '1')
Chris@16 1636 break; // non digit character
Chris@16 1637
Chris@16 1638 else {
Chris@101 1639 BOOST_TRY {
Chris@16 1640 appender.do_append(char(c) == '1');
Chris@16 1641 }
Chris@101 1642 BOOST_CATCH(...) {
Chris@16 1643 is.setstate(std::ios::failbit); // assume this can't throw
Chris@101 1644 BOOST_RETHROW;
Chris@16 1645 }
Chris@101 1646 BOOST_CATCH_END
Chris@16 1647 }
Chris@16 1648
Chris@16 1649 } // for
Chris@16 1650 }
Chris@16 1651
Chris@16 1652 is.width(0);
Chris@16 1653 if (b.size() == 0)
Chris@16 1654 err |= std::ios::failbit;
Chris@16 1655 if (err != std::ios::goodbit)
Chris@16 1656 is.setstate (err); // may throw
Chris@16 1657
Chris@16 1658 return is;
Chris@16 1659 }
Chris@16 1660
Chris@16 1661 #else // BOOST_OLD_IOSTREAMS
Chris@16 1662
Chris@16 1663 template <typename Ch, typename Tr, typename Block, typename Alloc>
Chris@16 1664 std::basic_istream<Ch, Tr>&
Chris@16 1665 operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
Chris@16 1666 {
Chris@16 1667
Chris@16 1668 using namespace std;
Chris@16 1669
Chris@16 1670 typedef dynamic_bitset<Block, Alloc> bitset_type;
Chris@16 1671 typedef typename bitset_type::size_type size_type;
Chris@16 1672
Chris@16 1673 const streamsize w = is.width();
Chris@16 1674 const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
Chris@101 1675 static_cast<size_type>(w) : b.max_size();
Chris@16 1676
Chris@16 1677 ios_base::iostate err = ios_base::goodbit;
Chris@16 1678 typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
Chris@16 1679 if(cerberos) {
Chris@16 1680
Chris@16 1681 // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
Chris@16 1682 BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
Chris@16 1683 const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
Chris@16 1684 const Ch one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
Chris@16 1685
Chris@16 1686 b.clear();
Chris@101 1687 BOOST_TRY {
Chris@16 1688 typename bitset_type::bit_appender appender(b);
Chris@16 1689 basic_streambuf <Ch, Tr> * buf = is.rdbuf();
Chris@16 1690 typename Tr::int_type c = buf->sgetc();
Chris@16 1691 for( ; appender.get_count() < limit; c = buf->snextc() ) {
Chris@16 1692
Chris@16 1693 if (Tr::eq_int_type(Tr::eof(), c)) {
Chris@16 1694 err |= ios_base::eofbit;
Chris@16 1695 break;
Chris@16 1696 }
Chris@16 1697 else {
Chris@16 1698 const Ch to_c = Tr::to_char_type(c);
Chris@16 1699 const bool is_one = Tr::eq(to_c, one);
Chris@16 1700
Chris@16 1701 if (!is_one && !Tr::eq(to_c, zero))
Chris@16 1702 break; // non digit character
Chris@16 1703
Chris@16 1704 appender.do_append(is_one);
Chris@16 1705
Chris@16 1706 }
Chris@16 1707
Chris@16 1708 } // for
Chris@16 1709 }
Chris@101 1710 BOOST_CATCH (...) {
Chris@16 1711 // catches from stream buf, or from vector:
Chris@16 1712 //
Chris@16 1713 // bits_stored bits have been extracted and stored, and
Chris@16 1714 // either no further character is extractable or we can't
Chris@16 1715 // append to the underlying vector (out of memory)
Chris@16 1716
Chris@16 1717 bool rethrow = false; // see std 27.6.1.1/4
Chris@101 1718 BOOST_TRY { is.setstate(ios_base::badbit); }
Chris@101 1719 BOOST_CATCH(...) { rethrow = true; }
Chris@101 1720 BOOST_CATCH_END
Chris@16 1721
Chris@16 1722 if (rethrow)
Chris@101 1723 BOOST_RETHROW;
Chris@16 1724
Chris@16 1725 }
Chris@101 1726 BOOST_CATCH_END
Chris@16 1727 }
Chris@16 1728
Chris@16 1729 is.width(0);
Chris@16 1730 if (b.size() == 0 /*|| !cerberos*/)
Chris@16 1731 err |= ios_base::failbit;
Chris@16 1732 if (err != ios_base::goodbit)
Chris@16 1733 is.setstate (err); // may throw
Chris@16 1734
Chris@16 1735 return is;
Chris@16 1736
Chris@16 1737 }
Chris@16 1738
Chris@16 1739
Chris@16 1740 #endif
Chris@16 1741
Chris@16 1742
Chris@16 1743 //-----------------------------------------------------------------------------
Chris@16 1744 // bitset operations
Chris@16 1745
Chris@16 1746 template <typename Block, typename Allocator>
Chris@16 1747 dynamic_bitset<Block, Allocator>
Chris@16 1748 operator&(const dynamic_bitset<Block, Allocator>& x,
Chris@16 1749 const dynamic_bitset<Block, Allocator>& y)
Chris@16 1750 {
Chris@16 1751 dynamic_bitset<Block, Allocator> b(x);
Chris@16 1752 return b &= y;
Chris@16 1753 }
Chris@16 1754
Chris@16 1755 template <typename Block, typename Allocator>
Chris@16 1756 dynamic_bitset<Block, Allocator>
Chris@16 1757 operator|(const dynamic_bitset<Block, Allocator>& x,
Chris@16 1758 const dynamic_bitset<Block, Allocator>& y)
Chris@16 1759 {
Chris@16 1760 dynamic_bitset<Block, Allocator> b(x);
Chris@16 1761 return b |= y;
Chris@16 1762 }
Chris@16 1763
Chris@16 1764 template <typename Block, typename Allocator>
Chris@16 1765 dynamic_bitset<Block, Allocator>
Chris@16 1766 operator^(const dynamic_bitset<Block, Allocator>& x,
Chris@16 1767 const dynamic_bitset<Block, Allocator>& y)
Chris@16 1768 {
Chris@16 1769 dynamic_bitset<Block, Allocator> b(x);
Chris@16 1770 return b ^= y;
Chris@16 1771 }
Chris@16 1772
Chris@16 1773 template <typename Block, typename Allocator>
Chris@16 1774 dynamic_bitset<Block, Allocator>
Chris@16 1775 operator-(const dynamic_bitset<Block, Allocator>& x,
Chris@16 1776 const dynamic_bitset<Block, Allocator>& y)
Chris@16 1777 {
Chris@16 1778 dynamic_bitset<Block, Allocator> b(x);
Chris@16 1779 return b -= y;
Chris@16 1780 }
Chris@16 1781
Chris@16 1782 //-----------------------------------------------------------------------------
Chris@16 1783 // namespace scope swap
Chris@16 1784
Chris@16 1785 template<typename Block, typename Allocator>
Chris@16 1786 inline void
Chris@16 1787 swap(dynamic_bitset<Block, Allocator>& left,
Chris@16 1788 dynamic_bitset<Block, Allocator>& right) // no throw
Chris@16 1789 {
Chris@16 1790 left.swap(right);
Chris@16 1791 }
Chris@16 1792
Chris@16 1793
Chris@16 1794 //-----------------------------------------------------------------------------
Chris@16 1795 // private (on conforming compilers) member functions
Chris@16 1796
Chris@16 1797
Chris@16 1798 template <typename Block, typename Allocator>
Chris@16 1799 inline typename dynamic_bitset<Block, Allocator>::size_type
Chris@16 1800 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
Chris@16 1801 {
Chris@16 1802 return num_bits / bits_per_block
Chris@101 1803 + static_cast<size_type>( num_bits % bits_per_block != 0 );
Chris@16 1804 }
Chris@16 1805
Chris@16 1806 // gives a reference to the highest block
Chris@16 1807 //
Chris@16 1808 template <typename Block, typename Allocator>
Chris@16 1809 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
Chris@16 1810 {
Chris@16 1811 return const_cast<Block &>
Chris@16 1812 (static_cast<const dynamic_bitset *>(this)->m_highest_block());
Chris@16 1813 }
Chris@16 1814
Chris@16 1815 // gives a const-reference to the highest block
Chris@16 1816 //
Chris@16 1817 template <typename Block, typename Allocator>
Chris@16 1818 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
Chris@16 1819 {
Chris@16 1820 assert(size() > 0 && num_blocks() > 0);
Chris@16 1821 return m_bits.back();
Chris@16 1822 }
Chris@16 1823
Chris@16 1824
Chris@16 1825 // If size() is not a multiple of bits_per_block
Chris@16 1826 // then not all the bits in the last block are used.
Chris@16 1827 // This function resets the unused bits (convenient
Chris@16 1828 // for the implementation of many member functions)
Chris@16 1829 //
Chris@16 1830 template <typename Block, typename Allocator>
Chris@16 1831 inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
Chris@16 1832 {
Chris@16 1833 assert (num_blocks() == calc_num_blocks(m_num_bits));
Chris@16 1834
Chris@16 1835 // if != 0 this is the number of bits used in the last block
Chris@16 1836 const block_width_type extra_bits = count_extra_bits();
Chris@16 1837
Chris@16 1838 if (extra_bits != 0)
Chris@16 1839 m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
Chris@16 1840
Chris@16 1841 }
Chris@16 1842
Chris@16 1843 // check class invariants
Chris@16 1844 template <typename Block, typename Allocator>
Chris@16 1845 bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
Chris@16 1846 {
Chris@16 1847 const block_width_type extra_bits = count_extra_bits();
Chris@16 1848 if (extra_bits > 0) {
Chris@16 1849 block_type const mask = (~static_cast<Block>(0) << extra_bits);
Chris@16 1850 if ((m_highest_block() & mask) != 0)
Chris@16 1851 return false;
Chris@16 1852 }
Chris@16 1853 if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
Chris@16 1854 return false;
Chris@16 1855
Chris@16 1856 return true;
Chris@16 1857
Chris@16 1858 }
Chris@16 1859
Chris@16 1860
Chris@16 1861 } // namespace boost
Chris@16 1862
Chris@16 1863
Chris@16 1864 #undef BOOST_BITSET_CHAR
Chris@16 1865
Chris@16 1866 #endif // include guard
Chris@16 1867