1 | //===----------------------------------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_H |
10 | #define _LIBCPP___ALGORITHM_RANGES_SEARCH_H |
11 | |
12 | #include <__algorithm/iterator_operations.h> |
13 | #include <__algorithm/search.h> |
14 | #include <__config> |
15 | #include <__functional/identity.h> |
16 | #include <__functional/ranges_operations.h> |
17 | #include <__iterator/advance.h> |
18 | #include <__iterator/concepts.h> |
19 | #include <__iterator/distance.h> |
20 | #include <__iterator/indirectly_comparable.h> |
21 | #include <__ranges/access.h> |
22 | #include <__ranges/concepts.h> |
23 | #include <__ranges/size.h> |
24 | #include <__ranges/subrange.h> |
25 | #include <__utility/pair.h> |
26 | |
27 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
28 | # pragma GCC system_header |
29 | #endif |
30 | |
31 | #if _LIBCPP_STD_VER >= 20 |
32 | |
33 | _LIBCPP_BEGIN_NAMESPACE_STD |
34 | |
35 | namespace ranges { |
36 | struct __search { |
37 | template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> |
38 | _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl( |
39 | _Iter1 __first1, |
40 | _Sent1 __last1, |
41 | _Iter2 __first2, |
42 | _Sent2 __last2, |
43 | _Pred& __pred, |
44 | _Proj1& __proj1, |
45 | _Proj2& __proj2) { |
46 | if constexpr (sized_sentinel_for<_Sent2, _Iter2>) { |
47 | auto __size2 = ranges::distance(__first2, __last2); |
48 | if (__size2 == 0) |
49 | return {__first1, __first1}; |
50 | |
51 | if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { |
52 | auto __size1 = ranges::distance(__first1, __last1); |
53 | if (__size1 < __size2) { |
54 | ranges::advance(__first1, __last1); |
55 | return {__first1, __first1}; |
56 | } |
57 | |
58 | if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { |
59 | auto __ret = std::__search_random_access_impl<_RangeAlgPolicy>( |
60 | __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2); |
61 | return {__ret.first, __ret.second}; |
62 | } |
63 | } |
64 | } |
65 | |
66 | auto __ret = |
67 | std::__search_forward_impl<_RangeAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); |
68 | return {__ret.first, __ret.second}; |
69 | } |
70 | |
71 | template <forward_iterator _Iter1, |
72 | sentinel_for<_Iter1> _Sent1, |
73 | forward_iterator _Iter2, |
74 | sentinel_for<_Iter2> _Sent2, |
75 | class _Pred = ranges::equal_to, |
76 | class _Proj1 = identity, |
77 | class _Proj2 = identity> |
78 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> |
79 | [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter1> operator()( |
80 | _Iter1 __first1, |
81 | _Sent1 __last1, |
82 | _Iter2 __first2, |
83 | _Sent2 __last2, |
84 | _Pred __pred = {}, |
85 | _Proj1 __proj1 = {}, |
86 | _Proj2 __proj2 = {}) const { |
87 | return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); |
88 | } |
89 | |
90 | template <forward_range _Range1, |
91 | forward_range _Range2, |
92 | class _Pred = ranges::equal_to, |
93 | class _Proj1 = identity, |
94 | class _Proj2 = identity> |
95 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> |
96 | [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range1> operator()( |
97 | _Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { |
98 | auto __first1 = ranges::begin(__range1); |
99 | if constexpr (sized_range<_Range2>) { |
100 | auto __size2 = ranges::size(__range2); |
101 | if (__size2 == 0) |
102 | return {__first1, __first1}; |
103 | if constexpr (sized_range<_Range1>) { |
104 | auto __size1 = ranges::size(__range1); |
105 | if (__size1 < __size2) { |
106 | ranges::advance(__first1, ranges::end(__range1)); |
107 | return {__first1, __first1}; |
108 | } |
109 | } |
110 | } |
111 | |
112 | return __ranges_search_impl( |
113 | ranges::begin(__range1), |
114 | ranges::end(__range1), |
115 | ranges::begin(__range2), |
116 | ranges::end(__range2), |
117 | __pred, |
118 | __proj1, |
119 | __proj2); |
120 | } |
121 | }; |
122 | |
123 | inline namespace __cpo { |
124 | inline constexpr auto search = __search{}; |
125 | } // namespace __cpo |
126 | } // namespace ranges |
127 | |
128 | _LIBCPP_END_NAMESPACE_STD |
129 | |
130 | #endif // _LIBCPP_STD_VER >= 20 |
131 | |
132 | #endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H |
133 | |