Adobe Source Libraries 1.49.0
A collection of C++ libraries.
Loading...
Searching...
No Matches
lower_bound.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_LOWER_BOUND_HPP
9#define ADOBE_ALGORITHM_LOWER_BOUND_HPP
10
11#include <adobe/config.hpp>
12
13#include <algorithm>
14#include <functional>
15#include <iterator>
16#include <type_traits>
17
18#include <boost/next_prior.hpp>
19#include <boost/range/begin.hpp>
20#include <boost/range/end.hpp>
21#include <boost/utility/enable_if.hpp>
22
23#include <adobe/functional/operator.hpp>
24
25/**************************************************************************************************/
26
27namespace adobe {
28namespace implementation {
29
30/**************************************************************************************************/
31
32template <typename I, // I models ForwardIterator
33 typename N, // N models IntegralType
34 typename T, // T == result_type(P)
35 typename C, // C models StrictWeakOrdering(T, T)
36 typename P>
37// P models UnaryFunction(value_type(I)) -> T
38I lower_bound_n_(I f, N n, const T& x, C c, P p) {
39 while (n != 0) {
40 N h = n >> 1;
41 I m = boost::next(f, h);
42
43 if (c(p(*m), x)) {
44 f = boost::next(m);
45 n -= h + N(1);
46 } else {
47 n = h;
48 }
49 }
50 return f;
51}
52
53/**************************************************************************************************/
54
55} // namespace implementation
56
57/**************************************************************************************************/
58
66
67/**************************************************************************************************/
68
69template <typename I, // I models ForwardIterator
70 typename N, // N models IntegralType
71 typename T>
72// T == value_type(I)
73inline I lower_bound_n(I f, N n, const T& x) {
74 return implementation::lower_bound_n_(f, n, x, less(), identity<T>());
75}
76
77/**************************************************************************************************/
78
79template <typename I, // I models FowardIterator
80 typename N, // N models IntegralType
81 typename T, // T == value_type(I)
82 typename C>
83// C models StrictWeakOrdering(T, T)
84inline I lower_bound_n(I f, N n, const T& x, C c) {
85 return implementation::lower_bound_n_(
86 f, n, x, std::bind(c, std::placeholders::_1, std::placeholders::_2), identity<T>());
87}
88
89/**************************************************************************************************/
90
91template <typename I, // I models ForwardIterator
92 typename N, // N models IntegralType
93 typename T, // T == result_type(P)
94 typename C, // C models StrictWeakOrdering(T, T)
95 typename P>
96// P models UnaryFunction(value_type(I)) -> T
97inline I lower_bound_n(I f, N n, const T& x, C c, P p) {
98 return implementation::lower_bound_n_(
99 f, n, x, std::bind(c, std::placeholders::_1, std::placeholders::_2),
100 std::bind(p, std::placeholders::_1));
101}
102
103/**************************************************************************************************/
104
105/*
106 NOTE (sparent) : These functions collide with the std functions when called unqualified as
107 is done by std::equal_range with VC++. We hide them from ADL by moving them into the
108 fn namespace.
109*/
110
111namespace fn {}
112using namespace fn;
113namespace fn {
114
115/**************************************************************************************************/
116
117template <typename I, // I models ForwardIterator
118 typename T>
119// T == value_type(I)
120inline I lower_bound(I f, I l, const T& x) {
121 return std::lower_bound(f, l, x);
122}
123
124/**************************************************************************************************/
125
126template <typename I, // I models FowardIterator
127 typename T, // T == value_type(I)
128 typename C>
129// C models StrictWeakOrdering(T, T)
130inline I lower_bound(I f, I l, const T& x, C c) {
131 return std::lower_bound(f, l, x, std::bind(c, std::placeholders::_1, std::placeholders::_2));
132}
133
134/**************************************************************************************************/
135
136template <typename I, // I models ForwardIterator
137 typename T, // T == result_type(P)
138 typename C, // C models StrictWeakOrdering(T, T)
139 typename P>
140// P models UnaryFunction(value_type(I)) -> T
141inline I lower_bound(I f, I l, const T& x, C c, P p) {
142 return lower_bound_n(f, std::distance(f, l), x, c, p);
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
152lower_bound(I& r, const T& x, C c, P p) {
153 return adobe::lower_bound(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
163lower_bound(const I& r, const T& x, C c, P p) {
164 return adobe::lower_bound(boost::begin(r), boost::end(r), x, c, p);
165}
166
167/**************************************************************************************************/
173template <class ForwardRange, class T>
174inline typename boost::range_iterator<ForwardRange>::type lower_bound(ForwardRange& range,
175 const T& value) {
176 return std::lower_bound(boost::begin(range), boost::end(range), value);
177}
178
184template <class ForwardRange, class T>
185inline typename boost::range_const_iterator<ForwardRange>::type
186lower_bound(const ForwardRange& range, const T& value) {
187 return std::lower_bound(boost::begin(range), boost::end(range), value);
188}
189
200template <typename I, class T, class Compare>
201inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_iterator<I>>::type
202lower_bound(I& range, const T& value, Compare comp) {
203 return adobe::lower_bound(boost::begin(range), boost::end(range), value, comp);
204}
205
211template <class I, class T, class Compare>
212inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_const_iterator<I>>::type
213lower_bound(const I& range, const T& value, Compare comp) {
214 return adobe::lower_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/**************************************************************************************************/
adobe::fn::lower_bound
I lower_bound(I f, I l, const T &x)
Definition lower_bound.hpp:120
adobe::lower_bound_n
I lower_bound_n(I f, N n, const T &x)
Definition lower_bound.hpp:73