boost/dynamic_bitset/dynamic_bitset.hpp

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