stlab.adobe.com Adobe Systems Incorporated
lower_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_LOWER_BOUND_HPP
10 #define ADOBE_ALGORITHM_LOWER_BOUND_HPP
11 
12 #include <adobe/config.hpp>
13 
14 #include <algorithm>
15 #include <iterator>
16 
17 #include <boost/range/begin.hpp>
18 #include <boost/range/end.hpp>
19 #include <boost/bind.hpp>
20 #include <boost/next_prior.hpp>
21 #include <boost/type_traits/is_same.hpp>
22 #include <boost/utility/enable_if.hpp>
23 
25 
26 /*************************************************************************************************/
27 
28 namespace adobe {
29 namespace implementation {
30 
31 /*************************************************************************************************/
32 
33 template < typename I, // I models ForwardIterator
34  typename N, // N models IntegralType
35  typename T, // T == result_type(P)
36  typename C, // C models StrictWeakOrdering(T, T)
37  typename P> // P models UnaryFunction(value_type(I)) -> T
38 I lower_bound_n_(I f, N n, const T& x, C c, P p)
39 {
40  while (n != 0)
41  {
42  N h = n >> 1;
43  I m = boost::next(f, h);
44 
45  if (c(p(*m), x)) { f = boost::next(m); n -= h + N(1); }
46  else { n = h; }
47  }
48  return f;
49 }
50 
51 /*************************************************************************************************/
52 
53 } // implementation
54 
55 /*************************************************************************************************/
56 
65 /*************************************************************************************************/
66 
67 template < typename I, // I models ForwardIterator
68  typename N, // N models IntegralType
69  typename T> // T == value_type(I)
70 inline I lower_bound_n(I f, N n, const T& x)
71 {
72  return implementation::lower_bound_n_(f, n, x, less(), identity<T>());
73 }
74 
75 /*************************************************************************************************/
76 
77 template < typename I, // I models FowardIterator
78  typename N, // N models IntegralType
79  typename T, // T == value_type(I)
80  typename C> // C models StrictWeakOrdering(T, T)
81 inline I lower_bound_n(I f, N n, const T& x, C c)
82 {
83  return implementation::lower_bound_n_(f, n, x, boost::bind(c, _1, _2), identity<T>());
84 }
85 
86 /*************************************************************************************************/
87 
88 template < typename I, // I models ForwardIterator
89  typename N, // N models IntegralType
90  typename T, // T == result_type(P)
91  typename C, // C models StrictWeakOrdering(T, T)
92  typename P> // P models UnaryFunction(value_type(I)) -> T
93 inline I lower_bound_n(I f, N n, const T& x, C c, P p)
94 {
95  return implementation::lower_bound_n_(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
96 }
97 
98 /*************************************************************************************************/
99 
100 /*
101  NOTE (sparent) : These functions collide with the std functions when called unqualified as
102  is done by std::equal_range with VC++. We hide them from ADL by moving them into the
103  fn namespace.
104 */
105 
106 namespace fn { } using namespace fn;
107 namespace fn {
108 
109 /*************************************************************************************************/
110 
111 template < typename I, // I models ForwardIterator
112  typename T> // T == value_type(I)
113 inline I lower_bound(I f, I l, const T& x)
114 {
115  return std::lower_bound(f, l, x);
116 }
117 
118 /*************************************************************************************************/
119 
120 template < typename I, // I models FowardIterator
121  typename T, // T == value_type(I)
122  typename C> // C models StrictWeakOrdering(T, T)
123 inline I lower_bound(I f, I l, const T& x, C c)
124 {
125  return std::lower_bound(f, l, x, boost::bind(c, _1, _2));
126 }
127 
128 /*************************************************************************************************/
129 
130 template < typename I, // I models ForwardIterator
131  typename T, // T == result_type(P)
132  typename C, // C models StrictWeakOrdering(T, T)
133  typename P> // P models UnaryFunction(value_type(I)) -> T
134 inline I lower_bound(I f, I l, const T& x, C c, P p)
135 {
136  return lower_bound_n(f, std::distance(f, l), x, c, p);
137 }
138 
139 /*************************************************************************************************/
140 
141 template < typename I, // I models ForwardRange
142  typename T, // T == result_type(P)
143  typename C, // C models StrictWeakOrdering(T, T)
144  typename P> // P models UnaryFunction(value_type(I)) -> T
145 inline
146  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
147  lower_bound(I& r, const T& x, C c, P p)
148 { return adobe::lower_bound(boost::begin(r), boost::end(r), x, c, p); }
149 
150 /*************************************************************************************************/
151 
152 template < typename I, // I models ForwardRange
153  typename T, // T == result_type(P)
154  typename C, // C models StrictWeakOrdering(T, T)
155  typename P> // P models UnaryFunction(value_type(I)) -> T
156 inline
157  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
158  lower_bound(const I& r, const T& x, C c, P p)
159 { return adobe::lower_bound(boost::begin(r), boost::end(r), x, c, p); }
160 
161 /*************************************************************************************************/
167 template <class ForwardRange, class T>
168 inline typename boost::range_iterator<ForwardRange>::type lower_bound(ForwardRange& range, const T& value)
169 {
170  return std::lower_bound(boost::begin(range), boost::end(range), value);
171 }
172 
178 template <class ForwardRange, class T>
179 inline typename boost::range_const_iterator<ForwardRange>::type lower_bound(const ForwardRange& range, const T& value)
180 {
181  return std::lower_bound(boost::begin(range), boost::end(range), value);
182 }
183 
194 template <typename I, class T, class Compare>
195 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
196  lower_bound(I& range, const T& value, Compare comp)
197 {
198  return adobe::lower_bound(boost::begin(range), boost::end(range), value, comp);
199 }
200 
206 template <class I, class T, class Compare>
207 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
208  lower_bound(const I& range, const T& value, Compare comp)
209 {
210  return adobe::lower_bound(boost::begin(range), boost::end(range), value, comp);
211 }
212 
213 /*************************************************************************************************/
214 
215 } // namespace fn
216 } // namespace adobe
217 
218 /*************************************************************************************************/
219 
220 #endif
221 
222 /*************************************************************************************************/
I lower_bound(I f, I l, const T &x)
boost::difference_type< I >::type distance(I &range)
Definition: distance.hpp:29
boost::lazy_disable_if< boost::is_same< I, T >, boost::range_const_iterator< I > >::type lower_bound(const I &range, const T &value, Compare comp)
lower_bound implementation
I lower_bound_n(I f, N n, const T &x)
Definition: lower_bound.hpp:70

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