[ceph.git] / ceph / src / boost / boost / multi_index / detail / rnk_index_ops.hpp

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