1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H 10 #define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H 11 12 #include <__config> 13 #include <__functional/identity.h> 14 #include <__functional/invoke.h> 15 #include <__functional/ranges_operations.h> 16 #include <__iterator/concepts.h> 17 #include <__iterator/indirectly_comparable.h> 18 #include <__iterator/next.h> 19 #include <__iterator/prev.h> 20 #include <__iterator/projected.h> 21 #include <__ranges/access.h> 22 #include <__ranges/concepts.h> 23 #include <__ranges/subrange.h> 24 #include <__utility/forward.h> 25 #include <__utility/move.h> 26 27 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 28 # pragma GCC system_header 29 #endif 30 31 _LIBCPP_PUSH_MACROS 32 #include <__undef_macros> 33 34 #if _LIBCPP_STD_VER >= 23 35 36 _LIBCPP_BEGIN_NAMESPACE_STD 37 38 namespace ranges { 39 40 template <class _Iter, class _Sent, class _Pred, class _Proj> 41 _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter> 42 __find_last_impl(_Iter __first, _Sent __last, _Pred __pred, _Proj& __proj) { 43 if (__first == __last) { 44 return subrange<_Iter>(__first, __first); 45 } 46 47 if constexpr (bidirectional_iterator<_Iter>) { 48 auto __last_it = ranges::next(__first, __last); 49 for (auto __it = ranges::prev(__last_it); __it != __first; --__it) { 50 if (__pred(std::invoke(__proj, *__it))) { 51 return subrange<_Iter>(std::move(__it), std::move(__last_it)); 52 } 53 } 54 if (__pred(std::invoke(__proj, *__first))) { 55 return subrange<_Iter>(std::move(__first), std::move(__last_it)); 56 } 57 return subrange<_Iter>(__last_it, __last_it); 58 } else { 59 bool __found = false; 60 _Iter __found_it; 61 for (; __first != __last; ++__first) { 62 if (__pred(std::invoke(__proj, *__first))) { 63 __found = true; 64 __found_it = __first; 65 } 66 } 67 68 if (__found) { 69 return subrange<_Iter>(std::move(__found_it), std::move(__first)); 70 } else { 71 return subrange<_Iter>(__first, __first); 72 } 73 } 74 } 75 76 struct __find_last { 77 template <class _Type> 78 struct __op { 79 const _Type& __value; 80 template <class _Elem> 81 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const { 82 return std::forward<_Elem>(__elem) == __value; 83 } 84 }; 85 86 template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity> 87 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*> 88 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter> 89 operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) { 90 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Type>{__value}, __proj); 91 } 92 93 template <forward_range _Range, class _Type, class _Proj = identity> 94 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> 95 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range> 96 operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) { 97 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Type>{__value}, __proj); 98 } 99 }; 100 101 struct __find_last_if { 102 template <class _Pred> 103 struct __op { 104 _Pred& __pred; 105 template <class _Elem> 106 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const { 107 return std::invoke(__pred, std::forward<_Elem>(__elem)); 108 } 109 }; 110 111 template <forward_iterator _Iter, 112 sentinel_for<_Iter> _Sent, 113 class _Proj = identity, 114 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 115 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter> 116 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) { 117 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj); 118 } 119 120 template <forward_range _Range, 121 class _Proj = identity, 122 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> 123 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range> 124 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) { 125 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj); 126 } 127 }; 128 129 struct __find_last_if_not { 130 template <class _Pred> 131 struct __op { 132 _Pred& __pred; 133 template <class _Elem> 134 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const { 135 return !std::invoke(__pred, std::forward<_Elem>(__elem)); 136 } 137 }; 138 139 template <forward_iterator _Iter, 140 sentinel_for<_Iter> _Sent, 141 class _Proj = identity, 142 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 143 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter> 144 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) { 145 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj); 146 } 147 148 template <forward_range _Range, 149 class _Proj = identity, 150 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> 151 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range> 152 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) { 153 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj); 154 } 155 }; 156 157 inline namespace __cpo { 158 inline constexpr auto find_last = __find_last{}; 159 inline constexpr auto find_last_if = __find_last_if{}; 160 inline constexpr auto find_last_if_not = __find_last_if_not{}; 161 } // namespace __cpo 162 } // namespace ranges 163 164 _LIBCPP_END_NAMESPACE_STD 165 166 #endif // _LIBCPP_STD_VER >= 23 167 168 _LIBCPP_POP_MACROS 169 170 #endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H 171