]>
Commit | Line | Data |
---|---|---|
160061ac JW |
1 | // Utilities for representing and manipulating ranges -*- C++ -*- |
2 | ||
a945c346 | 3 | // Copyright (C) 2019-2024 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> |
a6bbaab2 | 36 | # include <bits/invoke.h> |
de19b516 | 37 | # include <bits/cpp_type_traits.h> // __can_use_memchr_for_find |
160061ac | 38 | |
7ffa63df | 39 | #ifdef __glibcxx_ranges |
160061ac JW |
40 | namespace std _GLIBCXX_VISIBILITY(default) |
41 | { | |
42 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
43 | namespace ranges | |
44 | { | |
45 | // C++20 24.5 [range.utility] Range utilities | |
46 | ||
47 | namespace __detail | |
48 | { | |
49 | template<typename _Range> | |
50 | concept __simple_view = view<_Range> && range<const _Range> | |
51 | && same_as<iterator_t<_Range>, iterator_t<const _Range>> | |
52 | && same_as<sentinel_t<_Range>, sentinel_t<const _Range>>; | |
53 | ||
54 | template<typename _It> | |
55 | concept __has_arrow = input_iterator<_It> | |
56 | && (is_pointer_v<_It> || requires(_It __it) { __it.operator->(); }); | |
57 | ||
0d94c6df | 58 | using std::__detail::__different_from; |
160061ac JW |
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()))) | |
f2e7dd8b | 100 | requires forward_range<_Derived> && (!sized_range<_Derived>) |
9245b0e8 | 101 | { return _S_empty(_M_derived()); } |
160061ac | 102 | |
f2e7dd8b PP |
103 | constexpr bool |
104 | empty() | |
105 | noexcept(noexcept(ranges::size(_M_derived()) == 0)) | |
106 | requires sized_range<_Derived> | |
107 | { return ranges::size(_M_derived()) == 0; } | |
108 | ||
160061ac | 109 | constexpr bool |
9245b0e8 JW |
110 | empty() const |
111 | noexcept(noexcept(_S_empty(_M_derived()))) | |
f2e7dd8b | 112 | requires forward_range<const _Derived> && (!sized_range<const _Derived>) |
9245b0e8 | 113 | { return _S_empty(_M_derived()); } |
160061ac | 114 | |
f2e7dd8b PP |
115 | constexpr bool |
116 | empty() const | |
117 | noexcept(noexcept(ranges::size(_M_derived()) == 0)) | |
118 | requires sized_range<const _Derived> | |
119 | { return ranges::size(_M_derived()) == 0; } | |
120 | ||
160061ac | 121 | constexpr explicit |
9245b0e8 JW |
122 | operator bool() noexcept(noexcept(ranges::empty(_M_derived()))) |
123 | requires requires { ranges::empty(_M_derived()); } | |
160061ac JW |
124 | { return !ranges::empty(_M_derived()); } |
125 | ||
126 | constexpr explicit | |
9245b0e8 JW |
127 | operator bool() const noexcept(noexcept(ranges::empty(_M_derived()))) |
128 | requires requires { ranges::empty(_M_derived()); } | |
160061ac JW |
129 | { return !ranges::empty(_M_derived()); } |
130 | ||
131 | constexpr auto | |
9245b0e8 JW |
132 | data() noexcept(noexcept(ranges::begin(_M_derived()))) |
133 | requires contiguous_iterator<iterator_t<_Derived>> | |
134 | { return std::to_address(ranges::begin(_M_derived())); } | |
160061ac JW |
135 | |
136 | constexpr auto | |
9245b0e8 | 137 | data() const noexcept(noexcept(ranges::begin(_M_derived()))) |
160061ac JW |
138 | requires range<const _Derived> |
139 | && contiguous_iterator<iterator_t<const _Derived>> | |
9245b0e8 | 140 | { return std::to_address(ranges::begin(_M_derived())); } |
160061ac JW |
141 | |
142 | constexpr auto | |
9245b0e8 | 143 | size() noexcept(noexcept(_S_size(_M_derived()))) |
160061ac JW |
144 | requires forward_range<_Derived> |
145 | && sized_sentinel_for<sentinel_t<_Derived>, iterator_t<_Derived>> | |
9245b0e8 | 146 | { return _S_size(_M_derived()); } |
160061ac JW |
147 | |
148 | constexpr auto | |
9245b0e8 | 149 | size() const noexcept(noexcept(_S_size(_M_derived()))) |
160061ac JW |
150 | requires forward_range<const _Derived> |
151 | && sized_sentinel_for<sentinel_t<const _Derived>, | |
152 | iterator_t<const _Derived>> | |
9245b0e8 | 153 | { return _S_size(_M_derived()); } |
160061ac JW |
154 | |
155 | constexpr decltype(auto) | |
156 | front() requires forward_range<_Derived> | |
157 | { | |
158 | __glibcxx_assert(!empty()); | |
159 | return *ranges::begin(_M_derived()); | |
160 | } | |
161 | ||
162 | constexpr decltype(auto) | |
163 | front() const requires forward_range<const _Derived> | |
164 | { | |
165 | __glibcxx_assert(!empty()); | |
166 | return *ranges::begin(_M_derived()); | |
167 | } | |
168 | ||
169 | constexpr decltype(auto) | |
170 | back() | |
171 | requires bidirectional_range<_Derived> && common_range<_Derived> | |
172 | { | |
173 | __glibcxx_assert(!empty()); | |
174 | return *ranges::prev(ranges::end(_M_derived())); | |
175 | } | |
176 | ||
177 | constexpr decltype(auto) | |
178 | back() const | |
179 | requires bidirectional_range<const _Derived> | |
180 | && common_range<const _Derived> | |
181 | { | |
182 | __glibcxx_assert(!empty()); | |
183 | return *ranges::prev(ranges::end(_M_derived())); | |
184 | } | |
185 | ||
186 | template<random_access_range _Range = _Derived> | |
187 | constexpr decltype(auto) | |
188 | operator[](range_difference_t<_Range> __n) | |
189 | { return ranges::begin(_M_derived())[__n]; } | |
190 | ||
191 | template<random_access_range _Range = const _Derived> | |
192 | constexpr decltype(auto) | |
193 | operator[](range_difference_t<_Range> __n) const | |
194 | { return ranges::begin(_M_derived())[__n]; } | |
0d94c6df PP |
195 | |
196 | #if __cplusplus > 202002L | |
197 | constexpr auto | |
198 | cbegin() requires input_range<_Derived> | |
199 | { return ranges::cbegin(_M_derived()); } | |
200 | ||
201 | constexpr auto | |
202 | cbegin() const requires input_range<const _Derived> | |
203 | { return ranges::cbegin(_M_derived()); } | |
204 | ||
205 | constexpr auto | |
206 | cend() requires input_range<_Derived> | |
207 | { return ranges::cend(_M_derived()); } | |
208 | ||
209 | constexpr auto | |
210 | cend() const requires input_range<const _Derived> | |
211 | { return ranges::cend(_M_derived()); } | |
212 | #endif | |
160061ac JW |
213 | }; |
214 | ||
215 | namespace __detail | |
216 | { | |
98af6b86 PP |
217 | template<typename _From, typename _To> |
218 | concept __uses_nonqualification_pointer_conversion | |
219 | = is_pointer_v<_From> && is_pointer_v<_To> | |
220 | && !convertible_to<remove_pointer_t<_From>(*)[], | |
221 | remove_pointer_t<_To>(*)[]>; | |
222 | ||
223 | template<typename _From, typename _To> | |
160061ac | 224 | concept __convertible_to_non_slicing = convertible_to<_From, _To> |
98af6b86 PP |
225 | && !__uses_nonqualification_pointer_conversion<decay_t<_From>, |
226 | decay_t<_To>>; | |
160061ac | 227 | |
65b4cba9 PP |
228 | #if __glibcxx_tuple_like // >= C++23 |
229 | // P2165R4 version of __pair_like is defined in <bits/stl_pair.h>. | |
230 | #else | |
231 | // C++20 version of __pair_like from P2321R2. | |
160061ac JW |
232 | template<typename _Tp> |
233 | concept __pair_like | |
234 | = !is_reference_v<_Tp> && requires(_Tp __t) | |
235 | { | |
236 | typename tuple_size<_Tp>::type; | |
237 | requires derived_from<tuple_size<_Tp>, integral_constant<size_t, 2>>; | |
238 | typename tuple_element_t<0, remove_const_t<_Tp>>; | |
239 | typename tuple_element_t<1, remove_const_t<_Tp>>; | |
240 | { get<0>(__t) } -> convertible_to<const tuple_element_t<0, _Tp>&>; | |
241 | { get<1>(__t) } -> convertible_to<const tuple_element_t<1, _Tp>&>; | |
242 | }; | |
65b4cba9 | 243 | #endif |
160061ac JW |
244 | |
245 | template<typename _Tp, typename _Up, typename _Vp> | |
246 | concept __pair_like_convertible_from | |
65b4cba9 | 247 | = !range<_Tp> && !is_reference_v<_Vp> && __pair_like<_Tp> |
160061ac JW |
248 | && constructible_from<_Tp, _Up, _Vp> |
249 | && __convertible_to_non_slicing<_Up, tuple_element_t<0, _Tp>> | |
250 | && convertible_to<_Vp, tuple_element_t<1, _Tp>>; | |
251 | ||
160061ac JW |
252 | } // namespace __detail |
253 | ||
9626e447 PP |
254 | namespace views { struct _Drop; } // defined in <ranges> |
255 | ||
160061ac JW |
256 | enum class subrange_kind : bool { unsized, sized }; |
257 | ||
258 | /// The ranges::subrange class template | |
259 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent = _It, | |
260 | subrange_kind _Kind = sized_sentinel_for<_Sent, _It> | |
261 | ? subrange_kind::sized : subrange_kind::unsized> | |
262 | requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _It>) | |
263 | class subrange : public view_interface<subrange<_It, _Sent, _Kind>> | |
264 | { | |
265 | private: | |
9626e447 | 266 | static constexpr bool _S_store_size |
160061ac JW |
267 | = _Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _It>; |
268 | ||
9626e447 PP |
269 | friend struct views::_Drop; // Needs to inspect _S_store_size. |
270 | ||
160061ac | 271 | _It _M_begin = _It(); |
620db4ca | 272 | [[no_unique_address]] _Sent _M_end = _Sent(); |
160061ac | 273 | |
a88fc03b JW |
274 | using __size_type |
275 | = __detail::__make_unsigned_like_t<iter_difference_t<_It>>; | |
276 | ||
08448dc1 | 277 | template<typename _Tp, bool = _S_store_size> |
160061ac | 278 | struct _Size |
08448dc1 JW |
279 | { |
280 | [[__gnu__::__always_inline__]] | |
281 | constexpr _Size(_Tp = {}) { } | |
282 | }; | |
160061ac JW |
283 | |
284 | template<typename _Tp> | |
285 | struct _Size<_Tp, true> | |
08448dc1 JW |
286 | { |
287 | [[__gnu__::__always_inline__]] | |
288 | constexpr _Size(_Tp __s = {}) : _M_size(__s) { } | |
289 | ||
290 | _Tp _M_size; | |
291 | }; | |
160061ac | 292 | |
a88fc03b | 293 | [[no_unique_address]] _Size<__size_type> _M_size = {}; |
160061ac JW |
294 | |
295 | public: | |
4b4f5666 | 296 | subrange() requires default_initializable<_It> = default; |
160061ac JW |
297 | |
298 | constexpr | |
299 | subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s) | |
9245b0e8 JW |
300 | noexcept(is_nothrow_constructible_v<_It, decltype(__i)> |
301 | && is_nothrow_constructible_v<_Sent, _Sent&>) | |
160061ac JW |
302 | requires (!_S_store_size) |
303 | : _M_begin(std::move(__i)), _M_end(__s) | |
304 | { } | |
305 | ||
306 | constexpr | |
307 | subrange(__detail::__convertible_to_non_slicing<_It> auto __i, _Sent __s, | |
a88fc03b | 308 | __size_type __n) |
9245b0e8 JW |
309 | noexcept(is_nothrow_constructible_v<_It, decltype(__i)> |
310 | && is_nothrow_constructible_v<_Sent, _Sent&>) | |
160061ac | 311 | requires (_Kind == subrange_kind::sized) |
08448dc1 JW |
312 | : _M_begin(std::move(__i)), _M_end(__s), _M_size(__n) |
313 | { } | |
160061ac | 314 | |
c09cabb2 | 315 | template<__detail::__different_from<subrange> _Rng> |
160061ac JW |
316 | requires borrowed_range<_Rng> |
317 | && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
318 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
319 | constexpr | |
9245b0e8 JW |
320 | subrange(_Rng&& __r) |
321 | noexcept(noexcept(subrange(__r, ranges::size(__r)))) | |
322 | requires _S_store_size && sized_range<_Rng> | |
a55cda89 | 323 | : subrange(__r, ranges::size(__r)) |
160061ac JW |
324 | { } |
325 | ||
c09cabb2 | 326 | template<__detail::__different_from<subrange> _Rng> |
160061ac JW |
327 | requires borrowed_range<_Rng> |
328 | && __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
329 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
330 | constexpr | |
9245b0e8 JW |
331 | subrange(_Rng&& __r) |
332 | noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r)))) | |
333 | requires (!_S_store_size) | |
6e00d9bb | 334 | : subrange(ranges::begin(__r), ranges::end(__r)) |
160061ac JW |
335 | { } |
336 | ||
337 | template<borrowed_range _Rng> | |
338 | requires __detail::__convertible_to_non_slicing<iterator_t<_Rng>, _It> | |
339 | && convertible_to<sentinel_t<_Rng>, _Sent> | |
340 | constexpr | |
a88fc03b | 341 | subrange(_Rng&& __r, __size_type __n) |
9245b0e8 | 342 | noexcept(noexcept(subrange(ranges::begin(__r), ranges::end(__r), __n))) |
160061ac JW |
343 | requires (_Kind == subrange_kind::sized) |
344 | : subrange{ranges::begin(__r), ranges::end(__r), __n} | |
345 | { } | |
346 | ||
c09cabb2 | 347 | template<__detail::__different_from<subrange> _PairLike> |
160061ac JW |
348 | requires __detail::__pair_like_convertible_from<_PairLike, const _It&, |
349 | const _Sent&> | |
a88fc03b JW |
350 | constexpr |
351 | operator _PairLike() const | |
352 | { return _PairLike(_M_begin, _M_end); } | |
160061ac JW |
353 | |
354 | constexpr _It | |
355 | begin() const requires copyable<_It> | |
356 | { return _M_begin; } | |
357 | ||
358 | [[nodiscard]] constexpr _It | |
359 | begin() requires (!copyable<_It>) | |
360 | { return std::move(_M_begin); } | |
361 | ||
362 | constexpr _Sent end() const { return _M_end; } | |
363 | ||
364 | constexpr bool empty() const { return _M_begin == _M_end; } | |
365 | ||
a88fc03b | 366 | constexpr __size_type |
160061ac JW |
367 | size() const requires (_Kind == subrange_kind::sized) |
368 | { | |
369 | if constexpr (_S_store_size) | |
370 | return _M_size._M_size; | |
371 | else | |
372 | return __detail::__to_unsigned_like(_M_end - _M_begin); | |
373 | } | |
374 | ||
375 | [[nodiscard]] constexpr subrange | |
376 | next(iter_difference_t<_It> __n = 1) const & | |
377 | requires forward_iterator<_It> | |
378 | { | |
379 | auto __tmp = *this; | |
380 | __tmp.advance(__n); | |
381 | return __tmp; | |
382 | } | |
383 | ||
384 | [[nodiscard]] constexpr subrange | |
385 | next(iter_difference_t<_It> __n = 1) && | |
386 | { | |
387 | advance(__n); | |
388 | return std::move(*this); | |
389 | } | |
390 | ||
391 | [[nodiscard]] constexpr subrange | |
392 | prev(iter_difference_t<_It> __n = 1) const | |
393 | requires bidirectional_iterator<_It> | |
394 | { | |
395 | auto __tmp = *this; | |
396 | __tmp.advance(-__n); | |
397 | return __tmp; | |
398 | } | |
399 | ||
400 | constexpr subrange& | |
401 | advance(iter_difference_t<_It> __n) | |
402 | { | |
403 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
404 | // 3433. subrange::advance(n) has UB when n < 0 | |
405 | if constexpr (bidirectional_iterator<_It>) | |
406 | if (__n < 0) | |
407 | { | |
408 | ranges::advance(_M_begin, __n); | |
409 | if constexpr (_S_store_size) | |
410 | _M_size._M_size += __detail::__to_unsigned_like(-__n); | |
411 | return *this; | |
412 | } | |
413 | ||
414 | __glibcxx_assert(__n >= 0); | |
415 | auto __d = __n - ranges::advance(_M_begin, __n, _M_end); | |
416 | if constexpr (_S_store_size) | |
417 | _M_size._M_size -= __detail::__to_unsigned_like(__d); | |
418 | return *this; | |
419 | } | |
420 | }; | |
421 | ||
422 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
423 | subrange(_It, _Sent) -> subrange<_It, _Sent>; | |
424 | ||
425 | template<input_or_output_iterator _It, sentinel_for<_It> _Sent> | |
426 | subrange(_It, _Sent, | |
427 | __detail::__make_unsigned_like_t<iter_difference_t<_It>>) | |
428 | -> subrange<_It, _Sent, subrange_kind::sized>; | |
429 | ||
160061ac JW |
430 | template<borrowed_range _Rng> |
431 | subrange(_Rng&&) | |
432 | -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, | |
433 | (sized_range<_Rng> | |
434 | || sized_sentinel_for<sentinel_t<_Rng>, iterator_t<_Rng>>) | |
435 | ? subrange_kind::sized : subrange_kind::unsized>; | |
436 | ||
437 | template<borrowed_range _Rng> | |
438 | subrange(_Rng&&, | |
439 | __detail::__make_unsigned_like_t<range_difference_t<_Rng>>) | |
440 | -> subrange<iterator_t<_Rng>, sentinel_t<_Rng>, subrange_kind::sized>; | |
441 | ||
442 | template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> | |
443 | requires (_Num < 2) | |
444 | constexpr auto | |
445 | get(const subrange<_It, _Sent, _Kind>& __r) | |
446 | { | |
447 | if constexpr (_Num == 0) | |
448 | return __r.begin(); | |
449 | else | |
450 | return __r.end(); | |
451 | } | |
452 | ||
453 | template<size_t _Num, class _It, class _Sent, subrange_kind _Kind> | |
454 | requires (_Num < 2) | |
455 | constexpr auto | |
456 | get(subrange<_It, _Sent, _Kind>&& __r) | |
457 | { | |
458 | if constexpr (_Num == 0) | |
459 | return __r.begin(); | |
460 | else | |
461 | return __r.end(); | |
462 | } | |
463 | ||
2b71ca68 | 464 | template<typename _It, typename _Sent, subrange_kind _Kind> |
160061ac JW |
465 | inline constexpr bool |
466 | enable_borrowed_range<subrange<_It, _Sent, _Kind>> = true; | |
467 | ||
468 | template<range _Range> | |
a09bb4a8 JW |
469 | using borrowed_subrange_t = __conditional_t<borrowed_range<_Range>, |
470 | subrange<iterator_t<_Range>>, | |
471 | dangling>; | |
65b4cba9 PP |
472 | |
473 | // __is_subrange is defined in <bits/utility.h>. | |
474 | template<typename _Iter, typename _Sent, subrange_kind _Kind> | |
475 | inline constexpr bool __detail::__is_subrange<subrange<_Iter, _Sent, _Kind>> = true; | |
2786064d PP |
476 | } // namespace ranges |
477 | ||
65b4cba9 PP |
478 | #if __glibcxx_tuple_like // >= C++23 |
479 | // __is_tuple_like_v is defined in <bits/stl_pair.h>. | |
480 | template<typename _It, typename _Sent, ranges::subrange_kind _Kind> | |
481 | inline constexpr bool __is_tuple_like_v<ranges::subrange<_It, _Sent, _Kind>> = true; | |
482 | #endif | |
483 | ||
2786064d PP |
484 | // The following ranges algorithms are used by <ranges>, and are defined here |
485 | // so that <ranges> can avoid including all of <bits/ranges_algo.h>. | |
486 | namespace ranges | |
487 | { | |
488 | struct __find_fn | |
489 | { | |
490 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp, | |
491 | typename _Proj = identity> | |
492 | requires indirect_binary_predicate<ranges::equal_to, | |
493 | projected<_Iter, _Proj>, const _Tp*> | |
494 | constexpr _Iter | |
495 | operator()(_Iter __first, _Sent __last, | |
496 | const _Tp& __value, _Proj __proj = {}) const | |
497 | { | |
de19b516 JW |
498 | if constexpr (is_same_v<_Proj, identity>) |
499 | if constexpr(__can_use_memchr_for_find<iter_value_t<_Iter>, _Tp>) | |
500 | if constexpr (sized_sentinel_for<_Sent, _Iter>) | |
501 | if constexpr (contiguous_iterator<_Iter>) | |
502 | if (!is_constant_evaluated()) | |
503 | { | |
762ee55d | 504 | using _Vt = iter_value_t<_Iter>; |
de19b516 | 505 | auto __n = __last - __first; |
762ee55d JW |
506 | if (static_cast<_Vt>(__value) == __value) [[likely]] |
507 | if (__n > 0) | |
508 | { | |
cda469a5 | 509 | const size_t __nu = static_cast<size_t>(__n); |
762ee55d JW |
510 | const int __ival = static_cast<int>(__value); |
511 | const void* __p0 = std::to_address(__first); | |
cda469a5 | 512 | if (auto __p1 = __builtin_memchr(__p0, __ival, __nu)) |
762ee55d JW |
513 | __n = (const char*)__p1 - (const char*)__p0; |
514 | } | |
de19b516 JW |
515 | return __first + __n; |
516 | } | |
517 | ||
2786064d PP |
518 | while (__first != __last |
519 | && !(std::__invoke(__proj, *__first) == __value)) | |
520 | ++__first; | |
521 | return __first; | |
522 | } | |
523 | ||
524 | template<input_range _Range, typename _Tp, typename _Proj = identity> | |
525 | requires indirect_binary_predicate<ranges::equal_to, | |
526 | projected<iterator_t<_Range>, _Proj>, | |
527 | const _Tp*> | |
528 | constexpr borrowed_iterator_t<_Range> | |
529 | operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const | |
530 | { | |
531 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
532 | __value, std::move(__proj)); | |
533 | } | |
534 | }; | |
535 | ||
536 | inline constexpr __find_fn find{}; | |
537 | ||
538 | struct __find_if_fn | |
539 | { | |
540 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
541 | typename _Proj = identity, | |
542 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
543 | constexpr _Iter | |
544 | operator()(_Iter __first, _Sent __last, | |
545 | _Pred __pred, _Proj __proj = {}) const | |
546 | { | |
547 | while (__first != __last | |
548 | && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
549 | ++__first; | |
550 | return __first; | |
551 | } | |
552 | ||
553 | template<input_range _Range, typename _Proj = identity, | |
554 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
555 | _Pred> | |
556 | constexpr borrowed_iterator_t<_Range> | |
557 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
558 | { | |
559 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
560 | std::move(__pred), std::move(__proj)); | |
561 | } | |
562 | }; | |
563 | ||
564 | inline constexpr __find_if_fn find_if{}; | |
565 | ||
566 | struct __find_if_not_fn | |
567 | { | |
568 | template<input_iterator _Iter, sentinel_for<_Iter> _Sent, | |
569 | typename _Proj = identity, | |
570 | indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> | |
571 | constexpr _Iter | |
572 | operator()(_Iter __first, _Sent __last, | |
573 | _Pred __pred, _Proj __proj = {}) const | |
574 | { | |
575 | while (__first != __last | |
576 | && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first))) | |
577 | ++__first; | |
578 | return __first; | |
579 | } | |
580 | ||
581 | template<input_range _Range, typename _Proj = identity, | |
582 | indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> | |
583 | _Pred> | |
584 | constexpr borrowed_iterator_t<_Range> | |
585 | operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const | |
586 | { | |
587 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
588 | std::move(__pred), std::move(__proj)); | |
589 | } | |
590 | }; | |
591 | ||
592 | inline constexpr __find_if_not_fn find_if_not{}; | |
593 | ||
594 | template<typename _Iter1, typename _Iter2> | |
595 | struct in_in_result | |
596 | { | |
597 | [[no_unique_address]] _Iter1 in1; | |
598 | [[no_unique_address]] _Iter2 in2; | |
599 | ||
600 | template<typename _IIter1, typename _IIter2> | |
601 | requires convertible_to<const _Iter1&, _IIter1> | |
602 | && convertible_to<const _Iter2&, _IIter2> | |
603 | constexpr | |
604 | operator in_in_result<_IIter1, _IIter2>() const & | |
605 | { return {in1, in2}; } | |
606 | ||
607 | template<typename _IIter1, typename _IIter2> | |
608 | requires convertible_to<_Iter1, _IIter1> | |
609 | && convertible_to<_Iter2, _IIter2> | |
610 | constexpr | |
611 | operator in_in_result<_IIter1, _IIter2>() && | |
612 | { return {std::move(in1), std::move(in2)}; } | |
613 | }; | |
614 | ||
615 | template<typename _Iter1, typename _Iter2> | |
616 | using mismatch_result = in_in_result<_Iter1, _Iter2>; | |
617 | ||
618 | struct __mismatch_fn | |
619 | { | |
620 | template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
621 | input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
622 | typename _Pred = ranges::equal_to, | |
623 | typename _Proj1 = identity, typename _Proj2 = identity> | |
624 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
625 | constexpr mismatch_result<_Iter1, _Iter2> | |
626 | operator()(_Iter1 __first1, _Sent1 __last1, | |
627 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
628 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
629 | { | |
630 | while (__first1 != __last1 && __first2 != __last2 | |
631 | && (bool)std::__invoke(__pred, | |
632 | std::__invoke(__proj1, *__first1), | |
633 | std::__invoke(__proj2, *__first2))) | |
634 | { | |
635 | ++__first1; | |
636 | ++__first2; | |
637 | } | |
638 | return { std::move(__first1), std::move(__first2) }; | |
639 | } | |
640 | ||
641 | template<input_range _Range1, input_range _Range2, | |
642 | typename _Pred = ranges::equal_to, | |
643 | typename _Proj1 = identity, typename _Proj2 = identity> | |
644 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
645 | _Pred, _Proj1, _Proj2> | |
646 | constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>> | |
647 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, | |
648 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
649 | { | |
650 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
651 | ranges::begin(__r2), ranges::end(__r2), | |
652 | std::move(__pred), | |
653 | std::move(__proj1), std::move(__proj2)); | |
654 | } | |
655 | }; | |
656 | ||
657 | inline constexpr __mismatch_fn mismatch{}; | |
658 | ||
659 | struct __search_fn | |
660 | { | |
661 | template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1, | |
662 | forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, | |
663 | typename _Pred = ranges::equal_to, | |
664 | typename _Proj1 = identity, typename _Proj2 = identity> | |
665 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> | |
666 | constexpr subrange<_Iter1> | |
667 | operator()(_Iter1 __first1, _Sent1 __last1, | |
668 | _Iter2 __first2, _Sent2 __last2, _Pred __pred = {}, | |
669 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
670 | { | |
671 | if (__first1 == __last1 || __first2 == __last2) | |
672 | return {__first1, __first1}; | |
673 | ||
674 | for (;;) | |
675 | { | |
676 | for (;;) | |
677 | { | |
678 | if (__first1 == __last1) | |
679 | return {__first1, __first1}; | |
680 | if (std::__invoke(__pred, | |
681 | std::__invoke(__proj1, *__first1), | |
682 | std::__invoke(__proj2, *__first2))) | |
683 | break; | |
684 | ++__first1; | |
685 | } | |
686 | auto __cur1 = __first1; | |
687 | auto __cur2 = __first2; | |
688 | for (;;) | |
689 | { | |
690 | if (++__cur2 == __last2) | |
691 | return {__first1, ++__cur1}; | |
692 | if (++__cur1 == __last1) | |
693 | return {__cur1, __cur1}; | |
694 | if (!(bool)std::__invoke(__pred, | |
695 | std::__invoke(__proj1, *__cur1), | |
696 | std::__invoke(__proj2, *__cur2))) | |
697 | { | |
698 | ++__first1; | |
699 | break; | |
700 | } | |
701 | } | |
702 | } | |
703 | } | |
704 | ||
705 | template<forward_range _Range1, forward_range _Range2, | |
706 | typename _Pred = ranges::equal_to, | |
707 | typename _Proj1 = identity, typename _Proj2 = identity> | |
708 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, | |
709 | _Pred, _Proj1, _Proj2> | |
710 | constexpr borrowed_subrange_t<_Range1> | |
711 | operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {}, | |
712 | _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const | |
713 | { | |
714 | return (*this)(ranges::begin(__r1), ranges::end(__r1), | |
715 | ranges::begin(__r2), ranges::end(__r2), | |
716 | std::move(__pred), | |
717 | std::move(__proj1), std::move(__proj2)); | |
718 | } | |
719 | }; | |
160061ac | 720 | |
2786064d | 721 | inline constexpr __search_fn search{}; |
49e25d3e PP |
722 | |
723 | struct __min_fn | |
724 | { | |
725 | template<typename _Tp, typename _Proj = identity, | |
726 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
727 | _Comp = ranges::less> | |
728 | constexpr const _Tp& | |
729 | operator()(const _Tp& __a, const _Tp& __b, | |
730 | _Comp __comp = {}, _Proj __proj = {}) const | |
731 | { | |
732 | if (std::__invoke(__comp, | |
733 | std::__invoke(__proj, __b), | |
734 | std::__invoke(__proj, __a))) | |
735 | return __b; | |
736 | else | |
737 | return __a; | |
738 | } | |
739 | ||
740 | template<input_range _Range, typename _Proj = identity, | |
741 | indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> | |
742 | _Comp = ranges::less> | |
743 | requires indirectly_copyable_storable<iterator_t<_Range>, | |
744 | range_value_t<_Range>*> | |
745 | constexpr range_value_t<_Range> | |
746 | operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const | |
747 | { | |
748 | auto __first = ranges::begin(__r); | |
749 | auto __last = ranges::end(__r); | |
750 | __glibcxx_assert(__first != __last); | |
751 | auto __result = *__first; | |
752 | while (++__first != __last) | |
753 | { | |
754 | auto __tmp = *__first; | |
755 | if (std::__invoke(__comp, | |
756 | std::__invoke(__proj, __tmp), | |
757 | std::__invoke(__proj, __result))) | |
758 | __result = std::move(__tmp); | |
759 | } | |
760 | return __result; | |
761 | } | |
762 | ||
763 | template<copyable _Tp, typename _Proj = identity, | |
764 | indirect_strict_weak_order<projected<const _Tp*, _Proj>> | |
765 | _Comp = ranges::less> | |
766 | constexpr _Tp | |
767 | operator()(initializer_list<_Tp> __r, | |
768 | _Comp __comp = {}, _Proj __proj = {}) const | |
769 | { | |
770 | return (*this)(ranges::subrange(__r), | |
771 | std::move(__comp), std::move(__proj)); | |
772 | } | |
773 | }; | |
774 | ||
775 | inline constexpr __min_fn min{}; | |
776 | ||
29b39d4b PP |
777 | struct __adjacent_find_fn |
778 | { | |
779 | template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, | |
780 | typename _Proj = identity, | |
781 | indirect_binary_predicate<projected<_Iter, _Proj>, | |
782 | projected<_Iter, _Proj>> _Pred | |
783 | = ranges::equal_to> | |
784 | constexpr _Iter | |
785 | operator()(_Iter __first, _Sent __last, | |
786 | _Pred __pred = {}, _Proj __proj = {}) const | |
787 | { | |
788 | if (__first == __last) | |
789 | return __first; | |
790 | auto __next = __first; | |
791 | for (; ++__next != __last; __first = __next) | |
792 | { | |
793 | if (std::__invoke(__pred, | |
794 | std::__invoke(__proj, *__first), | |
795 | std::__invoke(__proj, *__next))) | |
796 | return __first; | |
797 | } | |
798 | return __next; | |
799 | } | |
800 | ||
801 | template<forward_range _Range, typename _Proj = identity, | |
802 | indirect_binary_predicate< | |
803 | projected<iterator_t<_Range>, _Proj>, | |
804 | projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to> | |
805 | constexpr borrowed_iterator_t<_Range> | |
806 | operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const | |
807 | { | |
808 | return (*this)(ranges::begin(__r), ranges::end(__r), | |
809 | std::move(__pred), std::move(__proj)); | |
810 | } | |
811 | }; | |
812 | ||
813 | inline constexpr __adjacent_find_fn adjacent_find{}; | |
814 | ||
160061ac JW |
815 | } // namespace ranges |
816 | ||
817 | using ranges::get; | |
818 | ||
a186ab67 JW |
819 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> |
820 | struct tuple_size<ranges::subrange<_Iter, _Sent, _Kind>> | |
821 | : integral_constant<size_t, 2> | |
822 | { }; | |
823 | ||
824 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
825 | struct tuple_element<0, ranges::subrange<_Iter, _Sent, _Kind>> | |
826 | { using type = _Iter; }; | |
827 | ||
828 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
829 | struct tuple_element<1, ranges::subrange<_Iter, _Sent, _Kind>> | |
830 | { using type = _Sent; }; | |
831 | ||
832 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
833 | struct tuple_element<0, const ranges::subrange<_Iter, _Sent, _Kind>> | |
834 | { using type = _Iter; }; | |
835 | ||
836 | template<typename _Iter, typename _Sent, ranges::subrange_kind _Kind> | |
837 | struct tuple_element<1, const ranges::subrange<_Iter, _Sent, _Kind>> | |
838 | { using type = _Sent; }; | |
839 | ||
160061ac JW |
840 | _GLIBCXX_END_NAMESPACE_VERSION |
841 | } // namespace std | |
842 | #endif // library concepts | |
843 | #endif // C++20 | |
844 | #endif // _RANGES_UTIL_H |