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