4#ifndef INCLUDED_SDSL_SUFFIX_TREE_HELPER
5#define INCLUDED_SDSL_SUFFIX_TREE_HELPER
54 m_cur_node = m_cst->sibling(m_cur_node);
65 return it.m_cur_node == m_cur_node;
69 return !(*
this == it);
93 return m_cst->select_child(m_parent, i + 1);
97 return m_cst->degree(m_parent);
101 return iterator_type(m_cst, m_cst->select_child(m_parent, 1));
119template <
class t_rac>
122 typedef typename t_rac::size_type size_type;
123 bp.
resize(2 * vec.size());
125 std::stack<typename t_rac::value_type> vec_stack;
128 for (size_type i = 0; i < vec.
size(); ++i)
130 typename t_rac::value_type l = vec[i];
133 while (vec_stack.size() > 0 and l < vec_stack.top())
142 while (vec_stack.size() > 0 and l > vec_stack.top())
152 while (vec_stack.size() > 0)
157 assert(k == 2 * vec.size());
170template <
class t_rac>
173 typedef typename t_rac::size_type size_type;
183 for (size_type i = 1; i < vec.
size(); ++i)
185 if (vec[i] < vec[i - 1])
188 while (vec_stack.
size() > 0 and vec[i] < vec[vec_stack.
top()])
196 vec_stack.
push(i - 1);
204 for (size_type i = 0; i < vec.
size(); ++i)
206 while (vec_stack.
size() > 0 and vec[i] > vec[vec_stack.
top()])
229template <u
int8_t t_w
idth>
234 if (lcp_buf.
size() > 0)
242 size_type last = lcp_buf[0];
243 for (size_type i = 1, x; i < lcp_buf.
size(); ++i)
249 while (!vec_stack.
empty() and x < vec_stack.
top())
257 vec_stack.
push(last);
266 for (size_type i = 0, x; i < lcp_buf.
size(); ++i)
269 while (!vec_stack.
empty() and x > vec_stack.
top())
293template <u
int8_t t_w
idth>
297 bool const minimum =
true)
300 size_type n = lcp_buf.
size();
305 size_type fc_cnt = 0;
315 for (size_type i = 0, x; i < n; ++i)
318 while (!vec_stack.
empty() and x < vec_stack.
top())
335 for (size_type i = 0, x; i < n; ++i)
338 while (!vec_stack.
empty() and x > vec_stack.
top())
352 while (!vec_stack.
empty())
368template <
class t_csa>
369typename t_csa::size_type
get_char_pos(
typename t_csa::size_type idx,
typename t_csa::size_type d, t_csa
const & csa)
376 if (csa.sa_sample_dens + csa.isa_sample_dens > 2 * d + 2)
378 for (
typename t_csa::size_type i = 0; i < d; ++i)
382 return csa.isa[csa[idx] + d];
389template <
typename t_wt>
392 template <
typename T>
394 typename std::is_same<decltype(std::declval<T>().id(std::declval<typename T::node_type &>())),
395 typename T::size_type>
::type
397 return std::true_type();
400 static constexpr std::false_type
check(...)
402 return std::false_type();
405 static constexpr bool value = type::value;
cst_node_child_proxy_iterator(t_cst const *cst, node_type v)
std::forward_iterator_tag iterator_category
cst_node_child_proxy_iterator(iterator_type const &it)
cst_node_child_proxy_iterator()
typename t_cst::node_type node_type
iterator_type operator++(int)
const node_type const_reference
typename t_cst::node_type value_type
bool operator!=(iterator_type const &it) const
iterator_type & operator++()
std::ptrdiff_t difference_type
bool operator==(iterator_type const &it) const
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()=delete
cst_node_child_proxy(cst_node_child_proxy const &p)
cst_node_child_proxy_iterator< t_cst > iterator_type
cst_node_child_proxy(t_cst const *cst, node_type v)
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.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
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, t_csa const &csa)
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, bool const minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
void construct_supercartesian_tree_bp(t_rac const &vec, bit_vector &bp, bool const minimum=true)
Calculate the balanced parentheses of the Super-Cartesian tree, described in Ohlebusch and Gog (SPIRE...
bit_vector construct_supercartesian_tree_bp_succinct(t_rac const &vec, bool const 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
decltype(check< t_wt >(nullptr)) type
static constexpr bool value
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.