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