ceph/src/boost/libs/multi_index/include/boost/multi_index/ranked_index.hpp

   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
  51   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
  57   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>
  67   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>
  74   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>
  82   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>
  89   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>
  97   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>
 104   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>
 112   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>
 120   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>
 129   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:
 149   ranked_index(const ranked_index& x):super(x){};
 150
 151   ranked_index(const ranked_index& x,do_not_copy_elements_tag):
 152     super(x,do_not_copy_elements_tag()){};
 153
 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>
 161   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>
 193   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>
 202   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>
 211   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
 218   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
 238   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   /* algorithmic stuff */
 274
 275   template<typename Pointer>
 276   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>
 286   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>
 295   static void copy(Pointer x,Pointer y)
 296   {
 297     y->size=x->size;
 298   }
 299
 300   template<typename Pointer>
 301   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>
 308   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>
 317   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