bitset.hpp

C++的一个好库。。。现在很流行

// (C) Copyright Jeremy Siek 2001. Permission to copy, use, modify,
// sell and distribute this software is granted provided this
// copyright notice appears in all copies. This software is provided
// "as is" without express or implied warranty, and with no claim as
// to its suitability for any purpose.

/*
 * Copyright (c) 1998
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

#include <boost/config.hpp>
#include <memory>
#include <stdexcept>
#include <algorithm>
#include <string>
#include <boost/config.hpp>
#include <boost/pending/ct_if.hpp>
#include <boost/graph/detail/bitset_adaptor.hpp>

// This provides versions of std::bitset with both static and dynamic size.

// UNDER CONSTRUCTION


// replace this later
#include <cassert>
#define BOOST_ASSERT_THROW(expr, except) assert(expr)

namespace boost {

  namespace detail {
    // structure to aid in counting bits
    template<bool dummy = true>
    struct bit_count {
      static unsigned char value[256];
    };

    // Mapping from 8 bit unsigned integers to the index of the first bit
    template<bool dummy = true>
    struct first_bit_location {
      static unsigned char value[256];
    };

    template <typename WordType>  // this size is in bits
    struct word_traits {
      typedef WordType word_type;
      static const std::size_t word_size = CHAR_BIT * sizeof(word_type);
    };
    
    //=========================================================================
    template <class WordTraits, class SizeType, class Derived>
    class bitset_base
      : public bitset_adaptor< SizeType, 
                               bitset_base<WordTraits, SizeType, Derived> >
    {
      //    private:
    public:
      typedef SizeType size_type;
      typedef typename WordTraits::word_type word_type;

      static size_type s_which_word(size_type pos) {
        return pos / WordTraits::word_size;
      }
      static size_type s_which_byte(size_type pos) {
        return (pos % WordTraits::word_size) / CHAR_BIT;
      }
      static size_type s_which_bit(size_type pos) {
        return pos % WordTraits::word_size;
      }
      static word_type s_mask_bit(size_type pos) {
        return (static_cast<word_type>(1)) << s_which_bit(pos); 
      }
      word_type& m_get_word(size_type pos) {
        return data()[s_which_word(pos)]; 
      }
      word_type m_get_word(size_type pos) const {
        return data()[s_which_word(pos)]; 
      }
      word_type& m_hi_word() { return data()[num_words() - 1]; }
      word_type  m_hi_word() const { return data()[num_words() - 1]; }

      void m_sanitize_highest() {
        size_type extra_bits = size() % WordTraits::word_size;
        if (extra_bits)
          m_hi_word() &= ~((~static_cast<word_type>(0)) << extra_bits);
      }
    public:

      class reference {
        friend class bitset_base;

        word_type *m_word_ptr;
        size_type m_bit_pos;

        // left undefined
        reference();

        reference(bitset_base& b, size_type pos ) {
          m_word_ptr = &b.m_get_word(pos);
          m_bit_pos = s_which_bit(pos);
        }

      public:
        ~reference() {}

        // for b[i] = x;
        reference& operator=(bool x) {
          if ( x )
            *m_word_ptr |= s_mask_bit(m_bit_pos);
          else
            *m_word_ptr &= ~s_mask_bit(m_bit_pos);

          return *this;
        }
        // for b[i] = b[j];
        reference& operator=(const reference& j) {
          if ( (*(j.m_word_ptr) & s_mask_bit(j.m_bit_pos)) )
            *m_word_ptr |= s_mask_bit(m_bit_pos);
          else
            *m_word_ptr &= ~s_mask_bit(m_bit_pos);

          return *this;
        }
        // flips the bit
        bool operator~() const { 
          return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) == 0; 
        }
        // for x = b[i];
        operator bool() const { 
          return (*(m_word_ptr) & s_mask_bit(m_bit_pos)) != 0; 
        }
        // for b[i].flip();
        reference& flip() {
          *m_word_ptr ^= s_mask_bit(m_bit_pos);
          return *this;
        }
      };

      void init_from_ulong(unsigned long val) {
        reset();
        const size_type n = (std::min)(sizeof(unsigned long) * CHAR_BIT,
                                     WordTraits::word_size * num_words());
        for(size_type i = 0; i < n; ++i, val >>= 1)
          if ( val & 0x1 )
            m_get_word(i) |= s_mask_bit(i);
      }
      
      // intersection: this = this & x
      Derived& operator&=(const Derived& x) {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] &= x.data()[i];
        return static_cast<Derived&>(*this);
      }
      // union: this = this | x
      Derived& operator|=(const Derived& x) {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] |= x.data()[i];
        return static_cast<Derived&>(*this);
      }
      // exclusive or: this = this ^ x
      Derived& operator^=(const Derived& x) {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] ^= x.data()[i];
        return static_cast<Derived&>(*this);
      }
      // left shift
      Derived& operator<<=(size_type pos);

      // right shift
      Derived& operator>>=(size_type pos);

      Derived& set() {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] = ~static_cast<word_type>(0);
        m_sanitize_highest();
        return static_cast<Derived&>(*this);
      }

      Derived& set(size_type pos, int val = true)
      {
        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::set(pos,value)"));
        if (val)
          m_get_word(pos) |= s_mask_bit(pos);
        else
          m_get_word(pos) &= ~s_mask_bit(pos);
        return static_cast<Derived&>(*this);
      }
      
      Derived& reset() {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] = 0;
        return static_cast<Derived&>(*this);
      }

      Derived& reset(size_type pos) {
        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::reset(pos)"));
        m_get_word(pos) &= ~s_mask_bit(pos);
        return static_cast<Derived&>(*this);
      }

      // compliment
      Derived operator~() const {
        return Derived(static_cast<const Derived&>(*this)).flip();
      }
      
      Derived& flip() {
        for (size_type i = 0; i < num_words(); ++i)
          data()[i] = ~data()[i];
        m_sanitize_highest();
        return static_cast<Derived&>(*this);
      }
      Derived& flip(size_type pos) {
        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::flip(pos)"));
        m_get_word(pos) ^= s_mask_bit(pos);
        return static_cast<Derived&>(*this);
      }

      // element access
      reference operator[](size_type pos) { return reference(*this, pos); }
      bool operator[](size_type pos) const { return test(pos); }

      unsigned long to_ulong() const;

      // to_string

      
      size_type count() const {
        size_type result = 0;
        const unsigned char* byte_ptr = (const unsigned char*)data();
        const unsigned char* end_ptr = 
          (const unsigned char*)(data() + num_words());
        while ( byte_ptr < end_ptr ) {
          result += bit_count<>::value[*byte_ptr];
          byte_ptr++;
        }
        return result;
      }   
      
      // size() must be provided by Derived class

      bool operator==(const Derived& x) const {
        return std::equal(data(), data() + num_words(), x.data());
      }

      bool operator!=(const Derived& x) const {
        return ! this->operator==(x);
      }

      bool test(size_type pos) const {
        BOOST_ASSERT_THROW(pos < size(), std::out_of_range("boost::bitset::test(pos)"));
        return (m_get_word(pos) & s_mask_bit(pos))
          != static_cast<word_type>(0);
      }

      bool any() const {
        for (size_type i = 0; i < num_words(); ++i) {
          if ( data()[i] != static_cast<word_type>(0) )
            return true;
        }
        return false;
      }
      bool none() const {
        return !any();
      }

      Derived operator<<(size_type pos) const
        { return Derived(static_cast<const Derived&>(*this)) <<= pos; }

      Derived operator>>(size_type pos) const
        { return Derived(static_cast<const Derived&>(*this)) >>= pos; }

      template <class CharT, class Traits, class Alloc>
      void m_copy_from_string(const basic_string<CharT,Traits,Alloc>& s,
                              size_type pos, size_type n)
      {
        reset();
        const size_type nbits = (std::min)(size(), (std::min)(n, s.size() - pos));
        for (size_type i = 0; i < nbits; ++i) {
          switch(s[pos + nbits - i - 1]) {
          case '0':
            break;
          case '1':
            this->set(i);
            break;
          default:
            throw std::invalid_argument
              ("boost::bitset_base::m_copy_from_string(s, pos, n)");
          }
        }
      }

      template <class CharT, class Traits, class Alloc>
      void m_copy_to_string(basic_string<CharT, Traits, Alloc>& s) const
      {