ceph/src/boost/libs/multi_index/include/boost/multi_index/detail/rnk_index_ops.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_DETAIL_RNK_INDEX_OPS_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_RNK_INDEX_OPS_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/mpl/and.hpp>
  18 #include <boost/multi_index/detail/promotes_arg.hpp>
  19 #include <cstddef>
  20 #include <utility>
  21
  22 namespace boost{
  23
  24 namespace multi_index{
  25
  26 namespace detail{
  27
  28 /* Common code for ranked_index memfuns having templatized and
  29  * non-templatized versions.
  30  */
  31
  32 template<typename Pointer>
  33 inline std::size_t ranked_node_size(Pointer x)
  34 {
  35   return x!=Pointer(0)?x->size:0;
  36 }
  37
  38 template<typename Pointer>
  39 inline Pointer ranked_index_nth(std::size_t n,Pointer end_)
  40 {
  41   Pointer top=end_->parent();
  42   if(top==Pointer(0)||n>=top->size)return end_;
  43
  44   for(;;){
  45     std::size_t s=ranked_node_size(top->left());
  46     if(n==s)return top;
  47     if(n<s)top=top->left();
  48     else{
  49       top=top->right();
  50       n-=s+1;
  51     }
  52   }
  53 }
  54
  55 template<typename Pointer>
  56 inline std::size_t ranked_index_rank(Pointer x,Pointer end_)
  57 {
  58   Pointer top=end_->parent();
  59   if(top==Pointer(0))return 0;
  60   if(x==end_)return top->size;
  61
  62   std::size_t s=ranked_node_size(x->left());
  63   while(x!=top){
  64     Pointer z=x->parent();
  65     if(x==z->right()){
  66       s+=ranked_node_size(z->left())+1;
  67     }
  68     x=z;
  69   }
  70   return s;
  71 }
  72
  73 template<
  74   typename Node,typename KeyFromValue,
  75   typename CompatibleKey,typename CompatibleCompare
  76 >
  77 inline std::size_t ranked_index_find_rank(
  78   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  79   const CompatibleCompare& comp)
  80 {
  81   typedef typename KeyFromValue::result_type key_type;
  82
  83   return ranked_index_find_rank(
  84     top,y,key,x,comp,
  85     mpl::and_<
  86       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
  87       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
  88 }
  89
  90 template<
  91   typename Node,typename KeyFromValue,
  92   typename CompatibleCompare
  93 >
  94 inline std::size_t ranked_index_find_rank(
  95   Node* top,Node* y,const KeyFromValue& key,
  96   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
  97   const CompatibleCompare& comp,mpl::true_)
  98 {
  99   return ranked_index_find_rank(top,y,key,x,comp,mpl::false_());
 100 }
 101
 102 template<
 103   typename Node,typename KeyFromValue,
 104   typename CompatibleKey,typename CompatibleCompare
 105 >
 106 inline std::size_t ranked_index_find_rank(
 107   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 108   const CompatibleCompare& comp,mpl::false_)
 109 {
 110   if(!top)return 0;
 111
 112   std::size_t s=top->size,
 113               s0=s;
 114   Node*       y0=y;
 115
 116   do{
 117     if(!comp(key(top->value()),x)){
 118       y=top;
 119       s-=ranked_node_size(y->right())+1;
 120       top=Node::from_impl(top->left());
 121     }
 122     else top=Node::from_impl(top->right());
 123   }while(top);
 124
 125   return (y==y0||comp(x,key(y->value())))?s0:s;
 126 }
 127
 128 template<
 129   typename Node,typename KeyFromValue,
 130   typename CompatibleKey,typename CompatibleCompare
 131 >
 132 inline std::size_t ranked_index_lower_bound_rank(
 133   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 134   const CompatibleCompare& comp)
 135 {
 136   typedef typename KeyFromValue::result_type key_type;
 137
 138   return ranked_index_lower_bound_rank(
 139     top,y,key,x,comp,
 140     promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
 141 }
 142
 143 template<
 144   typename Node,typename KeyFromValue,
 145   typename CompatibleCompare
 146 >
 147 inline std::size_t ranked_index_lower_bound_rank(
 148   Node* top,Node* y,const KeyFromValue& key,
 149   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
 150   const CompatibleCompare& comp,mpl::true_)
 151 {
 152   return ranked_index_lower_bound_rank(top,y,key,x,comp,mpl::false_());
 153 }
 154
 155 template<
 156   typename Node,typename KeyFromValue,
 157   typename CompatibleKey,typename CompatibleCompare
 158 >
 159 inline std::size_t ranked_index_lower_bound_rank(
 160   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 161   const CompatibleCompare& comp,mpl::false_)
 162 {
 163   if(!top)return 0;
 164
 165   std::size_t s=top->size;
 166
 167   do{
 168     if(!comp(key(top->value()),x)){
 169       y=top;
 170       s-=ranked_node_size(y->right())+1;
 171       top=Node::from_impl(top->left());
 172     }
 173     else top=Node::from_impl(top->right());
 174   }while(top);
 175
 176   return s;
 177 }
 178
 179 template<
 180   typename Node,typename KeyFromValue,
 181   typename CompatibleKey,typename CompatibleCompare
 182 >
 183 inline std::size_t ranked_index_upper_bound_rank(
 184   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 185   const CompatibleCompare& comp)
 186 {
 187   typedef typename KeyFromValue::result_type key_type;
 188
 189   return ranked_index_upper_bound_rank(
 190     top,y,key,x,comp,
 191     promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
 192 }
 193
 194 template<
 195   typename Node,typename KeyFromValue,
 196   typename CompatibleCompare
 197 >
 198 inline std::size_t ranked_index_upper_bound_rank(
 199   Node* top,Node* y,const KeyFromValue& key,
 200   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
 201   const CompatibleCompare& comp,mpl::true_)
 202 {
 203   return ranked_index_upper_bound_rank(top,y,key,x,comp,mpl::false_());
 204 }
 205
 206 template<
 207   typename Node,typename KeyFromValue,
 208   typename CompatibleKey,typename CompatibleCompare
 209 >
 210 inline std::size_t ranked_index_upper_bound_rank(
 211   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 212   const CompatibleCompare& comp,mpl::false_)
 213 {
 214   if(!top)return 0;
 215
 216   std::size_t s=top->size;
 217
 218   do{
 219     if(comp(x,key(top->value()))){
 220       y=top;
 221       s-=ranked_node_size(y->right())+1;
 222       top=Node::from_impl(top->left());
 223     }
 224     else top=Node::from_impl(top->right());
 225   }while(top);
 226
 227   return s;
 228 }
 229
 230 template<
 231   typename Node,typename KeyFromValue,
 232   typename CompatibleKey,typename CompatibleCompare
 233 >
 234 inline std::pair<std::size_t,std::size_t> ranked_index_equal_range_rank(
 235   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 236   const CompatibleCompare& comp)
 237 {
 238   typedef typename KeyFromValue::result_type key_type;
 239
 240   return ranked_index_equal_range_rank(
 241     top,y,key,x,comp,
 242     mpl::and_<
 243       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
 244       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
 245 }
 246
 247 template<
 248   typename Node,typename KeyFromValue,
 249   typename CompatibleCompare
 250 >
 251 inline std::pair<std::size_t,std::size_t> ranked_index_equal_range_rank(
 252   Node* top,Node* y,const KeyFromValue& key,
 253   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
 254   const CompatibleCompare& comp,mpl::true_)
 255 {
 256   return ranked_index_equal_range_rank(top,y,key,x,comp,mpl::false_());
 257 }
 258
 259 template<
 260   typename Node,typename KeyFromValue,
 261   typename CompatibleKey,typename CompatibleCompare
 262 >
 263 inline std::pair<std::size_t,std::size_t> ranked_index_equal_range_rank(
 264   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
 265   const CompatibleCompare& comp,mpl::false_)
 266 {
 267   if(!top)return std::pair<std::size_t,std::size_t>(0,0);
 268
 269   std::size_t s=top->size;
 270
 271   do{
 272     if(comp(key(top->value()),x)){
 273       top=Node::from_impl(top->right());
 274     }
 275     else if(comp(x,key(top->value()))){
 276       y=top;
 277       s-=ranked_node_size(y->right())+1;
 278       top=Node::from_impl(top->left());
 279     }
 280     else{
 281       return std::pair<std::size_t,std::size_t>(
 282         s-top->size+
 283           ranked_index_lower_bound_rank(
 284            Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
 285         s-ranked_node_size(top->right())+
 286           ranked_index_upper_bound_rank(
 287             Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
 288     }
 289   }while(top);
 290
 291   return std::pair<std::size_t,std::size_t>(s,s);
 292 }
 293
 294 } /* namespace multi_index::detail */
 295
 296 } /* namespace multi_index */
 297
 298 } /* namespace boost */
 299
 300 #endif