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