mdds
Loading...
Searching...
No Matches
flat_segment_tree_itr.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2010-2023 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#pragma once
29
30#include "./ref_pair.hpp"
31#include <type_traits>
32
33namespace mdds { namespace fst { namespace detail {
34
38template<typename FstType>
40{
41 using fst_type = FstType;
42
43 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
44 {
45 return _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get();
46 }
47
48 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
49 {
50 if (p == _db->m_right_leaf.get())
51 end = true;
52 else
53 p = p->next.get();
54 }
55
56 static void dec(const typename fst_type::node*& p, bool& end)
57 {
58 if (end)
59 end = false;
60 else
61 p = p->prev.get();
62 }
63};
64
68template<typename FstType>
70{
71 using fst_type = FstType;
72
73 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
74 {
75 return _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get();
76 }
77
78 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
79 {
80 if (p == _db->m_left_leaf.get())
81 end = true;
82 else
83 p = p->prev.get();
84 }
85
86 static void dec(const typename fst_type::node*& p, bool& end)
87 {
88 if (end)
89 end = false;
90 else
91 p = p->next.get();
92 }
93};
94
95template<typename FstType, typename Hdl>
97{
98 typedef Hdl handler_type;
99
100public:
101 typedef FstType fst_type;
102
103 // iterator traits
105 std::add_const_t<typename fst_type::key_type>, std::add_const_t<typename fst_type::value_type>>;
106 using pointer = value_type*;
107 using reference = value_type&;
108 using difference_type = ptrdiff_t;
109 using iterator_category = ::std::bidirectional_iterator_tag;
110
111 explicit const_iterator_base(const fst_type* _db, bool _end) : m_db(_db), m_end_pos(_end)
112 {
113 if (!_db)
114 return;
115
116 m_pos = handler_type::init_pos(_db, _end);
117 }
118
119 explicit const_iterator_base(const fst_type* _db, const typename fst_type::node* pos) : m_db(_db), m_pos(pos)
120 {}
121
122 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)
123 {}
124
125 const_iterator_base& operator=(const const_iterator_base& r)
126 {
127 m_db = r.m_db;
128 m_pos = r.m_pos;
129 m_end_pos = r.m_end_pos;
130 return *this;
131 }
132
133 const_iterator_base& operator++()
134 {
135 assert(m_pos);
136 handler_type::inc(m_db, m_pos, m_end_pos);
137 return *this;
138 }
139
140 const_iterator_base& operator--()
141 {
142 assert(m_pos);
143 handler_type::dec(m_pos, m_end_pos);
144 return *this;
145 }
146
147 bool operator==(const const_iterator_base& r) const
148 {
149 if (m_db != r.m_db)
150 return false;
151
152 return (m_pos == r.m_pos) && (m_end_pos == r.m_end_pos);
153 }
154
155 bool operator!=(const const_iterator_base& r) const
156 {
157 return !operator==(r);
158 }
159
160 value_type operator*()
161 {
162 return value_type(m_pos->key, m_pos->value_leaf.value);
163 }
164
165 value_type operator->()
166 {
167 return value_type(m_pos->key, m_pos->value_leaf.value);
168 }
169
170protected:
171 const typename fst_type::node* get_pos() const
172 {
173 return m_pos;
174 }
175
176 const fst_type* get_parent() const
177 {
178 return m_db;
179 }
180
181 bool is_end_pos() const
182 {
183 return m_end_pos;
184 }
185
186private:
187 const fst_type* m_db = nullptr;
188 const typename fst_type::node* m_pos = nullptr;
189 bool m_end_pos = false;
190};
191
192template<typename FstType>
194{
195 typedef FstType fst_type;
196 friend fst_type;
197
198 const_segment_iterator(const typename fst_type::node* start, const typename fst_type::node* end)
199 : m_start(start), m_end(end)
200 {
201 update_node();
202 }
203
204public:
206 {
207 typename fst_type::key_type start;
208 typename fst_type::key_type end;
209 typename fst_type::value_type value;
210
211 value_type() : start(), end(), value()
212 {}
213
215 typename fst_type::key_type _start, typename fst_type::key_type _end, typename fst_type::value_type _value)
216 : start(std::move(_start)), end(std::move(_end)), value(std::move(_value))
217 {}
218
219 bool operator==(const value_type& other) const
220 {
221 return start == other.start && end == other.end && value == other.value;
222 }
223
224 bool operator!=(const value_type& other) const
225 {
226 return !operator==(other);
227 }
228 };
229
230 const_segment_iterator() : m_start(nullptr), m_end(nullptr)
231 {}
232 const_segment_iterator(const const_segment_iterator& other) : m_start(other.m_start), m_end(other.m_end)
233 {
234 if (m_start)
235 update_node();
236 }
237 const_segment_iterator(const_segment_iterator&& other)
238 : m_start(std::move(other.m_start)), m_end(std::move(other.m_end))
239 {
240 if (m_start)
241 update_node();
242 }
243
244 ~const_segment_iterator()
245 {}
246
247 bool operator==(const const_segment_iterator& other) const
248 {
249 return m_start == other.m_start && m_end == other.m_end;
250 }
251
252 bool operator!=(const const_segment_iterator& other) const
253 {
254 return !operator==(other);
255 }
256
257 const_segment_iterator& operator=(const const_segment_iterator& other)
258 {
259 m_start = other.m_start;
260 m_end = other.m_end;
261 if (m_start)
262 update_node();
263 return *this;
264 }
265
266 const_segment_iterator& operator=(const_segment_iterator&& other)
267 {
268 m_start = std::move(other.m_start);
269 m_end = std::move(other.m_end);
270 if (m_start)
271 update_node();
272 return *this;
273 }
274
275 const value_type& operator*()
276 {
277 return m_node;
278 }
279
280 const value_type* operator->()
281 {
282 return &m_node;
283 }
284
285 const_segment_iterator& operator++()
286 {
287 assert(m_start);
288 m_start = m_start->next.get();
289 m_end = m_start->next.get();
290 update_node();
291 return *this;
292 }
293
294 const_segment_iterator operator++(int)
295 {
296 assert(m_start);
297 const_segment_iterator ret = *this;
298 m_start = m_start->next.get();
299 m_end = m_start->next.get();
300 update_node();
301 return ret;
302 }
303
304 const_segment_iterator& operator--()
305 {
306 assert(m_start);
307 m_start = m_start->prev.get();
308 m_end = m_start->next.get();
309 update_node();
310 return *this;
311 }
312
313 const_segment_iterator operator--(int)
314 {
315 assert(m_start);
316 const_segment_iterator ret = *this;
317 m_start = m_start->prev.get();
318 m_end = m_start->next.get();
319 update_node();
320 return ret;
321 }
322
323private:
324 void update_node()
325 {
326 if (!m_end)
327 // The iterator is at its end position. Nothing to do.
328 return;
329
330 m_node.start = m_start->key;
331 m_node.end = m_end->key;
332 m_node.value = m_start->value_leaf.value;
333 }
334
335private:
336 const typename fst_type::node* m_start;
337 const typename fst_type::node* m_end;
338 value_type m_node;
339};
340
341}}} // namespace mdds::fst::detail
Definition flat_segment_tree_itr.hpp:97
Definition flat_segment_tree_itr.hpp:194
Definition ref_pair.hpp:37
Definition flat_segment_tree_itr.hpp:206
Definition flat_segment_tree_itr.hpp:40
Definition flat_segment_tree_itr.hpp:70