8#ifndef INCLUDED_SDSL_WT_BLCD
9#define INCLUDED_SDSL_WT_BLCD
40 class t_rank =
typename t_bitvector::rank_1_type,
41 class t_select_one =
typename t_bitvector::select_1_type,
42 class t_select_zero =
typename t_bitvector::select_0_type,
43 class t_tree_strat = byte_tree<>>
50 typedef std::pair<uint64_t, uint64_t>
tPII;
56 template <
class t_rac>
60 std::vector<uint64_t> symbols;
61 std::for_each(std::begin(C), std::end(C), [&](
decltype(*std::begin(C)) & freq) {
62 if (freq > 0) { symbols.push_back(c); }
65 uint64_t sigma = symbols.size();
70 for (uint64_t i = 1; i < temp_nodes.size(); ++i)
72 temp_nodes[i - 1] = temp_nodes[i];
73 temp_nodes[i - 1].
parent = (temp_nodes[i - 1].parent + temp_nodes.size() - 1) % temp_nodes.size();
74 temp_nodes[i - 1].child[0] -= (temp_nodes[i - 1].child[0] !=
pc_node::undef);
75 temp_nodes[i - 1].child[1] -= (temp_nodes[i - 1].child[1] !=
pc_node::undef);
79 temp_nodes[temp_nodes.size() - 1] = root;
84 template <
class t_rac>
86 const std::vector<uint64_t> & symbols,
90 std::vector<pc_node> & temp_nodes)
94 uint64_t freq = C[symbols[lb]];
96 return tPII(freq, temp_nodes.size() - 1);
101 uint64_t node_id = temp_nodes.size() - 1;
102 uint64_t l_sigma = (sigma + 1) / 2;
104 tPII freq_nptr_1 =
_construct_tree(node_id, symbols, lb + l_sigma, sigma - l_sigma, C, temp_nodes);
105 uint64_t freq = freq_nptr_0.first + freq_nptr_1.first;
106 temp_nodes[node_id].freq = freq;
107 temp_nodes[node_id].child[0] = freq_nptr_0.second;
108 temp_nodes[node_id].child[1] = freq_nptr_1.second;
109 return tPII(freq, node_id);
116 template <
class t_wt>
A prefix code-shaped wavelet.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
static tPII _construct_tree(uint64_t parent, const std::vector< uint64_t > &symbols, uint64_t lb, uint64_t sigma, const t_rac &C, std::vector< pc_node > &temp_nodes)
t_wt::size_type size_type
std::pair< uint64_t, uint64_t > tPII
wt_pc.hpp contains a class for the wavelet tree of byte sequences.