4#ifndef INCLUDED_SDSL_SUFFIX_TREE_HELPER
5#define INCLUDED_SDSL_SUFFIX_TREE_HELPER
46 , m_cur_node(it.m_cur_node)
53 m_cur_node = m_cst->sibling(m_cur_node);
84 : m_parent(p.m_parent)
90 return m_cst->select_child(m_parent, i + 1);
107template <
class t_rac>
111 bp.
resize(2 * vec.size());
113 std::stack<typename t_rac::value_type> vec_stack;
118 typename t_rac::value_type l = vec[i];
121 while (vec_stack.size() > 0 and l < vec_stack.top())
130 while (vec_stack.size() > 0 and l > vec_stack.top())
140 while (vec_stack.size() > 0)
145 assert(k == 2 * vec.size());
158template <
class t_rac>
173 if (vec[i] < vec[i - 1])
176 while (vec_stack.
size() > 0 and vec[i] < vec[vec_stack.
top()])
184 vec_stack.
push(i - 1);
194 while (vec_stack.
size() > 0 and vec[i] > vec[vec_stack.
top()])
217template <u
int8_t t_w
idth>
222 if (lcp_buf.
size() > 0)
237 while (!vec_stack.
empty() and x < vec_stack.
top())
245 vec_stack.
push(last);
257 while (!vec_stack.
empty() and x > vec_stack.
top())
281template <u
int8_t t_w
idth>
285 const bool minimum =
true)
306 while (!vec_stack.
empty() and x < vec_stack.
top())
326 while (!vec_stack.
empty() and x > vec_stack.
top())
340 while (!vec_stack.
empty())
356template <
class t_csa>
359 if (d == 0)
return idx;
363 if (csa.sa_sample_dens + csa.isa_sample_dens > 2 * d + 2)
368 return csa.isa[csa[idx] + d];
375template <
typename t_wt>
378 template <
typename T>
379 static constexpr auto
380 check(T *) ->
typename std::is_same<decltype(std::declval<T>().id(std::declval<typename T::node_type &>())),
383 return std::true_type();
386 static constexpr std::false_type
check(...)
388 return std::false_type();
390 typedef decltype(check<t_wt>(
nullptr))
type;
391 static constexpr bool value = type::value;
std::forward_iterator_tag iterator_category
cst_node_child_proxy_iterator()
typename t_cst::node_type node_type
iterator_type operator++(int)
bool operator!=(const iterator_type &it) const
const node_type const_reference
typename t_cst::node_type value_type
bool operator==(const iterator_type &it) const
cst_node_child_proxy_iterator(const t_cst *cst, node_type v)
iterator_type & operator++()
std::ptrdiff_t difference_type
cst_node_child_proxy_iterator(const iterator_type &it)
const_reference operator*() const
typename t_cst::size_type size_type
iterator_type end() const
typename t_cst::node_type node_type
iterator_type begin() const
cst_node_child_proxy(const cst_node_child_proxy &p)
cst_node_child_proxy()=delete
cst_node_child_proxy(const t_cst *cst, node_type v)
cst_node_child_proxy_iterator< t_cst > iterator_type
node_type operator[](size_type i) const
uint64_t size() const
Returns the number of elements currently stored.
int_vector_size_type size_type
size_type size() const noexcept
The number of elements in the int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Stack which contains elements from [0..n] in sorted order. Duplicates are possible.
bool empty() const
Returns if the stack is empty.
size_type top() const
Returns the topmost index on the stack.
bool pop()
Pop the topmost index of the stack.
bool push(size_type x)
Push the index x of vector vec onto the stack.
A stack which contains strictly increasing numbers in the range from to .
size_type top() const
Returns the topmost index on the stack.
void pop()
Pop the topmost index of the stack.
void push(size_type x)
Push the index x of vector vec onto the stack.
size_type size() const
Returns the number of element is the stack.
iterators.hpp contains an generic iterator for random access containers.
int_vector ::size_type size_type
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Namespace for the succinct data structure library.
t_csa::size_type get_char_pos(typename t_csa::size_type idx, typename t_csa::size_type d, const t_csa &csa)
bit_vector construct_supercartesian_tree_bp_succinct(const t_rac &vec, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
bit_vector::size_type construct_supercartesian_tree_bp_succinct_and_first_child(int_vector_buffer< t_width > &lcp_buf, bit_vector &bp, bit_vector &bp_fc, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
void construct_supercartesian_tree_bp(const t_rac &vec, bit_vector &bp, const bool minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
sorted_multi_stack_support.hpp contains a data structure for a stack which contains elements from [0....
static constexpr std::false_type check(...)
static constexpr auto check(T *) -> typename std::is_same< decltype(std::declval< T >().id(std::declval< typename T::node_type & >())), typename T::size_type >::type
static constexpr bool value
decltype(check< t_wt >(nullptr)) type