__cxx03/__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___CXX03___ALGORITHM_RANGES_SEARCH_N_H
0010 #define _LIBCPP___CXX03___ALGORITHM_RANGES_SEARCH_N_H
0011
0012 #include <__cxx03/__algorithm/iterator_operations.h>
0013 #include <__cxx03/__algorithm/search_n.h>
0014 #include <__cxx03/__config>
0015 #include <__cxx03/__functional/identity.h>
0016 #include <__cxx03/__functional/ranges_operations.h>
0017 #include <__cxx03/__iterator/advance.h>
0018 #include <__cxx03/__iterator/concepts.h>
0019 #include <__cxx03/__iterator/distance.h>
0020 #include <__cxx03/__iterator/incrementable_traits.h>
0021 #include <__cxx03/__iterator/indirectly_comparable.h>
0022 #include <__cxx03/__iterator/iterator_traits.h>
0023 #include <__cxx03/__ranges/access.h>
0024 #include <__cxx03/__ranges/concepts.h>
0025 #include <__cxx03/__ranges/size.h>
0026 #include <__cxx03/__ranges/subrange.h>
0027 #include <__cxx03/__utility/move.h>
0028 #include <__cxx03/__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 <__cxx03/__undef_macros>
0036
0037 #if _LIBCPP_STD_VER >= 20
0038
0039 _LIBCPP_BEGIN_NAMESPACE_STD
0040
0041 namespace ranges {
0042 namespace __search_n {
0043 struct __fn {
0044   template <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj>
0045   _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl(
0046       _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) {
0047     if (__count == 0)
0048       return {__first, __first};
0049
0050     if constexpr (sized_sentinel_for<_Sent1, _Iter1>) {
0051       auto __size = ranges::distance(__first, __last);
0052       if (__size < __count) {
0053         ranges::advance(__first, __last);
0054         return {__first, __first};
0055       }
0056
0057       if constexpr (random_access_iterator<_Iter1>) {
0058         auto __ret = std::__search_n_random_access_impl<_RangeAlgPolicy>(
0059             __first, __last, __count, __value, __pred, __proj, __size);
0060         return {std::move(__ret.first), std::move(__ret.second)};
0061       }
0062     }
0063
0064     auto __ret = std::__search_n_forward_impl<_RangeAlgPolicy>(__first, __last, __count, __value, __pred, __proj);
0065     return {std::move(__ret.first), std::move(__ret.second)};
0066   }
0067
0068   template <forward_iterator _Iter,
0069             sentinel_for<_Iter> _Sent,
0070             class _Type,
0071             class _Pred = ranges::equal_to,
0072             class _Proj = identity>
0073     requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj>
0074   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
0075   operator()(_Iter __first,
0076              _Sent __last,
0077              iter_difference_t<_Iter> __count,
0078              const _Type& __value,
0079              _Pred __pred = {},
0080              _Proj __proj = _Proj{}) const {
0081     return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj);
0082   }
0083
0084   template <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity>
0085     requires indirectly_comparable<iterator_t<_Range>, const _Type*, _Pred, _Proj>
0086   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range> operator()(
0087       _Range&& __range, range_difference_t<_Range> __count, const _Type& __value, _Pred __pred = {}, _Proj __proj = {})
0088       const {
0089     auto __first = ranges::begin(__range);
0090     if (__count <= 0)
0091       return {__first, __first};
0092     if constexpr (sized_range<_Range>) {
0093       auto __size1 = ranges::size(__range);
0094       if (__size1 < static_cast<range_size_t<_Range>>(__count)) {
0095         ranges::advance(__first, ranges::end(__range));
0096         return {__first, __first};
0097       }
0098     }
0099
0100     return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj);
0101   }
0102 };
0103 } // namespace __search_n
0104
0105 inline namespace __cpo {
0106 inline constexpr auto search_n = __search_n::__fn{};
0107 } // namespace __cpo
0108 } // namespace ranges
0109
0110 _LIBCPP_END_NAMESPACE_STD
0111
0112 #endif // _LIBCPP_STD_VER >= 20
0113
0114 _LIBCPP_POP_MACROS
0115
0116 #endif // _LIBCPP___CXX03___ALGORITHM_RANGES_SEARCH_N_H