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/move.h> 25 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 # pragma GCC system_header 28 #endif 29 30 _LIBCPP_PUSH_MACROS 31 #include <__undef_macros> 32 33 #if _LIBCPP_STD_VER >= 23 34 35 _LIBCPP_BEGIN_NAMESPACE_STD 36 37 namespace ranges { 38 39 template <class _Iter, class _Sent, class _Pred, class _Proj> 40 _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter> 41 __find_last_impl(_Iter __first, _Sent __last, _Pred __pred, _Proj& __proj) { 42 if (__first == __last) { 43 return subrange<_Iter>(__first, __first); 44 } 45 46 if constexpr (bidirectional_iterator<_Iter>) { 47 auto __last_it = ranges::next(__first, __last); 48 for (auto __it = ranges::prev(__last_it); __it != __first; --__it) { 49 if (__pred(std::invoke(__proj, *__it))) { 50 return subrange<_Iter>(std::move(__it), std::move(__last_it)); 51 } 52 } 53 if (__pred(std::invoke(__proj, *__first))) { 54 return subrange<_Iter>(std::move(__first), std::move(__last_it)); 55 } 56 return subrange<_Iter>(__last_it, __last_it); 57 } else { 58 bool __found = false; 59 _Iter __found_it; 60 for (; __first != __last; ++__first) { 61 if (__pred(std::invoke(__proj, *__first))) { 62 __found = true; 63 __found_it = __first; 64 } 65 } 66 67 if (__found) { 68 return subrange<_Iter>(std::move(__found_it), std::move(__first)); 69 } else { 70 return subrange<_Iter>(__first, __first); 71 } 72 } 73 } 74 75 namespace __find_last { 76 struct __fn { 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 } // namespace __find_last 101 102 namespace __find_last_if { 103 struct __fn { 104 template <class _Pred> 105 struct __op { 106 _Pred& __pred; 107 template <class _Elem> 108 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const { 109 return std::invoke(__pred, std::forward<_Elem>(__elem)); 110 } 111 }; 112 113 template <forward_iterator _Iter, 114 sentinel_for<_Iter> _Sent, 115 class _Proj = identity, 116 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 117 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter> 118 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) { 119 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj); 120 } 121 122 template <forward_range _Range, 123 class _Proj = identity, 124 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> 125 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range> 126 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) { 127 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj); 128 } 129 }; 130 } // namespace __find_last_if 131 132 namespace __find_last_if_not { 133 struct __fn { 134 template <class _Pred> 135 struct __op { 136 _Pred& __pred; 137 template <class _Elem> 138 _LIBCPP_HIDE_FROM_ABI constexpr decltype(auto) operator()(_Elem&& __elem) const { 139 return !std::invoke(__pred, std::forward<_Elem>(__elem)); 140 } 141 }; 142 143 template <forward_iterator _Iter, 144 sentinel_for<_Iter> _Sent, 145 class _Proj = identity, 146 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> 147 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static subrange<_Iter> 148 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) { 149 return ranges::__find_last_impl(std::move(__first), std::move(__last), __op<_Pred>{__pred}, __proj); 150 } 151 152 template <forward_range _Range, 153 class _Proj = identity, 154 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> 155 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr static borrowed_subrange_t<_Range> 156 operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) { 157 return ranges::__find_last_impl(ranges::begin(__range), ranges::end(__range), __op<_Pred>{__pred}, __proj); 158 } 159 }; 160 } // namespace __find_last_if_not 161 162 inline namespace __cpo { 163 inline constexpr auto find_last = __find_last::__fn{}; 164 inline constexpr auto find_last_if = __find_last_if::__fn{}; 165 inline constexpr auto find_last_if_not = __find_last_if_not::__fn{}; 166 } // namespace __cpo 167 } // namespace ranges 168 169 _LIBCPP_END_NAMESPACE_STD 170 171 #endif // _LIBCPP_STD_VER >= 23 172 173 _LIBCPP_POP_MACROS 174 175 #endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H 176