9#ifndef INCLUDED_SDSL_WT_HUTU
10#define INCLUDED_SDSL_WT_HUTU
42 class t_rank =
typename t_bitvector::rank_1_type,
43 class t_select =
typename t_bitvector::select_1_type,
44 class t_select_zero =
typename t_bitvector::select_0_type,
45 class t_tree_strat = byte_tree<>>
59 template <
class t_element>
77 template <
class t_element>
115 free_node(item->
left);
117 item->
left =
nullptr;
121 free_node(item->
right);
123 item->
right =
nullptr;
135 return merge1(h1, h2);
137 return merge1(h2, h1);
174 return (m_root ==
nullptr);
192 if (m_root ==
nullptr)
194 if (m_root->
left ==
nullptr)
195 return m_root->
right;
196 if (m_root->
right ==
nullptr)
199 if (m_root->
left->operator<(*m_root->
right))
202 return m_root->
right;
222 m_root = merge(m_root->
left, m_root->
right);
263 m_root = merge(m_root, rhs->m_root);
264 rhs->m_root =
nullptr;
270 if (m_root !=
nullptr)
314 return other < *
this;
351 return other < *
this;
355 template <
class t_rac>
359 std::vector<ht_node> node_vector;
360 for (
size_t i = 0; i < C.size(); i++)
368 n.
pos = node_vector.size();
369 node_vector.push_back(n);
372 if (node_vector.size() == 1)
376 temp_nodes.emplace_back(
pc_node(node_vector[0].w, (
size_type)node_vector[0].c));
380 std::vector<ht_node> T(sigma);
381 std::vector<ht_node *> A(sigma);
383 std::vector<l_heap<ht_node>> HPQ(sigma);
387 T[0] = node_vector[0];
393 T[i] = node_vector[i];
396 T[i - 1].qr = HPQ[i - 1].
insert(&T[i - 1]);
397 T[i].ql = HPQ[i - 1].insert(&T[i]);
400 m->
min_sum = T[i - 1].w + T[i].w;
405 m->
myhpq = &HPQ[i - 1];
440 m->
myhpq->delete_element(l->
ql);
455 m->
myhpq->delete_element(r->
ql);
595 new_node->
w = l->
w + r->
w;
597 new_node->
pos = lpos;
601 new_node->
ql = n_hpq->
insert(new_node);
614 if (tmp_min->
pos < tmp_snd->
pos)
616 n_m->
i = tmp_min->
pos;
617 n_m->
j = tmp_snd->
pos;
621 n_m->
i = tmp_snd->
pos;
622 n_m->
j = tmp_min->
pos;
641 std::vector<ht_node *> stack(sigma,
nullptr);
649 int64_t spointer = -1;
650 uint64_t qpointer = 0;
651 while (qpointer < sigma or spointer >= 1LL)
653 if (spointer >= 1LL and (stack[spointer]->level == stack[spointer - 1]->level))
657 n_node->
left = stack[spointer - 1];
658 n_node->
right = stack[spointer];
659 n_node->
level = stack[spointer]->level - 1;
660 n_node->
w = stack[spointer]->w + stack[spointer - 1]->w;
663 n_node->
pos = temp_nodes.size();
664 temp_nodes[stack[spointer - 1]->pos].parent = temp_nodes.size();
665 temp_nodes[stack[spointer]->pos].parent = temp_nodes.size();
666 temp_nodes.emplace_back(
669 if (!stack[spointer - 1]->t)
670 delete stack[spointer - 1];
671 if (!stack[spointer]->t)
672 delete stack[spointer];
674 stack[--spointer] = n_node;
678 stack[++spointer] = &T[qpointer++];
702 template <
class t_wt>
void merge(l_heap< t_element > *rhs)
heap_node< t_element > * insert(t_element *x)
Insert an element into the heap.
void delete_element(heap_node< t_element > *item)
l_heap()
Default constructor.
bool empty() const
Indicates if the heap is empty.
heap_node< t_element > * find_min() const
Get the smallest element.
void delete_min()
Delete the smallest element in the heap.
heap_node< t_element > * find_snd_min() const
Get the second smallest element.
A prefix code-shaped wavelet.
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.
Node class used by the leftist heap.
bool operator<(heap_node const &other)
Less then operator.
heap_node(t_element *it=nullptr)
Constructor.
heap_node< ht_node > * qr
bool operator>(ht_node const &other)
bool operator<(ht_node const &other)
heap_node< ht_node > * ql
bool operator<(const m_node other)
l_heap< ht_node > * myhpq
bool operator>(const m_node other)
heap_node< m_node > * qel
static void construct_tree(t_rac &C, std::vector< pc_node > &temp_nodes)
t_wt::size_type size_type
static void assign_level(ht_node *n, int64_t lvl)
wt_pc.hpp contains a class for the wavelet tree of byte sequences.