1 // --------------------------------------------------

     2 //

     3 // (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.

     4 // (C) Copyright Gennaro Prota                 2003 - 2004.

     5 //

     6 // Distributed under the Boost Software License, Version 1.0.

     7 //    (See accompanying file LICENSE_1_0.txt or copy at

     8 //          http://www.boost.org/LICENSE_1_0.txt)

     9 //

    10 // -----------------------------------------------------------

    11 

    12 //  See http://www.boost.org/libs/dynamic_bitset for documentation.

    13 

    14 

    15 

    16 #ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

    17 #define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

    18 

    19 #include <cassert>

    20 #include <string>

    21 #include <stdexcept>           // for std::overflow_error

    22 #include <algorithm>           // for std::swap, std::min, std::copy, std::fill

    23 #include <vector>

    24 #include <climits>             // for CHAR_BIT

    25 

    26 #include "boost/dynamic_bitset/config.hpp"

    27 

    28 #ifndef BOOST_NO_STD_LOCALE

    29 # include <locale> // G.P.S

    30 #endif

    31 

    32 #if defined(BOOST_OLD_IOSTREAMS)

    33 #  include <iostream.h>

    34 #  include <ctype.h> // for isspace

    35 #else

    36 #  include <istream>

    37 #  include <ostream>

    38 #endif

    39 

    40 #include "boost/dynamic_bitset_fwd.hpp"

    41 #include "boost/detail/dynamic_bitset.hpp"

    42 #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)

    43 #include "boost/static_assert.hpp"

    44 #include "boost/limits.hpp"

    45 #include "boost/pending/lowest_bit.hpp" // used by find_first/next

    46 

    47 

    48 namespace boost {

    49 

    50 template

    51 

    52 #if defined(BOOST_MSVC) && BOOST_WORKAROUND(BOOST_MSVC, <= 1300)  // 1300 == VC++ 7.0

    53    // VC++ (up to 7.0) wants the default arguments again

    54    <typename Block = unsigned long, typename Allocator = std::allocator<Block> >

    55 # else

    56    <typename Block, typename Allocator>

    57 # endif

    58 

    59 class dynamic_bitset

    60 {

    61   // Portability note: member function templates are defined inside

    62   // this class definition to avoid problems with VC++. Similarly,

    63   // with the member functions of nested classes.

    64 

    65   BOOST_STATIC_ASSERT(detail::dynamic_bitset_allowed_block_type<Block>::value);

    66 

    67 public:

    68     typedef Block block_type;

    69     typedef Allocator allocator_type;

    70     typedef std::size_t size_type;

    71     typedef int block_width_type; // gps

    72 

    73     BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));

    74     BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));

    75 

    76 

    77 public:

    78 

    79     // A proxy class to simulate lvalues of bit type.

    80     // Shouldn't it be private? [gps]

    81     //

    82     class reference

    83     {

    84         friend class dynamic_bitset<Block, Allocator>;

    85 

    86 

    87         // the one and only non-copy ctor

    88         reference(block_type & b, int pos)

    89             :m_block(b), m_mask(block_type(1) << pos)

    90         {}

    91 

    92         void operator&(); // left undefined

    93 

    94     public:

    95 

    96         // copy constructor: compiler generated

    97 

    98         operator bool() const { return (m_block & m_mask) != 0; }

    99         bool operator~() const { return (m_block & m_mask) == 0; }

   100 

   101         reference& flip() { do_flip(); return *this; }

   102 

   103         reference& operator=(bool x)               { do_assign(x);   return *this; } // for b[i] = x

   104         reference& operator=(const reference& rhs) { do_assign(rhs); return *this; } // for b[i] = b[j]

   105 

   106         reference& operator|=(bool x) { if  (x) do_set();   return *this; }

   107         reference& operator&=(bool x) { if (!x) do_reset(); return *this; }

   108         reference& operator^=(bool x) { if  (x) do_flip();  return *this; }

   109         reference& operator-=(bool x) { if  (x) do_reset(); return *this; }

   110 

   111      private:

   112         block_type & m_block;

   113         const block_type m_mask;

   114 

   115         void do_set() { m_block |= m_mask; }

   116         void do_reset() { m_block &= ~m_mask; }

   117         void do_flip() { m_block ^= m_mask; }

   118         void do_assign(bool x) { x? do_set() : do_reset(); }

   119     };

   120 

   121     typedef bool const_reference;

   122 

   123     // constructors, etc.

   124     explicit

   125     dynamic_bitset(const Allocator& alloc = Allocator());

   126 

   127     explicit

   128     dynamic_bitset(size_type num_bits, unsigned long value = 0,

   129                const Allocator& alloc = Allocator());

   130 

   131 

   132     // The presence of this constructor is a concession to ease of

   133     // use, especially for the novice user. A conversion from string

   134     // is, in most cases, formatting, and should be done by the standard

   135     // formatting convention: operator>>.

   136     //

   137     // NOTE:

   138     // Leave the parentheses around std::basic_string<CharT, Traits, Alloc>::npos.

   139     // g++ 3.2 requires them and probably the standard will - see core issue 325

   140     // NOTE 2: 

   141     // split into two constructors because of bugs in MSVC 6.0sp5 with STLport

   142 

   143     template <typename CharT, typename Traits, typename Alloc>

   144     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,

   145         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,

   146         typename std::basic_string<CharT, Traits, Alloc>::size_type n,

   147         size_type num_bits = npos,

   148         const Allocator& alloc = Allocator())

   149 

   150     :m_bits(alloc),

   151      m_num_bits(0)

   152     {

   153       init_from_string(s, pos, n, num_bits, alloc);

   154     }

   155 

   156     template <typename CharT, typename Traits, typename Alloc>

   157     explicit

   158     dynamic_bitset(const std::basic_string<CharT, Traits, Alloc>& s,

   159       typename std::basic_string<CharT, Traits, Alloc>::size_type pos = 0)

   160 

   161     :m_bits(Allocator()),

   162      m_num_bits(0)

   163     {

   164       init_from_string(s, pos, (std::basic_string<CharT, Traits, Alloc>::npos),

   165                        npos, Allocator());

   166     }

   167 

   168     // The first bit in *first is the least significant bit, and the

   169     // last bit in the block just before *last is the most significant bit.

   170     template <typename BlockInputIterator>

   171     dynamic_bitset(BlockInputIterator first, BlockInputIterator last,

   172                    const Allocator& alloc = Allocator())

   173 

   174     :m_bits(first, last, alloc),

   175      m_num_bits(m_bits.size() * bits_per_block)

   176     {}

   177 

   178 

   179     // copy constructor

   180     dynamic_bitset(const dynamic_bitset& b);

   181 

   182     ~dynamic_bitset();

   183 

   184     void swap(dynamic_bitset& b);

   185     dynamic_bitset& operator=(const dynamic_bitset& b);

   186 

   187     allocator_type get_allocator() const;

   188 

   189     // size changing operations

   190     void resize(size_type num_bits, bool value = false);

   191     void clear();

   192     void push_back(bool bit);

   193     void append(Block block);

   194 

   195     template <typename BlockInputIterator>

   196     void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)

   197     {

   198         std::vector<Block, Allocator> v(first, last);

   199         m_append(v.begin(), v.end(), std::random_access_iterator_tag());

   200     }

   201     template <typename BlockInputIterator>

   202     void m_append(BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag)

   203     {

   204         assert(first != last);

   205         block_width_type r = count_extra_bits();

   206         std::size_t d = boost::detail::distance(first, last);

   207         m_bits.reserve(num_blocks() + d);

   208         if (r == 0) {

   209             for( ; first != last; ++first)

   210                 m_bits.push_back(*first); // could use vector<>::insert()

   211         }

   212         else {

   213             m_highest_block() |= (*first << r);

   214             do {

   215                 Block b = *first >> (bits_per_block - r);

   216                 ++first;

   217                 m_bits.push_back(b | (first==last? 0 : *first << r));

   218             } while (first != last);

   219         }

   220         m_num_bits += bits_per_block * d;

   221     }

   222     template <typename BlockInputIterator>

   223     void append(BlockInputIterator first, BlockInputIterator last) // strong guarantee

   224     {

   225         if (first != last) {

   226             typename detail::iterator_traits<BlockInputIterator>::iterator_category cat;

   227             m_append(first, last, cat);

   228         }

   229     }

   230 

   231 

   232     // bitset operations

   233     dynamic_bitset& operator&=(const dynamic_bitset& b);

   234     dynamic_bitset& operator|=(const dynamic_bitset& b);

   235     dynamic_bitset& operator^=(const dynamic_bitset& b);

   236     dynamic_bitset& operator-=(const dynamic_bitset& b);

   237     dynamic_bitset& operator<<=(size_type n);

   238     dynamic_bitset& operator>>=(size_type n);

   239     dynamic_bitset operator<<(size_type n) const;

   240     dynamic_bitset operator>>(size_type n) const;

   241 

   242     // basic bit operations

   243     dynamic_bitset& set(size_type n, bool val = true);

   244     dynamic_bitset& set();

   245     dynamic_bitset& reset(size_type n);

   246     dynamic_bitset& reset();

   247     dynamic_bitset& flip(size_type n);

   248     dynamic_bitset& flip();

   249     bool test(size_type n) const;

   250     bool any() const;

   251     bool none() const;

   252     dynamic_bitset operator~() const;

   253     size_type count() const;

   254 

   255     // subscript

   256     reference operator[](size_type pos) {

   257         return reference(m_bits[block_index(pos)], bit_index(pos));

   258     }

   259     bool operator[](size_type pos) const { return test(pos); }

   260 

   261     unsigned long to_ulong() const;

   262 

   263     size_type size() const;

   264     size_type num_blocks() const;

   265     size_type max_size() const;

   266     bool empty() const;

   267 #if 0 // gps

   268     void reserve(size_type n);

   269     size_type capacity() const;

   270 #endif

   271 

   272     bool is_subset_of(const dynamic_bitset& a) const;

   273     bool is_proper_subset_of(const dynamic_bitset& a) const;

   274     bool intersects(const dynamic_bitset & a) const;

   275 

   276     // lookup

   277     size_type find_first() const;

   278     size_type find_next(size_type pos) const;

   279 

   280 

   281 #if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS

   282     // lexicographical comparison

   283     template <typename B, typename A>

   284     friend bool operator==(const dynamic_bitset<B, A>& a,

   285                            const dynamic_bitset<B, A>& b);

   286 

   287     template <typename B, typename A>

   288     friend bool operator<(const dynamic_bitset<B, A>& a,

   289                           const dynamic_bitset<B, A>& b);

   290 

   291 

   292     template <typename B, typename A, typename BlockOutputIterator>

   293     friend void to_block_range(const dynamic_bitset<B, A>& b,

   294                                BlockOutputIterator result);

   295 

   296     template <typename BlockIterator, typename B, typename A>

   297     friend void from_block_range(BlockIterator first, BlockIterator last,

   298                                  dynamic_bitset<B, A>& result);

   299 

   300 

   301     template <typename CharT, typename Traits, typename B, typename A>

   302     friend std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is,

   303                                                          dynamic_bitset<B, A>& b);

   304 

   305     template <typename B, typename A, typename stringT>

   306     friend void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s, bool dump_all);

   307 

   308 

   309 #endif

   310 

   311 

   312 private:

   313     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);

   314     typedef std::vector<block_type, allocator_type> buffer_type;

   315 

   316     void m_zero_unused_bits();

   317     bool m_check_invariants() const;

   318 

   319     size_type m_do_find_from(size_type first_block) const;

   320 

   321     block_width_type count_extra_bits() const { return bit_index(size()); }

   322     static size_type block_index(size_type pos) { return pos / bits_per_block; }

   323     static block_width_type bit_index(size_type pos) { return static_cast<int>(pos % bits_per_block); }

   324     static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }

   325 

   326     template <typename CharT, typename Traits, typename Alloc>

   327     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,

   328         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,

   329         typename std::basic_string<CharT, Traits, Alloc>::size_type n,

   330         size_type num_bits,

   331         const Allocator& alloc)

   332     {

   333         assert(pos <= s.size());

   334 

   335         typedef typename std::basic_string<CharT, Traits, Alloc> StrT;

   336         typedef typename StrT::traits_type Tr;

   337 

   338         const typename StrT::size_type rlen = (std::min)(n, s.size() - pos); // gps

   339         const size_type sz = ( num_bits != npos? num_bits : rlen);

   340         m_bits.resize(calc_num_blocks(sz));

   341         m_num_bits = sz;

   342 

   343 

   344         BOOST_DYNAMIC_BITSET_CTYPE_FACET(CharT, fac, std::locale());

   345         const CharT one = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');

   346 

   347         const size_type m = num_bits < rlen ? num_bits : rlen; // [gps]

   348         typename StrT::size_type i = 0;

   349         for( ; i < m; ++i) {

   350 

   351             const CharT c = s[(pos + m - 1) - i];

   352 

   353             assert( Tr::eq(c, one)

   354                     || Tr::eq(c, BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0')) );

   355 

   356             if (Tr::eq(c, one))

   357                 set(i);

   358 

   359         }

   360 

   361     }

   362 

   363 BOOST_DYNAMIC_BITSET_PRIVATE:

   364 

   365     bool m_unchecked_test(size_type pos) const;

   366     static size_type calc_num_blocks(size_type num_bits);

   367 

   368     Block&        m_highest_block();

   369     const Block&  m_highest_block() const;

   370 

   371     buffer_type m_bits; // [gps] to be renamed

   372     size_type   m_num_bits;

   373 

   374 

   375     class bit_appender;

   376     friend class bit_appender;

   377     class bit_appender {

   378       // helper for stream >>

   379       // Supplies to the lack of an efficient append at the less

   380       // significant end: bits are actually appended "at left" but

   381       // rearranged in the destructor. Everything works just as if

   382       // dynamic_bitset<> had an append_at_right() function (which

   383       // threw, in case, the same exceptions as push_back) except

   384       // that the function is actually called bit_appender::do_append().

   385       //

   386       dynamic_bitset & bs;

   387       size_type n;

   388       Block mask;

   389       Block * current;

   390     public:

   391         bit_appender(dynamic_bitset & r) : bs(r), n(0), mask(0), current(0) {}

   392         ~bit_appender() {

   393             // reverse the order of blocks, shift

   394             // if needed, and then resize

   395             //

   396             std::reverse(bs.m_bits.begin(), bs.m_bits.end());

   397             const block_width_type offs = bit_index(n);

   398             if (offs)

   399                 bs >>= (bits_per_block - offs);

   400             bs.resize(n); // doesn't enlarge, so can't throw

   401             assert(bs.m_check_invariants());

   402         }

   403         inline void do_append(bool value) {

   404 

   405             if (mask == 0) {

   406                 bs.append(Block(0));

   407                 current = &bs.m_highest_block();

   408                 mask = Block(1) << (bits_per_block - 1);

   409             }

   410 

   411             if(value)

   412                 *current |= mask;

   413 

   414             mask /= 2;

   415             ++n;

   416         }

   417         size_type get_count() const { return n; }

   418     };

   419 

   420 };

   421 

   422 #if BOOST_WORKAROUND( __IBMCPP__, <=600 )

   423 

   424 // Workaround for IBM's AIX platform.

   425 // See http://comments.gmane.org/gmane.comp.lib.boost.user/15331

   426 

   427 template<typename Block, typename Allocator>

   428 dynamic_bitset<Block, Allocator>::block_width_type const

   429 dynamic_bitset<Block, Allocator>::bits_per_block;

   430 

   431 template<typename Block, typename Allocator>

   432 dynamic_bitset<Block, Allocator>::block_width_type const

   433 dynamic_bitset<Block, Allocator>::ulong_width;

   434 

   435 #endif

   436 

   437 // Global Functions:

   438 

   439 // comparison

   440 template <typename Block, typename Allocator>

   441 bool operator!=(const dynamic_bitset<Block, Allocator>& a,

   442                 const dynamic_bitset<Block, Allocator>& b);

   443 

   444 template <typename Block, typename Allocator>

   445 bool operator<=(const dynamic_bitset<Block, Allocator>& a,

   446                 const dynamic_bitset<Block, Allocator>& b);

   447 

   448 template <typename Block, typename Allocator>

   449 bool operator>(const dynamic_bitset<Block, Allocator>& a,

   450                const dynamic_bitset<Block, Allocator>& b);

   451 

   452 template <typename Block, typename Allocator>

   453 bool operator>=(const dynamic_bitset<Block, Allocator>& a,

   454                 const dynamic_bitset<Block, Allocator>& b);

   455 

   456 // stream operators

   457 #ifdef BOOST_OLD_IOSTREAMS

   458 template <typename Block, typename Allocator>

   459 std::ostream& operator<<(std::ostream& os,

   460                          const dynamic_bitset<Block, Allocator>& b);

   461 

   462 template <typename Block, typename Allocator>

   463 std::istream& operator>>(std::istream& is, dynamic_bitset<Block,Allocator>& b);

   464 #else

   465 // NOTE: Digital Mars wants the same template parameter names

   466 //       here and in the definition! [last tested: 8.48.10]

   467 //

   468 template <typename Ch, typename Tr, typename Block, typename Alloc>

   469 std::basic_ostream<Ch, Tr>&

   470 operator<<(std::basic_ostream<Ch, Tr>& os,

   471            const dynamic_bitset<Block, Alloc>& b);

   472 

   473 template <typename Ch, typename Tr, typename Block, typename Alloc>

   474 std::basic_istream<Ch, Tr>&

   475 operator>>(std::basic_istream<Ch, Tr>& is,

   476            dynamic_bitset<Block, Alloc>& b);

   477 #endif

   478 

   479 // bitset operations

   480 template <typename Block, typename Allocator>

   481 dynamic_bitset<Block, Allocator>

   482 operator&(const dynamic_bitset<Block, Allocator>& b1,

   483           const dynamic_bitset<Block, Allocator>& b2);

   484 

   485 template <typename Block, typename Allocator>

   486 dynamic_bitset<Block, Allocator>

   487 operator|(const dynamic_bitset<Block, Allocator>& b1,

   488           const dynamic_bitset<Block, Allocator>& b2);

   489 

   490 template <typename Block, typename Allocator>

   491 dynamic_bitset<Block, Allocator>

   492 operator^(const dynamic_bitset<Block, Allocator>& b1,

   493           const dynamic_bitset<Block, Allocator>& b2);

   494 

   495 template <typename Block, typename Allocator>

   496 dynamic_bitset<Block, Allocator>

   497 operator-(const dynamic_bitset<Block, Allocator>& b1,

   498           const dynamic_bitset<Block, Allocator>& b2);

   499 

   500 // namespace scope swap

   501 template<typename Block, typename Allocator>

   502 void swap(dynamic_bitset<Block, Allocator>& b1,

   503           dynamic_bitset<Block, Allocator>& b2);

   504 

   505 

   506 template <typename Block, typename Allocator, typename stringT>

   507 void

   508 to_string(const dynamic_bitset<Block, Allocator>& b, stringT & s); // gps

   509 

   510 template <typename Block, typename Allocator, typename BlockOutputIterator>

   511 void

   512 to_block_range(const dynamic_bitset<Block, Allocator>& b,

   513                BlockOutputIterator result);

   514 

   515 

   516 // gps - check docs with Jeremy

   517 //

   518 template <typename BlockIterator, typename B, typename A>

   519 inline void

   520 from_block_range(BlockIterator first, BlockIterator last,

   521                  dynamic_bitset<B, A>& result)

   522 {

   523     // PRE: distance(first, last) <= numblocks()

   524     std::copy (first, last, result.m_bits.begin()); //[gps]

   525 }

   526 

   527 //=============================================================================

   528 // dynamic_bitset implementation

   529 

   530 

   531 //-----------------------------------------------------------------------------

   532 // constructors, etc.

   533 

   534 template <typename Block, typename Allocator>

   535 dynamic_bitset<Block, Allocator>::dynamic_bitset(const Allocator& alloc)

   536   : m_bits(alloc), m_num_bits(0)

   537 {

   538 

   539 }

   540 

   541 template <typename Block, typename Allocator>

   542 dynamic_bitset<Block, Allocator>::

   543 dynamic_bitset(size_type num_bits, unsigned long value, const Allocator& alloc)

   544   : m_bits(calc_num_blocks(num_bits), Block(0), alloc),

   545     m_num_bits(num_bits)

   546 {

   547 

   548   if (num_bits == 0)

   549       return;

   550 

   551   typedef unsigned long num_type;

   552 

   553   // cut off all bits in value that have pos >= num_bits, if any

   554   if (num_bits < static_cast<size_type>(ulong_width)) {

   555       const num_type mask = (num_type(1) << num_bits) - 1;

   556       value &= mask;

   557   }

   558 

   559   if (bits_per_block >= ulong_width) {

   560       m_bits[0] = static_cast<block_type>(value);

   561   }

   562   else {

   563       for(size_type i = 0; value != 0; ++i) {

   564 

   565           m_bits[i] = static_cast<block_type>(value);

   566           value >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(bits_per_block);

   567       }

   568   }

   569 

   570 }

   571 

   572 // copy constructor

   573 template <typename Block, typename Allocator>

   574 inline dynamic_bitset<Block, Allocator>::

   575 dynamic_bitset(const dynamic_bitset& b)

   576   : m_bits(b.m_bits), m_num_bits(b.m_num_bits)  // [gps]

   577 {

   578 

   579 }

   580 

   581 template <typename Block, typename Allocator>

   582 inline dynamic_bitset<Block, Allocator>::

   583 ~dynamic_bitset()

   584 {

   585     assert(m_check_invariants());

   586 }

   587 

   588 template <typename Block, typename Allocator>

   589 inline void dynamic_bitset<Block, Allocator>::

   590 swap(dynamic_bitset<Block, Allocator>& b) // no throw

   591 {

   592     std::swap(m_bits, b.m_bits);

   593     std::swap(m_num_bits, b.m_num_bits);

   594 }

   595 

   596 template <typename Block, typename Allocator>

   597 dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::

   598 operator=(const dynamic_bitset<Block, Allocator>& b)

   599 {

   600 #if 0 // gps

   601     dynamic_bitset<Block, Allocator> tmp(b);

   602     this->swap(tmp);

   603     return *this;

   604 #else

   605     m_bits = b.m_bits;

   606     m_num_bits = b.m_num_bits;

   607     return *this;

   608 #endif

   609 }

   610 

   611 template <typename Block, typename Allocator>

   612 inline typename dynamic_bitset<Block, Allocator>::allocator_type

   613 dynamic_bitset<Block, Allocator>::get_allocator() const

   614 {

   615     return m_bits.get_allocator();

   616 }

   617 

   618 //-----------------------------------------------------------------------------

   619 // size changing operations

   620 

   621 template <typename Block, typename Allocator>

   622 void dynamic_bitset<Block, Allocator>::

   623 resize(size_type num_bits, bool value) // strong guarantee

   624 {

   625 

   626   const size_type old_num_blocks = num_blocks();

   627   const size_type required_blocks = calc_num_blocks(num_bits);

   628 

   629   const block_type v = value? ~Block(0) : Block(0);

   630 

   631   if (required_blocks != old_num_blocks) {

   632     m_bits.resize(required_blocks, v); // s.g. (copy) [gps]

   633   }

   634 

   635 

   636   // At this point:

   637   //

   638   //  - if the buffer was shrunk, there's nothing to do, except

   639   //    a call to m_zero_unused_bits()

   640   //

   641   //  - if it it is enlarged, all the (used) bits in the new blocks have

   642   //    the correct value, but we should also take care of the bits,

   643   //    if any, that were 'unused bits' before enlarging: if value == true,

   644   //    they must be set.

   645 

   646   if (value && (num_bits > m_num_bits)) {

   647 

   648     const size_type extra_bits = count_extra_bits(); // gps

   649     if (extra_bits) {

   650         assert(old_num_blocks >= 1 && old_num_blocks <= m_bits.size());

   651 

   652         // Set them.

   653         m_bits[old_num_blocks - 1] |= (v << extra_bits); // gps

   654     }

   655 

   656   }

   657 

   658 

   659 

   660   m_num_bits = num_bits;

   661   m_zero_unused_bits();

   662 

   663 }

   664 

   665 template <typename Block, typename Allocator>

   666 void dynamic_bitset<Block, Allocator>::

   667 clear() // no throw

   668 {

   669   m_bits.clear();

   670   m_num_bits = 0;

   671 }

   672 

   673 

   674 template <typename Block, typename Allocator>

   675 void dynamic_bitset<Block, Allocator>::

   676 push_back(bool bit)

   677 {

   678   resize(size() + 1);

   679   set(size() - 1, bit);

   680 }

   681 

   682 template <typename Block, typename Allocator>

   683 void dynamic_bitset<Block, Allocator>::

   684 append(Block value) // strong guarantee

   685 {

   686     // G.P.S. to be reviewed...

   687 

   688     const block_width_type r = count_extra_bits();

   689 

   690     if (r == 0) {

   691         // the buffer is empty, or all blocks are filled

   692         m_bits.push_back(value);

   693     }

   694     else {

   695         m_bits.push_back(value >> (bits_per_block - r));

   696         m_bits[m_bits.size() - 2] |= (value << r); // m_bits.size() >= 2

   697     }

   698 

   699     m_num_bits += bits_per_block;

   700     assert(m_check_invariants());

   701 

   702 }

   703 

   704 

   705 //-----------------------------------------------------------------------------

   706 // bitset operations

   707 template <typename Block, typename Allocator>

   708 dynamic_bitset<Block, Allocator>&

   709 dynamic_bitset<Block, Allocator>::operator&=(const dynamic_bitset& rhs)

   710 {

   711     assert(size() == rhs.size());

   712     for (size_type i = 0; i < num_blocks(); ++i)

   713         m_bits[i] &= rhs.m_bits[i];

   714     return *this;

   715 }

   716 

   717 template <typename Block, typename Allocator>

   718 dynamic_bitset<Block, Allocator>&

   719 dynamic_bitset<Block, Allocator>::operator|=(const dynamic_bitset& rhs)

   720 {

   721     assert(size() == rhs.size());

   722     for (size_type i = 0; i < num_blocks(); ++i)

   723         m_bits[i] |= rhs.m_bits[i];

   724     //m_zero_unused_bits();

   725     return *this;

   726 }

   727 

   728 template <typename Block, typename Allocator>

   729 dynamic_bitset<Block, Allocator>&

   730 dynamic_bitset<Block, Allocator>::operator^=(const dynamic_bitset& rhs)

   731 {

   732     assert(size() == rhs.size());

   733     for (size_type i = 0; i < this->num_blocks(); ++i)

   734         m_bits[i] ^= rhs.m_bits[i];

   735     //m_zero_unused_bits();

   736     return *this;

   737 }

   738 

   739 template <typename Block, typename Allocator>

   740 dynamic_bitset<Block, Allocator>&

   741 dynamic_bitset<Block, Allocator>::operator-=(const dynamic_bitset& rhs)

   742 {

   743     assert(size() == rhs.size());

   744     for (size_type i = 0; i < num_blocks(); ++i)

   745         m_bits[i] &= ~rhs.m_bits[i];

   746     //m_zero_unused_bits();

   747     return *this;

   748 }

   749 

   750 //

   751 // NOTE:

   752 //  Note that the 'if (r != 0)' is crucial to avoid undefined

   753 //  behavior when the left hand operand of >> isn't promoted to a

   754 //  wider type (because rs would be too large).

   755 //

   756 template <typename Block, typename Allocator>

   757 dynamic_bitset<Block, Allocator>&

   758 dynamic_bitset<Block, Allocator>::operator<<=(size_type n)

   759 {

   760     if (n >= m_num_bits)

   761         return reset();

   762     //else

   763     if (n > 0) {

   764 

   765         size_type    const last = num_blocks() - 1;  // num_blocks() is >= 1

   766         size_type    const div  = n / bits_per_block; // div is <= last

   767         block_width_type const r = bit_index(n);

   768         block_type * const b    = &m_bits[0];

   769 

   770         if (r != 0) {

   771 

   772             block_width_type const rs = bits_per_block - r;

   773 

   774             for (size_type i = last-div; i>0; --i) {

   775                 b[i+div] = (b[i] << r) | (b[i-1] >> rs);

   776             }

   777             b[div] = b[0] << r;

   778 

   779         }

   780         else {

   781             for (size_type i = last-div; i>0; --i) {

   782                 b[i+div] = b[i];

   783             }

   784             b[div] = b[0];

   785         }

   786 

   787 

   788         // zero out div blocks at the less significant end

   789         std::fill_n(b, div, static_cast<block_type>(0));

   790 

   791         // zero out any 1 bit that flowed into the unused part

   792         m_zero_unused_bits(); // thanks to Lester Gong

   793 

   794 

   795     }

   796 

   797     return *this;

   798 

   799 

   800 }

   801 

   802 

   803 //

   804 // NOTE:

   805 //  see the comments to operator <<=

   806 //

   807 template <typename B, typename A>

   808 dynamic_bitset<B, A> & dynamic_bitset<B, A>::operator>>=(size_type n) {

   809     if (n >= m_num_bits) {

   810         return reset();

   811     }

   812     //else

   813     if (n>0) {

   814 

   815         size_type  const last  = num_blocks() - 1; // num_blocks() is >= 1

   816         size_type  const div   = n / bits_per_block;   // div is <= last

   817         block_width_type const r     = bit_index(n);

   818         block_type * const b   = &m_bits[0];

   819 

   820 

   821         if (r != 0) {

   822 

   823             block_width_type const ls = bits_per_block - r;

   824 

   825             for (size_type i = div; i < last; ++i) {

   826                 b[i-div] = (b[i] >> r) | (b[i+1]  << ls);

   827             }

   828             // r bits go to zero

   829             b[last-div] = b[last] >> r;

   830         }

   831 

   832         else {

   833             for (size_type i = div; i <= last; ++i) {

   834                 b[i-div] = b[i];

   835             }

   836             // note the '<=': the last iteration 'absorbs'

   837             // b[last-div] = b[last] >> 0;

   838         }

   839 

   840 

   841 

   842         // div blocks are zero filled at the most significant end

   843         std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));

   844     }

   845 

   846     return *this;

   847 }

   848 

   849 

   850 template <typename Block, typename Allocator>

   851 dynamic_bitset<Block, Allocator>

   852 dynamic_bitset<Block, Allocator>::operator<<(size_type n) const

   853 {

   854     dynamic_bitset r(*this);

   855     return r <<= n;

   856 }

   857 

   858 template <typename Block, typename Allocator>

   859 dynamic_bitset<Block, Allocator>

   860 dynamic_bitset<Block, Allocator>::operator>>(size_type n) const

   861 {

   862     dynamic_bitset r(*this);

   863     return r >>= n;

   864 }

   865 

   866 

   867 //-----------------------------------------------------------------------------

   868 // basic bit operations

   869 

   870 template <typename Block, typename Allocator>

   871 dynamic_bitset<Block, Allocator>&

   872 dynamic_bitset<Block, Allocator>::set(size_type pos, bool val)

   873 {

   874     // [gps]

   875     //

   876     // Below we have no set(size_type) function to call when

   877     // value == true; instead of using a helper, I think

   878     // overloading set (rather than giving it a default bool

   879     // argument) would be more elegant.

   880 

   881     assert(pos < m_num_bits);

   882 

   883     if (val)

   884         m_bits[block_index(pos)] |= bit_mask(pos);

   885     else

   886         reset(pos);

   887 

   888     return *this;

   889 }

   890 

   891 template <typename Block, typename Allocator>

   892 dynamic_bitset<Block, Allocator>&

   893 dynamic_bitset<Block, Allocator>::set()

   894 {

   895   std::fill(m_bits.begin(), m_bits.end(), ~Block(0));

   896   m_zero_unused_bits();

   897   return *this;

   898 }

   899 

   900 template <typename Block, typename Allocator>

   901 dynamic_bitset<Block, Allocator>&

   902 dynamic_bitset<Block, Allocator>::reset(size_type pos)

   903 {

   904     assert(pos < m_num_bits);

   905     #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x

   906     // CodeWarrior 8 generates incorrect code when the &=~ is compiled,

   907     // use the |^ variation instead.. <grafik>

   908     m_bits[block_index(pos)] |= bit_mask(pos);

   909     m_bits[block_index(pos)] ^= bit_mask(pos);

   910     #else

   911     m_bits[block_index(pos)] &= ~bit_mask(pos);

   912     #endif

   913     return *this;

   914 }

   915 

   916 template <typename Block, typename Allocator>

   917 dynamic_bitset<Block, Allocator>&

   918 dynamic_bitset<Block, Allocator>::reset()

   919 {

   920   std::fill(m_bits.begin(), m_bits.end(), Block(0));

   921   return *this;

   922 }

   923 

   924 template <typename Block, typename Allocator>

   925 dynamic_bitset<Block, Allocator>&

   926 dynamic_bitset<Block, Allocator>::flip(size_type pos)

   927 {

   928     assert(pos < m_num_bits);

   929     m_bits[block_index(pos)] ^= bit_mask(pos);

   930     return *this;

   931 }

   932 

   933 template <typename Block, typename Allocator>

   934 dynamic_bitset<Block, Allocator>&

   935 dynamic_bitset<Block, Allocator>::flip()

   936 {

   937     for (size_type i = 0; i < num_blocks(); ++i)

   938         m_bits[i] = ~m_bits[i];

   939     m_zero_unused_bits();

   940     return *this;

   941 }

   942 

   943 template <typename Block, typename Allocator>

   944 bool dynamic_bitset<Block, Allocator>::m_unchecked_test(size_type pos) const

   945 {

   946     return (m_bits[block_index(pos)] & bit_mask(pos)) != 0;

   947 }

   948 

   949 template <typename Block, typename Allocator>

   950 bool dynamic_bitset<Block, Allocator>::test(size_type pos) const

   951 {

   952     assert(pos < m_num_bits);

   953     return m_unchecked_test(pos);

   954 }

   955 

   956 template <typename Block, typename Allocator>

   957 bool dynamic_bitset<Block, Allocator>::any() const

   958 {

   959     for (size_type i = 0; i < num_blocks(); ++i)

   960         if (m_bits[i])

   961             return true;

   962     return false;

   963 }

   964 

   965 template <typename Block, typename Allocator>

   966 inline bool dynamic_bitset<Block, Allocator>::none() const

   967 {

   968     return !any();

   969 }

   970 

   971 template <typename Block, typename Allocator>

   972 dynamic_bitset<Block, Allocator>

   973 dynamic_bitset<Block, Allocator>::operator~() const

   974 {

   975     dynamic_bitset b(*this);

   976     b.flip();

   977     return b;

   978 }

   979 

   980 

   981 /*

   982 

   983 The following is the straightforward implementation of count(), which

   984 we leave here in a comment for documentation purposes.

   985 

   986 template <typename Block, typename Allocator>

   987 typename dynamic_bitset<Block, Allocator>::size_type

   988 dynamic_bitset<Block, Allocator>::count() const

   989 {

   990     size_type sum = 0;

   991     for (size_type i = 0; i != this->m_num_bits; ++i)

   992         if (test(i))

   993             ++sum;

   994     return sum;

   995 }

   996 

   997 The actual algorithm uses a lookup table.

   998 

   999 

  1000   The basic idea of the method is to pick up X bits at a time

  1001   from the internal array of blocks and consider those bits as

  1002   the binary representation of a number N. Then, to use a table

  1003   of 1<<X elements where table[N] is the number of '1' digits

  1004   in the binary representation of N (i.e. in our X bits).

  1005 

  1006 

  1007   In this implementation X is 8 (but can be easily changed: you

  1008   just have to modify the definition of table_width and shrink/enlarge

  1009   the table accordingly - it could be useful, for instance, to expand

  1010   the table to 512 elements on an implementation with 9-bit bytes) and

  1011   the internal array of blocks is seen, if possible, as an array of bytes.

  1012   In practice the "reinterpretation" as array of bytes is possible if and

  1013   only if X >= CHAR_BIT and Block has no padding bits (that would be counted

  1014   together with the "real ones" if we saw the array as array of bytes).

  1015   Otherwise we simply 'extract' X bits at a time from each Block.

  1016 

  1017 */

  1018 

  1019 

  1020 template <typename Block, typename Allocator>

  1021 typename dynamic_bitset<Block, Allocator>::size_type

  1022 dynamic_bitset<Block, Allocator>::count() const

  1023 {

  1024     using namespace detail::dynamic_bitset_count_impl;

  1025 

  1026     const bool no_padding = bits_per_block == CHAR_BIT * sizeof(Block);

  1027     const bool enough_table_width = table_width >= CHAR_BIT;

  1028 

  1029     typedef mode_to_type< (no_padding && enough_table_width ?

  1030                           access_by_bytes : access_by_blocks) > m;

  1031 

  1032     return do_count(m_bits.begin(), num_blocks(), Block(0), static_cast<m*>(0));

  1033 

  1034 }

  1035 

  1036 

  1037 //-----------------------------------------------------------------------------

  1038 // conversions

  1039 

  1040 

  1041 template <typename B, typename A, typename stringT>

  1042 void to_string_helper(const dynamic_bitset<B, A> & b, stringT & s,

  1043                       bool dump_all)

  1044 {

  1045     typedef typename stringT::traits_type Tr;

  1046     typedef typename stringT::value_type  Ch;

  1047 

  1048     BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, std::locale());

  1049     const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');

  1050     const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');

  1051 

  1052     // Note that this function may access (when

  1053     // dump_all == true) bits beyond position size() - 1

  1054 

  1055     typedef typename dynamic_bitset<B, A>::size_type size_type;

  1056 

  1057     const size_type len = dump_all?

  1058          dynamic_bitset<B, A>::bits_per_block * b.num_blocks():

  1059          b.size();

  1060     s.assign (len, zero);

  1061 

  1062     for (size_type i = 0; i < len; ++i) {

  1063         if (b.m_unchecked_test(i))

  1064             Tr::assign(s[len - 1 - i], one);

  1065 

  1066     }

  1067 

  1068 }

  1069 

  1070 

  1071 // A comment similar to the one about the constructor from

  1072 // basic_string can be done here. Thanks to James Kanze for

  1073 // making me (Gennaro) realize this important separation of

  1074 // concerns issue, as well as many things about i18n.

  1075 //

  1076 template <typename Block, typename Allocator, typename stringT> // G.P.S.

  1077 inline void

  1078 to_string(const dynamic_bitset<Block, Allocator>& b, stringT& s)

  1079 {

  1080     to_string_helper(b, s, false);

  1081 }

  1082 

  1083 

  1084 // Differently from to_string this function dumps out

  1085 // every bit of the internal representation (may be

  1086 // useful for debugging purposes)

  1087 //

  1088 template <typename B, typename A, typename stringT>

  1089 inline void

  1090 dump_to_string(const dynamic_bitset<B, A>& b, stringT& s) // G.P.S.

  1091 {

  1092     to_string_helper(b, s, true /* =dump_all*/);

  1093 }

  1094 

  1095 template <typename Block, typename Allocator, typename BlockOutputIterator>

  1096 inline void

  1097 to_block_range(const dynamic_bitset<Block, Allocator>& b,

  1098                BlockOutputIterator result)

  1099 {

  1100     // note how this copies *all* bits, including the

  1101     // unused ones in the last block (which are zero)

  1102     std::copy(b.m_bits.begin(), b.m_bits.end(), result); // [gps]

  1103 }

  1104 

  1105 template <typename Block, typename Allocator>

  1106 unsigned long dynamic_bitset<Block, Allocator>::

  1107 to_ulong() const

  1108 {

  1109 

  1110   if (m_num_bits == 0)

  1111       return 0; // convention

  1112 

  1113   // Check for overflows. This may be a performance burden on very

  1114   // large bitsets but is required by the specification, sorry

  1115   if (find_next(ulong_width - 1) != npos)

  1116     throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");

  1117 

  1118 

  1119   // Ok, from now on we can be sure there's no "on" bit beyond

  1120   // the allowed positions

  1121 

  1122   if (bits_per_block >= ulong_width)

  1123       return m_bits[0];

  1124 

  1125 

  1126   size_type last_block = block_index((std::min)(m_num_bits-1, // gps

  1127                                     (size_type)(ulong_width-1)));

  1128   unsigned long result = 0;

  1129   for (size_type i = 0; i <= last_block; ++i) {

  1130 

  1131     assert((size_type)bits_per_block * i < (size_type)ulong_width); // gps

  1132 

  1133     unsigned long piece = m_bits[i];

  1134     result |= (piece << (bits_per_block * i));

  1135   }