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
48 namespace boost{
49
50 namespace multi_index{
51
52 namespace 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
61 template<
62 typename Node,typename KeyFromValue,
63 typename CompatibleKey,typename CompatibleCompare
64 >
ordered_index_find(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)65 inline 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
78 template<
79 typename Node,typename KeyFromValue,
80 typename CompatibleCompare
81 >
ordered_index_find(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)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_)
86 {
87 return ordered_index_find(top,y,key,x,comp,mpl::false_());
88 }
89
90 template<
91 typename Node,typename KeyFromValue,
92 typename CompatibleKey,typename CompatibleCompare
93 >
ordered_index_find(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)94 inline 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
111 template<
112 typename Node,typename KeyFromValue,
113 typename CompatibleKey,typename CompatibleCompare
114 >
ordered_index_lower_bound(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)115 inline 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
126 template<
127 typename Node,typename KeyFromValue,
128 typename CompatibleCompare
129 >
ordered_index_lower_bound(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)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_)
134 {
135 return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_());
136 }
137
138 template<
139 typename Node,typename KeyFromValue,
140 typename CompatibleKey,typename CompatibleCompare
141 >
ordered_index_lower_bound(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)142 inline 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
157 template<
158 typename Node,typename KeyFromValue,
159 typename CompatibleKey,typename CompatibleCompare
160 >
ordered_index_upper_bound(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)161 inline 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
172 template<
173 typename Node,typename KeyFromValue,
174 typename CompatibleCompare
175 >
ordered_index_upper_bound(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)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_)
180 {
181 return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_());
182 }
183
184 template<
185 typename Node,typename KeyFromValue,
186 typename CompatibleKey,typename CompatibleCompare
187 >
ordered_index_upper_bound(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)188 inline 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
203 template<
204 typename Node,typename KeyFromValue,
205 typename CompatibleKey,typename CompatibleCompare
206 >
ordered_index_equal_range(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp)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)
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
220 template<
221 typename Node,typename KeyFromValue,
222 typename CompatibleCompare
223 >
ordered_index_equal_range(Node * top,Node * y,const KeyFromValue & key,const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type & x,const CompatibleCompare & comp,mpl::true_)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_)
228 {
229 return ordered_index_equal_range(top,y,key,x,comp,mpl::false_());
230 }
231
232 template<
233 typename Node,typename KeyFromValue,
234 typename CompatibleKey,typename CompatibleCompare
235 >
ordered_index_equal_range(Node * top,Node * y,const KeyFromValue & key,const CompatibleKey & x,const CompatibleCompare & comp,mpl::false_)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_)
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