v1/__algorithm/ranges_find_last.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_FIND_LAST_H
0010 #define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H
0011
0012 #include <__config>
0013 #include <__functional/identity.h>
0014 #include <__functional/invoke.h>
0015 #include <__functional/ranges_operations.h>
0016 #include <__iterator/concepts.h>
0017 #include <__iterator/indirectly_comparable.h>
0018 #include <__iterator/next.h>
0019 #include <__iterator/prev.h>
0020 #include <__iterator/projected.h>
0021 #include <__ranges/access.h>
0022 #include <__ranges/concepts.h>
0023 #include <__ranges/subrange.h>
0024 #include <__utility/forward.h>
0025 #include <__utility/move.h>
0026
0027 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0028 #  pragma GCC system_header
0029 #endif
0030
0031 _LIBCPP_PUSH_MACROS
0032 #include <__undef_macros>
0033
0034 #if _LIBCPP_STD_VER >= 23
0035
0036 _LIBCPP_BEGIN_NAMESPACE_STD
0037
0038 namespace ranges {
0039
0040 template <class _Iter, class _Sent, class _Pred, class _Proj>
0041 _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
0042 __find_last_impl(_Iter __first, _Sent __last, _Pred __pred, _Proj& __proj) {
0043   if (__first == __last) {
0044     return subrange<_Iter>(__first, __first);
0045   }
0046
0047   if constexpr (bidirectional_iterator<_Iter>) {
0048     auto __last_it = ranges::next(__first, __last);
0049     for (auto __it = ranges::prev(__last_it); __it != __first; --__it) {
0050       if (__pred(std::invoke(__proj, *__it))) {
0051         return subrange<_Iter>(std::move(__it), std::move(__last_it));
0052       }
0053     }
0054     if (__pred(std::invoke(__proj, *__first))) {
0055       return subrange<_Iter>(std::move(__first), std::move(__last_it));
0056     }
0057     return subrange<_Iter>(__last_it, __last_it);
0058   } else {
0059     bool __found = false;
0060     _Iter __found_it;
0061     for (; __first != __last; ++__first) {
0062       if (__pred(std::invoke(__proj, *__first))) {
0063         __found    = true;
0064         __found_it = __first;
0065       }
0066     }
0067
0068     if (__found) {
0069       return subrange<_Iter>(std::move(__found_it), std::move(__first));
0070     } else {
0071       return subrange<_Iter>(__first, __first);
0072     }
0073   }
0074 }
0075
0076 struct __find_last {
0077   template <class _Type>
0078   struct __op {
0079     const _Type& __value;
0080     template <class _Elem>
0081     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
0082       return std::forward<_Elem>(__elem) == __value;
0083     }
0084   };
0085
0086   template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
0087     requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
0088   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
0089   operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) {
0090     return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Type>{__value}, __proj);
0091   }
0092
0093   template <forward_range _Range, class _Type, class _Proj = identity>
0094     requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
0095   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
0096   operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) {
0097     return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Type>{__value}, __proj);
0098   }
0099 };
0100
0101 struct __find_last_if {
0102   template <class _Pred>
0103   struct __op {
0104     _Pred& __pred;
0105     template <class _Elem>
0106     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
0107       return std::invoke(__pred, std::forward<_Elem>(__elem));
0108     }
0109   };
0110
0111   template <forward_iterator _Iter,
0112             sentinel_for<_Iter> _Sent,
0113             class _Proj = identity,
0114             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
0115   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
0116   operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
0117     return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
0118   }
0119
0120   template <forward_range _Range,
0121             class _Proj = identity,
0122             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
0123   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
0124   operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
0125     return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
0126   }
0127 };
0128
0129 struct __find_last_if_not {
0130   template <class _Pred>
0131   struct __op {
0132     _Pred& __pred;
0133     template <class _Elem>
0134     _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const {
0135       return !std::invoke(__pred, std::forward<_Elem>(__elem));
0136     }
0137   };
0138
0139   template <forward_iterator _Iter,
0140             sentinel_for<_Iter> _Sent,
0141             class _Proj = identity,
0142             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
0143   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter>
0144   operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) {
0145     return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj);
0146   }
0147
0148   template <forward_range _Range,
0149             class _Proj = identity,
0150             indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
0151   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range>
0152   operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) {
0153     return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj);
0154   }
0155 };
0156
0157 inline namespace __cpo {
0158 inline constexpr auto find_last        = __find_last{};
0159 inline constexpr auto find_last_if     = __find_last_if{};
0160 inline constexpr auto find_last_if_not = __find_last_if_not{};
0161 } // namespace __cpo
0162 } // namespace ranges
0163
0164 _LIBCPP_END_NAMESPACE_STD
0165
0166 #endif // _LIBCPP_STD_VER >= 23
0167
0168 _LIBCPP_POP_MACROS
0169
0170 #endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H