Loading [MathJax]/extensions/tex2jax.js
Tatooine
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Modules Pages Concepts
iterator_facade.h
Go to the documentation of this file.
1#ifndef TATOOINE_ITERATOR_FACADE_H
2#define TATOOINE_ITERATOR_FACADE_H
3//==============================================================================
5
6#include <concepts>
7#include <iterator>
8#include <memory>
9//==============================================================================
10namespace tatooine {
11//==============================================================================
13//==============================================================================
14// infer value type
15//==============================================================================
17template <typename Iter>
19 using type = std::remove_cvref_t<decltype(*std::declval<Iter>())>;
20};
21//------------------------------------------------------------------------------
23template <typename T>
24requires requires { typename T::value_type; }
26 using type = typename T::value_type;
27};
28//------------------------------------------------------------------------------
29template <typename T>
31//==============================================================================
32template <typename Iter>
33concept implements_distance_to = requires(Iter const iter) {
34 iter.distance_to(iter);
35};
36//------------------------------------------------------------------------------
37template <typename T>
38concept implements_decrement = requires(T iter) {
39 iter.decrement();
40};
41//==============================================================================
42template <typename T>
43concept implements_dereference = requires(T iter) {
44 iter.dereference();
45};
46//==============================================================================
47template <typename T>
48concept implements_increment = requires(T iter) {
49 iter.increment();
50};
51//==============================================================================
52// infer difference type
53//==============================================================================
55template <typename>
57 using type = std::ptrdiff_t;
58};
59//------------------------------------------------------------------------------
61template <implements_distance_to Iter>
63 using type = decltype(std::declval<Iter>().distance_to(std::declval<Iter>()));
64};
65//------------------------------------------------------------------------------
66template <typename Iter>
68//==============================================================================
69// Check for .advance
70template <typename T>
71concept implements_advance = requires(T it) {
72 it.advance(infer_difference_type<T>{});
73};
74//==============================================================================
75template <typename Arg, typename Iter>
77 std::convertible_to<Arg, infer_difference_type<Iter>>;
78//==============================================================================
79// Check for .equal_to
80template <typename T>
81concept implements_equal = requires(T const it) {
82 { it.equal(it) } -> std::convertible_to<bool>;
83};
84//==============================================================================
87template <typename T>
90//==============================================================================
92template <typename T>
94//==============================================================================
96template <typename T>
97concept declares_single_pass = bool(T::single_pass_iterator);
98//------------------------------------------------------------------------------
99template <typename Iter>
100concept implements_sentinel_type = requires {
101 typename Iter::sentinel_type;
102};
103//------------------------------------------------------------------------------
104template <typename T, typename Iter>
106 std::same_as<std::decay_t<T>, typename Iter::sentinel_type>;
107//------------------------------------------------------------------------------
108//template <typename Iter, typename Sentinel>
109//concept implements_distance_to_sentinel =
110// requires(Iter const it, Sentinel const sentinel) {
111// it.distance_to(sentinel);
112//};
113//==============================================================================
114template <typename Iter>
117//==============================================================================
145//==============================================================================
146template <typename Iter>
147class iterator_facade;
148//==============================================================================
149template <typename Iter>
151 std::is_base_of_v<tatooine::iterator_facade<Iter>, Iter>;
152//==============================================================================
153template <typename Iter>
155 public:
156 using iterator_type = Iter;
158 //==============================================================================
159 private:
160 [[nodiscard]] auto as_derived() -> auto & {
161 return static_cast<iterator_type &>(*this);
162 }
163 [[nodiscard]] auto as_derived() const -> auto const & {
164 return static_cast<iterator_type const &>(*this);
165 }
166
167 public:
168 //==============================================================================
169 auto operator*() const -> decltype(auto) requires implements_dereference<Iter> {
170 return as_derived().dereference();
171 }
172 //==============================================================================
173 auto operator->() const {
174 decltype(auto) ref = **this;
175 if constexpr (std::is_reference_v<decltype(ref)>) {
176 // `ref` is a true reference, and we're safe to take its address
177 return std::addressof(ref);
178 } else {
179 // `ref` is *not* a reference. Returning its address would be the
180 // address of a local. Return that thing wrapped in an arrow_proxy.
181 return arrow_proxy<std::decay_t<decltype(ref)>>{std::move(ref)};
182 }
183 }
184 //==============================================================================
185 auto operator++() -> auto &requires implements_increment<Iter> {
186 as_derived().increment();
187 return as_derived();
188 }
189 //==============================================================================
191 auto copy = as_derived();
192 as_derived().increment();
193 return copy;
194 }
195 //==============================================================================
196 auto operator--() -> auto &
198 as_derived().decrement();
199 return as_derived();
200 }
201 //==============================================================================
202 // Postfix:
204 auto copy = *this;
205 as_derived().decrement();
206 return copy;
207 }
208 //==============================================================================
209 friend auto operator+(iterator_type left,
212 return left += off;
213 }
214 //==============================================================================
215 friend auto operator+=(iterator_type &self,
216 difference_type_arg<iterator_type> auto const offset)
217 -> auto &
219 self.advance(offset);
220 return self;
221 }
222 //==============================================================================
223 friend auto operator+(difference_type_arg<iterator_type> auto const offset,
224 iterator_type right)
226 return right += offset;
227 }
228 //==============================================================================
229 friend auto operator-(iterator_type left,
232 return left + -off;
233 }
234 //==============================================================================
235 friend auto operator-=(iterator_type &left,
237 -> auto&
239 return left = left - off;
240 }
241 //==============================================================================
242 friend auto operator-=(iterator_type &left,
244 -> auto&
246 left = left - sentinel;
247 return left;
248 }
249 //==============================================================================
251 -> decltype(auto)
253 return *(as_derived() + pos);
254 }
255 //==============================================================================
256 friend auto operator-(iterator_type const &left, iterator_type const &right)
258 return right.distance_to(left);
259 }
260 //==============================================================================
261 friend auto operator-(iterator_type const &left,
262 iter_sentinel_arg<iterator_type> auto const right)
264 // How many times must we `++right` to reach `left`?
265 return -left.distance_to(right);
266 }
267 //==============================================================================
268 friend auto operator-(iter_sentinel_arg<iterator_type> auto const right,
269 iterator_type const &left)
271 return left.distance_to(right);
272 }
273 //==============================================================================
274 friend auto operator<=>(iterator_type const &left,
275 iterator_type const &right)
277 return (left - right) <=> 0;
278 }
279 //==============================================================================
280 friend auto operator==(iterator_type const &left,
281 iterator_type const &right)
282 requires implements_equal<Iter> {
283 return left.equal(right);
284 }
285 //==============================================================================
286 friend auto operator!=(iterator_type const &left,
287 iterator_type const &right) {
288 return !left.equal(right);
289 }
290 //==============================================================================
291 friend auto operator==(
292 iterator_type const &iter,
293 iter_sentinel_arg<iterator_type> auto const /*sentinel*/) -> bool {
294 return iter.at_end();
295 }
296 //==============================================================================
297 friend auto operator!=(
298 iterator_type const &iter,
299 iter_sentinel_arg<iterator_type> auto const /*sentinel*/) -> bool {
300 return !iter.at_end();
301 }
302 //==============================================================================
303 friend auto operator==(
304 iter_sentinel_arg<iterator_type> auto const /*sentinel*/,
305 iterator_type const &iter) -> bool {
306 return iter.at_end();
307 }
308 //==============================================================================
309 friend auto operator!=(
310 iter_sentinel_arg<iterator_type> auto const /*sentinel*/,
311 iterator_type const &iter) -> bool {
312 return !iter.at_end();
313 }
314};
315//==============================================================================
316template <typename Range>
317requires requires(Range &&range) { range.begin(); }
318auto begin(Range &&range) { return range.begin(); }
319//==============================================================================
320template <typename Range>
321requires requires(Range &&range) { range.end(); }
322auto end(Range &&range) { return range.end(); }
323//==============================================================================
324template <derived_from_iterator_facade Iter>
325auto next(Iter iter) {
326 return ++iter;
327}
328//==============================================================================
329template <derived_from_iterator_facade Iter>
330auto next(Iter iter, difference_type_arg<Iter> auto off) {
331 if constexpr (implements_advance<Iter>) {
332 return iter += off;
333 } else {
334 for (decltype(off) i = 0; i < off; ++i) {
335 ++iter;
336 }
337 return iter;
338 }
339}
340//==============================================================================
341template <derived_from_iterator_facade Iter>
342requires implements_decrement<Iter>
343auto prev(Iter iter) { return --iter; }
344//==============================================================================
345template <derived_from_iterator_facade Iter>
346requires implements_decrement<Iter>
347auto prev(Iter iter, difference_type_arg<Iter> auto off) {
348 if constexpr (implements_advance<Iter>) {
349 return iter -= off;
350 } else {
351 for (decltype(off) i = 0; i < off; ++i) {
352 --iter;
353 }
354 return iter;
355 }
356}
357//==============================================================================
358template <derived_from_iterator_facade Iter>
359requires implements_advance<Iter>
360auto advance(Iter &iter) {
361 return ++iter;
362}
363//==============================================================================
364template <derived_from_iterator_facade Iter>
365requires implements_advance<Iter>
366auto advance(Iter &iter, difference_type_arg<Iter> auto off) {
367 return iter.advance(off);
368}
369//------------------------------------------------------------------------------
370template <derived_from_iterator_facade Iter>
371requires implements_distance_to<Iter>
372constexpr auto distance(Iter const& it0, Iter const& it1) {
373 return it0.distance_to(it1);
374}
375//------------------------------------------------------------------------------
376template <derived_from_iterator_facade Iter>
377requires implements_distance_to<Iter>
378constexpr auto distance(Iter const& it0, iter_sentinel_arg<Iter> auto const& it1) {
379 return it0.distance_to(it1);
380}
381//------------------------------------------------------------------------------
382template <derived_from_iterator_facade Iter>
383requires implements_distance_to<Iter>
384constexpr auto distance(iter_sentinel_arg<Iter> auto const& it0, Iter const& it1) {
385 return -it1.distance_to(it0);
386}
387//==============================================================================
388} // namespace tatooine
389//==============================================================================
390template <tatooine::derived_from_iterator_facade Iter>
391struct std::iterator_traits<Iter> {
392 static Iter const &_it;
393 using reference = decltype(*_it);
394 using pointer = decltype(_it.operator->());
397 using iterator_category = conditional_t<
399 // We meet the requirements of random-access:
400 random_access_iterator_tag,
401 // We don't:
402 conditional_t<tatooine::meets_bidirectional<Iter>,
403 // We meet requirements for bidirectional usage:
404 bidirectional_iterator_tag,
405 // We don't:
406 conditional_t<tatooine::declares_single_pass<Iter>,
407 // A single-pass iterator is an
408 // input-iterator:
409 input_iterator_tag,
410 // Otherwise we are a forward iterator:
411 forward_iterator_tag>>>;
412
413 // Just set this to the iterator_category, for now
415};
416
417#endif
C++20 implementation of an iterator facade.
Definition: iterator_facade.h:154
auto operator++(int)
Definition: iterator_facade.h:190
friend auto operator+=(iterator_type &self, difference_type_arg< iterator_type > auto const offset) -> auto &
Definition: iterator_facade.h:215
auto operator--(int)
Definition: iterator_facade.h:203
friend auto operator-(iterator_type const &left, iterator_type const &right)
Definition: iterator_facade.h:256
friend auto operator!=(iter_sentinel_arg< iterator_type > auto const, iterator_type const &iter) -> bool
Definition: iterator_facade.h:309
friend auto operator==(iterator_type const &left, iterator_type const &right)
Definition: iterator_facade.h:280
friend auto operator-(iterator_type const &left, iter_sentinel_arg< iterator_type > auto const right)
Definition: iterator_facade.h:261
friend auto operator-=(iterator_type &left, difference_type_arg< iterator_type > auto off) -> auto &
Definition: iterator_facade.h:235
auto as_derived() -> auto &
Definition: iterator_facade.h:160
friend auto operator-(iterator_type left, difference_type_arg< iterator_type > auto off)
Definition: iterator_facade.h:229
friend auto operator-(iter_sentinel_arg< iterator_type > auto const right, iterator_type const &left)
Definition: iterator_facade.h:268
friend auto operator+(iterator_type left, difference_type_arg< iterator_type > auto const off)
Definition: iterator_facade.h:209
auto as_derived() const -> auto const &
Definition: iterator_facade.h:163
friend auto operator==(iterator_type const &iter, iter_sentinel_arg< iterator_type > auto const) -> bool
Definition: iterator_facade.h:291
auto operator--() -> auto &
Definition: iterator_facade.h:196
friend auto operator-=(iterator_type &left, iter_sentinel_arg< iterator_type > auto sentinel) -> auto &
Definition: iterator_facade.h:242
auto operator->() const
Definition: iterator_facade.h:173
friend auto operator==(iter_sentinel_arg< iterator_type > auto const, iterator_type const &iter) -> bool
Definition: iterator_facade.h:303
auto operator[](difference_type_arg< iterator_type > auto pos) -> decltype(auto)
Definition: iterator_facade.h:250
friend auto operator+(difference_type_arg< iterator_type > auto const offset, iterator_type right)
Definition: iterator_facade.h:223
friend auto operator!=(iterator_type const &left, iterator_type const &right)
Definition: iterator_facade.h:286
friend auto operator!=(iterator_type const &iter, iter_sentinel_arg< iterator_type > auto const) -> bool
Definition: iterator_facade.h:297
auto operator*() const -> decltype(auto)
Definition: iterator_facade.h:169
Iter iterator_type
Definition: iterator_facade.h:156
auto operator++() -> auto &
Definition: iterator_facade.h:185
friend auto operator<=>(iterator_type const &left, iterator_type const &right)
Definition: iterator_facade.h:274
Detect if the iterator declares itself to be a single-pass iterator.
Definition: iterator_facade.h:97
Definition: iterator_facade.h:150
Definition: iterator_facade.h:76
Definition: iterator_facade.h:71
Definition: iterator_facade.h:115
Definition: iterator_facade.h:38
Definition: iterator_facade.h:43
Definition: iterator_facade.h:33
Definition: iterator_facade.h:81
Definition: iterator_facade.h:48
Definition: iterator_facade.h:100
Definition: iterator_facade.h:105
We meet bidirectional if we are random_access, OR we have .decrement()
Definition: iterator_facade.h:93
Definition: iterator_facade.h:88
Definition: concepts.h:84
Definition: algorithm.h:6
constexpr auto distance(Iter const &it0, Iter const &it1)
Definition: iterator_facade.h:372
auto begin(Range &&range)
Definition: iterator_facade.h:318
auto advance(Iter &iter)
Definition: iterator_facade.h:360
auto end(Range &&range)
Definition: iterator_facade.h:322
typename infer_difference_type_impl< Iter >::type infer_difference_type
Definition: iterator_facade.h:67
auto next(Iter iter)
Definition: iterator_facade.h:325
typename infer_value_type_impl< T >::type infer_value_type
Definition: iterator_facade.h:30
auto prev(Iter iter)
Definition: iterator_facade.h:343
conditional_t< tatooine::meets_random_access< Iter >, random_access_iterator_tag, conditional_t< tatooine::meets_bidirectional< Iter >, bidirectional_iterator_tag, conditional_t< tatooine::declares_single_pass< Iter >, input_iterator_tag, forward_iterator_tag > > > iterator_category
Definition: iterator_facade.h:411
decltype(*_it) reference
Definition: iterator_facade.h:393
tatooine::infer_difference_type< Iter > difference_type
Definition: iterator_facade.h:396
iterator_category iterator_concept
Definition: iterator_facade.h:414
tatooine::infer_value_type< Iter > value_type
Definition: iterator_facade.h:395
static Iter const & _it
Definition: iterator_facade.h:392
decltype(_it.operator->()) pointer
Definition: iterator_facade.h:394
from https://quuxplusone.github.io/blog/2019/02/06/arrow-proxy/
Definition: arrow_proxy.h:8
decltype(std::declval< Iter >().distance_to(std::declval< Iter >())) type
Definition: iterator_facade.h:63
Base case.
Definition: iterator_facade.h:56
std::ptrdiff_t type
Definition: iterator_facade.h:57
typename T::value_type type
Definition: iterator_facade.h:26
Just use the return type of derefence operator.
Definition: iterator_facade.h:18
std::remove_cvref_t< decltype(*std::declval< Iter >())> type
Definition: iterator_facade.h:19
Definition: iterator_facade.h:12