8#ifndef INCLUDED_SDSL_CST_ITERATORS
9#define INCLUDED_SDSL_CST_ITERATORS
36template <
class Cst, u
int32_t cache_size = 128>
57 uint32_t m_stack_size;
62 if (m_stack_cache !=
nullptr and m_stack_size < cache_size) {
return m_stack_cache[m_stack_size]; }
64 return m_cst->parent(m_v);
69 if (m_stack_cache !=
nullptr and m_stack_size < cache_size)
70 m_stack_cache[m_stack_size] = m_v;
72 return m_cst->select_child(m_v, 1);
76 cst_dfs_const_forward_iterator()
80 , m_stack_cache(nullptr)
88 , m_stack_cache(nullptr)
92 if (m_cst ==
nullptr) { m_valid =
false; }
93 else if (m_v == m_cst->root() and !m_visited and m_valid)
95 m_stack_cache =
new node_type[cache_size];
108 if (m_stack_cache !=
nullptr)
111 delete[] m_stack_cache;
116 uint8_t
visit()
const {
return 1 + (uint8_t)m_visited; }
122 if (!m_visited) { m_visited =
true; }
132 if (!m_valid)
return *
this;
133 if (m_v == m_cst->root() and m_visited)
141 if (m_cst->is_leaf(m_v))
143 w = m_cst->sibling(m_v);
144 if (w == m_cst->root())
158 w = m_cst->sibling(m_v);
159 if (w == m_cst->root())
178 return (it.m_visited == m_visited)
179 and (it.m_valid == m_valid)
181 and (it.m_cst == m_cst);
205 typename Cst::node_type m_v;
221 if (m_cst ==
nullptr) m_valid =
false;
230 if (!m_valid)
return *
this;
231 if (m_v == m_cst->root())
237 if (w == m_cst->root())
239 m_v = m_cst->parent(m_v);
243 m_v = m_cst->leftmost_leaf(w);
259 return (it.m_valid == m_valid)
261 and (it.m_cst == m_cst);
274template <
class Cst,
class Queue = std::queue<
typename Cst::node_type>>
306 if (m_cst !=
nullptr and !end_it) { m_queue.push(node); }
318 if (!m_valid)
return *
this;
327 while (m_cst->root() != child)
330 child = m_cst->sibling(child);
346 if (m_queue.size() != it.m_queue.size())
352 return it.m_valid == m_valid and it.m_cst == m_cst;
354 return (it.m_valid == m_valid)
355 and (it.m_cst == m_cst)
356 and (it.m_queue.front() == m_queue.front())
357 and (it.m_queue.back() == m_queue.back());
A forward iterator for a breath first traversal of a tree.
std::forward_iterator_tag iterator_category
typename 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.
std::ptrdiff_t difference_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.
std::ptrdiff_t difference_type
iterator & operator++()
Prefix increment of the iterator.
typename Cst::node_type value_type
bool operator!=(const iterator &it) const
Inequality operator.
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.
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
const value_type const_reference
std::ptrdiff_t difference_type
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.
typename Cst::node_type value_type
const_reference operator*() const
Method for dereferencing the iterator.
Namespace for the succinct data structure library.