8#ifndef INCLUDED_SDSL_WT_BLCD
9#define INCLUDED_SDSL_WT_BLCD
47 class t_rank =
typename t_bitvector::rank_1_type,
48 class t_select_one =
typename t_bitvector::select_1_type,
49 class t_select_zero =
typename t_bitvector::select_0_type,
57 typedef std::pair<uint64_t, uint64_t>
tPII;
63 template <
class t_rac>
67 std::vector<uint64_t> symbols;
68 std::for_each(std::begin(C),
70 [&](
decltype(*std::begin(C)) & freq)
78 uint64_t sigma = symbols.size();
83 for (uint64_t i = 1; i < temp_nodes.size(); ++i)
85 temp_nodes[i - 1] = temp_nodes[i];
86 temp_nodes[i - 1].parent = (temp_nodes[i - 1].parent + temp_nodes.size() - 1) % temp_nodes.size();
87 temp_nodes[i - 1].child[0] -= (temp_nodes[i - 1].child[0] !=
pc_node::undef);
88 temp_nodes[i - 1].child[1] -= (temp_nodes[i - 1].child[1] !=
pc_node::undef);
92 temp_nodes[temp_nodes.size() - 1] = root;
97 template <
class t_rac>
99 std::vector<uint64_t>
const & symbols,
103 std::vector<pc_node> & temp_nodes)
107 uint64_t freq = C[symbols[lb]];
109 return tPII(freq, temp_nodes.size() - 1);
114 uint64_t node_id = temp_nodes.size() - 1;
115 uint64_t l_sigma = (sigma + 1) / 2;
117 tPII freq_nptr_1 =
_construct_tree(node_id, symbols, lb + l_sigma, sigma - l_sigma, C, temp_nodes);
118 uint64_t freq = freq_nptr_0.first + freq_nptr_1.first;
119 temp_nodes[node_id].freq = freq;
120 temp_nodes[node_id].child[0] = freq_nptr_0.second;
121 temp_nodes[node_id].child[1] = freq_nptr_1.second;
122 return tPII(freq, node_id);
129 template <
class t_wt>
A prefix code-shaped wavelet.
wt_pc< balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat > wt_blcd
A balanced wavelet tree.
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
static tPII _construct_tree(uint64_t parent, std::vector< uint64_t > const &symbols, uint64_t lb, uint64_t sigma, t_rac const &C, std::vector< pc_node > &temp_nodes)
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
t_wt::size_type size_type
std::pair< uint64_t, uint64_t > tPII
_balanced_shape< t_wt > type
wt_pc.hpp contains a class for the wavelet tree of byte sequences.