// --------------------------------------------------
//
// (C) Copyright Chuck Allison and Jeremy Siek 2001 - 2002.
// (C) Copyright Gennaro Prota                 2003 - 2006.
//
// 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.
//
//  $Revision: 41316 $ $Date: 2007-11-23 12:03:14 -0500 (Fri, 23 Nov 2007) $ - $Name$

#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"


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

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

    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