1 /* Copyright 2003-2007 Joaquín M López Muñoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
18 #include <boost/detail/allocator_utilities.hpp>
19 #include <boost/math/common_factor_rt.hpp>
20 #include <boost/multi_index/detail/prevent_eti.hpp>
26 namespace multi_index{
30 template<typename Allocator>
31 struct random_access_index_node_impl
33 typedef typename prevent_eti<
35 typename boost::detail::allocator::rebind_to<
36 Allocator,random_access_index_node_impl
38 >::type::pointer pointer;
39 typedef typename prevent_eti<
41 typename boost::detail::allocator::rebind_to<
42 Allocator,random_access_index_node_impl
44 >::type::const_pointer const_pointer;
45 typedef typename prevent_eti<
47 typename boost::detail::allocator::rebind_to<
50 >::type::pointer ptr_pointer;
52 ptr_pointer& up(){return up_;}
53 ptr_pointer up()const{return up_;}
55 /* interoperability with rnd_node_iterator */
57 static void increment(pointer& x)
62 static void decrement(pointer& x)
67 static void advance(pointer& x,std::ptrdiff_t n)
72 static std::ptrdiff_t distance(pointer x,pointer y)
74 return y->up()-x->up();
77 /* algorithmic stuff */
79 static void relocate(ptr_pointer pos,ptr_pointer x)
98 static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
100 ptr_pointer begin,middle,end;
112 std::ptrdiff_t n=end-begin;
113 std::ptrdiff_t m=middle-begin;
114 std::ptrdiff_t n_m=n-m;
115 std::ptrdiff_t p=math::gcd(n,m);
117 for(std::ptrdiff_t i=0;i<p;++i){
118 pointer tmp=begin[i];
119 for(std::ptrdiff_t j=i,k;;){
124 (*(begin+j))->up()=begin+j;
128 *(begin+j)=*(begin+k);
129 (*(begin+j))->up()=begin+j;
136 (*(begin+k))->up()=begin+k;
140 *(begin+k)=*(begin+j);
141 (*(begin+k))->up()=begin+k;
147 static void extract(ptr_pointer x,ptr_pointer pend)
157 static void transfer(
158 ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
160 while(pbegin0!=pend0){
162 (*pbegin1)->up()=pbegin1;
167 static void reverse(ptr_pointer pbegin,ptr_pointer pend)
169 std::ptrdiff_t d=(pend-pbegin)/2;
170 for(std::ptrdiff_t i=0;i<d;++i){
171 std::swap(*pbegin,*--pend);
172 (*pbegin)->up()=pbegin;
182 template<typename Super>
183 struct random_access_index_node_trampoline:
186 random_access_index_node_impl<
187 typename boost::detail::allocator::rebind_to<
188 typename Super::allocator_type,
194 typedef typename prevent_eti<
196 random_access_index_node_impl<
197 typename boost::detail::allocator::rebind_to<
198 typename Super::allocator_type,
205 template<typename Super>
206 struct random_access_index_node:
207 Super,random_access_index_node_trampoline<Super>
210 typedef random_access_index_node_trampoline<Super> trampoline;
213 typedef typename trampoline::impl_type impl_type;
214 typedef typename trampoline::pointer impl_pointer;
215 typedef typename trampoline::const_pointer const_impl_pointer;
216 typedef typename trampoline::ptr_pointer impl_ptr_pointer;
218 impl_ptr_pointer& up(){return trampoline::up();}
219 impl_ptr_pointer up()const{return trampoline::up();}
223 return static_cast<impl_pointer>(
224 static_cast<impl_type*>(static_cast<trampoline*>(this)));
227 const_impl_pointer impl()const
229 return static_cast<const_impl_pointer>(
230 static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
233 static random_access_index_node* from_impl(impl_pointer x)
235 return static_cast<random_access_index_node*>(
236 static_cast<trampoline*>(&*x));
239 static const random_access_index_node* from_impl(const_impl_pointer x)
241 return static_cast<const random_access_index_node*>(
242 static_cast<const trampoline*>(&*x));
245 /* interoperability with rnd_node_iterator */
247 static void increment(random_access_index_node*& x)
249 impl_pointer xi=x->impl();
250 trampoline::increment(xi);
254 static void decrement(random_access_index_node*& x)
256 impl_pointer xi=x->impl();
257 trampoline::decrement(xi);
261 static void advance(random_access_index_node*& x,std::ptrdiff_t n)
263 impl_pointer xi=x->impl();
264 trampoline::advance(xi,n);
268 static std::ptrdiff_t distance(
269 random_access_index_node* x,random_access_index_node* y)
271 return trampoline::distance(x->impl(),y->impl());
275 } /* namespace multi_index::detail */
277 } /* namespace multi_index */
279 } /* namespace boost */