v1/__algorithm/ranges_search_n.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H
0010 #define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H
0011
0012 #include <__algorithm/iterator_operations.h>
0013 #include <__algorithm/search_n.h>
0014 #include <__config>
0015 #include <__functional/identity.h>
0016 #include <__functional/ranges_operations.h>
0017 #include <__iterator/advance.h>
0018 #include <__iterator/concepts.h>
0019 #include <__iterator/distance.h>
0020 #include <__iterator/incrementable_traits.h>
0021 #include <__iterator/indirectly_comparable.h>
0022 #include <__iterator/iterator_traits.h>
0023 #include <__ranges/access.h>
0024 #include <__ranges/concepts.h>
0025 #include <__ranges/size.h>
0026 #include <__ranges/subrange.h>
0027 #include <__utility/move.h>
0028 #include <__utility/pair.h>
0029
0030 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0031 #  pragma GCC system_header
0032 #endif
0033
0034 _LIBCPP_PUSH_MACROS
0035 #include <__undef_macros>
0036
0037 #if _LIBCPP_STD_VER >= 20
0038
0039 _LIBCPP_BEGIN_NAMESPACE_STD
0040
0041 namespace ranges {
0042 struct __search_n {
0043   template <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj>
0044   _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl(
0045       _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) {
0046     if (__count == 0)
0047       return {__first, __first};
0048
0049     if constexpr (sized_sentinel_for<_Sent1, _Iter1>) {
0050       auto __size = ranges::distance(__first, __last);
0051       if (__size < __count) {
0052         ranges::advance(__first, __last);
0053         return {__first, __first};
0054       }
0055
0056       if constexpr (random_access_iterator<_Iter1>) {
0057         auto __ret = std::__search_n_random_access_impl<_RangeAlgPolicy>(
0058             __first, __last, __count, __value, __pred, __proj, __size);
0059         return {std::move(__ret.first), std::move(__ret.second)};
0060       }
0061     }
0062
0063     auto __ret = std::__search_n_forward_impl<_RangeAlgPolicy>(__first, __last, __count, __value, __pred, __proj);
0064     return {std::move(__ret.first), std::move(__ret.second)};
0065   }
0066
0067   template <forward_iterator _Iter,
0068             sentinel_for<_Iter> _Sent,
0069             class _Type,
0070             class _Pred = ranges::equal_to,
0071             class _Proj = identity>
0072     requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj>
0073   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
0074   operator()(_Iter __first,
0075              _Sent __last,
0076              iter_difference_t<_Iter> __count,
0077              const _Type& __value,
0078              _Pred __pred = {},
0079              _Proj __proj = _Proj{}) const {
0080     return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj);
0081   }
0082
0083   template <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity>
0084     requires indirectly_comparable<iterator_t<_Range>, const _Type*, _Pred, _Proj>
0085   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range> operator()(
0086       _Range&& __range, range_difference_t<_Range> __count, const _Type& __value, _Pred __pred = {}, _Proj __proj = {})
0087       const {
0088     auto __first = ranges::begin(__range);
0089     if (__count <= 0)
0090       return {__first, __first};
0091     if constexpr (sized_range<_Range>) {
0092       auto __size1 = ranges::size(__range);
0093       if (__size1 < static_cast<range_size_t<_Range>>(__count)) {
0094         ranges::advance(__first, ranges::end(__range));
0095         return {__first, __first};
0096       }
0097     }
0098
0099     return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj);
0100   }
0101 };
0102
0103 inline namespace __cpo {
0104 inline constexpr auto search_n = __search_n{};
0105 } // namespace __cpo
0106 } // namespace ranges
0107
0108 _LIBCPP_END_NAMESPACE_STD
0109
0110 #endif // _LIBCPP_STD_VER >= 20
0111
0112 _LIBCPP_POP_MACROS
0113
0114 #endif // _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H