Horizon
Loading...
Searching...
No Matches
split.hpp
Go to the documentation of this file.
1
2// 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
23
30#include <range/v3/utility/static_const.hpp>
31#include <range/v3/view/all.hpp>
35
36#include <range/v3/detail/prologue.hpp>
37
38namespace 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>,
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>)(
594 {
595 return {this, ranges::begin(base_)};
596 }
597 CPP_member
598 constexpr auto end() //
599 -> CPP_ret(outer_iterator<simple_view<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
609 return outer_iterator<true>{this, ranges::end(base_)};
610 else
611 return default_sentinel;
612#else
615#endif
616 }
617 };
618
619#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
620 template(typename R, typename P)(
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)(
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)(
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
677 RANGES_INLINE_VARIABLE(split_fn, split)
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
689 indirectly_comparable<
690 iterator_t<Rng>,
691 iterator_t<Pattern>,
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>
704RANGES_SATISFY_BOOST_RANGE(::ranges::split_view)
705
706#endif
The common_range concept.
The forward_range concept.
The indirectly_comparable concept.
The input_range concept.
The viewable_range concept.
#define CPP_broken_friend_member
INTERNAL ONLY.
Definition concepts.hpp:447
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
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
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