/* Copyright 2003-2008 Joaquin M Lopez Munoz. | |
* 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, | |
char | |
>::type | |
> | |
>::type | |
{ | |
typedef typename prevent_eti< | |
Super, | |
random_access_index_node_impl< | |
typename boost::detail::allocator::rebind_to< | |
typename Super::allocator_type, | |
char | |
>::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 |