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 | namespace __search { |
37 | struct __fn { |
38 | template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> |
39 | _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl( |
40 | _Iter1 __first1, |
41 | _Sent1 __last1, |
42 | _Iter2 __first2, |
43 | _Sent2 __last2, |
44 | _Pred& __pred, |
45 | _Proj1& __proj1, |
46 | _Proj2& __proj2) { |
47 | if constexpr (sized_sentinel_for<_Sent2, _Iter2>) { |
48 | auto __size2 = ranges::distance(__first2, __last2); |
49 | if (__size2 == 0) |
50 | return {__first1, __first1}; |
51 | |
52 | if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { |
53 | auto __size1 = ranges::distance(__first1, __last1); |
54 | if (__size1 < __size2) { |
55 | ranges::advance(__first1, __last1); |
56 | return {__first1, __first1}; |
57 | } |
58 | |
59 | if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { |
60 | auto __ret = std::__search_random_access_impl<_RangeAlgPolicy>( |
61 | __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2); |
62 | return {__ret.first, __ret.second}; |
63 | } |
64 | } |
65 | } |
66 | |
67 | auto __ret = |
68 | std::__search_forward_impl<_RangeAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); |
69 | return {__ret.first, __ret.second}; |
70 | } |
71 | |
72 | template <forward_iterator _Iter1, |
73 | sentinel_for<_Iter1> _Sent1, |
74 | forward_iterator _Iter2, |
75 | sentinel_for<_Iter2> _Sent2, |
76 | class _Pred = ranges::equal_to, |
77 | class _Proj1 = identity, |
78 | class _Proj2 = identity> |
79 | requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> |
80 | [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter1> operator()( |
81 | _Iter1 __first1, |
82 | _Sent1 __last1, |
83 | _Iter2 __first2, |
84 | _Sent2 __last2, |
85 | _Pred __pred = {}, |
86 | _Proj1 __proj1 = {}, |
87 | _Proj2 __proj2 = {}) const { |
88 | return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); |
89 | } |
90 | |
91 | template <forward_range _Range1, |
92 | forward_range _Range2, |
93 | class _Pred = ranges::equal_to, |
94 | class _Proj1 = identity, |
95 | class _Proj2 = identity> |
96 | requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> |
97 | [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range1> operator()( |
98 | _Range1&& __range1, _Range2&& __range2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { |
99 | auto __first1 = ranges::begin(__range1); |
100 | if constexpr (sized_range<_Range2>) { |
101 | auto __size2 = ranges::size(__range2); |
102 | if (__size2 == 0) |
103 | return {__first1, __first1}; |
104 | if constexpr (sized_range<_Range1>) { |
105 | auto __size1 = ranges::size(__range1); |
106 | if (__size1 < __size2) { |
107 | ranges::advance(__first1, ranges::end(__range1)); |
108 | return {__first1, __first1}; |
109 | } |
110 | } |
111 | } |
112 | |
113 | return __ranges_search_impl( |
114 | ranges::begin(__range1), |
115 | ranges::end(__range1), |
116 | ranges::begin(__range2), |
117 | ranges::end(__range2), |
118 | __pred, |
119 | __proj1, |
120 | __proj2); |
121 | } |
122 | }; |
123 | } // namespace __search |
124 | |
125 | inline namespace __cpo { |
126 | inline constexpr auto search = __search::__fn{}; |
127 | } // namespace __cpo |
128 | } // namespace ranges |
129 | |
130 | _LIBCPP_END_NAMESPACE_STD |
131 | |
132 | #endif // _LIBCPP_STD_VER >= 20 |
133 | |
134 | #endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H |
135 | |