8#ifndef INCLUDED_SDSL_CST_ITERATORS
9#define INCLUDED_SDSL_CST_ITERATORS
37template <
class Cst, u
int32_t cache_size = 128>
58 uint32_t m_stack_size;
63 if (m_stack_cache !=
nullptr and m_stack_size < cache_size)
65 return m_stack_cache[m_stack_size];
68 return m_cst->parent(m_v);
73 if (m_stack_cache !=
nullptr and m_stack_size < cache_size)
74 m_stack_cache[m_stack_size] = m_v;
76 return m_cst->select_child(m_v, 1);
80 cst_dfs_const_forward_iterator() : m_cst(nullptr), m_visited(false), m_valid(false), m_stack_cache(nullptr)
88 m_stack_cache(nullptr)
96 else if (m_v == m_cst->root() and !m_visited and m_valid)
98 m_stack_cache = new node_type[cache_size];
111 if (m_stack_cache !=
nullptr)
114 delete[] m_stack_cache;
121 return 1 + (uint8_t)m_visited;
146 if (m_v == m_cst->root() and m_visited)
154 if (m_cst->is_leaf(m_v))
156 w = m_cst->sibling(m_v);
157 if (w == m_cst->root())
171 w = m_cst->sibling(m_v);
172 if (w == m_cst->root())
194 return (it.m_visited == m_visited)
195 and (it.m_valid == m_valid)
197 and (it.m_cst == m_cst);
203 return !(*
this == it);
224 typename Cst::node_type m_v;
237 if (m_cst ==
nullptr)
252 if (m_v == m_cst->root())
258 if (w == m_cst->root())
260 m_v = m_cst->parent(m_v);
264 m_v = m_cst->leftmost_leaf(w);
280 return (it.m_valid == m_valid)
282 and (it.m_cst == m_cst);
288 return !(*
this == it);
298template <
class Cst,
class Queue = std::queue<
typename Cst::node_type>>
330 if (m_cst !=
nullptr and !end_it)
339 return m_queue.size();
345 return m_queue.front();
361 while (m_cst->root() != child)
364 child = m_cst->sibling(child);
380 if (m_queue.size() != it.m_queue.size())
386 return it.m_valid == m_valid and it.m_cst == m_cst;
388 return (it.m_valid == m_valid)
389 and (it.m_cst == m_cst)
390 and (it.m_queue.front() == m_queue.front())
391 and (it.m_queue.back() == m_queue.back());
397 return !(*
this == it);
A forward iterator for a breath first traversal of a tree.
bool operator!=(iterator const &it) const
Inequality operator.
cst_bfs_iterator< Cst, Queue > iterator
std::forward_iterator_tag iterator_category
typename Cst::node_type value_type
const value_type const_reference
bool operator==(iterator const &it) const
Equality operator.
iterator operator++(int)
Postfix increment of the iterator.
cst_bfs_iterator(Cst const *cst, const value_type node, bool valid=true, bool end_it=false)
Constructor.
iterator & operator++()
Prefix increment of the iterator.
const_reference operator*() const
Method for dereferencing the iterator.
size_type size() const
Returns the current number of nodes in the queue.
std::ptrdiff_t difference_type
A forward iterator for a bottom up traversal of a suffix tree.
bool operator==(iterator const &it) const
Equality operator.
iterator operator++(int)
Postfix increment of the iterator.
std::ptrdiff_t difference_type
iterator & operator++()
Prefix increment of the iterator.
const value_type const_reference
cst_bottom_up_const_forward_iterator(Cst const *cst, const value_type node, bool valid=true)
Constructor.
typename Cst::node_type value_type
cst_bottom_up_const_forward_iterator< Cst > iterator
bool operator!=(iterator const &it) const
Inequality operator.
cst_bottom_up_const_forward_iterator()
Default constructor.
const_reference operator*() const
Method for dereferencing the iterator.
std::forward_iterator_tag iterator_category
An forward iterator for (compressed) suffix trees.
uint8_t visit() const
Returns how often the current node was already visited.
std::forward_iterator_tag iterator_category
std::ptrdiff_t difference_type
bool operator!=(iterator const &it) const
Inequality operator.
void operator++(int)
Postfix increment of the iterator.
cst_dfs_const_forward_iterator(Cst const *cst, const value_type node, bool visited=false, bool valid=true)
Constructor.
iterator & operator++()
Prefix increment of the iterator.
const value_type const_reference
cst_dfs_const_forward_iterator< Cst > iterator
bool operator==(iterator const &it) const
Equality operator.
~cst_dfs_const_forward_iterator()
Copy Constructor.
typename Cst::node_type value_type
const_reference operator*() const
Method for dereferencing the iterator.
Namespace for the succinct data structure library.