boost_ext/boost/multi_index/detail/rnd_index_node.hpp

   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)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
  11
  12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/detail/allocator_utilities.hpp>
  19 #include <boost/math/common_factor_rt.hpp>
  20 #include <boost/multi_index/detail/prevent_eti.hpp>
  21 #include <cstddef>
  22 #include <functional>
  23
  24 namespace boost{
  25
  26 namespace multi_index{
  27
  28 namespace detail{
  29
  30 template<typename Allocator>
  31 struct random_access_index_node_impl
  32 {
  33   typedef typename prevent_eti<
  34     Allocator,
  35     typename boost::detail::allocator::rebind_to<
  36       Allocator,random_access_index_node_impl
  37     >::type
  38   >::type::pointer                                pointer;
  39   typedef typename prevent_eti<
  40     Allocator,
  41     typename boost::detail::allocator::rebind_to<
  42       Allocator,random_access_index_node_impl
  43     >::type
  44   >::type::const_pointer                          const_pointer;
  45   typedef typename prevent_eti<
  46     Allocator,
  47     typename boost::detail::allocator::rebind_to<
  48       Allocator,pointer
  49     >::type
  50   >::type::pointer                                ptr_pointer;
  51
  52   ptr_pointer& up(){return up_;}
  53   ptr_pointer  up()const{return up_;}
  54
  55   /* interoperability with rnd_node_iterator */
  56
  57   static void increment(pointer& x)
  58   {
  59     x=*(x->up()+1);
  60   }
  61
  62   static void decrement(pointer& x)
  63   {
  64     x=*(x->up()-1);
  65   }
  66
  67   static void advance(pointer& x,std::ptrdiff_t n)
  68   {
  69     x=*(x->up()+n);
  70   }
  71
  72   static std::ptrdiff_t distance(pointer x,pointer y)
  73   {
  74     return y->up()-x->up();
  75   }
  76
  77   /* algorithmic stuff */
  78
  79   static void relocate(ptr_pointer pos,ptr_pointer x)
  80   {
  81     pointer n=*x;
  82     if(x<pos){
  83       extract(x,pos);
  84       *(pos-1)=n;
  85       n->up()=pos-1;
  86     }
  87     else{
  88       while(x!=pos){
  89         *x=*(x-1);
  90         (*x)->up()=x;
  91         --x;
  92       }
  93       *pos=n;
  94       n->up()=pos;
  95     }
  96   };
  97
  98   static void relocate(ptr_pointer pos,ptr_pointer first,ptr_pointer last)
  99   {
 100     ptr_pointer begin,middle,end;
 101     if(pos<first){
 102       begin=pos;
 103       middle=first;
 104       end=last;
 105     }
 106     else{
 107       begin=first;
 108       middle=last;
 109       end=pos;
 110     }
 111
 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);
 116
 117     for(std::ptrdiff_t i=0;i<p;++i){
 118       pointer tmp=begin[i];
 119       for(std::ptrdiff_t j=i,k;;){
 120         if(j<n_m)k=j+m;
 121         else     k=j-n_m;
 122         if(k==i){
 123           *(begin+j)=tmp;
 124           (*(begin+j))->up()=begin+j;
 125           break;
 126         }
 127         else{
 128           *(begin+j)=*(begin+k);
 129           (*(begin+j))->up()=begin+j;
 130         }
 131
 132         if(k<n_m)j=k+m;
 133         else     j=k-n_m;
 134         if(j==i){
 135           *(begin+k)=tmp;
 136           (*(begin+k))->up()=begin+k;
 137           break;
 138         }
 139         else{
 140           *(begin+k)=*(begin+j);
 141           (*(begin+k))->up()=begin+k;
 142         }
 143       }
 144     }
 145   };
 146
 147   static void extract(ptr_pointer x,ptr_pointer pend)
 148   {
 149     --pend;
 150     while(x!=pend){
 151       *x=*(x+1);
 152       (*x)->up()=x;
 153       ++x;
 154     }
 155   }
 156
 157   static void transfer(
 158     ptr_pointer pbegin0,ptr_pointer pend0,ptr_pointer pbegin1)
 159   {
 160     while(pbegin0!=pend0){
 161       *pbegin1=*pbegin0++;
 162       (*pbegin1)->up()=pbegin1;
 163       ++pbegin1;
 164     }
 165   }
 166
 167   static void reverse(ptr_pointer pbegin,ptr_pointer pend)
 168   {
 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;
 173       (*pend)->up()=pend;
 174       ++pbegin;
 175     }
 176   }
 177
 178 private:
 179   ptr_pointer up_;
 180 };
 181
 182 template<typename Super>
 183 struct random_access_index_node_trampoline:
 184   prevent_eti<
 185     Super,
 186     random_access_index_node_impl<
 187       typename boost::detail::allocator::rebind_to<
 188         typename Super::allocator_type,
 189         void
 190       >::type
 191     >
 192   >::type
 193 {
 194   typedef typename prevent_eti<
 195     Super,
 196     random_access_index_node_impl<
 197       typename boost::detail::allocator::rebind_to<
 198         typename Super::allocator_type,
 199         void
 200       >::type
 201     >
 202   >::type impl_type;
 203 };
 204
 205 template<typename Super>
 206 struct random_access_index_node:
 207   Super,random_access_index_node_trampoline<Super>
 208 {
 209 private:
 210   typedef random_access_index_node_trampoline<Super> trampoline;
 211
 212 public:
 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;
 217
 218   impl_ptr_pointer& up(){return trampoline::up();}
 219   impl_ptr_pointer  up()const{return trampoline::up();}
 220
 221   impl_pointer impl()
 222   {
 223     return static_cast<impl_pointer>(
 224       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 225   }
 226
 227   const_impl_pointer impl()const
 228   {
 229     return static_cast<const_impl_pointer>(
 230       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 231   }
 232
 233   static random_access_index_node* from_impl(impl_pointer x)
 234   {
 235     return static_cast<random_access_index_node*>(
 236       static_cast<trampoline*>(&*x));
 237   }
 238
 239   static const random_access_index_node* from_impl(const_impl_pointer x)
 240   {
 241     return static_cast<const random_access_index_node*>(
 242       static_cast<const trampoline*>(&*x));
 243   }
 244
 245   /* interoperability with rnd_node_iterator */
 246
 247   static void increment(random_access_index_node*& x)
 248   {
 249     impl_pointer xi=x->impl();
 250     trampoline::increment(xi);
 251     x=from_impl(xi);
 252   }
 253
 254   static void decrement(random_access_index_node*& x)
 255   {
 256     impl_pointer xi=x->impl();
 257     trampoline::decrement(xi);
 258     x=from_impl(xi);
 259   }
 260
 261   static void advance(random_access_index_node*& x,std::ptrdiff_t n)
 262   {
 263     impl_pointer xi=x->impl();
 264     trampoline::advance(xi,n);
 265     x=from_impl(xi);
 266   }
 267
 268   static std::ptrdiff_t distance(
 269     random_access_index_node* x,random_access_index_node* y)
 270   {
 271     return trampoline::distance(x->impl(),y->impl());
 272   }
 273 };
 274
 275 } /* namespace multi_index::detail */
 276
 277 } /* namespace multi_index */
 278
 279 } /* namespace boost */
 280
 281 #endif