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 
31 namespace mdds { namespace fst { namespace detail {
32 
36 template<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 
66 template<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 
93 template<typename FstType, typename Hdl>
95 {
96  typedef Hdl handler_type;
97 
98 public:
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 
168 protected:
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 
184 private:
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 
197 template<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 
209 public:
210  struct value_type
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 
219  value_type(
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 
328 private:
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 
340 private:
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:67
Definition: flat_segment_tree_itr.hpp:210
Definition: flat_segment_tree_itr.hpp:94
Definition: flat_segment_tree_itr.hpp:37
Definition: flat_segment_tree_itr.hpp:198
Definition: flat_segment_tree.hpp:46