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