SDSL  3.0.0
Succinct Data Structure Library
cst_iterators.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_CST_ITERATORS
9 #define INCLUDED_SDSL_CST_ITERATORS
10 
11 #include <cstdint>
12 #include <queue>
13 
14 namespace sdsl
15 {
16 
18 
35 // TODO: implement operator--
36 template <class Cst, uint32_t cache_size = 128>
37 class cst_dfs_const_forward_iterator : public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
38 {
39  public:
40  typedef typename Cst::node_type value_type;
41  typedef const value_type const_reference;
42  typedef typename Cst::size_type size_type;
44  typedef typename Cst::node_type node_type;
45 
46  private:
47  const Cst * m_cst;
48  node_type m_v;
49  bool m_visited;
50  bool m_valid;
51  node_type * m_stack_cache;
52  uint32_t m_stack_size;
53 
54  inline node_type parent()
55  {
56  --m_stack_size; // decrease stack size
57  if (m_stack_cache != nullptr and m_stack_size < cache_size) { return m_stack_cache[m_stack_size]; }
58  else
59  return m_cst->parent(m_v);
60  }
61 
62  inline node_type first_child()
63  {
64  if (m_stack_cache != nullptr and m_stack_size < cache_size) // push node to the stack
65  m_stack_cache[m_stack_size] = m_v;
66  m_stack_size++;
67  return m_cst->select_child(m_v, 1);
68  }
69 
71  cst_dfs_const_forward_iterator()
72  : m_cst(nullptr)
73  , m_visited(false)
74  , m_valid(false)
75  , m_stack_cache(nullptr)
76  {}
77 
78  public:
80  cst_dfs_const_forward_iterator(const Cst * cst, const value_type node, bool visited = false, bool valid = true)
81  : m_visited(visited)
82  , m_valid(valid)
83  , m_stack_cache(nullptr)
84  {
85  m_cst = cst;
86  m_v = node;
87  if (m_cst == nullptr) { m_valid = false; }
88  else if (m_v == m_cst->root() and !m_visited and m_valid)
89  { // if the iterator equal cst.begin()
90  m_stack_cache = new node_type[cache_size];
91  m_stack_size = 0;
92  // std::cerr<<"#creating stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
93  }
94  }
95 
97  // cst_dfs_const_forward_iterator(const cst_dfs_const_forward_iterator
98  //&it):m_cst(it.cst),m_v(it.m_v),m_valid(m_valid), m_stack_cache(nullptr),m_stack_size(0){
99  // }
100 
102  {
103  if (m_stack_cache != nullptr)
104  {
105  // std::cerr<<"#deleting stack "<<m_cst->lb(m_v)<<" "<<m_cst->rb(m_v)<<std::endl;
106  delete[] m_stack_cache;
107  }
108  }
109 
111  uint8_t visit() const { return 1 + (uint8_t)m_visited; }
112 
114  {
115  if (m_valid)
116  {
117  if (!m_visited) { m_visited = true; }
118  }
119  }
120 
122  const_reference operator*() const { return m_v; }
123 
126  {
127  if (!m_valid) return *this;
128  if (m_v == m_cst->root() and m_visited)
129  {
130  m_valid = false;
131  return *this;
132  }
133  value_type w;
134  if (!m_visited)
135  { // go down, if possible
136  if (m_cst->is_leaf(m_v))
137  {
138  w = m_cst->sibling(m_v); // determine sibling of leaf v
139  if (w == m_cst->root())
140  { // if there exists no right sibling of the leaf v
141  // w = m_cst->parent(m_v);
142  w = parent();
143  m_visited = true; // go up
144  }
145  }
146  else
147  { // v is not a leaf => go down the tree
148  w = first_child();
149  }
150  }
151  else
152  { //
153  w = m_cst->sibling(m_v);
154  if (w == m_cst->root())
155  { // if there exists no right sibling
156  w = parent();
157  }
158  else
159  {
160  m_visited = false;
161  }
162  }
163  m_v = w;
164  return *this;
165  }
166 
168  void operator++(int) { ++(*this); }
169 
171  bool operator==(const iterator & it) const
172  {
173  return (it.m_visited == m_visited) // visited status is equal
174  and (it.m_valid == m_valid) // valid status is equal => for end() iterator
175  and (it.m_v == m_v) // nodes are equal
176  and (it.m_cst == m_cst); // iterator belongs to the same cst
177  }
178 
180  bool operator!=(const iterator & it) const { return !(*this == it); }
181 };
182 
184 template <class Cst>
185 class cst_bottom_up_const_forward_iterator : public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
186 {
187  public:
188  typedef typename Cst::node_type value_type;
190  typedef typename Cst::size_type size_type;
192 
193  private:
194  const Cst * m_cst;
195  typename Cst::node_type m_v;
196  bool m_valid;
197 
198  public:
201  : m_cst(nullptr)
202  , m_valid(false)
203  {}
204 
206  cst_bottom_up_const_forward_iterator(const Cst * cst, const value_type node, bool valid = true)
207  : m_valid(valid)
208  {
209  m_cst = cst;
210  m_v = node;
211  if (m_cst == nullptr) m_valid = false;
212  }
213 
215  const_reference operator*() const { return m_v; }
216 
219  {
220  if (!m_valid) return *this;
221  if (m_v == m_cst->root())
222  {
223  m_valid = false;
224  return *this;
225  }
226  value_type w = m_cst->sibling(m_v);
227  if (w == m_cst->root())
228  { // if no next right sibling exist
229  m_v = m_cst->parent(m_v); // go to parent
230  }
231  else
232  { // if next right sibling exist
233  m_v = m_cst->leftmost_leaf(w); // go to leaftmost leaf in the subtree of w
234  }
235  return *this;
236  }
237 
240  {
241  iterator it = *this;
242  ++(*this);
243  return it;
244  }
245 
247  bool operator==(const iterator & it) const
248  {
249  return (it.m_valid == m_valid) // valid status is equal => for end() iterator
250  and (it.m_v == m_v) // nodes are equal
251  and (it.m_cst == m_cst); // iterator belongs to the same cst
252  }
253 
255  bool operator!=(const iterator & it) const { return !(*this == it); }
256 };
257 
259 
264 template <class Cst, class Queue = std::queue<typename Cst::node_type>>
265 class cst_bfs_iterator : public std::iterator<std::forward_iterator_tag, typename Cst::node_type>
266 {
267  public:
268  typedef typename Cst::node_type value_type;
270  typedef typename Cst::size_type size_type;
272  typedef Queue queue_type;
273 
274  private:
275  const Cst * m_cst; // Pointer to the cst.
276  queue_type m_queue; //
277  bool m_valid; // State of the iterator.
278 
279  public:
281 
287  cst_bfs_iterator(const Cst * cst, const value_type node, bool valid = true, bool end_it = false)
288  {
289  m_cst = cst;
290  m_valid = valid;
291  if (m_cst != nullptr and !end_it) { m_queue.push(node); }
292  }
293 
295  size_type size() const { return m_queue.size(); }
296 
298  const_reference operator*() const { return m_queue.front(); }
299 
302  {
303  if (!m_valid) return *this;
304  if (m_queue.empty())
305  {
306  m_valid = false;
307  return *this;
308  }
309  value_type v = m_queue.front();
310  m_queue.pop();
311  value_type child = m_cst->select_child(v, 1);
312  while (m_cst->root() != child)
313  {
314  m_queue.push(child);
315  child = m_cst->sibling(child);
316  }
317  return *this;
318  }
319 
322  {
323  iterator it = *this;
324  ++(*this);
325  return it;
326  }
327 
329  bool operator==(const iterator & it) const
330  {
331  if (m_queue.size() != it.m_queue.size())
332  { // if the queue size is different
333  return false; // the state of the to iterator are different
334  }
335  if (m_queue.empty())
336  { // if the queue is empty, we have to check if they are valid and
337  return it.m_valid == m_valid and it.m_cst == m_cst; // belong to the same cst
338  }
339  return (it.m_valid == m_valid) // valid status is equal => for end() iterator
340  and (it.m_cst == m_cst) // iterator belongs to the same cst
341  and (it.m_queue.front() == m_queue.front()) // front element and
342  and (it.m_queue.back() == m_queue.back()); // back element are the same.
343  }
344 
346  bool operator!=(const iterator & it) const { return !(*this == it); }
347 };
348 
349 } // end namespace sdsl
350 
351 #endif
A forward iterator for a breath first traversal of a tree.
Cst::node_type value_type
const value_type const_reference
iterator operator++(int)
Postfix increment of the iterator.
cst_bfs_iterator(const Cst *cst, const value_type node, bool valid=true, bool end_it=false)
Constructor.
bool operator==(const iterator &it) const
Equality operator.
iterator & operator++()
Prefix increment of the iterator.
const_reference operator*() const
Method for dereferencing the iterator.
cst_bfs_iterator< Cst, Queue > iterator
bool operator!=(const iterator &it) const
Inequality operator.
size_type size() const
Returns the current number of nodes in the queue.
Cst::size_type size_type
A forward iterator for a bottom up traversal of a suffix tree.
cst_bottom_up_const_forward_iterator(const Cst *cst, const value_type node, bool valid=true)
Constructor.
iterator operator++(int)
Postfix increment of the iterator.
iterator & operator++()
Prefix increment of the iterator.
bool operator!=(const iterator &it) const
Inequality operator.
bool operator==(const iterator &it) const
Equality operator.
cst_bottom_up_const_forward_iterator()
Default constructor.
cst_bottom_up_const_forward_iterator< Cst > iterator
const_reference operator*() const
Method for dereferencing the iterator.
An forward iterator for (compressed) suffix trees.
uint8_t visit() const
Returns how often the current node was already visited.
void operator++(int)
Postfix increment of the iterator.
iterator & operator++()
Prefix increment of the iterator.
cst_dfs_const_forward_iterator< Cst > iterator
cst_dfs_const_forward_iterator(const Cst *cst, const value_type node, bool visited=false, bool valid=true)
Constructor.
~cst_dfs_const_forward_iterator()
Copy Constructor.
bool operator==(const iterator &it) const
Equality operator.
bool operator!=(const iterator &it) const
Inequality operator.
const_reference operator*() const
Method for dereferencing the iterator.
int_vector ::size_type size_type
Namespace for the succinct data structure library.