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 public:
98  typedef _FstType fst_type;
99 
100  // iterator traits
101  typedef ::std::pair<typename fst_type::key_type, typename fst_type::value_type> value_type;
102  typedef value_type* pointer;
103  typedef value_type& reference;
104  typedef ptrdiff_t difference_type;
105  typedef ::std::bidirectional_iterator_tag iterator_category;
106 
107  explicit const_iterator_base(const fst_type* _db, bool _end) :
108  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 
120  m_db(r.m_db), m_pos(r.m_pos), m_end_pos(r.m_end_pos) {}
121 
122  const_iterator_base& operator=(const const_iterator_base& r)
123  {
124  m_db = r.m_db;
125  m_pos = r.m_pos;
126  m_end_pos = r.m_end_pos;
127  return *this;
128  }
129 
130  const_iterator_base& operator++()
131  {
132  assert(m_pos);
133  handler_type::inc(m_db, m_pos, m_end_pos);
134  return *this;
135  }
136 
137  const_iterator_base& operator--()
138  {
139  assert(m_pos);
140  handler_type::dec(m_pos, m_end_pos);
141  return *this;
142  }
143 
144  bool operator==(const const_iterator_base& r) const
145  {
146  if (m_db != r.m_db)
147  return false;
148 
149  return (m_pos == r.m_pos) && (m_end_pos == r.m_end_pos);
150  }
151 
152  bool operator!=(const const_iterator_base& r) const
153  {
154  return !operator==(r);
155  }
156 
157  const value_type& operator*()
158  {
159  return get_current_node_pair();
160  }
161 
162  const value_type* operator->()
163  {
164  return &get_current_node_pair();
165  }
166 
167 protected:
168  const typename fst_type::node* get_pos() const { return m_pos; }
169  const fst_type* get_parent() const { return m_db; }
170 
171 private:
172  const value_type& get_current_node_pair()
173  {
174  m_current_pair = value_type(m_pos->value_leaf.key, m_pos->value_leaf.value);
175  return m_current_pair;
176  }
177 
178  const fst_type* m_db;
179  const typename fst_type::node* m_pos;
180  value_type m_current_pair;
181  bool m_end_pos;
182 };
183 
184 template<typename _FstType>
186 {
187  typedef _FstType fst_type;
188  friend fst_type;
189 
190  const_segment_iterator(const typename fst_type::node* start, const typename fst_type::node* end) :
191  m_start(start), m_end(end)
192  {
193  update_node();
194  }
195 public:
196  struct value_type
197  {
198  typename fst_type::key_type start;
199  typename fst_type::key_type end;
200  typename fst_type::value_type value;
201  };
202 
203  const_segment_iterator() : m_start(nullptr), m_end(nullptr) {}
205  m_start(other.m_start), m_end(other.m_end)
206  {
207  if (m_start)
208  update_node();
209  }
210 
212 
213  bool operator== (const const_segment_iterator& other) const
214  {
215  return m_start == other.m_start && m_end == other.m_end;
216  }
217 
218  bool operator!= (const const_segment_iterator& other) const
219  {
220  return !operator==(other);
221  }
222 
223  const_segment_iterator& operator=(const const_segment_iterator& other)
224  {
225  m_start = other.m_start;
226  m_end = other.m_end;
227  if (m_start)
228  update_node();
229  return *this;
230  }
231 
232  const value_type& operator*()
233  {
234  return m_node;
235  }
236 
237  const value_type* operator->()
238  {
239  return &m_node;
240  }
241 
242  const_segment_iterator& operator++()
243  {
244  assert(m_start);
245  m_start = m_start->next.get();
246  m_end = m_start->next.get();
247  update_node();
248  return *this;
249  }
250 
251  const_segment_iterator operator++(int)
252  {
253  assert(m_start);
254  const_segment_iterator ret = *this;
255  m_start = m_start->next.get();
256  m_end = m_start->next.get();
257  update_node();
258  return ret;
259  }
260 
261  const_segment_iterator& operator--()
262  {
263  assert(m_start);
264  m_start = m_start->prev.get();
265  m_end = m_start->next.get();
266  update_node();
267  return *this;
268  }
269 
270  const_segment_iterator operator--(int)
271  {
272  assert(m_start);
273  const_segment_iterator ret = *this;
274  m_start = m_start->prev.get();
275  m_end = m_start->next.get();
276  update_node();
277  return ret;
278  }
279 
280 private:
281  void update_node()
282  {
283  if (!m_end)
284  // The iterator is at its end position. Nothing to do.
285  return;
286 
287  m_node.start = m_start->value_leaf.key;
288  m_node.end = m_end->value_leaf.key;
289  m_node.value = m_start->value_leaf.value;
290  }
291 
292 private:
293  const typename fst_type::node* m_start;
294  const typename fst_type::node* m_end;
295  value_type m_node;
296 };
297 
298 }}
299 
300 #endif
Definition: flat_segment_tree_itr.hpp:37
Definition: flat_segment_tree_itr.hpp:196
Definition: default_deleter.hpp:33
Definition: flat_segment_tree_itr.hpp:67
Definition: flat_segment_tree_itr.hpp:94
Definition: flat_segment_tree_itr.hpp:185