4#ifndef INCLUDED_SDSL_SUPPORT_TREE2
5#define INCLUDED_SDSL_SUPPORT_TREE2
33template <u
int32_t t_dens, u
int8_t t_bwt_w
idth>
35 int_vector_buffer<t_bwt_width> &,
49template <u
int32_t t_dens,
class t_cst>
108 std::string sml_lcp_file =
tmp_file(config,
"_fc_lf_lcp_sml");
109 std::string big_lcp_file =
tmp_file(config,
"_fc_lf_lcp_big");
115 sml_lcp_buf.
close(
true);
126 return m_cst->size();
136 return m_small_lcp.
empty();
161 idx = m_cst->tlcp_idx(i);
162 val = m_small_lcp[idx];
169 i = m_cst->csa.lf[i];
175 return m_big_lcp[m_small_lcp.
rank(idx, 255)] - offset;
184 written_bytes += m_small_lcp.
serialize(out, child,
"small_lcp");
185 written_bytes += m_big_lcp.
serialize(out, child,
"large_lcp");
187 return written_bytes;
191 void load(std::istream & in, t_cst
const * cst =
nullptr)
193 m_small_lcp.
load(in);
198 template <
typename archive_t>
205 template <
typename archive_t>
215 return (m_small_lcp == other.m_small_lcp) && (m_big_lcp == other.m_big_lcp);
221 return !(*
this == other);
226template <u
int32_t t_dens = 16>
229 template <
class t_cst>
238template <u
int32_t t_dens, u
int8_t t_bwt_w
idth>
241 std::string
const & small_lcp_file,
242 std::string
const & big_lcp_file,
246 const size_type M = 255;
247 size_type buf_len = 1000000;
250 size_type n = lcp_buf.
size();
254 osfstream big_lcp_out(big_lcp_file, std::ios::out | std::ios::trunc | std::ios::binary);
256 size_type fc_cnt_big = 0;
259 bool is_one_big_and_not_reducable =
false;
261 size_type y, max_lcp = 0;
262 uint64_t last_bwti = 0, val;
263 for (size_type i = 0, x; i < n; ++i)
266 is_one_big_and_not_reducable =
false;
268 while (!vec_stack.
empty() and x < vec_stack.
top())
271 is_one_big_and_not_reducable |= is_big_and_not_reducable[vec_stack.
size() - 1];
276 if (is_one_big_and_not_reducable)
279 big_lcp_out.write((
char *)&y,
sizeof(y));
294 is_one_big_and_not_reducable =
false;
297 if (x > M - 2 and (0 == i or last_bwti != bwt_buf[i] or x % t_dens == 0))
299 is_big_and_not_reducable[vec_stack.
size()] = 1;
303 is_big_and_not_reducable[vec_stack.
size()] = 0;
306 last_bwti = bwt_buf[i];
309 while (!vec_stack.
empty())
316 if (is_big_and_not_reducable[vec_stack.
size()])
319 big_lcp_out.write((
char *)&y,
sizeof(y));
338 isfstream big_lcp_in(big_lcp_file, std::ios::in | std::ios::binary);
340 big_lcp.
resize(fc_cnt_big);
342 for (size_type i = 0; i < fc_cnt_big; ++i)
344 big_lcp_in.read((
char *)&y,
sizeof(y));
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
An lcp array class for cst_sct3 and cst_sada.
_lcp_support_tree2(_lcp_support_tree2 const &)=default
Copy / Move constructor.
const_iterator end() const
Returns a const_iterator to the element after the last element.
void load(std::istream &in, t_cst const *cst=nullptr)
Load from a stream.
void set_cst(cst_type const *cst)
_lcp_support_tree2()
Default constructor.
random_access_const_iterator< _lcp_support_tree2 > const_iterator
_lcp_support_tree2(cache_config &config, cst_type const *cst=nullptr)
Constructor.
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
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
_lcp_support_tree2 & operator=(_lcp_support_tree2 const &)=default
bool operator==(_lcp_support_tree2 const &other) const noexcept
Equality operator.
const_iterator begin() const
Returns a const_iterator to the first element.
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
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.
A generic vector class for integers of width .
ptrdiff_t difference_type
int_vector_size_type size_type
int_vector_trait< t_width >::value_type value_type
void load(std::istream &in)
Load the int_vector for 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.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
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, std::string const &name, std::string const &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.
csa_alphabet_strategy.hpp includes different strategy classes for representing an alphabet of a CSA.
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
std::string tmp_file(cache_config const &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
std::string cache_file_name(std::string const &key, cache_config const &config)
Returns the file name of the resource.
constexpr char const * key_bwt()
void construct_first_child_and_lf_lcp(int_vector_buffer<> &, int_vector_buffer< t_bwt_width > &, std::string const &, std::string const &, int_vector<> &)
rank_support_v5.hpp contains rank_support_v5.5
Contains declarations and definitions of data structure concepts.
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
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.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
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.