1 /* Copyright 2003-2018 Joaquin M Lopez Munoz.
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_RNK_INDEX_OPS_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RNK_INDEX_OPS_HPP
11
12 #if defined(_MSC_VER)
13 #pragma once
14 #endif
15
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
17 #include <boost/core/pointer_traits.hpp>
18 #include <boost/mpl/and.hpp>
19 #include <boost/multi_index/detail/promotes_arg.hpp>
20 #include <utility>
21
22 namespace boost{
23
24 namespace multi_index{
25
26 namespace detail{
27
28 /* Common code for ranked_index memfuns having templatized and
29 * non-templatized versions.
30 */
31
32 template<typename Pointer>
33 struct ranked_node_size_type
34 {
35 typedef typename boost::pointer_traits<Pointer>::
36 element_type::size_type type;
37 };
38
39 template<typename Pointer>
40 inline typename ranked_node_size_type<Pointer>::type
ranked_node_size(Pointer x)41 ranked_node_size(Pointer x)
42 {
43 return x!=Pointer(0)?x->size:0;
44 }
45
46 template<typename Pointer>
ranked_index_nth(BOOST_DEDUCED_TYPENAME ranked_node_size_type<Pointer>::type n,Pointer end_)47 inline Pointer ranked_index_nth(
48 BOOST_DEDUCED_TYPENAME ranked_node_size_type<Pointer>::type n,Pointer end_)
49 {
50 typedef typename ranked_node_size_type<Pointer>::type size_type;
51
52 Pointer top=end_->parent();
53 if(top==Pointer(0)||n>=top->size)return end_;
54
55 for(;;){
56 size_type s=ranked_node_size(top->left());
57 if(n==s)return top;
58 if(n<s)top=top->left();
59 else{
60 top=top->right();
61 n-=s+1;
62 }
63 }
64 }
65
66 template<typename Pointer>
67 inline typename ranked_node_size_type<Pointer>::type
ranked_index_rank(Pointer x,Pointer end_)68 ranked_index_rank(Pointer x,Pointer end_)
69 {
70 typedef typename ranked_node_size_type<Pointer>::type size_type;
71
72 Pointer top=end_->parent();
73 if(top==Pointer(0))return 0;
74 if(x==end_)return top->size;
75
76 size_type s=ranked_node_size(x->left());
77 while(x!=top){
78 Pointer z=x->parent();
79 if(x==z->right()){
80 s+=ranked_node_size(z->left())+1;
81 }
82 x=z;
83 }
84 return s;
85 }
86
87 template<
88 typename Node,typename KeyFromValue,
89 typename CompatibleKey,typename CompatibleCompare
90 >
ranked_index_find_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)91 inline typename Node::size_type ranked_index_find_rank(
92 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
93 const CompatibleCompare& comp)
94 {
95 typedef typename KeyFromValue::result_type key_type;
96
97 return ranked_index_find_rank(
98 top,y,key,x,comp,
99 mpl::and_<
100 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
101 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
102 }
103
104 template<
105 typename Node,typename KeyFromValue,
106 typename CompatibleCompare
107 >
ranked_index_find_rank(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)108 inline typename Node::size_type ranked_index_find_rank(
109 Node* top,Node* y,const KeyFromValue& key,
110 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
111 const CompatibleCompare& comp,mpl::true_)
112 {
113 return ranked_index_find_rank(top,y,key,x,comp,mpl::false_());
114 }
115
116 template<
117 typename Node,typename KeyFromValue,
118 typename CompatibleKey,typename CompatibleCompare
119 >
ranked_index_find_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)120 inline typename Node::size_type ranked_index_find_rank(
121 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
122 const CompatibleCompare& comp,mpl::false_)
123 {
124 typedef typename Node::size_type size_type;
125
126 if(!top)return 0;
127
128 size_type s=top->impl()->size,
129 s0=s;
130 Node* y0=y;
131
132 do{
133 if(!comp(key(top->value()),x)){
134 y=top;
135 s-=ranked_node_size(y->right())+1;
136 top=Node::from_impl(top->left());
137 }
138 else top=Node::from_impl(top->right());
139 }while(top);
140
141 return (y==y0||comp(x,key(y->value())))?s0:s;
142 }
143
144 template<
145 typename Node,typename KeyFromValue,
146 typename CompatibleKey,typename CompatibleCompare
147 >
ranked_index_lower_bound_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)148 inline typename Node::size_type ranked_index_lower_bound_rank(
149 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
150 const CompatibleCompare& comp)
151 {
152 typedef typename KeyFromValue::result_type key_type;
153
154 return ranked_index_lower_bound_rank(
155 top,y,key,x,comp,
156 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
157 }
158
159 template<
160 typename Node,typename KeyFromValue,
161 typename CompatibleCompare
162 >
ranked_index_lower_bound_rank(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)163 inline typename Node::size_type ranked_index_lower_bound_rank(
164 Node* top,Node* y,const KeyFromValue& key,
165 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
166 const CompatibleCompare& comp,mpl::true_)
167 {
168 return ranked_index_lower_bound_rank(top,y,key,x,comp,mpl::false_());
169 }
170
171 template<
172 typename Node,typename KeyFromValue,
173 typename CompatibleKey,typename CompatibleCompare
174 >
ranked_index_lower_bound_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)175 inline typename Node::size_type ranked_index_lower_bound_rank(
176 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
177 const CompatibleCompare& comp,mpl::false_)
178 {
179 typedef typename Node::size_type size_type;
180
181 if(!top)return 0;
182
183 size_type s=top->impl()->size;
184
185 do{
186 if(!comp(key(top->value()),x)){
187 y=top;
188 s-=ranked_node_size(y->right())+1;
189 top=Node::from_impl(top->left());
190 }
191 else top=Node::from_impl(top->right());
192 }while(top);
193
194 return s;
195 }
196
197 template<
198 typename Node,typename KeyFromValue,
199 typename CompatibleKey,typename CompatibleCompare
200 >
ranked_index_upper_bound_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)201 inline typename Node::size_type ranked_index_upper_bound_rank(
202 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
203 const CompatibleCompare& comp)
204 {
205 typedef typename KeyFromValue::result_type key_type;
206
207 return ranked_index_upper_bound_rank(
208 top,y,key,x,comp,
209 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
210 }
211
212 template<
213 typename Node,typename KeyFromValue,
214 typename CompatibleCompare
215 >
ranked_index_upper_bound_rank(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)216 inline typename Node::size_type ranked_index_upper_bound_rank(
217 Node* top,Node* y,const KeyFromValue& key,
218 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
219 const CompatibleCompare& comp,mpl::true_)
220 {
221 return ranked_index_upper_bound_rank(top,y,key,x,comp,mpl::false_());
222 }
223
224 template<
225 typename Node,typename KeyFromValue,
226 typename CompatibleKey,typename CompatibleCompare
227 >
ranked_index_upper_bound_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)228 inline typename Node::size_type ranked_index_upper_bound_rank(
229 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
230 const CompatibleCompare& comp,mpl::false_)
231 {
232 typedef typename Node::size_type size_type;
233
234 if(!top)return 0;
235
236 size_type s=top->impl()->size;
237
238 do{
239 if(comp(x,key(top->value()))){
240 y=top;
241 s-=ranked_node_size(y->right())+1;
242 top=Node::from_impl(top->left());
243 }
244 else top=Node::from_impl(top->right());
245 }while(top);
246
247 return s;
248 }
249
250 template<
251 typename Node,typename KeyFromValue,
252 typename CompatibleKey,typename CompatibleCompare
253 >
254 inline std::pair<typename Node::size_type,typename Node::size_type>
ranked_index_equal_range_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)255 ranked_index_equal_range_rank(
256 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
257 const CompatibleCompare& comp)
258 {
259 typedef typename KeyFromValue::result_type key_type;
260
261 return ranked_index_equal_range_rank(
262 top,y,key,x,comp,
263 mpl::and_<
264 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
265 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
266 }
267
268 template<
269 typename Node,typename KeyFromValue,
270 typename CompatibleCompare
271 >
272 inline std::pair<typename Node::size_type,typename Node::size_type>
ranked_index_equal_range_rank(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)273 ranked_index_equal_range_rank(
274 Node* top,Node* y,const KeyFromValue& key,
275 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
276 const CompatibleCompare& comp,mpl::true_)
277 {
278 return ranked_index_equal_range_rank(top,y,key,x,comp,mpl::false_());
279 }
280
281 template<
282 typename Node,typename KeyFromValue,
283 typename CompatibleKey,typename CompatibleCompare
284 >
285 inline std::pair<typename Node::size_type,typename Node::size_type>
ranked_index_equal_range_rank(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)286 ranked_index_equal_range_rank(
287 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
288 const CompatibleCompare& comp,mpl::false_)
289 {
290 typedef typename Node::size_type size_type;
291
292 if(!top)return std::pair<size_type,size_type>(0,0);
293
294 size_type s=top->impl()->size;
295
296 do{
297 if(comp(key(top->value()),x)){
298 top=Node::from_impl(top->right());
299 }
300 else if(comp(x,key(top->value()))){
301 y=top;
302 s-=ranked_node_size(y->right())+1;
303 top=Node::from_impl(top->left());
304 }
305 else{
306 return std::pair<size_type,size_type>(
307 s-top->impl()->size+
308 ranked_index_lower_bound_rank(
309 Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
310 s-ranked_node_size(top->right())+
311 ranked_index_upper_bound_rank(
312 Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
313 }
314 }while(top);
315
316 return std::pair<size_type,size_type>(s,s);
317 }
318
319 } /* namespace multi_index::detail */
320
321 } /* namespace multi_index */
322
323 } /* namespace boost */
324
325 #endif
326