Horizon
Loading...
Searching...
No Matches
search.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13//===----------------------------------------------------------------------===//
14//
15// The LLVM Compiler Infrastructure
16//
17// This file is dual licensed under the MIT and the University of Illinois Open
18// Source Licenses. See LICENSE.TXT for details.
19//
20//===----------------------------------------------------------------------===//
21#ifndef RANGES_V3_ALGORITHM_SEARCH_HPP
22#define RANGES_V3_ALGORITHM_SEARCH_HPP
23
24#include <meta/meta.hpp>
25
26#include <range/v3/range_fwd.hpp>
27
28#include <range/v3/functional/comparisons.hpp>
29#include <range/v3/functional/identity.hpp>
30#include <range/v3/functional/invoke.hpp>
31#include <range/v3/iterator/concepts.hpp>
32#include <range/v3/iterator/operations.hpp>
33#include <range/v3/iterator/traits.hpp>
34#include <range/v3/range/access.hpp>
35#include <range/v3/range/concepts.hpp>
36#include <range/v3/range/primitives.hpp>
37#include <range/v3/range/traits.hpp>
38#include <range/v3/utility/static_const.hpp>
39#include <range/v3/view/subrange.hpp>
40
41#include <range/v3/detail/prologue.hpp>
42
43namespace ranges
44{
47
49 namespace detail
50 {
51 template<typename I1, typename S1, typename D1, typename I2, typename S2,
52 typename D2, typename C, typename P1, typename P2>
53 constexpr subrange<I1> search_sized_impl(I1 const begin1_,
54 S1 end1,
55 D1 const d1_,
56 I2 begin2,
57 S2 end2,
58 D2 d2,
59 C & pred,
60 P1 & proj1,
61 P2 & proj2)
62 {
63 D1 d1 = d1_;
64 auto begin1 = uncounted(begin1_);
65 while(true)
66 {
67 // Find first element in sequence 1 that matches *begin2, with a mininum
68 // of loop checks
69 while(true)
70 {
71 if(d1 < d2) // return the last if we've run out of room
72 {
73 auto e =
74 ranges::next(recounted(begin1_, std::move(begin1), d1_ - d1),
75 std::move(end1));
76 return {e, e};
77 }
78 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
79 break;
80 ++begin1;
81 --d1;
82 }
83 // *begin1 matches *begin2, now match elements after here
84 auto m1 = begin1;
85 I2 m2 = begin2;
86 while(true)
87 {
88 if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
89 // for 1 element pattern)
90 {
91 return {recounted(begin1_, std::move(begin1), d1_ - d1),
92 recounted(begin1_, std::move(++m1), d1_ - d1)};
93 }
94 ++m1; // No need to check, we know we have room to match successfully
95 if(!invoke(
96 pred,
97 invoke(proj1, *m1),
98 invoke(
99 proj2,
100 *m2))) // if there is a mismatch, restart with a new begin1
101 {
102 ++begin1;
103 --d1;
104 break;
105 } // else there is a match, check next elements
106 }
107 }
108 }
109
110 template<typename I1, typename S1, typename I2, typename S2, typename C,
111 typename P1, typename P2>
112 constexpr subrange<I1> search_impl(I1 begin1,
113 S1 end1,
114 I2 begin2,
115 S2 end2,
116 C & pred,
117 P1 & proj1,
118 P2 & proj2)
119 {
120 while(true)
121 {
122 // Find first element in sequence 1 that matches *begin2, with a mininum
123 // of loop checks
124 while(true)
125 {
126 if(begin1 == end1) // return end1 if no element matches *begin2
127 return {begin1, begin1};
128 if(invoke(pred, invoke(proj1, *begin1), invoke(proj2, *begin2)))
129 break;
130 ++begin1;
131 }
132 // *begin1 matches *begin2, now match elements after here
133 I1 m1 = begin1;
134 I2 m2 = begin2;
135 while(true)
136 {
137 if(++m2 == end2) // If pattern exhausted, begin1 is the answer (works
138 // for 1 element pattern)
139 return {begin1, ++m1};
140 if(++m1 == end1) // Otherwise if source exhausted, pattern not found
141 return {m1, m1};
142 if(!invoke(
143 pred,
144 invoke(proj1, *m1),
145 invoke(
146 proj2,
147 *m2))) // if there is a mismatch, restart with a new begin1
148 {
149 ++begin1;
150 break;
151 } // else there is a match, check next elements
152 }
153 }
154 }
155 } // namespace detail
157
158 RANGES_FUNC_BEGIN(search)
159
160
161 template(typename I1,
162 typename S1,
163 typename I2,
164 typename S2,
165 typename C = equal_to,
166 typename P1 = identity,
167 typename P2 = identity)(
168 requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
169 forward_iterator<I2> AND sentinel_for<S2, I2> AND
170 indirectly_comparable<I1, I2, C, P1, P2>)
171 constexpr subrange<I1> RANGES_FUNC(search)(I1 begin1,
172 S1 end1,
173 I2 begin2,
174 S2 end2,
175 C pred = C{},
176 P1 proj1 = P1{},
177 P2 proj2 = P2{}) //
178 {
179 if(begin2 == end2)
180 return {begin1, begin1};
181 if(RANGES_CONSTEXPR_IF(sized_sentinel_for<S1, I1> &&
182 sized_sentinel_for<S2, I2>))
183 return detail::search_sized_impl(std::move(begin1),
184 std::move(end1),
185 distance(begin1, end1),
186 std::move(begin2),
187 std::move(end2),
188 distance(begin2, end2),
189 pred,
190 proj1,
191 proj2);
192 else
193 return detail::search_impl(std::move(begin1),
194 std::move(end1),
195 std::move(begin2),
196 std::move(end2),
197 pred,
198 proj1,
199 proj2);
200 }
201
203 template(typename Rng1,
204 typename Rng2,
205 typename C = equal_to,
206 typename P1 = identity,
207 typename P2 = identity)(
208 requires forward_range<Rng1> AND forward_range<Rng2> AND
209 indirectly_comparable<iterator_t<Rng1>, iterator_t<Rng2>, C, P1, P2>)
210 constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(search)(
211 Rng1 && rng1, Rng2 && rng2, C pred = C{}, P1 proj1 = P1{}, P2 proj2 = P2{}) //
212 {
213 if(empty(rng2))
214 return subrange<iterator_t<Rng1>>{begin(rng1), begin(rng1)};
215 if(RANGES_CONSTEXPR_IF(sized_range<Rng1> && sized_range<Rng2>))
216 return detail::search_sized_impl(begin(rng1),
217 end(rng1),
218 distance(rng1),
219 begin(rng2),
220 end(rng2),
221 distance(rng2),
222 pred,
223 proj1,
224 proj2);
225 else
226 return detail::search_impl(
227 begin(rng1), end(rng1), begin(rng2), end(rng2), pred, proj1, proj2);
228 }
229
230 RANGES_FUNC_END(search)
231
232 namespace cpp20
233 {
234 using ranges::search;
235 }
237} // namespace ranges
238
239#include <range/v3/detail/epilogue.hpp>
240
241#endif
ranges::forward_iterator
The forward_iterator concept.
ranges::forward_range
The forward_range concept.
ranges::indirectly_comparable
The indirectly_comparable concept.
ranges::sentinel_for
The sentinel_for concept.
ranges::sized_range
The sized_range concept.
ranges::sized_sentinel_for
The sized_sentinel_for concept.
ranges::iterator_t
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
meta::invoke
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
meta::empty
bool_< 0==size< L >::type::value > empty
An Boolean integral constant wrapper around true if L is an empty type list; false,...
Definition meta.hpp:2231
meta.hpp
Tiny meta-programming library.
ranges::cpp20
Definition adjacent_find.hpp:67
range_fwd.hpp
ranges::equal_to
Definition comparisons.hpp:28
ranges::identity
Definition identity.hpp:25
ranges::subrange
Definition subrange.hpp:196
Generated by doxygen 1.15.0