libcxx/include/__ranges/split_view.h

   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 _LIBCPP_EXPLICIT_SINCE_CXX23 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 _LIBCPP_EXPLICIT_SINCE_CXX23
  85   split_view(_Range&& __range, range_value_t<_Range> __elem)
  86       : __base_(views::all(std::forward<_Range>(__range))), __pattern_(views::single(std::move(__elem))) {}
  87
  88   _LIBCPP_HIDE_FROM_ABI constexpr _View base() const&
  89     requires copy_constructible<_View>
  90   {
  91     return __base_;
  92   }
  93
  94   _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return std::move(__base_); }
  95
  96   _LIBCPP_HIDE_FROM_ABI constexpr __iterator begin() {
  97     if (!__cached_begin_.__has_value()) {
  98       __cached_begin_.__emplace(__find_next(ranges::begin(__base_)));
  99     }
 100     return {*this, ranges::begin(__base_), *__cached_begin_};
 101   }
 102
 103   _LIBCPP_HIDE_FROM_ABI constexpr auto end() {
 104     if constexpr (common_range<_View>) {
 105       return __iterator{*this, ranges::end(__base_), {}};
 106     } else {
 107       return __sentinel{*this};
 108     }
 109   }
 110 };
 111
 112 template <class _Range, class _Pattern>
 113 split_view(_Range&&, _Pattern&&) -> split_view<views::all_t<_Range>, views::all_t<_Pattern>>;
 114
 115 template <forward_range _Range>
 116 split_view(_Range&&, range_value_t<_Range>) -> split_view<views::all_t<_Range>, single_view<range_value_t<_Range>>>;
 117
 118 template <forward_range _View, forward_range _Pattern>
 119   requires view<_View> && view<_Pattern> &&
 120            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
 121 struct split_view<_View, _Pattern>::__iterator {
 122 private:
 123   split_view* __parent_                                         = nullptr;
 124   _LIBCPP_NO_UNIQUE_ADDRESS iterator_t<_View> __cur_            = iterator_t<_View>();
 125   _LIBCPP_NO_UNIQUE_ADDRESS subrange<iterator_t<_View>> __next_ = subrange<iterator_t<_View>>();
 126   bool __trailing_empty_                                        = false;
 127
 128   friend struct __sentinel;
 129
 130 public:
 131   using iterator_concept  = forward_iterator_tag;
 132   using iterator_category = input_iterator_tag;
 133   using value_type        = subrange<iterator_t<_View>>;
 134   using difference_type   = range_difference_t<_View>;
 135
 136   _LIBCPP_HIDE_FROM_ABI __iterator() = default;
 137
 138   _LIBCPP_HIDE_FROM_ABI constexpr __iterator(
 139       split_view<_View, _Pattern>& __parent, iterator_t<_View> __current, subrange<iterator_t<_View>> __next)
 140       : __parent_(std::addressof(__parent)), __cur_(std::move(__current)), __next_(std::move(__next)) {}
 141
 142   _LIBCPP_HIDE_FROM_ABI constexpr iterator_t<_View> base() const { return __cur_; }
 143
 144   _LIBCPP_HIDE_FROM_ABI constexpr value_type operator*() const { return {__cur_, __next_.begin()}; }
 145
 146   _LIBCPP_HIDE_FROM_ABI constexpr __iterator& operator++() {
 147     __cur_ = __next_.begin();
 148     if (__cur_ != ranges::end(__parent_->__base_)) {
 149       __cur_ = __next_.end();
 150       if (__cur_ == ranges::end(__parent_->__base_)) {
 151         __trailing_empty_ = true;
 152         __next_           = {__cur_, __cur_};
 153       } else {
 154         __next_ = __parent_->__find_next(__cur_);
 155       }
 156     } else {
 157       __trailing_empty_ = false;
 158     }
 159     return *this;
 160   }
 161
 162   _LIBCPP_HIDE_FROM_ABI constexpr __iterator operator++(int) {
 163     auto __tmp = *this;
 164     ++*this;
 165     return __tmp;
 166   }
 167
 168   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __iterator& __y) {
 169     return __x.__cur_ == __y.__cur_ && __x.__trailing_empty_ == __y.__trailing_empty_;
 170   }
 171 };
 172
 173 template <forward_range _View, forward_range _Pattern>
 174   requires view<_View> && view<_Pattern> &&
 175            indirectly_comparable<iterator_t<_View>, iterator_t<_Pattern>, ranges::equal_to>
 176 struct split_view<_View, _Pattern>::__sentinel {
 177 private:
 178   _LIBCPP_NO_UNIQUE_ADDRESS sentinel_t<_View> __end_ = sentinel_t<_View>();
 179
 180   _LIBCPP_HIDE_FROM_ABI static constexpr bool __equals(const __iterator& __x, const __sentinel& __y) {
 181     return __x.__cur_ == __y.__end_ && !__x.__trailing_empty_;
 182   }
 183
 184 public:
 185   _LIBCPP_HIDE_FROM_ABI __sentinel() = default;
 186
 187   _LIBCPP_HIDE_FROM_ABI constexpr explicit __sentinel(split_view<_View, _Pattern>& __parent)
 188       : __end_(ranges::end(__parent.__base_)) {}
 189
 190   _LIBCPP_HIDE_FROM_ABI friend constexpr bool operator==(const __iterator& __x, const __sentinel& __y) {
 191     return __equals(__x, __y);
 192   }
 193 };
 194
 195 namespace views {
 196 namespace __split_view {
 197 struct __fn : __range_adaptor_closure<__fn> {
 198   // clang-format off
 199   template <class _Range, class _Pattern>
 200   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI
 201   constexpr auto operator()(_Range&& __range, _Pattern&& __pattern) const
 202     noexcept(noexcept(split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern))))
 203     -> decltype(      split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)))
 204     { return          split_view(std::forward<_Range>(__range), std::forward<_Pattern>(__pattern)); }
 205   // clang-format on
 206
 207   template <class _Pattern>
 208     requires constructible_from<decay_t<_Pattern>, _Pattern>
 209   _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Pattern&& __pattern) const
 210       noexcept(is_nothrow_constructible_v<decay_t<_Pattern>, _Pattern>) {
 211     return __range_adaptor_closure_t(std::__bind_back(*this, std::forward<_Pattern>(__pattern)));
 212   }
 213 };
 214 } // namespace __split_view
 215
 216 inline namespace __cpo {
 217 inline constexpr auto split = __split_view::__fn{};
 218 } // namespace __cpo
 219 } // namespace views
 220
 221 } // namespace ranges
 222
 223 #endif // _LIBCPP_STD_VER >= 20
 224
 225 _LIBCPP_END_NAMESPACE_STD
 226
 227 #endif // _LIBCPP___RANGES_SPLIT_VIEW_H