1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5 // See https://llvm.org/LICENSE.txt for license information. 6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef _LIBCPP___RANGES_FILTER_VIEW_H 11 #define _LIBCPP___RANGES_FILTER_VIEW_H 12 13 #include <__algorithm/ranges_find_if.h> 14 #include <__assert> 15 #include <__concepts/constructible.h> 16 #include <__concepts/copyable.h> 17 #include <__concepts/derived_from.h> 18 #include <__concepts/equality_comparable.h> 19 #include <__config> 20 #include <__functional/bind_back.h> 21 #include <__functional/invoke.h> 22 #include <__functional/reference_wrapper.h> 23 #include <__iterator/concepts.h> 24 #include <__iterator/iter_move.h> 25 #include <__iterator/iter_swap.h> 26 #include <__iterator/iterator_traits.h> 27 #include <__memory/addressof.h> 28 #include <__ranges/access.h> 29 #include <__ranges/all.h> 30 #include <__ranges/concepts.h> 31 #include <__ranges/movable_box.h> 32 #include <__ranges/non_propagating_cache.h> 33 #include <__ranges/range_adaptor.h> 34 #include <__ranges/view_interface.h> 35 #include <__type_traits/conditional.h> 36 #include <__type_traits/decay.h> 37 #include <__type_traits/is_nothrow_constructible.h> 38 #include <__type_traits/is_object.h> 39 #include <__utility/forward.h> 40 #include <__utility/in_place.h> 41 #include <__utility/move.h> 42 43 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 44 # pragma GCC system_header 45 #endif 46 47 _LIBCPP_PUSH_MACROS 48 #include <__undef_macros> 49 50 _LIBCPP_BEGIN_NAMESPACE_STD 51 52 #if _LIBCPP_STD_VER >= 20 53 54 namespace ranges { 55 template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 56 requires view<_View> && is_object_v<_Pred> 57 class _LIBCPP_ABI_LLVM18_NO_UNIQUE_ADDRESS filter_view : public view_interface<filter_view<_View, _Pred>> { 58 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 59 _LIBCPP_NO_UNIQUE_ADDRESS __movable_box<_Pred> __pred_; 60 61 // We cache the result of begin() to allow providing an amortized O(1) begin() whenever 62 // the underlying range is at least a forward_range. 63 static constexpr bool _UseCache = forward_range<_View>; 64 using _Cache = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 65 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache(); 66 67 class __iterator; 68 class __sentinel; 69 70 public: 71 _LIBCPP_HIDE_FROM_ABI filter_view() 72 requires default_initializable<_View> && default_initializable<_Pred> 73 = default; 74 filter_view(_View __base,_Pred __pred)75 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 filter_view(_View __base, _Pred __pred) 76 : __base_(std::move(__base)), __pred_(in_place, std::move(__pred)) {} 77 78 template <class _Vp = _View> base()79 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 80 requires copy_constructible<_Vp> 81 { 82 return __base_; 83 } base()84 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 85 pred()86 _LIBCPP_HIDE_FROM_ABI constexpr _Pred const& pred() const { return *__pred_; } 87 begin()88 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 89 // Note: this duplicates a check in `optional` but provides a better error message. 90 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 91 __pred_.__has_value(), "Trying to call begin() on a filter_view that does not have a valid predicate."); 92 if constexpr (_UseCache) { 93 if (!__cached_begin_.__has_value()) { 94 __cached_begin_.__emplace(ranges::find_if(__base_, std::ref(*__pred_))); 95 } 96 return {*this, *__cached_begin_}; 97 } else { 98 return {*this, ranges::find_if(__base_, std::ref(*__pred_))}; 99 } 100 } 101 end()102 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 103 if constexpr (common_range<_View>) 104 return __iterator{*this, ranges::end(__base_)}; 105 else 106 return __sentinel{*this}; 107 } 108 }; 109 110 template <class _Range, class _Pred> 111 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>; 112 113 template <class _View> 114 struct __filter_iterator_category {}; 115 116 template <forward_range _View> 117 struct __filter_iterator_category<_View> { 118 using _Cat = typename iterator_traits<iterator_t<_View>>::iterator_category; 119 using iterator_category = 120 _If<derived_from<_Cat, bidirectional_iterator_tag>, 121 bidirectional_iterator_tag, 122 _If<derived_from<_Cat, forward_iterator_tag>, 123 forward_iterator_tag, 124 /* else */ _Cat >>; 125 }; 126 127 template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 128 requires view<_View> && is_object_v<_Pred> 129 class filter_view<_View, _Pred>::__iterator : public __filter_iterator_category<_View> { 130 public: 131 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __current_ = iterator_t<_View>(); 132 _LIBCPP_NO_UNIQUE_ADDRESS filter_view* __parent_ = nullptr; 133 134 using iterator_concept = 135 _If<bidirectional_range<_View>, 136 bidirectional_iterator_tag, 137 _If<forward_range<_View>, 138 forward_iterator_tag, 139 /* else */ input_iterator_tag >>; 140 // using iterator_category = inherited; 141 using value_type = range_value_t<_View>; 142 using difference_type = range_difference_t<_View>; 143 144 _LIBCPP_HIDE_FROM_ABI __iterator() 145 requires default_initializable<iterator_t<_View>> 146 = default; 147 148 _LIBCPP_HIDE_FROM_ABI constexpr __iterator(filter_view& __parent, iterator_t<_View> __current) 149 : __current_(std::move(__current)), __parent_(std::addressof(__parent)) {} 150 151 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> const& base() const& noexcept { return __current_; } 152 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() && { return std::move(__current_); } 153 154 _LIBCPP_HIDE_FROM_ABI constexpr range_reference_t<_View> operator*() const { return *__current_; } 155 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> operator->() const 156 requires __has_arrow<iterator_t<_View>> && copyable<iterator_t<_View>> 157 { 158 return __current_; 159 } 160 161 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 162 __current_ = 163 ranges::find_if(std::move(++__current_), ranges::end(__parent_->__base_), std::ref(*__parent_->__pred_)); 164 return *this; 165 } 166 _LIBCPP_HIDE_FROM_ABI constexpr void operator++(int) { ++*this; } 167 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) 168 requires forward_range<_View> 169 { 170 auto __tmp = *this; 171 ++*this; 172 return __tmp; 173 } 174 175 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() 176 requires bidirectional_range<_View> 177 { 178 do { 179 --__current_; 180 } while (!std::invoke(*__parent_->__pred_, *__current_)); 181 return *this; 182 } 183 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) 184 requires bidirectional_range<_View> 185 { 186 auto __tmp = *this; 187 --*this; 188 return __tmp; 189 } 190 191 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __iterator const& __y) 192 requires equality_comparable<iterator_t<_View>> 193 { 194 return __x.__current_ == __y.__current_; 195 } 196 197 _LIBCPP_HIDE_FROM_ABI friend constexpr range_rvalue_reference_t<_View> 198 iter_move(__iterator const& __it) noexcept(noexcept(ranges::iter_move(__it.__current_))) { 199 return ranges::iter_move(__it.__current_); 200 } 201 202 _LIBCPP_HIDE_FROM_ABI friend constexpr void 203 iter_swap(__iterator const& __x, 204 __iterator const& __y) noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) 205 requires indirectly_swappable<iterator_t<_View>> 206 { 207 return ranges::iter_swap(__x.__current_, __y.__current_); 208 } 209 }; 210 211 template <input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 212 requires view<_View> && is_object_v<_Pred> 213 class filter_view<_View, _Pred>::__sentinel { 214 public: 215 sentinel_t<_View> __end_ = sentinel_t<_View>(); 216 217 _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 218 219 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(filter_view& __parent) : __end_(ranges::end(__parent.__base_)) {} 220 221 _LIBCPP_HIDE_FROM_ABI constexpr sentinel_t<_View> base() const { return __end_; } 222 223 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(__iterator const& __x, __sentinel const& __y) { 224 return __x.__current_ == __y.__end_; 225 } 226 }; 227 228 namespace views { 229 namespace __filter { 230 struct __fn { 231 template <class _Range, class _Pred> 232 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pred&& __pred) const 233 noexcept(noexcept(filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)))) 234 -> decltype(filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred))) { 235 return filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)); 236 } 237 238 template <class _Pred> 239 requires constructible_from<decay_t<_Pred>, _Pred> 240 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pred&& __pred) const 241 noexcept(is_nothrow_constructible_v<decay_t<_Pred>, _Pred>) { 242 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pred>(__pred))); 243 } 244 }; 245 } // namespace __filter 246 247 inline namespace __cpo { 248 inline constexpr auto filter = __filter::__fn{}; 249 } // namespace __cpo 250 } // namespace views 251 252 } // namespace ranges 253 254 #endif // _LIBCPP_STD_VER >= 20 255 256 _LIBCPP_END_NAMESPACE_STD 257 258 _LIBCPP_POP_MACROS 259 260 #endif // _LIBCPP___RANGES_FILTER_VIEW_H 261