8 #ifndef INCLUDED_SDSL_CST_ITERATORS
9 #define INCLUDED_SDSL_CST_ITERATORS
36 template <
class Cst, u
int32_t cache_size = 128>
52 uint32_t m_stack_size;
57 if (m_stack_cache !=
nullptr and m_stack_size < cache_size) {
return m_stack_cache[m_stack_size]; }
59 return m_cst->parent(m_v);
64 if (m_stack_cache !=
nullptr and m_stack_size < cache_size)
65 m_stack_cache[m_stack_size] = m_v;
67 return m_cst->select_child(m_v, 1);
71 cst_dfs_const_forward_iterator()
75 , m_stack_cache(nullptr)
83 , m_stack_cache(nullptr)
87 if (m_cst ==
nullptr) { m_valid =
false; }
88 else if (m_v == m_cst->root() and !m_visited and m_valid)
90 m_stack_cache =
new node_type[cache_size];
103 if (m_stack_cache !=
nullptr)
106 delete[] m_stack_cache;
111 uint8_t
visit()
const {
return 1 + (uint8_t)m_visited; }
117 if (!m_visited) { m_visited =
true; }
127 if (!m_valid)
return *
this;
128 if (m_v == m_cst->root() and m_visited)
136 if (m_cst->is_leaf(m_v))
138 w = m_cst->sibling(m_v);
139 if (w == m_cst->root())
153 w = m_cst->sibling(m_v);
154 if (w == m_cst->root())
173 return (it.m_visited == m_visited)
174 and (it.m_valid == m_valid)
176 and (it.m_cst == m_cst);
195 typename Cst::node_type m_v;
211 if (m_cst ==
nullptr) m_valid =
false;
220 if (!m_valid)
return *
this;
221 if (m_v == m_cst->root())
227 if (w == m_cst->root())
229 m_v = m_cst->parent(m_v);
233 m_v = m_cst->leftmost_leaf(w);
249 return (it.m_valid == m_valid)
251 and (it.m_cst == m_cst);
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>
291 if (m_cst !=
nullptr and !end_it) { m_queue.push(node); }
303 if (!m_valid)
return *
this;
312 while (m_cst->root() != child)
315 child = m_cst->sibling(child);
331 if (m_queue.size() != it.m_queue.size())
337 return it.m_valid == m_valid and it.m_cst == m_cst;
339 return (it.m_valid == m_valid)
340 and (it.m_cst == m_cst)
341 and (it.m_queue.front() == m_queue.front())
342 and (it.m_queue.back() == m_queue.back());
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.
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.
Cst::node_type value_type
const value_type const_reference
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.
const value_type const_reference
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.
Cst::node_type value_type
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.