1 /* Copyright 2003-2015 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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_RANKED_INDEX_HPP
10 #define BOOST_MULTI_INDEX_RANKED_INDEX_HPP
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>
23 namespace multi_index{
27 /* ranked_index augments a given ordered index to provide rank operations */
29 template<typename OrderedIndexNodeImpl>
30 struct ranked_node:OrderedIndexNodeImpl
35 template<typename OrderedIndexImpl>
36 class ranked_index:public OrderedIndexImpl
38 typedef OrderedIndexImpl super;
41 typedef typename super::node_type node_type;
42 typedef typename super::node_impl_pointer node_impl_pointer;
45 typedef typename super::ctor_args_list ctor_args_list;
46 typedef typename super::allocator_type allocator_type;
47 typedef typename super::iterator iterator;
51 iterator nth(std::size_t n)const
53 return this->make_iterator(node_type::from_impl(
54 ranked_index_nth(n,this->header()->impl())));
57 std::size_t rank(iterator position)const
59 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
60 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
62 return ranked_index_rank(
63 position.get_node()->impl(),this->header()->impl());
66 template<typename CompatibleKey>
67 std::size_t find_rank(const CompatibleKey& x)const
69 return ranked_index_find_rank(
70 this->root(),this->header(),this->key,x,this->comp_);
73 template<typename CompatibleKey,typename CompatibleCompare>
74 std::size_t find_rank(
75 const CompatibleKey& x,const CompatibleCompare& comp)const
77 return ranked_index_find_rank(
78 this->root(),this->header(),this->key,x,comp);
81 template<typename CompatibleKey>
82 std::size_t lower_bound_rank(const CompatibleKey& x)const
84 return ranked_index_lower_bound_rank(
85 this->root(),this->header(),this->key,x,this->comp_);
88 template<typename CompatibleKey,typename CompatibleCompare>
89 std::size_t lower_bound_rank(
90 const CompatibleKey& x,const CompatibleCompare& comp)const
92 return ranked_index_lower_bound_rank(
93 this->root(),this->header(),this->key,x,comp);
96 template<typename CompatibleKey>
97 std::size_t upper_bound_rank(const CompatibleKey& x)const
99 return ranked_index_upper_bound_rank(
100 this->root(),this->header(),this->key,x,this->comp_);
103 template<typename CompatibleKey,typename CompatibleCompare>
104 std::size_t upper_bound_rank(
105 const CompatibleKey& x,const CompatibleCompare& comp)const
107 return ranked_index_upper_bound_rank(
108 this->root(),this->header(),this->key,x,comp);
111 template<typename CompatibleKey>
112 std::pair<std::size_t,std::size_t> equal_range_rank(
113 const CompatibleKey& x)const
115 return ranked_index_equal_range_rank(
116 this->root(),this->header(),this->key,x,this->comp_);
119 template<typename CompatibleKey,typename CompatibleCompare>
120 std::pair<std::size_t,std::size_t> equal_range_rank(
121 const CompatibleKey& x,const CompatibleCompare& comp)const
123 return ranked_index_equal_range_rank(
124 this->root(),this->header(),this->key,x,comp);
127 template<typename LowerBounder,typename UpperBounder>
128 std::pair<std::size_t,std::size_t>
129 range_rank(LowerBounder lower,UpperBounder upper)const
131 typedef typename mpl::if_<
132 is_same<LowerBounder,unbounded_type>,
133 BOOST_DEDUCED_TYPENAME mpl::if_<
134 is_same<UpperBounder,unbounded_type>,
138 BOOST_DEDUCED_TYPENAME mpl::if_<
139 is_same<UpperBounder,unbounded_type>,
145 return range_rank(lower,upper,dispatch());
149 ranked_index(const ranked_index& x):super(x){};
151 ranked_index(const ranked_index& x,do_not_copy_elements_tag):
152 super(x,do_not_copy_elements_tag()){};
155 const ctor_args_list& args_list,const allocator_type& al):
156 super(args_list,al){}
159 template<typename LowerBounder,typename UpperBounder>
160 std::pair<std::size_t,std::size_t>
161 range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
163 node_type* y=this->header();
164 node_type* z=this->root();
166 if(!z)return std::pair<std::size_t,std::size_t>(0,0);
168 std::size_t s=z->size;
171 if(!lower(this->key(z->value()))){
172 z=node_type::from_impl(z->right());
174 else if(!upper(this->key(z->value()))){
176 s-=ranked_node_size(y->right())+1;
177 z=node_type::from_impl(z->left());
180 return std::pair<std::size_t,std::size_t>(
182 lower_range_rank(node_type::from_impl(z->left()),z,lower),
183 s-ranked_node_size(z->right())+
184 upper_range_rank(node_type::from_impl(z->right()),y,upper));
188 return std::pair<std::size_t,std::size_t>(s,s);
191 template<typename LowerBounder,typename UpperBounder>
192 std::pair<std::size_t,std::size_t>
193 range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
195 return std::pair<std::size_t,std::size_t>(
197 upper_range_rank(this->root(),this->header(),upper));
200 template<typename LowerBounder,typename UpperBounder>
201 std::pair<std::size_t,std::size_t>
202 range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
204 return std::pair<std::size_t,std::size_t>(
205 lower_range_rank(this->root(),this->header(),lower),
209 template<typename LowerBounder,typename UpperBounder>
210 std::pair<std::size_t,std::size_t>
211 range_rank(LowerBounder,UpperBounder,both_unbounded_tag)const
213 return std::pair<std::size_t,std::size_t>(0,this->size());
216 template<typename LowerBounder>
218 lower_range_rank(node_type* top,node_type* y,LowerBounder lower)const
222 std::size_t s=top->size;
225 if(lower(this->key(top->value()))){
227 s-=ranked_node_size(y->right())+1;
228 top=node_type::from_impl(top->left());
230 else top=node_type::from_impl(top->right());
236 template<typename UpperBounder>
238 upper_range_rank(node_type* top,node_type* y,UpperBounder upper)const
242 std::size_t s=top->size;
245 if(!upper(this->key(top->value()))){
247 s-=ranked_node_size(y->right())+1;
248 top=node_type::from_impl(top->left());
250 else top=node_type::from_impl(top->right());
257 /* augmenting policy for ordered_index */
261 template<typename OrderedIndexNodeImpl>
262 struct augmented_node
264 typedef ranked_node<OrderedIndexNodeImpl> type;
267 template<typename OrderedIndexImpl>
268 struct augmented_interface
270 typedef ranked_index<OrderedIndexImpl> type;
273 /* algorithmic stuff */
275 template<typename Pointer>
276 static void add(Pointer x,Pointer root)
285 template<typename Pointer>
286 static void remove(Pointer x,Pointer root)
294 template<typename Pointer>
295 static void copy(Pointer x,Pointer y)
300 template<typename Pointer>
301 static void rotate_left(Pointer x,Pointer y) /* in: x==y->left() */
304 x->size=ranked_node_size(x->left())+ranked_node_size(x->right())+1;
307 template<typename Pointer>
308 static void rotate_right(Pointer x,Pointer y) /* in: x==y->right() */
313 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
314 /* invariant stuff */
316 template<typename Pointer>
317 static bool invariant(Pointer x)
319 return x->size==ranked_node_size(x->left())+ranked_node_size(x->right())+1;
324 } /* namespace multi_index::detail */
326 /* ranked_index specifiers */
328 template<typename Arg1,typename Arg2,typename Arg3>
331 typedef typename detail::ordered_index_args<
332 Arg1,Arg2,Arg3> index_args;
333 typedef typename index_args::tag_list_type::type tag_list_type;
334 typedef typename index_args::key_from_value_type key_from_value_type;
335 typedef typename index_args::compare_type compare_type;
337 template<typename Super>
340 typedef detail::ordered_index_node<detail::rank_policy,Super> type;
343 template<typename SuperMeta>
346 typedef detail::ordered_index<
347 key_from_value_type,compare_type,
348 SuperMeta,tag_list_type,detail::ordered_unique_tag,
349 detail::rank_policy> type;
353 template<typename Arg1,typename Arg2,typename Arg3>
354 struct ranked_non_unique
356 typedef detail::ordered_index_args<
357 Arg1,Arg2,Arg3> index_args;
358 typedef typename index_args::tag_list_type::type tag_list_type;
359 typedef typename index_args::key_from_value_type key_from_value_type;
360 typedef typename index_args::compare_type compare_type;
362 template<typename Super>
365 typedef detail::ordered_index_node<detail::rank_policy,Super> type;
368 template<typename SuperMeta>
371 typedef detail::ordered_index<
372 key_from_value_type,compare_type,
373 SuperMeta,tag_list_type,detail::ordered_non_unique_tag,
374 detail::rank_policy> type;
378 } /* namespace multi_index */
380 } /* namespace boost */