mdds
flat_segment_tree_itr.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2010-2017 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 {
32
36template<typename _FstType>
38{
39 typedef _FstType fst_type;
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 typedef _FstType fst_type;
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 const fst_type* get_parent() const
174 {
175 return m_db;
176 }
177
178private:
179 const value_type& get_current_node_pair()
180 {
181 m_current_pair = value_type(m_pos->value_leaf.key, m_pos->value_leaf.value);
182 return m_current_pair;
183 }
184
185 const fst_type* m_db;
186 const typename fst_type::node* m_pos;
187 value_type m_current_pair;
188 bool m_end_pos;
189};
190
191template<typename _FstType>
193{
194 typedef _FstType fst_type;
195 friend fst_type;
196
197 const_segment_iterator(const typename fst_type::node* start, const typename fst_type::node* end)
198 : m_start(start), m_end(end)
199 {
200 update_node();
201 }
202
203public:
205 {
206 typename fst_type::key_type start;
207 typename fst_type::key_type end;
208 typename fst_type::value_type value;
209
210 value_type() : start(), end(), value()
211 {}
212 };
213
214 const_segment_iterator() : m_start(nullptr), m_end(nullptr)
215 {}
216 const_segment_iterator(const const_segment_iterator& other) : m_start(other.m_start), m_end(other.m_end)
217 {
218 if (m_start)
219 update_node();
220 }
221 const_segment_iterator(const_segment_iterator&& other)
222 : m_start(std::move(other.m_start)), m_end(std::move(other.m_end))
223 {
224 if (m_start)
225 update_node();
226 }
227
228 ~const_segment_iterator()
229 {}
230
231 bool operator==(const const_segment_iterator& other) const
232 {
233 return m_start == other.m_start && m_end == other.m_end;
234 }
235
236 bool operator!=(const const_segment_iterator& other) const
237 {
238 return !operator==(other);
239 }
240
241 const_segment_iterator& operator=(const const_segment_iterator& other)
242 {
243 m_start = other.m_start;
244 m_end = other.m_end;
245 if (m_start)
246 update_node();
247 return *this;
248 }
249
250 const_segment_iterator& operator=(const_segment_iterator&& other)
251 {
252 m_start = std::move(other.m_start);
253 m_end = std::move(other.m_end);
254 if (m_start)
255 update_node();
256 return *this;
257 }
258
259 const value_type& operator*()
260 {
261 return m_node;
262 }
263
264 const value_type* operator->()
265 {
266 return &m_node;
267 }
268
269 const_segment_iterator& operator++()
270 {
271 assert(m_start);
272 m_start = m_start->next.get();
273 m_end = m_start->next.get();
274 update_node();
275 return *this;
276 }
277
278 const_segment_iterator operator++(int)
279 {
280 assert(m_start);
281 const_segment_iterator ret = *this;
282 m_start = m_start->next.get();
283 m_end = m_start->next.get();
284 update_node();
285 return ret;
286 }
287
288 const_segment_iterator& operator--()
289 {
290 assert(m_start);
291 m_start = m_start->prev.get();
292 m_end = m_start->next.get();
293 update_node();
294 return *this;
295 }
296
297 const_segment_iterator operator--(int)
298 {
299 assert(m_start);
300 const_segment_iterator ret = *this;
301 m_start = m_start->prev.get();
302 m_end = m_start->next.get();
303 update_node();
304 return ret;
305 }
306
307private:
308 void update_node()
309 {
310 if (!m_end)
311 // The iterator is at its end position. Nothing to do.
312 return;
313
314 m_node.start = m_start->value_leaf.key;
315 m_node.end = m_end->value_leaf.key;
316 m_node.value = m_start->value_leaf.value;
317 }
318
319private:
320 const typename fst_type::node* m_start;
321 const typename fst_type::node* m_end;
322 value_type m_node;
323};
324
325}} // namespace mdds::__fst
326
327#endif
Definition: flat_segment_tree_itr.hpp:95
Definition: flat_segment_tree_itr.hpp:193
Definition: flat_segment_tree_itr.hpp:205
Definition: flat_segment_tree_itr.hpp:38
Definition: flat_segment_tree_itr.hpp:68