]>
Commit | Line | Data |
---|---|---|
160061ac JW |
1 | // Utilities for representing and manipulating ranges -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2019-2022 Free Software Foundation, Inc. |
160061ac JW |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 3, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // Under Section 7 of GPL version 3, you are granted additional | |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
24 | ||
25 | /** @file bits/ranges_util.h | |
26 | * This is an internal header file, included by other library headers. | |
27 | * Do not attempt to use it directly. @headername{ranges} | |
28 | */ | |
29 | ||
30 | #ifndef _RANGES_UTIL_H | |
31 | #define _RANGES_UTIL_H 1 | |
32 | ||
33 | #if __cplusplus > 201703L | |
34 | # include <bits/ranges_base.h> | |
261d5a4a | 35 | # include <bits/utility.h> |
160061ac JW |
36 | |
37 | #ifdef __cpp_lib_ranges | |
38 | namespace std _GLIBCXX_VISIBILITY(default) | |
39 | { | |
40 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
41 | namespace ranges | |
42 | { | |
43 | // C++20 24.5 [range.utility] Range utilities | |
44 | ||
45 | namespace __detail | |
46 | { | |
47 | template<typename _Range> | |
48 | concept __simple_view = view<_Range> && range<const _Range> | |
49 | && same_as<iterator_t<_Range>, iterator_t<const _Range>> | |
50 | && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>; | |
51 | ||
52 | template<typename _It> | |
53 | concept __has_arrow = input_iterator<_It> | |
54 | && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); }); | |
55 | ||
56 | template<typename _Tp, typename _Up> | |
c09cabb2 | 57 | concept __different_from |
160061ac JW |
58 | = !same_as<remove_cvref_t<_Tp>, remove_cvref_t<_Up>>; |
59 | } // namespace __detail | |
60 | ||
61 | /// The ranges::view_interface class template | |
62 | template<typename _Derived> | |
63 | requires is_class_v<_Derived> && same_as<_Derived, remove_cv_t<_Derived>> | |
53b1c382 | 64 | class view_interface |
160061ac JW |
65 | { |
66 | private: | |
67 | constexpr _Derived& _M_derived() noexcept | |
68 | { | |
69 | static_assert(derived_from<_Derived, view_interface<_Derived>>); | |
70 | static_assert(view<_Derived>); | |
71 | return static_cast<_Derived&>(*this); | |
72 | } | |
73 | ||
74 | constexpr const _Derived& _M_derived() const noexcept | |
75 | { | |
76 | static_assert(derived_from<_Derived, view_interface<_Derived>>); | |
77 | static_assert(view<_Derived>); | |
78 | return static_cast<const _Derived&>(*this); | |
79 | } | |
80 | ||
9245b0e8 JW |
81 | static constexpr bool |
82 | _S_bool(bool) noexcept; // not defined | |
83 | ||
84 | template<typename _Tp> | |
85 | static constexpr bool | |
86 | _S_empty(_Tp& __t) | |
87 | noexcept(noexcept(_S_bool(ranges::begin(__t) == ranges::end(__t)))) | |
88 | { return ranges::begin(__t) == ranges::end(__t); } | |
89 | ||
90 | template<typename _Tp> | |
91 | static constexpr auto | |
92 | _S_size(_Tp& __t) | |
93 | noexcept(noexcept(ranges::end(__t) - ranges::begin(__t))) | |
94 | { return ranges::end(__t) - ranges::begin(__t); } | |
95 | ||
160061ac JW |
96 | public: |
97 | constexpr bool | |
9245b0e8 JW |
98 | empty() |
99 | noexcept(noexcept(_S_empty(_M_derived()))) | |
100 | requires forward_range<_Derived> | |
101 | { return _S_empty(_M_derived()); } | |
160061ac JW |
102 | |
103 | constexpr bool | |
9245b0e8 JW |
104 | empty() const |
105 | noexcept(noexcept(_S_empty(_M_derived()))) | |
106 | requires forward_range<const _Derived> | |
107 | { return _S_empty(_M_derived()); } | |
160061ac JW |
108 | |
109 | constexpr explicit | |
9245b0e8 JW |
110 | operator bool() noexcept(noexcept(ranges::empty(_M_derived()))) |
111 | requires requires { ranges::empty(_M_derived()); } | |
160061ac JW |
112 | { return !ranges::empty(_M_derived()); } |
113 | ||
114 | constexpr explicit | |
9245b0e8 JW |
115 | operator bool() const noexcept(noexcept(ranges::empty(_M_derived()))) |
116 | requires requires { ranges::empty(_M_derived()); } | |
160061ac JW |
117 | { return !ranges::empty(_M_derived()); } |
118 | ||
119 | constexpr auto | |
9245b0e8 JW |
120 | data() noexcept(noexcept(ranges::begin(_M_derived()))) |
121 | requires contiguous_iterator<iterator_t<_Derived>> | |
122 | { return std::to_address(ranges::begin(_M_derived())); } | |
160061ac JW |
123 | |
124 | constexpr auto | |
9245b0e8 | 125 | data() const noexcept(noexcept(ranges::begin(_M_derived()))) |
160061ac JW |
126 | requires range<const _Derived> |
127 | && contiguous_iterator<iterator_t<const _Derived>> | |
9245b0e8 | 128 | { return std::to_address(ranges::begin(_M_derived())); } |
160061ac JW |
129 | |
130 | constexpr auto | |
9245b0e8 | 131 | size() noexcept(noexcept(_S_size(_M_derived()))) |
160061ac JW |
132 | requires forward_range<_Derived> |
133 | && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>> | |
9245b0e8 | 134 | { return _S_size(_M_derived()); } |
160061ac JW |
135 | |
136 | constexpr auto | |
9245b0e8 | 137 | size() const noexcept(noexcept(_S_size(_M_derived()))) |
160061ac JW |
138 | requires forward_range<const _Derived> |
139 | && sized_sentinel_for<sentinel_t<const _Derived>, | |
140 | iterator_t<const _Derived>> | |
9245b0e8 | 141 | { return _S_size(_M_derived()); } |
160061ac JW |
142 | |
143 | constexpr decltype(auto) | |
144 | front() requires forward_range<_Derived> | |
145 | { | |
146 | __glibcxx_assert(!empty()); | |
147 | return *ranges::begin(_M_derived()); | |
148 | } | |
149 | ||
150 | constexpr decltype(auto) | |
151 | front() const requires forward_range<const _Derived> | |
152 | { | |
153 | __glibcxx_assert(!empty()); | |
154 | return *ranges::begin(_M_derived()); | |
155 | } | |
156 | ||
157 | constexpr decltype(auto) | |
158 | back() | |
159 | requires bidirectional_range<_Derived> && common_range<_Derived> | |
160 | { | |
161 | __glibcxx_assert(!empty()); | |
162 | return *ranges::prev(ranges::end(_M_derived())); | |
163 | } | |
164 | ||
165 | constexpr decltype(auto) | |
166 | back() const | |
167 | requires bidirectional_range<const _Derived> | |
168 | && common_range<const _Derived> | |
169 | { | |
170 | __glibcxx_assert(!empty()); | |
171 | return *ranges::prev(ranges::end(_M_derived())); | |
172 | } | |
173 | ||
174 | template<random_access_range _Range = _Derived> | |
175 | constexpr decltype(auto) | |
176 | operator[](range_difference_t<_Range> __n) | |
177 | { return ranges::begin(_M_derived())[__n]; } | |
178 | ||
179 | template<random_access_range _Range = const _Derived> | |
180 | constexpr decltype(auto) | |
181 | operator[](range_difference_t<_Range> __n) const | |
182 | { return ranges::begin(_M_derived())[__n]; } | |
183 | }; | |
184 | ||
185 | namespace __detail | |
186 | { | |
98af6b86 PP |
187 | template<typename _From, typename _To> |
188 | concept __uses_nonqualification_pointer_conversion | |
189 | = is_pointer_v<_From> && is_pointer_v<_To> | |
190 | && !convertible_to<remove_pointer_t<_From>(*)[], | |
191 | remove_pointer_t<_To>(*)[]>; | |
192 | ||
193 | template<typename _From, typename _To> | |
160061ac | 194 | concept __convertible_to_non_slicing = convertible_to<_From, _To> |
98af6b86 PP |
195 | && !__uses_nonqualification_pointer_conversion<decay_t<_From>, |
196 | decay_t<_To>>; | |
160061ac JW |
197 | |
198 | template<typename _Tp> | |
199 | concept __pair_like | |
200 | = !is_reference_v<_Tp> && requires(_Tp __t) | |
201 | { | |
202 | typename tuple_size<_Tp>::type; | |
203 | requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>; | |
204 | typename tuple_element_t<0, remove_const_t<_Tp>>; | |
205 | typename tuple_element_t<1, remove_const_t<_Tp>>; | |
206 | { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>; | |
207 | { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>; | |
208 | }; | |
209 | ||
210 | template<typename _Tp, typename _Up, typename _Vp> | |
211 | concept __pair_like_convertible_from | |
212 | = !range<_Tp> && __pair_like<_Tp> | |
213 | && constructible_from<_Tp, _Up, _Vp> | |
214 | && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> | |
215 | && convertible_to<_Vp, tuple_element_t<1, _Tp>>; | |
216 | ||
160061ac JW |
217 | } // namespace __detail |
218 | ||
9626e447 PP |
219 | namespace views { struct _Drop; } // defined in <ranges> |
220 | ||
160061ac JW |
221 | enum class subrange_kind : bool { unsized, sized }; |
222 | ||
223 | /// The ranges::subrange class template | |
224 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It, | |
225 | subrange_kind _Kind = sized_sentinel_for<_Sent, _It> | |
226 | ? subrange_kind::sized : subrange_kind::unsized> | |
227 | requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>) | |
228 | class subrange : public view_interface<subrange<_It, _Sent, _Kind>> | |
229 | { | |
230 | private: | |
9626e447 | 231 | static constexpr bool _S_store_size |
160061ac JW |
232 | = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; |
233 | ||
9626e447 PP |
234 | friend struct views::_Drop; // Needs to inspect _S_store_size. |
235 | ||
160061ac | 236 | _It _M_begin = _It(); |
620db4ca | 237 | [[no_unique_address]] _Sent _M_end = _Sent(); |
160061ac | 238 | |
a88fc03b JW |
239 | using __size_type |
240 | = __detail::__make_unsigned_like_t<iter_difference_t<_It>>; | |
241 | ||
160061ac JW |
242 | template<typename, bool = _S_store_size> |
243 | struct _Size | |
244 | { }; | |
245 | ||
246 | template<typename _Tp> | |
247 | struct _Size<_Tp, true> | |
a88fc03b | 248 | { _Tp _M_size; }; |
160061ac | 249 | |
a88fc03b | 250 | [[no_unique_address]] _Size<__size_type> _M_size = {}; |
160061ac JW |
251 | |
252 | public: | |
4b4f5666 | 253 | subrange() requires default_initializable<_It> = default; |
160061ac JW |
254 | |
255 | constexpr | |
256 | subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) | |
9245b0e8 JW |
257 | noexcept(is_nothrow_constructible_v<_It, decltype(__i)> |
258 | && is_nothrow_constructible_v<_Sent, _Sent&>) | |
160061ac JW |
259 | requires (!_S_store_size) |
260 | : _M_begin(std::move(__i)), _M_end(__s) | |
261 | { } | |
262 | ||
263 | constexpr | |
264 | subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s, | |
a88fc03b | 265 | __size_type __n) |
9245b0e8 JW |
266 | noexcept(is_nothrow_constructible_v<_It, decltype(__i)> |
267 | && is_nothrow_constructible_v<_Sent, _Sent&>) | |
160061ac JW |
268 | requires (_Kind == subrange_kind::sized) |
269 | : _M_begin(std::move(__i)), _M_end(__s) | |
270 | { | |
160061ac JW |
271 | if constexpr (_S_store_size) |
272 | _M_size._M_size = __n; | |
273 | } | |
274 | ||
c09cabb2 | 275 | template<__detail::__different_from<subrange> _Rng> |
160061ac JW |
276 | requires borrowed_range<_Rng> |
277 | && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
278 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
279 | constexpr | |
9245b0e8 JW |
280 | subrange(_Rng&& __r) |
281 | noexcept(noexcept(subrange(__r, ranges::size(__r)))) | |
282 | requires _S_store_size && sized_range<_Rng> | |
a55cda89 | 283 | : subrange(__r, ranges::size(__r)) |
160061ac JW |
284 | { } |
285 | ||
c09cabb2 | 286 | template<__detail::__different_from<subrange> _Rng> |
160061ac JW |
287 | requires borrowed_range<_Rng> |
288 | && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
289 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
290 | constexpr | |
9245b0e8 JW |
291 | subrange(_Rng&& __r) |
292 | noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r)))) | |
293 | requires (!_S_store_size) | |
6e00d9bb | 294 | : subrange(ranges::begin(__r), ranges::end(__r)) |
160061ac JW |
295 | { } |
296 | ||
297 | template<borrowed_range _Rng> | |
298 | requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
299 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
300 | constexpr | |
a88fc03b | 301 | subrange(_Rng&& __r, __size_type __n) |
9245b0e8 | 302 | noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n))) |
160061ac JW |
303 | requires (_Kind == subrange_kind::sized) |
304 | : subrange{ranges::begin(__r), ranges::end(__r), __n} | |
305 | { } | |
306 | ||
c09cabb2 | 307 | template<__detail::__different_from<subrange> _PairLike> |
160061ac JW |
308 | requires __detail::__pair_like_convertible_from<_PairLike, const _It&, |
309 | const _Sent&> | |
a88fc03b JW |
310 | constexpr |
311 | operator _PairLike() const | |
312 | { return _PairLike(_M_begin, _M_end); } | |
160061ac JW |
313 | |
314 | constexpr _It | |
315 | begin() const requires copyable<_It> | |
316 | { return _M_begin; } | |
317 | ||
318 | [[nodiscard]] constexpr _It | |
319 | begin() requires (!copyable<_It>) | |
320 | { return std::move(_M_begin); } | |
321 | ||
322 | constexpr _Sent end() const { return _M_end; } | |
323 | ||
324 | constexpr bool empty() const { return _M_begin == _M_end; } | |
325 | ||
a88fc03b | 326 | constexpr __size_type |
160061ac JW |
327 | size() const requires (_Kind == subrange_kind::sized) |
328 | { | |
329 | if constexpr (_S_store_size) | |
330 | return _M_size._M_size; | |
331 | else | |
332 | return __detail::__to_unsigned_like(_M_end - _M_begin); | |
333 | } | |
334 | ||
335 | [[nodiscard]] constexpr subrange | |
336 | next(iter_difference_t<_It> __n = 1) const & | |
337 | requires forward_iterator<_It> | |
338 | { | |
339 | auto __tmp = *this; | |
340 | __tmp.advance(__n); | |
341 | return __tmp; | |
342 | } | |
343 | ||
344 | [[nodiscard]] constexpr subrange | |
345 | next(iter_difference_t<_It> __n = 1) && | |
346 | { | |
347 | advance(__n); | |
348 | return std::move(*this); | |
349 | } | |
350 | ||
351 | [[nodiscard]] constexpr subrange | |
352 | prev(iter_difference_t<_It> __n = 1) const | |
353 | requires bidirectional_iterator<_It> | |
354 | { | |
355 | auto __tmp = *this; | |
356 | __tmp.advance(-__n); | |
357 | return __tmp; | |
358 | } | |
359 | ||
360 | constexpr subrange& | |
361 | advance(iter_difference_t<_It> __n) | |
362 | { | |
363 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
364 | // 3433. subrange::advance(n) has UB when n < 0 | |
365 | if constexpr (bidirectional_iterator<_It>) | |
366 | if (__n < 0) | |
367 | { | |
368 | ranges::advance(_M_begin, __n); | |
369 | if constexpr (_S_store_size) | |
370 | _M_size._M_size += __detail::__to_unsigned_like(-__n); | |
371 | return *this; | |
372 | } | |
373 | ||
374 | __glibcxx_assert(__n >= 0); | |
375 | auto __d = __n - ranges::advance(_M_begin, __n, _M_end); | |
376 | if constexpr (_S_store_size) | |
377 | _M_size._M_size -= __detail::__to_unsigned_like(__d); | |
378 | return *this; | |
379 | } | |
380 | }; | |
381 | ||
382 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
383 | subrange(_It, _Sent) -> subrange<_It, _Sent>; | |
384 | ||
385 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
386 | subrange(_It, _Sent, | |
387 | __detail::__make_unsigned_like_t<iter_difference_t<_It>>) | |
388 | -> subrange<_It, _Sent, subrange_kind::sized>; | |
389 | ||
160061ac JW |
390 | template<borrowed_range _Rng> |
391 | subrange(_Rng&&) | |
392 | -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, | |
393 | (sized_range<_Rng> | |
394 | || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>) | |
395 | ? subrange_kind::sized : subrange_kind::unsized>; | |
396 | ||
397 | template<borrowed_range _Rng> | |
398 | subrange(_Rng&&, | |
399 | __detail::__make_unsigned_like_t<range_difference_t<_Rng>>) | |
400 | -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>; | |
401 | ||
402 | template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> | |
403 | requires (_Num < 2) | |
404 | constexpr auto | |
405 | get(const subrange<_It, _Sent, _Kind>& __r) | |
406 | { | |
407 | if constexpr (_Num == 0) | |
408 | return __r.begin(); | |
409 | else | |
410 | return __r.end(); | |
411 | } | |
412 | ||
413 | template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> | |
414 | requires (_Num < 2) | |
415 | constexpr auto | |
416 | get(subrange<_It, _Sent, _Kind>&& __r) | |
417 | { | |
418 | if constexpr (_Num == 0) | |
419 | return __r.begin(); | |
420 | else | |
421 | return __r.end(); | |
422 | } | |
423 | ||
2b71ca68 | 424 | template<typename _It, typename _Sent, subrange_kind _Kind> |
160061ac JW |
425 | inline constexpr bool |
426 | enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true; | |
427 | ||
428 | template<range _Range> | |
a09bb4a8 JW |
429 | using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>, |
430 | subrange<iterator_t<_Range>>, | |
431 | dangling>; | |
2786064d PP |
432 | } // namespace ranges |
433 | ||
434 | // The following ranges algorithms are used by <ranges>, and are defined here | |
435 | // so that <ranges> can avoid including all of <bits/ranges_algo.h>. | |
436 | namespace ranges | |
437 | { | |
438 | struct __find_fn | |
439 | { | |
440 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, | |
441 | typename _Proj = identity> | |
442 | requires indirect_binary_predicate<ranges::equal_to, | |
443 | projected<_Iter, _Proj>, const _Tp*> | |
444 | constexpr _Iter | |
445 | operator()(_Iter __first, _Sent __last, | |
446 | const _Tp& __value, _Proj __proj = {}) const | |
447 | { | |
448 | while (__first != __last | |
449 | && !(std::__invoke(__proj, *__first) == __value)) | |
450 | ++__first; | |
451 | return __first; | |
452 | } | |
453 | ||
454 | template<input_range _Range, typename _Tp, typename _Proj = identity> | |
455 | requires indirect_binary_predicate<ranges::equal_to, | |
456 | projected<iterator_t<_Range>, _Proj>, | |
457 | const _Tp*> | |
458 | constexpr borrowed_iterator_t<_Range> | |
459 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const | |
460 | { | |
461 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
462 | __value, std::move(__proj)); | |
463 | } | |
464 | }; | |
465 | ||
466 | inline constexpr __find_fn find{}; | |
467 | ||
468 | struct __find_if_fn | |
469 | { | |
470 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
471 | typename _Proj = identity, | |
472 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
473 | constexpr _Iter | |
474 | operator()(_Iter __first, _Sent __last, | |
475 | _Pred __pred, _Proj __proj = {}) const | |
476 | { | |
477 | while (__first != __last | |
478 | && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
479 | ++__first; | |
480 | return __first; | |
481 | } | |
482 | ||
483 | template<input_range _Range, typename _Proj = identity, | |
484 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
485 | _Pred> | |
486 | constexpr borrowed_iterator_t<_Range> | |
487 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
488 | { | |
489 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
490 | std::move(__pred), std::move(__proj)); | |
491 | } | |
492 | }; | |
493 | ||
494 | inline constexpr __find_if_fn find_if{}; | |
495 | ||
496 | struct __find_if_not_fn | |
497 | { | |
498 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
499 | typename _Proj = identity, | |
500 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
501 | constexpr _Iter | |
502 | operator()(_Iter __first, _Sent __last, | |
503 | _Pred __pred, _Proj __proj = {}) const | |
504 | { | |
505 | while (__first != __last | |
506 | && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
507 | ++__first; | |
508 | return __first; | |
509 | } | |
510 | ||
511 | template<input_range _Range, typename _Proj = identity, | |
512 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
513 | _Pred> | |
514 | constexpr borrowed_iterator_t<_Range> | |
515 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
516 | { | |
517 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
518 | std::move(__pred), std::move(__proj)); | |
519 | } | |
520 | }; | |
521 | ||
522 | inline constexpr __find_if_not_fn find_if_not{}; | |
523 | ||
524 | template<typename _Iter1, typename _Iter2> | |
525 | struct in_in_result | |
526 | { | |
527 | [[no_unique_address]] _Iter1 in1; | |
528 | [[no_unique_address]] _Iter2 in2; | |
529 | ||
530 | template<typename _IIter1, typename _IIter2> | |
531 | requires convertible_to<const _Iter1&, _IIter1> | |
532 | && convertible_to<const _Iter2&, _IIter2> | |
533 | constexpr | |
534 | operator in_in_result<_IIter1, _IIter2>() const & | |
535 | { return {in1, in2}; } | |
536 | ||
537 | template<typename _IIter1, typename _IIter2> | |
538 | requires convertible_to<_Iter1, _IIter1> | |
539 | && convertible_to<_Iter2, _IIter2> | |
540 | constexpr | |
541 | operator in_in_result<_IIter1, _IIter2>() && | |
542 | { return {std::move(in1), std::move(in2)}; } | |
543 | }; | |
544 | ||
545 | template<typename _Iter1, typename _Iter2> | |
546 | using mismatch_result = in_in_result<_Iter1, _Iter2>; | |
547 | ||
548 | struct __mismatch_fn | |
549 | { | |
550 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
551 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
552 | typename _Pred = ranges::equal_to, | |
553 | typename _Proj1 = identity, typename _Proj2 = identity> | |
554 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
555 | constexpr mismatch_result<_Iter1, _Iter2> | |
556 | operator()(_Iter1 __first1, _Sent1 __last1, | |
557 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
558 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
559 | { | |
560 | while (__first1 != __last1 && __first2 != __last2 | |
561 | && (bool)std::__invoke(__pred, | |
562 | std::__invoke(__proj1, *__first1), | |
563 | std::__invoke(__proj2, *__first2))) | |
564 | { | |
565 | ++__first1; | |
566 | ++__first2; | |
567 | } | |
568 | return { std::move(__first1), std::move(__first2) }; | |
569 | } | |
570 | ||
571 | template<input_range _Range1, input_range _Range2, | |
572 | typename _Pred = ranges::equal_to, | |
573 | typename _Proj1 = identity, typename _Proj2 = identity> | |
574 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
575 | _Pred, _Proj1, _Proj2> | |
576 | constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>> | |
577 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, | |
578 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
579 | { | |
580 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
581 | ranges::begin(__r2), ranges::end(__r2), | |
582 | std::move(__pred), | |
583 | std::move(__proj1), std::move(__proj2)); | |
584 | } | |
585 | }; | |
586 | ||
587 | inline constexpr __mismatch_fn mismatch{}; | |
588 | ||
589 | struct __search_fn | |
590 | { | |
591 | template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
592 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
593 | typename _Pred = ranges::equal_to, | |
594 | typename _Proj1 = identity, typename _Proj2 = identity> | |
595 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
596 | constexpr subrange<_Iter1> | |
597 | operator()(_Iter1 __first1, _Sent1 __last1, | |
598 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
599 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
600 | { | |
601 | if (__first1 == __last1 || __first2 == __last2) | |
602 | return {__first1, __first1}; | |
603 | ||
604 | for (;;) | |
605 | { | |
606 | for (;;) | |
607 | { | |
608 | if (__first1 == __last1) | |
609 | return {__first1, __first1}; | |
610 | if (std::__invoke(__pred, | |
611 | std::__invoke(__proj1, *__first1), | |
612 | std::__invoke(__proj2, *__first2))) | |
613 | break; | |
614 | ++__first1; | |
615 | } | |
616 | auto __cur1 = __first1; | |
617 | auto __cur2 = __first2; | |
618 | for (;;) | |
619 | { | |
620 | if (++__cur2 == __last2) | |
621 | return {__first1, ++__cur1}; | |
622 | if (++__cur1 == __last1) | |
623 | return {__cur1, __cur1}; | |
624 | if (!(bool)std::__invoke(__pred, | |
625 | std::__invoke(__proj1, *__cur1), | |
626 | std::__invoke(__proj2, *__cur2))) | |
627 | { | |
628 | ++__first1; | |
629 | break; | |
630 | } | |
631 | } | |
632 | } | |
633 | } | |
634 | ||
635 | template<forward_range _Range1, forward_range _Range2, | |
636 | typename _Pred = ranges::equal_to, | |
637 | typename _Proj1 = identity, typename _Proj2 = identity> | |
638 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
639 | _Pred, _Proj1, _Proj2> | |
640 | constexpr borrowed_subrange_t<_Range1> | |
641 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, | |
642 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
643 | { | |
644 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
645 | ranges::begin(__r2), ranges::end(__r2), | |
646 | std::move(__pred), | |
647 | std::move(__proj1), std::move(__proj2)); | |
648 | } | |
649 | }; | |
160061ac | 650 | |
2786064d | 651 | inline constexpr __search_fn search{}; |
160061ac JW |
652 | } // namespace ranges |
653 | ||
654 | using ranges::get; | |
655 | ||
a186ab67 JW |
656 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> |
657 | struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>> | |
658 | : integral_constant<size_t, 2> | |
659 | { }; | |
660 | ||
661 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
662 | struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>> | |
663 | { using type = _Iter; }; | |
664 | ||
665 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
666 | struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>> | |
667 | { using type = _Sent; }; | |
668 | ||
669 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
670 | struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>> | |
671 | { using type = _Iter; }; | |
672 | ||
673 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
674 | struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>> | |
675 | { using type = _Sent; }; | |
676 | ||
160061ac JW |
677 | _GLIBCXX_END_NAMESPACE_VERSION |
678 | } // namespace std | |
679 | #endif // library concepts | |
680 | #endif // C++20 | |
681 | #endif // _RANGES_UTIL_H |