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

/* Copyright 2003-2015 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/mpl/and.hpp>
#include <boost/multi_index/detail/promotes_arg.hpp>
#include <cstddef>
#include <utility>

namespace boost{

namespace multi_index{

namespace detail{

/* Common code for ranked_index memfuns having templatized and
 * non-templatized versions.
 */

template<typename Pointer>
inline std::size_t ranked_node_size(Pointer x)
{
  return x!=Pointer(0)?x->size:0;
}

template<typename Pointer>
inline Pointer ranked_index_nth(std::size_t n,Pointer end_)
{
  Pointer top=end_->parent();
  if(top==Pointer(0)||n>=top->size)return end_;

  for(;;){
    std::size_t 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 std::size_t ranked_index_rank(Pointer x,Pointer end_)
{
  Pointer top=end_->parent();
  if(top==Pointer(0))return 0;
  if(x==end_)return top->size;

  std::size_t 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 std::size_t 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 std::size_t 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 std::size_t ranked_index_find_rank(
  Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  const CompatibleCompare& comp,mpl::false_)
{
  if(!top)return 0;

  std::size_t s=top->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 std::size_t 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 std::size_t 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 std::size_t ranked_index_lower_bound_rank(
  Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  const CompatibleCompare& comp,mpl::false_)
{
  if(!top)return 0;

  std::size_t s=top->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 std::size_t 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 std::size_t 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 std::size_t ranked_index_upper_bound_rank(
  Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  const CompatibleCompare& comp,mpl::false_)
{
  if(!top)return 0;

  std::size_t s=top->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<std::size_t,std::size_t> 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<std::size_t,std::size_t> 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<std::size_t,std::size_t> ranked_index_equal_range_rank(
  Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
  const CompatibleCompare& comp,mpl::false_)
{
  if(!top)return std::pair<std::size_t,std::size_t>(0,0);

  std::size_t s=top->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<std::size_t,std::size_t>(
        s-top->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<std::size_t,std::size_t>(s,s);
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

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