// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
// Copyright (C) 2005-2009 Daniel James
// 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_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED

#include <cstddef>
#include <utility>
#include <algorithm>
#include <boost/limits.hpp>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <boost/preprocessor/seq/enum.hpp>
#include <boost/unordered/detail/fwd.hpp>

namespace boost { namespace unordered_detail {

    ////////////////////////////////////////////////////////////////////////////
    // convert double to std::size_t

    inline std::size_t double_to_size_t(double f)
    {
        return f >= static_cast<double>(
            (std::numeric_limits<std::size_t>::max)()) ?
            (std::numeric_limits<std::size_t>::max)() :
            static_cast<std::size_t>(f);
    }

    ////////////////////////////////////////////////////////////////////////////
    // primes

#define BOOST_UNORDERED_PRIMES \
    (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
    (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
    (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
    (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
    (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
    (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
    (1610612741ul)(3221225473ul)(4294967291ul)

    template<class T> struct prime_list_template
    {
        static std::size_t const value[];

#if !defined(SUNPRO_CC)
        static std::ptrdiff_t const length;
#else
        static std::ptrdiff_t const length
            = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
#endif
    };

    template<class T>
    std::size_t const prime_list_template<T>::value[] = {
        BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
    };

#if !defined(SUNPRO_CC)
    template<class T>
    std::ptrdiff_t const prime_list_template<T>::length
        = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
#endif

#undef BOOST_UNORDERED_PRIMES

    typedef prime_list_template<std::size_t> prime_list;

    // no throw
    inline std::size_t next_prime(std::size_t num) {
        std::size_t const* const prime_list_begin = prime_list::value;
        std::size_t const* const prime_list_end = prime_list_begin +
            prime_list::length;
        std::size_t const* bound =
            std::lower_bound(prime_list_begin, prime_list_end, num);
        if(bound == prime_list_end)
            bound--;
        return *bound;
    }

    // no throw
    inline std::size_t prev_prime(std::size_t num) {
        std::size_t const* const prime_list_begin = prime_list::value;
        std::size_t const* const prime_list_end = prime_list_begin +
            prime_list::length;
        std::size_t const* bound =
            std::upper_bound(prime_list_begin,prime_list_end, num);
        if(bound != prime_list_begin)
            bound--;
        return *bound;
    }

    ////////////////////////////////////////////////////////////////////////////
    // pair_cast - because some libraries don't have the full pair constructors.

    template <class Dst1, class Dst2, class Src1, class Src2>
    inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x)
    {
        return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second));
    }

    ////////////////////////////////////////////////////////////////////////////
    // insert_size/initial_size

#if !defined(BOOST_NO_STD_DISTANCE)
    using ::std::distance;
#else
    template <class ForwardIterator>
    inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
        std::size_t x;
        std::distance(i, j, x);
        return x;
    }
#endif

    template <class I>
    inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag)
    {
        return std::distance(i, j);
    }

    template <class I>
    inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag)
    {
        return 1;
    }

    template <class I>
    inline std::size_t insert_size(I i, I j)
    {
        BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
            iterator_traversal_tag;
        return insert_size(i, j, iterator_traversal_tag);
    }
    
    template <class I>
    inline std::size_t initial_size(I i, I j,
        std::size_t num_buckets = boost::unordered_detail::default_bucket_count)
    {
        return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1,
            num_buckets);
    }

    ////////////////////////////////////////////////////////////////////////////
    // Node Constructors

#if defined(BOOST_UNORDERED_STD_FORWARD)

    template <class T, class... Args>
    inline void construct_impl(T*, void* address, Args&&... args)
    {
        new(address) T(std::forward<Args>(args)...);
    }

#if defined(BOOST_UNORDERED_CPP0X_PAIR)
    template <class First, class Second, class Key, class Arg0, class... Args>
    inline void construct_impl(std::pair<First, Second>*, void* address,
        Key&& k, Arg0&& arg0, Args&&... args)
    )
    {
        new(address) std::pair<First, Second>(k,
            Second(arg0, std::forward<Args>(args)...);
    }
#endif

#else

#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _)                       \
    template <                                                                 \
        class T,                                                               \
        BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)                           \
    >                                                                          \
    inline void construct_impl(                                                \
        T*, void* address,                                                     \
        BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)                         \
    )                                                                          \
    {                                                                          \
        new(address) T(                                                        \
            BOOST_UNORDERED_CALL_PARAMS(z, num_params));                       \
    }                                                                          \
                                                                               \
    template <class First, class Second, class Key,                            \
        BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)                           \
    >                                                                          \
    inline void construct_impl(                                                \
        std::pair<First, Second>*, void* address,                              \
        Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params))          \
    {                                                                          \
        new(address) std::pair<First, Second>(k,                               \
            Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params)));               \
    }

    BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
        BOOST_UNORDERED_CONSTRUCT_IMPL, _)

#undef BOOST_UNORDERED_CONSTRUCT_IMPL
#endif

    // hash_node_constructor
    //
    // Used to construct nodes in an exception safe manner.

    template <class Alloc, class Grouped>
    class hash_node_constructor
    {
        typedef hash_buckets<Alloc, Grouped> buckets;
        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
        typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;

        buckets& buckets_;
        real_node_ptr node_;
        bool node_constructed_;
        bool value_constructed_;

    public:

        hash_node_constructor(buckets& m) :
            buckets_(m),
            node_(),
            node_constructed_(false),
            value_constructed_(false)
        {
        }

        ~hash_node_constructor();
        void construct_preamble();

#if defined(BOOST_UNORDERED_STD_FORWARD)
        template <class... Args>
        void construct(Args&&... args)
        {
            construct_preamble();
            construct_impl((value_type*) 0, node_->address(),
                std::forward<Args>(args)...);
            value_constructed_ = true;
        }
#else

#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _)                            \
        template <                                                             \
            BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)                       \
        >                                                                      \
        void construct(                                                        \
            BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)                     \
        )                                                                      \
        {                                                                      \
            construct_preamble();                                              \
            construct_impl(                                                    \
                (value_type*) 0, node_->address(),                             \
                BOOST_UNORDERED_CALL_PARAMS(z, num_params)                     \
            );                                                                 \
            value_constructed_ = true;                                         \
        }

        BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
            BOOST_UNORDERED_CONSTRUCT, _)

#undef BOOST_UNORDERED_CONSTRUCT

#endif
        template <class K, class M>
        void construct_pair(K const& k, M*)
        {
            construct_preamble();
            new(node_->address()) value_type(k, M());                    
            value_constructed_ = true;
        }

        value_type& value() const
        {
            BOOST_ASSERT(node_);
            return node_->value();
        }

        // no throw
        BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
        {
            real_node_ptr p = node_;
            node_ = real_node_ptr();
            // node_ptr cast
            return buckets_.bucket_alloc().address(*p);
        }

    private:
        hash_node_constructor(hash_node_constructor const&);
        hash_node_constructor& operator=(hash_node_constructor const&);
    };
    
    // hash_node_constructor

    template <class Alloc, class Grouped>
    inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor()
    {
        if (node_) {
            if (value_constructed_) {
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
                struct dummy { hash_node<Alloc, Grouped> x; };
#endif
                boost::unordered_detail::destroy(&node_->value());
            }

            if (node_constructed_)
                buckets_.node_alloc().destroy(node_);

            buckets_.node_alloc().deallocate(node_, 1);
        }
    }

    template <class Alloc, class Grouped>
    inline void hash_node_constructor<Alloc, Grouped>::construct_preamble()
    {
        if(!node_) {
            node_constructed_ = false;
            value_constructed_ = false;

            node_ = buckets_.node_alloc().allocate(1);
            buckets_.node_alloc().construct(node_, node());
            node_constructed_ = true;
        }
        else {
            BOOST_ASSERT(node_constructed_ && value_constructed_);
            boost::unordered_detail::destroy(&node_->value());
            value_constructed_ = false;
        }
    }
}}

#endif