// --------------------------------------------------

//

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

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

//

// 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)

//

// -----------------------------------------------------------

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

#ifndef BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

#define BOOST_DYNAMIC_BITSET_DYNAMIC_BITSET_HPP

#include <cassert>

#include <string>

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

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

#include <vector>

#include <climits>             // for CHAR_BIT

#include "boost/dynamic_bitset/config.hpp"

#ifndef BOOST_NO_STD_LOCALE

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

#endif

#if defined(BOOST_OLD_IOSTREAMS)

#  include <iostream.h>

#  include <ctype.h> // for isspace

#else

#  include <istream>

#  include <ostream>

#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/limits.hpp"

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

namespace boost {

template

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

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

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

# else

   <typename Block, typename Allocator>

# endif

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.

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

public:

    typedef Block block_type;

    typedef Allocator allocator_type;

    typedef std::size_t size_type;

    typedef int block_width_type; // gps

    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));

public:

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

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

    //

    class reference

    {

        friend class dynamic_bitset<Block, Allocator>;

        // the one and only non-copy ctor

        reference(block_type & b, int pos)

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

        {}

        void operator&(); // left undefined

    public:

        // copy constructor: compiler generated

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

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

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

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

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

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

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

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

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

     private:

        block_type & m_block;

        const block_type m_mask;

        void do_set() { m_block |= m_mask; }

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

        void do_flip() { m_block ^= m_mask; }

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

    };

    typedef bool const_reference;

    // constructors, etc.

    explicit

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

    explicit

    dynamic_bitset(size_type num_bits, unsigned long value = 0,

               const Allocator& alloc = Allocator());

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

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

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

    // formatting convention: operator>>.

    //

    // NOTE:

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

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

    // NOTE 2: 

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

    template <typename CharT, typename Traits, typename Alloc>

    dynamic_bitset(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,

        size_type num_bits = npos,

        const Allocator& alloc = Allocator())

    :m_bits(alloc),

     m_num_bits(0)

    {

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

    }

    template <typename CharT, typename Traits, typename Alloc>

    explicit

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

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

    :m_bits(Allocator()),

     m_num_bits(0)

    {

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

                       npos, Allocator());

    }

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

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

    template <typename BlockInputIterator>

    dynamic_bitset(BlockInputIterator first, BlockInputIterator last,

                   const Allocator& alloc = Allocator())

    :m_bits(first, last, alloc),

     m_num_bits(m_bits.size() * bits_per_block)

    {}

    // copy constructor

    dynamic_bitset(const dynamic_bitset& b);

    ~dynamic_bitset();

    void swap(dynamic_bitset& b);

    dynamic_bitset& operator=(const dynamic_bitset& b);

    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 append(Block block);

    template <typename BlockInputIterator>

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

    {

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

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

    }

    template <typename BlockInputIterator>

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

    {

        assert(first != last);

        block_width_type r = count_extra_bits();

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

        m_bits.reserve(num_blocks() + d);

        if (r == 0) {

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

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

        }

        else {

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

            do {

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

                ++first;

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

            } while (first != last);

        }

        m_num_bits += bits_per_block * d;

    }

    template <typename BlockInputIterator>

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

    {

        if (first != last) {

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

            m_append(first, last, cat);

        }

    }

    // bitset operations

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

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

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

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

    dynamic_bitset& operator<<=(size_type n);

    dynamic_bitset& operator>>=(size_type n);

    dynamic_bitset operator<<(size_type n) const;

    dynamic_bitset operator>>(size_type n) const;

    // basic bit operations

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

    dynamic_bitset& set();

    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 any() const;

    bool none() const;

    dynamic_bitset operator~() const;

    size_type count() const;

    // 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;

#if 0 // gps

    void reserve(size_type n);

    size_type capacity() const;

#endif

    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;

    // lookup

    size_type find_first() const;

    size_type find_next(size_type pos) const;

#if !defined BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS

    // lexicographical comparison

    template <typename B, typename A>

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

                           const dynamic_bitset<B, A>& b);

    template <typename B, typename A>

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

                          const dynamic_bitset<B, A>& b);

    template <typename B, typename A, typename BlockOutputIterator>

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

                               BlockOutputIterator result);

    template <typename BlockIterator, typename B, typename A>

    friend void from_block_range(BlockIterator first, BlockIterator last,

                                 dynamic_bitset<B, A>& result);

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

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

                                                         dynamic_bitset<B, A>& b);

    template <typename B, typename A, typename stringT>

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

#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<int>(pos % bits_per_block); }

    static Block bit_mask(size_type pos) { 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,

        size_type num_bits,

        const Allocator& alloc)

    {

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

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

        typedef typename StrT::traits_type Tr;

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

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

        m_bits.resize(calc_num_blocks(sz));

        m_num_bits = sz;

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

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

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

        typename StrT::size_type i = 0;

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

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

            assert( Tr::eq(c, one)

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

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

                set(i);

        }

    }

BOOST_DYNAMIC_BITSET_PRIVATE:

    bool m_unchecked_test(size_type pos) const;

    static size_type calc_num_blocks(size_type num_bits);

    Block&        m_highest_block();

    const Block&  m_highest_block() const;

    buffer_type m_bits; // [gps] to be renamed

    size_type   m_num_bits;

    class bit_appender;

    friend class bit_appender;

    class bit_appender {

      // helper for stream >>

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

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

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

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

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

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

      //

      dynamic_bitset & bs;

      size_type n;

      Block mask;

      Block * current;

    public:

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

        ~bit_appender() {

            // reverse the order of blocks, shift

            // if needed, and then resize

            //

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

            const block_width_type offs = bit_index(n);

            if (offs)

                bs >>= (bits_per_block - offs);

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

            assert(bs.m_check_invariants());

        }

        inline void do_append(bool value) {

            if (mask == 0) {

                bs.append(Block(0));

                current = &bs.m_highest_block();

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

            }

            if(value)

                *current |= mask;

            mask /= 2;

            ++n;

        }

        size_type get_count() const { return n; }

    };

};

#if BOOST_WORKAROUND( __IBMCPP__, <=600 )

// Workaround for IBM's AIX platform.

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

template<typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::block_width_type const

dynamic_bitset<Block, Allocator>::bits_per_block;

template<typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>::block_width_type const

dynamic_bitset<Block, Allocator>::ulong_width;

#endif

// Global Functions:

// comparison

template <typename Block, typename Allocator>

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

                const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>

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

                const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>

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

               const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>

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

                const dynamic_bitset<Block, Allocator>& b);

// stream operators

#ifdef BOOST_OLD_IOSTREAMS

template <typename Block, typename Allocator>

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

                         const dynamic_bitset<Block, Allocator>& b);

template <typename Block, typename Allocator>

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

#else

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

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

//

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

std::basic_ostream<Ch, Tr>&

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

           const dynamic_bitset<Block, Alloc>& b);

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

std::basic_istream<Ch, Tr>&

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

           dynamic_bitset<Block, Alloc>& b);

#endif

// bitset operations

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>

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

          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>

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

          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>

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

          const dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator>

dynamic_bitset<Block, Allocator>

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

          const dynamic_bitset<Block, Allocator>& b2);

// namespace scope swap

template<typename Block, typename Allocator>

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

          dynamic_bitset<Block, Allocator>& b2);

template <typename Block, typename Allocator, typename stringT>

void

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

template <typename Block, typename Allocator, typename BlockOutputIterator>

void

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

               BlockOutputIterator result);

// gps - check docs with Jeremy

//

template <typename BlockIterator, typename B, typename A>

inline void

from_block_range(BlockIterator first, BlockIterator last,

                 dynamic_bitset<B, A>& result)

{

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

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

}

//=============================================================================

// dynamic_bitset implementation