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