Horizon
Loading...
Searching...
No Matches
concat.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2013-2014.
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_CONCAT_HPP
15#define RANGES_V3_VIEW_CONCAT_HPP
16
17#include <tuple>
18#include <type_traits>
19#include <utility>
20
21#include <meta/meta.hpp>
22
24
32#include <range/v3/utility/static_const.hpp>
35#include <range/v3/view/all.hpp>
38
39#include <range/v3/detail/prologue.hpp>
40
41namespace ranges
42{
44 namespace detail
45 {
46 template<typename State, typename Value>
47 using concat_cardinality_ = std::integral_constant<
48 cardinality,
49 State::value == infinite || Value::value == infinite
50 ? infinite
51 : State::value == unknown || Value::value == unknown
52 ? unknown
53 : State::value == finite || Value::value == finite
54 ? finite
55 : static_cast<cardinality>(State::value + Value::value)>;
56
57 template<typename... Rngs>
58 using concat_cardinality =
60 std::integral_constant<cardinality, static_cast<cardinality>(0)>,
62 } // namespace detail
64
67 template<typename... Rngs>
69 : view_facade<concat_view<Rngs...>, detail::concat_cardinality<Rngs...>::value>
70 {
71 private:
72 friend range_access;
73 using difference_type_ = common_type_t<range_difference_t<Rngs>...>;
74 static constexpr std::size_t cranges{sizeof...(Rngs)};
75 std::tuple<Rngs...> rngs_;
76
77 template<bool IsConst>
78 struct cursor;
79
80 template<bool IsConst>
81 struct sentinel
82 {
83 private:
84 friend struct sentinel<!IsConst>;
85 friend struct cursor<IsConst>;
86 template<typename T>
87 using constify_if = meta::const_if_c<IsConst, T>;
88 using concat_view_t = constify_if<concat_view>;
89 sentinel_t<constify_if<meta::back<meta::list<Rngs...>>>> end_;
90
91 public:
92 sentinel() = default;
93 sentinel(concat_view_t * rng, end_tag)
94 : end_(end(std::get<cranges - 1>(rng->rngs_)))
95 {}
96 template(bool Other)(
97 requires IsConst AND CPP_NOT(Other)) //
98 sentinel(sentinel<Other> that)
99 : end_(std::move(that.end_))
100 {}
101 };
102
103 template<bool IsConst>
104 struct cursor
105 {
106 using difference_type = common_type_t<range_difference_t<Rngs>...>;
107
108 private:
109 friend struct cursor<!IsConst>;
110 template<typename T>
111 using constify_if = meta::const_if_c<IsConst, T>;
112 using concat_view_t = constify_if<concat_view>;
113 concat_view_t * rng_;
115
116 template<std::size_t N>
117 void satisfy(meta::size_t<N>)
118 {
119 RANGES_EXPECT(its_.index() == N);
120 if(ranges::get<N>(its_) == end(std::get<N>(rng_->rngs_)))
121 {
122 ranges::emplace<N + 1>(its_, begin(std::get<N + 1>(rng_->rngs_)));
123 this->satisfy(meta::size_t<N + 1>{});
124 }
125 }
126 void satisfy(meta::size_t<cranges - 1>)
127 {
128 RANGES_EXPECT(its_.index() == cranges - 1);
129 }
130 struct next_fun
131 {
132 cursor * pos;
133 template(typename I, std::size_t N)(
134 requires input_iterator<I>)
135 void operator()(indexed_element<I, N> it) const
136 {
137 RANGES_ASSERT(it.get() != end(std::get<N>(pos->rng_->rngs_)));
138 ++it.get();
139 pos->satisfy(meta::size_t<N>{});
140 }
141 };
142 struct prev_fun
143 {
144 cursor * pos;
145 template(typename I)(
147 void operator()(indexed_element<I, 0> it) const
148 {
149 RANGES_ASSERT(it.get() != begin(std::get<0>(pos->rng_->rngs_)));
150 --it.get();
151 }
152 template(typename I, std::size_t N)(
153 requires (N != 0) AND bidirectional_iterator<I>)
154 void operator()(indexed_element<I, N> it) const
155 {
156 if(it.get() == begin(std::get<N>(pos->rng_->rngs_)))
157 {
158 auto && rng = std::get<N - 1>(pos->rng_->rngs_);
159 ranges::emplace<N - 1>(
160 pos->its_,
161 ranges::next(ranges::begin(rng), ranges::end(rng)));
162 pos->its_.visit_i(*this);
163 }
164 else
165 --it.get();
166 }
167 };
168 struct advance_fwd_fun
169 {
170 cursor * pos;
171 difference_type n;
172 template(typename I)(
174 void operator()(indexed_element<I, cranges - 1> it) const
175 {
176 ranges::advance(it.get(), n);
177 }
178 template(typename I, std::size_t N)(
180 void operator()(indexed_element<I, N> it) const
181 {
182 auto last = ranges::end(std::get<N>(pos->rng_->rngs_));
183 // BUGBUG If distance(it, last) > n, then using bounded advance
184 // is O(n) when it need not be since the last iterator position
185 // is actually not interesting. Only the "rest" is needed, which
186 // can sometimes be O(1).
187 auto rest = ranges::advance(it.get(), n, std::move(last));
188 pos->satisfy(meta::size_t<N>{});
189 if(rest != 0)
190 pos->its_.visit_i(advance_fwd_fun{pos, rest});
191 }
192 };
193 struct advance_rev_fun
194 {
195 cursor * pos;
196 difference_type n;
197 template(typename I)(
199 void operator()(indexed_element<I, 0> it) const
200 {
201 ranges::advance(it.get(), n);
202 }
203 template(typename I, std::size_t N)(
205 void operator()(indexed_element<I, N> it) const
206 {
207 auto first = ranges::begin(std::get<N>(pos->rng_->rngs_));
208 if(it.get() == first)
209 {
210 auto && rng = std::get<N - 1>(pos->rng_->rngs_);
211 ranges::emplace<N - 1>(
212 pos->its_,
213 ranges::next(ranges::begin(rng), ranges::end(rng)));
214 pos->its_.visit_i(*this);
215 }
216 else
217 {
218 auto rest = ranges::advance(it.get(), n, std::move(first));
219 if(rest != 0)
220 pos->its_.visit_i(advance_rev_fun{pos, rest});
221 }
222 }
223 };
224 [[noreturn]] static difference_type distance_to_(meta::size_t<cranges>,
225 cursor const &,
226 cursor const &)
227 {
228 RANGES_EXPECT(false);
229 }
230 template<std::size_t N>
231 static difference_type distance_to_(meta::size_t<N>, cursor const & from,
232 cursor const & to)
233 {
234 if(from.its_.index() > N)
235 return cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
236 if(from.its_.index() == N)
237 {
238 if(to.its_.index() == N)
239 return distance(ranges::get<N>(from.its_),
240 ranges::get<N>(to.its_));
241 return distance(ranges::get<N>(from.its_),
242 end(std::get<N>(from.rng_->rngs_))) +
243 cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
244 }
245 if(from.its_.index() < N && to.its_.index() > N)
246 return distance(std::get<N>(from.rng_->rngs_)) +
247 cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
248 RANGES_EXPECT(to.its_.index() == N);
249 return distance(begin(std::get<N>(from.rng_->rngs_)),
250 ranges::get<N>(to.its_));
251 }
252
253 public:
254 // BUGBUG what about rvalue_reference and common_reference?
255 using reference = common_reference_t<range_reference_t<constify_if<Rngs>>...>;
257 cursor() = default;
258 cursor(concat_view_t * rng, begin_tag)
259 : rng_(rng)
260 , its_{emplaced_index<0>, begin(std::get<0>(rng->rngs_))}
261 {
262 this->satisfy(meta::size_t<0>{});
263 }
264 cursor(concat_view_t * rng, end_tag)
265 : rng_(rng)
266 , its_{emplaced_index<cranges - 1>, end(std::get<cranges - 1>(rng->rngs_))}
267 {}
268 template(bool Other)(
269 requires IsConst && CPP_NOT(Other)) //
270 cursor(cursor<Other> that)
271 : rng_(that.rng_)
272 , its_(std::move(that.its_))
273 {}
274 reference read() const
275 {
276 // Kind of a dumb implementation. Surely there's a better way.
277 return ranges::get<0>(unique_variant(its_.visit(
278 compose(convert_to<reference>{}, detail::dereference_fn{}))));
279 }
280 void next()
281 {
282 its_.visit_i(next_fun{this});
283 }
284 CPP_member
285 auto equal(cursor const & pos) const //
286 -> CPP_ret(bool)(
287 requires //
288 equality_comparable<variant<iterator_t<constify_if<Rngs>>...>>)
289 {
290 return its_ == pos.its_;
291 }
292 bool equal(sentinel<IsConst> const & pos) const
293 {
294 return its_.index() == cranges - 1 &&
295 ranges::get<cranges - 1>(its_) == pos.end_;
296 }
297 CPP_member
298 auto prev() //
299 -> CPP_ret(void)(
300 requires and_v<bidirectional_range<Rngs>...>)
301 {
302 its_.visit_i(prev_fun{this});
303 }
304 CPP_member
305 auto advance(difference_type n) //
306 -> CPP_ret(void)(
307 requires and_v<random_access_range<Rngs>...>)
308 {
309 if(n > 0)
310 its_.visit_i(advance_fwd_fun{this, n});
311 else if(n < 0)
312 its_.visit_i(advance_rev_fun{this, n});
313 }
314 CPP_member
315 auto distance_to(cursor const & that) const //
316 -> CPP_ret(difference_type)(
317 requires and_v<sized_sentinel_for<iterator_t<Rngs>,
318 iterator_t<Rngs>>...>)
319 {
320 if(its_.index() <= that.its_.index())
321 return cursor::distance_to_(meta::size_t<0>{}, *this, that);
322 return -cursor::distance_to_(meta::size_t<0>{}, that, *this);
323 }
324 };
325 cursor<meta::and_c<simple_view<Rngs>()...>::value> begin_cursor()
326 {
327 return {this, begin_tag{}};
328 }
330 cursor<meta::and_c<simple_view<Rngs>()...>::value>,
331 sentinel<meta::and_c<simple_view<Rngs>()...>::value>>
332 end_cursor()
333 {
334 return {this, end_tag{}};
335 }
336 CPP_member
337 auto begin_cursor() const //
338 -> CPP_ret(cursor<true>)(
339 requires and_v<range<Rngs const>...>)
340 {
341 return {this, begin_tag{}};
342 }
343 CPP_member
344 auto end_cursor() const //
345 -> CPP_ret(
347 cursor<true>, //
348 sentinel<true>>)(
349 requires and_v<range<Rngs const>...>)
350 {
351 return {this, end_tag{}};
352 }
353
354 public:
355 concat_view() = default;
356 explicit concat_view(Rngs... rngs)
357 : rngs_{std::move(rngs)...}
358 {}
359 CPP_member
360 constexpr auto size() const //
361 -> CPP_ret(std::size_t)(
362 requires (detail::concat_cardinality<Rngs...>::value >= 0))
363 {
364 return static_cast<std::size_t>(detail::concat_cardinality<Rngs...>::value);
365 }
366 CPP_auto_member
367 constexpr auto CPP_fun(size)()(const //
368 requires(detail::concat_cardinality<Rngs...>::value < 0) &&
369 and_v<sized_range<Rngs const>...>)
370 {
371 using size_type = common_type_t<range_size_t<Rngs const>...>;
372 return tuple_foldl(
373 tuple_transform(rngs_,
374 [](auto && r) -> size_type { return ranges::size(r); }),
375 size_type{0},
376 plus{});
377 }
378 CPP_auto_member
379 constexpr auto CPP_fun(size)()(
380 requires (detail::concat_cardinality<Rngs...>::value < 0) &&
381 and_v<sized_range<Rngs>...>)
382 {
383 using size_type = common_type_t<range_size_t<Rngs>...>;
384 return tuple_foldl(
385 tuple_transform(rngs_,
386 [](auto && r) -> size_type { return ranges::size(r); }),
387 size_type{0},
388 plus{});
389 }
390 };
391
392#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
393 template<typename... Rng>
394 concat_view(Rng &&...) //
396#endif
397
398 namespace views
399 {
401 {
402 template(typename... Rngs)(
403 requires and_v<(viewable_range<Rngs> && input_range<Rngs>)...>)
404 concat_view<all_t<Rngs>...> operator()(Rngs &&... rngs) const
405 {
406 return concat_view<all_t<Rngs>...>{all(static_cast<Rngs &&>(rngs))...};
407 }
408 template(typename Rng)(
410 all_t<Rng> operator()(Rng && rng) const //
411 {
412 return all(static_cast<Rng &&>(rng));
413 }
414 // MSVC doesn't like variadics in operator() for some reason
415#if defined(_MSC_VER)
416 template(typename Rng0, typename Rng1)(
419 concat_view<all_t<Rng0>, all_t<Rng1>> operator()(Rng0 && rng0, Rng1 && rng1)
420 const
421 {
422 return concat_view<all_t<Rng0>, all_t<Rng1>>{
423 all(static_cast<Rng0 &&>(rng0)),
424 all(static_cast<Rng1 &&>(rng1))};
425 }
426 template(typename Rng0, typename Rng1, typename Rng2)(
430 concat_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> //
431 operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const
432 {
433 return concat_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{
434 all(static_cast<Rng0 &&>(rng0)),
435 all(static_cast<Rng1 &&>(rng1)),
436 all(static_cast<Rng2 &&>(rng2))};
437 }
438#endif
439 };
440
443 RANGES_INLINE_VARIABLE(concat_fn, concat)
444 } // namespace views
446} // namespace ranges
447
448#include <range/v3/detail/epilogue.hpp>
449#include <range/v3/detail/satisfy_boost_range.hpp>
450RANGES_SATISFY_BOOST_RANGE(::ranges::concat_view)
451
452#endif
The bidirectional_iterator concept.
The common_range concept.
The input_iterator concept.
The input_range concept.
The random_access_iterator concept.
The viewable_range concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
std::integral_constant< std::size_t, N > size_t
An integral constant wrapper for std::size_t.
Definition meta.hpp:163
_t< detail::back_< L > > back
Return the last element in meta::list L.
Definition meta.hpp:2103
_t< detail::_if_< list< Args... > > > if_
Select one type or another depending on a compile-time Boolean.
Definition meta.hpp:1247
_t< detail::fold_< L, id< State >, Fn > > fold
Return a new meta::list constructed by doing a left fold of the list L using binary invocable Fn and ...
Definition meta.hpp:1589
Tiny meta-programming library.
Definition meta.hpp:1383
A list of types.
Definition meta.hpp:1684
Logically OR together all the Boolean parameters.
Definition meta.hpp:1432
Turn a template C into an invocable.
Definition meta.hpp:913
Definition range_fwd.hpp:488
Definition concat.hpp:70
Definition arithmetic.hpp:66
Definition range_fwd.hpp:490
Definition variant.hpp:71
Definition arithmetic.hpp:25
Definition variant.hpp:621
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition facade.hpp:66
Definition concat.hpp:401