/* Copyright 2003-2010 Joaquin M Lopez Munoz.
 * 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/multi_index for library home page.
 */

#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/call_traits.hpp>
#include <boost/detail/allocator_utilities.hpp>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/limits.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/multi_index/detail/access_specifier.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/bucket_array.hpp>
#include <boost/multi_index/detail/hash_index_iterator.hpp>
#include <boost/multi_index/detail/index_node_base.hpp>
#include <boost/multi_index/detail/modify_key_adaptor.hpp>
#include <boost/multi_index/detail/safe_ctr_proxy.hpp>
#include <boost/multi_index/detail/safe_mode.hpp>
#include <boost/multi_index/detail/scope_guard.hpp>
#include <boost/multi_index/hashed_index_fwd.hpp>
#include <boost/tuple/tuple.hpp>
#include <cstddef>
#include <functional>
#include <utility>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/serialization/nvp.hpp>
#endif

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \
  detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
    detail::make_obj_guard(*this,&hashed_index::check_invariant_);           \
  BOOST_JOIN(check_invariant_,__LINE__).touch();
#else
#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* hashed_index adds a layer of hashed indexing to a given Super */

/* Most of the implementation of unique and non-unique indices is
 * shared. We tell from one another on instantiation time by using
 * these tags.
 */

struct hashed_unique_tag{};
struct hashed_non_unique_tag{};

template<
  typename KeyFromValue,typename Hash,typename Pred,
  typename SuperMeta,typename TagList,typename Category
>
class hashed_index:
  BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
  ,public safe_ctr_proxy_impl<
    hashed_index_iterator<
      hashed_index_node<typename SuperMeta::type::node_type>,
      bucket_array<typename SuperMeta::type::final_allocator_type> >,
    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
#else
  ,public safe_mode::safe_container<
    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
#endif
#endif

{ 
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
    BOOST_WORKAROUND(__MWERKS__,<=0x3003)
/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
 * lifetime of const references bound to temporaries --precisely what
 * scopeguards are.
 */

#pragma parse_mfunc_templ off
#endif

  typedef typename SuperMeta::type                   super;

protected:
  typedef hashed_index_node<
    typename super::node_type>                       node_type;

private:
  typedef typename node_type::impl_type              node_impl_type;
  typedef typename node_impl_type::pointer           node_impl_pointer;
  typedef bucket_array<
    typename super::final_allocator_type>            bucket_array_type;

public:
  /* types */

  typedef typename KeyFromValue::result_type         key_type;
  typedef typename node_type::value_type             value_type;
  typedef KeyFromValue                               key_from_value;
  typedef Hash                                       hasher;
  typedef Pred                                       key_equal;
  typedef tuple<std::size_t,
    key_from_value,hasher,key_equal>                 ctor_args;
  typedef typename super::final_allocator_type       allocator_type;
  typedef typename allocator_type::pointer           pointer;
  typedef typename allocator_type::const_pointer     const_pointer;
  typedef typename allocator_type::reference         reference;
  typedef typename allocator_type::const_reference   const_reference;
  typedef std::size_t                                size_type;      
  typedef std::ptrdiff_t                             difference_type;

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
  typedef safe_mode::safe_iterator<
    hashed_index_iterator<
      node_type,bucket_array_type>,
    safe_ctr_proxy<
      hashed_index_iterator<
        node_type,bucket_array_type> > >             iterator;
#else
  typedef safe_mode::safe_iterator<
    hashed_index_iterator<
      node_type,bucket_array_type>,
    hashed_index>                                    iterator;
#endif
#else
  typedef hashed_index_iterator<
    node_type,bucket_array_type>                     iterator;
#endif

  typedef iterator                                   const_iterator;

  typedef iterator                                   local_iterator;
  typedef const_iterator                             const_local_iterator;
  typedef TagList                                    tag_list;

protected:
  typedef typename super::final_node_type     final_node_type;
  typedef tuples::cons<
    ctor_args, 
    typename super::ctor_args_list>           ctor_args_list;
  typedef typename mpl::push_front<
    typename super::index_type_list,
    hashed_index>::type                       index_type_list;
  typedef typename mpl::push_front<
    typename super::iterator_type_list,
    iterator>::type                           iterator_type_list;
  typedef typename mpl::push_front<
    typename super::const_iterator_type_list,
    const_iterator>::type                     const_iterator_type_list;
  typedef typename super::copy_map_type       copy_map_type;

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  typedef typename super::index_saver_type    index_saver_type;
  typedef typename super::index_loader_type   index_loader_type;
#endif

private:
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
  typedef safe_ctr_proxy_impl<
    hashed_index_iterator<
      node_type,bucket_array_type>,
    hashed_index>                             safe_super;
#else
  typedef safe_mode::safe_container<
    hashed_index>                             safe_super;
#endif
#endif

  typedef typename call_traits<value_type>::param_type value_param_type;
  typedef typename call_traits<
    key_type>::param_type                              key_param_type;

public:

  /* construct/destroy/copy
   * Default and copy ctors are in the protected section as indices are
   * not supposed to be created on their own. No range ctor either.
   */

  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
  {
    this->final()=x.final();
    return *this;
  }

  allocator_type get_allocator()const
  {
    return this->final().get_allocator();
  }

  /* size and capacity */

  bool      empty()const{return this->final_empty_();}
  size_type size()const{return this->final_size_();}
  size_type max_size()const{return this->final_max_size_();}

  /* iterators */

  iterator begin()
  {
    return make_iterator(
      node_type::from_impl(buckets.at(first_bucket)->next()));
  }

  const_iterator begin()const
  {
    return make_iterator(
      node_type::from_impl(buckets.at(first_bucket)->next()));
  }

  iterator       end(){return make_iterator(header());}
  const_iterator end()const{return make_iterator(header());}

  const_iterator cbegin()const{return begin();}
  const_iterator cend()const{return end();}

  iterator iterator_to(const value_type& x)
  {
    return make_iterator(node_from_value<node_type>(&x));
  }

  const_iterator iterator_to(const value_type& x)const
  {
    return make_iterator(node_from_value<node_type>(&x));
  }

  /* modifiers */

  std::pair<iterator,bool> insert(value_param_type x)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    std::pair<final_node_type*,bool> p=this->final_insert_(x);
    return std::pair<iterator,bool>(make_iterator(p.first),p.second);
  }

  iterator insert(iterator position,value_param_type x)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    std::pair<final_node_type*,bool> p=this->final_insert_(
      x,static_cast<final_node_type*>(position.get_node()));
    return make_iterator(p.first);
  }
    
  template<typename InputIterator>
  void insert(InputIterator first,InputIterator last)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    iterator hint=end();
    for(;first!=last;++first)hint=insert(hint,*first);
  }

  iterator erase(iterator position)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
    return position;
  }

  size_type erase(key_param_type k)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    size_type         s=0;
    std::size_t       buc=buckets.position(hash(k));
    node_impl_pointer x=buckets.at(buc);
    node_impl_pointer y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        bool b;
        do{
          node_impl_pointer z=y->next();
          b=z!=x&&eq(
            key(node_type::from_impl(y)->value()),
            key(node_type::from_impl(z)->value()));
          this->final_erase_(
            static_cast<final_node_type*>(node_type::from_impl(y)));
          y=z;
          ++s;
        }while(b);
        break;
      }
      y=y->next();
    }
    return s;
  }

  iterator erase(iterator first,iterator last)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
    BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    while(first!=last){
      first=erase(first);
    }
    return first;
  }

  bool replace(iterator position,value_param_type x)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    return this->final_replace_(
      x,static_cast<final_node_type*>(position.get_node()));
  }

  template<typename Modifier>
  bool modify(iterator position,Modifier mod)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    /* MSVC++ 6.0 optimizer on safe mode code chokes if this
     * this is not added. Left it for all compilers as it does no
     * harm.
     */

    position.detach();
#endif

    return this->final_modify_(
      mod,static_cast<final_node_type*>(position.get_node()));
  }

  template<typename Modifier,typename Rollback>
  bool modify(iterator position,Modifier mod,Rollback back)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    /* MSVC++ 6.0 optimizer on safe mode code chokes if this
     * this is not added. Left it for all compilers as it does no
     * harm.
     */

    position.detach();
#endif

    return this->final_modify_(
      mod,back,static_cast<final_node_type*>(position.get_node()));
  }

  template<typename Modifier>
  bool modify_key(iterator position,Modifier mod)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    return modify(
      position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
  }

  template<typename Modifier,typename Rollback>
  bool modify_key(iterator position,Modifier mod,Rollback back)
  {
    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    return modify(
      position,
      modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
      modify_key_adaptor<Rollback,value_type,KeyFromValue>(back,key));
  }

  void clear()
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    this->final_clear_();
  }

  void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    this->final_swap_(x.final());
  }

  /* observers */

  key_from_value key_extractor()const{return key;}
  hasher         hash_function()const{return hash;}
  key_equal      key_eq()const{return eq;}
  
  /* lookup */

  /* Internally, these ops rely on const_iterator being the same
   * type as iterator.
   */

  template<typename CompatibleKey>
  iterator find(const CompatibleKey& k)const
  {
    return find(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  iterator find(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    std::size_t       buc=buckets.position(hash(k));
    node_impl_pointer x=buckets.at(buc);
    node_impl_pointer y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        return make_iterator(node_type::from_impl(y));
      }
      y=y->next();
    }
    return end();
  }

  template<typename CompatibleKey>
  size_type count(const CompatibleKey& k)const
  {
    return count(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  size_type count(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    size_type         res=0;
    std::size_t       buc=buckets.position(hash(k));
    node_impl_pointer x=buckets.at(buc);
    node_impl_pointer y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        do{
          ++res;
          y=y->next();
        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
        break;
      }
      y=y->next();
    }
    return res;
  }

  template<typename CompatibleKey>
  std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
  {
    return equal_range(k,hash,eq);
  }

  template<
    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
  >
  std::pair<iterator,iterator> equal_range(
    const CompatibleKey& k,
    const CompatibleHash& hash,const CompatiblePred& eq)const
  {
    std::size_t       buc=buckets.position(hash(k));
    node_impl_pointer x=buckets.at(buc);
    node_impl_pointer y=x->next();
    while(y!=x){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        node_impl_pointer y0=y;
        do{
          y=y->next();
        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
        if(y==x){
          do{
            ++y;
          }while(y==y->next());
          y=y->next();
        }
        return std::pair<iterator,iterator>(
          make_iterator(node_type::from_impl(y0)),
          make_iterator(node_type::from_impl(y)));
      }
      y=y->next();
    }
    return std::pair<iterator,iterator>(end(),end());
  }

  /* bucket interface */

  size_type bucket_count()const{return buckets.size();}
  size_type max_bucket_count()const{return static_cast<size_type>(-1);}

  size_type bucket_size(size_type n)const
  {
    size_type         res=0;
    node_impl_pointer x=buckets.at(n);
    node_impl_pointer y=x->next();
    while(y!=x){
      ++res;
      y=y->next();
    }
    return res;
  }

  size_type bucket(key_param_type k)const
  {
    return buckets.position(hash(k));
  }

  local_iterator begin(size_type n)
  {
    return const_cast<const hashed_index*>(this)->begin(n);
  }

  const_local_iterator begin(size_type n)const
  {
    node_impl_pointer x=buckets.at(n);
    node_impl_pointer y=x->next();
    if(y==x)return end();
    return make_iterator(node_type::from_impl(y));
  }

  local_iterator end(size_type n)
  {
    return const_cast<const hashed_index*>(this)->end(n);
  }

  const_local_iterator end(size_type n)const
  {
    node_impl_pointer x=buckets.at(n);
    if(x==x->next())return end();
    do{
      ++x;
    }while(x==x->next());
    return make_iterator(node_type::from_impl(x->next()));
  }

  const_local_iterator cbegin(size_type n)const{return begin(n);}
  const_local_iterator cend(size_type n)const{return end(n);}

  local_iterator local_iterator_to(const value_type& x)
  {
    return make_iterator(node_from_value<node_type>(&x));
  }

  const_local_iterator local_iterator_to(const value_type& x)const
  {
    return make_iterator(node_from_value<node_type>(&x));
  }

  /* hash policy */

  float load_factor()const{return static_cast<float>(size())/bucket_count();}
  float max_load_factor()const{return mlf;}
  void  max_load_factor(float z){mlf=z;calculate_max_load();}

  void rehash(size_type n)
  {
    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
    if(size()<max_load&&n<=bucket_count())return;

    size_type bc =(std::numeric_limits<size_type>::max)();
    float     fbc=static_cast<float>(1+size()/mlf);
    if(bc>fbc){
      bc=static_cast<size_type>(fbc);
      if(bc<n)bc=n;
    }
    unchecked_rehash(bc);
  }

BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
  hashed_index(const ctor_args_list& args_list,const allocator_type& al):
    super(args_list.get_tail(),al),
    key(tuples::get<1>(args_list.get_head())),
    hash(tuples::get<2>(args_list.get_head())),
    eq(tuples::get<3>(args_list.get_head())),
    buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
    mlf(1.0),
    first_bucket(buckets.size())
  {
    calculate_max_load();
  }

  hashed_index(
    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
    super(x),

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super(),
#endif

    key(x.key),
    hash(x.hash),
    eq(x.eq),
    buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
    mlf(x.mlf),
    max_load(x.max_load),
    first_bucket(x.first_bucket)
  {
    /* Copy ctor just takes the internal configuration objects from x. The rest
     * is done in subsequent call to copy_().
     */
  }

  ~hashed_index()
  {
    /* the container is guaranteed to be empty by now */
  }

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  iterator make_iterator(node_type* node)
  {
    return iterator(node,&buckets,this);
  }

  const_iterator make_iterator(node_type* node)const
  {
    return const_iterator(
      node,
      &const_cast<bucket_array_type&>(buckets),
      const_cast<hashed_index*>(this));
  }
#else
  iterator make_iterator(node_type* node)
  {
    return iterator(node,&buckets);
  }

  const_iterator make_iterator(node_type* node)const
  {
    return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
  }
#endif

  void copy_(
    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
    const copy_map_type& map)
  {
    for(node_impl_pointer begin_org=x.buckets.begin(),
                          begin_cpy=buckets.begin(),
                          end_org=x.buckets.end();
        begin_org!=end_org;++begin_org,++begin_cpy){

      node_impl_pointer next_org=begin_org->next();
      node_impl_pointer cpy=begin_cpy;
      while(next_org!=begin_org){
        cpy->next()=
          static_cast<node_type*>(
            map.find(
              static_cast<final_node_type*>(
                node_type::from_impl(next_org))))->impl();
        next_org=next_org->next();
        cpy=cpy->next();
      }
      cpy->next()=begin_cpy;
    }

    super::copy_(x,map);
  }

  node_type* insert_(value_param_type v,node_type* x)
  {
    reserve(size()+1);

    std::size_t       buc=find_bucket(v);
    node_impl_pointer pos=buckets.at(buc);
    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,x));
    if(res==x){
      link(x,pos);
      if(first_bucket>buc)first_bucket=buc;
    }
    return res;
  }

  node_type* insert_(value_param_type v,node_type* position,node_type* x)
  {
    reserve(size()+1);

    std::size_t       buc=find_bucket(v);
    node_impl_pointer pos=buckets.at(buc);
    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
    if(res==x){
      link(x,pos);
      if(first_bucket>buc)first_bucket=buc;
    }
    return res;
  }

  void erase_(node_type* x)
  {
    unlink(x);
    first_bucket=buckets.first_nonempty(first_bucket);
    super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    detach_iterators(x);
#endif
  }

  void delete_all_nodes_()
  {
    for(node_impl_pointer x=buckets.begin(),x_end=buckets.end();
        x!=x_end;++x){
      node_impl_pointer y=x->next();
      while(y!=x){
        node_impl_pointer z=y->next();
        this->final_delete_node_(
          static_cast<final_node_type*>(node_type::from_impl(y)));
        y=z;
      }
    }
  }

  void clear_()
  {
    super::clear_();
    buckets.clear();
    first_bucket=buckets.size();

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super::detach_dereferenceable_iterators();
#endif
  }

  void swap_(
    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
  {
    std::swap(key,x.key);
    std::swap(hash,x.hash);
    std::swap(eq,x.eq);
    buckets.swap(x.buckets);
    std::swap(mlf,x.mlf);
    std::swap(max_load,x.max_load);
    std::swap(first_bucket,x.first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
    safe_super::swap(x);
#endif

    super::swap_(x);
  }

  bool replace_(value_param_type v,node_type* x)
  {
    if(eq(key(v),key(x->value()))){
      return super::replace_(v,x);
    }

    node_impl_pointer y=prev(x);
    unlink_next(y);

    BOOST_TRY{
      std::size_t       buc=find_bucket(v);
      node_impl_pointer pos=buckets.at(buc);
      if(link_point(v,pos,Category())&&super::replace_(v,x)){
        link(x,pos);
        if(first_bucket>buc){
          first_bucket=buc;
        }
        else if(first_bucket<buc){
          first_bucket=buckets.first_nonempty(first_bucket);
        }
        return true;
      }
      link(x,y);
      return false;
    }
    BOOST_CATCH(...){
      link(x,y);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
  }

  bool modify_(node_type* x)
  {
    std::size_t buc;
    bool        b; 
    BOOST_TRY{
      buc=find_bucket(x->value());
      b=in_place(x->impl(),key(x->value()),buc,Category());
    }
    BOOST_CATCH(...){
      erase_(x);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
    if(!b){
      unlink(x);
      BOOST_TRY{
        node_impl_pointer pos=buckets.at(buc);
        if(!link_point(x->value(),pos,Category())){
          first_bucket=buckets.first_nonempty(first_bucket);
          super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
          detach_iterators(x);
#endif
          return false;
        }
        link(x,pos);
        if(first_bucket>buc){
          first_bucket=buc;
        }
        else if(first_bucket<buc){
          first_bucket=buckets.first_nonempty(first_bucket);
        }
      }
      BOOST_CATCH(...){
        first_bucket=buckets.first_nonempty(first_bucket);
        super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
      detach_iterators(x);
#endif

        BOOST_RETHROW;
      }
      BOOST_CATCH_END
    }

    BOOST_TRY{
      if(!super::modify_(x)){
        unlink(x);
        first_bucket=buckets.first_nonempty(first_bucket);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
        detach_iterators(x);
#endif
        return false;
      }
      else return true;
    }
    BOOST_CATCH(...){
      unlink(x);
      first_bucket=buckets.first_nonempty(first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
      detach_iterators(x);
#endif

      BOOST_RETHROW;
    }
    BOOST_CATCH_END
  }

  bool modify_rollback_(node_type* x)
  {
    std::size_t buc=find_bucket(x->value());
    if(in_place(x->impl(),key(x->value()),buc,Category())){
      return super::modify_rollback_(x);
    }

    node_impl_pointer y=prev(x);
    unlink_next(y);

    BOOST_TRY{
      node_impl_pointer pos=buckets.at(buc);
      if(link_point(x->value(),pos,Category())&&super::modify_rollback_(x)){
        link(x,pos);
        if(first_bucket>buc){
          first_bucket=buc;
        }
        else if(first_bucket<buc){
          first_bucket=buckets.first_nonempty(first_bucket);
        }
        return true;
      }
      link(x,y);
      return false;
    }
    BOOST_CATCH(...){
      link(x,y);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  /* serialization */

  template<typename Archive>
  void save_(
    Archive& ar,const unsigned int version,const index_saver_type& sm)const
  {
    ar<<serialization::make_nvp("position",buckets);
    super::save_(ar,version,sm);
  }

  template<typename Archive>
  void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
  {
    ar>>serialization::make_nvp("position",buckets);
    super::load_(ar,version,lm);
  }
#endif

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  /* invariant stuff */

  bool invariant_()const
  {
    if(size()==0||begin()==end()){
      if(size()!=0||begin()!=end())return false;
    }
    else{
      size_type s0=0;
      for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
      if(s0!=size())return false;

      size_type s1=0;
      for(size_type buc=0;buc<bucket_count();++buc){
        size_type ss1=0;
        for(const_local_iterator it=begin(buc),it_end=end(buc);
            it!=it_end;++it,++ss1){
          if(find_bucket(*it)!=buc)return false;
        }
        if(ss1!=bucket_size(buc))return false;
        s1+=ss1;
      }
      if(s1!=size())return false;
    }

    if(first_bucket!=buckets.first_nonempty(0))return false;

    return super::invariant_();
  }

  /* This forwarding function eases things for the boost::mem_fn construct
   * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
   * final_check_invariant is already an inherited member function of index.
   */
  void check_invariant_()const{this->final_check_invariant_();}
#endif

private:
  node_type* header()const{return this->final_header();}

  std::size_t find_bucket(value_param_type v)const
  {
    return bucket(key(v));
  }

  bool link_point(
    value_param_type v,node_impl_pointer& pos,hashed_unique_tag)
  {
    node_impl_pointer x=pos->next();
    while(x!=pos){
      if(eq(key(v),key(node_type::from_impl(x)->value()))){
        pos=x;
        return false;
      }
      x=x->next();
    }
    return true;
  }

  bool link_point(
    value_param_type v,node_impl_pointer& pos,hashed_non_unique_tag)
  {
    node_impl_pointer prev=pos;
    node_impl_pointer x=pos->next();
    while(x!=pos){
      if(eq(key(v),key(node_type::from_impl(x)->value()))){
        pos=prev;
        return true;
      }
      prev=x;
      x=x->next();
    }
    return true;
  }
  
  static void link(node_type* x,node_impl_pointer pos)
  {
    node_impl_type::link(x->impl(),pos);
  };

  static void link(node_impl_pointer x,node_impl_pointer pos)
  {
    node_impl_type::link(x,pos);
  };

  static void unlink(node_type* x)
  {
    node_impl_type::unlink(x->impl());
  };

  static node_impl_pointer prev(node_type* x)
  {
    return node_impl_type::prev(x->impl());
  }

  static node_impl_pointer prev_from(node_type* x,node_impl_pointer y)
  {
    return node_impl_type::prev_from(x->impl(),y);
  }

  static void unlink_next(node_impl_pointer x)
  {
    node_impl_type::unlink_next(x);
  }

  void calculate_max_load()
  {
    float fml=static_cast<float>(mlf*bucket_count());
    max_load=(std::numeric_limits<size_type>::max)();
    if(max_load>fml)max_load=static_cast<size_type>(fml);
  }

  void reserve(size_type n)
  {
    if(n>max_load){
      size_type bc =(std::numeric_limits<size_type>::max)();
      float     fbc=static_cast<float>(1+n/mlf);
      if(bc>fbc)bc =static_cast<size_type>(fbc);
      unchecked_rehash(bc);
    }
  }

  void unchecked_rehash(size_type n)
  {
    bucket_array_type buckets1(get_allocator(),header()->impl(),n);
    auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());

    std::size_t i=0;
    node_impl_pointer x=buckets.begin();
    node_impl_pointer x_end=buckets.end();
    for(;x!=x_end;++x){
      node_impl_pointer y=x->next();
      while(y!=x){
        hashes.data()[i++]=hash(key(node_type::from_impl(y)->value()));
        y=y->next();
      }
    }

    i=0;
    x=buckets.begin();
    for(;x!=x_end;++x){
      node_impl_pointer y=x->next();
      while(y!=x){
        node_impl_pointer z=y->next();
        std::size_t       buc1=buckets1.position(hashes.data()[i++]);
        node_impl_pointer x1=buckets1.at(buc1);
        link(y,x1);
        y=z;
      }
    }

    buckets.swap(buckets1);
    calculate_max_load();
    first_bucket=buckets.first_nonempty(0);
  }

  bool in_place(
    node_impl_pointer x,key_param_type k,std::size_t buc,
    hashed_unique_tag)const
  {
    std::less_equal<node_impl_pointer> leq;
    node_impl_pointer                  bbegin=buckets.begin();
    node_impl_pointer                  bend=buckets.end();
    node_impl_pointer                  pbuc=x->next();

    while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next();
    if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false;

    node_impl_pointer y=x;
    while(y->next()!=x){
      y=y->next();
      if(y==pbuc)continue;
      if(eq(k,key(node_type::from_impl(y)->value())))return false;
    }
    return true;
  }

  bool in_place(
    node_impl_pointer x,key_param_type k,std::size_t buc,
    hashed_non_unique_tag)const
  {
    std::less_equal<node_impl_pointer> leq;
    node_impl_pointer                  bbegin=buckets.begin();
    node_impl_pointer                  bend=buckets.end();
    node_impl_pointer                  pbuc=x->next();

    while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next();
    if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false;

    node_impl_pointer y=x->next();
    if(y!=pbuc){
      if(eq(k,key(node_type::from_impl(y)->value()))){
        /* adjacent to equivalent element -> in place */
        return true;
      }
      else{
        y=y->next();
        while(y!=pbuc){
          if(eq(k,key(node_type::from_impl(y)->value())))return false;
          y=y->next();
        }
      }
    }
    while(y->next()!=x){
      y=y->next();
      if(eq(k,key(node_type::from_impl(y)->value()))){
        while(y->next()!=x){
          y=y->next();
          if(!eq(k,key(node_type::from_impl(y)->value())))return false;
        }
        /* after a group of equivalent elements --> in place */
        return true;
      }
    }
    return true;
  }


#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  void detach_iterators(node_type* x)
  {
    iterator it=make_iterator(x);
    safe_mode::detach_equivalent_iterators(it);
  }
#endif

  key_from_value               key;
  hasher                       hash;
  key_equal                    eq;
  bucket_array_type            buckets;
  float                        mlf;
  size_type                    max_load;
  std::size_t                  first_bucket;
      
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
    BOOST_WORKAROUND(__MWERKS__,<=0x3003)
#pragma parse_mfunc_templ reset
#endif
};

/*  specialized algorithms */

template<
  typename KeyFromValue,typename Hash,typename Pred,
  typename SuperMeta,typename TagList,typename Category
>
void swap(
  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
{
  x.swap(y);
}

} /* namespace multi_index::detail */

/* hashed index specifiers */

template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
struct hashed_unique
{
  typedef typename detail::hashed_index_args<
    Arg1,Arg2,Arg3,Arg4>                           index_args;
  typedef typename index_args::tag_list_type::type tag_list_type;
  typedef typename index_args::key_from_value_type key_from_value_type;
  typedef typename index_args::hash_type           hash_type;
  typedef typename index_args::pred_type           pred_type;

  template<typename Super>
  struct node_class
  {
    typedef detail::hashed_index_node<Super> type;
  };

  template<typename SuperMeta>
  struct index_class
  {
    typedef detail::hashed_index<
      key_from_value_type,hash_type,pred_type,
      SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
  };
};

template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
struct hashed_non_unique
{
  typedef typename detail::hashed_index_args<
    Arg1,Arg2,Arg3,Arg4>                           index_args;
  typedef typename index_args::tag_list_type::type tag_list_type;
  typedef typename index_args::key_from_value_type key_from_value_type;
  typedef typename index_args::hash_type           hash_type;
  typedef typename index_args::pred_type           pred_type;

  template<typename Super>
  struct node_class
  {
    typedef detail::hashed_index_node<Super> type;
  };

  template<typename SuperMeta>
  struct index_class
  {
    typedef detail::hashed_index<
      key_from_value_type,hash_type,pred_type,
      SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
  };
};

} /* namespace multi_index */

} /* namespace boost */

#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT

#endif