stlab.adobe.com Adobe Systems Incorporated
upper_bound.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_UPPER_BOUND_HPP
10 #define ADOBE_ALGORITHM_UPPER_BOUND_HPP
11 
12 #include <adobe/config.hpp>
13 
14 #include <algorithm>
15 #include <cassert>
16 #include <iterator>
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 #include <boost/type_traits/is_same.hpp>
23 #include <boost/utility/enable_if.hpp>
24 
25 #include <adobe/functional.hpp>
26 
27 /*************************************************************************************************/
28 
29 namespace adobe {
30 namespace implementation {
31 
32 /*************************************************************************************************/
33 
34 template < typename I, // I models ForwardIterator
35  typename N, // N models IntegralType
36  typename T, // T == result_type(P)
37  typename C, // C models StrictWeakOrdering(T, T)
38  typename P> // P models UnaryFunction(value_type(I)) -> T
39 I upper_bound_n(I f, N n, const T& x, C c, P p)
40 {
41  assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
42 
43  while (n != 0)
44  {
45  N h = n >> 1;
46 
47  I m = boost::next(f, h);
48 
49  if (!c(x, p(*m))) { f = boost::next(m); n -= h + N(1); }
50  else { n = h; }
51  }
52  return f;
53 }
54 
55 /*************************************************************************************************/
56 
57 } // implementation
58 
59 /*************************************************************************************************/
60 
69 /*************************************************************************************************/
70 
71 template < typename I, // I models ForwardIterator
72  typename N, // N models IntegralType
73  typename T> // T == value_type(I)
74 inline I upper_bound_n(I f, N n, const T& x)
75 {
76  return implementation::upper_bound_n(f, n, x, less(), identity<T>());
77 }
78 
79 /*************************************************************************************************/
80 
81 template < typename I, // I models FowardIterator
82  typename N, // N models IntegralType
83  typename T, // T == value_type(I)
84  typename C> // C models StrictWeakOrdering(T, T)
85 inline I upper_bound_n(I f, N n, const T& x, C c)
86 {
87  return implementation::upper_bound_n(f, n, x, boost::bind(c, _1, _2), identity<T>());
88 }
89 
90 /*************************************************************************************************/
91 
92 template < typename I, // I models ForwardIterator
93  typename N, // N models IntegralType
94  typename T, // T == result_type(P)
95  typename C, // C models StrictWeakOrdering(T, T)
96  typename P> // P models UnaryFunction(value_type(I)) -> T
97 inline I upper_bound_n(I f, N n, const T& x, C c, P p)
98 {
99  return implementation::upper_bound_n(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
100 }
101 
102 /*************************************************************************************************/
103 
104 /*
105  NOTE (sparent) : These functions collide with the std functions when called unqualified as
106  is done by std::equal_range with VC++. We hide them from ADL by moving them into the
107  fn namespace.
108 */
109 
110 namespace fn { } using namespace fn;
111 namespace fn {
112 
113 /*************************************************************************************************/
114 
115 template < typename I, // I models ForwardIterator
116  typename T> // T == value_type(I)
117 inline I upper_bound(I f, I l, const T& x)
118 {
119  return std::upper_bound(f, l, x);
120 }
121 
122 /*************************************************************************************************/
123 
124 template < typename I, // I models FowardIterator
125  typename T, // T == value_type(I)
126  typename C> // C models StrictWeakOrdering(T, T)
127 inline I upper_bound(I f, I l, const T& x, C c)
128 {
129  return std::upper_bound(f, l, x, boost::bind(c, _1, _2));
130 }
131 
132 /*************************************************************************************************/
133 
134 template < typename I, // I models ForwardIterator
135  typename T, // T == result_type(P)
136  typename C, // C models StrictWeakOrdering(T, T)
137  typename P> // P models UnaryFunction(value_type(I)) -> T
138 inline I upper_bound(I f, I l, const T& x, C c, P p)
139 {
140  return upper_bound_n(f, std::distance(f, l), x, c, p);
141 }
142 
143 /*************************************************************************************************/
144 
145 template < typename I, // I models ForwardRange
146  typename T, // T == result_type(P)
147  typename C, // C models StrictWeakOrdering(T, T)
148  typename P> // P models UnaryFunction(value_type(I)) -> T
149 inline
150  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
151  upper_bound(I& r, const T& x, C c, P p)
152 { return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p); }
153 
154 /*************************************************************************************************/
155 
156 template < typename I, // I models ForwardRange
157  typename T, // T == result_type(P)
158  typename C, // C models StrictWeakOrdering(T, T)
159  typename P> // P models UnaryFunction(value_type(I)) -> T
160 inline
161  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
162  upper_bound(const I& r, const T& x, C c, P p)
163 { return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p); }
164 
165 /*************************************************************************************************/
171 template <class ForwardRange, class T>
172 inline typename boost::range_iterator<ForwardRange>::type upper_bound(ForwardRange& range, const T& value)
173 {
174  return std::upper_bound(boost::begin(range), boost::end(range), value);
175 }
176 
182 template <class ForwardRange, class T>
183 inline typename boost::range_const_iterator<ForwardRange>::type upper_bound(const ForwardRange& range, const T& value)
184 {
185  return std::upper_bound(boost::begin(range), boost::end(range), value);
186 }
187 
198 template <typename I, class T, class Compare>
199 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
200  upper_bound(I& range, const T& value, Compare comp)
201 {
202  return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
203 }
204 
210 template <class I, class T, class Compare>
211 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
212  upper_bound(const I& range, const T& value, Compare comp)
213 {
214  return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
215 }
216 
217 /*************************************************************************************************/
218 
219 } // namespace fn
220 } // namespace adobe
221 
222 /*************************************************************************************************/
223 
224 #endif
225 
226 /*************************************************************************************************/
boost::lazy_disable_if< boost::is_same< I, T >, boost::range_const_iterator< I > >::type upper_bound(const I &range, const T &value, Compare comp)
upper_bound implementation
I upper_bound_n(I f, N n, const T &x, C c, P p)
Definition: upper_bound.hpp:97
I upper_bound_n(I f, N n, const T &x)
Definition: upper_bound.hpp:74
boost::difference_type< I >::type distance(I &range)
Definition: distance.hpp:29

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