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_CHUNK_BY_VIEW_H 11 #define _LIBCPP___RANGES_CHUNK_BY_VIEW_H 12 13 #include <__algorithm/ranges_adjacent_find.h> 14 #include <__assert> 15 #include <__concepts/constructible.h> 16 #include <__config> 17 #include <__functional/bind_back.h> 18 #include <__functional/invoke.h> 19 #include <__iterator/concepts.h> 20 #include <__iterator/default_sentinel.h> 21 #include <__iterator/iterator_traits.h> 22 #include <__iterator/next.h> 23 #include <__iterator/prev.h> 24 #include <__memory/addressof.h> 25 #include <__ranges/access.h> 26 #include <__ranges/all.h> 27 #include <__ranges/concepts.h> 28 #include <__ranges/movable_box.h> 29 #include <__ranges/non_propagating_cache.h> 30 #include <__ranges/range_adaptor.h> 31 #include <__ranges/reverse_view.h> 32 #include <__ranges/subrange.h> 33 #include <__ranges/view_interface.h> 34 #include <__type_traits/conditional.h> 35 #include <__type_traits/decay.h> 36 #include <__type_traits/is_nothrow_constructible.h> 37 #include <__type_traits/is_object.h> 38 #include <__utility/forward.h> 39 #include <__utility/in_place.h> 40 #include <__utility/move.h> 41 42 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 43 # pragma GCC system_header 44 #endif 45 46 _LIBCPP_PUSH_MACROS 47 #include <__undef_macros> 48 49 _LIBCPP_BEGIN_NAMESPACE_STD 50 51 #if _LIBCPP_STD_VER >= 23 52 53 namespace ranges { 54 55 template <forward_range _View, indirect_binary_predicate<iterator_t<_View>, iterator_t<_View>> _Pred> 56 requires view<_View> && is_object_v<_Pred> 57 class _LIBCPP_ABI_LLVM18_NO_UNIQUE_ADDRESS chunk_by_view : public view_interface<chunk_by_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). 62 using _Cache = __non_propagating_cache<iterator_t<_View>>; 63 _Cache __cached_begin_; 64 65 class __iterator; 66 __find_next(iterator_t<_View> __current)67 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> __find_next(iterator_t<_View> __current) { 68 // Note: this duplicates a check in `optional` but provides a better error message. 69 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 70 __pred_.__has_value(), "Trying to call __find_next() on a chunk_by_view that does not have a valid predicate."); 71 auto __reversed_pred = [this]<class _Tp, class _Up>(_Tp&& __x, _Up&& __y) -> bool { 72 return !std::invoke(*__pred_, std::forward<_Tp>(__x), std::forward<_Up>(__y)); 73 }; 74 return ranges::next( 75 ranges::adjacent_find(__current, ranges::end(__base_), __reversed_pred), 1, ranges::end(__base_)); 76 } 77 __find_prev(iterator_t<_View> __current)78 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> __find_prev(iterator_t<_View> __current) 79 requires bidirectional_range<_View> 80 { 81 // Attempting to decrement a begin iterator is a no-op (`__find_prev` would return the same argument given to it). 82 _LIBCPP_ASSERT_PEDANTIC(__current != ranges::begin(__base_), "Trying to call __find_prev() on a begin iterator."); 83 // Note: this duplicates a check in `optional` but provides a better error message. 84 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 85 __pred_.__has_value(), "Trying to call __find_prev() on a chunk_by_view that does not have a valid predicate."); 86 87 auto __first = ranges::begin(__base_); 88 reverse_view __reversed{subrange{__first, __current}}; 89 auto __reversed_pred = [this]<class _Tp, class _Up>(_Tp&& __x, _Up&& __y) -> bool { 90 return !std::invoke(*__pred_, std::forward<_Up>(__y), std::forward<_Tp>(__x)); 91 }; 92 return ranges::prev(ranges::adjacent_find(__reversed, __reversed_pred).base(), 1, std::move(__first)); 93 } 94 95 public: 96 _LIBCPP_HIDE_FROM_ABI chunk_by_view() 97 requires default_initializable<_View> && default_initializable<_Pred> 98 = default; 99 chunk_by_view(_View __base,_Pred __pred)100 _LIBCPP_HIDE_FROM_ABI constexpr explicit chunk_by_view(_View __base, _Pred __pred) 101 : __base_(std::move(__base)), __pred_(in_place, std::move(__pred)) {} 102 base()103 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 104 requires copy_constructible<_View> 105 { 106 return __base_; 107 } 108 base()109 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 110 pred()111 _LIBCPP_HIDE_FROM_ABI constexpr const _Pred& pred() const { return *__pred_; } 112 begin()113 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 114 // Note: this duplicates a check in `optional` but provides a better error message. 115 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 116 __pred_.__has_value(), "Trying to call begin() on a chunk_by_view that does not have a valid predicate."); 117 118 auto __first = ranges::begin(__base_); 119 if (!__cached_begin_.__has_value()) { 120 __cached_begin_.__emplace(__find_next(__first)); 121 } 122 return {*this, std::move(__first), *__cached_begin_}; 123 } 124 end()125 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 126 if constexpr (common_range<_View>) { 127 return __iterator{*this, ranges::end(__base_), ranges::end(__base_)}; 128 } else { 129 return default_sentinel; 130 } 131 } 132 }; 133 134 template <class _Range, class _Pred> 135 chunk_by_view(_Range&&, _Pred) -> chunk_by_view<views::all_t<_Range>, _Pred>; 136 137 template <forward_range _View, indirect_binary_predicate<iterator_t<_View>, iterator_t<_View>> _Pred> 138 requires view<_View> && is_object_v<_Pred> 139 class chunk_by_view<_View, _Pred>::__iterator { 140 friend chunk_by_view; 141 142 chunk_by_view* __parent_ = nullptr; 143 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __current_ = iterator_t<_View>(); 144 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __next_ = iterator_t<_View>(); 145 __iterator(chunk_by_view & __parent,iterator_t<_View> __current,iterator_t<_View> __next)146 _LIBCPP_HIDE_FROM_ABI constexpr __iterator( 147 chunk_by_view& __parent, iterator_t<_View> __current, iterator_t<_View> __next) 148 : __parent_(std::addressof(__parent)), __current_(__current), __next_(__next) {} 149 150 public: 151 using value_type = subrange<iterator_t<_View>>; 152 using difference_type = range_difference_t<_View>; 153 using iterator_category = input_iterator_tag; 154 using iterator_concept = conditional_t<bidirectional_range<_View>, bidirectional_iterator_tag, forward_iterator_tag>; 155 156 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 157 158 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { 159 // If the iterator is at end, this would return an empty range which can be checked by the calling code and doesn't 160 // necessarily lead to a bad access. 161 _LIBCPP_ASSERT_PEDANTIC(__current_ != __next_, "Trying to dereference past-the-end chunk_by_view iterator."); 162 return {__current_, __next_}; 163 } 164 165 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 166 // Attempting to increment an end iterator is a no-op (`__find_next` would return the same argument given to it). 167 _LIBCPP_ASSERT_PEDANTIC(__current_ != __next_, "Trying to increment past end chunk_by_view iterator."); 168 __current_ = __next_; 169 __next_ = __parent_->__find_next(__current_); 170 return *this; 171 } 172 173 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { 174 auto __tmp = *this; 175 ++*this; 176 return __tmp; 177 } 178 179 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator--() 180 requires bidirectional_range<_View> 181 { 182 __next_ = __current_; 183 __current_ = __parent_->__find_prev(__next_); 184 return *this; 185 } 186 187 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator--(int) 188 requires bidirectional_range<_View> 189 { 190 auto __tmp = *this; 191 --*this; 192 return __tmp; 193 } 194 195 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) { 196 return __x.__current_ == __y.__current_; 197 } 198 199 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, default_sentinel_t) { 200 return __x.__current_ == __x.__next_; 201 } 202 }; 203 204 namespace views { 205 namespace __chunk_by { 206 struct __fn { 207 template <class _Range, class _Pred> 208 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Range&& __range, _Pred&& __pred) const 209 noexcept(noexcept(/**/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)))) 210 -> decltype(/*--*/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred))) { 211 return /*-------------*/ chunk_by_view(std::forward<_Range>(__range), std::forward<_Pred>(__pred)); 212 } 213 214 template <class _Pred> 215 requires constructible_from<decay_t<_Pred>, _Pred> operator__fn216 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pred&& __pred) const 217 noexcept(is_nothrow_constructible_v<decay_t<_Pred>, _Pred>) { 218 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pred>(__pred))); 219 } 220 }; 221 } // namespace __chunk_by 222 223 inline namespace __cpo { 224 inline constexpr auto chunk_by = __chunk_by::__fn{}; 225 } // namespace __cpo 226 } // namespace views 227 } // namespace ranges 228 229 #endif // _LIBCPP_STD_VER >= 23 230 231 _LIBCPP_END_NAMESPACE_STD 232 233 _LIBCPP_POP_MACROS 234 235 #endif // _LIBCPP___RANGES_CHUNK_BY_VIEW_H 236