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_SPLIT_VIEW_H 11 #define _LIBCPP___RANGES_SPLIT_VIEW_H 12 13 #include <__algorithm/ranges_search.h> 14 #include <__concepts/constructible.h> 15 #include <__config> 16 #include <__functional/bind_back.h> 17 #include <__functional/ranges_operations.h> 18 #include <__iterator/indirectly_comparable.h> 19 #include <__iterator/iterator_traits.h> 20 #include <__memory/addressof.h> 21 #include <__ranges/access.h> 22 #include <__ranges/all.h> 23 #include <__ranges/concepts.h> 24 #include <__ranges/empty.h> 25 #include <__ranges/non_propagating_cache.h> 26 #include <__ranges/range_adaptor.h> 27 #include <__ranges/single_view.h> 28 #include <__ranges/subrange.h> 29 #include <__ranges/view_interface.h> 30 #include <__type_traits/decay.h> 31 #include <__type_traits/is_nothrow_constructible.h> 32 #include <__utility/forward.h> 33 #include <__utility/move.h> 34 35 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 36 # pragma GCC system_header 37 #endif 38 39 _LIBCPP_PUSH_MACROS 40 #include <__undef_macros> 41 42 _LIBCPP_BEGIN_NAMESPACE_STD 43 44 #if _LIBCPP_STD_VER >= 20 45 46 namespace ranges { 47 48 template <forward_range _View, forward_range _Pattern> 49 requires view<_View> && view<_Pattern> && 50 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 51 class split_view : public view_interface<split_view<_View, _Pattern>> { 52 private: 53 _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View(); 54 _LIBCPP_NO_UNIQUE_ADDRESS _Pattern __pattern_ = _Pattern(); 55 using _Cache = __non_propagating_cache<subrange<iterator_t<_View>>>; 56 _Cache __cached_begin_ = _Cache(); 57 58 template <class, class> 59 friend struct __iterator; 60 61 template <class, class> 62 friend struct __sentinel; 63 64 struct __iterator; 65 struct __sentinel; 66 67 _LIBCPP_HIDE_FROM_ABI constexpr subrange<iterator_t<_View>> __find_next(iterator_t<_View> __it) { 68 auto [__begin, __end] = ranges::search(subrange(__it, ranges::end(__base_)), __pattern_); 69 if (__begin != ranges::end(__base_) && ranges::empty(__pattern_)) { 70 ++__begin; 71 ++__end; 72 } 73 return {__begin, __end}; 74 } 75 76 public: 77 _LIBCPP_HIDE_FROM_ABI split_view() 78 requires default_initializable<_View> && default_initializable<_Pattern> 79 = default; 80 81 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 split_view(_View __base, _Pattern __pattern) 82 : __base_(std::move(__base)), __pattern_(std::move((__pattern))) {} 83 84 template <forward_range _Range> 85 requires constructible_from<_View, views::all_t<_Range>> && 86 constructible_from<_Pattern, single_view<range_value_t<_Range>>> 87 _LIBCPP_HIDE_FROM_ABI constexpr _LIBCPP_EXPLICIT_SINCE_CXX23 88 split_view(_Range&& __range, range_value_t<_Range> __elem) 89 : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {} 90 91 _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& 92 requires copy_constructible<_View> 93 { 94 return __base_; 95 } 96 97 _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); } 98 99 _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() { 100 if (!__cached_begin_.__has_value()) { 101 __cached_begin_.__emplace(__find_next(ranges::begin(__base_))); 102 } 103 return {*this, ranges::begin(__base_), *__cached_begin_}; 104 } 105 106 _LIBCPP_HIDE_FROM_ABI constexpr auto end() { 107 if constexpr (common_range<_View>) { 108 return __iterator{*this, ranges::end(__base_), {}}; 109 } else { 110 return __sentinel{*this}; 111 } 112 } 113 }; 114 115 template <class _Range, class _Pattern> 116 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>; 117 118 template <forward_range _Range> 119 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>; 120 121 template <forward_range _View, forward_range _Pattern> 122 requires view<_View> && view<_Pattern> && 123 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 124 struct split_view<_View, _Pattern>::__iterator { 125 private: 126 split_view* __parent_ = nullptr; 127 _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_ = iterator_t<_View>(); 128 _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>(); 129 bool __trailing_empty_ = false; 130 131 friend struct __sentinel; 132 133 public: 134 using iterator_concept = forward_iterator_tag; 135 using iterator_category = input_iterator_tag; 136 using value_type = subrange<iterator_t<_View>>; 137 using difference_type = range_difference_t<_View>; 138 139 _LIBCPP_HIDE_FROM_ABI __iterator() = default; 140 141 _LIBCPP_HIDE_FROM_ABI constexpr __iterator( 142 split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next) 143 : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {} 144 145 _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; } 146 147 _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; } 148 149 _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() { 150 __cur_ = __next_.begin(); 151 if (__cur_ != ranges::end(__parent_->__base_)) { 152 __cur_ = __next_.end(); 153 if (__cur_ == ranges::end(__parent_->__base_)) { 154 __trailing_empty_ = true; 155 __next_ = {__cur_, __cur_}; 156 } else { 157 __next_ = __parent_->__find_next(__cur_); 158 } 159 } else { 160 __trailing_empty_ = false; 161 } 162 return *this; 163 } 164 165 _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) { 166 auto __tmp = *this; 167 ++*this; 168 return __tmp; 169 } 170 171 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) { 172 return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_; 173 } 174 }; 175 176 template <forward_range _View, forward_range _Pattern> 177 requires view<_View> && view<_Pattern> && 178 indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to> 179 struct split_view<_View, _Pattern>::__sentinel { 180 private: 181 _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>(); 182 183 _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) { 184 return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_; 185 } 186 187 public: 188 _LIBCPP_HIDE_FROM_ABI __sentinel() = default; 189 190 _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent) 191 : __end_(ranges::end(__parent.__base_)) {} 192 193 _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) { 194 return __equals(__x, __y); 195 } 196 }; 197 198 namespace views { 199 namespace __split_view { 200 struct __fn { 201 // clang-format off 202 template <class _Range, class _Pattern> 203 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI 204 constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const 205 noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))) 206 -> decltype( split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))) 207 { return split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); } 208 // clang-format on 209 210 template <class _Pattern> 211 requires constructible_from<decay_t<_Pattern>, _Pattern> 212 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const 213 noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) { 214 return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern))); 215 } 216 }; 217 } // namespace __split_view 218 219 inline namespace __cpo { 220 inline constexpr auto split = __split_view::__fn{}; 221 } // namespace __cpo 222 } // namespace views 223 224 } // namespace ranges 225 226 #endif // _LIBCPP_STD_VER >= 20 227 228 _LIBCPP_END_NAMESPACE_STD 229 230 _LIBCPP_POP_MACROS 231 232 #endif // _LIBCPP___RANGES_SPLIT_VIEW_H 233