SDSL  3.0.0
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 
15 namespace sdsl
16 {
17 
18 // forward declaration
19 struct huff_shape;
20 
22 
55 template <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
63 template <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:51
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.