boost/multi_index/ranked_index.hpp

0001 /* Copyright 2003-2022 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_RANKED_INDEX_HPP
0010 #define BOOST_MULTI_INDEX_RANKED_INDEX_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/multi_index/detail/ord_index_impl.hpp>
0018 #include <boost/multi_index/detail/rnk_index_ops.hpp>
0019 #include <boost/multi_index/ranked_index_fwd.hpp>
0020
0021 namespace boost{
0022
0023 namespace multi_index{
0024
0025 namespace detail{
0026
0027 /* ranked_index augments a given ordered index to provide rank operations */
0028
0029 template<typename OrderedIndexNodeImpl>
0030 struct ranked_node:OrderedIndexNodeImpl
0031 {
0032   typedef typename OrderedIndexNodeImpl::size_type size_type;
0033
0034   size_type size;
0035 };
0036
0037 template<typename OrderedIndexImpl>
0038 class ranked_index:public OrderedIndexImpl
0039 {
0040   typedef          OrderedIndexImpl         super;
0041
0042 protected:
0043   typedef typename super::index_node_type   index_node_type;
0044   typedef typename super::node_impl_pointer node_impl_pointer;
0045
0046 public:
0047   typedef typename super::ctor_args_list ctor_args_list;
0048   typedef typename super::allocator_type allocator_type;
0049   typedef typename super::iterator       iterator;
0050   typedef typename super::size_type      size_type;
0051
0052   /* set operations */
0053
0054   template<typename CompatibleKey>
0055   size_type count(const CompatibleKey& x)const
0056   {
0057     return count(x,this->comp_);
0058   }
0059
0060   template<typename CompatibleKey,typename CompatibleCompare>
0061   size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
0062   {
0063     std::pair<size_type,size_type> p=this->equal_range_rank(x,comp);
0064     return p.second-p.first;
0065   }
0066
0067   /* rank operations */
0068
0069   iterator nth(size_type n)const
0070   {
0071     return this->make_iterator(index_node_type::from_impl(
0072       ranked_index_nth(n,this->header()->impl())));
0073   }
0074
0075   size_type rank(iterator position)const
0076   {
0077     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
0078     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
0079
0080     return ranked_index_rank(
0081       position.get_node()->impl(),this->header()->impl());
0082   }
0083
0084   template<typename CompatibleKey>
0085   size_type find_rank(const CompatibleKey& x)const
0086   {
0087     return ranked_index_find_rank(
0088       this->root(),this->header(),this->key,x,this->comp_);
0089   }
0090
0091   template<typename CompatibleKey,typename CompatibleCompare>
0092   size_type find_rank(
0093     const CompatibleKey& x,const CompatibleCompare& comp)const
0094   {
0095     return ranked_index_find_rank(
0096       this->root(),this->header(),this->key,x,comp);
0097   }
0098
0099   template<typename CompatibleKey>
0100   size_type lower_bound_rank(const CompatibleKey& x)const
0101   {
0102     return ranked_index_lower_bound_rank(
0103       this->root(),this->header(),this->key,x,this->comp_);
0104   }
0105
0106   template<typename CompatibleKey,typename CompatibleCompare>
0107   size_type lower_bound_rank(
0108     const CompatibleKey& x,const CompatibleCompare& comp)const
0109   {
0110     return ranked_index_lower_bound_rank(
0111       this->root(),this->header(),this->key,x,comp);
0112   }
0113
0114   template<typename CompatibleKey>
0115   size_type upper_bound_rank(const CompatibleKey& x)const
0116   {
0117     return ranked_index_upper_bound_rank(
0118       this->root(),this->header(),this->key,x,this->comp_);
0119   }
0120
0121   template<typename CompatibleKey,typename CompatibleCompare>
0122   size_type upper_bound_rank(
0123     const CompatibleKey& x,const CompatibleCompare& comp)const
0124   {
0125     return ranked_index_upper_bound_rank(
0126       this->root(),this->header(),this->key,x,comp);
0127   }
0128
0129   template<typename CompatibleKey>
0130   std::pair<size_type,size_type> equal_range_rank(
0131     const CompatibleKey& x)const
0132   {
0133     return ranked_index_equal_range_rank(
0134       this->root(),this->header(),this->key,x,this->comp_);
0135   }
0136
0137   template<typename CompatibleKey,typename CompatibleCompare>
0138   std::pair<size_type,size_type> equal_range_rank(
0139     const CompatibleKey& x,const CompatibleCompare& comp)const
0140   {
0141     return ranked_index_equal_range_rank(
0142       this->root(),this->header(),this->key,x,comp);
0143   }
0144
0145   template<typename LowerBounder,typename UpperBounder>
0146   std::pair<size_type,size_type>
0147   range_rank(LowerBounder lower,UpperBounder upper)const
0148   {
0149     typedef typename mpl::if_<
0150       is_same<LowerBounder,unbounded_type>,
0151       BOOST_DEDUCED_TYPENAME mpl::if_<
0152         is_same<UpperBounder,unbounded_type>,
0153         both_unbounded_tag,
0154         lower_unbounded_tag
0155       >::type,
0156       BOOST_DEDUCED_TYPENAME mpl::if_<
0157         is_same<UpperBounder,unbounded_type>,
0158         upper_unbounded_tag,
0159         none_unbounded_tag
0160       >::type
0161     >::type dispatch;
0162
0163     return range_rank(lower,upper,dispatch());
0164   }
0165
0166 protected:
0167   ranked_index(const ranked_index& x):super(x){};
0168
0169   ranked_index(const ranked_index& x,do_not_copy_elements_tag):
0170     super(x,do_not_copy_elements_tag()){};
0171
0172   ranked_index(
0173     const ctor_args_list& args_list,const allocator_type& al):
0174     super(args_list,al){}
0175
0176 private:
0177   template<typename LowerBounder,typename UpperBounder>
0178   std::pair<size_type,size_type>
0179   range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
0180   {
0181     index_node_type* y=this->header();
0182     index_node_type* z=this->root();
0183
0184     if(!z)return std::pair<size_type,size_type>(0,0);
0185
0186     size_type s=z->impl()->size;
0187
0188     do{
0189       if(!lower(this->key(z->value()))){
0190         z=index_node_type::from_impl(z->right());
0191       }
0192       else if(!upper(this->key(z->value()))){
0193         y=z;
0194         s-=ranked_node_size(y->right())+1;
0195         z=index_node_type::from_impl(z->left());
0196       }
0197       else{
0198         return std::pair<size_type,size_type>(
0199           s-z->impl()->size+
0200             lower_range_rank(index_node_type::from_impl(z->left()),z,lower),
0201           s-ranked_node_size(z->right())+
0202             upper_range_rank(index_node_type::from_impl(z->right()),y,upper));
0203       }
0204     }while(z);
0205
0206     return std::pair<size_type,size_type>(s,s);
0207   }
0208
0209   template<typename LowerBounder,typename UpperBounder>
0210   std::pair<size_type,size_type>
0211   range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
0212   {
0213     return std::pair<size_type,size_type>(
0214       0,
0215       upper_range_rank(this->root(),this->header(),upper));
0216   }
0217
0218   template<typename LowerBounder,typename UpperBounder>
0219   std::pair<size_type,size_type>
0220   range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
0221   {
0222     return std::pair<size_type,size_type>(
0223       lower_range_rank(this->root(),this->header(),lower),
0224       this->size());
0225   }
0226
0227   template<typename LowerBounder,typename UpperBounder>
0228   std::pair<size_type,size_type>
0229   range_rank(LowerBounder,UpperBounder,both_unbounded_tag)const
0230   {
0231     return std::pair<size_type,size_type>(0,this->size());
0232   }
0233
0234   template<typename LowerBounder>
0235   size_type
0236   lower_range_rank(
0237     index_node_type* top,index_node_type* y,LowerBounder lower)const
0238   {
0239     if(!top)return 0;
0240
0241     size_type s=top->impl()->size;
0242
0243     do{
0244       if(lower(this->key(top->value()))){
0245         y=top;
0246         s-=ranked_node_size(y->right())+1;
0247         top=index_node_type::from_impl(top->left());
0248       }
0249       else top=index_node_type::from_impl(top->right());
0250     }while(top);
0251
0252     return s;
0253   }
0254
0255   template<typename UpperBounder>
0256   size_type
0257   upper_range_rank(
0258     index_node_type* top,index_node_type* y,UpperBounder upper)const
0259   {
0260     if(!top)return 0;
0261
0262     size_type s=top->impl()->size;
0263
0264     do{
0265       if(!upper(this->key(top->value()))){
0266         y=top;
0267         s-=ranked_node_size(y->right())+1;
0268         top=index_node_type::from_impl(top->left());
0269       }
0270       else top=index_node_type::from_impl(top->right());
0271     }while(top);
0272
0273     return s;
0274   }
0275 };
0276
0277 /* augmenting policy for ordered_index */
0278
0279 struct rank_policy
0280 {
0281   template<typename OrderedIndexNodeImpl>
0282   struct augmented_node
0283   {
0284     typedef ranked_node<OrderedIndexNodeImpl> type;
0285   };
0286
0287   template<typename OrderedIndexImpl>
0288   struct augmented_interface
0289   {
0290     typedef ranked_index<OrderedIndexImpl> type;
0291   };
0292
0293   /* algorithmic stuff */
0294
0295   template<typename Pointer>
0296   static void add(Pointer x,Pointer root)
0297   {
0298     x->size=1;
0299     while(x!=root){
0300       x=x->parent();
0301       ++(x->size);
0302     }
0303   }
0304
0305   template<typename Pointer>
0306   static void remove(Pointer x,Pointer root)
0307   {
0308     while(x!=root){
0309       x=x->parent();
0310       --(x->size);
0311     }
0312   }
0313
0314   template<typename Pointer>
0315   static void copy(Pointer x,Pointer y)
0316   {
0317     y->size=x->size;
0318   }
0319
0320   template<typename Pointer>
0321   static void rotate_left(Pointer x,Pointer y) /* in: x==y->left() */
0322   {
0323     y->size=x->size;
0324     x->size=ranked_node_size(x->left())+ranked_node_size(x->right())+1;
0325   }
0326
0327   template<typename Pointer>
0328   static void rotate_right(Pointer x,Pointer y) /* in: x==y->right() */
0329   {
0330     rotate_left(x,y);
0331   }
0332
0333 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
0334   /* invariant stuff */
0335
0336   template<typename Pointer>
0337   static bool invariant(Pointer x)
0338   {
0339     return x->size==ranked_node_size(x->left())+ranked_node_size(x->right())+1;
0340   }
0341 #endif
0342 };
0343
0344 } /* namespace multi_index::detail */
0345
0346 /* ranked_index specifiers */
0347
0348 template<typename Arg1,typename Arg2,typename Arg3>
0349 struct ranked_unique
0350 {
0351   typedef typename detail::ordered_index_args<
0352     Arg1,Arg2,Arg3>                                index_args;
0353   typedef typename index_args::tag_list_type::type tag_list_type;
0354   typedef typename index_args::key_from_value_type key_from_value_type;
0355   typedef typename index_args::compare_type        compare_type;
0356
0357   template<typename Super>
0358   struct node_class
0359   {
0360     typedef detail::ordered_index_node<detail::rank_policy,Super> type;
0361   };
0362
0363   template<typename SuperMeta>
0364   struct index_class
0365   {
0366     typedef detail::ordered_index<
0367       key_from_value_type,compare_type,
0368       SuperMeta,tag_list_type,detail::ordered_unique_tag,
0369       detail::rank_policy>                                type;
0370   };
0371 };
0372
0373 template<typename Arg1,typename Arg2,typename Arg3>
0374 struct ranked_non_unique
0375 {
0376   typedef detail::ordered_index_args<
0377     Arg1,Arg2,Arg3>                                index_args;
0378   typedef typename index_args::tag_list_type::type tag_list_type;
0379   typedef typename index_args::key_from_value_type key_from_value_type;
0380   typedef typename index_args::compare_type        compare_type;
0381
0382   template<typename Super>
0383   struct node_class
0384   {
0385     typedef detail::ordered_index_node<detail::rank_policy,Super> type;
0386   };
0387
0388   template<typename SuperMeta>
0389   struct index_class
0390   {
0391     typedef detail::ordered_index<
0392       key_from_value_type,compare_type,
0393       SuperMeta,tag_list_type,detail::ordered_non_unique_tag,
0394       detail::rank_policy>                                    type;
0395   };
0396 };
0397
0398 } /* namespace multi_index */
0399
0400 } /* namespace boost */
0401
0402 #endif