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/hamts/champ.hpp> |
12 | #include <immer/detail/iterator_facade.hpp> |
13 | |
14 | namespace immer { |
15 | namespace detail { |
16 | namespace hamts { |
17 | |
18 | template <typename T, typename Hash, typename Eq, typename MP, bits_t B> |
19 | struct champ_iterator |
20 | : iterator_facade<champ_iterator<T, Hash, Eq, MP, B>, |
21 | std::forward_iterator_tag, |
22 | T, |
23 | const T&, |
24 | std::ptrdiff_t, |
25 | const T*> |
26 | { |
27 | using tree_t = champ<T, Hash, Eq, MP, B>; |
28 | using node_t = typename tree_t::node_t; |
29 | |
30 | struct end_t {}; |
31 | |
32 | champ_iterator() = default; |
33 | |
34 | champ_iterator(const tree_t& v) |
35 | : depth_ { 0 } |
36 | { |
37 | if (v.root->datamap()) { |
38 | cur_ = v.root->values(); |
39 | end_ = v.root->values() + popcount(v.root->datamap()); |
40 | } else { |
41 | cur_ = end_ = nullptr; |
42 | } |
43 | path_[0] = &v.root; |
44 | ensure_valid_(); |
45 | } |
46 | |
47 | champ_iterator(const tree_t& v, end_t) |
48 | : cur_ { nullptr } |
49 | , end_ { nullptr } |
50 | , depth_ { 0 } |
51 | { |
52 | path_[0] = &v.root; |
53 | } |
54 | |
55 | champ_iterator(const champ_iterator& other) |
56 | : cur_ { other.cur_ } |
57 | , end_ { other.end_ } |
58 | , depth_ { other.depth_ } |
59 | { |
60 | std::copy(other.path_, other.path_ + depth_ + 1, path_); |
61 | } |
62 | |
63 | private: |
64 | friend iterator_core_access; |
65 | |
66 | T* cur_; |
67 | T* end_; |
68 | count_t depth_; |
69 | node_t* const* path_[max_depth<B> + 1]; |
70 | |
71 | void increment() |
72 | { |
73 | ++cur_; |
74 | ensure_valid_(); |
75 | } |
76 | |
77 | bool step_down() |
78 | { |
79 | if (depth_ < max_depth<B>) { |
80 | auto parent = *path_[depth_]; |
81 | if (parent->nodemap()) { |
82 | ++depth_; |
83 | path_[depth_] = parent->children(); |
84 | auto child = *path_[depth_]; |
85 | if (depth_ < max_depth<B>) { |
86 | if (child->datamap()) { |
87 | cur_ = child->values(); |
88 | end_ = cur_ + popcount(child->datamap()); |
89 | } |
90 | } else { |
91 | cur_ = child->collisions(); |
92 | end_ = cur_ + child->collision_count(); |
93 | } |
94 | return true; |
95 | } |
96 | } |
97 | return false; |
98 | } |
99 | |
100 | bool step_right() |
101 | { |
102 | while (depth_ > 0) { |
103 | auto parent = *path_[depth_ - 1]; |
104 | auto last = parent->children() + popcount(parent->nodemap()); |
105 | auto next = path_[depth_] + 1; |
106 | if (next < last) { |
107 | path_[depth_] = next; |
108 | auto child = *path_[depth_]; |
109 | if (depth_ < max_depth<B>) { |
110 | if (child->datamap()) { |
111 | cur_ = child->values(); |
112 | end_ = cur_ + popcount(child->datamap()); |
113 | } |
114 | } else { |
115 | cur_ = child->collisions(); |
116 | end_ = cur_ + child->collision_count(); |
117 | } |
118 | return true; |
119 | } |
120 | -- depth_; |
121 | } |
122 | return false; |
123 | } |
124 | |
125 | void ensure_valid_() |
126 | { |
127 | while (cur_ == end_) { |
128 | while (step_down()) |
129 | if (cur_ != end_) |
130 | return; |
131 | if (!step_right()) { |
132 | // end of sequence |
133 | assert(depth_ == 0); |
134 | cur_ = end_ = nullptr; |
135 | return; |
136 | } |
137 | } |
138 | } |
139 | |
140 | bool equal(const champ_iterator& other) const |
141 | { |
142 | return cur_ == other.cur_; |
143 | } |
144 | |
145 | const T& dereference() const |
146 | { |
147 | return *cur_; |
148 | } |
149 | }; |
150 | |
151 | } // namespace hamts |
152 | } // namespace detail |
153 | } // namespace immer |
154 | |