9 #ifndef INCLUDED_SDSL_WT_HUTU
10 #define INCLUDED_SDSL_WT_HUTU
38 class t_rank =
typename t_bitvector::rank_1_type,
39 class t_select =
typename t_bitvector::select_1_type,
40 class t_select_zero =
typename t_bitvector::select_0_type,
41 class t_tree_strat = byte_tree<>>
55 template <
class t_element>
75 template <
class t_element>
112 free_node(item->
left);
114 item->
left =
nullptr;
118 free_node(item->
right);
120 item->
right =
nullptr;
130 return merge1(h1, h2);
132 return merge1(h2, h1);
165 bool empty()
const {
return (m_root ==
nullptr); }
179 if (m_root ==
nullptr)
return nullptr;
180 if (m_root->
left ==
nullptr)
return m_root->
right;
181 if (m_root->
right ==
nullptr)
return m_root->
left;
183 if (m_root->
left->operator<(*m_root->
right))
186 return m_root->
right;
206 m_root = merge(m_root->
left, m_root->
right);
207 if (m_root) m_root->
parent =
nullptr;
242 m_root = merge(m_root, rhs->m_root);
243 rhs->m_root =
nullptr;
249 if (m_root !=
nullptr)
285 if (
i != other.
i) {
return i < other.
i; }
322 if (
w != other.
w) {
return w < other.
w; }
329 template <
class t_rac>
333 std::vector<ht_node> node_vector;
334 for (
size_t i = 0; i < C.size(); i++)
342 n.
pos = node_vector.size();
343 node_vector.push_back(n);
346 if (node_vector.size() == 1)
350 temp_nodes.emplace_back(
pc_node(node_vector[0].w, (
size_type)node_vector[0].c));
354 std::vector<ht_node> T(sigma);
355 std::vector<ht_node *> A(sigma);
357 std::vector<l_heap<ht_node>> HPQ(sigma);
361 T[0] = node_vector[0];
367 T[i] = node_vector[i];
370 T[i - 1].qr = HPQ[i - 1].
insert(&T[i - 1]);
371 T[i].ql = HPQ[i - 1].insert(&T[i]);
374 m->
min_sum = T[i - 1].w + T[i].w;
379 m->
myhpq = &HPQ[i - 1];
412 m->
myhpq->delete_element(l->
ql);
425 m->
myhpq->delete_element(r->
ql);
438 if (n_lt == l) n_lt =
nullptr;
439 if (n_lt) n_lt->
mpqr = n_m;
462 if (n_rt == r) n_rt =
nullptr;
463 if (n_rt) n_rt->
mpql = n_m;
471 if (n_rt) n_rt->
mpql = n_m;
484 if (n_lt) n_lt->
mpqr = n_m;
486 if (n_rt) n_rt->
mpql = n_m;
499 if (n_rt) n_rt->
mpql = n_m;
511 if (n_lt) n_lt->
mpqr = n_m;
513 if (n_rt) n_rt->
mpql = n_m;
525 if (n_lt) n_lt->
mpqr = n_m;
543 if (n_lt) n_lt->
mpqr = n_m;
544 if (n_rt) n_rt->
mpql = n_m;
552 new_node->
w = l->
w + r->
w;
554 new_node->
pos = lpos;
558 new_node->
ql = n_hpq->
insert(new_node);
571 if (tmp_min->
pos < tmp_snd->
pos)
573 n_m->
i = tmp_min->
pos;
574 n_m->
j = tmp_snd->
pos;
578 n_m->
i = tmp_snd->
pos;
579 n_m->
j = tmp_min->
pos;
598 std::vector<ht_node *> stack(sigma,
nullptr);
606 int64_t spointer = -1;
607 uint64_t qpointer = 0;
608 int64_t max_nodes = sigma;
609 while (qpointer < sigma or spointer >= 1LL)
611 if (spointer >= 1LL and (stack[spointer]->level == stack[spointer - 1]->level))
616 n_node->
left = stack[spointer - 1];
617 n_node->
right = stack[spointer];
618 n_node->
level = stack[spointer]->level - 1;
619 n_node->
w = stack[spointer]->w + stack[spointer - 1]->w;
622 n_node->
pos = temp_nodes.size();
623 temp_nodes[stack[spointer - 1]->pos].parent = temp_nodes.size();
624 temp_nodes[stack[spointer]->pos].parent = temp_nodes.size();
625 temp_nodes.emplace_back(
pc_node(n_node->
w,
628 stack[spointer - 1]->pos,
629 stack[spointer]->pos));
631 if (!stack[spointer - 1]->t)
delete stack[spointer - 1];
632 if (!stack[spointer]->t)
delete stack[spointer];
634 stack[--spointer] = n_node;
638 stack[++spointer] = &T[qpointer++];
652 if (!n->
t) {
delete n; }
659 template <
class t_wt>
void merge(l_heap< t_element > *rhs)
void delete_element(heap_node< t_element > *item)
l_heap()
Default constructor.
heap_node< t_element > * find_min() const
Get the smallest element.
bool empty() const
Indicates if the heap is empty.
heap_node< t_element > * find_snd_min() const
Get the second smallest element.
void delete_min()
Delete the smallest element in the heap.
heap_node< t_element > * insert(t_element *x)
Insert an element into the heap.
A prefix code-shaped wavelet.
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.
Node class used by the leftist heap.
heap_node(t_element *it=nullptr)
Constructor.
bool operator<(const heap_node &other)
Less then operator.
heap_node< ht_node > * qr
bool operator>(const ht_node &other)
heap_node< ht_node > * ql
bool operator<(const ht_node &other)
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.