multi_index/detail/rnk_index_ops.hpp

0001 /* Copyright 2003-2018 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_RNK_INDEX_OPS_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_RNK_INDEX_OPS_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <boost/core/pointer_traits.hpp>
0018 #include <boost/mpl/and.hpp>
0019 #include <boost/multi_index/detail/promotes_arg.hpp>
0020 #include <utility>
0021
0022 namespace boost{
0023
0024 namespace multi_index{
0025
0026 namespace detail{
0027
0028 /* Common code for ranked_index memfuns having templatized and
0029  * non-templatized versions.
0030  */
0031
0032 template<typename Pointer>
0033 struct ranked_node_size_type
0034 {
0035   typedef typename boost::pointer_traits<Pointer>::
0036     element_type::size_type type;
0037 };
0038
0039 template<typename Pointer>
0040 inline typename ranked_node_size_type<Pointer>::type
0041 ranked_node_size(Pointer x)
0042 {
0043   return x!=Pointer(0)?x->size:0;
0044 }
0045
0046 template<typename Pointer>
0047 inline Pointer ranked_index_nth(
0048   BOOST_DEDUCED_TYPENAME ranked_node_size_type<Pointer>::type n,Pointer end_)
0049 {
0050   typedef typename ranked_node_size_type<Pointer>::type size_type;
0051
0052   Pointer top=end_->parent();
0053   if(top==Pointer(0)||n>=top->size)return end_;
0054
0055   for(;;){
0056     size_type s=ranked_node_size(top->left());
0057     if(n==s)return top;
0058     if(n<s)top=top->left();
0059     else{
0060       top=top->right();
0061       n-=s+1;
0062     }
0063   }
0064 }
0065
0066 template<typename Pointer>
0067 inline typename ranked_node_size_type<Pointer>::type
0068 ranked_index_rank(Pointer x,Pointer end_)
0069 {
0070   typedef typename ranked_node_size_type<Pointer>::type size_type;
0071
0072   Pointer top=end_->parent();
0073   if(top==Pointer(0))return 0;
0074   if(x==end_)return top->size;
0075
0076   size_type s=ranked_node_size(x->left());
0077   while(x!=top){
0078     Pointer z=x->parent();
0079     if(x==z->right()){
0080       s+=ranked_node_size(z->left())+1;
0081     }
0082     x=z;
0083   }
0084   return s;
0085 }
0086
0087 template<
0088   typename Node,typename KeyFromValue,
0089   typename CompatibleKey,typename CompatibleCompare
0090 >
0091 inline typename Node::size_type ranked_index_find_rank(
0092   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0093   const CompatibleCompare& comp)
0094 {
0095   typedef typename KeyFromValue::result_type key_type;
0096
0097   return ranked_index_find_rank(
0098     top,y,key,x,comp,
0099     mpl::and_<
0100       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
0101       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
0102 }
0103
0104 template<
0105   typename Node,typename KeyFromValue,
0106   typename CompatibleCompare
0107 >
0108 inline typename Node::size_type ranked_index_find_rank(
0109   Node* top,Node* y,const KeyFromValue& key,
0110   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0111   const CompatibleCompare& comp,mpl::true_)
0112 {
0113   return ranked_index_find_rank(top,y,key,x,comp,mpl::false_());
0114 }
0115
0116 template<
0117   typename Node,typename KeyFromValue,
0118   typename CompatibleKey,typename CompatibleCompare
0119 >
0120 inline typename Node::size_type ranked_index_find_rank(
0121   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0122   const CompatibleCompare& comp,mpl::false_)
0123 {
0124   typedef typename Node::size_type size_type;
0125
0126   if(!top)return 0;
0127
0128   size_type s=top->impl()->size,
0129             s0=s;
0130   Node*     y0=y;
0131
0132   do{
0133     if(!comp(key(top->value()),x)){
0134       y=top;
0135       s-=ranked_node_size(y->right())+1;
0136       top=Node::from_impl(top->left());
0137     }
0138     else top=Node::from_impl(top->right());
0139   }while(top);
0140
0141   return (y==y0||comp(x,key(y->value())))?s0:s;
0142 }
0143
0144 template<
0145   typename Node,typename KeyFromValue,
0146   typename CompatibleKey,typename CompatibleCompare
0147 >
0148 inline typename Node::size_type ranked_index_lower_bound_rank(
0149   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0150   const CompatibleCompare& comp)
0151 {
0152   typedef typename KeyFromValue::result_type key_type;
0153
0154   return ranked_index_lower_bound_rank(
0155     top,y,key,x,comp,
0156     promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
0157 }
0158
0159 template<
0160   typename Node,typename KeyFromValue,
0161   typename CompatibleCompare
0162 >
0163 inline typename Node::size_type ranked_index_lower_bound_rank(
0164   Node* top,Node* y,const KeyFromValue& key,
0165   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0166   const CompatibleCompare& comp,mpl::true_)
0167 {
0168   return ranked_index_lower_bound_rank(top,y,key,x,comp,mpl::false_());
0169 }
0170
0171 template<
0172   typename Node,typename KeyFromValue,
0173   typename CompatibleKey,typename CompatibleCompare
0174 >
0175 inline typename Node::size_type ranked_index_lower_bound_rank(
0176   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0177   const CompatibleCompare& comp,mpl::false_)
0178 {
0179   typedef typename Node::size_type size_type;
0180
0181   if(!top)return 0;
0182
0183   size_type s=top->impl()->size;
0184
0185   do{
0186     if(!comp(key(top->value()),x)){
0187       y=top;
0188       s-=ranked_node_size(y->right())+1;
0189       top=Node::from_impl(top->left());
0190     }
0191     else top=Node::from_impl(top->right());
0192   }while(top);
0193
0194   return s;
0195 }
0196
0197 template<
0198   typename Node,typename KeyFromValue,
0199   typename CompatibleKey,typename CompatibleCompare
0200 >
0201 inline typename Node::size_type ranked_index_upper_bound_rank(
0202   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0203   const CompatibleCompare& comp)
0204 {
0205   typedef typename KeyFromValue::result_type key_type;
0206
0207   return ranked_index_upper_bound_rank(
0208     top,y,key,x,comp,
0209     promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
0210 }
0211
0212 template<
0213   typename Node,typename KeyFromValue,
0214   typename CompatibleCompare
0215 >
0216 inline typename Node::size_type ranked_index_upper_bound_rank(
0217   Node* top,Node* y,const KeyFromValue& key,
0218   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0219   const CompatibleCompare& comp,mpl::true_)
0220 {
0221   return ranked_index_upper_bound_rank(top,y,key,x,comp,mpl::false_());
0222 }
0223
0224 template<
0225   typename Node,typename KeyFromValue,
0226   typename CompatibleKey,typename CompatibleCompare
0227 >
0228 inline typename Node::size_type ranked_index_upper_bound_rank(
0229   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0230   const CompatibleCompare& comp,mpl::false_)
0231 {
0232   typedef typename Node::size_type size_type;
0233
0234   if(!top)return 0;
0235
0236   size_type s=top->impl()->size;
0237
0238   do{
0239     if(comp(x,key(top->value()))){
0240       y=top;
0241       s-=ranked_node_size(y->right())+1;
0242       top=Node::from_impl(top->left());
0243     }
0244     else top=Node::from_impl(top->right());
0245   }while(top);
0246
0247   return s;
0248 }
0249
0250 template<
0251   typename Node,typename KeyFromValue,
0252   typename CompatibleKey,typename CompatibleCompare
0253 >
0254 inline std::pair<typename Node::size_type,typename Node::size_type>
0255 ranked_index_equal_range_rank(
0256   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0257   const CompatibleCompare& comp)
0258 {
0259   typedef typename KeyFromValue::result_type key_type;
0260
0261   return ranked_index_equal_range_rank(
0262     top,y,key,x,comp,
0263     mpl::and_<
0264       promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
0265       promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
0266 }
0267
0268 template<
0269   typename Node,typename KeyFromValue,
0270   typename CompatibleCompare
0271 >
0272 inline std::pair<typename Node::size_type,typename Node::size_type>
0273 ranked_index_equal_range_rank(
0274   Node* top,Node* y,const KeyFromValue& key,
0275   const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
0276   const CompatibleCompare& comp,mpl::true_)
0277 {
0278   return ranked_index_equal_range_rank(top,y,key,x,comp,mpl::false_());
0279 }
0280
0281 template<
0282   typename Node,typename KeyFromValue,
0283   typename CompatibleKey,typename CompatibleCompare
0284 >
0285 inline std::pair<typename Node::size_type,typename Node::size_type>
0286 ranked_index_equal_range_rank(
0287   Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
0288   const CompatibleCompare& comp,mpl::false_)
0289 {
0290   typedef typename Node::size_type size_type;
0291
0292   if(!top)return std::pair<size_type,size_type>(0,0);
0293
0294   size_type s=top->impl()->size;
0295
0296   do{
0297     if(comp(key(top->value()),x)){
0298       top=Node::from_impl(top->right());
0299     }
0300     else if(comp(x,key(top->value()))){
0301       y=top;
0302       s-=ranked_node_size(y->right())+1;
0303       top=Node::from_impl(top->left());
0304     }
0305     else{
0306       return std::pair<size_type,size_type>(
0307         s-top->impl()->size+
0308           ranked_index_lower_bound_rank(
0309            Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
0310         s-ranked_node_size(top->right())+
0311           ranked_index_upper_bound_rank(
0312             Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
0313     }
0314   }while(top);
0315
0316   return std::pair<size_type,size_type>(s,s);
0317 }
0318
0319 } /* namespace multi_index::detail */
0320
0321 } /* namespace multi_index */
0322
0323 } /* namespace boost */
0324
0325 #endif