stlab.adobe.com Adobe Systems Incorporated
equal_range.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_ALGORITHM_EQUAL_RANGE_HPP
10 #define ADOBE_ALGORITHM_EQUAL_RANGE_HPP
11 
12 #include <adobe/config.hpp>
13 
14 #include <algorithm>
15 #include <cassert>
16 #include <utility>
17 
18 #include <boost/bind.hpp>
19 #include <boost/next_prior.hpp>
20 #include <boost/range/begin.hpp>
21 #include <boost/range/end.hpp>
22 
25 #include <adobe/functional.hpp>
26 
27 /*************************************************************************************************/
28 
37 /*************************************************************************************************/
38 
39 namespace adobe {
40 namespace implementation {
41 
42 /*************************************************************************************************/
43 
44 template < typename I, // I models ForwardIterator
45  typename N, // N models IntegralType
46  typename T, // T == result_type(P)
47  typename C, // C models StrictWeakOrdering(T, T)
48  typename P> // P models UnaryFunction(value_type(I)) -> T
49 std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p)
50 {
51  assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
52 
53  while (n != 0) {
54  N h = n >> 1;
55  I m = boost::next(f, h);
56 
57  if (c(p(*m), x)) {
58  f = boost::next(m);
59  n -= h + 1;
60  } else if (c(x, p(*m))) {
61  n = h;
62  } else {
63  return std::make_pair(implementation::lower_bound_n_(f, h, x, c, p),
64  implementation::upper_bound_n(boost::next(m), n - (h + 1), x, c, p));
65  }
66  }
67  return std::make_pair(f, f);
68 }
69 
70 /*************************************************************************************************/
71 
72 template <typename I> // I models ForwardRange
73 struct lazy_range
74 {
75  typedef std::pair<typename boost::range_iterator<I>::type,
76  typename boost::range_iterator<I>::type> type;
77 };
78 
79 /*************************************************************************************************/
80 
81 template <typename I> // I models ForwardRange
82 struct lazy_range_const
83 {
84  typedef std::pair<typename boost::range_const_iterator<I>::type,
85  typename boost::range_const_iterator<I>::type> type;
86 };
87 
88 /*************************************************************************************************/
89 
90 } // namespace implementation
91 
92 /*************************************************************************************************/
93 
98 template < typename I, // I models ForwardIterator
99  typename N, // N models IntegralType
100  typename T> // T == result_type(P)
101 inline std::pair<I, I> equal_range_n(I f, N n, const T& x)
102 {
103  return implementation::equal_range_n(f, n, x, less(), identity<T>());
104 }
105 
106 /*************************************************************************************************/
107 
112 template < typename I, // I models ForwardIterator
113  typename N, // N models IntegralType
114  typename T, // T == result_type(P)
115  typename C> // C models StrictWeakOrdering(T, T)
116 inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c)
117 {
118  return implementation::equal_range_n(f, n, x, boost::bind(c, _1, _2), identity<T>());
119 }
120 
121 /*************************************************************************************************/
122 
127 template < typename I, // I models ForwardIterator
128  typename N, // N models IntegralType
129  typename T, // T == result_type(P)
130  typename C, // C models StrictWeakOrdering(T, T)
131  typename P> // P models UnaryFunction(value_type(I)) -> T
132 inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p)
133 {
134  return implementation::equal_range_n(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
135 }
136 
137 /*************************************************************************************************/
138 
143 template < typename I, // I models ForwardIterator
144  typename T> // T == value_type(I)
145 inline std::pair<I, I> equal_range(I f, I l, const T& x)
146 {
147  return std::equal_range(f, l, x);
148 }
149 
150 /*************************************************************************************************/
151 
156 template < typename I, // I models ForwardIterator
157  typename T, // T == result_type(P)
158  typename C> // C models StrictWeakOrdering(T, T)
159 inline std::pair<I, I> equal_range(I f, I l, const T& x, C c)
160 {
161  return std::equal_range(f, l, x, boost::bind(c, _1, _2));
162 }
163 
164 /*************************************************************************************************/
165 
170 template < typename I, // I models ForwardIterator
171  typename T, // T == result_type(P)
172  typename C, // C models StrictWeakOrdering(T, T)
173  typename P> // P models UnaryFunction(value_type(I)) -> T
174 inline std::pair<I, I> equal_range(I f, I l, const T& x, C c, P p)
175 {
176  return equal_range_n(f, std::distance(f, l), x, c, p);
177 }
178 
179 /*************************************************************************************************/
180 
185 template < typename I, // I models ForwardRange
186  typename T, // T == result_type(P)
187  typename C, // C models StrictWeakOrdering(T, T)
188  typename P> // P models UnaryFunction(value_type(I)) -> T
189 inline
190 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range<I> >::type
191  equal_range(I& r, const T& x, C c, P p)
192 { return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p); }
193 
194 /*************************************************************************************************/
195 
200 template < typename I, // I models ForwardRange
201  typename T, // T == result_type(P)
202  typename C, // C models StrictWeakOrdering(T, T)
203  typename P> // P models UnaryFunction(value_type(I)) -> T
204 inline
205 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range_const<I> >::type
206  equal_range(const I& r, const T& x, C c, P p)
207 { return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p); }
208 
209 /*************************************************************************************************/
210 
215 template < typename I, // I models ForwardRange
216  typename T> // T == result_type(P)
217 inline std::pair<typename boost::range_iterator<I>::type,
218  typename boost::range_iterator<I>::type>
219 equal_range(I& r, const T& x)
220 {
221  return std::equal_range(boost::begin(r), boost::end(r), x);
222 }
223 
224 /*************************************************************************************************/
225 
230 template < typename I, // I models ForwardRange
231  typename T> // T == result_type(P)
232 inline std::pair<typename boost::range_const_iterator<I>::type,
233  typename boost::range_const_iterator<I>::type>
234 equal_range(const I& r, const T& x)
235 {
236  return std::equal_range(boost::begin(r), boost::end(r), x);
237 }
238 
239 /*************************************************************************************************/
240 
245 template < typename I, // I models ForwardRange
246  typename T, // T == result_type(P)
247  typename C> // C models StrictWeakOrdering(T, T)
248 inline
249 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range<I> >::type
250 equal_range(I& r, const T& x, C c)
251 {
252  return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
253 }
254 
255 /*************************************************************************************************/
256 
261 template < typename I, // I models ForwardRange
262  typename T, // T == result_type(P)
263  typename C> // C models StrictWeakOrdering(T, T)
264 inline
265 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range_const<I> >::type
266 equal_range(const I& r, const T& x, C c)
267 {
268  return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
269 }
270 
271 /*************************************************************************************************/
272 
273 } // namespace adobe
274 
275 /*************************************************************************************************/
276 
277 #endif
278 
279 /*************************************************************************************************/

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google