1753f127fSDimitry Andric //===----------------------------------------------------------------------===// 2753f127fSDimitry Andric // 3753f127fSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4753f127fSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5753f127fSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6753f127fSDimitry Andric // 7753f127fSDimitry Andric //===----------------------------------------------------------------------===// 8753f127fSDimitry Andric 9753f127fSDimitry Andric #ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H 10753f127fSDimitry Andric #define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H 11753f127fSDimitry Andric 12753f127fSDimitry Andric #include <__algorithm/iterator_operations.h> 13753f127fSDimitry Andric #include <__algorithm/search_n.h> 14753f127fSDimitry Andric #include <__config> 15753f127fSDimitry Andric #include <__functional/identity.h> 16753f127fSDimitry Andric #include <__functional/ranges_operations.h> 17753f127fSDimitry Andric #include <__iterator/advance.h> 18753f127fSDimitry Andric #include <__iterator/concepts.h> 19753f127fSDimitry Andric #include <__iterator/distance.h> 20753f127fSDimitry Andric #include <__iterator/incrementable_traits.h> 21753f127fSDimitry Andric #include <__iterator/indirectly_comparable.h> 22753f127fSDimitry Andric #include <__iterator/iterator_traits.h> 23753f127fSDimitry Andric #include <__ranges/access.h> 24753f127fSDimitry Andric #include <__ranges/concepts.h> 25753f127fSDimitry Andric #include <__ranges/size.h> 26753f127fSDimitry Andric #include <__ranges/subrange.h> 27753f127fSDimitry Andric #include <__utility/move.h> 28bdd1243dSDimitry Andric #include <__utility/pair.h> 29753f127fSDimitry Andric 30753f127fSDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 31753f127fSDimitry Andric # pragma GCC system_header 32753f127fSDimitry Andric #endif 33753f127fSDimitry Andric 34b3edf446SDimitry Andric _LIBCPP_PUSH_MACROS 35b3edf446SDimitry Andric #include <__undef_macros> 36b3edf446SDimitry Andric 3706c3fb27SDimitry Andric #if _LIBCPP_STD_VER >= 20 38753f127fSDimitry Andric 39753f127fSDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 40753f127fSDimitry Andric 41753f127fSDimitry Andric namespace ranges { 42753f127fSDimitry Andric namespace __search_n { 43753f127fSDimitry Andric struct __fn { 44753f127fSDimitry Andric template <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj> 45753f127fSDimitry Andric _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl( 46753f127fSDimitry Andric _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) { 47753f127fSDimitry Andric if (__count == 0) 48753f127fSDimitry Andric return {__first, __first}; 49753f127fSDimitry Andric 50753f127fSDimitry Andric if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { 51753f127fSDimitry Andric auto __size = ranges::distance(__first, __last); 52753f127fSDimitry Andric if (__size < __count) { 53753f127fSDimitry Andric ranges::advance(__first, __last); 54753f127fSDimitry Andric return {__first, __first}; 55753f127fSDimitry Andric } 56753f127fSDimitry Andric 57753f127fSDimitry Andric if constexpr (random_access_iterator<_Iter1>) { 58bdd1243dSDimitry Andric auto __ret = std::__search_n_random_access_impl<_RangeAlgPolicy>( 59bdd1243dSDimitry Andric __first, __last, __count, __value, __pred, __proj, __size); 60753f127fSDimitry Andric return {std::move(__ret.first), std::move(__ret.second)}; 61753f127fSDimitry Andric } 62753f127fSDimitry Andric } 63753f127fSDimitry Andric 6406c3fb27SDimitry Andric auto __ret = std::__search_n_forward_impl<_RangeAlgPolicy>(__first, __last, __count, __value, __pred, __proj); 65753f127fSDimitry Andric return {std::move(__ret.first), std::move(__ret.second)}; 66753f127fSDimitry Andric } 67753f127fSDimitry Andric 6806c3fb27SDimitry Andric template <forward_iterator _Iter, 6906c3fb27SDimitry Andric sentinel_for<_Iter> _Sent, 70753f127fSDimitry Andric class _Type, 71753f127fSDimitry Andric class _Pred = ranges::equal_to, 72753f127fSDimitry Andric class _Proj = identity> 73753f127fSDimitry Andric requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj> 74*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter> 7506c3fb27SDimitry Andric operator()(_Iter __first, 7606c3fb27SDimitry Andric _Sent __last, 77753f127fSDimitry Andric iter_difference_t<_Iter> __count, 78753f127fSDimitry Andric const _Type& __value, 79753f127fSDimitry Andric _Pred __pred = {}, 80753f127fSDimitry Andric _Proj __proj = _Proj{}) const { 81753f127fSDimitry Andric return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj); 82753f127fSDimitry Andric } 83753f127fSDimitry Andric 84753f127fSDimitry Andric template <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity> 85753f127fSDimitry Andric requires indirectly_comparable<iterator_t<_Range>, const _Type*, _Pred, _Proj> 86*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range> operator()( 8706c3fb27SDimitry Andric _Range&& __range, range_difference_t<_Range> __count, const _Type& __value, _Pred __pred = {}, _Proj __proj = {}) 8806c3fb27SDimitry Andric const { 89753f127fSDimitry Andric auto __first = ranges::begin(__range); 90753f127fSDimitry Andric if (__count <= 0) 91753f127fSDimitry Andric return {__first, __first}; 92753f127fSDimitry Andric if constexpr (sized_range<_Range>) { 93753f127fSDimitry Andric auto __size1 = ranges::size(__range); 94753f127fSDimitry Andric if (__size1 < static_cast<range_size_t<_Range>>(__count)) { 95753f127fSDimitry Andric ranges::advance(__first, ranges::end(__range)); 96753f127fSDimitry Andric return {__first, __first}; 97753f127fSDimitry Andric } 98753f127fSDimitry Andric } 99753f127fSDimitry Andric 100753f127fSDimitry Andric return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj); 101753f127fSDimitry Andric } 102753f127fSDimitry Andric }; 103753f127fSDimitry Andric } // namespace __search_n 104753f127fSDimitry Andric 105753f127fSDimitry Andric inline namespace __cpo { 106753f127fSDimitry Andric inline constexpr auto search_n = __search_n::__fn{}; 107753f127fSDimitry Andric } // namespace __cpo 108753f127fSDimitry Andric } // namespace ranges 109753f127fSDimitry Andric 110753f127fSDimitry Andric _LIBCPP_END_NAMESPACE_STD 111753f127fSDimitry Andric 11206c3fb27SDimitry Andric #endif // _LIBCPP_STD_VER >= 20 113753f127fSDimitry Andric 114b3edf446SDimitry Andric _LIBCPP_POP_MACROS 115b3edf446SDimitry Andric 116753f127fSDimitry Andric #endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H 117