171 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H10#define _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H11 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_header29#endif30 31_LIBCPP_PUSH_MACROS32#include <__undef_macros>33 34#if _LIBCPP_STD_VER >= 2335 36_LIBCPP_BEGIN_NAMESPACE_STD37 38namespace ranges {39 40template <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 76struct __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 101struct __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 129struct __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 157inline namespace __cpo {158inline constexpr auto find_last = __find_last{};159inline constexpr auto find_last_if = __find_last_if{};160inline constexpr auto find_last_if_not = __find_last_if_not{};161} // namespace __cpo162} // namespace ranges163 164_LIBCPP_END_NAMESPACE_STD165 166#endif // _LIBCPP_STD_VER >= 23167 168_LIBCPP_POP_MACROS169 170#endif // _LIBCPP___ALGORITHM_RANGES_FIND_LAST_H171