1 /* Copyright 2003-2014 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)
6 * See http://www.boost.org/libs/multi_index for library home page.
8 * The internal implementation of red-black trees is based on that of SGI STL
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
14 * Permission to use, copy, modify, distribute and sell this software
15 * and its documentation for any purpose is hereby granted without fee,
16 * provided that the above copyright notice appear in all copies and
17 * that both that copyright notice and this permission notice appear
18 * in supporting documentation. Silicon Graphics makes no
19 * representations about the suitability of this software for any
20 * purpose. It is provided "as is" without express or implied warranty.
24 * Hewlett-Packard Company
26 * Permission to use, copy, modify, distribute and sell this software
27 * and its documentation for any purpose is hereby granted without fee,
28 * provided that the above copyright notice appear in all copies and
29 * that both that copyright notice and this permission notice appear
30 * in supporting documentation. Hewlett-Packard Company makes no
31 * representations about the suitability of this software for any
32 * purpose. It is provided "as is" without express or implied warranty.
36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
44 #include <boost/mpl/and.hpp>
45 #include <boost/multi_index/detail/promotes_arg.hpp>
50 namespace multi_index{
54 /* Common code for index memfuns having templatized and
55 * non-templatized versions.
56 * Implementation note: When CompatibleKey is consistently promoted to
57 * KeyFromValue::result_type for comparison, the promotion is made once in
58 * advance to increase efficiency.
62 typename Node,typename KeyFromValue,
63 typename CompatibleKey,typename CompatibleCompare
65 inline Node* ordered_index_find(
66 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
67 const CompatibleCompare& comp)
69 typedef typename KeyFromValue::result_type key_type;
71 return ordered_index_find(
74 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
75 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
79 typename Node,typename KeyFromValue,
80 typename CompatibleCompare
82 inline Node* ordered_index_find(
83 Node* top,Node* y,const KeyFromValue& key,
84 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
85 const CompatibleCompare& comp,mpl::true_)
87 return ordered_index_find(top,y,key,x,comp,mpl::false_());
91 typename Node,typename KeyFromValue,
92 typename CompatibleKey,typename CompatibleCompare
94 inline Node* ordered_index_find(
95 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
96 const CompatibleCompare& comp,mpl::false_)
101 if(!comp(key(top->value()),x)){
103 top=Node::from_impl(top->left());
105 else top=Node::from_impl(top->right());
108 return (y==y0||comp(x,key(y->value())))?y0:y;
112 typename Node,typename KeyFromValue,
113 typename CompatibleKey,typename CompatibleCompare
115 inline Node* ordered_index_lower_bound(
116 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
117 const CompatibleCompare& comp)
119 typedef typename KeyFromValue::result_type key_type;
121 return ordered_index_lower_bound(
123 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
127 typename Node,typename KeyFromValue,
128 typename CompatibleCompare
130 inline Node* ordered_index_lower_bound(
131 Node* top,Node* y,const KeyFromValue& key,
132 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
133 const CompatibleCompare& comp,mpl::true_)
135 return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_());
139 typename Node,typename KeyFromValue,
140 typename CompatibleKey,typename CompatibleCompare
142 inline Node* ordered_index_lower_bound(
143 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
144 const CompatibleCompare& comp,mpl::false_)
147 if(!comp(key(top->value()),x)){
149 top=Node::from_impl(top->left());
151 else top=Node::from_impl(top->right());
158 typename Node,typename KeyFromValue,
159 typename CompatibleKey,typename CompatibleCompare
161 inline Node* ordered_index_upper_bound(
162 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
163 const CompatibleCompare& comp)
165 typedef typename KeyFromValue::result_type key_type;
167 return ordered_index_upper_bound(
169 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
173 typename Node,typename KeyFromValue,
174 typename CompatibleCompare
176 inline Node* ordered_index_upper_bound(
177 Node* top,Node* y,const KeyFromValue& key,
178 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
179 const CompatibleCompare& comp,mpl::true_)
181 return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_());
185 typename Node,typename KeyFromValue,
186 typename CompatibleKey,typename CompatibleCompare
188 inline Node* ordered_index_upper_bound(
189 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
190 const CompatibleCompare& comp,mpl::false_)
193 if(comp(x,key(top->value()))){
195 top=Node::from_impl(top->left());
197 else top=Node::from_impl(top->right());
204 typename Node,typename KeyFromValue,
205 typename CompatibleKey,typename CompatibleCompare
207 inline std::pair<Node*,Node*> ordered_index_equal_range(
208 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
209 const CompatibleCompare& comp)
211 typedef typename KeyFromValue::result_type key_type;
213 return ordered_index_equal_range(
216 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
217 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
221 typename Node,typename KeyFromValue,
222 typename CompatibleCompare
224 inline std::pair<Node*,Node*> ordered_index_equal_range(
225 Node* top,Node* y,const KeyFromValue& key,
226 const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
227 const CompatibleCompare& comp,mpl::true_)
229 return ordered_index_equal_range(top,y,key,x,comp,mpl::false_());
233 typename Node,typename KeyFromValue,
234 typename CompatibleKey,typename CompatibleCompare
236 inline std::pair<Node*,Node*> ordered_index_equal_range(
237 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
238 const CompatibleCompare& comp,mpl::false_)
241 if(comp(key(top->value()),x)){
242 top=Node::from_impl(top->right());
244 else if(comp(x,key(top->value()))){
246 top=Node::from_impl(top->left());
249 return std::pair<Node*,Node*>(
250 ordered_index_lower_bound(
251 Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
252 ordered_index_upper_bound(
253 Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
257 return std::pair<Node*,Node*>(y,y);
260 } /* namespace multi_index::detail */
262 } /* namespace multi_index */
264 } /* namespace boost */