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) 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 std::size_t size; 33 }; 34 35 template<typename OrderedIndexImpl> 36 class ranked_index:public OrderedIndexImpl 37 { 38 typedef OrderedIndexImpl super; 39 40 protected: 41 typedef typename super::node_type node_type; 42 typedef typename super::node_impl_pointer node_impl_pointer; 43 44 public: 45 typedef typename super::ctor_args_list ctor_args_list; 46 typedef typename super::allocator_type allocator_type; 47 typedef typename super::iterator iterator; 48 49 /* rank operations */ 50 nth(std::size_t n) const51 iterator nth(std::size_t n)const 52 { 53 return this->make_iterator(node_type::from_impl( 54 ranked_index_nth(n,this->header()->impl()))); 55 } 56 rank(iterator position) const57 std::size_t rank(iterator position)const 58 { 59 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); 60 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); 61 62 return ranked_index_rank( 63 position.get_node()->impl(),this->header()->impl()); 64 } 65 66 template<typename CompatibleKey> find_rank(const CompatibleKey & x) const67 std::size_t find_rank(const CompatibleKey& x)const 68 { 69 return ranked_index_find_rank( 70 this->root(),this->header(),this->key,x,this->comp_); 71 } 72 73 template<typename CompatibleKey,typename CompatibleCompare> find_rank(const CompatibleKey & x,const CompatibleCompare & comp) const74 std::size_t find_rank( 75 const CompatibleKey& x,const CompatibleCompare& comp)const 76 { 77 return ranked_index_find_rank( 78 this->root(),this->header(),this->key,x,comp); 79 } 80 81 template<typename CompatibleKey> lower_bound_rank(const CompatibleKey & x) const82 std::size_t lower_bound_rank(const CompatibleKey& x)const 83 { 84 return ranked_index_lower_bound_rank( 85 this->root(),this->header(),this->key,x,this->comp_); 86 } 87 88 template<typename CompatibleKey,typename CompatibleCompare> lower_bound_rank(const CompatibleKey & x,const CompatibleCompare & comp) const89 std::size_t lower_bound_rank( 90 const CompatibleKey& x,const CompatibleCompare& comp)const 91 { 92 return ranked_index_lower_bound_rank( 93 this->root(),this->header(),this->key,x,comp); 94 } 95 96 template<typename CompatibleKey> upper_bound_rank(const CompatibleKey & x) const97 std::size_t upper_bound_rank(const CompatibleKey& x)const 98 { 99 return ranked_index_upper_bound_rank( 100 this->root(),this->header(),this->key,x,this->comp_); 101 } 102 103 template<typename CompatibleKey,typename CompatibleCompare> upper_bound_rank(const CompatibleKey & x,const CompatibleCompare & comp) const104 std::size_t upper_bound_rank( 105 const CompatibleKey& x,const CompatibleCompare& comp)const 106 { 107 return ranked_index_upper_bound_rank( 108 this->root(),this->header(),this->key,x,comp); 109 } 110 111 template<typename CompatibleKey> equal_range_rank(const CompatibleKey & x) const112 std::pair<std::size_t,std::size_t> equal_range_rank( 113 const CompatibleKey& x)const 114 { 115 return ranked_index_equal_range_rank( 116 this->root(),this->header(),this->key,x,this->comp_); 117 } 118 119 template<typename CompatibleKey,typename CompatibleCompare> equal_range_rank(const CompatibleKey & x,const CompatibleCompare & comp) const120 std::pair<std::size_t,std::size_t> equal_range_rank( 121 const CompatibleKey& x,const CompatibleCompare& comp)const 122 { 123 return ranked_index_equal_range_rank( 124 this->root(),this->header(),this->key,x,comp); 125 } 126 127 template<typename LowerBounder,typename UpperBounder> 128 std::pair<std::size_t,std::size_t> range_rank(LowerBounder lower,UpperBounder upper) const129 range_rank(LowerBounder lower,UpperBounder upper)const 130 { 131 typedef typename mpl::if_< 132 is_same<LowerBounder,unbounded_type>, 133 BOOST_DEDUCED_TYPENAME mpl::if_< 134 is_same<UpperBounder,unbounded_type>, 135 both_unbounded_tag, 136 lower_unbounded_tag 137 >::type, 138 BOOST_DEDUCED_TYPENAME mpl::if_< 139 is_same<UpperBounder,unbounded_type>, 140 upper_unbounded_tag, 141 none_unbounded_tag 142 >::type 143 >::type dispatch; 144 145 return range_rank(lower,upper,dispatch()); 146 } 147 148 protected: ranked_index(const ranked_index & x)149 ranked_index(const ranked_index& x):super(x){}; 150 ranked_index(const ranked_index & x,do_not_copy_elements_tag)151 ranked_index(const ranked_index& x,do_not_copy_elements_tag): 152 super(x,do_not_copy_elements_tag()){}; 153 ranked_index(const ctor_args_list & args_list,const allocator_type & al)154 ranked_index( 155 const ctor_args_list& args_list,const allocator_type& al): 156 super(args_list,al){} 157 158 private: 159 template<typename LowerBounder,typename UpperBounder> 160 std::pair<std::size_t,std::size_t> range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag) const161 range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const 162 { 163 node_type* y=this->header(); 164 node_type* z=this->root(); 165 166 if(!z)return std::pair<std::size_t,std::size_t>(0,0); 167 168 std::size_t s=z->size; 169 170 do{ 171 if(!lower(this->key(z->value()))){ 172 z=node_type::from_impl(z->right()); 173 } 174 else if(!upper(this->key(z->value()))){ 175 y=z; 176 s-=ranked_node_size(y->right())+1; 177 z=node_type::from_impl(z->left()); 178 } 179 else{ 180 return std::pair<std::size_t,std::size_t>( 181 s-z->size+ 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)); 185 } 186 }while(z); 187 188 return std::pair<std::size_t,std::size_t>(s,s); 189 } 190 191 template<typename LowerBounder,typename UpperBounder> 192 std::pair<std::size_t,std::size_t> range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag) const193 range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag)const 194 { 195 return std::pair<std::size_t,std::size_t>( 196 0, 197 upper_range_rank(this->root(),this->header(),upper)); 198 } 199 200 template<typename LowerBounder,typename UpperBounder> 201 std::pair<std::size_t,std::size_t> range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag) const202 range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag)const 203 { 204 return std::pair<std::size_t,std::size_t>( 205 lower_range_rank(this->root(),this->header(),lower), 206 this->size()); 207 } 208 209 template<typename LowerBounder,typename UpperBounder> 210 std::pair<std::size_t,std::size_t> range_rank(LowerBounder,UpperBounder,both_unbounded_tag) const211 range_rank(LowerBounder,UpperBounder,both_unbounded_tag)const 212 { 213 return std::pair<std::size_t,std::size_t>(0,this->size()); 214 } 215 216 template<typename LowerBounder> 217 std::size_t lower_range_rank(node_type * top,node_type * y,LowerBounder lower) const218 lower_range_rank(node_type* top,node_type* y,LowerBounder lower)const 219 { 220 if(!top)return 0; 221 222 std::size_t s=top->size; 223 224 do{ 225 if(lower(this->key(top->value()))){ 226 y=top; 227 s-=ranked_node_size(y->right())+1; 228 top=node_type::from_impl(top->left()); 229 } 230 else top=node_type::from_impl(top->right()); 231 }while(top); 232 233 return s; 234 } 235 236 template<typename UpperBounder> 237 std::size_t upper_range_rank(node_type * top,node_type * y,UpperBounder upper) const238 upper_range_rank(node_type* top,node_type* y,UpperBounder upper)const 239 { 240 if(!top)return 0; 241 242 std::size_t s=top->size; 243 244 do{ 245 if(!upper(this->key(top->value()))){ 246 y=top; 247 s-=ranked_node_size(y->right())+1; 248 top=node_type::from_impl(top->left()); 249 } 250 else top=node_type::from_impl(top->right()); 251 }while(top); 252 253 return s; 254 } 255 }; 256 257 /* augmenting policy for ordered_index */ 258 259 struct rank_policy 260 { 261 template<typename OrderedIndexNodeImpl> 262 struct augmented_node 263 { 264 typedef ranked_node<OrderedIndexNodeImpl> type; 265 }; 266 267 template<typename OrderedIndexImpl> 268 struct augmented_interface 269 { 270 typedef ranked_index<OrderedIndexImpl> type; 271 }; 272 273 /* algorihmic stuff */ 274 275 template<typename Pointer> addboost::multi_index::detail::rank_policy276 static void add(Pointer x,Pointer root) 277 { 278 x->size=1; 279 while(x!=root){ 280 x=x->parent(); 281 ++(x->size); 282 } 283 } 284 285 template<typename Pointer> removeboost::multi_index::detail::rank_policy286 static void remove(Pointer x,Pointer root) 287 { 288 while(x!=root){ 289 x=x->parent(); 290 --(x->size); 291 } 292 } 293 294 template<typename Pointer> copyboost::multi_index::detail::rank_policy295 static void copy(Pointer x,Pointer y) 296 { 297 y->size=x->size; 298 } 299 300 template<typename Pointer> rotate_leftboost::multi_index::detail::rank_policy301 static void rotate_left(Pointer x,Pointer y) /* in: x==y->left() */ 302 { 303 y->size=x->size; 304 x->size=ranked_node_size(x->left())+ranked_node_size(x->right())+1; 305 }; 306 307 template<typename Pointer> rotate_rightboost::multi_index::detail::rank_policy308 static void rotate_right(Pointer x,Pointer y) /* in: x==y->right() */ 309 { 310 rotate_left(x,y); 311 }; 312 313 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) 314 /* invariant stuff */ 315 316 template<typename Pointer> invariantboost::multi_index::detail::rank_policy317 static bool invariant(Pointer x) 318 { 319 return x->size==ranked_node_size(x->left())+ranked_node_size(x->right())+1; 320 } 321 #endif 322 }; 323 324 } /* namespace multi_index::detail */ 325 326 /* ranked_index specifiers */ 327 328 template<typename Arg1,typename Arg2,typename Arg3> 329 struct ranked_unique 330 { 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; 336 337 template<typename Super> 338 struct node_class 339 { 340 typedef detail::ordered_index_node<detail::rank_policy,Super> type; 341 }; 342 343 template<typename SuperMeta> 344 struct index_class 345 { 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; 350 }; 351 }; 352 353 template<typename Arg1,typename Arg2,typename Arg3> 354 struct ranked_non_unique 355 { 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; 361 362 template<typename Super> 363 struct node_class 364 { 365 typedef detail::ordered_index_node<detail::rank_policy,Super> type; 366 }; 367 368 template<typename SuperMeta> 369 struct index_class 370 { 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; 375 }; 376 }; 377 378 } /* namespace multi_index */ 379 380 } /* namespace boost */ 381 382 #endif 383