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

//

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

//        Copyright (c) 2003-2006, 2008 Gennaro Prota

//

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

//

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

#ifndef BOOST_DETAIL_DYNAMIC_BITSET_HPP

#define BOOST_DETAIL_DYNAMIC_BITSET_HPP

#include <cstddef>

#include "boost/config.hpp"

#include "boost/detail/workaround.hpp"

namespace boost {

  namespace detail {

  namespace dynamic_bitset_impl {

    // Gives (read-)access to the object representation

    // of an object of type T (3.9p4). CANNOT be used

    // on a base sub-object

    //

    template <typename T>

    inline const unsigned char * object_representation (T* p)

    {

        return static_cast<const unsigned char *>(static_cast<const void *>(p));

    }

    template<typename T, int amount, int width /* = default */>

    struct shifter

    {

        static void left_shift(T & v) {

            amount >= width ? (v = 0)

                : (v >>= BOOST_DYNAMIC_BITSET_WRAP_CONSTANT(amount));

        }

    };

    // ------- count function implementation --------------

    typedef unsigned char byte_type;

    // These two entities

    //

    //     enum mode { access_by_bytes, access_by_blocks };

    //     template <mode> struct mode_to_type {};

    //

    // were removed, since the regression logs (as of 24 Aug 2008)

    // showed that several compilers had troubles with recognizing

    //

    //   const mode m = access_by_bytes

    //

    // as a constant expression

    //

    // * So, we'll use bool, instead of enum *.

    //

    template <bool value>

    struct value_to_type

    {

        value_to_type() {}

    };

    const bool access_by_bytes = true;

    const bool access_by_blocks = false;

    // the table: wrapped in a class template, so

    // that it is only instantiated if/when needed

    //

    template <bool dummy_name = true>

    struct count_table { static const byte_type table[]; };

    template <>

    struct count_table<false> { /* no table */ };

     const unsigned int table_width = 8;

     template <bool b>

     const byte_type count_table<b>::table[] =

     {

       // Automatically generated by GPTableGen.exe v.1.0

       //

     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

     2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

     3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

     };

     // overload for access by bytes

     //

     template <typename Iterator>

     inline std::size_t do_count(Iterator first, std::size_t length,

                                 int /*dummy param*/,

                                 value_to_type<access_by_bytes>* )

     {

         std::size_t num = 0;

         if (length)

         {

             const byte_type * p = object_representation(&*first);

             length *= sizeof(*first);

              do {

                 num += count_table<>::table[*p];

                 ++p;

                 --length;

             } while (length);

         }

         return num;

     }

     // overload for access by blocks

     //

     template <typename Iterator, typename ValueType>

     inline std::size_t do_count(Iterator first, std::size_t length, ValueType,

                                 value_to_type<access_by_blocks>*)

     {

         std::size_t num = 0;

         while (length){

             ValueType value = *first;

             while (value) {

                 num += count_table<>::table[value & ((1u<<table_width) - 1)];

                 value >>= table_width;

             }

             ++first;

             --length;

         }

         return num;

     }

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

    // Some library implementations simply return a dummy

    // value such as

    //

    //   size_type(-1) / sizeof(T)

    //

    // from vector<>::max_size. This tries to get more

    // meaningful info.

    //

    template <typename T>

    typename T::size_type vector_max_size_workaround(const T & v) {

      typedef typename T::allocator_type allocator_type;

      const typename allocator_type::size_type alloc_max =

                                                  v.get_allocator().max_size();

      const typename T::size_type container_max = v.max_size();

      return alloc_max < container_max?

                    alloc_max :

                    container_max;

    }

    // for static_asserts

    template <typename T>

    struct allowed_block_type {

        enum { value = T(-1) > 0 }; // ensure T has no sign

    };

    template <>

    struct allowed_block_type<bool> {

        enum { value = false };

    };

    template <typename T>

    struct is_numeric {

        enum { value = false };

    };

#   define BOOST_dynamic_bitset_is_numeric(x)       \

                template<>                          \

                struct is_numeric< x > {            \

                    enum { value = true };          \

                }                                /**/

    BOOST_dynamic_bitset_is_numeric(bool);

    BOOST_dynamic_bitset_is_numeric(char);

#if !defined(BOOST_NO_INTRINSIC_WCHAR_T)

    BOOST_dynamic_bitset_is_numeric(wchar_t);

#endif

    BOOST_dynamic_bitset_is_numeric(signed char);

    BOOST_dynamic_bitset_is_numeric(short int);

    BOOST_dynamic_bitset_is_numeric(int);

    BOOST_dynamic_bitset_is_numeric(long int);

    BOOST_dynamic_bitset_is_numeric(unsigned char);

    BOOST_dynamic_bitset_is_numeric(unsigned short);

    BOOST_dynamic_bitset_is_numeric(unsigned int);

    BOOST_dynamic_bitset_is_numeric(unsigned long);

#if defined(BOOST_HAS_LONG_LONG)

    BOOST_dynamic_bitset_is_numeric(::boost::long_long_type);

    BOOST_dynamic_bitset_is_numeric(::boost::ulong_long_type);

#endif

    // intentionally omitted

    //BOOST_dynamic_bitset_is_numeric(float);

    //BOOST_dynamic_bitset_is_numeric(double);

    //BOOST_dynamic_bitset_is_numeric(long double);

#undef BOOST_dynamic_bitset_is_numeric

  } // dynamic_bitset_impl

  } // namespace detail

} // namespace boost

#endif // include guard