comparison DEPENDENCIES/generic/include/boost/dynamic_bitset/dynamic_bitset.hpp @ 101:c530137014c0

Update Boost headers (1.58.0)

 // -----------------------------------------------------------
 //
 //   Copyright (c) 2001-2002 Chuck Allison and Jeremy Siek
 //        Copyright (c) 2003-2006, 2008 Gennaro Prota
+//             Copyright (c) 2014 Ahmed Charles
+//
+// Copyright (c) 2014 Glen Joseph Fernandes
+// glenfe at live dot com
+// Copyright (c) 2014 Riccardo Marcangelo
 //
 // Distributed under the Boost Software License, Version 1.0.
 //    (See accompanying file LICENSE_1_0.txt or copy at
 //          http://www.boost.org/LICENSE_1_0.txt)
 //

 #endif
 
 #include "boost/dynamic_bitset_fwd.hpp"
 #include "boost/detail/dynamic_bitset.hpp"
 #include "boost/detail/iterator.hpp" // used to implement append(Iter, Iter)
-#include "boost/static_assert.hpp"
+#include "boost/move/move.hpp"
 #include "boost/limits.hpp"
 #include "boost/pending/lowest_bit.hpp"
+#include "boost/static_assert.hpp"
+#include "boost/utility/addressof.hpp"
+#include "boost/detail/no_exceptions_support.hpp"
+#include "boost/throw_exception.hpp"
 
 
 namespace boost {
 
 template <typename Block, typename Allocator>
 class dynamic_bitset
 {
-  // Portability note: member function templates are defined inside
-  // this class definition to avoid problems with VC++. Similarly,
-  // with the member functions of nested classes.
-  //
-  // [October 2008: the note above is mostly historical; new versions
-  // of VC++ are likely able to digest a more drinking form of the
-  // code; but changing it now is probably not worth the risks...]
-
-  BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
+    // Portability note: member function templates are defined inside
+    // this class definition to avoid problems with VC++. Similarly,
+    // with the member functions of nested classes.
+    //
+    // [October 2008: the note above is mostly historical; new versions
+    // of VC++ are likely able to digest a more drinking form of the
+    // code; but changing it now is probably not worth the risks...]
+
+    BOOST_STATIC_ASSERT((bool)detail::dynamic_bitset_impl::allowed_block_type<Block>::value);
+    typedef std::vector<Block, Allocator> buffer_type;
 
 public:
     typedef Block block_type;
     typedef Allocator allocator_type;
     typedef std::size_t size_type;
-    typedef block_type block_width_type;
+    typedef typename buffer_type::size_type block_width_type;
 
     BOOST_STATIC_CONSTANT(block_width_type, bits_per_block = (std::numeric_limits<Block>::digits));
     BOOST_STATIC_CONSTANT(size_type, npos = static_cast<size_type>(-1));
 
 

     ~dynamic_bitset();
 
     void swap(dynamic_bitset& b);
     dynamic_bitset& operator=(const dynamic_bitset& b);
 
+#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
+    dynamic_bitset(dynamic_bitset&& src);
+    dynamic_bitset& operator=(dynamic_bitset&& src);
+#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
+
     allocator_type get_allocator() const;
 
     // size changing operations
     void resize(size_type num_bits, bool value = false);
     void clear();
     void push_back(bool bit);
+    void pop_back();
     void append(Block block);
 
     template <typename BlockInputIterator>
     void m_append(BlockInputIterator first, BlockInputIterator last, std::input_iterator_tag)
     {

     dynamic_bitset& reset(size_type n);
     dynamic_bitset& reset();
     dynamic_bitset& flip(size_type n);
     dynamic_bitset& flip();
     bool test(size_type n) const;
+    bool test_set(size_type n, bool val = true);
+    bool all() const;
     bool any() const;
     bool none() const;
     dynamic_bitset operator~() const;
-    size_type count() const;
+    size_type count() const BOOST_NOEXCEPT;
 
     // subscript
     reference operator[](size_type pos) {
         return reference(m_bits[block_index(pos)], bit_index(pos));
     }
     bool operator[](size_type pos) const { return test(pos); }
 
     unsigned long to_ulong() const;
 
-    size_type size() const;
-    size_type num_blocks() const;
-    size_type max_size() const;
-    bool empty() const;
+    size_type size() const BOOST_NOEXCEPT;
+    size_type num_blocks() const BOOST_NOEXCEPT;
+    size_type max_size() const BOOST_NOEXCEPT;
+    bool empty() const BOOST_NOEXCEPT;
 
     bool is_subset_of(const dynamic_bitset& a) const;
     bool is_proper_subset_of(const dynamic_bitset& a) const;
     bool intersects(const dynamic_bitset & a) const;
 

 #endif
 
 
 private:
     BOOST_STATIC_CONSTANT(block_width_type, ulong_width = std::numeric_limits<unsigned long>::digits);
-    typedef std::vector<block_type, allocator_type> buffer_type;
 
     void m_zero_unused_bits();
     bool m_check_invariants() const;
 
     size_type m_do_find_from(size_type first_block) const;
 
-    block_width_type count_extra_bits() const { return bit_index(size()); }
-    static size_type block_index(size_type pos) { return pos / bits_per_block; }
-    static block_width_type bit_index(size_type pos) { return static_cast<block_width_type>(pos % bits_per_block); }
-    static Block bit_mask(size_type pos) { return Block(1) << bit_index(pos); }
+    block_width_type count_extra_bits() const BOOST_NOEXCEPT { return bit_index(size()); }
+    static size_type block_index(size_type pos) BOOST_NOEXCEPT { return pos / bits_per_block; }
+    static block_width_type bit_index(size_type pos) BOOST_NOEXCEPT { return static_cast<block_width_type>(pos % bits_per_block); }
+    static Block bit_mask(size_type pos) BOOST_NOEXCEPT { return Block(1) << bit_index(pos); }
 
     template <typename CharT, typename Traits, typename Alloc>
     void init_from_string(const std::basic_string<CharT, Traits, Alloc>& s,
         typename std::basic_string<CharT, Traits, Alloc>::size_type pos,
         typename std::basic_string<CharT, Traits, Alloc>::size_type n,

     m_bits = b.m_bits;
     m_num_bits = b.m_num_bits;
     return *this;
 }
 
+#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
+
+template <typename Block, typename Allocator>
+inline dynamic_bitset<Block, Allocator>::
+dynamic_bitset(dynamic_bitset<Block, Allocator>&& b)
+  : m_bits(boost::move(b.m_bits)), m_num_bits(boost::move(b.m_num_bits))
+{
+    // Required so that assert(m_check_invariants()); works.
+    assert((b.m_bits = buffer_type()).empty());
+    b.m_num_bits = 0;
+}
+
+template <typename Block, typename Allocator>
+inline dynamic_bitset<Block, Allocator>& dynamic_bitset<Block, Allocator>::
+operator=(dynamic_bitset<Block, Allocator>&& b)
+{
+    if (boost::addressof(b) == this) { return *this; }
+
+    m_bits = boost::move(b.m_bits);
+    m_num_bits = boost::move(b.m_num_bits);
+    // Required so that assert(m_check_invariants()); works.
+    assert((b.m_bits = buffer_type()).empty());
+    b.m_num_bits = 0;
+    return *this;
+}
+
+#endif // BOOST_NO_CXX11_RVALUE_REFERENCES
+
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::allocator_type
 dynamic_bitset<Block, Allocator>::get_allocator() const
 {
     return m_bits.get_allocator();

   set(sz, bit);
 }
 
 template <typename Block, typename Allocator>
 void dynamic_bitset<Block, Allocator>::
+pop_back() 
+{
+  const size_type old_num_blocks = num_blocks();
+  const size_type required_blocks = calc_num_blocks(m_num_bits - 1);
+  
+  if (required_blocks != old_num_blocks) {
+    m_bits.pop_back(); 
+  }
+    
+  --m_num_bits;
+  m_zero_unused_bits();
+}
+
+
+template <typename Block, typename Allocator>
+void dynamic_bitset<Block, Allocator>::
 append(Block value) // strong guarantee
 {
     const block_width_type r = count_extra_bits();
 
     if (r == 0) {

             }
             b[div] = b[0];
         }
 
         // zero out div blocks at the less significant end
-        std::fill_n(b, div, static_cast<block_type>(0));
+        std::fill_n(m_bits.begin(), div, static_cast<block_type>(0));
 
         // zero out any 1 bit that flowed into the unused part
         m_zero_unused_bits(); // thanks to Lester Gong
 
     }

         }
 
 
 
         // div blocks are zero filled at the most significant end
-        std::fill_n(b + (num_blocks()-div), div, static_cast<block_type>(0));
+        std::fill_n(m_bits.begin() + (num_blocks()-div), div, static_cast<block_type>(0));
     }
 
     return *this;
 }
 

     assert(pos < m_num_bits);
     return m_unchecked_test(pos);
 }
 
 template <typename Block, typename Allocator>
+bool dynamic_bitset<Block, Allocator>::test_set(size_type pos, bool val)
+{
+    bool const b = test(pos);
+    if (b != val) {
+        set(pos, val);
+    }
+    return b;
+}
+
+template <typename Block, typename Allocator>
+bool dynamic_bitset<Block, Allocator>::all() const
+{
+    if (empty()) {
+        return true;
+    }
+
+    const block_width_type extra_bits = count_extra_bits();
+    block_type const all_ones = ~static_cast<Block>(0);
+
+    if (extra_bits == 0) {
+        for (size_type i = 0, e = num_blocks(); i < e; ++i) {
+            if (m_bits[i] != all_ones) {
+                return false;
+            }
+        }
+    } else {
+        for (size_type i = 0, e = num_blocks() - 1; i < e; ++i) {
+            if (m_bits[i] != all_ones) {
+                return false;
+            }
+        }
+        block_type const mask = ~(~static_cast<Block>(0) << extra_bits);
+        if (m_highest_block() != mask) {
+            return false;
+        }
+    }
+    return true;
+}
+
+template <typename Block, typename Allocator>
 bool dynamic_bitset<Block, Allocator>::any() const
 {
     for (size_type i = 0; i < num_blocks(); ++i)
         if (m_bits[i])
             return true;

     return b;
 }
 
 template <typename Block, typename Allocator>
 typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::count() const
+dynamic_bitset<Block, Allocator>::count() const BOOST_NOEXCEPT
 {
     using detail::dynamic_bitset_impl::table_width;
     using detail::dynamic_bitset_impl::access_by_bytes;
     using detail::dynamic_bitset_impl::access_by_blocks;
     using detail::dynamic_bitset_impl::value_to_type;

       return 0; // convention
 
   // Check for overflows. This may be a performance burden on very
   // large bitsets but is required by the specification, sorry
   if (find_next(ulong_width - 1) != npos)
-    throw std::overflow_error("boost::dynamic_bitset::to_ulong overflow");
+    BOOST_THROW_EXCEPTION(std::overflow_error("boost::dynamic_bitset::to_ulong overflow"));
 
 
   // Ok, from now on we can be sure there's no "on" bit
   // beyond the "allowed" positions
   typedef unsigned long result_type;

   return result;
 }
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::size() const
+dynamic_bitset<Block, Allocator>::size() const BOOST_NOEXCEPT
 {
     return m_num_bits;
 }
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::num_blocks() const
+dynamic_bitset<Block, Allocator>::num_blocks() const BOOST_NOEXCEPT
 {
     return m_bits.size();
 }
 
 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
-dynamic_bitset<Block, Allocator>::max_size() const
+dynamic_bitset<Block, Allocator>::max_size() const BOOST_NOEXCEPT
 {
     // Semantics of vector<>::max_size() aren't very clear
     // (see lib issue 197) and many library implementations
     // simply return dummy values, _unrelated_ to the underlying
     // allocator.

         m * bits_per_block :
         size_type(-1);
 }
 
 template <typename Block, typename Allocator>
-inline bool dynamic_bitset<Block, Allocator>::empty() const
+inline bool dynamic_bitset<Block, Allocator>::empty() const BOOST_NOEXCEPT
 {
   return size() == 0;
 }
 
 template <typename Block, typename Allocator>

         ++i;
 
     if (i >= num_blocks())
         return npos; // not found
 
-    return i * bits_per_block + boost::lowest_bit(m_bits[i]);
+    return i * bits_per_block + static_cast<size_type>(boost::lowest_bit(m_bits[i]));
 
 }
 
 
 template <typename Block, typename Allocator>

     ++pos;
 
     const size_type blk = block_index(pos);
     const block_width_type ind = bit_index(pos);
 
-    // mask out bits before pos
-    const Block fore = m_bits[blk] & ( ~Block(0) << ind );
+    // shift bits upto one immediately after current
+    const Block fore = m_bits[blk] >> ind;
 
     return fore?
-        blk * bits_per_block + lowest_bit(fore)
+        pos + static_cast<size_type>(lowest_bit(fore))
         :
         m_do_find_from(blk + 1);
 
 }
 

 
         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, os.getloc());
         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
 
-        try {
-
-            typedef typename dynamic_bitset<Block, Alloc>::size_type bitsetsize_type;
+        BOOST_TRY {
+
+            typedef typename dynamic_bitset<Block, Alloc>::size_type bitset_size_type;
             typedef basic_streambuf<Ch, Tr> buffer_type;
 
             buffer_type * buf = os.rdbuf();
-            size_t npad = os.width() <= 0  // careful: os.width() is signed (and can be < 0)
-                || (bitsetsize_type) os.width() <= b.size()? 0 : os.width() - b.size();
+            // careful: os.width() is signed (and can be < 0)
+            const bitset_size_type width = (os.width() <= 0) ? 0 : static_cast<bitset_size_type>(os.width());
+            streamsize npad = (width <= b.size()) ? 0 : width - b.size();
 
             const Ch fill_char = os.fill();
             const ios_base::fmtflags adjustfield = os.flags() & ios_base::adjustfield;
 
-            // if needed fill at left; pad is decresed along the way
+            // if needed fill at left; pad is decreased along the way
             if (adjustfield != ios_base::left) {
                 for (; 0 < npad; --npad)
                     if (Tr::eq_int_type(Tr::eof(), buf->sputc(fill_char))) {
                           err |= ios_base::failbit;
                           break;
                     }
             }
 
             if (err == ok) {
                 // output the bitset
-                for (bitsetsize_type i = b.size(); 0 < i; --i) {
+                for (bitset_size_type i = b.size(); 0 < i; --i) {
                     typename buffer_type::int_type
                         ret = buf->sputc(b.test(i-1)? one : zero);
                     if (Tr::eq_int_type(Tr::eof(), ret)) {
                         err |= ios_base::failbit;
                         break;

             }
 
 
             os.width(0);
 
-        } catch (...) { // see std 27.6.1.1/4
+        } BOOST_CATCH (...) { // see std 27.6.1.1/4
             bool rethrow = false;
-            try { os.setstate(ios_base::failbit); } catch (...) { rethrow = true; }
+            BOOST_TRY { os.setstate(ios_base::failbit); } BOOST_CATCH (...) { rethrow = true; } BOOST_CATCH_END
 
             if (rethrow)
-                throw;
-        }
+                BOOST_RETHROW;
+        }
+        BOOST_CATCH_END
     }
 
     if(err != ok)
         os.setstate(err); // may throw exception
     return os;

 
         b.clear();
 
         const std::streamsize w = is.width();
         const size_type limit = w > 0 && static_cast<size_type>(w) < b.max_size()
-                                                         ? w : b.max_size();
+                                                         ? static_cast<size_type>(w) : b.max_size();
         typename bitset_type::bit_appender appender(b);
         std::streambuf * buf = is.rdbuf();
         for(int c = buf->sgetc(); appender.get_count() < limit; c = buf->snextc() ) {
 
             if (c == EOF) {

             }
             else if (char(c) != '0' && char(c) != '1')
                 break; // non digit character
 
             else {
-                try {
+                BOOST_TRY {
                     appender.do_append(char(c) == '1');
                 }
-                catch(...) {
+                BOOST_CATCH(...) {
                     is.setstate(std::ios::failbit); // assume this can't throw
-                    throw;
+                    BOOST_RETHROW;
                 }
+                BOOST_CATCH_END
             }
 
         } // for
     }
 

     typedef dynamic_bitset<Block, Alloc> bitset_type;
     typedef typename bitset_type::size_type size_type;
 
     const streamsize w = is.width();
     const size_type limit = 0 < w && static_cast<size_type>(w) < b.max_size()?
-                                         w : b.max_size();
+                                         static_cast<size_type>(w) : b.max_size();
 
     ios_base::iostate err = ios_base::goodbit;
     typename basic_istream<Ch, Tr>::sentry cerberos(is); // skips whitespaces
     if(cerberos) {
 

         BOOST_DYNAMIC_BITSET_CTYPE_FACET(Ch, fac, is.getloc());
         const Ch zero = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '0');
         const Ch one  = BOOST_DYNAMIC_BITSET_WIDEN_CHAR(fac, '1');
 
         b.clear();
-        try {
+        BOOST_TRY {
             typename bitset_type::bit_appender appender(b);
             basic_streambuf <Ch, Tr> * buf = is.rdbuf();
             typename Tr::int_type c = buf->sgetc();
             for( ; appender.get_count() < limit; c = buf->snextc() ) {
 

 
                 }
 
             } // for
         }
-        catch (...) {
+        BOOST_CATCH (...) {
             // catches from stream buf, or from vector:
             //
             // bits_stored bits have been extracted and stored, and
             // either no further character is extractable or we can't
             // append to the underlying vector (out of memory)
 
             bool rethrow = false;   // see std 27.6.1.1/4
-            try { is.setstate(ios_base::badbit); }
-            catch(...) { rethrow = true; }
+            BOOST_TRY { is.setstate(ios_base::badbit); }
+            BOOST_CATCH(...) { rethrow = true; }
+            BOOST_CATCH_END
 
             if (rethrow)
-                throw;
-
-        }
+                BOOST_RETHROW;
+
+        }
+        BOOST_CATCH_END
     }
 
     is.width(0);
     if (b.size() == 0 /*|| !cerberos*/)
         err |= ios_base::failbit;

 template <typename Block, typename Allocator>
 inline typename dynamic_bitset<Block, Allocator>::size_type
 dynamic_bitset<Block, Allocator>::calc_num_blocks(size_type num_bits)
 {
     return num_bits / bits_per_block
-           + static_cast<int>( num_bits % bits_per_block != 0 );
+           + static_cast<size_type>( num_bits % bits_per_block != 0 );
 }
 
 // gives a reference to the highest block
 //
 template <typename Block, typename Allocator>