stlab.adobe.com Adobe Systems Incorporated
binary_search.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_BINARY_SEARCH_HPP
10 #define ADOBE_ALGORITHM_BINARY_SEARCH_HPP
11 
12 #include <adobe/config.hpp>
13 
14 #include <boost/range/begin.hpp>
15 #include <boost/range/const_iterator.hpp>
16 #include <boost/range/end.hpp>
17 #include <boost/range/iterator.hpp>
18 
21 
22 /*************************************************************************************************/
23 
24 namespace adobe {
25 
26 namespace implementation {
27 
28 template <typename I, // I models ForwardIterator
29  typename T, // T models Regular
30  typename C, // C models StrictWeakOrdering
31  typename P> // P models UnaryFunction(value_type(I)) -> T
32 inline I binary_search(I f, I l, const T& x, C c, P p)
33 {
34  I result = adobe::lower_bound(f, l, x, c, p);
35  if (result != l && p(*result) == x) return result;
36  return l;
37 }
38 
39 }
40 
41 /*************************************************************************************************/
95 /*************************************************************************************************/
96 
97 template <typename I, // I models ForwardIterator
98  typename T, // T models Regular
99  typename C, // C models StrictWeakOrdering
100  typename P> // P models UnaryFunction(value_type(I)) -> T
101 inline I binary_search(I f, I l, const T& x, C c, P p)
102 {
103  return implementation::binary_search(f, l, x, c, boost::bind(p, _1));
104 }
105 
106 
107 template <typename I, // I models ForwardIterator
108  typename T, // T models Regular
109  typename C> // C models StrictWeakOrdering
110 inline I binary_search(I f, I l, const T& x, C c)
111 {
112  return adobe::binary_search(f, l, x, c, identity<T>());
113 }
114 
115 template <typename I, // I models ForwardIterator
116  typename T> // T models Regular
117 inline I binary_search(I f, I l, const T& x)
118 { return binary_search(f, l, x, less()); }
119 
120 template <typename I, typename T>
121 inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x)
122 {
123  return adobe::binary_search(boost::begin(range), boost::end(range), x);
124 }
125 
126 template <typename I, typename T>
127 inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x)
128 {
129  return adobe::binary_search(boost::begin(range), boost::end(range), x);
130 }
131 
132 template <typename I, typename T, typename C>
133 inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x, C c)
134 {
135  return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
136 }
137 
138 template <typename I, typename T, typename C>
139 inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x, C c)
140 {
141  return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
142 }
143 
144 /*************************************************************************************************/
145 
146 template < typename I, // I models ForwardRange
147  typename T, // T == result_type(P)
148  typename C, // C models StrictWeakOrdering(T, T)
149  typename P> // P models UnaryFunction(value_type(I)) -> T
150 inline
151  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
152  binary_search(I& r, const T& x, C c, P p)
153 { return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }
154 
155 /*************************************************************************************************/
156 
157 template < typename I, // I models ForwardRange
158  typename T, // T == result_type(P)
159  typename C, // C models StrictWeakOrdering(T, T)
160  typename P> // P models UnaryFunction(value_type(I)) -> T
161 inline
162  typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
163  binary_search(const I& r, const T& x, C c, P p)
164 { return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }
165 
170 /*************************************************************************************************/
171 
172 } // namespace adobe
173 
174 /*************************************************************************************************/
175 
176 #endif
177 
178 /*************************************************************************************************/
boost::lazy_disable_if< boost::is_same< I, T >, boost::range_const_iterator< I > >::type binary_search(const I &r, const T &x, C c, P p)
I lower_bound(I f, I l, const T &x)
I binary_search(I f, I l, const T &x, C c, P p)

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