Adobe Source Libraries 1.49.0
A collection of C++ libraries.
Loading...
Searching...
No Matches
upper_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_UPPER_BOUND_HPP
9#define ADOBE_ALGORITHM_UPPER_BOUND_HPP
10
11#include <adobe/config.hpp>
12
13#include <algorithm>
14#include <cassert>
15#include <functional>
16#include <iterator>
17#include <type_traits>
18
19#include <boost/next_prior.hpp>
20#include <boost/range/begin.hpp>
21#include <boost/range/end.hpp>
22#include <boost/utility/enable_if.hpp>
23
24#include <adobe/functional.hpp>
25
26/**************************************************************************************************/
27
28namespace adobe {
29namespace implementation {
30
31/**************************************************************************************************/
32
33template <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>
38// P models UnaryFunction(value_type(I)) -> T
39I upper_bound_n(I f, N n, const T& x, C c, P p) {
40 assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
41
42 while (n != 0) {
43 N h = n >> 1;
44
45 I m = boost::next(f, h);
46
47 if (!c(x, p(*m))) {
48 f = boost::next(m);
49 n -= h + N(1);
50 } else {
51 n = h;
52 }
53 }
54 return f;
55}
56
57/**************************************************************************************************/
58
59} // namespace implementation
60
61/**************************************************************************************************/
62
70
71/**************************************************************************************************/
72
73template <typename I, // I models ForwardIterator
74 typename N, // N models IntegralType
75 typename T>
76// T == value_type(I)
77inline I upper_bound_n(I f, N n, const T& x) {
78 return implementation::upper_bound_n(f, n, x, less(), identity<T>());
79}
80
81/**************************************************************************************************/
82
83template <typename I, // I models FowardIterator
84 typename N, // N models IntegralType
85 typename T, // T == value_type(I)
86 typename C>
87// C models StrictWeakOrdering(T, T)
88inline I upper_bound_n(I f, N n, const T& x, C c) {
89 return implementation::upper_bound_n(
90 f, n, x, std::bind(c, std::placeholders::_1, std::placeholders::_2), identity<T>());
91}
92
93/**************************************************************************************************/
94
95template <typename I, // I models ForwardIterator
96 typename N, // N models IntegralType
97 typename T, // T == result_type(P)
98 typename C, // C models StrictWeakOrdering(T, T)
99 typename P>
100// P models UnaryFunction(value_type(I)) -> T
101inline I upper_bound_n(I f, N n, const T& x, C c, P p) {
102 return implementation::upper_bound_n(f, n, x,
103 std::bind(c, std::placeholders::_1, std::placeholders::_2),
104 std::bind(p, std::placeholders::_1));
105}
106
107/**************************************************************************************************/
108
109/*
110 NOTE (sparent) : These functions collide with the std functions when called unqualified as
111 is done by std::equal_range with VC++. We hide them from ADL by moving them into the
112 fn namespace.
113*/
114
115namespace fn {}
116using namespace fn;
117namespace fn {
118
119/**************************************************************************************************/
120
121template <typename I, // I models ForwardIterator
122 typename T>
123// T == value_type(I)
124inline I upper_bound(I f, I l, const T& x) {
125 return std::upper_bound(f, l, x);
126}
127
128/**************************************************************************************************/
129
130template <typename I, // I models FowardIterator
131 typename T, // T == value_type(I)
132 typename C>
133// C models StrictWeakOrdering(T, T)
134inline I upper_bound(I f, I l, const T& x, C c) {
135 return std::upper_bound(f, l, x, std::bind(c, std::placeholders::_1, std::placeholders::_2));
136}
137
138/**************************************************************************************************/
139
140template <typename I, // I models ForwardIterator
141 typename T, // T == result_type(P)
142 typename C, // C models StrictWeakOrdering(T, T)
143 typename P>
144// P models UnaryFunction(value_type(I)) -> T
145inline I upper_bound(I f, I l, const T& x, C c, P p) {
146 return upper_bound_n(f, std::distance(f, l), x, c, p);
147}
148
149/**************************************************************************************************/
150
151template <typename I, // I models ForwardRange
152 typename T, // T == result_type(P)
153 typename C, // C models StrictWeakOrdering(T, T)
154 typename P> // P models UnaryFunction(value_type(I)) -> T
155inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_iterator<I>>::type
156upper_bound(I& r, const T& x, C c, P p) {
157 return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p);
158}
159
160/**************************************************************************************************/
161
162template <typename I, // I models ForwardRange
163 typename T, // T == result_type(P)
164 typename C, // C models StrictWeakOrdering(T, T)
165 typename P> // P models UnaryFunction(value_type(I)) -> T
166inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_const_iterator<I>>::type
167upper_bound(const I& r, const T& x, C c, P p) {
168 return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p);
169}
170
171/**************************************************************************************************/
177template <class ForwardRange, class T>
178inline typename boost::range_iterator<ForwardRange>::type upper_bound(ForwardRange& range,
179 const T& value) {
180 return std::upper_bound(boost::begin(range), boost::end(range), value);
181}
182
188template <class ForwardRange, class T>
189inline typename boost::range_const_iterator<ForwardRange>::type
190upper_bound(const ForwardRange& range, const T& value) {
191 return std::upper_bound(boost::begin(range), boost::end(range), value);
192}
193
204template <typename I, class T, class Compare>
205inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_iterator<I>>::type
206upper_bound(I& range, const T& value, Compare comp) {
207 return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
208}
209
215template <class I, class T, class Compare>
216inline typename boost::lazy_disable_if<std::is_same<I, T>, boost::range_const_iterator<I>>::type
217upper_bound(const I& range, const T& value, Compare comp) {
218 return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
219}
220
221/**************************************************************************************************/
222
223} // namespace fn
224} // namespace adobe
225
226/**************************************************************************************************/
227
228#endif
229
230/**************************************************************************************************/
adobe::fn::upper_bound
I upper_bound(I f, I l, const T &x)
Definition upper_bound.hpp:124
adobe::upper_bound_n
I upper_bound_n(I f, N n, const T &x)
Definition upper_bound.hpp:77