326 lines
8.4 KiB
C++
326 lines
8.4 KiB
C++
/* Copyright 2003-2018 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_DETAIL_RNK_INDEX_OPS_HPP
|
|
#define BOOST_MULTI_INDEX_DETAIL_RNK_INDEX_OPS_HPP
|
|
|
|
#if defined(_MSC_VER)
|
|
#pragma once
|
|
#endif
|
|
|
|
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
|
#include <boost/core/pointer_traits.hpp>
|
|
#include <boost/mpl/and.hpp>
|
|
#include <boost/multi_index/detail/promotes_arg.hpp>
|
|
#include <utility>
|
|
|
|
namespace boost{
|
|
|
|
namespace multi_index{
|
|
|
|
namespace detail{
|
|
|
|
/* Common code for ranked_index memfuns having templatized and
|
|
* non-templatized versions.
|
|
*/
|
|
|
|
template<typename Pointer>
|
|
struct ranked_node_size_type
|
|
{
|
|
typedef typename boost::pointer_traits<Pointer>::
|
|
element_type::size_type type;
|
|
};
|
|
|
|
template<typename Pointer>
|
|
inline typename ranked_node_size_type<Pointer>::type
|
|
ranked_node_size(Pointer x)
|
|
{
|
|
return x!=Pointer(0)?x->size:0;
|
|
}
|
|
|
|
template<typename Pointer>
|
|
inline Pointer ranked_index_nth(
|
|
BOOST_DEDUCED_TYPENAME ranked_node_size_type<Pointer>::type n,Pointer end_)
|
|
{
|
|
typedef typename ranked_node_size_type<Pointer>::type size_type;
|
|
|
|
Pointer top=end_->parent();
|
|
if(top==Pointer(0)||n>=top->size)return end_;
|
|
|
|
for(;;){
|
|
size_type s=ranked_node_size(top->left());
|
|
if(n==s)return top;
|
|
if(n<s)top=top->left();
|
|
else{
|
|
top=top->right();
|
|
n-=s+1;
|
|
}
|
|
}
|
|
}
|
|
|
|
template<typename Pointer>
|
|
inline typename ranked_node_size_type<Pointer>::type
|
|
ranked_index_rank(Pointer x,Pointer end_)
|
|
{
|
|
typedef typename ranked_node_size_type<Pointer>::type size_type;
|
|
|
|
Pointer top=end_->parent();
|
|
if(top==Pointer(0))return 0;
|
|
if(x==end_)return top->size;
|
|
|
|
size_type s=ranked_node_size(x->left());
|
|
while(x!=top){
|
|
Pointer z=x->parent();
|
|
if(x==z->right()){
|
|
s+=ranked_node_size(z->left())+1;
|
|
}
|
|
x=z;
|
|
}
|
|
return s;
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_find_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp)
|
|
{
|
|
typedef typename KeyFromValue::result_type key_type;
|
|
|
|
return ranked_index_find_rank(
|
|
top,y,key,x,comp,
|
|
mpl::and_<
|
|
promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
|
|
promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_find_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,
|
|
const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
|
|
const CompatibleCompare& comp,mpl::true_)
|
|
{
|
|
return ranked_index_find_rank(top,y,key,x,comp,mpl::false_());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_find_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp,mpl::false_)
|
|
{
|
|
typedef typename Node::size_type size_type;
|
|
|
|
if(!top)return 0;
|
|
|
|
size_type s=top->impl()->size,
|
|
s0=s;
|
|
Node* y0=y;
|
|
|
|
do{
|
|
if(!comp(key(top->value()),x)){
|
|
y=top;
|
|
s-=ranked_node_size(y->right())+1;
|
|
top=Node::from_impl(top->left());
|
|
}
|
|
else top=Node::from_impl(top->right());
|
|
}while(top);
|
|
|
|
return (y==y0||comp(x,key(y->value())))?s0:s;
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_lower_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp)
|
|
{
|
|
typedef typename KeyFromValue::result_type key_type;
|
|
|
|
return ranked_index_lower_bound_rank(
|
|
top,y,key,x,comp,
|
|
promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_lower_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,
|
|
const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
|
|
const CompatibleCompare& comp,mpl::true_)
|
|
{
|
|
return ranked_index_lower_bound_rank(top,y,key,x,comp,mpl::false_());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_lower_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp,mpl::false_)
|
|
{
|
|
typedef typename Node::size_type size_type;
|
|
|
|
if(!top)return 0;
|
|
|
|
size_type s=top->impl()->size;
|
|
|
|
do{
|
|
if(!comp(key(top->value()),x)){
|
|
y=top;
|
|
s-=ranked_node_size(y->right())+1;
|
|
top=Node::from_impl(top->left());
|
|
}
|
|
else top=Node::from_impl(top->right());
|
|
}while(top);
|
|
|
|
return s;
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_upper_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp)
|
|
{
|
|
typedef typename KeyFromValue::result_type key_type;
|
|
|
|
return ranked_index_upper_bound_rank(
|
|
top,y,key,x,comp,
|
|
promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_upper_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,
|
|
const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
|
|
const CompatibleCompare& comp,mpl::true_)
|
|
{
|
|
return ranked_index_upper_bound_rank(top,y,key,x,comp,mpl::false_());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline typename Node::size_type ranked_index_upper_bound_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp,mpl::false_)
|
|
{
|
|
typedef typename Node::size_type size_type;
|
|
|
|
if(!top)return 0;
|
|
|
|
size_type s=top->impl()->size;
|
|
|
|
do{
|
|
if(comp(x,key(top->value()))){
|
|
y=top;
|
|
s-=ranked_node_size(y->right())+1;
|
|
top=Node::from_impl(top->left());
|
|
}
|
|
else top=Node::from_impl(top->right());
|
|
}while(top);
|
|
|
|
return s;
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline std::pair<typename Node::size_type,typename Node::size_type>
|
|
ranked_index_equal_range_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp)
|
|
{
|
|
typedef typename KeyFromValue::result_type key_type;
|
|
|
|
return ranked_index_equal_range_rank(
|
|
top,y,key,x,comp,
|
|
mpl::and_<
|
|
promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
|
|
promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleCompare
|
|
>
|
|
inline std::pair<typename Node::size_type,typename Node::size_type>
|
|
ranked_index_equal_range_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,
|
|
const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
|
|
const CompatibleCompare& comp,mpl::true_)
|
|
{
|
|
return ranked_index_equal_range_rank(top,y,key,x,comp,mpl::false_());
|
|
}
|
|
|
|
template<
|
|
typename Node,typename KeyFromValue,
|
|
typename CompatibleKey,typename CompatibleCompare
|
|
>
|
|
inline std::pair<typename Node::size_type,typename Node::size_type>
|
|
ranked_index_equal_range_rank(
|
|
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
|
|
const CompatibleCompare& comp,mpl::false_)
|
|
{
|
|
typedef typename Node::size_type size_type;
|
|
|
|
if(!top)return std::pair<size_type,size_type>(0,0);
|
|
|
|
size_type s=top->impl()->size;
|
|
|
|
do{
|
|
if(comp(key(top->value()),x)){
|
|
top=Node::from_impl(top->right());
|
|
}
|
|
else if(comp(x,key(top->value()))){
|
|
y=top;
|
|
s-=ranked_node_size(y->right())+1;
|
|
top=Node::from_impl(top->left());
|
|
}
|
|
else{
|
|
return std::pair<size_type,size_type>(
|
|
s-top->impl()->size+
|
|
ranked_index_lower_bound_rank(
|
|
Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
|
|
s-ranked_node_size(top->right())+
|
|
ranked_index_upper_bound_rank(
|
|
Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
|
|
}
|
|
}while(top);
|
|
|
|
return std::pair<size_type,size_type>(s,s);
|
|
}
|
|
|
|
} /* namespace multi_index::detail */
|
|
|
|
} /* namespace multi_index */
|
|
|
|
} /* namespace boost */
|
|
|
|
#endif
|