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