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
|