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 
31 namespace mdds { namespace __fst {
32 
36 template<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 
66 template<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 
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  const fst_type* get_parent() const
174  {
175  return m_db;
176  }
177 
178 private:
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 
191 template<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 
203 public:
204  struct value_type
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 
307 private:
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 
319 private:
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