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

source code of include/c++/11/bits/ranges_util.h