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_BEGIN_NAMESPACE_STD 48 49 #if _LIBCPP_STD_VER >= 20 50 51 namespace ranges { 52 template<input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 53 requires view<_View> && is_object_v<_Pred> 54 class filter_view : public view_interface<filter_view<_View, _Pred>> { 55 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 56 _LIBCPP_NO_UNIQUE_ADDRESS __movable_box<_Pred> __pred_; 57 58 // We cache the result of begin() to allow providing an amortized O(1) begin() whenever 59 // the underlying range is at least a forward_range. 60 static constexpr bool _UseCache = forward_range<_View>; 61 using _Cache = _If<_UseCache, __non_propagating_cache<iterator_t<_View>>, __empty_cache>; 62 _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cached_begin_ = _Cache(); 63 64 class __iterator; 65 class __sentinel; 66 67 public: 68 _LIBCPP_HIDE_FROM_ABI 69 filter_view() requires default_initializable<_View> && default_initializable<_Pred> = default; 70 71 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 filter_view(_View __base, _Pred __pred) 72 : __base_(std::move(__base)), __pred_(in_place, std::move(__pred)) {} 73 74 template<class _Vp = _View> 75 _LIBCPP_HIDE_FROM_ABI 76 constexpr _View base() const& requires copy_constructible<_Vp> { return __base_; } 77 _LIBCPP_HIDE_FROM_ABI 78 constexpr _View base() && { return std::move(__base_); } 79 80 _LIBCPP_HIDE_FROM_ABI 81 constexpr _Pred const& pred() const { return *__pred_; } 82 83 _LIBCPP_HIDE_FROM_ABI 84 constexpr __iterator begin() { 85 _LIBCPP_ASSERT_UNCATEGORIZED( 86 __pred_.__has_value(), 87 "Trying to call begin() on a filter_view that does not have a valid predicate."); 88 if constexpr (_UseCache) { 89 if (!__cached_begin_.__has_value()) { 90 __cached_begin_.__emplace(ranges::find_if(__base_, std::ref(*__pred_))); 91 } 92 return {*this, *__cached_begin_}; 93 } else { 94 return {*this, ranges::find_if(__base_, std::ref(*__pred_))}; 95 } 96 } 97 98 _LIBCPP_HIDE_FROM_ABI 99 constexpr auto end() { 100 if constexpr (common_range<_View>) 101 return __iterator{*this, ranges::end(__base_)}; 102 else 103 return __sentinel{*this}; 104 } 105 }; 106 107 template<class _Range, class _Pred> 108 filter_view(_Range&&, _Pred) -> filter_view<views::all_t<_Range>, _Pred>; 109 110 template<class _View> 111 struct __filter_iterator_category { }; 112 113 template<forward_range _View> 114 struct __filter_iterator_category<_View> { 115 using _Cat = typename iterator_traits<iterator_t<_View>>::iterator_category; 116 using iterator_category = 117 _If<derived_from<_Cat, bidirectional_iterator_tag>, bidirectional_iterator_tag, 118 _If<derived_from<_Cat, forward_iterator_tag>, forward_iterator_tag, 119 /* else */ _Cat 120 >>; 121 }; 122 123 template<input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 124 requires view<_View> && is_object_v<_Pred> 125 class filter_view<_View, _Pred>::__iterator : public __filter_iterator_category<_View> { 126 127 public: 128 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __current_ = iterator_t<_View>(); 129 _LIBCPP_NO_UNIQUE_ADDRESS filter_view* __parent_ = nullptr; 130 131 using iterator_concept = 132 _If<bidirectional_range<_View>, bidirectional_iterator_tag, 133 _If<forward_range<_View>, forward_iterator_tag, 134 /* else */ input_iterator_tag 135 >>; 136 // using iterator_category = inherited; 137 using value_type = range_value_t<_View>; 138 using difference_type = range_difference_t<_View>; 139 140 _LIBCPP_HIDE_FROM_ABI 141 __iterator() requires default_initializable<iterator_t<_View>> = default; 142 143 _LIBCPP_HIDE_FROM_ABI 144 constexpr __iterator(filter_view& __parent, iterator_t<_View> __current) 145 : __current_(std::move(__current)), __parent_(std::addressof(__parent)) 146 { } 147 148 _LIBCPP_HIDE_FROM_ABI 149 constexpr iterator_t<_View> const& base() const& noexcept { return __current_; } 150 _LIBCPP_HIDE_FROM_ABI 151 constexpr iterator_t<_View> base() && { return std::move(__current_); } 152 153 _LIBCPP_HIDE_FROM_ABI 154 constexpr range_reference_t<_View> operator*() const { return *__current_; } 155 _LIBCPP_HIDE_FROM_ABI 156 constexpr iterator_t<_View> operator->() const 157 requires __has_arrow<iterator_t<_View>> && copyable<iterator_t<_View>> 158 { 159 return __current_; 160 } 161 162 _LIBCPP_HIDE_FROM_ABI 163 constexpr __iterator& operator++() { 164 __current_ = ranges::find_if(std::move(++__current_), ranges::end(__parent_->__base_), 165 std::ref(*__parent_->__pred_)); 166 return *this; 167 } 168 _LIBCPP_HIDE_FROM_ABI 169 constexpr void operator++(int) { ++*this; } 170 _LIBCPP_HIDE_FROM_ABI 171 constexpr __iterator operator++(int) requires forward_range<_View> { 172 auto __tmp = *this; 173 ++*this; 174 return __tmp; 175 } 176 177 _LIBCPP_HIDE_FROM_ABI 178 constexpr __iterator& operator--() requires bidirectional_range<_View> { 179 do { 180 --__current_; 181 } while (!std::invoke(*__parent_->__pred_, *__current_)); 182 return *this; 183 } 184 _LIBCPP_HIDE_FROM_ABI 185 constexpr __iterator operator--(int) requires bidirectional_range<_View> { 186 auto __tmp = *this; 187 --*this; 188 return __tmp; 189 } 190 191 _LIBCPP_HIDE_FROM_ABI 192 friend constexpr bool operator==(__iterator const& __x, __iterator const& __y) 193 requires equality_comparable<iterator_t<_View>> 194 { 195 return __x.__current_ == __y.__current_; 196 } 197 198 _LIBCPP_HIDE_FROM_ABI 199 friend constexpr range_rvalue_reference_t<_View> iter_move(__iterator const& __it) 200 noexcept(noexcept(ranges::iter_move(__it.__current_))) 201 { 202 return ranges::iter_move(__it.__current_); 203 } 204 205 _LIBCPP_HIDE_FROM_ABI 206 friend constexpr void iter_swap(__iterator const& __x, __iterator const& __y) 207 noexcept(noexcept(ranges::iter_swap(__x.__current_, __y.__current_))) 208 requires indirectly_swappable<iterator_t<_View>> 209 { 210 return ranges::iter_swap(__x.__current_, __y.__current_); 211 } 212 }; 213 214 template<input_range _View, indirect_unary_predicate<iterator_t<_View>> _Pred> 215 requires view<_View> && is_object_v<_Pred> 216 class filter_view<_View, _Pred>::__sentinel { 217 public: 218 sentinel_t<_View> __end_ = sentinel_t<_View>(); 219 220 _LIBCPP_HIDE_FROM_ABI 221 __sentinel() = default; 222 223 _LIBCPP_HIDE_FROM_ABI 224 constexpr explicit __sentinel(filter_view& __parent) 225 : __end_(ranges::end(__parent.__base_)) 226 { } 227 228 _LIBCPP_HIDE_FROM_ABI 229 constexpr sentinel_t<_View> base() const { return __end_; } 230 231 _LIBCPP_HIDE_FROM_ABI friend constexpr bool 232 operator==(__iterator const& __x, __sentinel const& __y) { 233 return __x.__current_ == __y.__end_; 234 } 235 }; 236 237 namespace views { 238 namespace __filter { 239 struct __fn { 240 template<class _Range, class _Pred> 241 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 242 constexpr auto operator()(_Range&& __range, _Pred&& __pred) const 243 noexcept(noexcept(filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)))) 244 -> decltype( filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred))) 245 { return filter_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)); } 246 247 template<class _Pred> 248 requires constructible_from<decay_t<_Pred>, _Pred> 249 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI 250 constexpr auto operator()(_Pred&& __pred) const 251 noexcept(is_nothrow_constructible_v<decay_t<_Pred>, _Pred>) 252 { return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pred>(__pred))); } 253 }; 254 } // namespace __filter 255 256 inline namespace __cpo { 257 inline constexpr auto filter = __filter::__fn{}; 258 } // namespace __cpo 259 } // namespace views 260 261 } // namespace ranges 262 263 #endif // _LIBCPP_STD_VER >= 20 264 265 _LIBCPP_END_NAMESPACE_STD 266 267 #endif // _LIBCPP___RANGES_FILTER_VIEW_H 268