SDSL 3.0.3
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 <cstdint>
12#include <memory>
13#include <utility>
14#include <vector>
15
16#include <sdsl/int_vector.hpp>
17#include <sdsl/wt_helper.hpp>
18#include <sdsl/wt_pc.hpp>
19
21namespace sdsl
22{
23
24// forward declaration
25struct balanced_shape;
26
28
46template <class t_bitvector = bit_vector,
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,
50 class t_tree_strat = byte_tree<>>
52
53template <class t_wt>
55{
56 typedef typename t_wt::size_type size_type;
57 typedef std::pair<uint64_t, uint64_t> tPII; // (freq, nodenr)-pair
58 enum
59 {
61 };
62
63 template <class t_rac>
64 static void construct_tree(t_rac & C, std::vector<pc_node> & temp_nodes)
65 {
66 size_type c = 0;
67 std::vector<uint64_t> symbols;
68 std::for_each(std::begin(C),
69 std::end(C),
70 [&](decltype(*std::begin(C)) & freq)
71 {
72 if (freq > 0)
73 {
74 symbols.push_back(c);
75 }
76 ++c;
77 });
78 uint64_t sigma = symbols.size();
79 if (sigma > 0)
80 {
81 _construct_tree(pc_node::undef, symbols, 0, sigma, C, temp_nodes);
82 pc_node root = temp_nodes[0];
83 for (uint64_t i = 1; i < temp_nodes.size(); ++i)
84 {
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);
89 }
90 root.child[0] -= (root.child[0] != pc_node::undef);
91 root.child[1] -= (root.child[1] != pc_node::undef);
92 temp_nodes[temp_nodes.size() - 1] = root;
93 }
94 }
95
96 // recursive construct_tree method returns node frequency and node pointer
97 template <class t_rac>
98 static tPII _construct_tree(uint64_t parent,
99 std::vector<uint64_t> const & symbols,
100 uint64_t lb,
101 uint64_t sigma,
102 t_rac const & C,
103 std::vector<pc_node> & temp_nodes)
104 {
105 if (sigma == 1)
106 {
107 uint64_t freq = C[symbols[lb]];
108 temp_nodes.emplace_back(pc_node(freq, symbols[lb], parent, pc_node::undef, pc_node::undef));
109 return tPII(freq, temp_nodes.size() - 1);
110 }
111 else
112 {
113 temp_nodes.emplace_back(pc_node(0, 0, parent, pc_node::undef, pc_node::undef));
114 uint64_t node_id = temp_nodes.size() - 1;
115 uint64_t l_sigma = (sigma + 1) / 2;
116 tPII freq_nptr_0 = _construct_tree(node_id, symbols, lb, l_sigma, C, temp_nodes);
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);
123 }
124 }
125};
126
128{
129 template <class t_wt>
131};
132
133} // end namespace sdsl
134#endif
A prefix code-shaped wavelet.
Definition wt_pc.hpp:60
wt_pc< balanced_shape, t_bitvector, t_rank, t_select_one, t_select_zero, t_tree_strat > wt_blcd
A balanced wavelet tree.
Definition wt_blcd.hpp:51
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)
Definition wt_blcd.hpp:98
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
Definition wt_blcd.hpp:64
t_wt::size_type size_type
Definition wt_blcd.hpp:56
std::pair< uint64_t, uint64_t > tPII
Definition wt_blcd.hpp:57
_balanced_shape< t_wt > type
Definition wt_blcd.hpp:130
uint64_t child[2]
Definition wt_helper.hpp:77
wt_pc.hpp contains a class for the wavelet tree of byte sequences.