Adobe Source Libraries 2.0.0
A collection of C++ libraries.
Loading...
Searching...
No Matches
binary_search.hpp
Go to the documentation of this file.
1/*
2 Copyright 2013 Adobe
3 Distributed under the Boost Software License, Version 1.0.
4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5*/
6/**************************************************************************************************/
7
8#ifndef ADOBE_ALGORITHM_BINARY_SEARCH_HPP
9#define ADOBE_ALGORITHM_BINARY_SEARCH_HPP
10
11#include <adobe/config.hpp>
12
13#include <functional>
14#include <type_traits>
15
16#include <boost/range/begin.hpp>
17#include <boost/range/const_iterator.hpp>
18#include <boost/range/end.hpp>
19#include <boost/range/iterator.hpp>
20
21#include <adobe/algorithm/lower_bound.hpp>
22#include <adobe/functional/operator.hpp>
23
24/**************************************************************************************************/
25
26namespace adobe {
27
28namespace implementation {
29
30template <typename I, // I models ForwardIterator
31 typename T, // T models Regular
32 typename C, // C models StrictWeakOrdering
33 typename P>
34// P models UnaryFunction(value_type(I)) -> T
35inline I binary_search(I f, I l, const T& x, C c, P p) {
36 I result = adobe::lower_bound(f, l, x, c, p);
37 if (result != l && p(*result) == x)
38 return result;
39 return l;
40}
41} // namespace implementation
42
43/**************************************************************************************************/
97/**************************************************************************************************/
98
99template <typename I, // I models ForwardIterator
100 typename T, // T models Regular
101 typename C, // C models StrictWeakOrdering
102 typename P>
103// P models UnaryFunction(value_type(I)) -> T
104inline I binary_search(I f, I l, const T& x, C c, P p) {
105 return implementation::binary_search(f, l, x, c, std::bind(p, std::placeholders::_1));
106}
107
108
109template <typename I, // I models ForwardIterator
110 typename T, // T models Regular
111 typename C>
112// C models StrictWeakOrdering
113inline I binary_search(I f, I l, const T& x, C c) {
114 return adobe::binary_search(f, l, x, c, identity<T>());
115}
116
117template <typename I, // I models ForwardIterator
118 typename T>
119// T models Regular
120inline I binary_search(I f, I l, const T& x) {
121 return adobe::binary_search(f, l, x, less());
122}
123
124template <typename I, typename T>
125inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x) {
126 return adobe::binary_search(boost::begin(range), boost::end(range), x);
127}
128
129template <typename I, typename T>
130inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x) {
131 return adobe::binary_search(boost::begin(range), boost::end(range), x);
132}
133
134template <typename I, typename T, typename C>
135inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x, C c) {
136 return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
137}
138
139template <typename I, typename T, typename C>
140inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x,
141 C c) {
142 return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
143}
144
145/**************************************************************************************************/
146
147template <typename I, // I models ForwardRange
148 typename T, // T == result_type(P)
149 typename C, // C models StrictWeakOrdering(T, T)
150 typename P> // P models UnaryFunction(value_type(I)) -> T
151inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_iterator<I>>::type
152binary_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
158template <typename I, // I models ForwardRange
159 typename T, // T == result_type(P)
160 typename C, // C models StrictWeakOrdering(T, T)
161 typename P> // P models UnaryFunction(value_type(I)) -> T
162inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_const_iterator<I>>::type
163binary_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}
166
170
171/**************************************************************************************************/
172
173} // namespace adobe
174
175/**************************************************************************************************/
176
177#endif
178
179/**************************************************************************************************/
adobe::binary_search
I binary_search(I f, I l, const T &x, C c, P p)
Definition binary_search.hpp:104
lower_bound.hpp
adobe::fn::lower_bound
I lower_bound(I f, I l, const T &x)
Definition lower_bound.hpp:120