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

 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_LOADER_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/multi_index/detail/auto_space.hpp>

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

 #include <boost/noncopyable.hpp>

 #include <cstddef>

 namespace boost{

 namespace multi_index{

 namespace detail{

 /* This class implements a serialization rearranger for random access

  * indices. In order to achieve O(n) performance, the following strategy

  * is followed: the nodes of the index are handled as if in a bidirectional

  * list, where the next pointers are stored in the original

  * random_access_index_ptr_array and the prev pointers are stored in

  * an auxiliary array. Rearranging of nodes in such a bidirectional list

  * is constant time. Once all the arrangements are performed (on destruction

  * time) the list is traversed in reverse order and

  * pointers are swapped and set accordingly so that they recover its

  * original semantics ( *(node->up())==node ) while retaining the

  * new order.

  */

 template<typename Allocator>

 class random_access_index_loader_base:private noncopyable

 {

 protected:

   typedef random_access_index_node_impl            node_type;

   typedef random_access_index_ptr_array<Allocator> ptr_array_type;

   random_access_index_loader_base(const Allocator& al_,ptr_array_type& ptrs_):

     al(al_),

     ptrs(ptrs_),

     header(*ptrs.end()),

     prev_spc(al,0),

     preprocessed(false)

   {}

   ~random_access_index_loader_base()

   {

     if(preprocessed)

     {

       node_type* n=header;

       next(n)=n;

       for(std::size_t i=ptrs.size();i--;){

         n=prev(n);

         std::size_t d=position(n);

         if(d!=i){

           node_type* m=prev(next_at(i));

           std::swap(m->up(),n->up());

           next_at(d)=next_at(i);

           std::swap(prev_at(d),prev_at(i));

         }

         next(n)=n;

       }

     }

   }

   void rearrange(node_type* position,node_type *x)

   {

     preprocess(); /* only incur this penalty if rearrange() is ever called */

     if(!position)position=header;

     next(prev(x))=next(x);

     prev(next(x))=prev(x);

     prev(x)=position;

     next(x)=next(position);

     next(prev(x))=prev(next(x))=x;

   }

 private:

   void preprocess()

   {

     if(!preprocessed){

       /* get space for the auxiliary prev array */

       auto_space<node_type*,Allocator> tmp(al,ptrs.size()+1);

       prev_spc.swap(tmp);

       /* prev_spc elements point to the prev nodes */

       std::rotate_copy(ptrs.begin(),ptrs.end(),ptrs.end()+1,prev_spc.data());

       /* ptrs elements point to the next nodes */

       std::rotate(ptrs.begin(),ptrs.begin()+1,ptrs.end()+1);

       preprocessed=true;

     }

   }

   std::size_t position(node_type* x)const

   {

     return (std::size_t)(x->up()-ptrs.begin());

   }

   node_type*& next_at(std::size_t n)const

   {

     return *ptrs.at(n);

   }

   node_type*& prev_at(std::size_t n)const

   {

     return prev_spc.data()[n];

   }

   node_type*& next(node_type* x)const

   {

     return *(x->up());

   }

   node_type*& prev(node_type* x)const

   {

     return prev_at(position(x));

   }

   Allocator                        al;

   ptr_array_type&                  ptrs;

   node_type*                       header;

   auto_space<node_type*,Allocator> prev_spc;

   bool                             preprocessed;

 };

 template<typename Node,typename Allocator>

 class random_access_index_loader:

   private random_access_index_loader_base<Allocator>

 {

   typedef random_access_index_loader_base<Allocator> super;

   typedef typename super::ptr_array_type             ptr_array_type;

 public:

   random_access_index_loader(const Allocator& al_,ptr_array_type& ptrs_):

     super(al_,ptrs_)

   {}

   void rearrange(Node* position,Node *x)

   {

     super::rearrange(position?position->impl():0,x->impl());

   }

 };

 } /* namespace multi_index::detail */

 } /* namespace multi_index */

 } /* namespace boost */

 #endif