SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
wt_blcd.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_WT_BLCD
9#define INCLUDED_SDSL_WT_BLCD
10
11#include <sdsl/wt_pc.hpp>
12
14namespace sdsl
15{
16
17// forward declaration
18struct balanced_shape;
19
21
39template <class t_bitvector = bit_vector,
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<>>
45
46template <class t_wt>
48{
49 typedef typename t_wt::size_type size_type;
50 typedef std::pair<uint64_t, uint64_t> tPII; // (freq, nodenr)-pair
51 enum
52 {
53 lex_ordered = 1
54 };
55
56 template <class t_rac>
57 static void construct_tree(t_rac & C, std::vector<pc_node> & temp_nodes)
58 {
59 size_type c = 0;
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); }
63 ++c;
64 });
65 uint64_t sigma = symbols.size();
66 if (sigma > 0)
67 {
68 _construct_tree(pc_node::undef, symbols, 0, sigma, C, temp_nodes);
69 pc_node root = temp_nodes[0];
70 for (uint64_t i = 1; i < temp_nodes.size(); ++i)
71 {
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);
76 }
77 root.child[0] -= (root.child[0] != pc_node::undef);
78 root.child[1] -= (root.child[1] != pc_node::undef);
79 temp_nodes[temp_nodes.size() - 1] = root;
80 }
81 }
82
83 // recursive construct_tree method returns node frequency and node pointer
84 template <class t_rac>
85 static tPII _construct_tree(uint64_t parent,
86 const std::vector<uint64_t> & symbols,
87 uint64_t lb,
88 uint64_t sigma,
89 const t_rac & C,
90 std::vector<pc_node> & temp_nodes)
91 {
92 if (sigma == 1)
93 {
94 uint64_t freq = C[symbols[lb]];
95 temp_nodes.emplace_back(pc_node(freq, symbols[lb], parent, pc_node::undef, pc_node::undef));
96 return tPII(freq, temp_nodes.size() - 1);
97 }
98 else
99 {
100 temp_nodes.emplace_back(pc_node(0, 0, parent, pc_node::undef, pc_node::undef));
101 uint64_t node_id = temp_nodes.size() - 1;
102 uint64_t l_sigma = (sigma + 1) / 2;
103 tPII freq_nptr_0 = _construct_tree(node_id, symbols, lb, l_sigma, C, temp_nodes);
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);
110 }
111 }
112};
113
115{
116 template <class t_wt>
118};
119
120} // end namespace sdsl
121#endif
A prefix code-shaped wavelet.
Definition: wt_pc.hpp:44
Namespace for the succinct data structure library.
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:53
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
Definition: wt_blcd.hpp:57
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)
Definition: wt_blcd.hpp:85
t_wt::size_type size_type
Definition: wt_blcd.hpp:49
std::pair< uint64_t, uint64_t > tPII
Definition: wt_blcd.hpp:50
uint64_t parent
Definition: wt_helper.hpp:61
uint64_t child[2]
Definition: wt_helper.hpp:62
wt_pc.hpp contains a class for the wavelet tree of byte sequences.