4#ifndef INCLUDED_SDSL_CONSTRUCT_LCP_HELPER
5#define INCLUDED_SDSL_CONSTRUCT_LCP_HELPER
37 uint64_t max_lcp_value,
38 uint64_t lcp_value_offset)
40 std::string tmp_lcp_file = lcp_file +
"_TMP";
41 const uint64_t buffer_size = 1000000;
44 uint64_t n = lcp_buffer.
size();
47 uint8_t int_width =
bits::hi(max_lcp_value) + 1;
50 for (size_type i = 0, calc_idx = 0; i < n; ++i)
54 out_buf[i] = lcp_buffer[i];
58 if (partial_lcp[calc_idx])
61 out_buf[i] = partial_lcp[calc_idx] + lcp_value_offset;
77 std::vector<unsigned char> cs(wt.sigma);
78 std::vector<uint64_t> rank_c_i(wt.sigma);
79 std::vector<uint64_t> rank_c_j(wt.sigma);
81 C = std::vector<uint64_t>(257, 0);
83 for (uint64_t i = 0; i < quantity; ++i)
85 unsigned char c = cs[i];
86 C[c + 1] = rank_c_j[i];
88 for (uint64_t i = 1; i < C.size() - 1; ++i)
97 typedef std::queue<uint8_t> tQ;
100 static const uint32_t m_buffer_size = 10000;
101 uint8_t m_write_buf[m_buffer_size];
102 uint8_t m_read_buf[m_buffer_size];
106 size_type m_disk_buffered_blocks;
111 std::string m_file_name;
113 std::fstream m_stream;
116 buffered_char_queue() : m_widx(0), m_ridx(0), m_sync(true), m_disk_buffered_blocks(0), m_c(
'?'), m_rb(0), m_wb(0)
119 void init(std::string
const & dir,
char c)
134 m_write_buf[m_widx] = x;
137 m_read_buf[m_widx] = x;
140 if (m_widx == m_buffer_size)
144 if (!m_stream.is_open())
146 m_stream.open(m_file_name, std::ios::in | std::ios::out | std::ios::binary | std::ios::trunc);
148 m_stream.seekp(m_buffer_size * (m_wb++), std::ios::beg);
149 m_stream.write((
char *)m_write_buf, m_buffer_size);
150 ++m_disk_buffered_blocks;
159 uint8_t x = m_read_buf[m_ridx];
161 if (m_ridx == m_buffer_size)
163 if (m_disk_buffered_blocks > 0)
165 m_stream.seekg(m_buffer_size * (m_rb++), std::ios::beg);
166 m_stream.read((
char *)m_read_buf, m_buffer_size);
167 --m_disk_buffered_blocks;
172 memcpy(m_read_buf, m_write_buf, m_widx + 1);
180typedef std::list<int_vector<>::size_type>
tLI;
181typedef std::vector<int_vector<>::size_type>
tVI;
183template <
class size_type_
class>
187 uint8_t (&m_chars)[256],
188 size_type_class & m_char_count)
190 if (m_list[c].
empty())
192 m_chars[m_char_count++] = c;
194 m_list[c].push_front(i);
197template <
class size_type_
class>
201 uint8_t (&m_chars)[256],
202 size_type_class & m_char_count)
204 if (m_list[c].
empty())
206 m_chars[m_char_count++] = c;
208 m_list[c].push_back(i);
bits.hpp contains the sdsl::bits class.
void push_back(uint8_t x)
void init(std::string const &dir, char c)
uint64_t size() const
Returns the number of elements currently stored.
void close(bool remove_file=false)
Close the int_vector_buffer.
A generic vector class for integers of width .
int_vector_size_type size_type
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
std::string to_string(T const &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)
int remove(std::string const &)
Remove a file.
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.
void create_C_array(std::vector< uint64_t > &C, tWT const &wt)
int rename(std::string const &old_filename, std::string const &new_filename)
Rename a file.
void interval_symbols(t_wt const &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).
std::vector< int_vector<>::size_type > tVI
bool empty(range_type const &r)
Empty range check.
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.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.