/* Copyright 2003-2007 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_RND_INDEX_NODE_HPP

#define BOOST_MULTI_INDEX_DETAIL_RND_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 <algorithm>

#include <boost/detail/allocator_utilities.hpp>

#include <boost/math/common_factor_rt.hpp>

#include <boost/multi_index/detail/prevent_eti.hpp>

#include <cstddef>

#include <functional>



namespace boost{



namespace multi_index{



namespace detail{



template<typename Allocator>

struct random_access_index_node_impl

{

  typedef typename prevent_eti<

    Allocator,

    typename boost::detail::allocator::rebind_to<

      Allocator,random_access_index_node_impl

    >::type

  >::type::pointer                                pointer;

  typedef typename prevent_eti<

    Allocator,

    typename boost::detail::allocator::rebind_to<

      Allocator,random_access_index_node_impl

    >::type

  >::type::const_pointer                          const_pointer;

  typedef typename prevent_eti<

    Allocator,

    typename boost::detail::allocator::rebind_to<

      Allocator,pointer

    >::type

  >::type::pointer                                ptr_pointer;



  ptr_pointer& up(){return up_;}

  ptr_pointer  up()const{return up_;}



  /* interoperability with rnd_node_iterator */



  static void increment(pointer& x)

  {

    x=*(x->up()+1);

  }



  static void decrement(pointer& x)

  {

    x=*(x->up()-1);

  }



  static void advance(pointer& x,std::ptrdiff_t n)

  {

    x=*(x->up()+n);

  }



  static std::ptrdiff_t distance(pointer x,pointer y)

  {

    return y->up()-x->up();

  }



  /* algorithmic stuff */



  static void relocate(ptr_pointer pos,ptr_pointer x)

  {

    pointer n=*x;

    if(x<pos){

      extract(x,pos);

      *(pos-1)=n;

      n->up()=pos-1;

    }

    else{

      while(x!=pos){

        *x=*(x-1);

        (*x)->up()=x;

        --x;

      }

      *pos=n;

      n->up()=pos;

    }

  };



  static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)

  {

    ptr_pointer begin,middle,end;

    if(pos<first){

      begin=pos;

      middle=first;

      end=last;

    }

    else{

      begin=first;

      middle=last;

      end=pos;

    }



    std::ptrdiff_t n=end-begin;

    std::ptrdiff_t m=middle-begin;

    std::ptrdiff_t n_m=n-m;

    std::ptrdiff_t p=math::gcd(n,m);



    for(std::ptrdiff_t i=0;i<p;++i){

      pointer tmp=begin[i];

      for(std::ptrdiff_t j=i,k;;){

        if(j<n_m)k=j+m;

        else     k=j-n_m;

        if(k==i){

          *(begin+j)=tmp;

          (*(begin+j))->up()=begin+j;

          break;

        }

        else{

          *(begin+j)=*(begin+k);

          (*(begin+j))->up()=begin+j;

        }



        if(k<n_m)j=k+m;

        else     j=k-n_m;

        if(j==i){

          *(begin+k)=tmp;

          (*(begin+k))->up()=begin+k;

          break;

        }

        else{

          *(begin+k)=*(begin+j);

          (*(begin+k))->up()=begin+k;

        }

      }

    }

  };



  static void extract(ptr_pointer x,ptr_pointer pend)

  {

    --pend;

    while(x!=pend){

      *x=*(x+1);

      (*x)->up()=x;

      ++x;

    }

  }



  static void transfer(

    ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)

  {

    while(pbegin0!=pend0){

      *pbegin1=*pbegin0++;

      (*pbegin1)->up()=pbegin1;

      ++pbegin1;

    }

  }



  static void reverse(ptr_pointer pbegin,ptr_pointer pend)

  {

    std::ptrdiff_t d=(pend-pbegin)/2;

    for(std::ptrdiff_t i=0;i<d;++i){

      std::swap(*pbegin,*--pend);

      (*pbegin)->up()=pbegin;

      (*pend)->up()=pend;

      ++pbegin;

    }

  }



private:

  ptr_pointer up_;

};



template<typename Super>

struct random_access_index_node_trampoline:

  prevent_eti<

    Super,

    random_access_index_node_impl<

      typename boost::detail::allocator::rebind_to<

        typename Super::allocator_type,

        void

      >::type

    >

  >::type

{

  typedef typename prevent_eti<

    Super,

    random_access_index_node_impl<

      typename boost::detail::allocator::rebind_to<

        typename Super::allocator_type,

        void

      >::type

    >

  >::type impl_type;

};



template<typename Super>

struct random_access_index_node:

  Super,random_access_index_node_trampoline<Super>

{

private:

  typedef random_access_index_node_trampoline<Super> trampoline;



public:

  typedef typename trampoline::impl_type     impl_type;

  typedef typename trampoline::pointer       impl_pointer;

  typedef typename trampoline::const_pointer const_impl_pointer;

  typedef typename trampoline::ptr_pointer   impl_ptr_pointer;



  impl_ptr_pointer& up(){return trampoline::up();}

  impl_ptr_pointer  up()const{return trampoline::up();}



  impl_pointer impl()

  {

    return static_cast<impl_pointer>(

      static_cast<impl_type*>(static_cast<trampoline*>(this)));

  }



  const_impl_pointer impl()const

  {

    return static_cast<const_impl_pointer>(

      static_cast<const impl_type*>(static_cast<const trampoline*>(this)));

  }



  static random_access_index_node* from_impl(impl_pointer x)

  {

    return static_cast<random_access_index_node*>(

      static_cast<trampoline*>(&*x));

  }



  static const random_access_index_node* from_impl(const_impl_pointer x)

  {

    return static_cast<const random_access_index_node*>(

      static_cast<const trampoline*>(&*x));

  }



  /* interoperability with rnd_node_iterator */



  static void increment(random_access_index_node*& x)

  {

    impl_pointer xi=x->impl();

    trampoline::increment(xi);

    x=from_impl(xi);

  }



  static void decrement(random_access_index_node*& x)

  {

    impl_pointer xi=x->impl();

    trampoline::decrement(xi);

    x=from_impl(xi);

  }



  static void advance(random_access_index_node*& x,std::ptrdiff_t n)

  {

    impl_pointer xi=x->impl();

    trampoline::advance(xi,n);

    x=from_impl(xi);

  }



  static std::ptrdiff_t distance(

    random_access_index_node* x,random_access_index_node* y)

  {

    return trampoline::distance(x->impl(),y->impl());

  }

};



} /* namespace multi_index::detail */



} /* namespace multi_index */



} /* namespace boost */



#endif

