1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #pragma once |
10 | |
11 | #include <immer/detail/rbts/rrbtree.hpp> |
12 | #include <immer/detail/iterator_facade.hpp> |
13 | |
14 | namespace immer { |
15 | namespace detail { |
16 | namespace rbts { |
17 | |
18 | template <typename T, typename MP, bits_t B, bits_t BL> |
19 | struct rrbtree_iterator |
20 | : iterator_facade<rrbtree_iterator<T, MP, B, BL>, |
21 | std::random_access_iterator_tag, |
22 | T, |
23 | const T&, |
24 | std::ptrdiff_t, |
25 | const T*> |
26 | { |
27 | using tree_t = rrbtree<T, MP, B, BL>; |
28 | using region_t = std::tuple<const T*, size_t, size_t>; |
29 | |
30 | struct end_t {}; |
31 | |
32 | const tree_t& impl() const { return *v_; } |
33 | size_t index() const { return i_; } |
34 | |
35 | rrbtree_iterator() = default; |
36 | |
37 | rrbtree_iterator(const tree_t& v) |
38 | : v_ { &v } |
39 | , i_ { 0 } |
40 | , curr_ { nullptr, ~size_t{}, ~size_t{} } |
41 | { |
42 | } |
43 | |
44 | rrbtree_iterator(const tree_t& v, end_t) |
45 | : v_ { &v } |
46 | , i_ { v.size } |
47 | , curr_ { nullptr, ~size_t{}, ~size_t{} } |
48 | {} |
49 | |
50 | private: |
51 | friend iterator_core_access; |
52 | |
53 | const tree_t* v_; |
54 | size_t i_; |
55 | mutable region_t curr_; |
56 | |
57 | void increment() |
58 | { |
59 | using std::get; |
60 | assert(i_ < v_->size); |
61 | ++i_; |
62 | } |
63 | |
64 | void decrement() |
65 | { |
66 | using std::get; |
67 | assert(i_ > 0); |
68 | --i_; |
69 | } |
70 | |
71 | void advance(std::ptrdiff_t n) |
72 | { |
73 | using std::get; |
74 | assert(n <= 0 || i_ + static_cast<size_t>(n) <= v_->size); |
75 | assert(n >= 0 || static_cast<size_t>(-n) <= i_); |
76 | i_ += n; |
77 | } |
78 | |
79 | bool equal(const rrbtree_iterator& other) const |
80 | { |
81 | return i_ == other.i_; |
82 | } |
83 | |
84 | std::ptrdiff_t distance_to(const rrbtree_iterator& other) const |
85 | { |
86 | return other.i_ > i_ |
87 | ? static_cast<std::ptrdiff_t>(other.i_ - i_) |
88 | : - static_cast<std::ptrdiff_t>(i_ - other.i_); |
89 | } |
90 | |
91 | const T& dereference() const |
92 | { |
93 | using std::get; |
94 | if (i_ < get<1>(curr_) || i_ >= get<2>(curr_)) |
95 | curr_ = v_->region_for(i_); |
96 | return get<0>(curr_)[i_ - get<1>(curr_)]; |
97 | } |
98 | }; |
99 | |
100 | } // namespace rbts |
101 | } // namespace detail |
102 | } // namespace immer |
103 | |