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