SDSL  3.0.0
Succinct Data Structure Library
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 
14 namespace sdsl
15 {
16 
17 // forward declaration
18 struct balanced_shape;
19 
21 
39 template <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 
46 template <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
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
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.