Adobe Source Libraries 1.49.0
A collection of C++ libraries.
Loading...
Searching...
No Matches
equal_range.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_EQUAL_RANGE_HPP
9#define ADOBE_ALGORITHM_EQUAL_RANGE_HPP
10
11#include <adobe/config.hpp>
12
13#include <algorithm>
14#include <cassert>
15#include <functional>
16#include <type_traits>
17#include <utility>
18
19#include <boost/next_prior.hpp>
20#include <boost/range/begin.hpp>
21#include <boost/range/end.hpp>
22
23#include <adobe/algorithm/lower_bound.hpp>
24#include <adobe/algorithm/upper_bound.hpp>
25#include <adobe/functional.hpp>
26
27/**************************************************************************************************/
28
36
37/**************************************************************************************************/
38
39namespace adobe {
40namespace implementation {
41
42/**************************************************************************************************/
43
44template <typename I, // I models ForwardIterator
45 typename N, // N models IntegralType
46 typename T, // T == result_type(P)
47 typename C, // C models StrictWeakOrdering(T, T)
48 typename P>
49// P models UnaryFunction(value_type(I)) -> T
50std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p) {
51 assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
52
53 while (n != 0) {
54 N h = n >> 1;
55 I m = boost::next(f, h);
56
57 if (c(p(*m), x)) {
58 f = boost::next(m);
59 n -= h + 1;
60 } else if (c(x, p(*m))) {
61 n = h;
62 } else {
63 return std::make_pair(
64 implementation::lower_bound_n_(f, h, x, c, p),
65 implementation::upper_bound_n(boost::next(m), n - (h + 1), x, c, p));
66 }
67 }
68 return std::make_pair(f, f);
69}
70
71/**************************************************************************************************/
72
73template <typename I> // I models ForwardRange
74struct lazy_range {
75 typedef std::pair<typename boost::range_iterator<I>::type,
76 typename boost::range_iterator<I>::type>
77 type;
78};
79
80/**************************************************************************************************/
81
82template <typename I> // I models ForwardRange
83struct lazy_range_const {
84 typedef std::pair<typename boost::range_const_iterator<I>::type,
85 typename boost::range_const_iterator<I>::type>
86 type;
87};
88
89/**************************************************************************************************/
90
91} // namespace implementation
92
93/**************************************************************************************************/
94
98
99template <typename I, // I models ForwardIterator
100 typename N, // N models IntegralType
101 typename T>
102// T == result_type(P)
103inline std::pair<I, I> equal_range_n(I f, N n, const T& x) {
104 return implementation::equal_range_n(f, n, x, less(), identity<T>());
105}
106
107/**************************************************************************************************/
108
112
113template <typename I, // I models ForwardIterator
114 typename N, // N models IntegralType
115 typename T, // T == result_type(P)
116 typename C>
117// C models StrictWeakOrdering(T, T)
118inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c) {
119 return implementation::equal_range_n(
120 f, n, x, std::bind(c, std::placeholders::_1, std::placeholders::_2), identity<T>());
121}
122
123/**************************************************************************************************/
124
128
129template <typename I, // I models ForwardIterator
130 typename N, // N models IntegralType
131 typename T, // T == result_type(P)
132 typename C, // C models StrictWeakOrdering(T, T)
133 typename P>
134// P models UnaryFunction(value_type(I)) -> T
135inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p) {
136 return implementation::equal_range_n(f, n, x,
137 std::bind(c, std::placeholders::_1, std::placeholders::_2),
138 std::bind(p, std::placeholders::_1));
139}
140
141/**************************************************************************************************/
142
146
147template <typename I, // I models ForwardIterator
148 typename T>
149// T == value_type(I)
150inline std::pair<I, I> equal_range(I f, I l, const T& x) {
151 return std::equal_range(f, l, x);
152}
153
154/**************************************************************************************************/
155
159
160template <typename I, // I models ForwardIterator
161 typename T, // T == result_type(P)
162 typename C>
163// C models StrictWeakOrdering(T, T)
164inline std::pair<I, I> equal_range(I f, I l, const T& x, C c) {
165 return std::equal_range(f, l, x, std::bind(c, std::placeholders::_1, std::placeholders::_2));
166}
167
168/**************************************************************************************************/
169
173
174template <typename I, // I models ForwardIterator
175 typename T, // T == result_type(P)
176 typename C, // C models StrictWeakOrdering(T, T)
177 typename P>
178// P models UnaryFunction(value_type(I)) -> T
179inline std::pair<I, I> equal_range(I f, I l, const T& x, C c, P p) {
180 return equal_range_n(f, std::distance(f, l), x, c, p);
181}
182
183/**************************************************************************************************/
184
188
189template <typename I, // I models ForwardRange
190 typename T, // T == result_type(P)
191 typename C, // C models StrictWeakOrdering(T, T)
192 typename P> // P models UnaryFunction(value_type(I)) -> T
193inline typename boost::lazy_disable_if<std::is_same<I, T>, implementation::lazy_range<I>>::type
194equal_range(I& r, const T& x, C c, P p) {
195 return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p);
196}
197
198/**************************************************************************************************/
199
203
204template <typename I, // I models ForwardRange
205 typename T, // T == result_type(P)
206 typename C, // C models StrictWeakOrdering(T, T)
207 typename P> // P models UnaryFunction(value_type(I)) -> T
208inline
209 typename boost::lazy_disable_if<std::is_same<I, T>, implementation::lazy_range_const<I>>::type
210 equal_range(const I& r, const T& x, C c, P p) {
211 return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p);
212}
213
214/**************************************************************************************************/
215
219
220template <typename I, // I models ForwardRange
221 typename T> // T == result_type(P)
222inline std::pair<typename boost::range_iterator<I>::type, typename boost::range_iterator<I>::type>
223equal_range(I& r, const T& x) {
224 return std::equal_range(boost::begin(r), boost::end(r), x);
225}
226
227/**************************************************************************************************/
228
232
233template <typename I, // I models ForwardRange
234 typename T> // T == result_type(P)
235inline std::pair<typename boost::range_const_iterator<I>::type,
236 typename boost::range_const_iterator<I>::type>
237equal_range(const I& r, const T& x) {
238 return std::equal_range(boost::begin(r), boost::end(r), x);
239}
240
241/**************************************************************************************************/
242
246
247template <typename I, // I models ForwardRange
248 typename T, // T == result_type(P)
249 typename C> // C models StrictWeakOrdering(T, T)
250inline typename boost::lazy_disable_if<std::is_same<I, T>, implementation::lazy_range<I>>::type
251equal_range(I& r, const T& x, C c) {
252 return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
253}
254
255/**************************************************************************************************/
256
260
261template <typename I, // I models ForwardRange
262 typename T, // T == result_type(P)
263 typename C> // C models StrictWeakOrdering(T, T)
264inline
265 typename boost::lazy_disable_if<std::is_same<I, T>, implementation::lazy_range_const<I>>::type
266 equal_range(const I& r, const T& x, C c) {
267 return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
268}
269
270/**************************************************************************************************/
271
272} // namespace adobe
273
274/**************************************************************************************************/
275
276#endif
277
278/**************************************************************************************************/
adobe::equal_range_n
std::pair< I, I > equal_range_n(I f, N n, const T &x)
Definition equal_range.hpp:103
adobe::equal_range
std::pair< I, I > equal_range(I f, I l, const T &x)
Definition equal_range.hpp:150
lower_bound.hpp
upper_bound.hpp