SDSL 3.0.1
Succinct Data Structure Library
wt_huff.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.
9#ifndef INCLUDED_SDSL_WT_HUFF
10#define INCLUDED_SDSL_WT_HUFF
11
12#include <sdsl/wt_pc.hpp>
13
15namespace sdsl
16{
17
18// forward declaration
19struct huff_shape;
20
22
55template <class t_bitvector = bit_vector,
56 class t_rank = typename t_bitvector::rank_1_type,
57 class t_select = typename t_bitvector::select_1_type,
58 class t_select_zero = typename t_bitvector::select_0_type,
59 class t_tree_strat = byte_tree<>>
61
62// Huffman shape for wt_pc
63template <class t_wt>
65{
66 typedef typename t_wt::size_type size_type;
67 typedef std::pair<size_type, size_type> tPII; // (freq, nodenr)-pair
68 typedef std::priority_queue<tPII, std::vector<tPII>,
69 std::greater<tPII>> tMPQPII; // min priority queue
70 enum
71 {
72 lex_ordered = 0
73 };
74
75 template <class t_rac>
76 static void construct_tree(t_rac & C, std::vector<pc_node> & temp_nodes)
77 {
78 tMPQPII pq;
79 size_type i = 0;
80 // add leaves of Huffman tree
81 std::for_each(std::begin(C), std::end(C), [&](decltype(*std::begin(C)) & freq) {
82 if (freq > 0)
83 {
84 pq.push(tPII(freq, temp_nodes.size())); // push (frequency, node pointer)
85 // initial bv_pos with number of occurrences and bv_pos_rank
86 // value with the code of the corresponding char, parent,
87 // child[0], and child[1] are set to undef
88 temp_nodes.emplace_back(pc_node(freq, i));
89 }
90 ++i;
91 });
92 while (pq.size() > 1)
93 {
94 tPII v1, v2;
95 v1 = pq.top();
96 pq.pop();
97 v2 = pq.top();
98 pq.pop();
99 temp_nodes[v1.second].parent = temp_nodes.size(); // parent is new node
100 temp_nodes[v2.second].parent = temp_nodes.size(); // parent is new node
101 size_type frq_sum = v1.first + v2.first;
102 pq.push(tPII(frq_sum, temp_nodes.size()));
103 temp_nodes.emplace_back(pc_node(frq_sum, 0, pc_node::undef, v1.second, v2.second));
104 }
105 }
106};
107
109{
110 template <class t_wt>
112};
113
114} // end namespace sdsl
115#endif
A prefix code-shaped wavelet.
Definition: wt_pc.hpp:44
int_vector ::size_type size_type
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
std::priority_queue< tPII, std::vector< tPII >, std::greater< tPII > > tMPQPII
Definition: wt_huff.hpp:69
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
Definition: wt_huff.hpp:76
std::pair< size_type, size_type > tPII
Definition: wt_huff.hpp:67
t_wt::size_type size_type
Definition: wt_huff.hpp:66
wt_pc.hpp contains a class for the wavelet tree of byte sequences.