Line data Source code
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 : >
65 0 : 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 0 : 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 : >
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 : >
94 0 : inline Node* ordered_index_find(
95 : Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
96 : const CompatibleCompare& comp,mpl::false_)
97 : {
98 0 : Node* y0=y;
99 :
100 0 : while (top){
101 0 : if(!comp(key(top->value()),x)){
102 0 : y=top;
103 0 : top=Node::from_impl(top->left());
104 : }
105 0 : else top=Node::from_impl(top->right());
106 : }
107 :
108 0 : 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 : >
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 : >
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 : >
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 : >
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 : >
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 : >
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 : >
207 0 : 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 0 : 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 : >
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 : >
236 0 : 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 0 : while(top){
241 0 : if(comp(key(top->value()),x)){
242 0 : top=Node::from_impl(top->right());
243 : }
244 0 : else if(comp(x,key(top->value()))){
245 0 : y=top;
246 0 : top=Node::from_impl(top->left());
247 : }
248 : else{
249 : return std::pair<Node*,Node*>(
250 0 : ordered_index_lower_bound(
251 0 : Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
252 0 : ordered_index_upper_bound(
253 0 : Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
254 : }
255 : }
256 :
257 0 : 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
|
