epoc32/include/stdapis/boost/dynamic_bitset/dynamic_bitset.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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   }
  1136 
  1137   return result;
  1138 
  1139 }
  1140 
  1141 
  1142 template <typename Block, typename Allocator>
  1143 inline typename dynamic_bitset<Block, Allocator>::size_type
  1144 dynamic_bitset<Block, Allocator>::size() const
  1145 {
  1146     return m_num_bits;
  1147 }
  1148 
  1149 template <typename Block, typename Allocator>
  1150 inline typename dynamic_bitset<Block, Allocator>::size_type
  1151 dynamic_bitset<Block, Allocator>::num_blocks() const
  1152 {
  1153     return m_bits.size();
  1154 }
  1155 
  1156 template <typename Block, typename Allocator>
  1157 inline typename dynamic_bitset<Block, Allocator>::size_type
  1158 dynamic_bitset<Block, Allocator>::max_size() const
  1159 {
  1160     // Semantics of vector<>::max_size() aren't very clear
  1161     // (see lib issue 197) and many library implementations
  1162     // simply return dummy values, _unrelated_ to the underlying
  1163     // allocator.
  1164     //
  1165     // Given these problems, I was tempted to not provide this
  1166     // function at all but the user could need it if he provides
  1167     // his own allocator.
  1168     //
  1169 
  1170     const size_type m = detail::vector_max_size_workaround(m_bits);
  1171 
  1172     return m <= (size_type(-1)/bits_per_block) ?
  1173         m * bits_per_block :
  1174         size_type(-1);
  1175 }
  1176 
  1177 template <typename Block, typename Allocator>
  1178 inline bool dynamic_bitset<Block, Allocator>::empty() const
  1179 {
  1180   return size() == 0;
  1181 }
  1182 
  1183 #if 0 // gps
  1184 template <typename Block, typename Allocator>
  1185 inline void dynamic_bitset<Block, Allocator>::reserve(size_type n)
  1186 {
  1187     assert(n <= max_size()); // PRE - G.P.S.
  1188     m_bits.reserve(calc_num_blocks(n));
  1189 }
  1190 
  1191 template <typename Block, typename Allocator>
  1192 typename dynamic_bitset<Block, Allocator>::size_type
  1193 dynamic_bitset<Block, Allocator>::capacity() const
  1194 {
  1195     // capacity is m_bits.capacity() * bits_per_block
  1196     // unless that one overflows
  1197     const size_type m = static_cast<size_type>(-1);
  1198     const size_type q = m / bits_per_block;
  1199 
  1200     const size_type c = m_bits.capacity();
  1201 
  1202     return c <= q ?
  1203         c * bits_per_block :
  1204         m;
  1205 }
  1206 #endif
  1207 
  1208 template <typename Block, typename Allocator>
  1209 bool dynamic_bitset<Block, Allocator>::
  1210 is_subset_of(const dynamic_bitset<Block, Allocator>& a) const
  1211 {
  1212     assert(size() == a.size());
  1213     for (size_type i = 0; i < num_blocks(); ++i)
  1214         if (m_bits[i] & ~a.m_bits[i])
  1215             return false;
  1216     return true;
  1217 }
  1218 
  1219 template <typename Block, typename Allocator>
  1220 bool dynamic_bitset<Block, Allocator>::
  1221 is_proper_subset_of(const dynamic_bitset<Block, Allocator>& a) const
  1222 {
  1223     assert(size() == a.size());
  1224     bool proper = false;
  1225     for (size_type i = 0; i < num_blocks(); ++i) {
  1226         Block bt = m_bits[i], ba = a.m_bits[i];
  1227         if (ba & ~bt)
  1228             proper = true;
  1229         if (bt & ~ba)
  1230             return false;
  1231     }
  1232     return proper;
  1233 }
  1234 
  1235 template <typename Block, typename Allocator>
  1236 bool dynamic_bitset<Block, Allocator>::intersects(const dynamic_bitset & b) const
  1237 {
  1238     size_type common_blocks = num_blocks() < b.num_blocks()
  1239                               ? num_blocks() : b.num_blocks();
  1240 
  1241     for(size_type i = 0; i < common_blocks; ++i) {
  1242         if(m_bits[i] & b.m_bits[i])
  1243             return true;
  1244     }
  1245     return false;
  1246 }
  1247 
  1248 // --------------------------------
  1249 // lookup
  1250 
  1251 
  1252 // look for the first bit "on", starting
  1253 // from the block with index first_block
  1254 //
  1255 template <typename Block, typename Allocator>
  1256 typename dynamic_bitset<Block, Allocator>::size_type
  1257 dynamic_bitset<Block, Allocator>::m_do_find_from(size_type first_block) const
  1258 {
  1259     size_type i = first_block;
  1260 
  1261     // skip null blocks
  1262     while (i < num_blocks() && m_bits[i] == 0)
  1263         ++i;
  1264 
  1265     if (i >= num_blocks())
  1266         return npos; // not found
  1267 
  1268     return i * bits_per_block + boost::lowest_bit(m_bits[i]);
  1269 
  1270 }
  1271 
  1272 
  1273 template <typename Block, typename Allocator>
  1274 typename dynamic_bitset<Block, Allocator>::size_type
  1275 dynamic_bitset<Block, Allocator>::find_first() const
  1276 {
  1277     return m_do_find_from(0);
  1278 }
  1279 
  1280 
  1281 template <typename Block, typename Allocator>
  1282 typename dynamic_bitset<Block, Allocator>::size_type
  1283 dynamic_bitset<Block, Allocator>::find_next(size_type pos) const
  1284 {
  1285 
  1286     const size_type sz = size();
  1287     if (pos >= (sz-1) || sz == 0)
  1288         return npos;
  1289 
  1290     ++pos;
  1291 
  1292     const size_type blk = block_index(pos);
  1293     const block_width_type ind = bit_index(pos);
  1294 
  1295     // mask out bits before pos
  1296     const Block fore = m_bits[blk] & ( ~Block(0) << ind );
  1297 
  1298     return fore?
  1299         blk * bits_per_block + lowest_bit(fore)
  1300         :
  1301         m_do_find_from(blk + 1);
  1302 
  1303 }
  1304 
  1305 
  1306 
  1307 //-----------------------------------------------------------------------------
  1308 // comparison
  1309 
  1310 template <typename Block, typename Allocator>
  1311 bool operator==(const dynamic_bitset<Block, Allocator>& a,
  1312                 const dynamic_bitset<Block, Allocator>& b)
  1313 {
  1314     return (a.m_num_bits == b.m_num_bits)
  1315            && (a.m_bits == b.m_bits); // [gps]
  1316 }
  1317 
  1318 template <typename Block, typename Allocator>
  1319 inline bool operator!=(const dynamic_bitset<Block, Allocator>& a,
  1320                        const dynamic_bitset<Block, Allocator>& b)
  1321 {
  1322     return !(a == b);
  1323 }
  1324 
  1325 template <typename Block, typename Allocator>
  1326 bool operator<(const dynamic_bitset<Block, Allocator>& a,
  1327                const dynamic_bitset<Block, Allocator>& b)
  1328 {
  1329     assert(a.size() == b.size());
  1330     typedef typename dynamic_bitset<Block, Allocator>::size_type size_type;
  1331 
  1332     if (a.size() == 0)
  1333       return false;
  1334 
  1335     // Since we are storing the most significant bit
  1336     // at pos == size() - 1, we need to do the comparisons in reverse.
  1337 
  1338     // Compare a block at a time
  1339     for (size_type i = a.num_blocks() - 1; i > 0; --i)
  1340       if (a.m_bits[i] < b.m_bits[i])
  1341         return true;
  1342       else if (a.m_bits[i] > b.m_bits[i])
  1343         return false;
  1344 
  1345     if (a.m_bits[0] < b.m_bits[0])
  1346       return true;
  1347     else
  1348       return false;
  1349 }
  1350 
  1351 template <typename Block, typename Allocator>
  1352 inline bool operator<=(const dynamic_bitset<Block, Allocator>& a,
  1353                        const dynamic_bitset<Block, Allocator>& b)
  1354 {
  1355     return !(a > b);
  1356 }
  1357 
  1358 template <typename Block, typename Allocator>
  1359 inline bool operator>(const dynamic_bitset<Block, Allocator>& a,
  1360                       const dynamic_bitset<Block, Allocator>& b)
  1361 {
  1362     return b < a;
  1363 }
  1364 
  1365 template <typename Block, typename Allocator>
  1366 inline bool operator>=(const dynamic_bitset<Block, Allocator>& a,
  1367                        const dynamic_bitset<Block, Allocator>& b)
  1368 {
  1369     return !(a < b);
  1370 }
  1371 
  1372 //-----------------------------------------------------------------------------
  1373 // stream operations
  1374 
  1375 #ifdef BOOST_OLD_IOSTREAMS
  1376 template < typename Block, typename Alloc>
  1377 std::ostream&
  1378 operator<<(std::ostream& os, const dynamic_bitset<Block, Alloc>& b)
  1379 {
  1380     // NOTE: since this is aimed at "classic" iostreams, exception
  1381     // masks on the stream are not supported. The library that
  1382     // ships with gcc 2.95 has an exceptions() member function but
  1383     // nothing is actually implemented; not even the class ios::failure.
  1384 
  1385     using namespace std;
  1386 
  1387     const ios::iostate ok = ios::goodbit;
  1388     ios::iostate err = ok;
  1389 
  1390     if (os.opfx()) { // gps
  1391 
  1392         //try
  1393         typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
  1394 
  1395         const bitsetsize_type sz = b.size();
  1396         std::streambuf * buf = os.rdbuf();
  1397         size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
  1398             || (bitsetsize_type) os.width() <= sz? 0 : os.width() - sz; //- gps
  1399 
  1400         const char fill_char = os.fill();
  1401         const ios::fmtflags adjustfield = os.flags() & ios::adjustfield;
  1402 
  1403         // if needed fill at left; pad is decresed along the way
  1404         if (adjustfield != ios::left) {
  1405             for (; 0 < npad; --npad)
  1406                 if (fill_char != buf->sputc(fill_char)) {
  1407                     err |= ios::failbit;   // gps
  1408                     break;
  1409                 }
  1410         }
  1411 
  1412         if (err == ok) {
  1413             // output the bitset
  1414             for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
  1415                 const char dig = b.test(i-1)? '1' : '0';
  1416                 if (EOF == buf->sputc(dig)) { // ok?? gps
  1417                     err |= ios::failbit;
  1418                     break;
  1419                 }
  1420             }
  1421         }
  1422 
  1423         if (err == ok) {
  1424             // if needed fill at right
  1425             for (; 0 < npad; --npad) {
  1426                 if (fill_char != buf->sputc(fill_char)) {
  1427                     err |= ios::failbit;
  1428                     break;
  1429                 }
  1430             }
  1431         }
  1432 
  1433         os.osfx();
  1434         os.width(0);
  1435 
  1436     } // if opfx
  1437 
  1438     if(err != ok)
  1439         os.setstate(err); // assume this does NOT throw - gps
  1440     return os;
  1441 
  1442 }
  1443 #else
  1444 
  1445 template <typename Ch, typename Tr, typename Block, typename Alloc>
  1446 std::basic_ostream<Ch, Tr>&
  1447 operator<<(std::basic_ostream<Ch, Tr>& os,
  1448            const dynamic_bitset<Block, Alloc>& b)
  1449 {
  1450 
  1451     using namespace std;
  1452 
  1453     const ios_base::iostate ok = ios_base::goodbit;
  1454     ios_base::iostate err = ok;
  1455 
  1456     typename basic_ostream<Ch, Tr>::sentry cerberos(os);
  1457     if (cerberos) {
  1458 
  1459         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
  1460         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
  1461         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
  1462 
  1463         try {
  1464 
  1465             typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
  1466             typedef basic_streambuf<Ch, Tr> buffer_type; // G.P.S.
  1467 
  1468             buffer_type * buf = os.rdbuf();
  1469             size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
  1470                 || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size(); //- G.P.S.
  1471 
  1472             const Ch fill_char = os.fill();
  1473             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
  1474 
  1475             // if needed fill at left; pad is decresed along the way
  1476             if (adjustfield != ios_base::left) {
  1477                 for (; 0 < npad; --npad)
  1478                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
  1479                           err |= ios_base::failbit;   // G.P.S.
  1480                           break;
  1481                     }
  1482             }
  1483 
  1484             if (err == ok) {
  1485                 // output the bitset
  1486                 for (bitsetsize_type i = b.size(); 0 < i; --i) {// G.P.S.
  1487                     typename buffer_type::int_type
  1488                         ret = buf->sputc(b.test(i-1)? one : zero);
  1489                     if (Tr::eq_int_type(Tr::eof(), ret)) {
  1490                         err |= ios_base::failbit;
  1491                         break;
  1492                     }
  1493                 }
  1494             }
  1495 
  1496             if (err == ok) {
  1497                 // if needed fill at right
  1498                 for (; 0 < npad; --npad) {
  1499                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
  1500                         err |= ios_base::failbit;
  1501                         break;
  1502                     }
  1503                 }
  1504             }
  1505 
  1506 
  1507             os.width(0);
  1508 
  1509         } catch (...) { // see std 27.6.1.1/4
  1510             bool rethrow = false;
  1511             try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
  1512 
  1513             if (rethrow)
  1514                 throw;
  1515         }
  1516     }
  1517 
  1518     if(err != ok)
  1519         os.setstate(err); // may throw exception
  1520     return os;
  1521 
  1522 }
  1523 #endif
  1524 
  1525 
  1526 #ifdef BOOST_OLD_IOSTREAMS
  1527 
  1528     // gps - A sentry-like class that calls isfx in its
  1529     // destructor. Necessary because bit_appender::do_append may throw.
  1530     class pseudo_sentry {
  1531         std::istream & m_r;
  1532         const bool m_ok;
  1533     public:
  1534         explicit pseudo_sentry(std::istream & r) : m_r(r), m_ok(r.ipfx(0)) { }
  1535         ~pseudo_sentry() { m_r.isfx(); }
  1536         operator bool() const { return m_ok; }
  1537     };
  1538 
  1539 template <typename Block, typename Alloc>
  1540 std::istream&
  1541 operator>>(std::istream& is, dynamic_bitset<Block, Alloc>& b)
  1542 {
  1543 
  1544 // Extractor for classic IO streams (libstdc++ < 3.0)
  1545 // ----------------------------------------------------//
  1546 //  It's assumed that the stream buffer functions, and
  1547 //  the stream's setstate() _cannot_ throw.
  1548 
  1549 
  1550     typedef dynamic_bitset<Block, Alloc> bitset_type;
  1551     typedef typename bitset_type::size_type size_type;
  1552 
  1553     std::ios::iostate err = std::ios::goodbit; // gps
  1554     pseudo_sentry cerberos(is); // skips whitespaces
  1555     if(cerberos) {
  1556 
  1557         b.clear();
  1558 
  1559         const std::streamsize w = is.width();
  1560         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()// gps
  1561                                                          ? w : b.max_size();
  1562         typename bitset_type::bit_appender appender(b);
  1563         std::streambuf * buf = is.rdbuf();
  1564         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
  1565 
  1566             if (c == EOF) {
  1567                 err |= std::ios::eofbit; // G.P.S.
  1568                 break;
  1569             }
  1570             else if (char(c) != '0' && char(c) != '1')
  1571                 break; // non digit character
  1572 
  1573             else {
  1574                 try {
  1575                     //throw std::bad_alloc(); // gps
  1576                     appender.do_append(char(c) == '1');
  1577                 }
  1578                 catch(...) {
  1579                     is.setstate(std::ios::failbit); // assume this can't throw
  1580                     throw;
  1581                 }
  1582             }
  1583 
  1584         } // for
  1585     }
  1586 
  1587     is.width(0); // gps
  1588     if (b.size() == 0)
  1589         err |= std::ios::failbit;
  1590     if (err != std::ios::goodbit) // gps
  1591         is.setstate (err); // may throw
  1592 
  1593     return is;
  1594 }
  1595 
  1596 #else // BOOST_OLD_IOSTREAMS
  1597 
  1598 template <typename Ch, typename Tr, typename Block, typename Alloc>
  1599 std::basic_istream<Ch, Tr>&
  1600 operator>>(std::basic_istream<Ch, Tr>& is, dynamic_bitset<Block, Alloc>& b)
  1601 {
  1602 
  1603     using namespace std;
  1604 
  1605     typedef dynamic_bitset<Block, Alloc> bitset_type;
  1606     typedef typename bitset_type::size_type size_type;
  1607 
  1608     const streamsize w = is.width();
  1609     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()? // gps
  1610                                          w : b.max_size();
  1611 
  1612     ios_base::iostate err = ios_base::goodbit; // gps
  1613     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
  1614     if(cerberos) {
  1615 
  1616         // in accordance with prop. resol. of lib DR 303 [last checked 4 Feb 2004]
  1617         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
  1618         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
  1619         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
  1620 
  1621         b.clear();
  1622         try {
  1623             typename bitset_type::bit_appender appender(b);
  1624             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
  1625             typename Tr::int_type c = buf->sgetc(); // G.P.S.
  1626             for( ; appender.get_count() < limit; c = buf->snextc() ) {
  1627 
  1628                 if (Tr::eq_int_type(Tr::eof(), c)) {
  1629                     err |= ios_base::eofbit; // G.P.S.
  1630                     break;
  1631                 }
  1632                 else {
  1633                     const Ch to_c = Tr::to_char_type(c);
  1634                     const bool is_one = Tr::eq(to_c, one);
  1635 
  1636                     if (!is_one && !Tr::eq(to_c, zero))
  1637                         break; // non digit character
  1638 
  1639                     appender.do_append(is_one);
  1640 
  1641                 }
  1642 
  1643             } // for
  1644         }
  1645         catch (...) {
  1646             // catches from stream buf, or from vector:
  1647             //
  1648             // bits_stored bits have been extracted and stored, and
  1649             // either no further character is extractable or we can't
  1650             // append to the underlying vector (out of memory) gps
  1651 
  1652             bool rethrow = false;   // see std 27.6.1.1/4
  1653             try { is.setstate(ios_base::badbit); }
  1654             catch(...) { rethrow = true; }
  1655 
  1656             if (rethrow)
  1657                 throw;
  1658 
  1659         }
  1660     }
  1661 
  1662     is.width(0); // gps
  1663     if (b.size() == 0 /*|| !cerberos*/)
  1664         err |= ios_base::failbit;
  1665     if (err != ios_base::goodbit) // gps
  1666         is.setstate (err); // may throw
  1667 
  1668     return is;
  1669 
  1670 }
  1671 
  1672 
  1673 #endif
  1674 
  1675 
  1676 //-----------------------------------------------------------------------------
  1677 // bitset operations
  1678 
  1679 template <typename Block, typename Allocator>
  1680 dynamic_bitset<Block, Allocator>
  1681 operator&(const dynamic_bitset<Block, Allocator>& x,
  1682           const dynamic_bitset<Block, Allocator>& y)
  1683 {
  1684     dynamic_bitset<Block, Allocator> b(x);
  1685     return b &= y;
  1686 }
  1687 
  1688 template <typename Block, typename Allocator>
  1689 dynamic_bitset<Block, Allocator>
  1690 operator|(const dynamic_bitset<Block, Allocator>& x,
  1691           const dynamic_bitset<Block, Allocator>& y)
  1692 {
  1693     dynamic_bitset<Block, Allocator> b(x);
  1694     return b |= y;
  1695 }
  1696 
  1697 template <typename Block, typename Allocator>
  1698 dynamic_bitset<Block, Allocator>
  1699 operator^(const dynamic_bitset<Block, Allocator>& x,
  1700           const dynamic_bitset<Block, Allocator>& y)
  1701 {
  1702     dynamic_bitset<Block, Allocator> b(x);
  1703     return b ^= y;
  1704 }
  1705 
  1706 template <typename Block, typename Allocator>
  1707 dynamic_bitset<Block, Allocator>
  1708 operator-(const dynamic_bitset<Block, Allocator>& x,
  1709           const dynamic_bitset<Block, Allocator>& y)
  1710 {
  1711     dynamic_bitset<Block, Allocator> b(x);
  1712     return b -= y;
  1713 }
  1714 
  1715 //-----------------------------------------------------------------------------
  1716 // namespace scope swap
  1717 
  1718 template<typename Block, typename Allocator>
  1719 inline void
  1720 swap(dynamic_bitset<Block, Allocator>& left,
  1721      dynamic_bitset<Block, Allocator>& right) // no throw
  1722 {
  1723     left.swap(right); // gps
  1724 }
  1725 
  1726 
  1727 //-----------------------------------------------------------------------------
  1728 // private (on conforming compilers) member functions
  1729 
  1730 
  1731 template <typename Block, typename Allocator>
  1732 inline typename dynamic_bitset<Block, Allocator>::size_type
  1733 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
  1734 {
  1735     return num_bits / bits_per_block
  1736            + static_cast<int>( num_bits % bits_per_block != 0 );
  1737 }
  1738 
  1739 // gives a reference to the highest block
  1740 //
  1741 template <typename Block, typename Allocator>
  1742 inline Block& dynamic_bitset<Block, Allocator>::m_highest_block()
  1743 {
  1744     return const_cast<Block &>
  1745            (static_cast<const dynamic_bitset *>(this)->m_highest_block());
  1746 }
  1747 
  1748 // gives a const-reference to the highest block
  1749 //
  1750 template <typename Block, typename Allocator>
  1751 inline const Block& dynamic_bitset<Block, Allocator>::m_highest_block() const
  1752 {
  1753     assert(size() > 0 && num_blocks() > 0);
  1754     return m_bits.back();
  1755 }
  1756 
  1757 
  1758 // If size() is not a multiple of bits_per_block
  1759 // then not all the bits in the last block are used.
  1760 // This function resets the unused bits (convenient
  1761 // for the implementation of many member functions)
  1762 //
  1763 template <typename Block, typename Allocator>
  1764 inline void dynamic_bitset<Block, Allocator>::m_zero_unused_bits()
  1765 {
  1766     assert (num_blocks() == calc_num_blocks(m_num_bits));
  1767 
  1768     // if != 0 this is the number of bits used in the last block
  1769     const block_width_type extra_bits = count_extra_bits();
  1770 
  1771     if (extra_bits != 0)
  1772         m_highest_block() &= ~(~static_cast<Block>(0) << extra_bits);
  1773 
  1774 }
  1775 
  1776 // check class invariants
  1777 template <typename Block, typename Allocator>
  1778 bool dynamic_bitset<Block, Allocator>::m_check_invariants() const
  1779 {
  1780     const block_width_type extra_bits = count_extra_bits();
  1781     if (extra_bits > 0) {
  1782         block_type const mask = (~static_cast<Block>(0) << extra_bits);
  1783         if ((m_highest_block() & mask) != 0)
  1784             return false;
  1785     }
  1786     if (m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks(size()))
  1787         return false;
  1788 
  1789     return true;
  1790 
  1791 }
  1792 
  1793 
  1794 } // namespace boost
  1795 
  1796 
  1797 #undef BOOST_BITSET_CHAR
  1798 
  1799 #endif // include guard
  1800