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