Horizon
split.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 //
6 // Use, modification and distribution is subject to the
7 // Boost Software License, Version 1.0. (See accompanying
8 // file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10 //
11 // Project home: https://github.com/ericniebler/range-v3
12 //
13 
14 #ifndef RANGES_V3_VIEW_SPLIT_HPP
15 #define RANGES_V3_VIEW_SPLIT_HPP
16 
17 #include <type_traits>
18 #include <utility>
19 
20 #include <meta/meta.hpp>
21 
22 #include <range/v3/range_fwd.hpp>
23 
30 #include <range/v3/utility/static_const.hpp>
31 #include <range/v3/view/all.hpp>
33 #include <range/v3/view/single.hpp>
34 #include <range/v3/view/view.hpp>
35 
36 #include <range/v3/detail/prologue.hpp>
37 
38 namespace ranges
39 {
42 
44  namespace detail
45  {
46  // clang-format off
47 #if defined(_MSC_VER) && !defined(__clang__) && \
48  RANGES_CXX_VER <= RANGES_CXX_STD_17
49  template<typename R, std::size_t Sz = static_cast<std::size_t>(R::size())>
50  constexpr bool _is_tiny_range_(R const *) noexcept
51  {
52  return R::size() <= 1u;
53  }
54  constexpr bool _is_tiny_range_(void const*) noexcept
55  {
56  return false;
57  }
60  template<typename R>
61  CPP_concept tiny_range =
62  sized_range<R> &&
63  detail::_is_tiny_range_(static_cast<std::add_pointer_t<R>>(nullptr));
64 #else // ^^^^ workaround / no workaround vvvv
67  template(typename R)(
68  concept (tiny_range_)(R),
69  ranges::type<
70  std::integral_constant<decltype(R::size()), R::size()>> AND
71  (R::size() <= 1)
72  );
75  template<typename R>
76  CPP_concept tiny_range =
77  sized_range<R> &&
78  CPP_concept_ref(detail::tiny_range_, std::remove_reference_t<R>);
79 #endif
80  // clang-format on
81  } // namespace detail
82 
83  template<typename V, typename Pattern>
84 #if CPP_CXX_CONCEPTS
85  requires input_range<V> && forward_range<Pattern> && view_<V> && view_<
86  Pattern> && indirectly_comparable<iterator_t<V>, iterator_t<Pattern>,
88  (forward_range<V> || detail::tiny_range<Pattern>)
89 #endif
90  struct split_view;
91 
92  namespace detail
93  {
94  struct there
95  {
96  template<typename T>
97  static decltype(auto) current_(T & t) noexcept
98  {
99  return (t.curr_);
100  }
101  };
102 
103  template<typename It>
104  struct here
105  {
106  It curr_ = It();
107  It & current_(ignore_t) noexcept
108  {
109  return curr_;
110  }
111  It const & current_(ignore_t) const noexcept
112  {
113  return curr_;
114  }
115  };
116 
117  template<bool>
118  struct here_or_there_
119  {
120  template<typename>
121  using invoke = there;
122  };
123 
124  template<>
125  struct here_or_there_<true>
126  {
127  template<typename It>
128  using invoke = here<It>;
129  };
130 
131  template<typename It>
132  using split_view_base = meta::invoke<here_or_there_<!forward_iterator<It>>, It>;
133 
134  template<typename JoinView, bool Const>
135  struct split_outer_iterator;
136 
137  template<typename JoinView, bool Const>
138  struct split_inner_iterator;
139 
140  template<typename V, typename Pattern, bool Const>
141  struct split_inner_iterator<split_view<V, Pattern>, Const>
142  {
143  private:
144  using Outer = split_outer_iterator<split_view<V, Pattern>, Const>;
145  using Base = meta::const_if_c<Const, V>;
146  using BaseIterCategory =
147  typename std::iterator_traits<iterator_t<Base>>::iterator_category;
148  Outer i_ = Outer();
149  bool incremented_ = false;
150  constexpr decltype(auto) current_() noexcept
151  {
152  return i_.current_();
153  }
154  constexpr decltype(auto) current_() const noexcept
155  {
156  return i_.current_();
157  }
158  constexpr bool done_() const
159  {
160  auto cur = current_();
161  auto last = ranges::end(i_.parent_->base_);
162  if(cur == last)
163  return true;
164  auto pcur = ranges::begin(i_.parent_->pattern_);
165  auto pend = ranges::end(i_.parent_->pattern_);
166  if(pcur == pend)
167  return incremented_;
168  do
169  {
170  if(*cur != *pcur)
171  return false;
172  if(++pcur == pend)
173  return true;
174  } while(++cur != last);
175  return false;
176  }
177 #if RANGES_CXX_IF_CONSTEXPR < RANGES_CXX_IF_CONSTEXPR_17
178  constexpr void pre_inc(std::true_type) // Forward
179  {
180  ++current_();
181  }
182  constexpr void pre_inc(std::false_type) // Input
183  {
184  if(Pattern::size() != 0)
185  ++current_();
186  }
187  constexpr split_inner_iterator post_inc(std::true_type) // Forward
188  {
189  auto tmp = *this;
190  pre_inc(std::true_type{});
191  return tmp;
192  }
193  constexpr void post_inc(std::false_type) // Input
194  {
195  pre_inc(std::false_type{});
196  }
197 #endif
198  public:
199  using iterator_concept = typename Outer::iterator_concept;
200  using iterator_category =
202  derived_from<BaseIterCategory, std::forward_iterator_tag>,
203  std::forward_iterator_tag,
204  std::input_iterator_tag>;
205  using value_type = range_value_t<Base>;
206  using difference_type = range_difference_t<Base>;
207  using reference = range_reference_t<Base>; // Not to spec
208  using pointer = iter_pointer_t<iterator_t<Base>>; // Not to spec
209 
210  split_inner_iterator() = default;
211 
212  constexpr explicit split_inner_iterator(Outer i)
213  : i_(std::move(i))
214  {}
215 
216  constexpr decltype(auto) operator*() const
217  {
218  return *current_();
219  }
220 
221  constexpr split_inner_iterator & operator++()
222  {
223  incremented_ = true;
224 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
225  if constexpr(!forward_range<Base>)
226  if constexpr(Pattern::size() == 0)
227  return *this;
228  ++current_();
229 #else
230  pre_inc(meta::bool_<forward_range<Base>>{});
231 #endif
232  return *this;
233  }
234 
235  constexpr decltype(auto) operator++(int)
236  {
237 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
238  if constexpr(forward_range<V>)
239  {
240  auto tmp = *this;
241  ++*this;
242  return tmp;
243  }
244  else
245  ++*this;
246 #else
247  return post_inc(meta::bool_<forward_range<V>>{});
248 #endif
249  }
250 
252  friend constexpr auto operator==(split_inner_iterator const & x,
253  split_inner_iterator const & y)
254  -> CPP_broken_friend_ret(bool)(
255  requires forward_range<Base>)
256  {
257  return x.i_.curr_ == y.i_.curr_;
258  }
260  friend constexpr auto operator!=(split_inner_iterator const & x,
261  split_inner_iterator const & y)
262  -> CPP_broken_friend_ret(bool)(
263  requires forward_range<Base>)
264  {
265  return x.i_.curr_ != y.i_.curr_;
266  }
267 #ifdef RANGES_WORKAROUND_MSVC_756601
268  template<typename = void>
269 #endif // RANGES_WORKAROUND_MSVC_756601
270  friend constexpr bool operator==(split_inner_iterator const & x,
271  default_sentinel_t)
272  {
273  return x.done_();
274  }
275 #ifdef RANGES_WORKAROUND_MSVC_756601
276  template<typename = void>
277 #endif // RANGES_WORKAROUND_MSVC_756601
278  friend constexpr bool operator==(default_sentinel_t,
279  split_inner_iterator const & x)
280  {
281  return x.done_();
282  }
283 #ifdef RANGES_WORKAROUND_MSVC_756601
284  template<typename = void>
285 #endif // RANGES_WORKAROUND_MSVC_756601
286  friend constexpr bool operator!=(split_inner_iterator const & x,
287  default_sentinel_t)
288  {
289  return !x.done_();
290  }
291 #ifdef RANGES_WORKAROUND_MSVC_756601
292  template<typename = void>
293 #endif // RANGES_WORKAROUND_MSVC_756601
294  friend constexpr bool operator!=(default_sentinel_t,
295  split_inner_iterator const & x)
296  {
297  return !x.done_();
298  }
299 #ifdef RANGES_WORKAROUND_MSVC_756601
300  template<typename = void>
301 #endif // RANGES_WORKAROUND_MSVC_756601
302  friend constexpr decltype(auto) iter_move(
303  split_inner_iterator const &
304  i) noexcept(noexcept(ranges::iter_move(i.current_())))
305  {
306  return ranges::iter_move(i.current_());
307  }
309  friend constexpr auto iter_swap(
310  split_inner_iterator const & x,
311  split_inner_iterator const &
312  y) noexcept(noexcept(ranges::iter_swap(x.current_(), y.current_())))
313  -> CPP_broken_friend_ret(void)(
314  requires indirectly_swappable<iterator_t<Base>>)
315  {
316  ranges::iter_swap(x.current_(), y.current_());
317  }
318  };
319 
320  template<typename It>
321  using split_outer_iterator_base =
323 
324  template<typename JoinView, bool Const>
325  struct split_outer_iterator;
326 
327  template<typename V, typename Pattern, bool Const>
328  struct split_outer_iterator<split_view<V, Pattern>, Const>
329  : split_outer_iterator_base<iterator_t<meta::const_if_c<Const, V>>>
330  {
331  private:
332  friend struct split_inner_iterator<split_view<V, Pattern>, Const>;
333  using Parent = meta::const_if_c<Const, split_view<V, Pattern>>;
334  using Base = meta::const_if_c<Const, V>;
335  using Current = split_outer_iterator_base<iterator_t<Base>>;
336 
337  Parent * parent_ = nullptr;
338  constexpr decltype(auto) current_() noexcept
339  {
340  return parent_->current_(*this);
341  }
342  constexpr decltype(auto) current_() const noexcept
343  {
344  return parent_->current_(*this);
345  }
346  constexpr decltype(auto) base_() const noexcept
347  {
348  return (parent_->base_);
349  }
350 #if RANGES_CXX_IF_CONSTEXPR < RANGES_CXX_IF_CONSTEXPR_17
351  constexpr split_outer_iterator post_inc(std::true_type) // Forward
352  {
353  auto tmp = *this;
354  ++*this;
355  return tmp;
356  }
357  constexpr void post_inc(std::false_type) // Input
358  {
359  ++*this;
360  }
361 #endif
362 
363  public:
364  using iterator_concept =
365  meta::conditional_t<forward_range<Base>, std::forward_iterator_tag,
366  std::input_iterator_tag>;
367  using iterator_category = std::input_iterator_tag;
368  struct value_type : view_interface<value_type>
369  {
370  private:
371  split_outer_iterator i_ = split_outer_iterator();
372 
373  public:
374  value_type() = default;
375  constexpr explicit value_type(split_outer_iterator i)
376  : i_(std::move(i))
377  {}
378  constexpr split_inner_iterator<split_view<V, Pattern>, Const> begin()
379  const
380  {
381  return split_inner_iterator<split_view<V, Pattern>, Const>(i_);
382  }
383  constexpr default_sentinel_t end() const
384  {
385  return default_sentinel;
386  }
387  };
388  using difference_type = range_difference_t<Base>;
389  using reference = value_type; // Not to spec
390  using pointer = value_type *; // Not to spec
391 
392  split_outer_iterator() = default;
393 
394  CPP_member
395  constexpr explicit CPP_ctor(split_outer_iterator)(Parent * parent)(
396  requires (!forward_range<Base>))
397  : parent_(parent)
398  {}
399 
400  CPP_member
401  constexpr CPP_ctor(split_outer_iterator)(Parent * parent,
402  iterator_t<Base> current)(
403  requires forward_range<Base>)
404  : Current{std::move(current)}
405  , parent_(parent)
406  {}
407 
408  template(bool Other)(
409  requires Const AND CPP_NOT(Other) AND
410  convertible_to<iterator_t<V>, iterator_t<Base>>)
411  constexpr split_outer_iterator(
412  split_outer_iterator<split_view<V, Pattern>, Other> i)
413  : Current{std::move(i.curr_)}
414  , parent_(i.parent_)
415  {}
416 
417  constexpr value_type operator*() const
418  {
419  return value_type{*this};
420  }
421 
422  constexpr split_outer_iterator & operator++()
423  {
424  auto & current = current_();
425  const auto last = ranges::end(base_());
426  if(current == last)
427  return *this;
428  auto const pbegin = ranges::begin(parent_->pattern_);
429  auto const pend = ranges::end(parent_->pattern_);
430  if(pbegin == pend)
431  ++current;
432  else
433  do
434  {
435  const auto ret = ranges::mismatch(current, last, pbegin, pend);
436  if(ret.in2 == pend)
437  {
438  current = ret.in1; // The pattern matched; skip it
439  break;
440  }
441  } while(++current != last);
442  return *this;
443  }
444 
445  constexpr decltype(auto) operator++(int)
446  {
447 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
448  if constexpr(forward_range<Base>)
449  {
450  auto tmp = *this;
451  ++*this;
452  return tmp;
453  }
454  else
455  ++*this;
456 #else
457  return post_inc(meta::bool_<forward_range<Base>>{});
458 #endif
459  }
460 
462  friend constexpr auto operator==(split_outer_iterator const & x,
463  split_outer_iterator const & y)
464  -> CPP_broken_friend_ret(bool)(
465  requires forward_range<Base>)
466  {
467  return x.curr_ == y.curr_;
468  }
470  friend constexpr auto operator!=(split_outer_iterator const & x,
471  split_outer_iterator const & y)
472  -> CPP_broken_friend_ret(bool)(
473  requires forward_range<Base>)
474  {
475  return x.curr_ != y.curr_;
476  }
477 #ifdef RANGES_WORKAROUND_MSVC_756601
478  template<typename = void>
479 #endif // RANGES_WORKAROUND_MSVC_756601
480  friend constexpr bool operator==(split_outer_iterator const & x,
481  default_sentinel_t)
482  {
483  return x.current_() == ranges::end(x.base_());
484  }
485 #ifdef RANGES_WORKAROUND_MSVC_756601
486  template<typename = void>
487 #endif // RANGES_WORKAROUND_MSVC_756601
488  friend constexpr bool operator==(default_sentinel_t,
489  split_outer_iterator const & x)
490  {
491  return x.current_() == ranges::end(x.base_());
492  }
493 #ifdef RANGES_WORKAROUND_MSVC_756601
494  template<typename = void>
495 #endif // RANGES_WORKAROUND_MSVC_756601
496  friend constexpr bool operator!=(split_outer_iterator const & x,
497  default_sentinel_t)
498  {
499  return x.current_() != ranges::end(x.base_());
500  }
501 #ifdef RANGES_WORKAROUND_MSVC_756601
502  template<typename = void>
503 #endif // RANGES_WORKAROUND_MSVC_756601
504  friend constexpr bool operator!=(default_sentinel_t,
505  split_outer_iterator const & x)
506  {
507  return x.current_() != ranges::end(x.base_());
508  }
509  };
510  } // namespace detail
512 
513  template<typename V, typename Pattern>
514 #if CPP_CXX_CONCEPTS
515  requires input_range<V> && forward_range<Pattern> && view_<V> && view_<
516  Pattern> && indirectly_comparable<iterator_t<V>, iterator_t<Pattern>,
517  ranges::equal_to> &&
518  (forward_range<V> || detail::tiny_range<Pattern>)
519 #endif
520  struct RANGES_EMPTY_BASES split_view
521  : view_interface<split_view<V, Pattern>, is_finite<V>::value ? finite : unknown>
522  , private detail::split_view_base<iterator_t<V>>
523  {
524  private:
525  template<typename, bool>
526  friend struct detail::split_outer_iterator;
527  template<typename, bool>
528  friend struct detail::split_inner_iterator;
529 
530  V base_ = V();
531  Pattern pattern_ = Pattern();
532  template<bool Const>
533  using outer_iterator = detail::split_outer_iterator<split_view, Const>;
534 
535 #if RANGES_CXX_IF_CONSTEXPR < RANGES_CXX_IF_CONSTEXPR_17
536  outer_iterator<simple_view<V>()> begin_(std::true_type)
537  {
538  return outer_iterator<simple_view<V>()>{this, ranges::begin(base_)};
539  }
540  outer_iterator<false> begin_(std::false_type)
541  {
542  this->curr_ = ranges::begin(base_);
543  return outer_iterator<false>{this};
544  }
545 
546  outer_iterator<simple_view<V>()> end_(std::true_type) const
547  {
548  return outer_iterator<true>{this, ranges::end(base_)};
549  }
550  default_sentinel_t end_(std::false_type) const
551  {
552  return default_sentinel;
553  }
554 #endif
555 
556  public:
557  split_view() = default;
558 
559  constexpr split_view(V base, Pattern pattern)
560  : base_((V &&) base)
561  , pattern_((Pattern &&) pattern)
562  {}
563 
564  CPP_member
565  constexpr CPP_ctor(split_view)(V base, range_value_t<V> e)(
566  requires constructible_from<Pattern, range_value_t<V>>)
567  : base_(std::move(base))
568  , pattern_(e)
569  {}
570 
571  constexpr V base() const
572  {
573  return base_;
574  }
575 
576  constexpr outer_iterator<forward_range<V> && simple_view<V>()> begin()
577  {
578 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
579  if constexpr(forward_range<V>)
580  return outer_iterator<simple_view<V>()>{this, ranges::begin(base_)};
581  else
582  {
583  this->curr_ = ranges::begin(base_);
584  return outer_iterator<false>{this};
585  }
586 #else
587  return begin_(meta::bool_<forward_range<V>>{});
588 #endif
589  }
590  CPP_member
591  constexpr auto begin() const //
592  -> CPP_ret(outer_iterator<true>)(
593  requires forward_range<V> && forward_range<const V>)
594  {
595  return {this, ranges::begin(base_)};
596  }
597  CPP_member
598  constexpr auto end() //
599  -> CPP_ret(outer_iterator<simple_view<V>()>)(
600  requires forward_range<V> && common_range<V>)
601  {
602  return outer_iterator<simple_view<V>()>{this, ranges::end(base_)};
603  }
604  constexpr auto end() const
605  {
606 #if RANGES_CXX_IF_CONSTEXPR >= RANGES_CXX_IF_CONSTEXPR_17
607  if constexpr(forward_range<V> && forward_range<const V> &&
608  common_range<const V>)
609  return outer_iterator<true>{this, ranges::end(base_)};
610  else
611  return default_sentinel;
612 #else
613  return end_(meta::bool_ < forward_range<V> && forward_range<const V> &&
614  common_range<const V> > {});
615 #endif
616  }
617  };
618 
619 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
620  template(typename R, typename P)(
621  requires input_range<R> AND forward_range<P> AND viewable_range<R> AND
622  viewable_range<P> AND
624  (forward_range<R> || detail::tiny_range<P>)) //
625  split_view(R &&, P &&)
626  ->split_view<views::all_t<R>, views::all_t<P>>;
627 
628  template(typename R)(
629  requires input_range<R>)
630  split_view(R &&, range_value_t<R>)
631  ->split_view<views::all_t<R>, single_view<range_value_t<R>>>;
632 #endif
633 
634  namespace views
635  {
637  {
638  template(typename Rng)(
639  requires viewable_range<Rng> AND input_range<Rng> AND
641  range_value_t<Rng> const *,
644  operator()(Rng && rng, range_value_t<Rng> val) const
645  {
646  return {all(static_cast<Rng &&>(rng)), single(std::move(val))};
647  }
648 
649  template(typename Rng, typename Pattern)(
650  requires viewable_range<Rng> AND input_range<Rng> AND
651  viewable_range<Pattern> AND forward_range<Pattern> AND
655  ranges::equal_to> AND
656  (forward_range<Rng> || detail::tiny_range<Pattern>)) //
657  constexpr split_view<all_t<Rng>, all_t<Pattern>> //
658  operator()(Rng && rng, Pattern && pattern) const
659  {
660  return {all((Rng &&) rng), all((Pattern &&) pattern)};
661  }
662  };
663 
665  {
666  using split_base_fn::operator();
667 
668  template<typename T>
669  constexpr auto operator()(T t) const
670  {
671  return make_view_closure(bind_back(split_base_fn{}, std::move(t)));
672  }
673  };
674 
678  } // namespace views
679 
680  namespace cpp20
681  {
682  namespace views
683  {
684  using ranges::views::split;
685  }
686  template(typename Rng, typename Pattern)(
687  requires input_range<Rng> AND forward_range<Pattern> AND view_<Rng> AND
688  view_<Pattern> AND
690  iterator_t<Rng>,
691  iterator_t<Pattern>,
692  ranges::equal_to> AND
693  (forward_range<Rng> || ranges::detail::tiny_range<Pattern>)) //
694  using split_view =
696  } // namespace cpp20
697 
699 } // namespace ranges
700 
701 #include <range/v3/detail/epilogue.hpp>
702 
703 #include <range/v3/detail/satisfy_boost_range.hpp>
704 RANGES_SATISFY_BOOST_RANGE(::ranges::split_view)
705 
706 #endif
#define CPP_broken_friend_member
INTERNAL ONLY.
Definition: concepts.hpp:447
CPP_concept indirectly_comparable
\concept indirectly_comparable
Definition: concepts.hpp:832
CPP_concept view_
\concept view_
Definition: concepts.hpp:252
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition: meta.hpp:168
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
typename detail::_cond< If >::template invoke< Then, Else > conditional_t
Select one type or another depending on a compile-time Boolean.
Definition: meta.hpp:1148
Tiny meta-programming library.
Point operator*(double s, const Point &a)
Multiply point by scalar.
Definition: shapes.h:250
Definition: default_sentinel.hpp:26
Definition: comparisons.hpp:28
Definition: single.hpp:41
Definition: split.hpp:523
Definition: interface.hpp:129
Definition: split.hpp:637
Definition: split.hpp:665