mdds
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#ifndef INCLUDED_MDDS_FLAT_SEGMENT_TREE_ITR_HPP
29#define INCLUDED_MDDS_FLAT_SEGMENT_TREE_ITR_HPP
30
31namespace mdds { namespace fst { namespace detail {
32
36template<typename FstType>
38{
39 using fst_type = FstType;
40
41 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
42 {
43 return _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get();
44 }
45
46 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
47 {
48 if (p == _db->m_right_leaf.get())
49 end = true;
50 else
51 p = p->next.get();
52 }
53
54 static void dec(const typename fst_type::node*& p, bool& end)
55 {
56 if (end)
57 end = false;
58 else
59 p = p->prev.get();
60 }
61};
62
66template<typename FstType>
68{
69 using fst_type = FstType;
70
71 static const typename fst_type::node* init_pos(const fst_type* _db, bool _end)
72 {
73 return _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get();
74 }
75
76 static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end)
77 {
78 if (p == _db->m_left_leaf.get())
79 end = true;
80 else
81 p = p->prev.get();
82 }
83
84 static void dec(const typename fst_type::node*& p, bool& end)
85 {
86 if (end)
87 end = false;
88 else
89 p = p->next.get();
90 }
91};
92
93template<typename FstType, typename Hdl>
95{
96 typedef Hdl handler_type;
97
98public:
99 typedef FstType fst_type;
100
101 // iterator traits
102 typedef ::std::pair<typename fst_type::key_type, typename fst_type::value_type> value_type;
103 typedef value_type* pointer;
104 typedef value_type& reference;
105 typedef ptrdiff_t difference_type;
106 typedef ::std::bidirectional_iterator_tag iterator_category;
107
108 explicit const_iterator_base(const fst_type* _db, bool _end) : m_db(_db), m_pos(nullptr), m_end_pos(_end)
109 {
110 if (!_db)
111 return;
112
113 m_pos = handler_type::init_pos(_db, _end);
114 }
115
116 explicit const_iterator_base(const fst_type* _db, const typename fst_type::node* pos)
117 : m_db(_db), m_pos(pos), m_end_pos(false)
118 {}
119
120 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)
121 {}
122
123 const_iterator_base& operator=(const const_iterator_base& r)
124 {
125 m_db = r.m_db;
126 m_pos = r.m_pos;
127 m_end_pos = r.m_end_pos;
128 return *this;
129 }
130
131 const_iterator_base& operator++()
132 {
133 assert(m_pos);
134 handler_type::inc(m_db, m_pos, m_end_pos);
135 return *this;
136 }
137
138 const_iterator_base& operator--()
139 {
140 assert(m_pos);
141 handler_type::dec(m_pos, m_end_pos);
142 return *this;
143 }
144
145 bool operator==(const const_iterator_base& r) const
146 {
147 if (m_db != r.m_db)
148 return false;
149
150 return (m_pos == r.m_pos) && (m_end_pos == r.m_end_pos);
151 }
152
153 bool operator!=(const const_iterator_base& r) const
154 {
155 return !operator==(r);
156 }
157
158 const value_type& operator*()
159 {
160 return get_current_node_pair();
161 }
162
163 const value_type* operator->()
164 {
165 return &get_current_node_pair();
166 }
167
168protected:
169 const typename fst_type::node* get_pos() const
170 {
171 return m_pos;
172 }
173
174 const fst_type* get_parent() const
175 {
176 return m_db;
177 }
178
179 bool is_end_pos() const
180 {
181 return m_end_pos;
182 }
183
184private:
185 const value_type& get_current_node_pair()
186 {
187 m_current_pair = value_type(m_pos->value_leaf.key, m_pos->value_leaf.value);
188 return m_current_pair;
189 }
190
191 const fst_type* m_db;
192 const typename fst_type::node* m_pos;
193 value_type m_current_pair;
194 bool m_end_pos;
195};
196
197template<typename FstType>
199{
200 typedef FstType fst_type;
201 friend fst_type;
202
203 const_segment_iterator(const typename fst_type::node* start, const typename fst_type::node* end)
204 : m_start(start), m_end(end)
205 {
206 update_node();
207 }
208
209public:
211 {
212 typename fst_type::key_type start;
213 typename fst_type::key_type end;
214 typename fst_type::value_type value;
215
216 value_type() : start(), end(), value()
217 {}
218
220 typename fst_type::key_type _start, typename fst_type::key_type _end, typename fst_type::value_type _value)
221 : start(std::move(_start)), end(std::move(_end)), value(std::move(_value))
222 {}
223
224 bool operator==(const value_type& other) const
225 {
226 return start == other.start && end == other.end && value == other.value;
227 }
228
229 bool operator!=(const value_type& other) const
230 {
231 return !operator==(other);
232 }
233 };
234
235 const_segment_iterator() : m_start(nullptr), m_end(nullptr)
236 {}
237 const_segment_iterator(const const_segment_iterator& other) : m_start(other.m_start), m_end(other.m_end)
238 {
239 if (m_start)
240 update_node();
241 }
242 const_segment_iterator(const_segment_iterator&& other)
243 : m_start(std::move(other.m_start)), m_end(std::move(other.m_end))
244 {
245 if (m_start)
246 update_node();
247 }
248
249 ~const_segment_iterator()
250 {}
251
252 bool operator==(const const_segment_iterator& other) const
253 {
254 return m_start == other.m_start && m_end == other.m_end;
255 }
256
257 bool operator!=(const const_segment_iterator& other) const
258 {
259 return !operator==(other);
260 }
261
262 const_segment_iterator& operator=(const const_segment_iterator& other)
263 {
264 m_start = other.m_start;
265 m_end = other.m_end;
266 if (m_start)
267 update_node();
268 return *this;
269 }
270
271 const_segment_iterator& operator=(const_segment_iterator&& other)
272 {
273 m_start = std::move(other.m_start);
274 m_end = std::move(other.m_end);
275 if (m_start)
276 update_node();
277 return *this;
278 }
279
280 const value_type& operator*()
281 {
282 return m_node;
283 }
284
285 const value_type* operator->()
286 {
287 return &m_node;
288 }
289
290 const_segment_iterator& operator++()
291 {
292 assert(m_start);
293 m_start = m_start->next.get();
294 m_end = m_start->next.get();
295 update_node();
296 return *this;
297 }
298
299 const_segment_iterator operator++(int)
300 {
301 assert(m_start);
302 const_segment_iterator ret = *this;
303 m_start = m_start->next.get();
304 m_end = m_start->next.get();
305 update_node();
306 return ret;
307 }
308
309 const_segment_iterator& operator--()
310 {
311 assert(m_start);
312 m_start = m_start->prev.get();
313 m_end = m_start->next.get();
314 update_node();
315 return *this;
316 }
317
318 const_segment_iterator operator--(int)
319 {
320 assert(m_start);
321 const_segment_iterator ret = *this;
322 m_start = m_start->prev.get();
323 m_end = m_start->next.get();
324 update_node();
325 return ret;
326 }
327
328private:
329 void update_node()
330 {
331 if (!m_end)
332 // The iterator is at its end position. Nothing to do.
333 return;
334
335 m_node.start = m_start->value_leaf.key;
336 m_node.end = m_end->value_leaf.key;
337 m_node.value = m_start->value_leaf.value;
338 }
339
340private:
341 const typename fst_type::node* m_start;
342 const typename fst_type::node* m_end;
343 value_type m_node;
344};
345
346}}} // namespace mdds::fst::detail
347
348#endif
Definition: flat_segment_tree_itr.hpp:95
Definition: flat_segment_tree_itr.hpp:199
Definition: flat_segment_tree_itr.hpp:211
Definition: flat_segment_tree_itr.hpp:38
Definition: flat_segment_tree_itr.hpp:68