SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
wm_int.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_WM_INT
10#define INCLUDED_SDSL_WM_INT
11
12#include <algorithm> // for std::swap
13#include <array>
14#include <assert.h>
15#include <cstdint>
16#include <functional>
17#include <iterator>
18#include <ostream>
19#include <stddef.h>
20#include <string>
21#include <tuple>
22#include <type_traits>
23#include <utility>
24#include <vector>
25
26#include <sdsl/bits.hpp>
27#include <sdsl/cereal.hpp>
28#include <sdsl/int_vector.hpp>
30#include <sdsl/io.hpp>
31#include <sdsl/iterators.hpp>
32#include <sdsl/ram_fs.hpp>
34#include <sdsl/sfstream.hpp>
36#include <sdsl/util.hpp>
37#include <sdsl/wt_helper.hpp>
38
40namespace sdsl
41{
42
44
59template <class t_bitvector = bit_vector,
60 class t_rank = typename t_bitvector::rank_1_type,
61 class t_select = typename t_bitvector::select_1_type,
62 class t_select_zero = typename t_bitvector::select_0_type>
63class wm_int
64{
65public:
68 typedef typename t_bitvector::difference_type difference_type;
71 typedef t_bitvector bit_vector_type;
72 typedef t_rank rank_1_type;
73 typedef t_select select_1_type;
74 typedef t_select_zero select_0_type;
77 enum
78 {
79 lex_ordered = 0
80 };
81
82 typedef std::pair<value_type, size_type> point_type;
83 typedef std::vector<point_type> point_vec_type;
84 typedef std::pair<size_type, point_vec_type> r2d_res_type;
85
86 struct node_type;
87
88protected:
90 size_type m_sigma = 0; //<- \f$ |\Sigma| \f$
91 bit_vector_type m_tree; // bit vector to store the wavelet tree
92 rank_1_type m_tree_rank; // rank support for the wavelet tree bit vector
93 select_1_type m_tree_select1; // select support for the wavelet tree bit vector
95 uint32_t m_max_level = 0;
96 int_vector<64> m_zero_cnt; // m_zero_cnt[i] contains the number of zeros in level i
97 int_vector<64> m_rank_level; // m_rank_level[i] contains m_tree_rank(i*size())
98
99public:
102 uint32_t const & max_level = m_max_level;
103
105 wm_int() = default;
106
108
116 template <typename t_it>
117 wm_int(t_it begin, t_it end, std::string tmp_dir = ram_file_name("")) : m_size(std::distance(begin, end))
118 {
119 if (0 == m_size)
120 return;
121 m_sigma = 0;
122
123 value_type max_elem = 1; // variable for the biggest value in rac
124 for (auto it = begin; it != end; ++it)
125 {
126 value_type value = *it;
127 if (value > max_elem)
128 max_elem = value;
129 }
130 m_max_level = bits::hi(max_elem) + 1;
131 std::string tree_out_buf_file_name = tmp_file(tmp_dir, "_m_tree");
132 {
134 std::copy(begin, end, rac.begin());
135
136 // buffer for elements in the right node
137 std::string zero_buf_file_name = tmp_file(tmp_dir, "_zero_buf");
138 osfstream tree_out_buf(tree_out_buf_file_name,
139 std::ios::binary | std::ios::trunc | std::ios::out); // open buffer for tree
140 size_type bit_size = m_size * m_max_level;
141 int_vector<1>::write_header(bit_size, 1, tree_out_buf); // write bv header
142
143 size_type tree_pos = 0;
144 uint64_t tree_word = 0;
145
146 m_zero_cnt = int_vector<64>(m_max_level, 0); // zeros at level i
147
148 for (uint32_t k = 0; k < m_max_level; ++k)
149 {
150 uint8_t width = m_max_level - k - 1;
151 const uint64_t mask = 1ULL << width;
152 uint64_t x = 0;
153 size_type zeros = 0;
154 int_vector_buffer<> zero_buf(zero_buf_file_name, std::ios::out, 1024 * 1024, m_max_level);
155 for (size_t i = 0; i < m_size; ++i)
156 {
157 x = rac[i];
158 if (x & mask)
159 {
160 tree_word |= (1ULL << (tree_pos & 0x3FULL));
161 zero_buf.push_back(x);
162 }
163 else
164 {
165 rac[zeros++] = x;
166 }
167 ++tree_pos;
168 if ((tree_pos & 0x3FULL) == 0)
169 { // if tree_pos % 64 == 0 write old word
170 tree_out_buf.write((char *)&tree_word, sizeof(tree_word));
171 tree_word = 0;
172 }
173 }
174 m_zero_cnt[k] = zeros;
175 for (size_t i = zeros; i < m_size; ++i)
176 {
177 rac[i] = zero_buf[i - zeros];
178 }
179 }
180 if ((tree_pos & 0x3FULL) != 0)
181 { // if tree_pos % 64 > 0 => there are remaining entries we have to write
182 tree_out_buf.write((char *)&tree_word, sizeof(tree_word));
183 }
184 sdsl::remove(zero_buf_file_name);
185 tree_out_buf.close();
186 m_sigma = std::unique(rac.begin(), rac.end()) - rac.begin();
187 }
189 load_from_file(tree, tree_out_buf_file_name);
190 sdsl::remove(tree_out_buf_file_name);
191 m_tree = bit_vector_type(std::move(tree));
192 util::init_support(m_tree_rank, &m_tree);
193 util::init_support(m_tree_select0, &m_tree);
194 util::init_support(m_tree_select1, &m_tree);
196 for (uint32_t k = 0; k < m_rank_level.size(); ++k)
197 {
199 }
200 }
201
203 wm_int(wm_int const & wt) :
204 m_size(wt.m_size),
205 m_sigma(wt.m_sigma),
206 m_tree(wt.m_tree),
213 {
214 m_tree_rank.set_vector(&m_tree);
215 m_tree_select1.set_vector(&m_tree);
216 m_tree_select0.set_vector(&m_tree);
217 }
218
220 wm_int(wm_int && wt) :
221 m_size(wt.m_size),
222 m_sigma(wt.m_sigma),
223 m_tree(std::move(wt.m_tree)),
224 m_tree_rank(std::move(wt.m_tree_rank)),
225 m_tree_select1(std::move(wt.m_tree_select1)),
226 m_tree_select0(std::move(wt.m_tree_select0)),
230 {
231 m_tree_rank.set_vector(&m_tree);
232 m_tree_select1.set_vector(&m_tree);
233 m_tree_select0.set_vector(&m_tree);
234 }
235
237 wm_int & operator=(wm_int const & wt)
238 {
239 if (this != &wt)
240 {
241 m_size = wt.m_size;
242 m_sigma = wt.m_sigma;
243 m_tree = wt.m_tree;
245 m_tree_rank.set_vector(&m_tree);
247 m_tree_select1.set_vector(&m_tree);
249 m_tree_select0.set_vector(&m_tree);
253 }
254 return *this;
255 }
256
259 {
260 if (this != &wt)
261 {
262 m_size = wt.m_size;
263 m_sigma = wt.m_sigma;
264 m_tree = std::move(wt.m_tree);
265 m_tree_rank = std::move(wt.m_tree_rank);
266 m_tree_rank.set_vector(&m_tree);
267 m_tree_select1 = std::move(wt.m_tree_select1);
268 m_tree_select1.set_vector(&m_tree);
269 m_tree_select0 = std::move(wt.m_tree_select0);
270 m_tree_select0.set_vector(&m_tree);
271 m_max_level = std::move(wt.m_max_level);
272 m_zero_cnt = std::move(wt.m_zero_cnt);
273 m_rank_level = std::move(wt.m_rank_level);
274 }
275 return *this;
276 }
277
280 {
281 return m_size;
282 }
283
285 bool empty() const
286 {
287 return m_size == 0;
288 }
289
291
297 {
298 assert(i < size());
299 value_type res = 0;
300 for (uint32_t k = 0; k < m_max_level; ++k)
301 {
302 res <<= 1;
303 size_type rank_ones = m_tree_rank(i) - m_rank_level[k];
304 if (m_tree[i])
305 { // one at position i => follow right child
306 i = (k + 1) * m_size + m_zero_cnt[k] + rank_ones;
307 res |= 1;
308 }
309 else
310 { // zero at position i => follow left child
311 auto rank_zeros = (i - k * m_size) - rank_ones;
312 i = (k + 1) * m_size + rank_zeros;
313 }
314 }
315 return res;
316 };
317
319
329 {
330 assert(i <= size());
331 if (((1ULL) << (m_max_level)) <= c)
332 { // c is greater than any symbol in wt
333 return 0;
334 }
335 size_type b = 0; // start position of the interval
336 uint64_t mask = (1ULL) << (m_max_level - 1);
337 for (uint32_t k = 0; k < m_max_level and i; ++k)
338 {
339 size_type rank_b = m_tree_rank(b);
340 size_type ones = m_tree_rank(b + i) - rank_b; // ones in [b..i)
341 size_type ones_p = rank_b - m_rank_level[k]; // ones in [level_b..b)
342 if (c & mask)
343 { // search for a one at this level
344 i = ones;
345 b = (k + 1) * m_size + m_zero_cnt[k] + ones_p;
346 }
347 else
348 { // search for a zero at this level
349 i = i - ones;
350 b = (k + 1) * m_size + (b - k * m_size - ones_p);
351 }
352 mask >>= 1;
353 }
354 return i;
355 };
356
358
364 std::pair<size_type, value_type> inverse_select(size_type i) const
365 {
366 assert(i < size());
367 value_type c = 0;
368 size_type b = 0; // start position of the interval
369 for (uint32_t k = 0; k < m_max_level; ++k)
370 {
371 size_type rank_b = m_tree_rank(b);
372 size_type ones = m_tree_rank(b + i) - rank_b; // ones in [b..i)
373 size_type ones_p = rank_b - m_rank_level[k]; // ones in [level_b..b)
374 c <<= 1;
375 if (m_tree[b + i])
376 { // go to the right child
377 i = ones;
378 b = (k + 1) * m_size + m_zero_cnt[k] + ones_p;
379 c |= 1;
380 }
381 else
382 { // go to the left child
383 i = i - ones;
384 b = (k + 1) * m_size + (b - k * m_size - ones_p);
385 }
386 }
387 return std::make_pair(i, c);
388 }
389
391
400 {
401 assert(1 <= i and i <= rank(size(), c));
402 uint64_t mask = 1ULL << (m_max_level - 1);
403 int_vector<64> m_path_off(max_level + 1);
404 int_vector<64> m_path_rank_off(max_level + 1);
405 m_path_off[0] = m_path_rank_off[0] = 0;
406 size_type b = 0; // start position of the interval
407 size_type r = i;
408 for (uint32_t k = 0; k < m_max_level and i; ++k)
409 {
410 size_type rank_b = m_tree_rank(b);
411 size_type ones = m_tree_rank(b + r) - rank_b; // ones in [b..i)
412 size_type ones_p = rank_b - m_rank_level[k]; // ones in [0..b)
413 if (c & mask)
414 { // search for a one at this level
415 r = ones;
416 b = (k + 1) * m_size + m_zero_cnt[k] + ones_p;
417 }
418 else
419 { // search for a zero at this level
420 r = r - ones;
421 b = (k + 1) * m_size + (b - k * m_size - ones_p);
422 }
423 mask >>= 1;
424 m_path_off[k + 1] = b;
425 m_path_rank_off[k] = rank_b;
426 }
427 mask = 1ULL;
428 for (uint32_t k = m_max_level; k > 0; --k)
429 {
430 b = m_path_off[k - 1];
431 size_type rank_b = m_path_rank_off[k - 1];
432 if (c & mask)
433 { // right child => search i'th one
434 i = m_tree_select1(rank_b + i) - b + 1;
435 }
436 else
437 { // left child => search i'th zero
438 i = m_tree_select0(b - rank_b + i) - b + 1;
439 }
440 mask <<= 1;
441 }
442 return i - 1;
443 };
444
446
454 std::pair<size_type, std::vector<std::pair<value_type, size_type>>>
455 range_search_2d(size_type lb, size_type rb, value_type vlb, value_type vrb, bool report = true) const
456 {
457
458 if (vrb > (1ULL << m_max_level))
459 vrb = (1ULL << m_max_level);
460 if (vlb > vrb)
461 return make_pair(0, point_vec_type());
462 size_type cnt_answers = 0;
463 point_vec_type point_vec;
464 if (lb <= rb)
465 {
466 std::vector<size_type> is(m_max_level + 1);
467 std::vector<size_type> rank_off(m_max_level + 1);
468 _range_search_2d(root(), {{lb, rb}}, vlb, vrb, 0, is, rank_off, point_vec, report, cnt_answers);
469 }
470 return make_pair(cnt_answers, point_vec);
471 }
472
474 range_type r,
475 value_type vlb,
476 value_type vrb,
477 size_type ilb,
478 std::vector<size_type> & is,
479 std::vector<size_type> & rank_off,
480 point_vec_type & point_vec,
481 bool report,
482 size_type & cnt_answers) const
483 {
484 using std::get;
485 if (get<0>(r) > get<1>(r))
486 return;
487 is[v.level] = v.offset + get<0>(r);
488
489 if (v.level == m_max_level)
490 {
491 for (size_type j = 1; j <= sdsl::size(r) and report; ++j)
492 {
493 size_type i = j;
494 size_type c = v.sym;
495 for (uint32_t k = m_max_level; k > 0; --k)
496 {
497 size_type offset = is[k - 1];
498 size_type rank_offset = rank_off[k - 1];
499 if (c & 1)
500 {
501 i = m_tree_select1(rank_offset + i) - offset + 1;
502 }
503 else
504 {
505 i = m_tree_select0(offset - rank_offset + i) - offset + 1;
506 }
507 c >>= 1;
508 }
509 point_vec.emplace_back(is[0] + i - 1, v.sym);
510 }
511 cnt_answers += sdsl::size(r);
512 return;
513 }
514 else
515 {
516 rank_off[v.level] = m_tree_rank(is[v.level]);
517 }
518 size_type irb = ilb + (1ULL << (m_max_level - v.level));
519 size_type mid = (irb + ilb) >> 1;
520
521 auto c_v = expand(v);
522 auto c_r = expand(v, r);
523
524 if (!sdsl::empty(get<0>(c_r)) and vlb < mid and mid)
525 {
526 _range_search_2d(get<0>(c_v),
527 get<0>(c_r),
528 vlb,
529 std::min(vrb, mid - 1),
530 ilb,
531 is,
532 rank_off,
533 point_vec,
534 report,
535 cnt_answers);
536 }
537 if (!sdsl::empty(get<1>(c_r)) and vrb >= mid)
538 {
539 _range_search_2d(get<1>(c_v),
540 get<1>(c_r),
541 std::max(mid, vlb),
542 vrb,
543 mid,
544 is,
545 rank_off,
546 point_vec,
547 report,
548 cnt_answers);
549 }
550 }
551
554 {
555 return const_iterator(this, 0);
556 }
557
560 {
561 return const_iterator(this, size());
562 }
563
565 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
566 {
567 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
568 size_type written_bytes = 0;
569 written_bytes += write_member(m_size, out, child, "size");
570 written_bytes += write_member(m_sigma, out, child, "sigma");
571 written_bytes += m_tree.serialize(out, child, "tree");
572 written_bytes += m_tree_rank.serialize(out, child, "tree_rank");
573 written_bytes += m_tree_select1.serialize(out, child, "tree_select_1");
574 written_bytes += m_tree_select0.serialize(out, child, "tree_select_0");
575 written_bytes += write_member(m_max_level, out, child, "max_level");
576 written_bytes += m_zero_cnt.serialize(out, child, "zero_cnt");
577 written_bytes += m_rank_level.serialize(out, child, "rank_level");
578 structure_tree::add_size(child, written_bytes);
579 return written_bytes;
580 }
581
583 void load(std::istream & in)
584 {
585 read_member(m_size, in);
586 read_member(m_sigma, in);
587 m_tree.load(in);
588 m_tree_rank.load(in, &m_tree);
589 m_tree_select1.load(in, &m_tree);
590 m_tree_select0.load(in, &m_tree);
592 m_zero_cnt.load(in);
593 m_rank_level.load(in);
594 }
595
597 template <typename archive_t>
598 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
599 {
600 ar(CEREAL_NVP(m_size));
601 ar(CEREAL_NVP(m_sigma));
603 ar(CEREAL_NVP(m_tree));
609 }
610
612 template <typename archive_t>
613 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
614 {
615 ar(CEREAL_NVP(m_size));
616 ar(CEREAL_NVP(m_sigma));
618 ar(CEREAL_NVP(m_tree));
620 m_tree_rank.set_vector(&m_tree);
622 m_tree_select1.set_vector(&m_tree);
624 m_tree_select0.set_vector(&m_tree);
627 }
628
630 bool operator==(wm_int const & other) const noexcept
631 {
632 return (m_size == other.m_size) && (m_sigma == other.m_sigma) && (m_max_level == other.m_max_level)
633 && (m_tree == other.m_tree) && (m_tree_rank == other.m_tree_rank)
634 && (m_tree_select1 == other.m_tree_select1) && (m_tree_select0 == other.m_tree_select0)
635 && (m_zero_cnt == other.m_zero_cnt) && (m_rank_level == other.m_rank_level);
636 }
637
639 bool operator!=(wm_int const & other) const noexcept
640 {
641 return !(*this == other);
642 }
643
646 {
651
652 // Default constructor
653 node_type(size_type o = 0, size_type sz = 0, size_type l = 0, value_type sy = 0) :
654 offset(o),
655 size(sz),
656 level(l),
657 sym(sy)
658 {}
659
660 // Copy constructor
661 node_type(node_type const &) = default;
662
663 // Move copy constructor
664 node_type(node_type &&) = default;
665
666 // Assignment operator
667 node_type & operator=(node_type const &) = default;
668
669 // Move assignment operator
671
672 // Comparator operator
673 bool operator==(node_type const & v) const
674 {
675 return offset == v.offset;
676 }
677
678 // Smaller operator
679 bool operator<(node_type const & v) const
680 {
681 return offset < v.offset;
682 }
683
684 // Greater operator
685 bool operator>(node_type const & v) const
686 {
687 return offset > v.offset;
688 }
689 };
690
692 bool is_leaf(node_type const & v) const
693 {
694 return v.level == m_max_level;
695 }
696
698 value_type sym(node_type const & v) const
699 {
700 return v.sym;
701 }
702
705 {
707 }
708
710 auto seq(node_type const & v) const -> random_access_container<std::function<value_type(size_type)>>
711 {
712 return random_access_container<std::function<value_type(size_type)>>(
713 [&v, this](size_type i)
714 {
715 node_type vv = v;
716 while (!is_leaf(vv))
717 {
718 auto vs = expand(vv);
719 auto rs = expand(vv, {0, i});
720 bool bit = *(begin(vv) + i);
721 i = std::get<1>(rs[bit]);
722 vv = vs[bit];
723 }
724 return sym(vv);
725 },
726 size(v));
727 }
728
730 bool empty(node_type const & v) const
731 {
732 return v.size == (size_type)0;
733 }
734
736 auto size(node_type const & v) const -> decltype(v.size)
737 {
738 return v.size;
739 }
740
743 {
744 return node_type(0, m_size, 0, 0);
745 }
746
748
752 std::array<node_type, 2> expand(node_type const & v) const
753 {
754 node_type v_right = v;
755 return expand(std::move(v_right));
756 }
757
759
763 std::array<node_type, 2> expand(node_type && v) const
764 {
765 node_type v_left;
766 size_type rank_b = m_tree_rank(v.offset);
767 size_type ones = m_tree_rank(v.offset + v.size) - rank_b; // ones in [b..size)
768 size_type ones_p = rank_b - m_rank_level[v.level]; // ones in [level_b..b)
769
770 v_left.offset = (v.level + 1) * m_size + (v.offset - v.level * m_size) - ones_p;
771 v_left.size = v.size - ones;
772 v_left.level = v.level + 1;
773 v_left.sym = v.sym << 1;
774
775 v.offset = (v.level + 1) * m_size + m_zero_cnt[v.level] + ones_p;
776 v.size = ones;
777 v.level = v.level + 1;
778 v.sym = (v.sym << 1) | 1;
779
780 return {{std::move(v_left), v}};
781 }
782
784
793 std::array<range_vec_type, 2> expand(node_type const & v, range_vec_type const & ranges) const
794 {
795 auto ranges_copy = ranges;
796 return expand(v, std::move(ranges_copy));
797 }
798
800
809 std::array<range_vec_type, 2> expand(node_type const & v, range_vec_type && ranges) const
810 {
811 auto v_sp_rank = m_tree_rank(v.offset); // this is already calculated in expand(v)
812 range_vec_type res(ranges.size());
813 size_t i = 0;
814 for (auto & r : ranges)
815 {
816 auto sp_rank = m_tree_rank(v.offset + r[0]);
817 auto right_size = m_tree_rank(v.offset + r[1] + 1) - sp_rank;
818 auto left_size = (r[1] - r[0] + 1) - right_size;
819
820 auto right_sp = sp_rank - v_sp_rank;
821 auto left_sp = r[0] - right_sp;
822
823 r = {{left_sp, left_sp + left_size - 1}};
824 res[i++] = {{right_sp, right_sp + right_size - 1}};
825 }
826 return {{ranges, std::move(res)}};
827 }
828
830
839 std::array<range_type, 2> expand(node_type const & v, range_type const & r) const
840 {
841 auto v_sp_rank = m_tree_rank(v.offset); // this is already calculated in expand(v)
842 auto sp_rank = m_tree_rank(v.offset + r[0]);
843 auto right_size = m_tree_rank(v.offset + r[1] + 1) - sp_rank;
844 auto left_size = (r[1] - r[0] + 1) - right_size;
845
846 auto right_sp = sp_rank - v_sp_rank;
847 auto left_sp = r[0] - right_sp;
848
849 return {{{{left_sp, left_sp + left_size - 1}}, {{right_sp, right_sp + right_size - 1}}}};
850 }
851
853 std::pair<uint64_t, uint64_t> path(value_type c) const
854 {
855 return {m_max_level, c};
856 }
857
858private:
860 auto begin(node_type const & v) const -> decltype(m_tree.begin() + v.offset)
861 {
862 return m_tree.begin() + v.offset;
863 }
864
866 auto end(node_type const & v) const -> decltype(m_tree.begin() + v.offset + v.size)
867 {
868 return m_tree.begin() + v.offset + v.size;
869 }
870};
871
872} // end namespace sdsl
873#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
void push_back(const uint64_t value)
Appends the given element value to the end of the int_vector_buffer.
A generic vector class for integers of width .
Definition io.hpp:36
static uint64_t write_header(uint64_t size, uint8_t int_width, std::ostream &out)
Write the size and int_width of a int_vector.
iterator end() noexcept
Iterator that points to the element after the last element of int_vector.
int_vector_size_type size_type
int_vector_trait< t_width >::value_type value_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
iterator begin() noexcept
Iterator that points to the first element of the int_vector.
void close()
Close the stream.
Definition sfstream.hpp:91
Generic iterator for a random access container.
Definition iterators.hpp:24
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
A wavelet tree class for integer sequences.
Definition wm_int.hpp:64
uint32_t m_max_level
Definition wm_int.hpp:95
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition wm_int.hpp:559
t_bitvector::difference_type difference_type
Definition wm_int.hpp:68
size_type const & sigma
Effective alphabet size of the wavelet tree.
Definition wm_int.hpp:100
std::pair< size_type, point_vec_type > r2d_res_type
Definition wm_int.hpp:84
const_iterator iterator
Definition wm_int.hpp:70
void load(std::istream &in)
Loads the data structure from the given istream.
Definition wm_int.hpp:583
bool empty(node_type const &v) const
Indicates if node v is empty.
Definition wm_int.hpp:730
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
Definition wm_int.hpp:296
void _range_search_2d(node_type v, range_type r, value_type vlb, value_type vrb, size_type ilb, std::vector< size_type > &is, std::vector< size_type > &rank_off, point_vec_type &point_vec, bool report, size_type &cnt_answers) const
Definition wm_int.hpp:473
int_alphabet_tag alphabet_category
Definition wm_int.hpp:76
std::array< range_type, 2 > expand(node_type const &v, range_type const &r) const
Returns for a range its left and right child ranges.
Definition wm_int.hpp:839
t_rank rank_1_type
Definition wm_int.hpp:72
auto seq(node_type const &v) const -> random_access_container< std::function< value_type(size_type)> >
Random access container to sequence of node v.
Definition wm_int.hpp:710
std::array< range_vec_type, 2 > expand(node_type const &v, range_vec_type &&ranges) const
Returns for each range its left and right child ranges.
Definition wm_int.hpp:809
wm_int(wm_int const &wt)
Copy constructor.
Definition wm_int.hpp:203
t_bitvector bit_vector_type
Definition wm_int.hpp:71
auto size(node_type const &v) const -> decltype(v.size)
Return the size of node v.
Definition wm_int.hpp:736
std::pair< uint64_t, uint64_t > path(value_type c) const
return the path to the leaf for a given symbol
Definition wm_int.hpp:853
std::pair< size_type, value_type > inverse_select(size_type i) const
Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.
Definition wm_int.hpp:364
std::array< node_type, 2 > expand(node_type &&v) const
Returns the two child nodes of an inner node.
Definition wm_int.hpp:763
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition wm_int.hpp:613
rank_1_type m_tree_rank
Definition wm_int.hpp:92
size_type m_size
Definition wm_int.hpp:89
wt_tag index_category
Definition wm_int.hpp:75
std::pair< size_type, std::vector< std::pair< value_type, size_type > > > range_search_2d(size_type lb, size_type rb, value_type vlb, value_type vrb, bool report=true) const
range_search_2d searches points in the index interval [lb..rb] and value interval [vlb....
Definition wm_int.hpp:455
size_type size() const
Returns the size of the original vector.
Definition wm_int.hpp:279
wm_int & operator=(wm_int const &wt)
Assignment operator.
Definition wm_int.hpp:237
int_vector< 64 > m_rank_level
Definition wm_int.hpp:97
bool operator==(wm_int const &other) const noexcept
Equality operator.
Definition wm_int.hpp:630
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition wm_int.hpp:598
const_iterator begin() const
Returns a const_iterator to the first element.
Definition wm_int.hpp:553
bool empty() const
Returns whether the wavelet tree contains no data.
Definition wm_int.hpp:285
wm_int()=default
Default constructor.
int_vector< 64 > m_zero_cnt
Definition wm_int.hpp:96
size_type m_sigma
Definition wm_int.hpp:90
int_vector ::value_type value_type
Definition wm_int.hpp:67
bit_vector_type const & tree
A concatenation of all bit vectors of the wavelet tree.
Definition wm_int.hpp:101
std::vector< point_type > point_vec_type
Definition wm_int.hpp:83
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
Definition wm_int.hpp:565
bool is_leaf(node_type const &v) const
Checks if the node is a leaf node.
Definition wm_int.hpp:692
uint32_t const & max_level
Maximal level of the wavelet tree.
Definition wm_int.hpp:102
std::pair< value_type, size_type > point_type
Definition wm_int.hpp:82
random_access_const_iterator< wm_int > const_iterator
Definition wm_int.hpp:69
bool operator!=(wm_int const &other) const noexcept
Inequality operator.
Definition wm_int.hpp:639
t_select_zero select_0_type
Definition wm_int.hpp:74
node_type root() const
Return the root node.
Definition wm_int.hpp:742
t_select select_1_type
Definition wm_int.hpp:73
size_type rank(size_type i, value_type c) const
Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
Definition wm_int.hpp:328
value_type sym(node_type const &v) const
Symbol of leaf node v.
Definition wm_int.hpp:698
bit_vector_type m_tree
Definition wm_int.hpp:91
select_1_type m_tree_select1
Definition wm_int.hpp:93
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
Definition wm_int.hpp:399
select_0_type m_tree_select0
Definition wm_int.hpp:94
wm_int & operator=(wm_int &&wt)
Assignment move operator.
Definition wm_int.hpp:258
std::array< range_vec_type, 2 > expand(node_type const &v, range_vec_type const &ranges) const
Returns for each range its left and right child ranges.
Definition wm_int.hpp:793
int_vector ::size_type size_type
Definition wm_int.hpp:66
wm_int(t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
Construct the wavelet tree from a sequence defined by two interators.
Definition wm_int.hpp:117
auto bit_vec(node_type const &v) const -> node_bv_container< t_bitvector >
Random access container to bitvector of node v.
Definition wm_int.hpp:704
wm_int(wm_int &&wt)
Move copy constructor.
Definition wm_int.hpp:220
std::array< node_type, 2 > expand(node_type const &v) const
Returns the two child nodes of an inner node.
Definition wm_int.hpp:752
int_vector.hpp contains the sdsl::int_vector class.
int_vector_buffer.hpp contains the sdsl::int_vector_buffer class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
int remove(std::string const &)
Remove a file.
Definition ram_fs.hpp:221
std::string tmp_file(cache_config const &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
Definition io.hpp:759
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
Definition ram_fs.hpp:195
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
bool load_from_file(T &v, std::string const &file)
Load sdsl-object v from a file.
Definition io.hpp:989
void read_member(T &t, std::istream &in)
Definition io.hpp:119
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
std::array< int_vector<>::size_type, 2 > range_type
Definition wt_helper.hpp:27
bool empty(range_type const &r)
Empty range check.
int_vector ::size_type size(range_type const &r)
Size of a range.
std::vector< range_type > range_vec_type
Definition wt_helper.hpp:28
ram_fs.hpp
Contains declarations and definitions of data structure concepts.
sfstream.hpp contains a two stream class which can be used to read/write from/to files or strings.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
Represents a node in the wavelet tree.
Definition wm_int.hpp:646
node_type(node_type const &)=default
node_type & operator=(node_type const &)=default
bool operator>(node_type const &v) const
Definition wm_int.hpp:685
bool operator<(node_type const &v) const
Definition wm_int.hpp:679
node_type(node_type &&)=default
node_type & operator=(node_type &&)=default
node_type(size_type o=0, size_type sz=0, size_type l=0, value_type sy=0)
Definition wm_int.hpp:653
bool operator==(node_type const &v) const
Definition wm_int.hpp:673
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.