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
14namespace immer {
15namespace detail {
16namespace hamts {
17
18template <typename T, typename Hash, typename Eq, typename MP, bits_t B>
19struct 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
63private:
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