133 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_H10#define _LIBCPP___ALGORITHM_RANGES_SEARCH_H11 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_header29#endif30 31#if _LIBCPP_STD_VER >= 2032 33_LIBCPP_BEGIN_NAMESPACE_STD34 35namespace ranges {36struct __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 123inline namespace __cpo {124inline constexpr auto search = __search{};125} // namespace __cpo126} // namespace ranges127 128_LIBCPP_END_NAMESPACE_STD129 130#endif // _LIBCPP_STD_VER >= 20131 132#endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_H133