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

//

// (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_DETAIL_DYNAMIC_BITSET_HPP

#define BOOST_DETAIL_DYNAMIC_BITSET_HPP

#include <cstddef> // for std::size_t

#include "boost/config.hpp"

#include "boost/detail/workaround.hpp"

//#include "boost/static_assert.hpp" // gps

namespace boost {

  namespace detail {

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

    }

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

    namespace dynamic_bitset_count_impl {

    typedef unsigned char byte_type;

    enum mode { access_by_bytes, access_by_blocks };

    template <mode> struct mode_to_type {};

    // 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*/,

                                 mode_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,

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

     }

    } // dynamic_bitset_count_impl

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

    // Some library implementations simply return a dummy

    // value such as

    //

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

    //

    // from vector<>::max_size. This tries to get out 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 dynamic_bitset_allowed_block_type {

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

    };

    template <>

    struct dynamic_bitset_allowed_block_type<bool> {

        enum { value = false };

    };

  } // namespace detail

} // namespace boost

#endif // include guard