4#ifndef INCLUDED_SDSL_SUPPORT_TREE2
5#define INCLUDED_SDSL_SUPPORT_TREE2
20template <u
int32_t t_dens, u
int8_t t_bwt_w
idth>
22 int_vector_buffer<t_bwt_width> &,
36template <u
int32_t t_dens,
class t_cst>
91 std::string bwt_file =
cache_file_name(key_bwt<t_cst::csa_type::alphabet_type::int_width>(), config);
94 std::string sml_lcp_file =
tmp_file(config,
"_fc_lf_lcp_sml");
95 std::string big_lcp_file =
tmp_file(config,
"_fc_lf_lcp_big");
97 construct_first_child_and_lf_lcp<t_dens>(lcp_buf, bwt_buf, sml_lcp_file, big_lcp_file, m_big_lcp);
101 sml_lcp_buf.
close(
true);
129 idx = m_cst->tlcp_idx(i);
130 val = m_small_lcp[idx];
137 i = m_cst->csa.lf[i];
143 return m_big_lcp[m_small_lcp.
rank(idx, 255)] - offset;
152 written_bytes += m_small_lcp.
serialize(out, child,
"small_lcp");
153 written_bytes += m_big_lcp.
serialize(out, child,
"large_lcp");
155 return written_bytes;
159 void load(std::istream & in,
const t_cst * cst =
nullptr)
161 m_small_lcp.
load(in);
166 template <
typename archive_t>
173 template <
typename archive_t>
183 return (m_small_lcp == other.m_small_lcp) && (m_big_lcp == other.m_big_lcp);
191template <u
int32_t t_dens = 16>
194 template <
class t_cst>
203template <u
int32_t t_dens, u
int8_t t_bwt_w
idth>
206 const std::string & small_lcp_file,
207 const std::string & big_lcp_file,
211 const size_type M = 255;
212 size_type buf_len = 1000000;
215 size_type n = lcp_buf.
size();
219 osfstream big_lcp_out(big_lcp_file, std::ios::out | std::ios::trunc | std::ios::binary);
221 size_type fc_cnt = 0;
222 size_type fc_cnt_big = 0;
223 size_type fc_cnt_big2 = 0;
226 bool is_one_big_and_not_reducable =
false;
228 size_type y, max_lcp = 0;
229 uint64_t last_bwti = 0, val;
230 for (size_type i = 0, x; i < n; ++i)
233 is_one_big_and_not_reducable =
false;
235 while (!vec_stack.
empty() and x < vec_stack.
top())
238 is_one_big_and_not_reducable |= is_big_and_not_reducable[vec_stack.
size() - 1];
243 if (is_one_big_and_not_reducable)
246 big_lcp_out.write((
char *)&y,
sizeof(y));
248 if (y > max_lcp) max_lcp = y;
262 is_one_big_and_not_reducable =
false;
265 if (x > M - 2 and (0 == i or last_bwti != bwt_buf[i] or x % t_dens == 0))
267 is_big_and_not_reducable[vec_stack.
size()] = 1;
271 is_big_and_not_reducable[vec_stack.
size()] = 0;
274 last_bwti = bwt_buf[i];
277 while (!vec_stack.
empty())
284 if (is_big_and_not_reducable[vec_stack.
size()])
287 big_lcp_out.write((
char *)&y,
sizeof(y));
289 if (y > max_lcp) max_lcp = y;
307 isfstream big_lcp_in(big_lcp_file, std::ios::in | std::ios::binary);
309 big_lcp.
resize(fc_cnt_big);
311 for (size_type i = 0; i < fc_cnt_big; ++i)
313 big_lcp_in.read((
char *)&y,
sizeof(y));
An lcp array class for cst_sct3 and cst_sada.
const_iterator end() const
Returns a const_iterator to the element after the last element.
_lcp_support_tree2()
Default constructor.
random_access_const_iterator< _lcp_support_tree2 > const_iterator
_lcp_support_tree2(cache_config &config, const cst_type *cst=nullptr)
Constructor.
_lcp_support_tree2 & operator=(const _lcp_support_tree2 &)=default
int_vector ::size_type size_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
_lcp_support_tree2 & operator=(_lcp_support_tree2 &&)=default
lcp_tree_and_lf_compressed_tag lcp_category
bool operator!=(_lcp_support_tree2 const &other) const noexcept
Inequality operator.
wt_huff< bit_vector, rank_support_v5<>, select_support_scan< 1 >, select_support_scan< 0 > > small_lcp_type
void set_cst(const cst_type *cst)
const_reference * pointer
_lcp_support_tree2(_lcp_support_tree2 &&)=default
static size_type max_size()
int_vector ::value_type value_type
value_type operator[](size_type i) const
[]-operator
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
const value_type const_reference
bool operator==(_lcp_support_tree2 const &other) const noexcept
Equality operator.
const_iterator begin() const
Returns a const_iterator to the first element.
_lcp_support_tree2(const _lcp_support_tree2 &)=default
Copy / Move constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize to a stream.
const_reference reference
int_vector ::difference_type difference_type
const pointer const_pointer
void load(std::istream &in, const t_cst *cst=nullptr)
Load from a stream.
uint64_t size() const
Returns the number of elements currently stored.
void close(bool remove_file=false)
Close the int_vector_buffer.
uint64_t buffersize() const
Returns the buffersize in bytes.
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
static size_type max_size() noexcept
Maximum size of the int_vector.
void resize(const size_type size)
Resize the int_vector in terms of elements.
void close()
Close the stream.
Generic iterator for a random access container.
A class supporting linear time select queries.
Stack which contains elements from [0..n] in sorted order. Duplicates are possible.
size_type size() const
Returns the number of element is the stack.
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.
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
A prefix code-shaped wavelet.
size_type rank(size_type i, value_type c) const
Calculates how many symbols c are in the prefix [0..i-1].
void load(std::istream &in)
Loads the data structure from the given istream.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
bool empty() const
Returns whether the wavelet tree contains no data.
lcp.hpp contains classes for lcp information.
Namespace for the succinct data structure library.
std::string cache_file_name(const std::string &key, const cache_config &config)
Returns the file name of the resource.
std::string tmp_file(const cache_config &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
int remove(const std::string &)
Remove a file.
void construct_first_child_and_lf_lcp(int_vector_buffer<> &, int_vector_buffer< t_bwt_width > &, const std::string &, const std::string &, int_vector<> &)
rank_support_v.hpp contains rank_support_v.
sorted_multi_stack_support.hpp contains a data structure for a stack which contains elements from [0....
_lcp_support_tree2 lcp_type
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Helper class for construction process.
Helper class which provides _lcp_support_tree2 the context of a CST.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.
wt_huff.hpp contains a class for a Huffman shaped wavelet tree over byte sequences.