Chris@101: /* Copyright 2003-2015 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <algorithm>
Chris@16: #include <boost/detail/allocator_utilities.hpp>
Chris@101: #include <boost/integer/common_factor_rt.hpp>
Chris@16: #include <cstddef>
Chris@16: #include <functional>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: template<typename Allocator>
Chris@16: struct random_access_index_node_impl
Chris@16: {
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,random_access_index_node_impl
Chris@101:   >::type::pointer                          pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,random_access_index_node_impl
Chris@101:   >::type::const_pointer                    const_pointer;
Chris@101:   typedef typename
Chris@101:   boost::detail::allocator::rebind_to<
Chris@101:     Allocator,pointer
Chris@101:   >::type::pointer                          ptr_pointer;
Chris@16: 
Chris@16:   ptr_pointer& up(){return up_;}
Chris@16:   ptr_pointer  up()const{return up_;}
Chris@16: 
Chris@16:   /* interoperability with rnd_node_iterator */
Chris@16: 
Chris@16:   static void increment(pointer& x)
Chris@16:   {
Chris@16:     x=*(x->up()+1);
Chris@16:   }
Chris@16: 
Chris@16:   static void decrement(pointer& x)
Chris@16:   {
Chris@16:     x=*(x->up()-1);
Chris@16:   }
Chris@16: 
Chris@16:   static void advance(pointer& x,std::ptrdiff_t n)
Chris@16:   {
Chris@16:     x=*(x->up()+n);
Chris@16:   }
Chris@16: 
Chris@16:   static std::ptrdiff_t distance(pointer x,pointer y)
Chris@16:   {
Chris@16:     return y->up()-x->up();
Chris@16:   }
Chris@16: 
Chris@16:   /* algorithmic stuff */
Chris@16: 
Chris@16:   static void relocate(ptr_pointer pos,ptr_pointer x)
Chris@16:   {
Chris@16:     pointer n=*x;
Chris@16:     if(x<pos){
Chris@16:       extract(x,pos);
Chris@16:       *(pos-1)=n;
Chris@16:       n->up()=pos-1;
Chris@16:     }
Chris@16:     else{
Chris@16:       while(x!=pos){
Chris@16:         *x=*(x-1);
Chris@16:         (*x)->up()=x;
Chris@16:         --x;
Chris@16:       }
Chris@16:       *pos=n;
Chris@16:       n->up()=pos;
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
Chris@16:   {
Chris@16:     ptr_pointer begin,middle,end;
Chris@16:     if(pos<first){
Chris@16:       begin=pos;
Chris@16:       middle=first;
Chris@16:       end=last;
Chris@16:     }
Chris@16:     else{
Chris@16:       begin=first;
Chris@16:       middle=last;
Chris@16:       end=pos;
Chris@16:     }
Chris@16: 
Chris@16:     std::ptrdiff_t n=end-begin;
Chris@16:     std::ptrdiff_t m=middle-begin;
Chris@16:     std::ptrdiff_t n_m=n-m;
Chris@101:     std::ptrdiff_t p=integer::gcd(n,m);
Chris@16: 
Chris@16:     for(std::ptrdiff_t i=0;i<p;++i){
Chris@16:       pointer tmp=begin[i];
Chris@16:       for(std::ptrdiff_t j=i,k;;){
Chris@16:         if(j<n_m)k=j+m;
Chris@16:         else     k=j-n_m;
Chris@16:         if(k==i){
Chris@16:           *(begin+j)=tmp;
Chris@16:           (*(begin+j))->up()=begin+j;
Chris@16:           break;
Chris@16:         }
Chris@16:         else{
Chris@16:           *(begin+j)=*(begin+k);
Chris@16:           (*(begin+j))->up()=begin+j;
Chris@16:         }
Chris@16: 
Chris@16:         if(k<n_m)j=k+m;
Chris@16:         else     j=k-n_m;
Chris@16:         if(j==i){
Chris@16:           *(begin+k)=tmp;
Chris@16:           (*(begin+k))->up()=begin+k;
Chris@16:           break;
Chris@16:         }
Chris@16:         else{
Chris@16:           *(begin+k)=*(begin+j);
Chris@16:           (*(begin+k))->up()=begin+k;
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16:   static void extract(ptr_pointer x,ptr_pointer pend)
Chris@16:   {
Chris@16:     --pend;
Chris@16:     while(x!=pend){
Chris@16:       *x=*(x+1);
Chris@16:       (*x)->up()=x;
Chris@16:       ++x;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   static void transfer(
Chris@16:     ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
Chris@16:   {
Chris@16:     while(pbegin0!=pend0){
Chris@16:       *pbegin1=*pbegin0++;
Chris@16:       (*pbegin1)->up()=pbegin1;
Chris@16:       ++pbegin1;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   static void reverse(ptr_pointer pbegin,ptr_pointer pend)
Chris@16:   {
Chris@16:     std::ptrdiff_t d=(pend-pbegin)/2;
Chris@16:     for(std::ptrdiff_t i=0;i<d;++i){
Chris@16:       std::swap(*pbegin,*--pend);
Chris@16:       (*pbegin)->up()=pbegin;
Chris@16:       (*pend)->up()=pend;
Chris@16:       ++pbegin;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   ptr_pointer up_;
Chris@16: };
Chris@16: 
Chris@16: template<typename Super>
Chris@16: struct random_access_index_node_trampoline:
Chris@101:   random_access_index_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       typename Super::allocator_type,
Chris@101:       char
Chris@101:     >::type
Chris@101:   >
Chris@16: {
Chris@101:   typedef random_access_index_node_impl<
Chris@101:     typename boost::detail::allocator::rebind_to<
Chris@101:       typename Super::allocator_type,
Chris@101:       char
Chris@101:     >::type
Chris@101:   > impl_type;
Chris@16: };
Chris@16: 
Chris@16: template<typename Super>
Chris@16: struct random_access_index_node:
Chris@16:   Super,random_access_index_node_trampoline<Super>
Chris@16: {
Chris@16: private:
Chris@16:   typedef random_access_index_node_trampoline<Super> trampoline;
Chris@16: 
Chris@16: public:
Chris@16:   typedef typename trampoline::impl_type     impl_type;
Chris@16:   typedef typename trampoline::pointer       impl_pointer;
Chris@16:   typedef typename trampoline::const_pointer const_impl_pointer;
Chris@16:   typedef typename trampoline::ptr_pointer   impl_ptr_pointer;
Chris@16: 
Chris@16:   impl_ptr_pointer& up(){return trampoline::up();}
Chris@16:   impl_ptr_pointer  up()const{return trampoline::up();}
Chris@16: 
Chris@16:   impl_pointer impl()
Chris@16:   {
Chris@16:     return static_cast<impl_pointer>(
Chris@16:       static_cast<impl_type*>(static_cast<trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   const_impl_pointer impl()const
Chris@16:   {
Chris@16:     return static_cast<const_impl_pointer>(
Chris@16:       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
Chris@16:   }
Chris@16: 
Chris@16:   static random_access_index_node* from_impl(impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<random_access_index_node*>(
Chris@16:       static_cast<trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@16:   static const random_access_index_node* from_impl(const_impl_pointer x)
Chris@16:   {
Chris@16:     return static_cast<const random_access_index_node*>(
Chris@16:       static_cast<const trampoline*>(&*x));
Chris@16:   }
Chris@16: 
Chris@16:   /* interoperability with rnd_node_iterator */
Chris@16: 
Chris@16:   static void increment(random_access_index_node*& x)
Chris@16:   {
Chris@16:     impl_pointer xi=x->impl();
Chris@16:     trampoline::increment(xi);
Chris@16:     x=from_impl(xi);
Chris@16:   }
Chris@16: 
Chris@16:   static void decrement(random_access_index_node*& x)
Chris@16:   {
Chris@16:     impl_pointer xi=x->impl();
Chris@16:     trampoline::decrement(xi);
Chris@16:     x=from_impl(xi);
Chris@16:   }
Chris@16: 
Chris@16:   static void advance(random_access_index_node*& x,std::ptrdiff_t n)
Chris@16:   {
Chris@16:     impl_pointer xi=x->impl();
Chris@16:     trampoline::advance(xi,n);
Chris@16:     x=from_impl(xi);
Chris@16:   }
Chris@16: 
Chris@16:   static std::ptrdiff_t distance(
Chris@16:     random_access_index_node* x,random_access_index_node* y)
Chris@16:   {
Chris@16:     return trampoline::distance(x->impl(),y->impl());
Chris@16:   }
Chris@16: };
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif