epoc32/include/stdapis/boost/multi_index/detail/rnd_index_node.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
williamr@2
     1
/* Copyright 2003-2006 Joaquín M López Muñoz.
williamr@2
     2
 * Distributed under the Boost Software License, Version 1.0.
williamr@2
     3
 * (See accompanying file LICENSE_1_0.txt or copy at
williamr@2
     4
 * http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     5
 *
williamr@2
     6
 * See http://www.boost.org/libs/multi_index for library home page.
williamr@2
     7
 */
williamr@2
     8
williamr@2
     9
#ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
williamr@2
    10
#define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_NODE_HPP
williamr@2
    11
williamr@2
    12
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
williamr@2
    13
#pragma once
williamr@2
    14
#endif
williamr@2
    15
williamr@2
    16
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
williamr@2
    17
#include <algorithm>
williamr@2
    18
#include <boost/math/common_factor_rt.hpp>
williamr@2
    19
#include <cstddef>
williamr@2
    20
#include <functional>
williamr@2
    21
williamr@2
    22
namespace boost{
williamr@2
    23
williamr@2
    24
namespace multi_index{
williamr@2
    25
williamr@2
    26
namespace detail{
williamr@2
    27
williamr@2
    28
struct random_access_index_node_impl
williamr@2
    29
{
williamr@2
    30
  random_access_index_node_impl**& up(){return up_;}
williamr@2
    31
  random_access_index_node_impl**  up()const{return up_;}
williamr@2
    32
williamr@2
    33
  /* interoperability with rnd_node_iterator */
williamr@2
    34
williamr@2
    35
  static void increment(random_access_index_node_impl*& x)
williamr@2
    36
  {
williamr@2
    37
    x=*(x->up()+1);
williamr@2
    38
  }
williamr@2
    39
williamr@2
    40
  static void decrement(random_access_index_node_impl*& x)
williamr@2
    41
  {
williamr@2
    42
    x=*(x->up()-1);
williamr@2
    43
  }
williamr@2
    44
williamr@2
    45
  static void advance(
williamr@2
    46
    random_access_index_node_impl*& x,std::ptrdiff_t n)
williamr@2
    47
  {
williamr@2
    48
    x=*(x->up()+n);
williamr@2
    49
  }
williamr@2
    50
williamr@2
    51
  static std::ptrdiff_t distance(
williamr@2
    52
    random_access_index_node_impl* x,random_access_index_node_impl* y)
williamr@2
    53
  {
williamr@2
    54
    return y->up()-x->up();
williamr@2
    55
  }
williamr@2
    56
williamr@2
    57
  /* algorithmic stuff */
williamr@2
    58
williamr@2
    59
  static void relocate(
williamr@2
    60
    random_access_index_node_impl** pos,
williamr@2
    61
    random_access_index_node_impl** x)
williamr@2
    62
  {
williamr@2
    63
    random_access_index_node_impl* n=*x;
williamr@2
    64
    if(x<pos){
williamr@2
    65
      extract(x,pos);
williamr@2
    66
      *(pos-1)=n;
williamr@2
    67
      n->up()=pos-1;
williamr@2
    68
    }
williamr@2
    69
    else{
williamr@2
    70
      while(x!=pos){
williamr@2
    71
        *x=*(x-1);
williamr@2
    72
        (*x)->up()=x;
williamr@2
    73
        --x;
williamr@2
    74
      }
williamr@2
    75
      *pos=n;
williamr@2
    76
      n->up()=pos;
williamr@2
    77
    }
williamr@2
    78
  };
williamr@2
    79
williamr@2
    80
  static void relocate(
williamr@2
    81
    random_access_index_node_impl** pos,
williamr@2
    82
    random_access_index_node_impl** first,
williamr@2
    83
    random_access_index_node_impl** last)
williamr@2
    84
  {
williamr@2
    85
    random_access_index_node_impl** begin,**middle,**end;
williamr@2
    86
    if(pos<first){
williamr@2
    87
      begin=pos;
williamr@2
    88
      middle=first;
williamr@2
    89
      end=last;
williamr@2
    90
    }
williamr@2
    91
    else{
williamr@2
    92
      begin=first;
williamr@2
    93
      middle=last;
williamr@2
    94
      end=pos;
williamr@2
    95
    }
williamr@2
    96
williamr@2
    97
    std::ptrdiff_t n=end-begin;
williamr@2
    98
    std::ptrdiff_t m=middle-begin;
williamr@2
    99
    std::ptrdiff_t n_m=n-m;
williamr@2
   100
    std::ptrdiff_t p=math::gcd(n,m);
williamr@2
   101
williamr@2
   102
    for(std::ptrdiff_t i=0;i<p;++i){
williamr@2
   103
      random_access_index_node_impl* tmp=begin[i];
williamr@2
   104
      for(std::ptrdiff_t j=i,k;;){
williamr@2
   105
        if(j<n_m)k=j+m;
williamr@2
   106
        else     k=j-n_m;
williamr@2
   107
        if(k==i){
williamr@2
   108
          begin[j]=tmp;
williamr@2
   109
          begin[j]->up()=&begin[j];
williamr@2
   110
          break;
williamr@2
   111
        }
williamr@2
   112
        else{
williamr@2
   113
          begin[j]=begin[k];
williamr@2
   114
          begin[j]->up()=&begin[j];
williamr@2
   115
        }
williamr@2
   116
williamr@2
   117
        if(k<n_m)j=k+m;
williamr@2
   118
        else     j=k-n_m;
williamr@2
   119
        if(j==i){
williamr@2
   120
          begin[k]=tmp;
williamr@2
   121
          begin[k]->up()=&begin[k];
williamr@2
   122
          break;
williamr@2
   123
        }
williamr@2
   124
        else{
williamr@2
   125
          begin[k]=begin[j];
williamr@2
   126
          begin[k]->up()=&begin[k];
williamr@2
   127
        }
williamr@2
   128
      }
williamr@2
   129
    }
williamr@2
   130
  };
williamr@2
   131
williamr@2
   132
  static void extract(
williamr@2
   133
    random_access_index_node_impl** x,
williamr@2
   134
    random_access_index_node_impl** pend)
williamr@2
   135
  {
williamr@2
   136
    --pend;
williamr@2
   137
    while(x!=pend){
williamr@2
   138
      *x=*(x+1);
williamr@2
   139
      (*x)->up()=x;
williamr@2
   140
      ++x;
williamr@2
   141
    }
williamr@2
   142
  }
williamr@2
   143
williamr@2
   144
  static void transfer(
williamr@2
   145
    random_access_index_node_impl** pbegin0,
williamr@2
   146
    random_access_index_node_impl** pend0,
williamr@2
   147
    random_access_index_node_impl** pbegin1)
williamr@2
   148
  {
williamr@2
   149
    while(pbegin0!=pend0){
williamr@2
   150
      *pbegin1=*pbegin0++;
williamr@2
   151
      (*pbegin1)->up()=pbegin1;
williamr@2
   152
      ++pbegin1;
williamr@2
   153
    }
williamr@2
   154
  }
williamr@2
   155
williamr@2
   156
  static void reverse(
williamr@2
   157
    random_access_index_node_impl** pbegin,
williamr@2
   158
    random_access_index_node_impl** pend)
williamr@2
   159
  {
williamr@2
   160
    std::ptrdiff_t d=(pend-pbegin)/2;
williamr@2
   161
    for(std::ptrdiff_t i=0;i<d;++i){
williamr@2
   162
      std::swap(*pbegin,*--pend);
williamr@2
   163
      (*pbegin)->up()=pbegin;
williamr@2
   164
      (*pend)->up()=pend;
williamr@2
   165
      ++pbegin;
williamr@2
   166
    }
williamr@2
   167
  }
williamr@2
   168
williamr@2
   169
private:
williamr@2
   170
  random_access_index_node_impl** up_;
williamr@2
   171
};
williamr@2
   172
williamr@2
   173
template<typename Super>
williamr@2
   174
struct random_access_index_node_trampoline:random_access_index_node_impl{};
williamr@2
   175
williamr@2
   176
template<typename Super>
williamr@2
   177
struct random_access_index_node:
williamr@2
   178
  Super,random_access_index_node_trampoline<Super>
williamr@2
   179
{
williamr@2
   180
  random_access_index_node_impl**& up(){return impl_type::up();}
williamr@2
   181
  random_access_index_node_impl**  up()const{return impl_type::up();}
williamr@2
   182
williamr@2
   183
  random_access_index_node_impl*       impl()
williamr@2
   184
    {return static_cast<impl_type*>(this);}
williamr@2
   185
  const random_access_index_node_impl* impl()const
williamr@2
   186
    {return static_cast<const impl_type*>(this);}
williamr@2
   187
williamr@2
   188
  static random_access_index_node* from_impl(random_access_index_node_impl *x)
williamr@2
   189
  {
williamr@2
   190
    return static_cast<random_access_index_node*>(
williamr@2
   191
      static_cast<impl_type*>(x));
williamr@2
   192
  }
williamr@2
   193
williamr@2
   194
  static const random_access_index_node* from_impl(
williamr@2
   195
    const random_access_index_node_impl* x)
williamr@2
   196
  {
williamr@2
   197
    return static_cast<const random_access_index_node*>(
williamr@2
   198
      static_cast<const impl_type*>(x));
williamr@2
   199
  }
williamr@2
   200
williamr@2
   201
  /* interoperability with rnd_node_iterator */
williamr@2
   202
williamr@2
   203
  static void increment(random_access_index_node*& x)
williamr@2
   204
  {
williamr@2
   205
    random_access_index_node_impl* xi=x->impl();
williamr@2
   206
    impl_type::increment(xi);
williamr@2
   207
    x=from_impl(xi);
williamr@2
   208
  }
williamr@2
   209
williamr@2
   210
  static void decrement(random_access_index_node*& x)
williamr@2
   211
  {
williamr@2
   212
    random_access_index_node_impl* xi=x->impl();
williamr@2
   213
    impl_type::decrement(xi);
williamr@2
   214
    x=from_impl(xi);
williamr@2
   215
  }
williamr@2
   216
williamr@2
   217
  static void advance(random_access_index_node*& x,std::ptrdiff_t n)
williamr@2
   218
  {
williamr@2
   219
    random_access_index_node_impl* xi=x->impl();
williamr@2
   220
    impl_type::advance(xi,n);
williamr@2
   221
    x=from_impl(xi);
williamr@2
   222
  }
williamr@2
   223
williamr@2
   224
  static std::ptrdiff_t distance(
williamr@2
   225
    random_access_index_node* x,random_access_index_node* y)
williamr@2
   226
  {
williamr@2
   227
    return impl_type::distance(x->impl(),y->impl());
williamr@2
   228
  }
williamr@2
   229
williamr@2
   230
private:
williamr@2
   231
  typedef random_access_index_node_trampoline<Super> impl_type;
williamr@2
   232
};
williamr@2
   233
williamr@2
   234
} /* namespace multi_index::detail */
williamr@2
   235
williamr@2
   236
} /* namespace multi_index */
williamr@2
   237
williamr@2
   238
} /* namespace boost */
williamr@2
   239
williamr@2
   240
#endif