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)
5 *
6 * See http://www.boost.org/libs/multi_index for library home page.
7 *
8 * The internal implementation of red-black trees is based on that of SGI STL
9 * stl_tree.h file:
10 *
11 * Copyright (c) 1996,1997
12 * Silicon Graphics Computer Systems, Inc.
13 *
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.
21 *
22 *
23 * Copyright (c) 1994
24 * Hewlett-Packard Company
25 *
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.
33 *
34 */
35
36#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
37#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_HPP
38
39#if defined(_MSC_VER)
40#pragma once
41#endif
42
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>
46#include <utility>
47
48namespace boost{
49
50namespace multi_index{
51
52namespace detail{
53
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.
59 */
60
61template<
62 typename Node,typename KeyFromValue,
63 typename CompatibleKey,typename CompatibleCompare
64>
65inline Node* ordered_index_find(
66 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
67 const CompatibleCompare& comp)
68{
69 typedef typename KeyFromValue::result_type key_type;
70
71 return ordered_index_find(
72 top,y,key,x,comp,
73 mpl::and_<
74 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
75 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
76}
77
78template<
79 typename Node,typename KeyFromValue,
80 typename CompatibleCompare
81>
82inline 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_)
86{
87 return ordered_index_find(top,y,key,x,comp,mpl::false_());
88}
89
90template<
91 typename Node,typename KeyFromValue,
92 typename CompatibleKey,typename CompatibleCompare
93>
94inline Node* ordered_index_find(
95 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
96 const CompatibleCompare& comp,mpl::false_)
97{
98 Node* y0=y;
99
100 while (top){
101 if(!comp(key(top->value()),x)){
102 y=top;
103 top=Node::from_impl(top->left());
104 }
105 else top=Node::from_impl(top->right());
106 }
107
108 return (y==y0||comp(x,key(y->value())))?y0:y;
109}
110
111template<
112 typename Node,typename KeyFromValue,
113 typename CompatibleKey,typename CompatibleCompare
114>
115inline Node* ordered_index_lower_bound(
116 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
117 const CompatibleCompare& comp)
118{
119 typedef typename KeyFromValue::result_type key_type;
120
121 return ordered_index_lower_bound(
122 top,y,key,x,comp,
123 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
124}
125
126template<
127 typename Node,typename KeyFromValue,
128 typename CompatibleCompare
129>
130inline 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_)
134{
135 return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_());
136}
137
138template<
139 typename Node,typename KeyFromValue,
140 typename CompatibleKey,typename CompatibleCompare
141>
142inline Node* ordered_index_lower_bound(
143 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
144 const CompatibleCompare& comp,mpl::false_)
145{
146 while(top){
147 if(!comp(key(top->value()),x)){
148 y=top;
149 top=Node::from_impl(top->left());
150 }
151 else top=Node::from_impl(top->right());
152 }
153
154 return y;
155}
156
157template<
158 typename Node,typename KeyFromValue,
159 typename CompatibleKey,typename CompatibleCompare
160>
161inline Node* ordered_index_upper_bound(
162 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
163 const CompatibleCompare& comp)
164{
165 typedef typename KeyFromValue::result_type key_type;
166
167 return ordered_index_upper_bound(
168 top,y,key,x,comp,
169 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
170}
171
172template<
173 typename Node,typename KeyFromValue,
174 typename CompatibleCompare
175>
176inline 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_)
180{
181 return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_());
182}
183
184template<
185 typename Node,typename KeyFromValue,
186 typename CompatibleKey,typename CompatibleCompare
187>
188inline Node* ordered_index_upper_bound(
189 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
190 const CompatibleCompare& comp,mpl::false_)
191{
192 while(top){
193 if(comp(x,key(top->value()))){
194 y=top;
195 top=Node::from_impl(top->left());
196 }
197 else top=Node::from_impl(top->right());
198 }
199
200 return y;
201}
202
203template<
204 typename Node,typename KeyFromValue,
205 typename CompatibleKey,typename CompatibleCompare
206>
207inline std::pair<Node*,Node*> ordered_index_equal_range(
208 Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
209 const CompatibleCompare& comp)
210{
211 typedef typename KeyFromValue::result_type key_type;
212
213 return ordered_index_equal_range(
214 top,y,key,x,comp,
215 mpl::and_<
216 promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
217 promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
218}
219
220template<
221 typename Node,typename KeyFromValue,
222 typename CompatibleCompare
223>
224inline 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_)
228{
229 return ordered_index_equal_range(top,y,key,x,comp,mpl::false_());
230}
231
232template<
233 typename Node,typename KeyFromValue,
234 typename CompatibleKey,typename CompatibleCompare
235>
236inline 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_)
239{
240 while(top){
241 if(comp(key(top->value()),x)){
242 top=Node::from_impl(top->right());
243 }
244 else if(comp(x,key(top->value()))){
245 y=top;
246 top=Node::from_impl(top->left());
247 }
248 else{
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_()));
254 }
255 }
256
257 return std::pair<Node*,Node*>(y,y);
258}
259
260} /* namespace multi_index::detail */
261
262} /* namespace multi_index */
263
264} /* namespace boost */
265
266#endif
267