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 _LIBCPP_NODISCARD_EXT _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 _LIBCPP_NODISCARD_EXT _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