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