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 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 # pragma GCC system_header 28 #endif 29 30 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 31 32 _LIBCPP_BEGIN_NAMESPACE_STD 33 34 namespace ranges { 35 namespace __search { 36 struct __fn { 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, sentinel_for<_Iter1> _Sent1, 72 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, 73 class _Pred = ranges::equal_to, 74 class _Proj1 = identity, 75 class _Proj2 = identity> 76 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> 77 _LIBCPP_HIDE_FROM_ABI constexpr 78 subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, 79 _Iter2 __first2, _Sent2 __last2, 80 _Pred __pred = {}, 81 _Proj1 __proj1 = {}, 82 _Proj2 __proj2 = {}) const { 83 return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); 84 } 85 86 template <forward_range _Range1, 87 forward_range _Range2, 88 class _Pred = ranges::equal_to, 89 class _Proj1 = identity, 90 class _Proj2 = identity> 91 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> 92 _LIBCPP_HIDE_FROM_ABI constexpr 93 borrowed_subrange_t<_Range1> operator()(_Range1&& __range1, 94 _Range2&& __range2, 95 _Pred __pred = {}, 96 _Proj1 __proj1 = {}, 97 _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 } // 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 > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 133 134 #endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H 135