mdds
Loading...
Searching...
No Matches
flat_segment_tree_itr.hpp
1// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include "./ref_pair.hpp"
8#include <type_traits>
9
10namespace mdds { namespace fst { namespace detail {
11
15template<typename FstType>
17{
18 using fst_type = FstType;
19
20 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
21 {
22 return _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get();
23 }
24
25 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
26 {
27 if (p == _db->m_right_leaf.get())
28 end = true;
29 else
30 p = p->next.get();
31 }
32
33 static void dec(const typename fst_type::node*& p, bool& end)
34 {
35 if (end)
36 end = false;
37 else
38 p = p->prev.get();
39 }
40};
41
45template<typename FstType>
47{
48 using fst_type = FstType;
49
50 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
51 {
52 return _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get();
53 }
54
55 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
56 {
57 if (p == _db->m_left_leaf.get())
58 end = true;
59 else
60 p = p->prev.get();
61 }
62
63 static void dec(const typename fst_type::node*& p, bool& end)
64 {
65 if (end)
66 end = false;
67 else
68 p = p->next.get();
69 }
70};
71
72template<typename FstType, typename Hdl>
73class const_iterator_base
74{
75 typedef Hdl handler_type;
76
77public:
78 typedef FstType fst_type;
79
80 // iterator traits
81 using value_type =
82 mdds::ref_pair<std::add_const_t<typename fst_type::key_type>, std::add_const_t<typename fst_type::value_type>>;
83 using pointer = value_type*;
84 using reference = value_type&;
85 using difference_type = ptrdiff_t;
86 using iterator_category = ::std::bidirectional_iterator_tag;
87
88 explicit const_iterator_base(const fst_type* _db, bool _end) : m_db(_db), m_end_pos(_end)
89 {
90 if (!_db)
91 return;
92
93 m_pos = handler_type::init_pos(_db, _end);
94 }
95
96 explicit const_iterator_base(const fst_type* _db, const typename fst_type::node* pos) : m_db(_db), m_pos(pos)
97 {}
98
99 const_iterator_base(const const_iterator_base& r) : m_db(r.m_db), m_pos(r.m_pos), m_end_pos(r.m_end_pos)
100 {}
101
102 const_iterator_base& operator=(const const_iterator_base& r)
103 {
104 m_db = r.m_db;
105 m_pos = r.m_pos;
106 m_end_pos = r.m_end_pos;
107 return *this;
108 }
109
110 const_iterator_base& operator++()
111 {
112 assert(m_pos);
113 handler_type::inc(m_db, m_pos, m_end_pos);
114 return *this;
115 }
116
117 const_iterator_base& operator--()
118 {
119 assert(m_pos);
120 handler_type::dec(m_pos, m_end_pos);
121 return *this;
122 }
123
124 bool operator==(const const_iterator_base& r) const
125 {
126 if (m_db != r.m_db)
127 return false;
128
129 return (m_pos == r.m_pos) && (m_end_pos == r.m_end_pos);
130 }
131
132 value_type operator*()
133 {
134 return value_type(m_pos->key, m_pos->value_leaf.value);
135 }
136
137 value_type operator->()
138 {
139 return value_type(m_pos->key, m_pos->value_leaf.value);
140 }
141
142protected:
143 const typename fst_type::node* get_pos() const
144 {
145 return m_pos;
146 }
147
148 const fst_type* get_parent() const
149 {
150 return m_db;
151 }
152
153 bool is_end_pos() const
154 {
155 return m_end_pos;
156 }
157
158private:
159 const fst_type* m_db = nullptr;
160 const typename fst_type::node* m_pos = nullptr;
161 bool m_end_pos = false;
162};
163
164template<typename FstType>
165class const_segment_iterator
166{
167 typedef FstType fst_type;
168 friend fst_type;
169
170 const_segment_iterator(const typename fst_type::node* start, const typename fst_type::node* end)
171 : m_start(start), m_end(end)
172 {
173 update_node();
174 }
175
176public:
177 struct value_type
178 {
179 typename fst_type::key_type start;
180 typename fst_type::key_type end;
181 typename fst_type::value_type value;
182
183 value_type() : start(), end(), value()
184 {}
185
186 value_type(
187 typename fst_type::key_type _start, typename fst_type::key_type _end, typename fst_type::value_type _value)
188 : start(std::move(_start)), end(std::move(_end)), value(std::move(_value))
189 {}
190
191 bool operator==(const value_type& other) const
192 {
193 return start == other.start && end == other.end && value == other.value;
194 }
195 };
196
197 const_segment_iterator() : m_start(nullptr), m_end(nullptr)
198 {}
199 const_segment_iterator(const const_segment_iterator& other) : m_start(other.m_start), m_end(other.m_end)
200 {
201 if (m_start)
202 update_node();
203 }
204 const_segment_iterator(const_segment_iterator&& other)
205 : m_start(std::move(other.m_start)), m_end(std::move(other.m_end))
206 {
207 if (m_start)
208 update_node();
209 }
210
211 ~const_segment_iterator()
212 {}
213
214 bool operator==(const const_segment_iterator& other) const
215 {
216 return m_start == other.m_start && m_end == other.m_end;
217 }
218
219 const_segment_iterator& operator=(const const_segment_iterator& other)
220 {
221 m_start = other.m_start;
222 m_end = other.m_end;
223 if (m_start)
224 update_node();
225 return *this;
226 }
227
228 const_segment_iterator& operator=(const_segment_iterator&& other)
229 {
230 m_start = std::move(other.m_start);
231 m_end = std::move(other.m_end);
232 if (m_start)
233 update_node();
234 return *this;
235 }
236
237 const value_type& operator*()
238 {
239 return m_node;
240 }
241
242 const value_type* operator->()
243 {
244 return &m_node;
245 }
246
247 const_segment_iterator& operator++()
248 {
249 assert(m_start);
250 m_start = m_start->next.get();
251 m_end = m_start->next.get();
252 update_node();
253 return *this;
254 }
255
256 const_segment_iterator operator++(int)
257 {
258 assert(m_start);
259 const_segment_iterator ret = *this;
260 m_start = m_start->next.get();
261 m_end = m_start->next.get();
262 update_node();
263 return ret;
264 }
265
266 const_segment_iterator& operator--()
267 {
268 assert(m_start);
269 m_start = m_start->prev.get();
270 m_end = m_start->next.get();
271 update_node();
272 return *this;
273 }
274
275 const_segment_iterator operator--(int)
276 {
277 assert(m_start);
278 const_segment_iterator ret = *this;
279 m_start = m_start->prev.get();
280 m_end = m_start->next.get();
281 update_node();
282 return ret;
283 }
284
285private:
286 void update_node()
287 {
288 if (!m_end)
289 // The iterator is at its end position. Nothing to do.
290 return;
291
292 m_node.start = m_start->key;
293 m_node.end = m_end->key;
294 m_node.value = m_start->value_leaf.value;
295 }
296
297private:
298 const typename fst_type::node* m_start;
299 const typename fst_type::node* m_end;
300 value_type m_node;
301};
302
303}}} // namespace mdds::fst::detail
Definition flat_segment_tree_itr.hpp:166
Definition flat_segment_tree_itr.hpp:178
Definition flat_segment_tree_itr.hpp:17
Definition flat_segment_tree_itr.hpp:47
Definition ref_pair.hpp:24