ceph/src/boost/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_width_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     template <typename B, typename A>
 332     friend bool oplessthan(const dynamic_bitset<B, A>& a,
 333                           const dynamic_bitset<B, A>& b);
 334
 335
 336     template <typename B, typename A, typename BlockOutputIterator>
 337     friend void to_block_range(const dynamic_bitset<B, A>& b,
 338                                BlockOutputIterator result);
 339
 340     template <typename BlockIterator, typename B, typename A>
 341     friend void from_block_range(BlockIterator first, BlockIterator last,
 342                                  dynamic_bitset<B, A>& result);
 343
 344
 345     template <typename CharT, typename Traits, typename B, typename A>
 346     friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,
 347                                                          dynamic_bitset<B, A>& b);
 348
 349     template <typename B, typename A, typename stringT>
 350     friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);
 351
 352
 353 #endif
 354
 355 public:
 356     // forward declaration for optional zero-copy serialization support
 357     class serialize_impl;
 358     friend class serialize_impl;
 359
 360 private:
 361     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
 362
 363     void m_zero_unused_bits();
 364     bool m_check_invariants() const;
 365
 366     size_type m_do_find_from(size_type first_block) const;
 367
 368     block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); }
 369     static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
 370     static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
 371     static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
 372
 373     template <typename CharT, typename Traits, typename Alloc>
 374     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
 375         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
 376         typename std::basic_string<CharT, Traits, Alloc>::size_type n,
 377         size_type num_bits)
 378     {
 379         assert(pos <= s.size());
 380
 381         typedef typename std::basic_string<CharT, Traits, Alloc> StrT;
 382         typedef typename StrT::traits_type Tr;
 383
 384         const typename StrT::size_type rlen = (std::min)(n, s.size() - pos);
 385         const size_type sz = ( num_bits != npos? num_bits : rlen);
 386         m_bits.resize(calc_num_blocks(sz));
 387         m_num_bits = sz;
 388
 389
 390         BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());
 391         const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
 392
 393         const size_type m = num_bits < rlen ? num_bits : rlen;
 394         typename StrT::size_type i = 0;
 395         for( ; i < m; ++i) {
 396
 397             const CharT c = s[(pos + m - 1) - i];
 398
 399             assert( Tr::eq(c, one)
 400                     || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );
 401
 402             if (Tr::eq(c, one))
 403                 set(i);
 404
 405         }
 406
 407     }
 408
 409     void init_from_unsigned_long(size_type num_bits,
 410                                  unsigned long value/*,
 411                                  const Allocator& alloc*/)
 412     {
 413
 414         assert(m_bits.size() == 0);
 415
 416         m_bits.resize(calc_num_blocks(num_bits));
 417         m_num_bits = num_bits;
 418
 419         typedef unsigned long num_type;
 420         typedef boost::detail::dynamic_bitset_impl
 421             ::shifter<num_type, bits_per_block, ulong_width> shifter;
 422
 423         //if (num_bits == 0)
 424         //    return;
 425
 426         // zero out all bits at pos >= num_bits, if any;
 427         // note that: num_bits == 0 implies value == 0
 428         if (num_bits < static_cast<size_type>(ulong_width)) {
 429             const num_type mask = (num_type(1) << num_bits) - 1;
 430             value &= mask;
 431         }
 432
 433         typename buffer_type::iterator it = m_bits.begin();
 434         for( ; value; shifter::left_shift(value), ++it) {
 435             *it = static_cast<block_type>(value);
 436         }
 437
 438     }
 439
 440
 441
 442 BOOST_DYNAMIC_BITSET_PRIVATE:
 443
 444     bool m_unchecked_test(size_type pos) const;
 445     static size_type calc_num_blocks(size_type num_bits);
 446
 447     Block&        m_highest_block();
 448     const Block&  m_highest_block() const;
 449
 450     buffer_type m_bits;
 451     size_type   m_num_bits;
 452
 453
 454     class bit_appender;
 455     friend class bit_appender;
 456     class bit_appender {
 457       // helper for stream >>
 458       // Supplies to the lack of an efficient append at the less
 459       // significant end: bits are actually appended "at left" but
 460       // rearranged in the destructor. From the perspective of
 461       // client code everything works *as if* dynamic_bitset<> had
 462       // an append_at_right() function (eventually throwing the same
 463       // exceptions as push_back) except that the function is in fact
 464       // called bit_appender::do_append().
 465       //
 466       dynamic_bitset & bs;
 467       size_type n;
 468       Block mask;
 469       Block * current;
 470
 471       // not implemented
 472       bit_appender(const bit_appender &);
 473       bit_appender & operator=(const bit_appender &);
 474
 475     public:
 476         bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}
 477         ~bit_appender() {
 478             // reverse the order of blocks, shift
 479             // if needed, and then resize
 480             //
 481             std::reverse(bs.m_bits.begin(), bs.m_bits.end());
 482             const block_width_type offs = bit_index(n);
 483             if (offs)
 484                 bs >>= (bits_per_block - offs);
 485             bs.resize(n); // doesn't enlarge, so can't throw
 486             assert(bs.m_check_invariants());
 487         }
 488         inline void do_append(bool value) {
 489
 490             if (mask == 0) {
 491                 bs.append(Block(0));
 492                 current = &bs.m_highest_block();
 493                 mask = Block(1) << (bits_per_block - 1);
 494             }
 495
 496             if(value)
 497                 *current |= mask;
 498
 499             mask /= 2;
 500             ++n;
 501         }
 502         size_type get_count() const { return n; }
 503     };
 504
 505 };
 506
 507 #if !defined BOOST_NO_INCLASS_MEMBER_INITIALIZATION
 508
 509 template <typename Block, typename Allocator>
 510 const typename dynamic_bitset<Block, Allocator>::block_width_type
 511 dynamic_bitset<Block, Allocator>::bits_per_block;
 512
 513 template <typename Block, typename Allocator>
 514 const typename dynamic_bitset<Block, Allocator>::size_type
 515 dynamic_bitset<Block, Allocator>::npos;
 516
 517 template <typename Block, typename Allocator>
 518 const typename dynamic_bitset<Block, Allocator>::block_width_type
 519 dynamic_bitset<Block, Allocator>::ulong_width;
 520
 521 #endif
 522
 523 // Global Functions:
 524
 525 // comparison
 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 template <typename Block, typename Allocator>
 539 bool operator>=(const dynamic_bitset<Block, Allocator>& a,
 540                 const dynamic_bitset<Block, Allocator>& b);
 541
 542 // stream operators
 543 #ifdef BOOST_OLD_IOSTREAMS
 544 template <typename Block, typename Allocator>
 545 std::ostream& operator<<(std::ostream& os,
 546                          const dynamic_bitset<Block, Allocator>& b);
 547
 548 template <typename Block, typename Allocator>
 549 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);
 550 #else
 551 template <typename CharT, typename Traits, typename Block, typename Allocator>
 552 std::basic_ostream<CharT, Traits>&
 553 operator<<(std::basic_ostream<CharT, Traits>& os,
 554            const dynamic_bitset<Block, Allocator>& b);
 555
 556 template <typename CharT, typename Traits, typename Block, typename Allocator>
 557 std::basic_istream<CharT, Traits>&
 558 operator>>(std::basic_istream<CharT, Traits>& is,
 559            dynamic_bitset<Block, Allocator>& b);
 560 #endif
 561
 562 // bitset operations
 563 template <typename Block, typename Allocator>
 564 dynamic_bitset<Block, Allocator>
 565 operator&(const dynamic_bitset<Block, Allocator>& b1,
 566           const dynamic_bitset<Block, Allocator>& b2);
 567
 568 template <typename Block, typename Allocator>
 569 dynamic_bitset<Block, Allocator>
 570 operator|(const dynamic_bitset<Block, Allocator>& b1,
 571           const dynamic_bitset<Block, Allocator>& b2);
 572
 573 template <typename Block, typename Allocator>
 574 dynamic_bitset<Block, Allocator>
 575 operator^(const dynamic_bitset<Block, Allocator>& b1,
 576           const dynamic_bitset<Block, Allocator>& b2);
 577
 578 template <typename Block, typename Allocator>
 579 dynamic_bitset<Block, Allocator>
 580 operator-(const dynamic_bitset<Block, Allocator>& b1,
 581           const dynamic_bitset<Block, Allocator>& b2);
 582
 583 // namespace scope swap
 584 template<typename Block, typename Allocator>
 585 void swap(dynamic_bitset<Block, Allocator>& b1,
 586           dynamic_bitset<Block, Allocator>& b2);
 587
 588
 589 template <typename Block, typename Allocator, typename stringT>
 590 void
 591 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s);
 592
 593 template <typename Block, typename Allocator, typename BlockOutputIterator>
 594 void
 595 to_block_range(const dynamic_bitset<Block, Allocator>& b,
 596                BlockOutputIterator result);
 597
 598
 599 template <typename BlockIterator, typename B, typename A>
 600 inline void
 601 from_block_range(BlockIterator first, BlockIterator last,
 602                  dynamic_bitset<B, A>& result)
 603 {
 604     // PRE: distance(first, last) <= numblocks()
 605     std::copy (first, last, result.m_bits.begin());
 606 }
 607
 608 //=============================================================================
 609 // dynamic_bitset implementation
 610
 611
 612 //-----------------------------------------------------------------------------
 613 // constructors, etc.
 614
 615 template <typename Block, typename Allocator>
 616 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)
 617   : m_bits(alloc), m_num_bits(0)
 618 {
 619
 620 }
 621
 622 template <typename Block, typename Allocator>
 623 dynamic_bitset<Block, Allocator>::
 624 dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)
 625     : m_bits(alloc),
 626       m_num_bits(0)
 627 {
 628     init_from_unsigned_long(num_bits, value);
 629 }
 630
 631 // copy constructor
 632 template <typename Block, typename Allocator>
 633 inline dynamic_bitset<Block, Allocator>::
 634 dynamic_bitset(const dynamic_bitset& b)
 635   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)
 636 {
 637
 638 }
 639
 640 template <typename Block, typename Allocator>
 641 inline dynamic_bitset<Block, Allocator>::
 642 ~dynamic_bitset()
 643 {
 644     assert(m_check_invariants());
 645 }
 646
 647 template <typename Block, typename Allocator>
 648 inline void dynamic_bitset<Block, Allocator>::
 649 swap(dynamic_bitset<Block, Allocator>& b) // no throw
 650 {
 651     std::swap(m_bits, b.m_bits);
 652     std::swap(m_num_bits, b.m_num_bits);
 653 }
 654
 655 template <typename Block, typename Allocator>
 656 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
 657 operator=(const dynamic_bitset<Block, Allocator>& b)
 658 {
 659     m_bits = b.m_bits;
 660     m_num_bits = b.m_num_bits;
 661     return *this;
 662 }
 663
 664 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 665
 666 template <typename Block, typename Allocator>
 667 inline dynamic_bitset<Block, Allocator>::
 668 dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
 669   : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
 670 {
 671     // Required so that assert(m_check_invariants()); works.
 672     assert((b.m_bits = buffer_type()).empty());
 673     b.m_num_bits = 0;
 674 }
 675
 676 template <typename Block, typename Allocator>
 677 inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
 678 operator=(dynamic_bitset<Block, Allocator>&& b)
 679 {
 680     if (boost::addressof(b) == this) { return *this; }
 681
 682     m_bits = boost::move(b.m_bits);
 683     m_num_bits = boost::move(b.m_num_bits);
 684     // Required so that assert(m_check_invariants()); works.
 685     assert((b.m_bits = buffer_type()).empty());
 686     b.m_num_bits = 0;
 687     return *this;
 688 }
 689
 690 #endif // BOOST_NO_CXX11_RVALUE_REFERENCES
 691
 692 template <typename Block, typename Allocator>
 693 inline typename dynamic_bitset<Block, Allocator>::allocator_type
 694 dynamic_bitset<Block, Allocator>::get_allocator() const
 695 {
 696     return m_bits.get_allocator();
 697 }
 698
 699 //-----------------------------------------------------------------------------
 700 // size changing operations
 701
 702 template <typename Block, typename Allocator>
 703 void dynamic_bitset<Block, Allocator>::
 704 resize(size_type num_bits, bool value) // strong guarantee
 705 {
 706
 707   const size_type old_num_blocks = num_blocks();
 708   const size_type required_blocks = calc_num_blocks(num_bits);
 709
 710   const block_type v = value? ~Block(0) : Block(0);
 711
 712   if (required_blocks != old_num_blocks) {
 713     m_bits.resize(required_blocks, v); // s.g. (copy)
 714   }
 715
 716
 717   // At this point:
 718   //
 719   //  - if the buffer was shrunk, we have nothing more to do,
 720   //    except a call to m_zero_unused_bits()
 721   //
 722   //  - if it was enlarged, all the (used) bits in the new blocks have
 723   //    the correct value, but we have not yet touched those bits, if
 724   //    any, that were 'unused bits' before enlarging: if value == true,
 725   //    they must be set.
 726
 727   if (value && (num_bits > m_num_bits)) {
 728
 729     const block_width_type extra_bits = count_extra_bits();
 730     if (extra_bits) {
 731         assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());
 732
 733         // Set them.
 734         m_bits[old_num_blocks - 1] |= (v << extra_bits);
 735     }
 736
 737   }
 738
 739   m_num_bits = num_bits;
 740   m_zero_unused_bits();
 741
 742 }
 743
 744 template <typename Block, typename Allocator>
 745 void dynamic_bitset<Block, Allocator>::
 746 clear() // no throw
 747 {
 748   m_bits.clear();
 749   m_num_bits = 0;
 750 }
 751
 752
 753 template <typename Block, typename Allocator>
 754 void dynamic_bitset<Block, Allocator>::
 755 push_back(bool bit)
 756 {
 757   const size_type sz = size();
 758   resize(sz + 1);
 759   set(sz, bit);
 760 }
 761
 762 template <typename Block, typename Allocator>
 763 void dynamic_bitset<Block, Allocator>::
 764 pop_back()
 765 {
 766   const size_type old_num_blocks = num_blocks();
 767   const size_type required_blocks = calc_num_blocks(m_num_bits - 1);
 768
 769   if (required_blocks != old_num_blocks) {
 770     m_bits.pop_back();
 771   }
 772
 773   --m_num_bits;
 774   m_zero_unused_bits();
 775 }
 776
 777
 778 template <typename Block, typename Allocator>
 779 void dynamic_bitset<Block, Allocator>::
 780 append(Block value) // strong guarantee
 781 {
 782     const block_width_type r = count_extra_bits();
 783
 784     if (r == 0) {
 785         // the buffer is empty, or all blocks are filled
 786         m_bits.push_back(value);
 787     }
 788     else {
 789         m_bits.push_back(value >> (bits_per_block - r));
 790         m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2
 791     }
 792
 793     m_num_bits += bits_per_block;
 794     assert(m_check_invariants());
 795
 796 }
 797
 798
 799 //-----------------------------------------------------------------------------
 800 // bitset operations
 801 template <typename Block, typename Allocator>
 802 dynamic_bitset<Block, Allocator>&
 803 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)
 804 {
 805     assert(size() == rhs.size());
 806     for (size_type i = 0; i < num_blocks(); ++i)
 807         m_bits[i] &= rhs.m_bits[i];
 808     return *this;
 809 }
 810
 811 template <typename Block, typename Allocator>
 812 dynamic_bitset<Block, Allocator>&
 813 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)
 814 {
 815     assert(size() == rhs.size());
 816     for (size_type i = 0; i < num_blocks(); ++i)
 817         m_bits[i] |= rhs.m_bits[i];
 818     //m_zero_unused_bits();
 819     return *this;
 820 }
 821
 822 template <typename Block, typename Allocator>
 823 dynamic_bitset<Block, Allocator>&
 824 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)
 825 {
 826     assert(size() == rhs.size());
 827     for (size_type i = 0; i < this->num_blocks(); ++i)
 828         m_bits[i] ^= rhs.m_bits[i];
 829     //m_zero_unused_bits();
 830     return *this;
 831 }
 832
 833 template <typename Block, typename Allocator>
 834 dynamic_bitset<Block, Allocator>&
 835 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)
 836 {
 837     assert(size() == rhs.size());
 838     for (size_type i = 0; i < num_blocks(); ++i)
 839         m_bits[i] &= ~rhs.m_bits[i];
 840     //m_zero_unused_bits();
 841     return *this;
 842 }
 843
 844 //
 845 // NOTE:
 846 //  Note that the 'if (r != 0)' is crucial to avoid undefined
 847 //  behavior when the left hand operand of >> isn't promoted to a
 848 //  wider type (because rs would be too large).
 849 //
 850 template <typename Block, typename Allocator>
 851 dynamic_bitset<Block, Allocator>&
 852 dynamic_bitset<Block, Allocator>::operator<<=(size_type n)
 853 {
 854     if (n >= m_num_bits)
 855         return reset();
 856     //else
 857     if (n > 0) {
 858
 859         size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1
 860         size_type    const div  = n / bits_per_block; // div is <= last
 861         block_width_type const r = bit_index(n);
 862         block_type * const b    = &m_bits[0];
 863
 864         if (r != 0) {
 865
 866             block_width_type const rs = bits_per_block - r;
 867
 868             for (size_type i = last-div; i>0; --i) {
 869                 b[i+div] = (b[i] << r) | (b[i-1] >> rs);
 870             }
 871             b[div] = b[0] << r;
 872
 873         }
 874         else {
 875             for (size_type i = last-div; i>0; --i) {
 876                 b[i+div] = b[i];
 877             }
 878             b[div] = b[0];
 879         }
 880
 881         // zero out div blocks at the less significant end
 882         std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
 883
 884         // zero out any 1 bit that flowed into the unused part
 885         m_zero_unused_bits(); // thanks to Lester Gong
 886
 887     }
 888
 889     return *this;
 890
 891
 892 }
 893
 894
 895 //
 896 // NOTE:
 897 //  see the comments to operator <<=
 898 //
 899 template <typename B, typename A>
 900 dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {
 901     if (n >= m_num_bits) {
 902         return reset();
 903     }
 904     //else
 905     if (n>0) {
 906
 907         size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1
 908         size_type  const div   = n / bits_per_block;   // div is <= last
 909         block_width_type const r     = bit_index(n);
 910         block_type * const b   = &m_bits[0];
 911
 912
 913         if (r != 0) {
 914
 915             block_width_type const ls = bits_per_block - r;
 916
 917             for (size_type i = div; i < last; ++i) {
 918                 b[i-div] = (b[i] >> r) | (b[i+1]  << ls);
 919             }
 920             // r bits go to zero
 921             b[last-div] = b[last] >> r;
 922         }
 923
 924         else {
 925             for (size_type i = div; i <= last; ++i) {
 926                 b[i-div] = b[i];
 927             }
 928             // note the '<=': the last iteration 'absorbs'
 929             // b[last-div] = b[last] >> 0;
 930         }
 931
 932
 933
 934         // div blocks are zero filled at the most significant end
 935         std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
 936     }
 937
 938     return *this;
 939 }
 940
 941
 942 template <typename Block, typename Allocator>
 943 dynamic_bitset<Block, Allocator>
 944 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const
 945 {
 946     dynamic_bitset r(*this);
 947     return r <<= n;
 948 }
 949
 950 template <typename Block, typename Allocator>
 951 dynamic_bitset<Block, Allocator>
 952 dynamic_bitset<Block, Allocator>::operator>>(size_type n) const
 953 {
 954     dynamic_bitset r(*this);
 955     return r >>= n;
 956 }
 957
 958
 959 //-----------------------------------------------------------------------------
 960 // basic bit operations
 961
 962 template <typename Block, typename Allocator>
 963 dynamic_bitset<Block, Allocator>&
 964 dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)
 965 {
 966     assert(pos < m_num_bits);
 967
 968     if (val)
 969         m_bits[block_index(pos)] |= bit_mask(pos);
 970     else
 971         reset(pos);
 972
 973     return *this;
 974 }
 975
 976 template <typename Block, typename Allocator>
 977 dynamic_bitset<Block, Allocator>&
 978 dynamic_bitset<Block, Allocator>::set()
 979 {
 980   std::fill(m_bits.begin(), m_bits.end(), static_cast<Block>(~0));
 981   m_zero_unused_bits();
 982   return *this;
 983 }
 984
 985 template <typename Block, typename Allocator>
 986 dynamic_bitset<Block, Allocator>&
 987 dynamic_bitset<Block, Allocator>::reset(size_type pos)
 988 {
 989     assert(pos < m_num_bits);
 990 #if defined __MWERKS__ && BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
 991     // CodeWarrior 8 generates incorrect code when the &=~ is compiled,
 992     // use the |^ variation instead.. <grafik>
 993     m_bits[block_index(pos)] |= bit_mask(pos);
 994     m_bits[block_index(pos)] ^= bit_mask(pos);
 995 #else
 996     m_bits[block_index(pos)] &= ~bit_mask(pos);
 997 #endif
 998     return *this;
 999 }
1000
1001 template <typename Block, typename Allocator>
1002 dynamic_bitset<Block, Allocator>&
1003 dynamic_bitset<Block, Allocator>::reset()
1004 {
1005   std::fill(m_bits.begin(), m_bits.end(), Block(0));
1006   return *this;
1007 }
1008
1009 template <typename Block, typename Allocator>
1010 dynamic_bitset<Block, Allocator>&
1011 dynamic_bitset<Block, Allocator>::flip(size_type pos)
1012 {
1013     assert(pos < m_num_bits);
1014     m_bits[block_index(pos)] ^= bit_mask(pos);
1015     return *this;
1016 }
1017
1018 template <typename Block, typename Allocator>
1019 dynamic_bitset<Block, Allocator>&
1020 dynamic_bitset<Block, Allocator>::flip()
1021 {
1022     for (size_type i = 0; i < num_blocks(); ++i)
1023         m_bits[i] = ~m_bits[i];
1024     m_zero_unused_bits();
1025     return *this;
1026 }
1027
1028 template <typename Block, typename Allocator>
1029 bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const
1030 {
1031     return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;
1032 }
1033
1034 template <typename Block, typename Allocator>
1035 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const
1036 {
1037     assert(pos < m_num_bits);
1038     return m_unchecked_test(pos);
1039 }
1040
1041 template <typename Block, typename Allocator>
1042 bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
1043 {
1044     bool const b = test(pos);
1045     if (b != val) {
1046         set(pos, val);
1047     }
1048     return b;
1049 }
1050
1051 template <typename Block, typename Allocator>
1052 bool dynamic_bitset<Block, Allocator>::all() const
1053 {
1054     if (empty()) {
1055         return true;
1056     }
1057
1058     const block_width_type extra_bits = count_extra_bits();
1059     block_type const all_ones = static_cast<Block>(~0);
1060
1061     if (extra_bits == 0) {
1062         for (size_type i = 0, e = num_blocks(); i < e; ++i) {
1063             if (m_bits[i] != all_ones) {
1064                 return false;
1065             }
1066         }
1067     } else {
1068         for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
1069             if (m_bits[i] != all_ones) {
1070                 return false;
1071             }
1072         }
1073         block_type const mask = ~(~static_cast<Block>(0) << extra_bits);
1074         if (m_highest_block() != mask) {
1075             return false;
1076         }
1077     }
1078     return true;
1079 }
1080
1081 template <typename Block, typename Allocator>
1082 bool dynamic_bitset<Block, Allocator>::any() const
1083 {
1084     for (size_type i = 0; i < num_blocks(); ++i)
1085         if (m_bits[i])
1086             return true;
1087     return false;
1088 }
1089
1090 template <typename Block, typename Allocator>
1091 inline bool dynamic_bitset<Block, Allocator>::none() const
1092 {
1093     return !any();
1094 }
1095
1096 template <typename Block, typename Allocator>
1097 dynamic_bitset<Block, Allocator>
1098 dynamic_bitset<Block, Allocator>::operator~() const
1099 {
1100     dynamic_bitset b(*this);
1101     b.flip();
1102     return b;
1103 }
1104
1105 template <typename Block, typename Allocator>
1106 typename dynamic_bitset<Block, Allocator>::size_type
1107 dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
1108 {
1109     using detail::dynamic_bitset_impl::table_width;
1110     using detail::dynamic_bitset_impl::access_by_bytes;
1111     using detail::dynamic_bitset_impl::access_by_blocks;
1112     using detail::dynamic_bitset_impl::value_to_type;
1113
1114 #if BOOST_WORKAROUND(__GNUC__, == 4) && (__GNUC_MINOR__ == 3) && (__GNUC_PATCHLEVEL__ == 3)
1115     // NOTE: Explicit qualification of "bits_per_block"
1116     //       breaks compilation on gcc 4.3.3
1117     enum { no_padding = bits_per_block == CHAR_BIT * sizeof(Block) };
1118 #else
1119     // NOTE: Explicitly qualifying "bits_per_block" to workaround
1120     //       regressions of gcc 3.4.x
1121     enum { no_padding =
1122         dynamic_bitset<Block, Allocator>::bits_per_block
1123         == CHAR_BIT * sizeof(Block) };
1124 #endif
1125
1126     enum { enough_table_width = table_width >= CHAR_BIT };
1127
1128     enum { mode = (no_padding && enough_table_width)
1129                           ? access_by_bytes
1130                           : access_by_blocks };
1131
1132     return do_count(m_bits.begin(), num_blocks(), Block(0),
1133                     static_cast<value_to_type<(bool)mode> *>(0));
1134 }
1135
1136
1137 //-----------------------------------------------------------------------------
1138 // conversions
1139
1140
1141 template <typename B, typename A, typename stringT>
1142 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,
1143                       bool dump_all)
1144 {
1145     typedef typename stringT::traits_type Tr;
1146     typedef typename stringT::value_type  Ch;
1147
1148     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());
1149     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1150     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1151
1152     // Note that this function may access (when
1153     // dump_all == true) bits beyond position size() - 1
1154
1155     typedef typename dynamic_bitset<B, A>::size_type size_type;
1156
1157     const size_type len = dump_all?
1158          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():
1159          b.size();
1160     s.assign (len, zero);
1161
1162     for (size_type i = 0; i < len; ++i) {
1163         if (b.m_unchecked_test(i))
1164             Tr::assign(s[len - 1 - i], one);
1165
1166     }
1167
1168 }
1169
1170
1171 // A comment similar to the one about the constructor from
1172 // basic_string can be done here. Thanks to James Kanze for
1173 // making me (Gennaro) realize this important separation of
1174 // concerns issue, as well as many things about i18n.
1175 //
1176 template <typename Block, typename Allocator, typename stringT>
1177 inline void
1178 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)
1179 {
1180     to_string_helper(b, s, false);
1181 }
1182
1183
1184 // Differently from to_string this function dumps out
1185 // every bit of the internal representation (may be
1186 // useful for debugging purposes)
1187 //
1188 template <typename B, typename A, typename stringT>
1189 inline void
1190 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s)
1191 {
1192     to_string_helper(b, s, true /* =dump_all*/);
1193 }
1194
1195 template <typename Block, typename Allocator, typename BlockOutputIterator>
1196 inline void
1197 to_block_range(const dynamic_bitset<Block, Allocator>& b,
1198                BlockOutputIterator result)
1199 {
1200     // note how this copies *all* bits, including the
1201     // unused ones in the last block (which are zero)
1202     std::copy(b.m_bits.begin(), b.m_bits.end(), result);
1203 }
1204
1205 template <typename Block, typename Allocator>
1206 unsigned long dynamic_bitset<Block, Allocator>::
1207 to_ulong() const
1208 {
1209
1210   if (m_num_bits == 0)
1211       return 0; // convention
1212
1213   // Check for overflows. This may be a performance burden on very
1214   // large bitsets but is required by the specification, sorry
1215   if (find_next(ulong_width - 1) != npos)
1216     BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
1217
1218
1219   // Ok, from now on we can be sure there's no "on" bit
1220   // beyond the "allowed" positions
1221   typedef unsigned long result_type;
1222
1223   const size_type maximum_size =
1224             (std::min)(m_num_bits, static_cast<size_type>(ulong_width));
1225
1226   const size_type last_block = block_index( maximum_size - 1 );
1227
1228   assert((last_block * bits_per_block) < static_cast<size_type>(ulong_width));
1229
1230   result_type result = 0;
1231   for (size_type i = 0; i <= last_block; ++i) {
1232     const size_type offset = i * bits_per_block;
1233     result |= (static_cast<result_type>(m_bits[i]) << offset);
1234   }
1235
1236   return result;
1237 }
1238
1239 template <typename Block, typename Allocator>
1240 inline typename dynamic_bitset<Block, Allocator>::size_type
1241 dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
1242 {
1243     return m_num_bits;
1244 }
1245
1246 template <typename Block, typename Allocator>
1247 inline typename dynamic_bitset<Block, Allocator>::size_type
1248 dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
1249 {
1250     return m_bits.size();
1251 }
1252
1253 template <typename Block, typename Allocator>
1254 inline typename dynamic_bitset<Block, Allocator>::size_type
1255 dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
1256 {
1257     // Semantics of vector<>::max_size() aren't very clear
1258     // (see lib issue 197) and many library implementations
1259     // simply return dummy values, _unrelated_ to the underlying
1260     // allocator.
1261     //
1262     // Given these problems, I was tempted to not provide this
1263     // function at all but the user could need it if he provides
1264     // his own allocator.
1265     //
1266
1267     const size_type m = detail::dynamic_bitset_impl::
1268                         vector_max_size_workaround(m_bits);
1269
1270     return m <= (size_type(-1)/bits_per_block) ?
1271         m * bits_per_block :
1272         size_type(-1);
1273 }
1274
1275 template <typename Block, typename Allocator>
1276 inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
1277 {
1278   return size() == 0;
1279 }
1280
1281 template <typename Block, typename Allocator>
1282 inline typename dynamic_bitset<Block, Allocator>::size_type
1283 dynamic_bitset<Block, Allocator>::capacity() const BOOST_NOEXCEPT
1284 {
1285     return m_bits.capacity() * bits_per_block;
1286 }
1287
1288 template <typename Block, typename Allocator>
1289 inline void dynamic_bitset<Block, Allocator>::reserve(size_type num_bits)
1290 {
1291     m_bits.reserve(calc_num_blocks(num_bits));
1292 }
1293
1294 template <typename Block, typename Allocator>
1295 void dynamic_bitset<Block, Allocator>::shrink_to_fit()
1296 {
1297     if (m_bits.size() < m_bits.capacity()) {
1298       buffer_type(m_bits).swap(m_bits);
1299     }
1300 }
1301
1302 template <typename Block, typename Allocator>
1303 bool dynamic_bitset<Block, Allocator>::
1304 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1305 {
1306     assert(size() == a.size());
1307     for (size_type i = 0; i < num_blocks(); ++i)
1308         if (m_bits[i] & ~a.m_bits[i])
1309             return false;
1310     return true;
1311 }
1312
1313 template <typename Block, typename Allocator>
1314 bool dynamic_bitset<Block, Allocator>::
1315 is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
1316 {
1317     assert(size() == a.size());
1318     assert(num_blocks() == a.num_blocks());
1319
1320     bool proper = false;
1321     for (size_type i = 0; i < num_blocks(); ++i) {
1322         const Block & bt =   m_bits[i];
1323         const Block & ba = a.m_bits[i];
1324
1325         if (bt & ~ba)
1326             return false; // not a subset at all
1327         if (ba & ~bt)
1328             proper = true;
1329     }
1330     return proper;
1331 }
1332
1333 template <typename Block, typename Allocator>
1334 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
1335 {
1336     size_type common_blocks = num_blocks() < b.num_blocks()
1337                               ? num_blocks() : b.num_blocks();
1338
1339     for(size_type i = 0; i < common_blocks; ++i) {
1340         if(m_bits[i] & b.m_bits[i])
1341             return true;
1342     }
1343     return false;
1344 }
1345
1346 // --------------------------------
1347 // lookup
1348
1349
1350 // look for the first bit "on", starting
1351 // from the block with index first_block
1352 //
1353 template <typename Block, typename Allocator>
1354 typename dynamic_bitset<Block, Allocator>::size_type
1355 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
1356 {
1357     size_type i = first_block;
1358
1359     // skip null blocks
1360     while (i < num_blocks() && m_bits[i] == 0)
1361         ++i;
1362
1363     if (i >= num_blocks())
1364         return npos; // not found
1365
1366     return i * bits_per_block + static_cast<size_type>(boost::lowest_bit(m_bits[i]));
1367
1368 }
1369
1370
1371 template <typename Block, typename Allocator>
1372 typename dynamic_bitset<Block, Allocator>::size_type
1373 dynamic_bitset<Block, Allocator>::find_first() const
1374 {
1375     return m_do_find_from(0);
1376 }
1377
1378
1379 template <typename Block, typename Allocator>
1380 typename dynamic_bitset<Block, Allocator>::size_type
1381 dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
1382 {
1383
1384     const size_type sz = size();
1385     if (pos >= (sz-1) || sz == 0)
1386         return npos;
1387
1388     ++pos;
1389
1390     const size_type blk = block_index(pos);
1391     const block_width_type ind = bit_index(pos);
1392
1393     // shift bits upto one immediately after current
1394     const Block fore = m_bits[blk] >> ind;
1395
1396     return fore?
1397         pos + static_cast<size_type>(lowest_bit(fore))
1398         :
1399         m_do_find_from(blk + 1);
1400
1401 }
1402
1403
1404
1405 //-----------------------------------------------------------------------------
1406 // comparison
1407
1408 template <typename Block, typename Allocator>
1409 bool operator==(const dynamic_bitset<Block, Allocator>& a,
1410                 const dynamic_bitset<Block, Allocator>& b)
1411 {
1412     return (a.m_num_bits == b.m_num_bits)
1413            && (a.m_bits == b.m_bits);
1414 }
1415
1416 template <typename Block, typename Allocator>
1417 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
1418                        const dynamic_bitset<Block, Allocator>& b)
1419 {
1420     return !(a == b);
1421 }
1422
1423 template <typename Block, typename Allocator>
1424 bool operator<(const dynamic_bitset<Block, Allocator>& a,
1425                const dynamic_bitset<Block, Allocator>& b)
1426 {
1427 //    assert(a.size() == b.size());
1428
1429     typedef BOOST_DEDUCED_TYPENAME dynamic_bitset<Block, Allocator>::size_type size_type;
1430
1431     size_type asize(a.size());
1432     size_type bsize(b.size());
1433
1434     if (!bsize)
1435         {
1436         return false;
1437         }
1438     else if (!asize)
1439         {
1440         return true;
1441         }
1442     else if (asize == bsize)
1443         {
1444         for (size_type ii = a.num_blocks(); ii > 0; --ii)
1445             {
1446             size_type i = ii-1;
1447             if (a.m_bits[i] < b.m_bits[i])
1448                 return true;
1449             else if (a.m_bits[i] > b.m_bits[i])
1450                 return false;
1451             }
1452         return false;
1453         }
1454     else
1455         {
1456
1457         size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize));
1458
1459         for (size_type ii = 0; ii < leqsize; ++ii,--asize,--bsize)
1460             {
1461             size_type i = asize-1;
1462             size_type j = bsize-1;
1463             if (a[i] < b[j])
1464                 return true;
1465             else if (a[i] > b[j])
1466                 return false;
1467             }
1468         return (a.size() < b.size());
1469         }
1470 }
1471
1472 template <typename Block, typename Allocator>
1473 bool oplessthan(const dynamic_bitset<Block, Allocator>& a,
1474                const dynamic_bitset<Block, Allocator>& b)
1475 {
1476 //    assert(a.size() == b.size());
1477
1478     typedef BOOST_DEDUCED_TYPENAME dynamic_bitset<Block, Allocator>::size_type size_type;
1479
1480     size_type asize(a.num_blocks());
1481     size_type bsize(b.num_blocks());
1482     assert(asize == 3);
1483     assert(bsize == 4);
1484
1485     if (!bsize)
1486         {
1487         return false;
1488         }
1489     else if (!asize)
1490         {
1491         return true;
1492         }
1493     else
1494         {
1495
1496         size_type leqsize(std::min BOOST_PREVENT_MACRO_SUBSTITUTION(asize,bsize));
1497         assert(leqsize == 3);
1498
1499         //if (a.size() == 0)
1500         //  return false;
1501
1502         // Since we are storing the most significant bit
1503         // at pos == size() - 1, we need to do the comparisons in reverse.
1504         //
1505         for (size_type ii = 0; ii < leqsize; ++ii,--asize,--bsize)
1506             {
1507             size_type i = asize-1;
1508             size_type j = bsize-1;
1509             if (a.m_bits[i] < b.m_bits[j])
1510                 return true;
1511             else if (a.m_bits[i] > b.m_bits[j])
1512                 return false;
1513             }
1514         return (a.num_blocks() < b.num_blocks());
1515         }
1516 }
1517
1518 template <typename Block, typename Allocator>
1519 inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
1520                        const dynamic_bitset<Block, Allocator>& b)
1521 {
1522     return !(a > b);
1523 }
1524
1525 template <typename Block, typename Allocator>
1526 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
1527                       const dynamic_bitset<Block, Allocator>& b)
1528 {
1529     return b < a;
1530 }
1531
1532 template <typename Block, typename Allocator>
1533 inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
1534                        const dynamic_bitset<Block, Allocator>& b)
1535 {
1536     return !(a < b);
1537 }
1538
1539 //-----------------------------------------------------------------------------
1540 // stream operations
1541
1542 #ifdef BOOST_OLD_IOSTREAMS
1543 template < typename Block, typename Alloc>
1544 std::ostream&
1545 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
1546 {
1547     // NOTE: since this is aimed at "classic" iostreams, exception
1548     // masks on the stream are not supported. The library that
1549     // ships with gcc 2.95 has an exceptions() member function but
1550     // nothing is actually implemented; not even the class ios::failure.
1551
1552     using namespace std;
1553
1554     const ios::iostate ok = ios::goodbit;
1555     ios::iostate err = ok;
1556
1557     if (os.opfx()) {
1558
1559         //try
1560         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
1561
1562         const bitsetsize_type sz = b.size();
1563         std::streambuf * buf = os.rdbuf();
1564         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
1565             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz;
1566
1567         const char fill_char = os.fill();
1568         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
1569
1570         // if needed fill at left; pad is decresed along the way
1571         if (adjustfield != ios::left) {
1572             for (; 0 < npad; --npad)
1573                 if (fill_char != buf->sputc(fill_char)) {
1574                     err |= ios::failbit;
1575                     break;
1576                 }
1577         }
1578
1579         if (err == ok) {
1580             // output the bitset
1581             for (bitsetsize_type i = b.size(); 0 < i; --i) {
1582                 const char dig = b.test(i-1)? '1' : '0';
1583                 if (EOF == buf->sputc(dig)) {
1584                     err |= ios::failbit;
1585                     break;
1586                 }
1587             }
1588         }
1589
1590         if (err == ok) {
1591             // if needed fill at right
1592             for (; 0 < npad; --npad) {
1593                 if (fill_char != buf->sputc(fill_char)) {
1594                     err |= ios::failbit;
1595                     break;
1596                 }
1597             }
1598         }
1599
1600         os.osfx();
1601         os.width(0);
1602
1603     } // if opfx
1604
1605     if(err != ok)
1606         os.setstate(err); // assume this does NOT throw
1607     return os;
1608
1609 }
1610 #else
1611
1612 template <typename Ch, typename Tr, typename Block, typename Alloc>
1613 std::basic_ostream<Ch, Tr>&
1614 operator<<(std::basic_ostream<Ch, Tr>& os,
1615            const dynamic_bitset<Block, Alloc>& b)
1616 {
1617
1618     using namespace std;
1619
1620     const ios_base::iostate ok = ios_base::goodbit;
1621     ios_base::iostate err = ok;
1622
1623     typename basic_ostream<Ch, Tr>::sentry cerberos(os);
1624     if (cerberos) {
1625
1626         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
1627         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1628         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1629
1630         BOOST_TRY {
1631
1632             typedef typename dynamic_bitset<Block, Alloc>::size_type bitset_size_type;
1633             typedef basic_streambuf<Ch, Tr> buffer_type;
1634
1635             buffer_type * buf = os.rdbuf();
1636             // careful: os.width() is signed (and can be < 0)
1637             const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast<bitset_size_type>(os.width());
1638             streamsize npad = (width <= b.size()) ? 0 : width - b.size();
1639
1640             const Ch fill_char = os.fill();
1641             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
1642
1643             // if needed fill at left; pad is decreased along the way
1644             if (adjustfield != ios_base::left) {
1645                 for (; 0 < npad; --npad)
1646                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1647                           err |= ios_base::failbit;
1648                           break;
1649                     }
1650             }
1651
1652             if (err == ok) {
1653                 // output the bitset
1654                 for (bitset_size_type i = b.size(); 0 < i; --i) {
1655                     typename buffer_type::int_type
1656                         ret = buf->sputc(b.test(i-1)? one : zero);
1657                     if (Tr::eq_int_type(Tr::eof(), ret)) {
1658                         err |= ios_base::failbit;
1659                         break;
1660                     }
1661                 }
1662             }
1663
1664             if (err == ok) {
1665                 // if needed fill at right
1666                 for (; 0 < npad; --npad) {
1667                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
1668                         err |= ios_base::failbit;
1669                         break;
1670                     }
1671                 }
1672             }
1673
1674
1675             os.width(0);
1676
1677         } BOOST_CATCH (...) { // see std 27.6.1.1/4
1678             bool rethrow = false;
1679             BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END
1680
1681             if (rethrow)
1682                 BOOST_RETHROW;
1683         }
1684         BOOST_CATCH_END
1685     }
1686
1687     if(err != ok)
1688         os.setstate(err); // may throw exception
1689     return os;
1690
1691 }
1692 #endif
1693
1694
1695 #ifdef BOOST_OLD_IOSTREAMS
1696
1697     // A sentry-like class that calls isfx in its destructor.
1698     // "Necessary" because bit_appender::do_append may throw.
1699     class pseudo_sentry {
1700         std::istream & m_r;
1701         const bool m_ok;
1702     public:
1703         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
1704         ~pseudo_sentry() { m_r.isfx(); }
1705         operator bool() const { return m_ok; }
1706     };
1707
1708 template <typename Block, typename Alloc>
1709 std::istream&
1710 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
1711 {
1712
1713 // Extractor for classic IO streams (libstdc++ < 3.0)
1714 // ----------------------------------------------------//
1715 //  It's assumed that the stream buffer functions, and
1716 //  the stream's setstate() _cannot_ throw.
1717
1718
1719     typedef dynamic_bitset<Block, Alloc> bitset_type;
1720     typedef typename bitset_type::size_type size_type;
1721
1722     std::ios::iostate err = std::ios::goodbit;
1723     pseudo_sentry cerberos(is); // skips whitespaces
1724     if(cerberos) {
1725
1726         b.clear();
1727
1728         const std::streamsize w = is.width();
1729         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
1730                                                          ? static_cast<size_type>(w) : b.max_size();
1731         typename bitset_type::bit_appender appender(b);
1732         std::streambuf * buf = is.rdbuf();
1733         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
1734
1735             if (c == EOF) {
1736                 err |= std::ios::eofbit;
1737                 break;
1738             }
1739             else if (char(c) != '0' && char(c) != '1')
1740                 break; // non digit character
1741
1742             else {
1743                 BOOST_TRY {
1744                     appender.do_append(char(c) == '1');
1745                 }
1746                 BOOST_CATCH(...) {
1747                     is.setstate(std::ios::failbit); // assume this can't throw
1748                     BOOST_RETHROW;
1749                 }
1750                 BOOST_CATCH_END
1751             }
1752
1753         } // for
1754     }
1755
1756     is.width(0);
1757     if (b.size() == 0)
1758         err |= std::ios::failbit;
1759     if (err != std::ios::goodbit)
1760         is.setstate (err); // may throw
1761
1762     return is;
1763 }
1764
1765 #else // BOOST_OLD_IOSTREAMS
1766
1767 template <typename Ch, typename Tr, typename Block, typename Alloc>
1768 std::basic_istream<Ch, Tr>&
1769 operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
1770 {
1771
1772     using namespace std;
1773
1774     typedef dynamic_bitset<Block, Alloc> bitset_type;
1775     typedef typename bitset_type::size_type size_type;
1776
1777     const streamsize w = is.width();
1778     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
1779                                          static_cast<size_type>(w) : b.max_size();
1780
1781     ios_base::iostate err = ios_base::goodbit;
1782     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
1783     if(cerberos) {
1784
1785         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
1786         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
1787         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
1788         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
1789
1790         b.clear();
1791         BOOST_TRY {
1792             typename bitset_type::bit_appender appender(b);
1793             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
1794             typename Tr::int_type c = buf->sgetc();
1795             for( ; appender.get_count() < limit; c = buf->snextc() ) {
1796
1797                 if (Tr::eq_int_type(Tr::eof(), c)) {
1798                     err |= ios_base::eofbit;
1799                     break;
1800                 }
1801                 else {
1802                     const Ch to_c = Tr::to_char_type(c);
1803                     const bool is_one = Tr::eq(to_c, one);
1804
1805                     if (!is_one && !Tr::eq(to_c, zero))
1806                         break; // non digit character
1807
1808                     appender.do_append(is_one);
1809
1810                 }
1811
1812             } // for
1813         }
1814         BOOST_CATCH (...) {
1815             // catches from stream buf, or from vector:
1816             //
1817             // bits_stored bits have been extracted and stored, and
1818             // either no further character is extractable or we can't
1819             // append to the underlying vector (out of memory)
1820
1821             bool rethrow = false;   // see std 27.6.1.1/4
1822             BOOST_TRY { is.setstate(ios_base::badbit); }
1823             BOOST_CATCH(...) { rethrow = true; }
1824             BOOST_CATCH_END
1825
1826             if (rethrow)
1827                 BOOST_RETHROW;
1828
1829         }
1830         BOOST_CATCH_END
1831     }
1832
1833     is.width(0);
1834     if (b.size() == 0 /*|| !cerberos*/)
1835         err |= ios_base::failbit;
1836     if (err != ios_base::goodbit)
1837         is.setstate (err); // may throw
1838
1839     return is;
1840
1841 }
1842
1843
1844 #endif
1845
1846
1847 //-----------------------------------------------------------------------------
1848 // bitset operations
1849
1850 template <typename Block, typename Allocator>
1851 dynamic_bitset<Block, Allocator>
1852 operator&(const dynamic_bitset<Block, Allocator>& x,
1853           const dynamic_bitset<Block, Allocator>& y)
1854 {
1855     dynamic_bitset<Block, Allocator> b(x);
1856     return b &= y;
1857 }
1858
1859 template <typename Block, typename Allocator>
1860 dynamic_bitset<Block, Allocator>
1861 operator|(const dynamic_bitset<Block, Allocator>& x,
1862           const dynamic_bitset<Block, Allocator>& y)
1863 {
1864     dynamic_bitset<Block, Allocator> b(x);
1865     return b |= y;
1866 }
1867
1868 template <typename Block, typename Allocator>
1869 dynamic_bitset<Block, Allocator>
1870 operator^(const dynamic_bitset<Block, Allocator>& x,
1871           const dynamic_bitset<Block, Allocator>& y)
1872 {
1873     dynamic_bitset<Block, Allocator> b(x);
1874     return b ^= y;
1875 }
1876
1877 template <typename Block, typename Allocator>
1878 dynamic_bitset<Block, Allocator>
1879 operator-(const dynamic_bitset<Block, Allocator>& x,
1880           const dynamic_bitset<Block, Allocator>& y)
1881 {
1882     dynamic_bitset<Block, Allocator> b(x);
1883     return b -= y;
1884 }
1885
1886 //-----------------------------------------------------------------------------
1887 // namespace scope swap
1888
1889 template<typename Block, typename Allocator>
1890 inline void
1891 swap(dynamic_bitset<Block, Allocator>& left,
1892      dynamic_bitset<Block, Allocator>& right) // no throw
1893 {
1894     left.swap(right);
1895 }
1896
1897
1898 //-----------------------------------------------------------------------------
1899 // private (on conforming compilers) member functions
1900
1901
1902 template <typename Block, typename Allocator>
1903 inline typename dynamic_bitset<Block, Allocator>::size_type
1904 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
1905 {
1906     return num_bits / bits_per_block
1907            + static_cast<size_type>( num_bits % bits_per_block != 0 );
1908 }
1909
1910 // gives a reference to the highest block
1911 //
1912 template <typename Block, typename Allocator>
1913 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
1914 {
1915     return const_cast<Block &>
1916            (static_cast<const dynamic_bitset *>(this)->m_highest_block());
1917 }
1918
1919 // gives a const-reference to the highest block
1920 //
1921 template <typename Block, typename Allocator>
1922 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
1923 {
1924     assert(size() > 0 && num_blocks() > 0);
1925     return m_bits.back();
1926 }
1927
1928
1929 // If size() is not a multiple of bits_per_block
1930 // then not all the bits in the last block are used.
1931 // This function resets the unused bits (convenient
1932 // for the implementation of many member functions)
1933 //
1934 template <typename Block, typename Allocator>
1935 inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
1936 {
1937     assert (num_blocks() == calc_num_blocks(m_num_bits));
1938
1939     // if != 0 this is the number of bits used in the last block
1940     const block_width_type extra_bits = count_extra_bits();
1941
1942     if (extra_bits != 0)
1943         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
1944
1945 }
1946
1947 // check class invariants
1948 template <typename Block, typename Allocator>
1949 bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
1950 {
1951     const block_width_type extra_bits = count_extra_bits();
1952     if (extra_bits > 0) {
1953         block_type const mask = (~static_cast<Block>(0) << extra_bits);
1954         if ((m_highest_block() & mask) != 0)
1955             return false;
1956     }
1957     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
1958         return false;
1959
1960     return true;
1961
1962 }
1963
1964
1965 } // namespace boost
1966
1967
1968 #undef BOOST_BITSET_CHAR
1969
1970 #endif // include guard
1971