boost/multi_index/ranked_index.hpp
/* Copyright 2003-2022 Joaquin M Lopez Munoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*
* See http://www.boost.org/libs/multi_index for library home page.
*/
#ifndef BOOST_MULTI_INDEX_RANKED_INDEX_HPP
#define BOOST_MULTI_INDEX_RANKED_INDEX_HPP
#if defined(_MSC_VER)
#pragma once
#endif
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/multi_index/detail/ord_index_impl.hpp>
#include <boost/multi_index/detail/rnk_index_ops.hpp>
#include <boost/multi_index/ranked_index_fwd.hpp>
namespace boost{
namespace multi_index{
namespace detail{
/* ranked_index augments a given ordered index to provide rank operations */
template<typename OrderedIndexNodeImpl>
struct ranked_node:OrderedIndexNodeImpl
{
typedef typename OrderedIndexNodeImpl::size_type size_type;
size_type size;
};
template<typename OrderedIndexImpl>
class ranked_index:public OrderedIndexImpl
{
typedef OrderedIndexImpl super;
protected:
typedef typename super::index_node_type index_node_type;
typedef typename super::node_impl_pointer node_impl_pointer;
public:
typedef typename super::ctor_args_list ctor_args_list;
typedef typename super::allocator_type allocator_type;
typedef typename super::iterator iterator;
typedef typename super::size_type size_type;
/* set operations */
template<typename CompatibleKey>
size_type count(const CompatibleKey& x)const
{
return count(x,this->comp_);
}
template<typename CompatibleKey,typename CompatibleCompare>
size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
{
std::pair<size_type,size_type> p=this->equal_range_rank(x,comp);
return p.second-p.first;
}
/* rank operations */
iterator nth(size_type n)const
{
return this->make_iterator(index_node_type::from_impl(
ranked_index_nth(n,this->header()->impl())));
}
size_type rank(iterator position)const
{
BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
return ranked_index_rank(
position.get_node()->impl(),this->header()->impl());
}
template<typename CompatibleKey>
size_type find_rank(const CompatibleKey& x)const
{
return ranked_index_find_rank(
this->root(),this->header(),this->key,x,this->comp_);
}
template<typename CompatibleKey,typename CompatibleCompare>
size_type find_rank(
const CompatibleKey& x,const CompatibleCompare& comp)const
{
return ranked_index_find_rank(
this->root(),this->header(),this->key,x,comp);
}
template<typename CompatibleKey>
size_type lower_bound_rank(const CompatibleKey& x)const
{
return ranked_index_lower_bound_rank(
this->root(),this->header(),this->key,x,this->comp_);
}
template<typename CompatibleKey,typename CompatibleCompare>
size_type lower_bound_rank(
const CompatibleKey& x,const CompatibleCompare& comp)const
{
return ranked_index_lower_bound_rank(
this->root(),this->header(),this->key,x,comp);
}
template<typename CompatibleKey>
size_type upper_bound_rank(const CompatibleKey& x)const
{
return ranked_index_upper_bound_rank(
this->root(),this->header(),this->key,x,this->comp_);
}
template<typename CompatibleKey,typename CompatibleCompare>
size_type upper_bound_rank(
const CompatibleKey& x,const CompatibleCompare& comp)const
{
return ranked_index_upper_bound_rank(
this->root(),this->header(),this->key,x,comp);
}
template<typename CompatibleKey>
std::pair<size_type,size_type> equal_range_rank(
const CompatibleKey& x)const
{
return ranked_index_equal_range_rank(
this->root(),this->header(),this->key,x,this->comp_);
}
template<typename CompatibleKey,typename CompatibleCompare>
std::pair<size_type,size_type> equal_range_rank(
const CompatibleKey& x,const CompatibleCompare& comp)const
{
return ranked_index_equal_range_rank(
this->root(),this->header(),this->key,x,comp);
}
template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type>
range_rank(LowerBounder lower,UpperBounder upper)const
{
typedef typename mpl::if_<
is_same<LowerBounder,unbounded_type>,
BOOST_DEDUCED_TYPENAME mpl::if_<
is_same<UpperBounder,unbounded_type>,
both_unbounded_tag,
lower_unbounded_tag
>::type,
BOOST_DEDUCED_TYPENAME mpl::if_<
is_same<UpperBounder,unbounded_type>,
upper_unbounded_tag,
none_unbounded_tag
>::type
>::type dispatch;
return range_rank(lower,upper,dispatch());
}
protected:
ranked_index(const ranked_index& x):super(x){};
ranked_index(const ranked_index& x,do_not_copy_elements_tag):
super(x,do_not_copy_elements_tag()){};
ranked_index(
const ctor_args_list& args_list,const allocator_type& al):
super(args_list,al){}
private:
template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type>
range_rank(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const
{
index_node_type* y=this->header();
index_node_type* z=this->root();
if(!z)return std::pair<size_type,size_type>(0,0);
size_type s=z->impl()->size;
do{
if(!lower(this->key(z->value()))){
z=index_node_type::from_impl(z->right());
}
else if(!upper(this->key(z->value()))){
y=z;
s-=ranked_node_size(y->right())+1;
z=index_node_type::from_impl(z->left());
}
else{
return std::pair<size_type,size_type>(
s-z->impl()->size+
lower_range_rank(index_node_type::from_impl(z->left()),z,lower),
s-ranked_node_size(z->right())+
upper_range_rank(index_node_type::from_impl(z->right()),y,upper));
}
}while(z);
return std::pair<size_type,size_type>(s,s);
}
template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type>
range_rank(LowerBounder,UpperBounder upper,lower_unbounded_tag)const
{
return std::pair<size_type,size_type>(
0,
upper_range_rank(this->root(),this->header(),upper));
}
template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type>
range_rank(LowerBounder lower,UpperBounder,upper_unbounded_tag)const
{
return std::pair<size_type,size_type>(
lower_range_rank(this->root(),this->header(),lower),
this->size());
}
template<typename LowerBounder,typename UpperBounder>
std::pair<size_type,size_type>
range_rank(LowerBounder,UpperBounder,both_unbounded_tag)const
{
return std::pair<size_type,size_type>(0,this->size());
}
template<typename LowerBounder>
size_type
lower_range_rank(
index_node_type* top,index_node_type* y,LowerBounder lower)const
{
if(!top)return 0;
size_type s=top->impl()->size;
do{
if(lower(this->key(top->value()))){
y=top;
s-=ranked_node_size(y->right())+1;
top=index_node_type::from_impl(top->left());
}
else top=index_node_type::from_impl(top->right());
}while(top);
return s;
}
template<typename UpperBounder>
size_type
upper_range_rank(
index_node_type* top,index_node_type* y,UpperBounder upper)const
{
if(!top)return 0;
size_type s=top->impl()->size;
do{
if(!upper(this->key(top->value()))){
y=top;
s-=ranked_node_size(y->right())+1;
top=index_node_type::from_impl(top->left());
}
else top=index_node_type::from_impl(top->right());
}while(top);
return s;
}
};
/* augmenting policy for ordered_index */
struct rank_policy
{
template<typename OrderedIndexNodeImpl>
struct augmented_node
{
typedef ranked_node<OrderedIndexNodeImpl> type;
};
template<typename OrderedIndexImpl>
struct augmented_interface
{
typedef ranked_index<OrderedIndexImpl> type;
};
/* algorithmic stuff */
template<typename Pointer>
static void add(Pointer x,Pointer root)
{
x->size=1;
while(x!=root){
x=x->parent();
++(x->size);
}
}
template<typename Pointer>
static void remove(Pointer x,Pointer root)
{
while(x!=root){
x=x->parent();
--(x->size);
}
}
template<typename Pointer>
static void copy(Pointer x,Pointer y)
{
y->size=x->size;
}
template<typename Pointer>
static void rotate_left(Pointer x,Pointer y) /* in: x==y->left() */
{
y->size=x->size;
x->size=ranked_node_size(x->left())+ranked_node_size(x->right())+1;
}
template<typename Pointer>
static void rotate_right(Pointer x,Pointer y) /* in: x==y->right() */
{
rotate_left(x,y);
}
#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
/* invariant stuff */
template<typename Pointer>
static bool invariant(Pointer x)
{
return x->size==ranked_node_size(x->left())+ranked_node_size(x->right())+1;
}
#endif
};
} /* namespace multi_index::detail */
/* ranked_index specifiers */
template<typename Arg1,typename Arg2,typename Arg3>
struct ranked_unique
{
typedef typename detail::ordered_index_args<
Arg1,Arg2,Arg3> index_args;
typedef typename index_args::tag_list_type::type tag_list_type;
typedef typename index_args::key_from_value_type key_from_value_type;
typedef typename index_args::compare_type compare_type;
template<typename Super>
struct node_class
{
typedef detail::ordered_index_node<detail::rank_policy,Super> type;
};
template<typename SuperMeta>
struct index_class
{
typedef detail::ordered_index<
key_from_value_type,compare_type,
SuperMeta,tag_list_type,detail::ordered_unique_tag,
detail::rank_policy> type;
};
};
template<typename Arg1,typename Arg2,typename Arg3>
struct ranked_non_unique
{
typedef detail::ordered_index_args<
Arg1,Arg2,Arg3> index_args;
typedef typename index_args::tag_list_type::type tag_list_type;
typedef typename index_args::key_from_value_type key_from_value_type;
typedef typename index_args::compare_type compare_type;
template<typename Super>
struct node_class
{
typedef detail::ordered_index_node<detail::rank_policy,Super> type;
};
template<typename SuperMeta>
struct index_class
{
typedef detail::ordered_index<
key_from_value_type,compare_type,
SuperMeta,tag_list_type,detail::ordered_non_unique_tag,
detail::rank_policy> type;
};
};
} /* namespace multi_index */
} /* namespace boost */
#endif