Horizon
Loading...
Searching...
No Matches
find_end.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#ifndef RANGES_V3_ALGORITHM_FIND_END_HPP
14#define RANGES_V3_ALGORITHM_FIND_END_HPP
15
16#include <utility>
17
18#include <meta/meta.hpp>
19
21
31#include <range/v3/utility/static_const.hpp>
33
34#include <range/v3/detail/prologue.hpp>
35
36namespace ranges
37{
39 namespace detail
40 {
41 template(typename I, typename S)(
42 requires input_iterator<I> AND sentinel_for<S, I>)
43 constexpr I next_to_if(I i, S s, std::true_type)
44 {
45 return ranges::next(i, s);
46 }
47
48 template(typename I, typename S)(
49 requires input_iterator<I> AND sentinel_for<S, I>)
50 constexpr S next_to_if(I, S s, std::false_type)
51 {
52 return s;
53 }
54
55 template(bool B, typename I, typename S)(
56 requires input_iterator<I> AND sentinel_for<S, I>)
57 constexpr meta::if_c<B, I, S> next_to_if(I i, S s)
58 {
59 return detail::next_to_if(std::move(i), std::move(s), meta::bool_<B>{});
60 }
61
62 template<typename I1, typename S1, typename I2, typename S2, typename R,
63 typename P>
64 constexpr subrange<I1> find_end_impl(I1 begin1, S1 end1, I2 begin2, S2 end2, R pred, P proj,
65 std::forward_iterator_tag, std::forward_iterator_tag)
66 {
67 bool found = false;
68 I1 res_begin, res_end;
69 if(begin2 == end2)
70 {
71 auto e1 = ranges::next(begin1, end1);
72 return {e1, e1};
73 }
74 while(true)
75 {
76 while(true)
77 {
78 if(begin1 == end1)
79 return {(found ? res_begin : begin1), (found ? res_end : begin1)};
80 if(invoke(pred, invoke(proj, *begin1), *begin2))
81 break;
82 ++begin1;
83 }
84 auto tmp1 = begin1;
85 auto tmp2 = begin2;
86 while(true)
87 {
88 if(++tmp2 == end2)
89 {
90 res_begin = begin1++;
91 res_end = ++tmp1;
92 found = true;
93 break;
94 }
95 if(++tmp1 == end1)
96 return {(found ? res_begin : tmp1), (found ? res_end : tmp1)};
97 if(!invoke(pred, invoke(proj, *tmp1), *tmp2))
98 {
99 ++begin1;
100 break;
101 }
102 }
103 }
104 }
105
106 template<typename I1, typename I2, typename R, typename P>
107 constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
108 std::bidirectional_iterator_tag,
109 std::bidirectional_iterator_tag)
110 {
111 // modeled after search algorithm (in reverse)
112 if(begin2 == end2)
113 return {end1, end1}; // Everything matches an empty sequence
114 I1 l1 = end1;
115 I2 l2 = end2;
116 --l2;
117 while(true)
118 {
119 // Find end element in sequence 1 that matches *(end2-1), with a mininum
120 // of loop checks
121 do
122 // return {end1,end1} if no element matches *begin2
123 if(begin1 == l1)
124 return {end1, end1};
125 while(!invoke(pred, invoke(proj, *--l1), *l2));
126 // *l1 matches *l2, now match elements before here
127 I1 m1 = l1;
128 I2 m2 = l2;
129 do
130 // If pattern exhausted, {m1,++l1} is the answer
131 // (works for 1 element pattern)
132 if(m2 == begin2)
133 return {m1, ++l1};
134 // Otherwise if source exhausted, pattern not found
135 else if(m1 == begin1)
136 return {end1, end1};
137 // if there is a mismatch, restart with a new l1
138 // else there is a match, check next elements
139 while(invoke(pred, invoke(proj, *--m1), *--m2));
140 }
141 }
142
143 template<typename I1, typename I2, typename R, typename P>
144 constexpr subrange<I1> find_end_impl(I1 begin1, I1 end1, I2 begin2, I2 end2, R pred, P proj,
145 std::random_access_iterator_tag,
146 std::random_access_iterator_tag)
147 {
148 // Take advantage of knowing source and pattern lengths. Stop short when
149 // source is smaller than pattern
150 auto len2 = end2 - begin2;
151 if(len2 == 0)
152 return {end1, end1};
153 auto len1 = end1 - begin1;
154 if(len1 < len2)
155 return {end1, end1};
156 I1 const start =
157 begin1 + (len2 - 1); // End of pattern match can't go before here
158 I1 l1 = end1;
159 I2 l2 = end2;
160 --l2;
161 while(true)
162 {
163 do
164 if(start == l1)
165 return {end1, end1};
166 while(!invoke(pred, invoke(proj, *--l1), *l2));
167 I1 m1 = l1;
168 I2 m2 = l2;
169 do
170 if(m2 == begin2)
171 return {m1, ++l1};
172 // no need to check range on m1 because s guarantees we have enough source
173 while(invoke(pred, invoke(proj, *--m1), *--m2));
174 }
175 }
176 } // namespace detail
178
181 RANGES_FUNC_BEGIN(find_end)
182
183
184 template(typename I1,
185 typename S1,
186 typename I2,
187 typename S2,
188 typename R = equal_to,
189 typename P = identity)(
190 requires forward_iterator<I1> AND sentinel_for<S1, I1> AND
191 forward_iterator<I2> AND sentinel_for<S2, I2> AND
192 indirect_relation<R, projected<I1, P>, I2>)
193 constexpr subrange<I1> RANGES_FUNC(find_end)(
194 I1 begin1, S1 end1, I2 begin2, S2 end2, R pred = R{}, P proj = P{}) //
195 {
196 constexpr bool Bidi =
197 bidirectional_iterator<I1> && bidirectional_iterator<I2>;
198 return detail::find_end_impl(begin1,
199 detail::next_to_if<Bidi>(begin1, end1),
200 begin2,
201 detail::next_to_if<Bidi>(begin2, end2),
202 std::move(pred),
203 std::move(proj),
204 iterator_tag_of<I1>(),
205 iterator_tag_of<I2>());
206 }
207
209 template(typename Rng1,
210 typename Rng2,
211 typename R = equal_to,
212 typename P = identity)(
215 constexpr borrowed_subrange_t<Rng1> RANGES_FUNC(find_end)(
216 Rng1 && rng1, Rng2 && rng2, R pred = R{}, P proj = P{}) //
217 {
218 return (*this)(begin(rng1),
219 end(rng1),
220 begin(rng2),
221 end(rng2),
222 std::move(pred),
223 std::move(proj));
224 }
225
226 RANGES_FUNC_END(find_end)
227
228 namespace cpp20
229 {
230 using ranges::find_end;
231 }
233} // namespace ranges
234
235#include <range/v3/detail/epilogue.hpp>
236
237#endif
The forward_iterator concept.
The forward_range concept.
The indirect_relation concept.
The sentinel_for concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition meta.hpp:168
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition meta.hpp:541
Tiny meta-programming library.
Definition comparisons.hpp:28
Definition identity.hpp:25
Definition subrange.hpp:196