Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-08-17 08:40:11 

0001 // -----------------------------------------------------------
0002 //
0003 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
0004 //      Copyright (c) 2003-2006, 2008, 2025 Gennaro Prota
0005 //             Copyright (c) 2014 Ahmed Charles
0006 //
0007 // Copyright (c) 2014 Glen Joseph Fernandes
0008 // (glenjofe@gmail.com)
0009 //
0010 // Copyright (c) 2014 Riccardo Marcangelo
0011 //             Copyright (c) 2018 Evgeny Shulgin
0012 //
0013 // Distributed under the Boost Software License, Version 1.0.
0014 //    (See accompanying file LICENSE_1_0.txt or copy at
0015 //          http://www.boost.org/LICENSE_1_0.txt)
0016 //
0017 // -----------------------------------------------------------
0018 
0019 #include "boost/assert.hpp"
0020 #include "boost/core/bit.hpp"
0021 #include "boost/core/no_exceptions_support.hpp"
0022 #include "boost/dynamic_bitset/detail/lowest_bit.hpp"
0023 #include "boost/functional/hash/hash.hpp"
0024 #include "boost/throw_exception.hpp"
0025 #include <algorithm>
0026 #include <climits>
0027 #include <istream>
0028 #include <locale>
0029 #include <ostream>
0030 #include <stdexcept>
0031 #include <utility>
0032 
0033 namespace boost {
0034 
0035 template< typename Block, typename AllocatorOrContainer >
0036 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0037 dynamic_bitset< Block, AllocatorOrContainer >::reference::reference( block_type & b, int pos )
0038     : m_block( b ), m_mask( ( BOOST_ASSERT( pos < bits_per_block ), block_type( 1 ) << pos ) )
0039 {
0040 }
0041 
0042 template< typename Block, typename AllocatorOrContainer >
0043 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >::reference::reference( const reference & other ) = default;
0044 
0045 template< typename Block, typename AllocatorOrContainer >
0046 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >::reference::
0047                                  operator bool() const
0048 {
0049     return ( m_block & m_mask ) != 0;
0050 }
0051 
0052 template< typename Block, typename AllocatorOrContainer >
0053 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0054 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator~() const
0055 {
0056     return ( m_block & m_mask ) == 0;
0057 }
0058 
0059 template< typename Block, typename AllocatorOrContainer >
0060 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0061 dynamic_bitset< Block, AllocatorOrContainer >::reference::flip()
0062 {
0063     do_flip();
0064     return *this;
0065 }
0066 
0067 template< typename Block, typename AllocatorOrContainer >
0068 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0069 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator=( bool x )
0070 {
0071     do_assign( x );
0072     return *this;
0073 }
0074 
0075 template< typename Block, typename AllocatorOrContainer >
0076 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0077 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator=( const reference & rhs )
0078 {
0079     do_assign( rhs );
0080     return *this;
0081 }
0082 
0083 template< typename Block, typename AllocatorOrContainer >
0084 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0085 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator|=( bool x )
0086 {
0087     if ( x ) {
0088         do_set();
0089     }
0090     return *this;
0091 }
0092 
0093 template< typename Block, typename AllocatorOrContainer >
0094 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0095 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator&=( bool x )
0096 {
0097     if ( ! x ) {
0098         do_reset();
0099     }
0100     return *this;
0101 }
0102 
0103 template< typename Block, typename AllocatorOrContainer >
0104 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0105 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator^=( bool x )
0106 {
0107     if ( x ) {
0108         do_flip();
0109     }
0110     return *this;
0111 }
0112 
0113 template< typename Block, typename AllocatorOrContainer >
0114 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference &
0115 dynamic_bitset< Block, AllocatorOrContainer >::reference::operator-=( bool x )
0116 {
0117     if ( x ) {
0118         do_reset();
0119     }
0120     return *this;
0121 }
0122 
0123 template< typename Block, typename AllocatorOrContainer >
0124 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0125 dynamic_bitset< Block, AllocatorOrContainer >::reference::do_set()
0126 {
0127     m_block |= m_mask;
0128 }
0129 
0130 template< typename Block, typename AllocatorOrContainer >
0131 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0132 dynamic_bitset< Block, AllocatorOrContainer >::reference::do_reset()
0133 {
0134     m_block &= ~m_mask;
0135 }
0136 
0137 template< typename Block, typename AllocatorOrContainer >
0138 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0139 dynamic_bitset< Block, AllocatorOrContainer >::reference::do_flip()
0140 {
0141     m_block ^= m_mask;
0142 }
0143 
0144 template< typename Block, typename AllocatorOrContainer >
0145 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0146 dynamic_bitset< Block, AllocatorOrContainer >::reference::do_assign( bool x )
0147 {
0148     if ( x ) {
0149         do_set();
0150     } else {
0151         do_reset();
0152     }
0153 }
0154 
0155 template< typename Iterator >
0156 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0157 bit_iterator_base< Iterator >::bit_iterator_base( Iterator block_iterator, int bit_index )
0158     : m_block_iterator( block_iterator )
0159     , m_bit_index( bit_index )
0160 {
0161     BOOST_ASSERT( 0 <= bit_index && bit_index < bits_per_block );
0162 }
0163 
0164 template< typename Iterator >
0165 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0166 bit_iterator_base< Iterator >::increment()
0167 {
0168     ++m_bit_index;
0169     if ( m_bit_index == bits_per_block ) {
0170         m_bit_index = 0;
0171         ++m_block_iterator;
0172     }
0173 }
0174 
0175 template< typename Iterator >
0176 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0177 bit_iterator_base< Iterator >::decrement()
0178 {
0179     --m_bit_index;
0180     if ( m_bit_index < 0 ) {
0181         m_bit_index = bits_per_block - 1;
0182         --m_block_iterator;
0183     }
0184 }
0185 
0186 template< typename Iterator >
0187 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0188 bit_iterator_base< Iterator >::add( typename Iterator::difference_type n )
0189 {
0190     typename Iterator::difference_type d = m_bit_index + n;
0191     m_block_iterator += d / bits_per_block;
0192     d %= bits_per_block;
0193     if ( d < 0 ) {
0194         d += bits_per_block;
0195         --m_block_iterator;
0196     }
0197     m_bit_index = static_cast< int >( d );
0198 }
0199 
0200 template< typename Iterator >
0201 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0202 operator==( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0203 {
0204     return lhs.m_block_iterator == rhs.m_block_iterator && lhs.m_bit_index == rhs.m_bit_index;
0205 }
0206 
0207 template< typename Iterator >
0208 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0209 operator!=( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0210 {
0211     return ! ( lhs == rhs );
0212 }
0213 
0214 template< typename Iterator >
0215 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0216 operator<( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0217 {
0218     return lhs.m_block_iterator < rhs.m_block_iterator
0219         || ( lhs.m_block_iterator == rhs.m_block_iterator && lhs.m_bit_index < rhs.m_bit_index );
0220 }
0221 
0222 template< typename Iterator >
0223 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0224 operator<=( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0225 {
0226     return ! ( rhs < lhs );
0227 }
0228 
0229 template< typename Iterator >
0230 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0231 operator>( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0232 {
0233     return rhs < lhs;
0234 }
0235 
0236 template< typename Iterator >
0237 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
0238 operator>=( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0239 {
0240     return ! ( lhs < rhs );
0241 }
0242 
0243 template< typename Iterator >
0244 BOOST_DYNAMIC_BITSET_CONSTEXPR20 std::ptrdiff_t
0245                                  operator-( const bit_iterator_base< Iterator > & lhs, const bit_iterator_base< Iterator > & rhs )
0246 {
0247     return ( lhs.m_block_iterator - rhs.m_block_iterator ) * bit_iterator_base< Iterator >::bits_per_block
0248          + lhs.m_bit_index - rhs.m_bit_index;
0249 }
0250 
0251 template< typename DynamicBitset >
0252 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0253 bit_iterator< DynamicBitset >::bit_iterator()
0254     : bit_iterator_base< typename DynamicBitset::buffer_type::iterator >()
0255 {
0256 }
0257 
0258 template< typename DynamicBitset >
0259 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0260 bit_iterator< DynamicBitset >::bit_iterator( typename DynamicBitset::buffer_type::iterator block_iterator, int bit_index )
0261     : bit_iterator_base< typename DynamicBitset::buffer_type::iterator >( block_iterator, bit_index )
0262 {
0263 }
0264 
0265 template< typename DynamicBitset >
0266 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename DynamicBitset::reference
0267 bit_iterator< DynamicBitset >::operator*() const
0268 {
0269     return reference( *( this->m_block_iterator ), this->m_bit_index );
0270 }
0271 
0272 template< typename DynamicBitset >
0273 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset > &
0274                                  bit_iterator< DynamicBitset >::operator++()
0275 {
0276     this->increment();
0277     return *this;
0278 }
0279 template< typename DynamicBitset >
0280 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset >
0281                                  bit_iterator< DynamicBitset >::operator++( int )
0282 {
0283     bit_iterator temp = *this;
0284     this->increment();
0285     return temp;
0286 }
0287 
0288 template< typename DynamicBitset >
0289 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset > &
0290                                  bit_iterator< DynamicBitset >::operator--()
0291 {
0292     this->decrement();
0293     return *this;
0294 }
0295 
0296 template< typename DynamicBitset >
0297 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset >
0298                                  bit_iterator< DynamicBitset >::operator--( int )
0299 {
0300     bit_iterator temp = *this;
0301     this->decrement();
0302     return temp;
0303 }
0304 
0305 template< typename DynamicBitset >
0306 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset > &
0307                                  bit_iterator< DynamicBitset >::operator+=( difference_type n )
0308 {
0309     this->add( n );
0310     return *this;
0311 }
0312 
0313 template< typename DynamicBitset >
0314 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset > &
0315                                  bit_iterator< DynamicBitset >::operator-=( difference_type n )
0316 {
0317     this->add( -n );
0318     return *this;
0319 }
0320 
0321 template< typename DynamicBitset >
0322 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset >
0323                                  operator+( const bit_iterator< DynamicBitset > & it, typename bit_iterator< DynamicBitset >::difference_type n )
0324 {
0325     bit_iterator< DynamicBitset > temp = it;
0326     temp += n;
0327     return temp;
0328 }
0329 
0330 template< typename DynamicBitset >
0331 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset >
0332                                  operator+( typename bit_iterator< DynamicBitset >::difference_type n, const bit_iterator< DynamicBitset > & it )
0333 {
0334     return it + n;
0335 }
0336 
0337 template< typename DynamicBitset >
0338 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bit_iterator< DynamicBitset >
0339                                  operator-( const bit_iterator< DynamicBitset > & it, typename bit_iterator< DynamicBitset >::difference_type n )
0340 {
0341     bit_iterator< DynamicBitset > temp = it;
0342     temp -= n;
0343     return temp;
0344 }
0345 
0346 template< typename DynamicBitset >
0347 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename DynamicBitset::reference
0348 bit_iterator< DynamicBitset >::operator[]( difference_type n ) const
0349 {
0350     return *( *this + n );
0351 }
0352 
0353 template< typename DynamicBitset >
0354 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0355 const_bit_iterator< DynamicBitset >::const_bit_iterator( typename DynamicBitset::buffer_type::const_iterator block_iterator, int bit_index )
0356     : bit_iterator_base< typename DynamicBitset::buffer_type::const_iterator >( block_iterator, bit_index )
0357 {
0358 }
0359 
0360 template< typename DynamicBitset >
0361 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0362 const_bit_iterator< DynamicBitset >::const_bit_iterator( const bit_iterator< DynamicBitset > & it )
0363     : bit_iterator_base< typename DynamicBitset::buffer_type::const_iterator >( it.m_block_iterator, it.m_bit_index )
0364 {
0365 }
0366 
0367 template< typename DynamicBitset >
0368 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename const_bit_iterator< DynamicBitset >::const_reference
0369 const_bit_iterator< DynamicBitset >::operator*() const
0370 {
0371     return ( *( this->m_block_iterator ) & ( typename DynamicBitset::block_type( 1 ) << this->m_bit_index ) ) != 0;
0372 }
0373 
0374 template< typename DynamicBitset >
0375 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset > &
0376                                  const_bit_iterator< DynamicBitset >::const_bit_iterator::operator++()
0377 {
0378     this->increment();
0379     return *this;
0380 }
0381 
0382 template< typename DynamicBitset >
0383 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset >
0384                                  const_bit_iterator< DynamicBitset >::operator++( int )
0385 {
0386     const_bit_iterator temp = *this;
0387     this->increment();
0388     return temp;
0389 }
0390 
0391 template< typename DynamicBitset >
0392 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset > &
0393                                  const_bit_iterator< DynamicBitset >::const_bit_iterator::operator--()
0394 {
0395     this->decrement();
0396     return *this;
0397 }
0398 
0399 template< typename DynamicBitset >
0400 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset >
0401                                  const_bit_iterator< DynamicBitset >::operator--( int )
0402 {
0403     const_bit_iterator temp = *this;
0404     this->decrement();
0405     return temp;
0406 }
0407 
0408 template< typename DynamicBitset >
0409 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset > &
0410                                  const_bit_iterator< DynamicBitset >::operator+=( difference_type n )
0411 {
0412     this->add( n );
0413     return *this;
0414 }
0415 
0416 template< typename DynamicBitset >
0417 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset > &
0418                                  const_bit_iterator< DynamicBitset >::operator-=( difference_type n )
0419 {
0420     this->add( -n );
0421     return *this;
0422 }
0423 
0424 template< typename DynamicBitset >
0425 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset >
0426                                  operator+( const const_bit_iterator< DynamicBitset > & it, typename const_bit_iterator< DynamicBitset >::difference_type n )
0427 {
0428     const_bit_iterator< DynamicBitset > temp = it;
0429     temp += n;
0430     return temp;
0431 }
0432 
0433 template< typename DynamicBitset >
0434 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset >
0435                                  operator+( typename const_bit_iterator< DynamicBitset >::difference_type n, const const_bit_iterator< DynamicBitset > & it )
0436 {
0437     return it + n;
0438 }
0439 
0440 template< typename DynamicBitset >
0441 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const_bit_iterator< DynamicBitset >
0442                                  operator-( const const_bit_iterator< DynamicBitset > & it, typename const_bit_iterator< DynamicBitset >::difference_type n )
0443 {
0444     const_bit_iterator< DynamicBitset > temp = it;
0445     temp -= n;
0446     return temp;
0447 }
0448 
0449 template< typename DynamicBitset >
0450 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename const_bit_iterator< DynamicBitset >::const_reference
0451 const_bit_iterator< DynamicBitset >::operator[]( difference_type n ) const
0452 {
0453     return *( *this + n );
0454 }
0455 
0456 template< typename BlockIterator, typename B, typename A >
0457 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0458 from_block_range( BlockIterator first, BlockIterator last, dynamic_bitset< B, A > & result )
0459 {
0460     // PRE: distance(first, last) <= numblocks()
0461     std::copy( first, last, result.m_bits.begin() );
0462 }
0463 
0464 template< typename Block, typename AllocatorOrContainer >
0465 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0466 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset()
0467     : m_num_bits( 0 )
0468 {
0469 }
0470 
0471 template< typename Block, typename AllocatorOrContainer >
0472 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0473 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset( const allocator_type & alloc )
0474     : m_bits( alloc ), m_num_bits( 0 )
0475 {
0476 }
0477 
0478 template< typename Block, typename AllocatorOrContainer >
0479 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0480 dynamic_bitset< Block, AllocatorOrContainer >::
0481     dynamic_bitset( size_type num_bits, unsigned long value, const allocator_type & alloc )
0482     : m_bits( alloc ), m_num_bits( 0 )
0483 {
0484     init_from_unsigned_long( num_bits, value );
0485 }
0486 
0487 template< typename Block, typename AllocatorOrContainer >
0488 template< typename CharT, typename Traits, typename Alloc >
0489 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset(
0490     const std::basic_string< CharT, Traits, Alloc > &             s,
0491     typename std::basic_string< CharT, Traits, Alloc >::size_type pos,
0492     typename std::basic_string< CharT, Traits, Alloc >::size_type n,
0493     size_type                                                     num_bits,
0494     const allocator_type &                                        alloc )
0495 
0496     : m_bits( alloc ), m_num_bits( 0 )
0497 {
0498     init_from_string( s.c_str(), s.length(), pos, n, num_bits );
0499 }
0500 
0501 template< typename Block, typename AllocatorOrContainer >
0502 template< typename CharT >
0503 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset(
0504     const CharT *          s,
0505     std::size_t            n,
0506     size_type              num_bits,
0507     const allocator_type & alloc )
0508     : m_bits( alloc ), m_num_bits( 0 )
0509 {
0510     init_from_string( s, std::char_traits< CharT >::length( s ), 0, n, num_bits );
0511 }
0512 
0513 #if defined( BOOST_DYNAMIC_BITSET_USE_CPP17_OR_LATER )
0514 
0515 template< typename Block, typename AllocatorOrContainer >
0516 template< typename CharT, typename Traits >
0517 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset(
0518     std::basic_string_view< CharT, Traits > sv,
0519     size_type                               num_bits,
0520     const allocator_type &                  alloc )
0521     : m_bits( alloc ), m_num_bits( 0 )
0522 {
0523     init_from_string( sv.data(), sv.length(), 0, sv.length(), num_bits );
0524 }
0525 
0526 #endif
0527 
0528 template< typename Block, typename AllocatorOrContainer >
0529 template< typename BlockInputIterator >
0530 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0531 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset(
0532     BlockInputIterator     first,
0533     BlockInputIterator     last,
0534     const allocator_type & alloc )
0535     : m_bits( alloc ), m_num_bits( 0 )
0536 {
0537     using boost::detail::dynamic_bitset_impl::is_numeric;
0538     using boost::detail::dynamic_bitset_impl::value_to_type;
0539 
0540     const value_to_type<
0541         is_numeric< BlockInputIterator >::value >
0542         selector;
0543 
0544     dispatch_init( first, last, selector );
0545 }
0546 
0547 // copy constructor
0548 template< typename Block, typename AllocatorOrContainer >
0549 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0550 dynamic_bitset< Block, AllocatorOrContainer >::dynamic_bitset( const dynamic_bitset & b )
0551     : m_bits( b.m_bits ), m_num_bits( b.m_num_bits )
0552 {
0553 }
0554 
0555 template< typename Block, typename AllocatorOrContainer >
0556 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >::~dynamic_bitset()
0557 {
0558     BOOST_ASSERT( m_check_invariants() );
0559 }
0560 
0561 template< typename Block, typename AllocatorOrContainer >
0562 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::iterator
0563 dynamic_bitset< Block, AllocatorOrContainer >::begin()
0564 {
0565     return iterator( m_bits.begin(), 0 );
0566 }
0567 
0568 template< typename Block, typename AllocatorOrContainer >
0569 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_iterator
0570 dynamic_bitset< Block, AllocatorOrContainer >::begin() const
0571 {
0572     return const_iterator( m_bits.cbegin(), 0 );
0573 }
0574 
0575 template< typename Block, typename AllocatorOrContainer >
0576 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::iterator
0577 dynamic_bitset< Block, AllocatorOrContainer >::end()
0578 {
0579     if ( count_extra_bits() == 0 ) {
0580         return iterator( m_bits.end(), 0 );
0581     } else {
0582         return iterator( std::prev( m_bits.end() ), size() % bits_per_block );
0583     }
0584 }
0585 
0586 template< typename Block, typename AllocatorOrContainer >
0587 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_iterator
0588 dynamic_bitset< Block, AllocatorOrContainer >::end() const
0589 {
0590     if ( count_extra_bits() == 0 ) {
0591         return const_iterator( m_bits.cend(), 0 );
0592     } else {
0593         return const_iterator( std::prev( m_bits.cend() ), size() % bits_per_block );
0594     }
0595 }
0596 
0597 template< typename Block, typename AllocatorOrContainer >
0598 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reverse_iterator
0599 dynamic_bitset< Block, AllocatorOrContainer >::rbegin()
0600 {
0601     return reverse_iterator( end() );
0602 }
0603 
0604 template< typename Block, typename AllocatorOrContainer >
0605 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_reverse_iterator
0606 dynamic_bitset< Block, AllocatorOrContainer >::rbegin() const
0607 {
0608     return const_reverse_iterator( end() );
0609 }
0610 
0611 template< typename Block, typename AllocatorOrContainer >
0612 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reverse_iterator
0613 dynamic_bitset< Block, AllocatorOrContainer >::rend()
0614 {
0615     return reverse_iterator( begin() );
0616 }
0617 
0618 template< typename Block, typename AllocatorOrContainer >
0619 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_reverse_iterator
0620 dynamic_bitset< Block, AllocatorOrContainer >::rend() const
0621 {
0622     return const_reverse_iterator( begin() );
0623 }
0624 
0625 template< typename Block, typename AllocatorOrContainer >
0626 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_iterator
0627 dynamic_bitset< Block, AllocatorOrContainer >::cbegin() const
0628 {
0629     return const_iterator( begin() );
0630 }
0631 
0632 template< typename Block, typename AllocatorOrContainer >
0633 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_iterator
0634 dynamic_bitset< Block, AllocatorOrContainer >::cend() const
0635 {
0636     return const_iterator( end() );
0637 }
0638 
0639 template< typename Block, typename AllocatorOrContainer >
0640 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_reverse_iterator
0641 dynamic_bitset< Block, AllocatorOrContainer >::crbegin() const
0642 {
0643     return const_reverse_iterator( end() );
0644 }
0645 
0646 template< typename Block, typename AllocatorOrContainer >
0647 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::const_reverse_iterator
0648 dynamic_bitset< Block, AllocatorOrContainer >::crend() const
0649 {
0650     return const_reverse_iterator( begin() );
0651 }
0652 
0653 template< typename Block, typename AllocatorOrContainer >
0654 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0655 dynamic_bitset< Block, AllocatorOrContainer >::
0656     swap( dynamic_bitset< Block, AllocatorOrContainer > & b ) noexcept
0657 {
0658     std::swap( m_bits, b.m_bits );
0659     std::swap( m_num_bits, b.m_num_bits );
0660 }
0661 
0662 template< typename Block, typename AllocatorOrContainer >
0663 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0664                                  dynamic_bitset< Block, AllocatorOrContainer >::
0665 operator=( const dynamic_bitset< Block, AllocatorOrContainer > & b )
0666 {
0667     m_bits     = b.m_bits;
0668     m_num_bits = b.m_num_bits;
0669     return *this;
0670 }
0671 
0672 template< typename Block, typename AllocatorOrContainer >
0673 BOOST_DYNAMIC_BITSET_CONSTEXPR20
0674 dynamic_bitset< Block, AllocatorOrContainer >::
0675     dynamic_bitset( dynamic_bitset< Block, AllocatorOrContainer > && b )
0676     : m_bits( std::move( b.m_bits ) ), m_num_bits( std::move( b.m_num_bits ) )
0677 {
0678     // Required so that BOOST_ASSERT(m_check_invariants()); works.
0679     BOOST_ASSERT( ( b.m_bits = buffer_type( get_allocator() ) ).empty() );
0680     b.m_num_bits = 0;
0681 }
0682 
0683 template< typename Block, typename AllocatorOrContainer >
0684 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0685                                  dynamic_bitset< Block, AllocatorOrContainer >::
0686 operator=( dynamic_bitset< Block, AllocatorOrContainer > && b )
0687 {
0688     if ( &b == this ) {
0689         return *this;
0690     }
0691 
0692     m_bits     = std::move( b.m_bits );
0693     m_num_bits = std::move( b.m_num_bits );
0694     // Required so that BOOST_ASSERT(m_check_invariants()); works.
0695     BOOST_ASSERT( ( b.m_bits = buffer_type( get_allocator() ) ).empty() );
0696     b.m_num_bits = 0;
0697     return *this;
0698 }
0699 
0700 template< typename Block, typename AllocatorOrContainer >
0701 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::allocator_type
0702 dynamic_bitset< Block, AllocatorOrContainer >::get_allocator() const
0703 {
0704     return m_bits.get_allocator();
0705 }
0706 
0707 //-----------------------------------------------------------------------------
0708 // size changing operations
0709 
0710 template< typename Block, typename AllocatorOrContainer >
0711 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0712 dynamic_bitset< Block, AllocatorOrContainer >::
0713     resize( size_type num_bits, bool value ) // strong guarantee
0714 {
0715     const size_type  old_num_blocks  = num_blocks();
0716     const size_type  required_blocks = calc_num_blocks( num_bits );
0717 
0718     const block_type v               = value ? Block( -1 ) : Block( 0 );
0719 
0720     if ( required_blocks != old_num_blocks ) {
0721         m_bits.resize( required_blocks, v ); // s.g. (copy)
0722     }
0723 
0724     // At this point:
0725     //
0726     //  - if the buffer was shrunk, we have nothing more to do,
0727     //    except a call to m_zero_unused_bits()
0728     //
0729     //  - if it was enlarged, all the (used) bits in the new blocks have
0730     //    the correct value, but we have not yet touched those bits, if
0731     //    any, that were 'unused bits' before enlarging: if value == true,
0732     //    they must be set.
0733 
0734     if ( value && ( num_bits > m_num_bits ) ) {
0735         const int extra_bits = count_extra_bits();
0736         if ( extra_bits ) {
0737             BOOST_ASSERT( old_num_blocks >= 1 && old_num_blocks <= m_bits.size() );
0738 
0739             // Set them.
0740             m_bits[ old_num_blocks - 1 ] |= ( v << extra_bits );
0741         }
0742     }
0743 
0744     m_num_bits = num_bits;
0745     m_zero_unused_bits();
0746 }
0747 
0748 template< typename Block, typename AllocatorOrContainer >
0749 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0750 dynamic_bitset< Block, AllocatorOrContainer >::
0751     clear() // no throw
0752 {
0753     m_bits.clear();
0754     m_num_bits = 0;
0755 }
0756 
0757 template< typename Block, typename AllocatorOrContainer >
0758 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0759 dynamic_bitset< Block, AllocatorOrContainer >::
0760     push_back( bool bit )
0761 {
0762     const int extra_bits = count_extra_bits();
0763     if ( extra_bits == 0 ) {
0764         m_bits.push_back( Block( bit ) );
0765     } else {
0766         m_bits.back() |= ( Block( bit ) << extra_bits );
0767     }
0768     ++m_num_bits;
0769 }
0770 
0771 template< typename Block, typename AllocatorOrContainer >
0772 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0773 dynamic_bitset< Block, AllocatorOrContainer >::
0774     push_front( bool bit )
0775 {
0776     resize( size() + 1 );
0777     *this <<= 1;
0778     set( 0, bit );
0779 }
0780 
0781 template< typename Block, typename AllocatorOrContainer >
0782 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0783 dynamic_bitset< Block, AllocatorOrContainer >::
0784     pop_back()
0785 {
0786     BOOST_ASSERT( ! empty() );
0787 
0788     if ( count_extra_bits() == 1 ) {
0789         m_bits.pop_back();
0790         --m_num_bits;
0791     } else {
0792         --m_num_bits;
0793         m_zero_unused_bits();
0794     }
0795 }
0796 
0797 template< typename Block, typename AllocatorOrContainer >
0798 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0799 dynamic_bitset< Block, AllocatorOrContainer >::
0800     pop_front()
0801 {
0802     BOOST_ASSERT( ! empty() );
0803 
0804     *this >>= 1;
0805     resize( size() - 1 );
0806 }
0807 
0808 template< typename Block, typename AllocatorOrContainer >
0809 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0810 dynamic_bitset< Block, AllocatorOrContainer >::
0811     append( Block value ) // strong guarantee
0812 {
0813     const int r = count_extra_bits();
0814 
0815     if ( r == 0 ) {
0816         // the buffer is empty, or all blocks are filled
0817         m_bits.push_back( value );
0818     } else {
0819         m_bits.push_back( value >> ( bits_per_block - r ) );
0820         m_bits[ m_bits.size() - 2 ] |= ( value << r ); // m_bits.size() >= 2
0821     }
0822 
0823     m_num_bits += bits_per_block;
0824     BOOST_ASSERT( m_check_invariants() );
0825 }
0826 
0827 template< typename Block, typename AllocatorOrContainer >
0828 template< typename BlockInputIterator >
0829 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
0830 dynamic_bitset< Block, AllocatorOrContainer >::append( BlockInputIterator first, BlockInputIterator last ) // strong guarantee
0831 {
0832     typename std::iterator_traits< BlockInputIterator >::iterator_category cat;
0833     m_append( first, last, cat );
0834 }
0835 
0836 //-----------------------------------------------------------------------------
0837 // bitset operations
0838 template< typename Block, typename AllocatorOrContainer >
0839 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0840                                  dynamic_bitset< Block, AllocatorOrContainer >::operator&=( const dynamic_bitset & rhs )
0841 {
0842     BOOST_ASSERT( size() == rhs.size() );
0843     for ( size_type i = 0; i < num_blocks(); ++i ) {
0844         m_bits[ i ] &= rhs.m_bits[ i ];
0845     }
0846     return *this;
0847 }
0848 
0849 template< typename Block, typename AllocatorOrContainer >
0850 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0851                                  dynamic_bitset< Block, AllocatorOrContainer >::operator|=( const dynamic_bitset & rhs )
0852 {
0853     BOOST_ASSERT( size() == rhs.size() );
0854     for ( size_type i = 0; i < num_blocks(); ++i ) {
0855         m_bits[ i ] |= rhs.m_bits[ i ];
0856     }
0857     // m_zero_unused_bits();
0858     return *this;
0859 }
0860 
0861 template< typename Block, typename AllocatorOrContainer >
0862 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0863                                  dynamic_bitset< Block, AllocatorOrContainer >::operator^=( const dynamic_bitset & rhs )
0864 {
0865     BOOST_ASSERT( size() == rhs.size() );
0866     for ( size_type i = 0; i < this->num_blocks(); ++i ) {
0867         m_bits[ i ] ^= rhs.m_bits[ i ];
0868     }
0869     // m_zero_unused_bits();
0870     return *this;
0871 }
0872 
0873 template< typename Block, typename AllocatorOrContainer >
0874 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0875                                  dynamic_bitset< Block, AllocatorOrContainer >::operator-=( const dynamic_bitset & rhs )
0876 {
0877     BOOST_ASSERT( size() == rhs.size() );
0878     for ( size_type i = 0; i < num_blocks(); ++i ) {
0879         m_bits[ i ] &= ~rhs.m_bits[ i ];
0880     }
0881     // m_zero_unused_bits();
0882     return *this;
0883 }
0884 
0885 // NOTE:
0886 //  Note that the 'if (r != 0)' is crucial to avoid undefined
0887 //  behavior when the left hand operand of >> isn't promoted to a
0888 //  wider type (because rs would be too large).
0889 //
0890 template< typename Block, typename AllocatorOrContainer >
0891 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0892                                  dynamic_bitset< Block, AllocatorOrContainer >::operator<<=( size_type n )
0893 {
0894     if ( n >= m_num_bits ) {
0895         return reset();
0896     }
0897     // else
0898     if ( n > 0 ) {
0899         const size_type last = num_blocks() - 1;   // num_blocks() is >= 1
0900         const size_type div  = n / bits_per_block; // div is <= last
0901         const int       r    = bit_index( n );
0902         buffer_type &   b    = m_bits;
0903 
0904         if ( r != 0 ) {
0905             const int rs = bits_per_block - r;
0906 
0907             for ( size_type i = last - div; i > 0; --i ) {
0908                 b[ i + div ] = ( b[ i ] << r ) | ( b[ i - 1 ] >> rs );
0909             }
0910             b[ div ] = b[ 0 ] << r;
0911 
0912         } else {
0913             for ( size_type i = last - div; i > 0; --i ) {
0914                 b[ i + div ] = b[ i ];
0915             }
0916             b[ div ] = b[ 0 ];
0917         }
0918 
0919         // zero out div blocks at the least significant end
0920         std::fill_n( m_bits.begin(), div, static_cast< block_type >( 0 ) );
0921 
0922         // zero out any 1 bit that flowed into the unused part
0923         m_zero_unused_bits(); // thanks to Lester Gong
0924     }
0925 
0926     return *this;
0927 }
0928 
0929 //
0930 // NOTE:
0931 //  See the comments to operator <<=.
0932 //
0933 template< typename B, typename A >
0934 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< B, A > &
0935                                  dynamic_bitset< B, A >::operator>>=( size_type n )
0936 {
0937     if ( n >= m_num_bits ) {
0938         return reset();
0939     }
0940     // else
0941     if ( n > 0 ) {
0942         const size_type last = num_blocks() - 1;   // num_blocks() is >= 1
0943         const size_type div  = n / bits_per_block; // div is <= last
0944         const int       r    = bit_index( n );
0945         buffer_type &   b    = m_bits;
0946 
0947         if ( r != 0 ) {
0948             const int ls = bits_per_block - r;
0949 
0950             for ( size_type i = div; i < last; ++i ) {
0951                 b[ i - div ] = ( b[ i ] >> r ) | ( b[ i + 1 ] << ls );
0952             }
0953             // r bits go to zero
0954             b[ last - div ] = b[ last ] >> r;
0955         }
0956 
0957         else {
0958             for ( size_type i = div; i <= last; ++i ) {
0959                 b[ i - div ] = b[ i ];
0960             }
0961             // note the '<=': the last iteration 'absorbs'
0962             // b[last-div] = b[last] >> 0;
0963         }
0964 
0965         // div blocks are zero filled at the most significant end
0966         std::fill_n( m_bits.begin() + ( num_blocks() - div ), div, static_cast< block_type >( 0 ) );
0967     }
0968 
0969     return *this;
0970 }
0971 
0972 template< typename Block, typename AllocatorOrContainer >
0973 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
0974                                  dynamic_bitset< Block, AllocatorOrContainer >::operator<<( size_type n ) const
0975 {
0976     dynamic_bitset r( *this );
0977     return r <<= n;
0978 }
0979 
0980 template< typename Block, typename AllocatorOrContainer >
0981 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
0982                                  dynamic_bitset< Block, AllocatorOrContainer >::operator>>( size_type n ) const
0983 {
0984     dynamic_bitset r( *this );
0985     return r >>= n;
0986 }
0987 
0988 //-----------------------------------------------------------------------------
0989 // basic bit operations
0990 
0991 template< typename Block, typename AllocatorOrContainer >
0992 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
0993                                  dynamic_bitset< Block, AllocatorOrContainer >::set( size_type pos, size_type len, bool val )
0994 {
0995     if ( val ) {
0996         return range_operation( pos, len, set_block_partial, set_block_full );
0997     } else {
0998         return range_operation( pos, len, reset_block_partial, reset_block_full );
0999     }
1000 }
1001 
1002 template< typename Block, typename AllocatorOrContainer >
1003 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1004                                  dynamic_bitset< Block, AllocatorOrContainer >::set( size_type pos, bool val )
1005 {
1006     BOOST_ASSERT( pos < m_num_bits );
1007 
1008     if ( val ) {
1009         m_bits[ block_index( pos ) ] |= bit_mask( pos );
1010     } else {
1011         reset( pos );
1012     }
1013 
1014     return *this;
1015 }
1016 
1017 template< typename Block, typename AllocatorOrContainer >
1018 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1019                                  dynamic_bitset< Block, AllocatorOrContainer >::set()
1020 {
1021     std::fill( m_bits.begin(), m_bits.end(), Block( -1 ) );
1022     m_zero_unused_bits();
1023     return *this;
1024 }
1025 
1026 template< typename Block, typename AllocatorOrContainer >
1027 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1028                                  dynamic_bitset< Block, AllocatorOrContainer >::reset( size_type pos, size_type len )
1029 {
1030     return range_operation( pos, len, reset_block_partial, reset_block_full );
1031 }
1032 
1033 template< typename Block, typename AllocatorOrContainer >
1034 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1035                                  dynamic_bitset< Block, AllocatorOrContainer >::reset( size_type pos )
1036 {
1037     BOOST_ASSERT( pos < m_num_bits );
1038     m_bits[ block_index( pos ) ] &= ~bit_mask( pos );
1039     return *this;
1040 }
1041 
1042 template< typename Block, typename AllocatorOrContainer >
1043 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1044                                  dynamic_bitset< Block, AllocatorOrContainer >::reset()
1045 {
1046     std::fill( m_bits.begin(), m_bits.end(), Block( 0 ) );
1047     return *this;
1048 }
1049 
1050 template< typename Block, typename AllocatorOrContainer >
1051 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1052                                  dynamic_bitset< Block, AllocatorOrContainer >::flip( size_type pos, size_type len )
1053 {
1054     return range_operation( pos, len, flip_block_partial, flip_block_full );
1055 }
1056 
1057 template< typename Block, typename AllocatorOrContainer >
1058 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1059                                  dynamic_bitset< Block, AllocatorOrContainer >::flip( size_type pos )
1060 {
1061     BOOST_ASSERT( pos < m_num_bits );
1062     m_bits[ block_index( pos ) ] ^= bit_mask( pos );
1063     return *this;
1064 }
1065 
1066 template< typename Block, typename AllocatorOrContainer >
1067 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1068                                  dynamic_bitset< Block, AllocatorOrContainer >::flip()
1069 {
1070     for ( size_type i = 0; i < num_blocks(); ++i ) {
1071         m_bits[ i ] = ~m_bits[ i ];
1072     }
1073     m_zero_unused_bits();
1074     return *this;
1075 }
1076 
1077 template< typename Block, typename AllocatorOrContainer >
1078 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference
1079 dynamic_bitset< Block, AllocatorOrContainer >::at( size_type pos )
1080 {
1081     if ( pos >= m_num_bits ) {
1082         BOOST_THROW_EXCEPTION( std::out_of_range( "boost::dynamic_bitset::at out_of_range" ) );
1083     }
1084 
1085     return ( *this )[ pos ];
1086 }
1087 
1088 template< typename Block, typename AllocatorOrContainer >
1089 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1090 dynamic_bitset< Block, AllocatorOrContainer >::at( size_type pos ) const
1091 {
1092     if ( pos >= m_num_bits ) {
1093         BOOST_THROW_EXCEPTION( std::out_of_range( "boost::dynamic_bitset::at out_of_range" ) );
1094     }
1095 
1096     return ( *this )[ pos ];
1097 }
1098 
1099 template< typename Block, typename AllocatorOrContainer >
1100 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1101 dynamic_bitset< Block, AllocatorOrContainer >::test( size_type pos ) const
1102 {
1103     BOOST_ASSERT( pos < m_num_bits );
1104     return m_unchecked_test( pos );
1105 }
1106 
1107 template< typename Block, typename AllocatorOrContainer >
1108 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1109 dynamic_bitset< Block, AllocatorOrContainer >::test_set( size_type pos, bool val )
1110 {
1111     const bool b = test( pos );
1112     if ( b != val ) {
1113         set( pos, val );
1114     }
1115     return b;
1116 }
1117 
1118 template< typename Block, typename AllocatorOrContainer >
1119 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1120 dynamic_bitset< Block, AllocatorOrContainer >::all() const
1121 {
1122     const int        extra_bits        = count_extra_bits();
1123     const block_type all_ones          = Block( -1 );
1124     const size_type  num_normal_blocks = num_blocks() - ( extra_bits != 0 ? 1 : 0 );
1125 
1126     for ( size_type i = 0; i < num_normal_blocks; ++i ) {
1127         if ( m_bits[ i ] != all_ones ) {
1128             return false;
1129         }
1130     }
1131     if ( extra_bits != 0 ) {
1132         const block_type mask = ( block_type( 1 ) << extra_bits ) - 1;
1133         if ( m_highest_block() != mask ) {
1134             return false;
1135         }
1136     }
1137     return true;
1138 }
1139 
1140 template< typename Block, typename AllocatorOrContainer >
1141 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1142 dynamic_bitset< Block, AllocatorOrContainer >::any() const
1143 {
1144     for ( size_type i = 0; i < num_blocks(); ++i ) {
1145         if ( m_bits[ i ] ) {
1146             return true;
1147         }
1148     }
1149     return false;
1150 }
1151 
1152 template< typename Block, typename AllocatorOrContainer >
1153 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1154 dynamic_bitset< Block, AllocatorOrContainer >::none() const
1155 {
1156     return ! any();
1157 }
1158 
1159 template< typename Block, typename AllocatorOrContainer >
1160 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
1161                                  dynamic_bitset< Block, AllocatorOrContainer >::operator~() const
1162 {
1163     dynamic_bitset b( *this );
1164     b.flip();
1165     return b;
1166 }
1167 
1168 template< typename Block, typename AllocatorOrContainer >
1169 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1170 dynamic_bitset< Block, AllocatorOrContainer >::count() const noexcept
1171 {
1172     size_type result = 0;
1173     for ( block_type block : m_bits ) {
1174         result += core::popcount( block );
1175     }
1176     return result;
1177 }
1178 
1179 //-----------------------------------------------------------------------------
1180 // subscript
1181 
1182 template< typename Block, typename AllocatorOrContainer >
1183 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::reference
1184 dynamic_bitset< Block, AllocatorOrContainer >::operator[]( size_type pos )
1185 {
1186     return reference( m_bits[ block_index( pos ) ], bit_index( pos ) );
1187 }
1188 
1189 template< typename Block, typename AllocatorOrContainer >
1190 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1191 dynamic_bitset< Block, AllocatorOrContainer >::operator[]( size_type pos ) const
1192 {
1193     return test( pos );
1194 }
1195 
1196 //-----------------------------------------------------------------------------
1197 // conversions
1198 
1199 template< typename Block, typename AllocatorOrContainer >
1200 BOOST_DYNAMIC_BITSET_CONSTEXPR20 unsigned long
1201 dynamic_bitset< Block, AllocatorOrContainer >::
1202     to_ulong() const
1203 {
1204     if ( m_num_bits == 0 ) {
1205         return 0; // convention
1206     }
1207 
1208     // Check for overflows. This may be a performance burden on very large
1209     // bitsets but is required by the specification, sorry.
1210     if ( find_first( ulong_width ) != npos ) {
1211         BOOST_THROW_EXCEPTION( std::overflow_error( "boost::dynamic_bitset::to_ulong overflow" ) );
1212     }
1213 
1214     // Ok, from now on we can be sure there's no "on" bit beyond the
1215     // "allowed" positions.
1216     typedef unsigned long result_type;
1217 
1218     const size_type       maximum_size =
1219         (std::min)( m_num_bits, static_cast< size_type >( ulong_width ) );
1220 
1221     const size_type last_block = block_index( maximum_size - 1 );
1222 
1223     BOOST_ASSERT( ( last_block * bits_per_block ) < static_cast< size_type >( ulong_width ) );
1224 
1225     result_type result = 0;
1226     for ( size_type i = 0; i <= last_block; ++i ) {
1227         const size_type offset = i * bits_per_block;
1228         result |= ( static_cast< result_type >( m_bits[ i ] ) << offset );
1229     }
1230 
1231     return result;
1232 }
1233 
1234 template< typename Block, typename AllocatorOrContainer, typename StringT >
1235 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1236 to_string( const dynamic_bitset< Block, AllocatorOrContainer > & b, StringT & s )
1237 {
1238     to_string_helper( b, s, false );
1239 }
1240 
1241 // Differently from to_string this function dumps out every bit of the
1242 // internal representation (may be useful for debugging purposes)
1243 template< typename B, typename A, typename StringT >
1244 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1245 dump_to_string( const dynamic_bitset< B, A > & b, StringT & s )
1246 {
1247     to_string_helper( b, s, true /* = dump_all */ );
1248 }
1249 
1250 template< typename Block, typename AllocatorOrContainer, typename BlockOutputIterator >
1251 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1252 to_block_range( const dynamic_bitset< Block, AllocatorOrContainer > & b, BlockOutputIterator result )
1253 {
1254     // Note how this copies *all* bits, including the unused ones in the
1255     // last block (which are zero).
1256     std::copy( b.m_bits.begin(), b.m_bits.end(), result );
1257 }
1258 
1259 template< typename Block, typename AllocatorOrContainer >
1260 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1261 dynamic_bitset< Block, AllocatorOrContainer >::size() const noexcept
1262 {
1263     return m_num_bits;
1264 }
1265 
1266 template< typename Block, typename AllocatorOrContainer >
1267 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1268 dynamic_bitset< Block, AllocatorOrContainer >::num_blocks() const noexcept
1269 {
1270     return m_bits.size();
1271 }
1272 
1273 template< typename Block, typename AllocatorOrContainer >
1274 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1275 dynamic_bitset< Block, AllocatorOrContainer >::max_size() const noexcept
1276 {
1277     // The semantics of vector<>::max_size() aren't very clear (see lib
1278     // issue 197).
1279     //
1280     // Because of that, I was tempted to not provide this function
1281     // at all, but the user could need it if they provide their own
1282     // allocator.
1283 
1284     const size_type m = m_bits.max_size();
1285 
1286     return m <= ( size_type( -1 ) / bits_per_block ) ? m * bits_per_block : size_type( -1 );
1287 }
1288 
1289 template< typename Block, typename AllocatorOrContainer >
1290 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1291 dynamic_bitset< Block, AllocatorOrContainer >::empty() const noexcept
1292 {
1293     return size() == 0;
1294 }
1295 
1296 template< typename Block, typename AllocatorOrContainer >
1297 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1298 dynamic_bitset< Block, AllocatorOrContainer >::capacity() const noexcept
1299 {
1300     return m_bits.capacity() * bits_per_block;
1301 }
1302 
1303 template< typename Block, typename AllocatorOrContainer >
1304 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1305 dynamic_bitset< Block, AllocatorOrContainer >::reserve( size_type num_bits )
1306 {
1307     m_bits.reserve( calc_num_blocks( num_bits ) );
1308 }
1309 
1310 template< typename Block, typename AllocatorOrContainer >
1311 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1312 dynamic_bitset< Block, AllocatorOrContainer >::shrink_to_fit()
1313 {
1314     if ( m_bits.size() < m_bits.capacity() ) {
1315         buffer_type( m_bits ).swap( m_bits );
1316     }
1317 }
1318 
1319 template< typename Block, typename AllocatorOrContainer >
1320 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1321 dynamic_bitset< Block, AllocatorOrContainer >::
1322     is_subset_of( const dynamic_bitset< Block, AllocatorOrContainer > & a ) const
1323 {
1324     BOOST_ASSERT( size() == a.size() );
1325     for ( size_type i = 0; i < num_blocks(); ++i ) {
1326         if ( m_bits[ i ] & ~a.m_bits[ i ] ) {
1327             return false;
1328         }
1329     }
1330     return true;
1331 }
1332 
1333 template< typename Block, typename AllocatorOrContainer >
1334 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1335 dynamic_bitset< Block, AllocatorOrContainer >::
1336     is_proper_subset_of( const dynamic_bitset< Block, AllocatorOrContainer > & a ) const
1337 {
1338     BOOST_ASSERT( size() == a.size() );
1339 
1340     bool proper = false;
1341     for ( size_type i = 0; i < num_blocks(); ++i ) {
1342         const Block & bt = m_bits[ i ];
1343         const Block & ba = a.m_bits[ i ];
1344 
1345         if ( bt & ~ba ) {
1346             return false; // not a subset at all
1347         }
1348         if ( ba & ~bt ) {
1349             proper = true;
1350         }
1351     }
1352     return proper;
1353 }
1354 
1355 template< typename Block, typename AllocatorOrContainer >
1356 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1357 dynamic_bitset< Block, AllocatorOrContainer >::intersects( const dynamic_bitset & b ) const
1358 {
1359     const size_type common_blocks = num_blocks() < b.num_blocks()
1360                                       ? num_blocks()
1361                                       : b.num_blocks();
1362 
1363     for ( size_type i = 0; i < common_blocks; ++i ) {
1364         if ( m_bits[ i ] & b.m_bits[ i ] ) {
1365             return true;
1366         }
1367     }
1368     return false;
1369 }
1370 
1371 // --------------------------------
1372 // lookup
1373 
1374 // Look for the first bit with value `value`, starting from the block with index
1375 // first_block.
1376 template< typename Block, typename AllocatorOrContainer >
1377 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1378 dynamic_bitset< Block, AllocatorOrContainer >::m_do_find_from( size_type first_block, bool value ) const
1379 {
1380     size_type i = std::distance( m_bits.begin(), std::find_if( m_bits.begin() + first_block, m_bits.end(), value ? m_not_empty : m_not_full ) );
1381 
1382     if ( i >= num_blocks() ) {
1383         return npos; // not found
1384     }
1385 
1386     const Block b = value
1387                       ? m_bits[ i ]
1388                       : m_bits[ i ] ^ Block( -1 );
1389     return i * bits_per_block + static_cast< size_type >( detail::lowest_bit( b ) );
1390 }
1391 
1392 template< typename Block, typename AllocatorOrContainer >
1393 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1394 dynamic_bitset< Block, AllocatorOrContainer >::find_first( size_type pos ) const
1395 {
1396     const size_type sz = size();
1397     if ( pos >= sz ) {
1398         return npos;
1399     }
1400 
1401     const size_type blk   = block_index( pos );
1402     const int       ind   = bit_index( pos );
1403 
1404     // shift bits upto one immediately after current
1405     const Block     fore  = m_bits[ blk ] >> ind;
1406 
1407     const bool      found = m_not_empty( fore );
1408     return found ? pos + static_cast< size_type >( detail::lowest_bit( fore ) )
1409                  : m_do_find_from( blk + 1, true );
1410 }
1411 
1412 template< typename Block, typename AllocatorOrContainer >
1413 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1414 dynamic_bitset< Block, AllocatorOrContainer >::find_first_off( size_type pos ) const
1415 {
1416     if ( pos >= size() ) {
1417         return npos;
1418     }
1419 
1420     const size_type blk                = block_index( pos );
1421     const int       ind                = bit_index( pos );
1422     const Block     fore               = m_bits[ blk ] >> ind;
1423     bool            found              = false;
1424     int             lowest_off_bit_pos = -1;
1425     if ( m_not_full( fore ) ) {
1426         lowest_off_bit_pos = detail::lowest_bit( fore ^ Block( -1 ) );
1427         // don't consider a zero introduced by m_bits[ blk ] >> ind as found
1428         found              = lowest_off_bit_pos <= ( bits_per_block - 1 - ind );
1429     }
1430 
1431     const size_type zero_pos = found
1432                                  ? pos + lowest_off_bit_pos
1433                                  : m_do_find_from( blk + 1, false );
1434     return zero_pos >= size()
1435              ? npos
1436              : zero_pos;
1437 }
1438 
1439 template< typename Block, typename AllocatorOrContainer >
1440 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1441 dynamic_bitset< Block, AllocatorOrContainer >::find_next( size_type pos ) const
1442 {
1443     return pos == npos
1444              ? npos
1445              : find_first( pos + 1 );
1446 }
1447 
1448 template< typename Block, typename AllocatorOrContainer >
1449 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1450 dynamic_bitset< Block, AllocatorOrContainer >::find_next_off( size_type pos ) const
1451 {
1452     return pos == npos
1453              ? npos
1454              : find_first_off( pos + 1 );
1455 }
1456 
1457 //-----------------------------------------------------------------------------
1458 // comparison
1459 
1460 template< typename Block, typename AllocatorOrContainer >
1461 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1462 operator==( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1463 {
1464     return ( a.m_num_bits == b.m_num_bits )
1465         && ( a.m_bits == b.m_bits );
1466 }
1467 
1468 template< typename Block, typename AllocatorOrContainer >
1469 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1470 operator!=( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1471 {
1472     return ! ( a == b );
1473 }
1474 
1475 template< typename Block, typename AllocatorOrContainer >
1476 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1477 operator<( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1478 {
1479     typedef BOOST_DEDUCED_TYPENAME dynamic_bitset< Block, AllocatorOrContainer >::size_type size_type;
1480 
1481     size_type                                                                               asize( a.size() );
1482     size_type                                                                               bsize( b.size() );
1483 
1484     if ( ! bsize ) {
1485         return false;
1486     } else if ( ! asize ) {
1487         return true;
1488     } else if ( asize == bsize ) {
1489         for ( size_type ii = a.num_blocks(); ii > 0; --ii ) {
1490             size_type i = ii - 1;
1491             if ( a.m_bits[ i ] < b.m_bits[ i ] ) {
1492                 return true;
1493             } else if ( a.m_bits[ i ] > b.m_bits[ i ] ) {
1494                 return false;
1495             }
1496         }
1497         return false;
1498     } else {
1499         size_type leqsize( std::min BOOST_PREVENT_MACRO_SUBSTITUTION( asize, bsize ) );
1500 
1501         for ( size_type ii = 0; ii < leqsize; ++ii, --asize, --bsize ) {
1502             size_type i = asize - 1;
1503             size_type j = bsize - 1;
1504             if ( a[ i ] < b[ j ] ) {
1505                 return true;
1506             } else if ( a[ i ] > b[ j ] ) {
1507                 return false;
1508             }
1509         }
1510         return a.size() < b.size();
1511     }
1512 }
1513 
1514 template< typename Block, typename AllocatorOrContainer >
1515 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1516 operator<=( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1517 {
1518     return ! ( a > b );
1519 }
1520 
1521 template< typename Block, typename AllocatorOrContainer >
1522 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1523 operator>( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1524 {
1525     return b < a;
1526 }
1527 
1528 template< typename Block, typename AllocatorOrContainer >
1529 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1530 operator>=( const dynamic_bitset< Block, AllocatorOrContainer > & a, const dynamic_bitset< Block, AllocatorOrContainer > & b )
1531 {
1532     return ! ( a < b );
1533 }
1534 
1535 template< typename B, typename A, typename StringT >
1536 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1537 to_string_helper( const dynamic_bitset< B, A > & b, StringT & s, bool dump_all )
1538 {
1539     typedef typename StringT::traits_type              Tr;
1540     typedef typename StringT::value_type               Ch;
1541 
1542     const std::ctype< Ch > &                           fac  = std::use_facet< std::ctype< Ch > >( std::locale() );
1543     const Ch                                           zero = fac.widen( '0' );
1544     const Ch                                           one  = fac.widen( '1' );
1545 
1546     // Note that this function may access (when
1547     // dump_all == true) bits beyond position size() - 1
1548 
1549     typedef typename dynamic_bitset< B, A >::size_type size_type;
1550 
1551     const size_type                                    len = dump_all ? dynamic_bitset< B, A >::bits_per_block * b.num_blocks() : b.size();
1552     s.assign( len, zero );
1553 
1554     for ( size_type i = 0; i < len; ++i ) {
1555         if ( b.m_unchecked_test( i ) ) {
1556             Tr::assign( s[ len - 1 - i ], one );
1557         }
1558     }
1559 }
1560 
1561 //-----------------------------------------------------------------------------
1562 // hash operations
1563 
1564 template< typename Block, typename AllocatorOrContainer >
1565 std::size_t
1566 hash_value( const dynamic_bitset< Block, AllocatorOrContainer > & a )
1567 {
1568     std::size_t res = hash_value( a.m_num_bits );
1569     boost::hash_combine( res, a.m_bits );
1570     return res;
1571 }
1572 
1573 //-----------------------------------------------------------------------------
1574 // stream operations
1575 
1576 template< typename Ch, typename Tr, typename Block, typename Alloc >
1577 std::basic_ostream< Ch, Tr > &
1578 operator<<( std::basic_ostream< Ch, Tr > & os, const dynamic_bitset< Block, Alloc > & b )
1579 {
1580     using namespace std;
1581 
1582     const ios_base::iostate                  ok  = ios_base::goodbit;
1583     ios_base::iostate                        err = ok;
1584 
1585     typename basic_ostream< Ch, Tr >::sentry cerberos( os );
1586     if ( cerberos ) {
1587         const Ch zero = os.widen( '0' );
1588         const Ch one  = os.widen( '1' );
1589 
1590         BOOST_TRY
1591         {
1592             typedef typename dynamic_bitset< Block, Alloc >::size_type bitset_size_type;
1593             typedef basic_streambuf< Ch, Tr >                          buffer_type;
1594 
1595             buffer_type *                                              buf         = os.rdbuf();
1596             // careful: os.width() is signed (and can be < 0)
1597             const bitset_size_type                                     width       = ( os.width() <= 0 ) ? 0 : static_cast< bitset_size_type >( os.width() );
1598             streamsize                                                 npad        = ( width <= b.size() ) ? 0 : width - b.size();
1599 
1600             const Ch                                                   fill_char   = os.fill();
1601             const ios_base::fmtflags                                   adjustfield = os.flags() & ios_base::adjustfield;
1602 
1603             // if needed fill at left; pad is decreased along the way
1604             if ( adjustfield != ios_base::left ) {
1605                 for ( ; 0 < npad; --npad ) {
1606                     if ( Tr::eq_int_type( Tr::eof(), buf->sputc( fill_char ) ) ) {
1607                         err |= ios_base::failbit;
1608                         break;
1609                     }
1610                 }
1611             }
1612 
1613             if ( err == ok ) {
1614                 // output the bitset
1615                 for ( bitset_size_type i = b.size(); 0 < i; --i ) {
1616                     typename buffer_type::int_type
1617                         ret = buf->sputc( b.test( i - 1 ) ? one : zero );
1618                     if ( Tr::eq_int_type( Tr::eof(), ret ) ) {
1619                         err |= ios_base::failbit;
1620                         break;
1621                     }
1622                 }
1623             }
1624 
1625             if ( err == ok ) {
1626                 // if needed fill at right
1627                 for ( ; 0 < npad; --npad ) {
1628                     if ( Tr::eq_int_type( Tr::eof(), buf->sputc( fill_char ) ) ) {
1629                         err |= ios_base::failbit;
1630                         break;
1631                     }
1632                 }
1633             }
1634 
1635             os.width( 0 );
1636         }
1637         BOOST_CATCH( ... )
1638         {
1639             bool rethrow = false;
1640             BOOST_TRY
1641             {
1642                 os.setstate( ios_base::badbit );
1643             }
1644             BOOST_CATCH( ... )
1645             {
1646                 rethrow = true;
1647             }
1648             BOOST_CATCH_END
1649 
1650             if ( rethrow ) {
1651                 BOOST_RETHROW
1652             }
1653         }
1654         BOOST_CATCH_END
1655     }
1656 
1657     if ( err != ok ) {
1658         os.setstate( err ); // may throw exception
1659     }
1660     return os;
1661 }
1662 
1663 template< typename Ch, typename Tr, typename Block, typename Alloc >
1664 std::basic_istream< Ch, Tr > &
1665 operator>>( std::basic_istream< Ch, Tr > & is, dynamic_bitset< Block, Alloc > & b )
1666 {
1667     using namespace std;
1668 
1669     typedef dynamic_bitset< Block, Alloc >   bitset_type;
1670     typedef typename bitset_type::size_type  size_type;
1671 
1672     const streamsize                         w                          = is.width();
1673     const size_type                          limit                      = 0 < w && static_cast< size_type >( w ) < b.max_size() ? static_cast< size_type >( w ) : b.max_size();
1674 
1675     bool                                     exceptions_are_from_vector = false;
1676     ios_base::iostate                        err                        = ios_base::goodbit;
1677     typename basic_istream< Ch, Tr >::sentry cerberos( is ); // skips whitespace
1678     if ( cerberos ) {
1679         // in accordance with the resolution of library issue 303
1680         const Ch zero = is.widen( '0' );
1681         const Ch one  = is.widen( '1' );
1682 
1683         b.clear();
1684         BOOST_TRY
1685         {
1686             typename bitset_type::bit_appender appender( b );
1687             basic_streambuf< Ch, Tr > *        buf = is.rdbuf();
1688             typename Tr::int_type              c   = buf->sgetc();
1689             for ( ; appender.get_count() < limit; c = buf->snextc() ) {
1690                 if ( Tr::eq_int_type( Tr::eof(), c ) ) {
1691                     err |= ios_base::eofbit;
1692                     break;
1693                 } else {
1694                     const Ch   to_c   = Tr::to_char_type( c );
1695                     const bool is_one = Tr::eq( to_c, one );
1696 
1697                     if ( ! is_one && ! Tr::eq( to_c, zero ) ) {
1698                         break; // non digit character
1699                     }
1700 
1701                     exceptions_are_from_vector = true;
1702                     appender.do_append( is_one );
1703                     exceptions_are_from_vector = false;
1704                 }
1705 
1706             } // for
1707         }
1708         BOOST_CATCH( ... )
1709         {
1710             // catches from stream buf, or from vector:
1711             //
1712             // bits_stored bits have been extracted and stored, and
1713             // either no further character is extractable or we can't
1714             // append to the underlying vector (out of memory)
1715             if ( exceptions_are_from_vector ) {
1716                 BOOST_RETHROW
1717             }
1718 
1719             bool rethrow = false;
1720             BOOST_TRY
1721             {
1722                 is.setstate( ios_base::badbit );
1723             }
1724             BOOST_CATCH( ... )
1725             {
1726                 rethrow = true;
1727             }
1728             BOOST_CATCH_END
1729 
1730             if ( rethrow ) {
1731                 BOOST_RETHROW
1732             }
1733         }
1734         BOOST_CATCH_END
1735     }
1736 
1737     is.width( 0 );
1738     if ( b.size() == 0 /*|| !cerberos*/ ) {
1739         err |= ios_base::failbit;
1740     }
1741     if ( err != ios_base::goodbit ) {
1742         is.setstate( err ); // may throw
1743     }
1744 
1745     return is;
1746 }
1747 
1748 //-----------------------------------------------------------------------------
1749 // bitset operations
1750 
1751 template< typename Block, typename AllocatorOrContainer >
1752 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
1753                                  operator&( const dynamic_bitset< Block, AllocatorOrContainer > & x, const dynamic_bitset< Block, AllocatorOrContainer > & y )
1754 {
1755     dynamic_bitset< Block, AllocatorOrContainer > b( x );
1756     return b &= y;
1757 }
1758 
1759 template< typename Block, typename AllocatorOrContainer >
1760 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
1761                                  operator|( const dynamic_bitset< Block, AllocatorOrContainer > & x, const dynamic_bitset< Block, AllocatorOrContainer > & y )
1762 {
1763     dynamic_bitset< Block, AllocatorOrContainer > b( x );
1764     return b |= y;
1765 }
1766 
1767 template< typename Block, typename AllocatorOrContainer >
1768 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
1769                                  operator^( const dynamic_bitset< Block, AllocatorOrContainer > & x, const dynamic_bitset< Block, AllocatorOrContainer > & y )
1770 {
1771     dynamic_bitset< Block, AllocatorOrContainer > b( x );
1772     return b ^= y;
1773 }
1774 
1775 template< typename Block, typename AllocatorOrContainer >
1776 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer >
1777                                  operator-( const dynamic_bitset< Block, AllocatorOrContainer > & x, const dynamic_bitset< Block, AllocatorOrContainer > & y )
1778 {
1779     dynamic_bitset< Block, AllocatorOrContainer > b( x );
1780     return b -= y;
1781 }
1782 
1783 //-----------------------------------------------------------------------------
1784 // namespace scope swap
1785 
1786 template< typename Block, typename AllocatorOrContainer >
1787 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1788 swap( dynamic_bitset< Block, AllocatorOrContainer > & a, dynamic_bitset< Block, AllocatorOrContainer > & b ) noexcept
1789 {
1790     a.swap( b );
1791 }
1792 
1793 template< typename Block, typename AllocatorOrContainer >
1794 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1795 dynamic_bitset< Block, AllocatorOrContainer >::m_unchecked_test( size_type pos ) const
1796 {
1797     return ( m_bits[ block_index( pos ) ] & bit_mask( pos ) ) != 0;
1798 }
1799 
1800 template< typename Block, typename AllocatorOrContainer >
1801 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1802 dynamic_bitset< Block, AllocatorOrContainer >::calc_num_blocks( size_type num_bits )
1803 {
1804     return num_bits / bits_per_block
1805          + static_cast< size_type >( num_bits % bits_per_block != 0 );
1806 }
1807 
1808 // gives a reference to the highest block
1809 //
1810 template< typename Block, typename AllocatorOrContainer >
1811 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block &
1812 dynamic_bitset< Block, AllocatorOrContainer >::m_highest_block()
1813 {
1814     return const_cast< Block & >( static_cast< const dynamic_bitset * >( this )->m_highest_block() );
1815 }
1816 
1817 // gives a const-reference to the highest block
1818 //
1819 template< typename Block, typename AllocatorOrContainer >
1820 BOOST_DYNAMIC_BITSET_CONSTEXPR20 const Block &
1821 dynamic_bitset< Block, AllocatorOrContainer >::m_highest_block() const
1822 {
1823     BOOST_ASSERT( num_blocks() > 0 );
1824     return m_bits.back();
1825 }
1826 
1827 template< typename Block, typename AllocatorOrContainer >
1828 BOOST_DYNAMIC_BITSET_CONSTEXPR20 dynamic_bitset< Block, AllocatorOrContainer > &
1829                                  dynamic_bitset< Block, AllocatorOrContainer >::range_operation(
1830     size_type pos, size_type len, Block ( *partial_block_operation )( Block, size_type, size_type ), Block ( *full_block_operation )( Block ) )
1831 {
1832     BOOST_ASSERT( pos + len <= m_num_bits );
1833 
1834     // Do nothing in case of zero length
1835     if ( ! len ) {
1836         return *this;
1837     }
1838 
1839     // Use an additional asserts in order to detect size_type overflow
1840     // For example: pos = 10, len = size_type_limit - 2, pos + len = 7
1841     // In case of overflow, 'pos + len' is always smaller than 'len'
1842     BOOST_ASSERT( pos + len >= len );
1843 
1844     // Start and end blocks of the [pos; pos + len - 1] sequence
1845     const size_type first_block     = block_index( pos );
1846     const size_type last_block      = block_index( pos + len - 1 );
1847 
1848     const size_type first_bit_index = bit_index( pos );
1849     const size_type last_bit_index  = bit_index( pos + len - 1 );
1850 
1851     if ( first_block == last_block ) {
1852         // Filling only a sub-block of a block
1853         m_bits[ first_block ] = partial_block_operation( m_bits[ first_block ], first_bit_index, last_bit_index );
1854     } else {
1855         // Check if the corner blocks won't be fully filled with 'val'
1856         const size_type first_block_shift = bit_index( pos ) ? 1 : 0;
1857         const size_type last_block_shift  = ( bit_index( pos + len - 1 )
1858                                              == bits_per_block - 1 )
1859                                               ? 0
1860                                               : 1;
1861 
1862         // Blocks that will be filled with ~0 or 0 at once
1863         const size_type first_full_block  = first_block + first_block_shift;
1864         const size_type last_full_block   = last_block - last_block_shift;
1865 
1866         for ( size_type i = first_full_block; i <= last_full_block; ++i ) {
1867             m_bits[ i ] = full_block_operation( m_bits[ i ] );
1868         }
1869 
1870         // Fill the first block from the 'first' bit index to the end
1871         if ( first_block_shift ) {
1872             m_bits[ first_block ] = partial_block_operation( m_bits[ first_block ], first_bit_index, bits_per_block - 1 );
1873         }
1874 
1875         // Fill the last block from the start to the 'last' bit index
1876         if ( last_block_shift ) {
1877             m_bits[ last_block ] = partial_block_operation( m_bits[ last_block ], 0, last_bit_index );
1878         }
1879     }
1880 
1881     return *this;
1882 }
1883 
1884 // If size() is not a multiple of bits_per_block then not all the bits
1885 // in the last block are used. This function resets the unused bits
1886 // (convenient for the implementation of many member functions).
1887 template< typename Block, typename AllocatorOrContainer >
1888 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
1889 dynamic_bitset< Block, AllocatorOrContainer >::m_zero_unused_bits()
1890 {
1891     BOOST_ASSERT( num_blocks() == calc_num_blocks( m_num_bits ) );
1892 
1893     // if != 0, this is the number of bits used in the last block.
1894     const int extra_bits = count_extra_bits();
1895 
1896     if ( extra_bits != 0 ) {
1897         m_highest_block() &= ( Block( 1 ) << extra_bits ) - 1;
1898     }
1899 }
1900 
1901 // check class invariants
1902 template< typename Block, typename AllocatorOrContainer >
1903 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1904 dynamic_bitset< Block, AllocatorOrContainer >::m_check_invariants() const
1905 {
1906     const int extra_bits = count_extra_bits();
1907     if ( extra_bits > 0 ) {
1908         const block_type mask = Block( -1 ) << extra_bits;
1909         if ( ( m_highest_block() & mask ) != 0 ) {
1910             return false;
1911         }
1912     }
1913     if ( m_bits.size() > m_bits.capacity() || num_blocks() != calc_num_blocks( size() ) ) {
1914         return false;
1915     }
1916 
1917     return true;
1918 }
1919 
1920 template< typename Block, typename AllocatorOrContainer >
1921 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1922 dynamic_bitset< Block, AllocatorOrContainer >::m_not_empty( Block x )
1923 {
1924     return x != Block( 0 );
1925 }
1926 
1927 template< typename Block, typename AllocatorOrContainer >
1928 BOOST_DYNAMIC_BITSET_CONSTEXPR20 bool
1929 dynamic_bitset< Block, AllocatorOrContainer >::m_not_full( Block x )
1930 {
1931     return x != Block( -1 );
1932 }
1933 
1934 template< typename Block, typename AllocatorOrContainer >
1935 BOOST_DYNAMIC_BITSET_CONSTEXPR20 int
1936 dynamic_bitset< Block, AllocatorOrContainer >::count_extra_bits() const noexcept
1937 {
1938     return bit_index( size() );
1939 }
1940 
1941 template< typename Block, typename AllocatorOrContainer >
1942 BOOST_DYNAMIC_BITSET_CONSTEXPR20 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
1943 dynamic_bitset< Block, AllocatorOrContainer >::block_index( size_type pos ) noexcept
1944 {
1945     return pos / bits_per_block;
1946 }
1947 
1948 template< typename Block, typename AllocatorOrContainer >
1949 BOOST_DYNAMIC_BITSET_CONSTEXPR20 int
1950 dynamic_bitset< Block, AllocatorOrContainer >::bit_index( size_type pos ) noexcept
1951 {
1952     return static_cast< int >( pos % bits_per_block );
1953 }
1954 
1955 template< typename Block, typename AllocatorOrContainer >
1956 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
1957 dynamic_bitset< Block, AllocatorOrContainer >::bit_mask( size_type pos ) noexcept
1958 {
1959     return Block( 1 ) << bit_index( pos );
1960 }
1961 
1962 template< typename Block, typename AllocatorOrContainer >
1963 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
1964 dynamic_bitset< Block, AllocatorOrContainer >::bit_mask( size_type first, size_type last ) noexcept
1965 {
1966     Block res = ( last == bits_per_block - 1 )
1967                   ? Block( -1 )
1968                   : ( ( Block( 1 ) << ( last + 1 ) ) - 1 );
1969     res ^= ( Block( 1 ) << first ) - 1;
1970     return res;
1971 }
1972 
1973 template< typename Block, typename AllocatorOrContainer >
1974 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
1975 dynamic_bitset< Block, AllocatorOrContainer >::set_block_bits(
1976     Block     block,
1977     size_type first,
1978     size_type last,
1979     bool      val ) noexcept
1980 {
1981     if ( val ) {
1982         return block | bit_mask( first, last );
1983     } else {
1984         return block & static_cast< Block >( ~bit_mask( first, last ) );
1985     }
1986 }
1987 
1988 // Functions for operations on ranges
1989 template< typename Block, typename AllocatorOrContainer >
1990 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
1991 dynamic_bitset< Block, AllocatorOrContainer >::set_block_partial(
1992     Block     block,
1993     size_type first,
1994     size_type last ) noexcept
1995 {
1996     return set_block_bits( block, first, last, true );
1997 }
1998 
1999 template< typename Block, typename AllocatorOrContainer >
2000 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
2001 dynamic_bitset< Block, AllocatorOrContainer >::set_block_full( Block ) noexcept
2002 {
2003     return Block( -1 );
2004 }
2005 
2006 template< typename Block, typename AllocatorOrContainer >
2007 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
2008 dynamic_bitset< Block, AllocatorOrContainer >::reset_block_partial(
2009     Block     block,
2010     size_type first,
2011     size_type last ) noexcept
2012 {
2013     return set_block_bits( block, first, last, false );
2014 }
2015 
2016 template< typename Block, typename AllocatorOrContainer >
2017 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
2018 dynamic_bitset< Block, AllocatorOrContainer >::reset_block_full( Block ) noexcept
2019 {
2020     return 0;
2021 }
2022 
2023 template< typename Block, typename AllocatorOrContainer >
2024 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
2025 dynamic_bitset< Block, AllocatorOrContainer >::flip_block_partial(
2026     Block     block,
2027     size_type first,
2028     size_type last ) noexcept
2029 {
2030     return block ^ bit_mask( first, last );
2031 }
2032 
2033 template< typename Block, typename AllocatorOrContainer >
2034 BOOST_DYNAMIC_BITSET_CONSTEXPR20 Block
2035 dynamic_bitset< Block, AllocatorOrContainer >::flip_block_full( Block block ) noexcept
2036 {
2037     return ~block;
2038 }
2039 
2040 template< typename Block, typename AllocatorOrContainer >
2041 template< typename T >
2042 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2043 dynamic_bitset< Block, AllocatorOrContainer >::dispatch_init(
2044     T             num_bits,
2045     unsigned long value,
2046     detail::dynamic_bitset_impl::value_to_type< true > )
2047 {
2048     init_from_unsigned_long( static_cast< size_type >( num_bits ), value );
2049 }
2050 
2051 template< typename Block, typename AllocatorOrContainer >
2052 template< typename T >
2053 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2054 dynamic_bitset< Block, AllocatorOrContainer >::dispatch_init(
2055     T first,
2056     T last,
2057     detail::dynamic_bitset_impl::value_to_type< false > )
2058 {
2059     init_from_block_range( first, last );
2060 }
2061 
2062 template< typename Block, typename AllocatorOrContainer >
2063 template< typename BlockIter >
2064 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2065 dynamic_bitset< Block, AllocatorOrContainer >::init_from_block_range( BlockIter first, BlockIter last )
2066 {
2067     BOOST_ASSERT( m_bits.size() == 0 );
2068     m_bits.insert( m_bits.end(), first, last );
2069     m_num_bits = m_bits.size() * bits_per_block;
2070 }
2071 
2072 template< typename Block, typename AllocatorOrContainer >
2073 template< typename CharT, typename Traits >
2074 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2075 dynamic_bitset< Block, AllocatorOrContainer >::init_from_string(
2076     const CharT * s, // caution: not necessarily null-terminated
2077     std::size_t   string_length,
2078     std::size_t   pos,
2079     std::size_t   n,
2080     size_type     num_bits )
2081 {
2082     BOOST_ASSERT( pos <= string_length );
2083 
2084     const std::size_t rlen = (std::min)( n, string_length - pos );
2085     const size_type   sz   = ( num_bits != npos ? num_bits : rlen );
2086     m_bits.resize( calc_num_blocks( sz ) );
2087     m_num_bits                      = sz;
2088 
2089     const std::ctype< CharT > & fac = std::use_facet< std::ctype< CharT > >( std::locale() );
2090     const CharT                 one = fac.widen( '1' );
2091 
2092     const size_type             m   = num_bits < rlen ? num_bits : rlen;
2093     for ( std::size_t i = 0; i < m; ++i ) {
2094         const CharT c = s[ ( pos + m - 1 ) - i ];
2095 
2096         if ( Traits::eq( c, one ) ) {
2097             set( i );
2098         } else {
2099             BOOST_ASSERT( Traits::eq( c, fac.widen( '0' ) ) );
2100         }
2101     }
2102 }
2103 
2104 template< typename Block, typename AllocatorOrContainer >
2105 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2106 dynamic_bitset< Block, AllocatorOrContainer >::init_from_unsigned_long(
2107     size_type     num_bits,
2108     unsigned long value )
2109 {
2110     BOOST_ASSERT( m_bits.size() == 0 );
2111 
2112     m_bits.resize( calc_num_blocks( num_bits ) );
2113     m_num_bits = num_bits;
2114 
2115     typedef unsigned long                                                                        num_type;
2116     typedef boost::detail::dynamic_bitset_impl::shifter< num_type, bits_per_block, ulong_width > shifter;
2117 
2118     // if (num_bits == 0)
2119     //     return;
2120 
2121     // zero out all bits at pos >= num_bits, if any;
2122     // note that: num_bits == 0 implies value == 0
2123     if ( num_bits < static_cast< size_type >( ulong_width ) ) {
2124         const num_type mask = ( num_type( 1 ) << num_bits ) - 1;
2125         value &= mask;
2126     }
2127 
2128     typename buffer_type::iterator it = m_bits.begin();
2129     for ( ; value; shifter::left_shift( value ), ++it ) {
2130         *it = static_cast< block_type >( value );
2131     }
2132 }
2133 
2134 template< typename Block, typename AllocatorOrContainer >
2135 template< typename BlockInputIterator >
2136 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2137 dynamic_bitset< Block, AllocatorOrContainer >::m_append( BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag )
2138 {
2139     for ( ; first != last; ++first ) {
2140         append( *first );
2141     }
2142 }
2143 
2144 template< typename Block, typename AllocatorOrContainer >
2145 template< typename BlockInputIterator >
2146 BOOST_DYNAMIC_BITSET_CONSTEXPR20 void
2147 dynamic_bitset< Block, AllocatorOrContainer >::m_append( BlockInputIterator first, BlockInputIterator last, std::forward_iterator_tag )
2148 {
2149     if ( first != last ) {
2150         const int         r = count_extra_bits();
2151         const std::size_t d = std::distance( first, last );
2152         m_bits.reserve( num_blocks() + d );
2153         if ( r == 0 ) {
2154             do {
2155                 m_bits.push_back( *first ); // could use vector<>::insert()
2156                 ++first;
2157             } while ( first != last );
2158         } else {
2159             m_highest_block() |= ( *first << r );
2160             do {
2161                 Block b = *first >> ( bits_per_block - r );
2162                 ++first;
2163                 m_bits.push_back( b | ( first == last ? 0 : *first << r ) );
2164             } while ( first != last );
2165         }
2166         m_num_bits += bits_per_block * d;
2167     }
2168 }
2169 
2170 // bit appender
2171 
2172 template< typename Block, typename AllocatorOrContainer >
2173 dynamic_bitset< Block, AllocatorOrContainer >::bit_appender::bit_appender( dynamic_bitset & r )
2174     : bs( r ), n( 0 ), mask( 0 ), current( 0 )
2175 {
2176 }
2177 
2178 template< typename Block, typename AllocatorOrContainer >
2179 dynamic_bitset< Block, AllocatorOrContainer >::bit_appender::~bit_appender()
2180 {
2181     // Reverse the order of the blocks, shift if needed, and then
2182     // resize.
2183     //
2184     std::reverse( bs.m_bits.begin(), bs.m_bits.end() );
2185     const int offs = bit_index( n );
2186     if ( offs ) {
2187         bs >>= ( bits_per_block - offs );
2188     }
2189     bs.resize( n ); // doesn't enlarge, so can't throw
2190     BOOST_ASSERT( bs.m_check_invariants() );
2191 }
2192 
2193 template< typename Block, typename AllocatorOrContainer >
2194 void
2195 dynamic_bitset< Block, AllocatorOrContainer >::bit_appender::do_append( bool value )
2196 {
2197     if ( mask == 0 ) {
2198         bs.append( Block( 0 ) );
2199         current = &bs.m_highest_block();
2200         mask    = Block( 1 ) << ( bits_per_block - 1 );
2201     }
2202 
2203     if ( value ) {
2204         *current |= mask;
2205     }
2206     mask /= 2;
2207     ++n;
2208 }
2209 
2210 template< typename Block, typename AllocatorOrContainer >
2211 typename dynamic_bitset< Block, AllocatorOrContainer >::size_type
2212 dynamic_bitset< Block, AllocatorOrContainer >::bit_appender::get_count() const
2213 {
2214     return n;
2215 }
2216 
2217 } // namespace boost
2218 
2219 // std::hash support
2220 #if defined( BOOST_DYNAMIC_BITSET_SPECIALIZE_STD_HASH )
2221 namespace std {
2222 
2223 template< typename Block, typename AllocatorOrContainer >
2224 struct hash< boost::dynamic_bitset< Block, AllocatorOrContainer > >
2225 {
2226     typedef boost::dynamic_bitset< Block, AllocatorOrContainer > argument_type;
2227     typedef std::size_t                                          result_type;
2228     result_type
2229     operator()( const argument_type & a ) const noexcept
2230     {
2231         boost::hash< argument_type > hasher;
2232         return hasher( a );
2233     }
2234 };
2235 
2236 }
2237 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!