1/* Copyright 2003-2022 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_RANKED_INDEX_HPP
10#define BOOST_MULTI_INDEX_RANKED_INDEX_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/multi_index/detail/ord_index_impl.hpp>
18#include <boost/multi_index/detail/rnk_index_ops.hpp>
19#include <boost/multi_index/ranked_index_fwd.hpp>
20
21namespace boost{
22
23namespace multi_index{
24
25namespace detail{
26
27/* ranked_index augments a given ordered index to provide rank operations */
28
29template<typename OrderedIndexNodeImpl>
30struct ranked_node:OrderedIndexNodeImpl
31{
32 typedef typename OrderedIndexNodeImpl::size_type size_type;
33
34 size_type size;
35};
36
37template<typename OrderedIndexImpl>
38class ranked_index:public OrderedIndexImpl
39{
40 typedef OrderedIndexImpl super;
41
42protected:
43 typedef typename super::index_node_type index_node_type;
44 typedef typename super::node_impl_pointer node_impl_pointer;
45
46public:
47 typedef typename super::ctor_args_list ctor_args_list;
48 typedef typename super::allocator_type allocator_type;
49 typedef typename super::iterator iterator;
50 typedef typename super::size_type size_type;
51
52 /* set operations */
53
54 template<typename CompatibleKey>
55 size_type count(const CompatibleKey& x)const
56 {
57 return count(x,this->comp_);
58 }
59
60 template<typename CompatibleKey,typename CompatibleCompare>
61 size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
62 {
63 std::pair<size_type,size_type> p=this->equal_range_rank(x,comp);
64 return p.second-p.first;
65 }
66
67 /* rank operations */
68
69 iterator nth(size_type n)const
70 {
71 return this->make_iterator(index_node_type::from_impl(
72 ranked_index_nth(n,this->header()->impl())));
73 }
74
75 size_type rank(iterator position)const
76 {
77 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
78 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
79
80 return ranked_index_rank(
81 position.get_node()->impl(),this->header()->impl());
82 }
83
84 template<typename CompatibleKey>
85 size_type find_rank(const CompatibleKey& x)const
86 {
87 return ranked_index_find_rank(
88 this->root(),this->header(),this->key,x,this->comp_);
89 }
90
91 template<typename CompatibleKey,typename CompatibleCompare>
92 size_type find_rank(
93 const CompatibleKey& x,const CompatibleCompare& comp)const
94 {
95 return ranked_index_find_rank(
96 this->root(),this->header(),this->key,x,comp);
97 }
98
99 template<typename CompatibleKey>
100 size_type lower_bound_rank(const CompatibleKey& x)const
101 {
102 return ranked_index_lower_bound_rank(
103 this->root(),this->header(),this->key,x,this->comp_);
104 }
105
106 template<typename CompatibleKey,typename CompatibleCompare>
107 size_type lower_bound_rank(
108 const CompatibleKey& x,const CompatibleCompare& comp)const
109 {
110 return ranked_index_lower_bound_rank(
111 this->root(),this->header(),this->key,x,comp);
112 }
113
114 template<typename CompatibleKey>
115 size_type upper_bound_rank(const CompatibleKey& x)const
116 {
117 return ranked_index_upper_bound_rank(
118 this->root(),this->header(),this->key,x,this->comp_);
119 }
120
121 template<typename CompatibleKey,typename CompatibleCompare>
122 size_type upper_bound_rank(
123 const CompatibleKey& x,const CompatibleCompare& comp)const
124 {
125 return ranked_index_upper_bound_rank(
126 this->root(),this->header(),this->key,x,comp);
127 }
128
129 template<typename CompatibleKey>
130 std::pair<size_type,size_type> equal_range_rank(
131 const CompatibleKey& x)const
132 {
133 return ranked_index_equal_range_rank(
134 this->root(),this->header(),this->key,x,this->comp_);
135 }
136
137 template<typename CompatibleKey,typename CompatibleCompare>
138 std::pair<size_type,size_type> equal_range_rank(
139 const CompatibleKey& x,const CompatibleCompare& comp)const
140 {
141 return ranked_index_equal_range_rank(
142 this->root(),this->header(),this->key,x,comp);
143 }
144
145 template<typename LowerBounder,typename UpperBounder>
146 std::pair<size_type,size_type>
147 range_rank(LowerBounder lower,UpperBounder upper)const
148 {
149 typedef typename mpl::if_<
150 is_same<LowerBounder,unbounded_type>,
151 BOOST_DEDUCED_TYPENAME mpl::if_<
152 is_same<UpperBounder,unbounded_type>,
153 both_unbounded_tag,
154 lower_unbounded_tag
155 >::type,
156 BOOST_DEDUCED_TYPENAME mpl::if_<
157 is_same<UpperBounder,unbounded_type>,
158 upper_unbounded_tag,
159 none_unbounded_tag
160 >::type
161 >::type dispatch;
162
163 return range_rank(lower,upper,dispatch());
164 }
165
166protected:
167 ranked_index(const ranked_index& x):super(x){};
168
169 ranked_index(const ranked_index& x,do_not_copy_elements_tag):
170 super(x,do_not_copy_elements_tag()){};
171
172 ranked_index(
173 const ctor_args_list& args_list,const allocator_type& al):
174 super(args_list,al){}
175
176private:
177 template<typename LowerBounder,typename UpperBounder>
178 std::pair<size_type,size_type>
179 range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
180 {
181 index_node_type* y=this->header();
182 index_node_type* z=this->root();
183
184 if(!z)return std::pair<size_type,size_type>(0,0);
185
186 size_type s=z->impl()->size;
187
188 do{
189 if(!lower(this->key(z->value()))){
190 z=index_node_type::from_impl(z->right());
191 }
192 else if(!upper(this->key(z->value()))){
193 y=z;
194 s-=ranked_node_size(y->right())+1;
195 z=index_node_type::from_impl(z->left());
196 }
197 else{
198 return std::pair<size_type,size_type>(
199 s-z->impl()->size+
200 lower_range_rank(index_node_type::from_impl(z->left()),z,lower),
201 s-ranked_node_size(z->right())+
202 upper_range_rank(index_node_type::from_impl(z->right()),y,upper));
203 }
204 }while(z);
205
206 return std::pair<size_type,size_type>(s,s);
207 }
208
209 template<typename LowerBounder,typename UpperBounder>
210 std::pair<size_type,size_type>
211 range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
212 {
213 return std::pair<size_type,size_type>(
214 0,
215 upper_range_rank(this->root(),this->header(),upper));
216 }
217
218 template<typename LowerBounder,typename UpperBounder>
219 std::pair<size_type,size_type>
220 range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
221 {
222 return std::pair<size_type,size_type>(
223 lower_range_rank(this->root(),this->header(),lower),
224 this->size());
225 }
226
227 template<typename LowerBounder,typename UpperBounder>
228 std::pair<size_type,size_type>
229 range_rank(LowerBounder,UpperBounder,both_unbounded_tag)const
230 {
231 return std::pair<size_type,size_type>(0,this->size());
232 }
233
234 template<typename LowerBounder>
235 size_type
236 lower_range_rank(
237 index_node_type* top,index_node_type* y,LowerBounder lower)const
238 {
239 if(!top)return 0;
240
241 size_type s=top->impl()->size;
242
243 do{
244 if(lower(this->key(top->value()))){
245 y=top;
246 s-=ranked_node_size(y->right())+1;
247 top=index_node_type::from_impl(top->left());
248 }
249 else top=index_node_type::from_impl(top->right());
250 }while(top);
251
252 return s;
253 }
254
255 template<typename UpperBounder>
256 size_type
257 upper_range_rank(
258 index_node_type* top,index_node_type* y,UpperBounder upper)const
259 {
260 if(!top)return 0;
261
262 size_type s=top->impl()->size;
263
264 do{
265 if(!upper(this->key(top->value()))){
266 y=top;
267 s-=ranked_node_size(y->right())+1;
268 top=index_node_type::from_impl(top->left());
269 }
270 else top=index_node_type::from_impl(top->right());
271 }while(top);
272
273 return s;
274 }
275};
276
277/* augmenting policy for ordered_index */
278
279struct rank_policy
280{
281 template<typename OrderedIndexNodeImpl>
282 struct augmented_node
283 {
284 typedef ranked_node<OrderedIndexNodeImpl> type;
285 };
286
287 template<typename OrderedIndexImpl>
288 struct augmented_interface
289 {
290 typedef ranked_index<OrderedIndexImpl> type;
291 };
292
293 /* algorithmic stuff */
294
295 template<typename Pointer>
296 static void add(Pointer x,Pointer root)
297 {
298 x->size=1;
299 while(x!=root){
300 x=x->parent();
301 ++(x->size);
302 }
303 }
304
305 template<typename Pointer>
306 static void remove(Pointer x,Pointer root)
307 {
308 while(x!=root){
309 x=x->parent();
310 --(x->size);
311 }
312 }
313
314 template<typename Pointer>
315 static void copy(Pointer x,Pointer y)
316 {
317 y->size=x->size;
318 }
319
320 template<typename Pointer>
321 static void rotate_left(Pointer x,Pointer y) /* in: x==y->left() */
322 {
323 y->size=x->size;
324 x->size=ranked_node_size(x->left())+ranked_node_size(x->right())+1;
325 }
326
327 template<typename Pointer>
328 static void rotate_right(Pointer x,Pointer y) /* in: x==y->right() */
329 {
330 rotate_left(x,y);
331 }
332
333#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
334 /* invariant stuff */
335
336 template<typename Pointer>
337 static bool invariant(Pointer x)
338 {
339 return x->size==ranked_node_size(x->left())+ranked_node_size(x->right())+1;
340 }
341#endif
342};
343
344} /* namespace multi_index::detail */
345
346/* ranked_index specifiers */
347
348template<typename Arg1,typename Arg2,typename Arg3>
349struct ranked_unique
350{
351 typedef typename detail::ordered_index_args<
352 Arg1,Arg2,Arg3> index_args;
353 typedef typename index_args::tag_list_type::type tag_list_type;
354 typedef typename index_args::key_from_value_type key_from_value_type;
355 typedef typename index_args::compare_type compare_type;
356
357 template<typename Super>
358 struct node_class
359 {
360 typedef detail::ordered_index_node<detail::rank_policy,Super> type;
361 };
362
363 template<typename SuperMeta>
364 struct index_class
365 {
366 typedef detail::ordered_index<
367 key_from_value_type,compare_type,
368 SuperMeta,tag_list_type,detail::ordered_unique_tag,
369 detail::rank_policy> type;
370 };
371};
372
373template<typename Arg1,typename Arg2,typename Arg3>
374struct ranked_non_unique
375{
376 typedef detail::ordered_index_args<
377 Arg1,Arg2,Arg3> index_args;
378 typedef typename index_args::tag_list_type::type tag_list_type;
379 typedef typename index_args::key_from_value_type key_from_value_type;
380 typedef typename index_args::compare_type compare_type;
381
382 template<typename Super>
383 struct node_class
384 {
385 typedef detail::ordered_index_node<detail::rank_policy,Super> type;
386 };
387
388 template<typename SuperMeta>
389 struct index_class
390 {
391 typedef detail::ordered_index<
392 key_from_value_type,compare_type,
393 SuperMeta,tag_list_type,detail::ordered_non_unique_tag,
394 detail::rank_policy> type;
395 };
396};
397
398} /* namespace multi_index */
399
400} /* namespace boost */
401
402#endif
403

source code of boost/libs/multi_index/include/boost/multi_index/ranked_index.hpp