/* Copyright 2003-2006 Joaquín M López Muñoz.

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

#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_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 <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* singly-linked node for use by hashed_index */

struct hashed_index_node_impl

{

  hashed_index_node_impl*& next(){return next_;}

  hashed_index_node_impl*  next()const{return next_;}

  /* algorithmic stuff */

  static void increment(

    hashed_index_node_impl*& x,

    hashed_index_node_impl* bbegin,hashed_index_node_impl* bbend)

  {

    std::less_equal<hashed_index_node_impl*> leq;

    x=x->next();

    if(leq(bbegin,x)&&leq(x,bbend)){ /* bucket node */

      do{

        ++x;

      }while(x->next()==x);

      x=x->next();

    }

  }

  static void link(

    hashed_index_node_impl* x,hashed_index_node_impl* pos)

  {

    x->next()=pos->next();

    pos->next()=x;

  };

  static void unlink(hashed_index_node_impl* x)

  {

    hashed_index_node_impl* y=x->next();

    while(y->next()!=x){y=y->next();}

    y->next()=x->next();

  }

  static hashed_index_node_impl* prev(hashed_index_node_impl* x)

  {

    hashed_index_node_impl* y=x->next();

    while(y->next()!=x){y=y->next();}

    return y;

  }

  static void unlink_next(hashed_index_node_impl* x)

  {

    x->next()=x->next()->next();

  }

private:

  hashed_index_node_impl* next_;

};

template<typename Super>

struct hashed_index_node_trampoline:hashed_index_node_impl{};

template<typename Super>

struct hashed_index_node:Super,hashed_index_node_trampoline<Super>

{

  hashed_index_node_impl*       impl()

    {return static_cast<impl_type*>(this);}

  const hashed_index_node_impl* impl()const

    {return static_cast<const impl_type*>(this);}

  static hashed_index_node* from_impl(hashed_index_node_impl *x)

    {return static_cast<hashed_index_node*>(static_cast<impl_type*>(x));}

  static const hashed_index_node* from_impl(const hashed_index_node_impl* x)

  {

    return static_cast<const hashed_index_node*>(

      static_cast<const impl_type*>(x));

  }

  static void increment(

    hashed_index_node*& x,

    hashed_index_node_impl* bbegin,hashed_index_node_impl* bend)

  {

    hashed_index_node_impl* xi=x->impl();

    impl_type::increment(xi,bbegin,bend);

    x=from_impl(xi);

  }

private:

  typedef hashed_index_node_trampoline<Super> impl_type;

};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif