4#ifndef INCLUDED_SDSL_CONSTRUCT_LCP_HELPER
5#define INCLUDED_SDSL_CONSTRUCT_LCP_HELPER
29 uint64_t max_lcp_value,
30 uint64_t lcp_value_offset)
32 std::string tmp_lcp_file = lcp_file +
"_TMP";
33 const uint64_t buffer_size = 1000000;
36 uint64_t n = lcp_buffer.
size();
39 uint8_t int_width =
bits::hi(max_lcp_value) + 1;
42 for (
size_type i = 0, calc_idx = 0; i < n; ++i)
46 out_buf[i] = lcp_buffer[i];
50 if (partial_lcp[calc_idx])
53 out_buf[i] = partial_lcp[calc_idx] + lcp_value_offset;
69 std::vector<unsigned char> cs(wt.sigma);
70 std::vector<uint64_t> rank_c_i(wt.sigma);
71 std::vector<uint64_t> rank_c_j(wt.sigma);
73 C = std::vector<uint64_t>(257, 0);
75 for (uint64_t i = 0; i < quantity; ++i)
77 unsigned char c = cs[i];
78 C[c + 1] = rank_c_j[i];
80 for (uint64_t i = 1; i < C.size() - 1; ++i) { C[i + 1] += C[i]; }
86 typedef std::queue<uint8_t> tQ;
89 static const uint32_t m_buffer_size = 10000;
90 uint8_t m_write_buf[m_buffer_size];
91 uint8_t m_read_buf[m_buffer_size];
95 size_type m_disk_buffered_blocks;
100 std::string m_file_name;
102 std::fstream m_stream;
109 , m_disk_buffered_blocks(0)
115 void init(
const std::string & dir,
char c)
130 m_write_buf[m_widx] = x;
131 if (m_sync) { m_read_buf[m_widx] = x; }
133 if (m_widx == m_buffer_size)
137 if (!m_stream.is_open())
139 m_stream.open(m_file_name, std::ios::in | std::ios::out | std::ios::binary | std::ios::trunc);
141 m_stream.seekp(m_buffer_size * (m_wb++), std::ios::beg);
142 m_stream.write((
char *)m_write_buf, m_buffer_size);
143 ++m_disk_buffered_blocks;
152 uint8_t x = m_read_buf[m_ridx];
154 if (m_ridx == m_buffer_size)
156 if (m_disk_buffered_blocks > 0)
158 m_stream.seekg(m_buffer_size * (m_rb++), std::ios::beg);
159 m_stream.read((
char *)m_read_buf, m_buffer_size);
160 --m_disk_buffered_blocks;
165 memcpy(m_read_buf, m_write_buf, m_widx + 1);
176template <
class size_type_
class>
180 uint8_t (&m_chars)[256],
181 size_type_class & m_char_count)
183 if (m_list[c].
empty()) { m_chars[m_char_count++] = c; }
184 m_list[c].push_front(i);
187template <
class size_type_
class>
191 uint8_t (&m_chars)[256],
192 size_type_class & m_char_count)
194 if (m_list[c].
empty()) { m_chars[m_char_count++] = c; }
195 m_list[c].push_back(i);
void init(const std::string &dir, char c)
void push_back(uint8_t x)
uint64_t size() const
Returns the number of elements currently stored.
void close(bool remove_file=false)
Close the int_vector_buffer.
int_vector_size_type size_type
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
std::string to_string(const T &t, int w=1)
Namespace for the succinct data structure library.
void push_back_m_index(size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
void interval_symbols(const t_wt &wt, typename t_wt::size_type i, typename t_wt::size_type j, typename t_wt::size_type &k, std::vector< typename t_wt::value_type > &cs, std::vector< typename t_wt::size_type > &rank_c_i, std::vector< typename t_wt::size_type > &rank_c_j)
For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).
void create_C_array(std::vector< uint64_t > &C, const tWT &wt)
void insert_lcp_values(int_vector<> &partial_lcp, bit_vector &index_done, std::string lcp_file, uint64_t max_lcp_value, uint64_t lcp_value_offset)
Merges a partial LCP array into the LCP array on disk.
bool empty(const range_type &r)
Empty range check.
int rename(const std::string &old_filename, const std::string &new_filename)
Rename a file.
std::vector< int_vector<>::size_type > tVI
int remove(const std::string &)
Remove a file.
std::list< int_vector<>::size_type > tLI
void push_front_m_index(size_type_class i, uint8_t c, tLI(&m_list)[256], uint8_t(&m_chars)[256], size_type_class &m_char_count)
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.