SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
wt_gmr.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_GMR
10#define INCLUDED_SDSL_WT_GMR
11
12#include <algorithm>
13#include <assert.h>
14#include <cstdint>
15#include <iosfwd>
16#include <iterator>
17#include <string>
18#include <type_traits>
19#include <utility>
20
21#include <sdsl/bits.hpp>
22#include <sdsl/cereal.hpp>
23#include <sdsl/int_vector.hpp>
25#include <sdsl/io.hpp>
26#include <sdsl/iterators.hpp>
27#include <sdsl/ram_fs.hpp>
30#include <sdsl/util.hpp>
31
33namespace sdsl
34{
35
37
50template <uint64_t t_s = 32,
51 class t_rac = int_vector<>,
52 class t_bv = bit_vector,
53 class t_rank = typename t_bv::rank_1_type>
55{
56public:
57 typedef t_rac iv_type;
58 typedef typename iv_type::size_type size_type;
59 typedef typename iv_type::value_type value_type;
60 typedef typename iv_type::difference_type difference_type;
61 typedef t_bv bit_vector_type;
62 typedef t_rank rank_type;
64
65private:
66 iv_type const * m_perm = nullptr; // pointer to supported permutation
67 uint64_t m_chunksize; // size of one permutation
68 int_vector<> m_back_pointer; // back pointers
69 bit_vector_type m_marked; // back pointer marking
70 rank_type m_marked_rank; // rank support for back pointer marking
71
72public:
75
77 inv_multi_perm_support(iv_type const * perm, int_vector<> & iv, uint64_t chunksize) :
78 m_perm(perm),
79 m_chunksize(chunksize)
80 {
81 bit_vector marked(iv.size(), 0);
82 bit_vector done(m_chunksize, 0);
83
84 size_type max_back_pointer = 0;
85 for (size_type i = 0, off = 0; i < iv.size(); ++i)
86 {
87 if (i == off + chunksize)
88 {
89 off = i;
90 util::set_to_value(done, 0);
91 }
92 if (!done[i - off])
93 {
94 done[i - off] = 1;
95 size_type back_pointer = i, j = i, j_new = 0;
96 uint64_t steps = 0, all_steps = 0;
97 while ((j_new = (iv[j] + off)) != i)
98 {
99 j = j_new;
100 done[j - off] = 1;
101 ++steps;
102 ++all_steps;
103 if (t_s == steps)
104 {
105 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
106 marked[j] = 1;
107 steps = 0;
108 back_pointer = j;
109 }
110 }
111 if (all_steps > t_s)
112 {
113 marked[i] = 1;
114 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
115 }
116 }
117 }
118
119 m_marked = t_bv(std::move(marked));
120 util::init_support(m_marked_rank, &m_marked);
121
122 util::set_to_value(done, 0);
123 size_type n_bp = m_marked_rank(iv.size());
124 m_back_pointer = int_vector<>(n_bp, 0, bits::hi(max_back_pointer) + 1);
125
126 for (size_type i = 0, off = 0; i < iv.size(); ++i)
127 {
128 if (i == off + chunksize)
129 {
130 off = i;
131 util::set_to_value(done, 0);
132 }
133 if (!done[i - off])
134 {
135 done[i - off] = 1;
136 size_type back_pointer = i, j = i, j_new = 0;
137 uint64_t steps = 0, all_steps = 0;
138 while ((j_new = (iv[j] + off)) != i)
139 {
140 j = j_new;
141 done[j - off] = 1;
142 ++steps;
143 ++all_steps;
144 if (t_s == steps)
145 {
146 m_back_pointer[m_marked_rank(j)] = back_pointer - off;
147 steps = 0;
148 back_pointer = j;
149 }
150 }
151 if (all_steps > t_s)
152 {
153 m_back_pointer[m_marked_rank(i)] = back_pointer - off;
154 }
155 }
156 }
157 }
158
161 m_perm(p.m_perm),
162 m_chunksize(p.m_chunksize),
163 m_back_pointer(p.m_back_pointer),
164 m_marked(p.m_marked),
165 m_marked_rank(p.m_marked_rank)
166 {
167 m_marked_rank.set_vector(&m_marked);
168 }
169
172 {
173 *this = std::move(p);
174 }
175
178 {
179 if (this != &p)
180 {
181 m_perm = p.m_perm;
182 m_chunksize = p.m_chunksize;
183 m_back_pointer = p.m_back_pointer;
184 m_marked = p.m_marked;
185 m_marked_rank = p.m_marked_rank;
186 m_marked_rank.set_vector(&m_marked);
187 }
188 return *this;
189 }
190
193 {
194 if (this != &p)
195 {
196 m_perm = std::move(p.m_perm);
197 m_chunksize = std::move(p.m_chunksize);
198 m_back_pointer = std::move(p.m_back_pointer);
199 m_marked = std::move(p.m_marked);
200 m_marked_rank = std::move(p.m_marked_rank);
201 m_marked_rank.set_vector(&m_marked);
202 }
203 return *this;
204 }
205
208 {
209 return nullptr == m_perm ? 0 : m_perm->size();
210 }
211
213 bool empty() const
214 {
215 return size() == 0;
216 }
217
219 /*
220 * \par Time complexity
221 * \f$ \Order{t_s} \f$
222 */
224 {
225 size_type off = (i / m_chunksize) * m_chunksize;
226 size_type j = i, j_new = 0;
227 while ((j_new = ((*m_perm)[j]) + off) != i)
228 {
229 if (m_marked[j])
230 {
231 j = m_back_pointer[m_marked_rank(j)] + off;
232 while ((j_new = ((*m_perm)[j]) + off) != i)
233 j = j_new;
234 }
235 else
236 {
237 j = j_new;
238 }
239 }
240 return j;
241 }
242
245 {
246 return const_iterator(this, 0);
247 }
248
251 {
252 return const_iterator(this, size());
253 }
254
255 void set_vector(iv_type const * v)
256 {
257 m_perm = v;
258 }
259
261 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
262 {
263 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
264 size_type written_bytes = 0;
265 written_bytes += write_member(m_chunksize, out, child, "chunksize");
266 written_bytes += m_back_pointer.serialize(out, child, "back_pointer");
267 written_bytes += m_marked.serialize(out, child, "marked");
268 written_bytes += m_marked_rank.serialize(out, child, "marked_rank");
269 structure_tree::add_size(child, written_bytes);
270 return written_bytes;
271 }
272
274 void load(std::istream & in, iv_type const * v = nullptr)
275 {
276 set_vector(v);
277 read_member(m_chunksize, in);
278 m_back_pointer.load(in);
279 m_marked.load(in);
280 m_marked_rank.load(in, &m_marked);
281 }
282
284 template <typename archive_t>
285 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
286 {
287 ar(CEREAL_NVP(m_chunksize));
288 ar(CEREAL_NVP(m_back_pointer));
289 ar(CEREAL_NVP(m_marked));
290 ar(CEREAL_NVP(m_marked_rank));
291 }
292
294 template <typename archive_t>
295 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
296 {
297 ar(CEREAL_NVP(m_chunksize));
298 ar(CEREAL_NVP(m_back_pointer));
299 ar(CEREAL_NVP(m_marked));
300 ar(CEREAL_NVP(m_marked_rank));
301 m_marked_rank.set_vector(&m_marked);
302 }
303
305 bool operator==(inv_multi_perm_support const & other) const noexcept
306 {
307 return (m_chunksize == other.m_chunksize) && (m_back_pointer == other.m_back_pointer)
308 && (m_marked == other.m_marked) && (m_marked_rank == other.m_marked_rank);
309 }
310
312 bool operator!=(inv_multi_perm_support const & other) const noexcept
313 {
314 return !(*this == other);
315 }
316};
317
318template <class t_rac>
320 typename std::enable_if<!(std::is_same<t_rac, int_vector<>>::value), t_rac>::type & rac,
321 const std::string filename)
322{
323 std::string tmp_file_name = tmp_file(filename, "_compress_int_vector");
324 store_to_file(iv, tmp_file_name);
325 util::clear(iv);
326 int_vector_buffer<> buf(tmp_file_name, std::ios::in, 1024 * 1024, iv.width());
327 rac = t_rac(buf);
328 buf.close(true); // delete tmp_file
329}
330
331template <class t_rac>
333 typename std::enable_if<std::is_same<t_rac, int_vector<>>::value, t_rac>::type & rac,
334 const std::string)
335{
336 rac = std::move(iv);
337}
338
340
356template <class t_rac = int_vector<>,
357 class t_bitvector = bit_vector,
358 class t_select = typename t_bitvector::select_1_type,
359 class t_select_zero = typename t_bitvector::select_0_type>
361{
362public:
365 typedef typename t_bitvector::difference_type difference_type;
370 enum
371 {
372 lex_ordered = 0
373 };
374
375private:
376 t_bitvector m_bv_blocks;
377 t_rac m_e;
378 t_select m_bv_blocks_select1;
379 t_select_zero m_bv_blocks_select0;
380 uint64_t m_size; // input length
381 uint64_t m_block_size = 0; // size of the blocks
382 uint64_t m_blocks; // blocks per character
383 uint64_t m_sigma = 0;
384
385public:
386 size_type const & sigma = m_sigma;
387
389 wt_gmr_rs() = default;
390
392
400 template <typename t_it>
401 wt_gmr_rs(t_it begin, t_it end, std::string tmp_dir = ram_file_name("")) : m_size(std::distance(begin, end))
402 {
403 // Determine max. symbol
404 for (auto it = begin; it != end; ++it)
405 {
406 value_type value = *it;
407 if (m_block_size < value)
408 m_block_size = value;
409 }
410 ++m_block_size;
411
412 // Create and fill m_bv_blocks
413 m_blocks = (m_size + m_block_size - 1) / m_block_size;
414 bit_vector b(m_size + m_block_size * m_blocks + 1, 0);
415 int_vector<> symbols(m_block_size, 0, bits::hi(m_size) + 1);
416 {
417 int_vector<> tmp(m_block_size * m_blocks, 0, bits::hi(m_block_size) + 1);
418 uint64_t j = 0, offset = 0;
419 for (auto it = begin; it != end; ++it, ++j)
420 {
421 if (j == m_block_size)
422 {
423 ++offset;
424 j = 0;
425 }
426 ++tmp[(*it) * m_blocks + offset];
427 }
428
429 for (uint64_t i = 0; i < symbols.size(); ++i)
430 {
431 for (uint64_t j = m_blocks * i; j < (i + 1) * m_blocks; ++j)
432 {
433 symbols[i] += tmp[j];
434 }
435 }
436
437 for (uint64_t i = 0, l = 1; i < tmp.size(); ++i, ++l)
438 {
439 for (uint64_t j = 0; j < tmp[i]; ++j)
440 b[l++] = 1;
441 }
442
443 // calc m_sigma
444 bool write = true;
445 uint64_t blocks = 0;
446 for (uint64_t i = 1; i < b.size(); ++i)
447 {
448 if (blocks == m_blocks)
449 {
450 blocks = 0;
451 write = true;
452 }
453 if (b[i])
454 {
455 if (write)
456 {
457 ++m_sigma;
458 write = false;
459 }
460 }
461 else
462 ++blocks;
463 }
464
465 m_bv_blocks = t_bitvector(std::move(b));
466 }
467
468 // Create and fill e
469 int_vector<> positions(m_size, 0, bits::hi(m_block_size) + 1);
470 for (uint64_t i = 0, tmp = 0, sum = 0; i < m_block_size; ++i)
471 {
472 tmp = symbols[i];
473 symbols[i] = sum;
474 sum += tmp;
475 }
476 for (auto it = begin; it != end;)
477 {
478 for (uint64_t j = 0; j < m_block_size and it != end; ++it, ++j)
479 {
480 positions[symbols[*it]++] = j;
481 }
482 }
483 _transform_to_compressed<t_rac>(positions, m_e, tmp_dir);
484
485 util::init_support(m_bv_blocks_select0, &m_bv_blocks);
486 util::init_support(m_bv_blocks_select1, &m_bv_blocks);
487 }
488
490 wt_gmr_rs(wt_gmr_rs const & wt) :
491 m_bv_blocks(wt.m_bv_blocks),
492 m_e(wt.m_e),
493 m_bv_blocks_select1(wt.m_bv_blocks_select1),
494 m_bv_blocks_select0(wt.m_bv_blocks_select0),
495 m_size(wt.m_size),
496 m_block_size(wt.m_block_size),
497 m_blocks(wt.m_blocks),
498 m_sigma(wt.m_sigma)
499 {
500 m_bv_blocks_select1.set_vector(&m_bv_blocks);
501 m_bv_blocks_select0.set_vector(&m_bv_blocks);
502 }
503
506 m_bv_blocks(std::move(wt.m_bv_blocks)),
507 m_e(std::move(wt.m_e)),
508 m_bv_blocks_select1(std::move(wt.m_bv_blocks_select1)),
509 m_bv_blocks_select0(std::move(wt.m_bv_blocks_select0)),
510 m_size(wt.m_size),
511 m_block_size(wt.m_block_size),
512 m_blocks(wt.m_blocks),
513 m_sigma(wt.m_sigma)
514 {
515 m_bv_blocks_select1.set_vector(&m_bv_blocks);
516 m_bv_blocks_select0.set_vector(&m_bv_blocks);
517 }
518
521 {
522 wt_gmr_rs tmp(wt);
523 *this = std::move(tmp);
524 return *this;
525 }
526
529 {
530 m_bv_blocks = std::move(wt.m_bv_blocks);
531 m_e = std::move(wt.m_e);
532 m_bv_blocks_select1 = std::move(wt.m_bv_blocks_select1);
533 m_bv_blocks_select1.set_vector(&m_bv_blocks);
534 m_bv_blocks_select0 = std::move(wt.m_bv_blocks_select0);
535 m_bv_blocks_select0.set_vector(&m_bv_blocks);
536 m_size = wt.m_size;
537 m_block_size = wt.m_block_size;
538 m_blocks = wt.m_blocks;
539 m_sigma = wt.m_sigma;
540 return *this;
541 }
542
545 {
546 return m_size;
547 }
548
550 bool empty() const
551 {
552 return m_size == 0;
553 }
554
556
564 {
565 assert(i < m_size);
566 size_type block = i / m_block_size + 1, val = i % m_block_size, search_begin, search_end, j;
567 while (true)
568 {
569 j = m_bv_blocks_select0(block) + 1;
570 search_begin = j - block;
571 if (m_bv_blocks[j])
572 {
573 search_end = m_bv_blocks_select0(block + 1) - (block);
574 if (search_end - search_begin < 50)
575 { // After a short test, this seems to be a good threshold
576 while (search_begin < search_end and m_e[search_begin] <= val)
577 {
578 if (m_e[search_begin] == val)
579 {
580 return (block - 1) / m_blocks;
581 }
582 ++search_begin;
583 }
584 }
585 else
586 {
587 if (std::binary_search(m_e.begin() + search_begin, m_e.begin() + search_end, val))
588 {
589 return (block - 1) / m_blocks;
590 }
591 }
592 }
593 block += m_blocks;
594 }
595 }
596
598
608 {
609 if (0 == i or c > m_block_size - 1)
610 {
611 return 0;
612 }
613
614 size_type offset = 0;
615 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - c * m_blocks;
616
617 auto begin = m_e.begin() + m_bv_blocks_select0(c * m_blocks + (i - 1) / m_block_size + 1)
618 - (c * m_blocks + (i - 1) / m_block_size + 1) + 1;
619 auto end = m_e.begin() + m_bv_blocks_select0(c * m_blocks + (i - 1) / m_block_size + 2)
620 - (c * m_blocks + (i - 1) / m_block_size + 1);
621
622 size_type val = (i - 1) % m_block_size;
623 if (end - begin < 50)
624 { // After a short test, this seems to be a good threshold
625 offset = std::find_if(begin,
626 end,
627 [&val](auto const && x)
628 {
629 return x > val;
630 })
631 - begin;
632 }
633 else
634 {
635 offset = std::lower_bound(begin, end, val + 1) - begin;
636 }
637 return (begin - m_e.begin()) + offset - ones_before_cblock;
638 }
639
641
650 std::pair<size_type, value_type> inverse_select(size_type i) const
651 {
652 assert(i < m_size);
653 size_type block = i / m_block_size + 1, val = i % m_block_size, offset = 0, search_begin, search_end, j;
654 while (true)
655 {
656 j = m_bv_blocks_select0(block) + 1;
657 search_begin = j - block;
658 if (m_bv_blocks[j])
659 {
660 search_end = m_bv_blocks_select0(block + 1) - (block);
661 offset = 0;
662 if (search_end - search_begin < 50)
663 { // After a short test, this seems to be a good threshold
664 while (search_begin < search_end and m_e[search_begin] <= val)
665 {
666 if (m_e[search_begin] == val)
667 {
668 value_type c = (block - 1) / m_blocks;
669 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks);
670 size_type r = search_begin - ones_before_cblock;
671 return std::make_pair(r, c);
672 }
673 ++search_begin;
674 }
675 }
676 else
677 {
678 offset = std::lower_bound(m_e.begin() + search_begin, m_e.begin() + search_end, val) - m_e.begin();
679 if (offset < search_end)
680 {
681 if (m_e[offset] == val)
682 {
683 value_type c = (block - 1) / m_blocks;
684 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks);
685 size_type r = offset - ones_before_cblock;
686 return std::make_pair(r, c);
687 }
688 }
689 }
690 }
691 block += m_blocks;
692 }
693 }
694
696
705 {
706 size_type k = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks) + i;
707 return (m_bv_blocks_select1(k) - k) * m_block_size + m_e[k - 1] - c * m_blocks * m_block_size;
708 }
709
711 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
712 {
713 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
714 size_type written_bytes = 0;
715 written_bytes += write_member(m_size, out, child, "size");
716 written_bytes += write_member(m_block_size, out, child, "block_size");
717 written_bytes += write_member(m_blocks, out, child, "blocks");
718 written_bytes += write_member(m_sigma, out, child, "sigma");
719 written_bytes += m_e.serialize(out, child, "E");
720 written_bytes += m_bv_blocks.serialize(out, child, "bv_blocks");
721 written_bytes += m_bv_blocks_select0.serialize(out, child, "bv_blocks_select0");
722 written_bytes += m_bv_blocks_select1.serialize(out, child, "bv_blocks_select1");
723 structure_tree::add_size(child, written_bytes);
724 return written_bytes;
725 }
726
728 void load(std::istream & in)
729 {
730 read_member(m_size, in);
731 read_member(m_block_size, in);
732 read_member(m_blocks, in);
733 read_member(m_sigma, in);
734 m_e.load(in);
735 m_bv_blocks.load(in);
736 m_bv_blocks_select0.load(in, &m_bv_blocks);
737 m_bv_blocks_select1.load(in, &m_bv_blocks);
738 }
739
741 template <typename archive_t>
742 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
743 {
744 ar(CEREAL_NVP(m_size));
745 ar(CEREAL_NVP(m_block_size));
746 ar(CEREAL_NVP(m_blocks));
747 ar(CEREAL_NVP(m_sigma));
748 ar(CEREAL_NVP(m_e));
749 ar(CEREAL_NVP(m_bv_blocks));
750 ar(CEREAL_NVP(m_bv_blocks_select0));
751 ar(CEREAL_NVP(m_bv_blocks_select1));
752 }
753
755 template <typename archive_t>
756 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
757 {
758 ar(CEREAL_NVP(m_size));
759 ar(CEREAL_NVP(m_block_size));
760 ar(CEREAL_NVP(m_blocks));
761 ar(CEREAL_NVP(m_sigma));
762 ar(CEREAL_NVP(m_e));
763 ar(CEREAL_NVP(m_bv_blocks));
764 ar(CEREAL_NVP(m_bv_blocks_select0));
765 m_bv_blocks_select0.set_vector(&m_bv_blocks);
766 ar(CEREAL_NVP(m_bv_blocks_select1));
767 m_bv_blocks_select1.set_vector(&m_bv_blocks);
768 }
769
771 {
772 return {this, 0};
773 };
775 {
776 return {this, size()};
777 };
779 {
780 return {this, 0};
781 };
783 {
784 return {this, size()};
785 };
786
788 bool operator==(wt_gmr_rs const & other) const noexcept
789 {
790 return (m_size == other.m_size) && (m_block_size == other.m_block_size) && (m_blocks == other.m_blocks)
791 && (m_sigma == other.m_sigma) && (m_e == other.m_e) && (m_bv_blocks == other.m_bv_blocks)
792 && (m_bv_blocks_select0 == other.m_bv_blocks_select0) && (m_bv_blocks_select1 == other.m_bv_blocks_select1);
793 }
794
796 bool operator!=(wt_gmr_rs const & other) const noexcept
797 {
798 return !(*this == other);
799 }
800};
801
803
820template <class t_rac = int_vector<>,
821 class t_inverse_support = inv_multi_perm_support<32, t_rac>,
822 class t_bitvector = bit_vector,
823 class t_select = typename t_bitvector::select_1_type,
824 class t_select_zero = typename t_bitvector::select_0_type>
826{
827public:
828 typedef typename t_rac::size_type size_type;
829 typedef typename t_rac::value_type value_type;
830 typedef typename t_bitvector::difference_type difference_type;
835 enum
836 {
837 lex_ordered = 0
838 };
839
840private:
841 t_bitvector m_bv_blocks; // 0 indicates end of block. Corresponds to B in the paper.
842 t_bitvector m_bv_chunks; // 0 indicates end of symbol in chunk. Corresponds to X in the paper.
843
844 t_rac m_perm; // Contains permutation of each chunk. Corresponds to \f$ \pi \f$ in the paper.
845 t_inverse_support m_ips; // Support for inverse permutation
846
847 t_select m_bv_blocks_select1, m_bv_chunks_select1;
848 t_select_zero m_bv_blocks_select0, m_bv_chunks_select0;
849
850 uint64_t m_size; // input length
851 uint64_t m_max_symbol = 0; // maximum character + 1
852 uint64_t m_chunks; // number of chunks
853 uint64_t m_chunksize;
854 uint64_t m_sigma = 0;
855
856public:
857 size_type const & sigma = m_sigma;
858
860 wt_gmr() = default;
861
863
871 template <typename t_it>
872 wt_gmr(t_it begin, t_it end, std::string tmp_dir = ram_file_name("")) : m_size(std::distance(begin, end))
873 {
874 // Determine max. symbol
875 for (auto it = begin; it != end; ++it)
876 {
877 value_type value = *it;
878 if (m_max_symbol < value)
879 m_max_symbol = value;
880 }
881 ++m_max_symbol;
882 m_chunksize = (1ULL << (bits::hi(m_max_symbol - 1) + 1)); // In some cases this is better than m_max_smbol
883 m_chunks = (m_size + m_chunksize - 1) / m_chunksize;
884
885 // calc m_bv_blocks
886 {
887 bit_vector b(m_size + m_max_symbol * m_chunks + 1, 0);
888 int_vector<> tmp(m_max_symbol * m_chunks, 0, bits::hi(m_max_symbol - 1) + 2);
889
890 uint64_t offset = 0, j = 0;
891 for (auto it = begin; it != end; ++it, ++j)
892 {
893 if (j == m_chunksize)
894 {
895 ++offset;
896 j = 0;
897 }
898 ++tmp[(*it) * m_chunks + offset];
899 }
900
901 for (uint64_t i = 0, l = 1; i < tmp.size(); ++i, ++l)
902 for (uint64_t j = 0; j < tmp[i]; ++j)
903 b[l++] = 1;
904
905 // calc m_sigma
906 bool write = true;
907 uint64_t blocks = 0;
908 for (uint64_t i = 1; i < b.size(); ++i)
909 {
910 if (blocks == m_chunks)
911 {
912 blocks = 0;
913 write = true;
914 }
915 if (b[i])
916 {
917 if (write)
918 {
919 ++m_sigma;
920 write = false;
921 }
922 }
923 else
924 ++blocks;
925 }
926
927 m_bv_blocks = t_bitvector(std::move(b));
928 }
929
930 // Calc perm and bv_chunks
931 {
932 uint64_t x_pos = 0;
933 bit_vector x(m_size + m_chunks * m_max_symbol + 1, 0);
934
935 // fill perm and m_bv_chunks for every chunk
936 int_vector<> perm(m_size, 0, bits::hi(m_max_symbol - 1) + 1);
937 for (uint64_t i = 0; i < m_chunks; ++i)
938 {
939 int_vector<> symbols(m_max_symbol, 0, bits::hi(m_max_symbol - 1) + 2);
940
941 // calc symbols
942 for (uint64_t j = i * m_chunksize; j < (i + 1) * m_chunksize and j < m_size; ++j)
943 {
944 ++symbols[*(begin + j)];
945 }
946 // calc m_bv_chunks
947 for (uint64_t j = 0; j < m_max_symbol; ++j, ++x_pos)
948 for (uint64_t k = 0; k < symbols[j]; ++k)
949 x[++x_pos] = 1;
950
951 // calc symbols prefix sum
952 for (uint64_t j = 0, tmp = 0, sum = 0; j < m_max_symbol; ++j)
953 {
954 tmp = symbols[j];
955 symbols[j] = sum;
956 sum += tmp;
957 }
958 // calc perm
959 for (uint64_t j = i * m_chunksize, k = 0; j < (i + 1) * m_chunksize and j < m_size; ++j, ++k)
960 {
961 perm[i * m_chunksize + (symbols[*(begin + j)]++)] = k;
962 }
963 }
964 m_bv_chunks = t_bitvector(std::move(x));
965 m_ips = t_inverse_support(&m_perm, perm, m_chunksize);
966 _transform_to_compressed<t_rac>(perm, m_perm, tmp_dir);
967 m_ips.set_vector(&m_perm);
968 }
969 util::init_support(m_bv_chunks_select1, &m_bv_chunks);
970 util::init_support(m_bv_chunks_select0, &m_bv_chunks);
971 util::init_support(m_bv_blocks_select1, &m_bv_blocks);
972 util::init_support(m_bv_blocks_select0, &m_bv_blocks);
973 }
974
976 wt_gmr(wt_gmr const & wt) :
977 m_bv_blocks(wt.m_bv_blocks),
978 m_bv_chunks(wt.m_bv_chunks),
979 m_perm(wt.m_perm),
980 m_ips(wt.m_ips),
981 m_bv_blocks_select1(wt.m_bv_blocks_select1),
982 m_bv_chunks_select1(wt.m_bv_chunks_select1),
983 m_bv_blocks_select0(wt.m_bv_blocks_select0),
984 m_bv_chunks_select0(wt.m_bv_chunks_select0),
985 m_size(wt.m_size),
986 m_max_symbol(wt.m_max_symbol),
987 m_chunks(wt.m_chunks),
988 m_chunksize(wt.m_chunksize),
989 m_sigma(wt.m_sigma)
990 {
991 m_ips.set_vector(&m_perm);
992 m_bv_blocks_select1.set_vector(&m_bv_blocks);
993 m_bv_chunks_select1.set_vector(&m_bv_chunks);
994 m_bv_blocks_select0.set_vector(&m_bv_blocks);
995 m_bv_chunks_select0.set_vector(&m_bv_chunks);
996 }
997
999 wt_gmr(wt_gmr && wt) :
1000 m_bv_blocks(std::move(wt.m_bv_blocks)),
1001 m_bv_chunks(std::move(wt.m_bv_chunks)),
1002 m_perm(std::move(wt.m_perm)),
1003 m_ips(std::move(wt.m_ips)),
1004 m_bv_blocks_select1(std::move(wt.m_bv_blocks_select1)),
1005 m_bv_chunks_select1(std::move(wt.m_bv_chunks_select1)),
1006 m_bv_blocks_select0(std::move(wt.m_bv_blocks_select0)),
1007 m_bv_chunks_select0(std::move(wt.m_bv_chunks_select0)),
1008 m_size(wt.m_size),
1009 m_max_symbol(wt.m_max_symbol),
1010 m_chunks(wt.m_chunks),
1011 m_chunksize(wt.m_chunksize),
1012 m_sigma(wt.m_sigma)
1013 {
1014 m_ips.set_vector(&m_perm);
1015 m_bv_blocks_select1.set_vector(&m_bv_blocks);
1016 m_bv_chunks_select1.set_vector(&m_bv_chunks);
1017 m_bv_blocks_select0.set_vector(&m_bv_blocks);
1018 m_bv_chunks_select0.set_vector(&m_bv_chunks);
1019 }
1020
1023 {
1024 wt_gmr tmp(wt);
1025 *this = std::move(tmp);
1026 return *this;
1027 }
1028
1031 {
1032 m_bv_blocks = std::move(wt.m_bv_blocks);
1033 m_bv_chunks = std::move(wt.m_bv_chunks);
1034 m_perm = std::move(wt.m_perm);
1035 m_ips = std::move(wt.m_ips);
1036 m_ips.set_vector(&m_perm);
1037 m_bv_blocks_select1 = std::move(wt.m_bv_blocks_select1);
1038 m_bv_blocks_select1.set_vector(&m_bv_blocks);
1039 m_bv_chunks_select1 = std::move(wt.m_bv_chunks_select1);
1040 m_bv_chunks_select1.set_vector(&m_bv_chunks);
1041 m_bv_blocks_select0 = std::move(wt.m_bv_blocks_select0);
1042 m_bv_blocks_select0.set_vector(&m_bv_blocks);
1043 m_bv_chunks_select0 = std::move(wt.m_bv_chunks_select0);
1044 m_bv_chunks_select0.set_vector(&m_bv_chunks);
1045 m_size = wt.m_size;
1046 m_max_symbol = wt.m_max_symbol;
1047 m_chunks = wt.m_chunks;
1048 m_chunksize = wt.m_chunksize;
1049 m_sigma = wt.m_sigma;
1050 return *this;
1051 }
1052
1055 {
1056 return m_size;
1057 }
1058
1060 bool empty() const
1061 {
1062 return m_size == 0;
1063 }
1064
1066
1074 {
1075 assert(i < size());
1076 uint64_t chunk = i / m_chunksize;
1077 uint64_t x = m_ips[i];
1078 return m_bv_chunks_select1(x + 1) - x - (chunk * m_max_symbol) - 1;
1079 }
1080
1082
1092 {
1093 assert(i <= size());
1094
1095 if (0 == i or c > m_max_symbol - 1)
1096 {
1097 return 0;
1098 }
1099
1100 uint64_t chunk = (i - 1) / m_chunksize;
1101 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks + 1) + 1;
1102 uint64_t c_ones_before_chunk =
1103 m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk + 1) + 1 - ones_before_c;
1104
1105 uint64_t c_ones_in_chunk = 0;
1106 auto begin =
1107 m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 1 + c) - (chunk * m_max_symbol + 1 + c) + 1;
1108 auto end =
1109 m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 2 + c) - (chunk * m_max_symbol + 2 + c) + 1;
1110
1111 size_type val = (i - 1) % m_chunksize;
1112 if (end - begin < 50)
1113 { // After a short test, this seems to be a good threshold
1114 c_ones_in_chunk = std::find_if(begin,
1115 end,
1116 [&val](auto const && x)
1117 {
1118 return x > val;
1119 })
1120 - begin;
1121 }
1122 else
1123 {
1124 c_ones_in_chunk = std::lower_bound(begin, end, val + 1) - begin;
1125 }
1126 return c_ones_before_chunk + c_ones_in_chunk;
1127 }
1128
1130
1138 std::pair<size_type, value_type> inverse_select(size_type i) const
1139 {
1140 assert(i < size());
1141 uint64_t chunk = i / m_chunksize;
1142 uint64_t x = m_ips[i];
1143 uint64_t tmp = m_bv_chunks_select1(x + 1);
1144 uint64_t c = tmp - x - (chunk * m_max_symbol) - 1;
1145
1146 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks + 1) + 1;
1147 uint64_t c_before_chunk =
1148 m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk + 1) + 1 - ones_before_c;
1149 uint64_t c_in_chunk = tmp - m_bv_chunks_select0(c + 1 + chunk * m_max_symbol) - 1;
1150 return std::make_pair(c_before_chunk + c_in_chunk, c);
1151 }
1152
1154
1163 {
1164 assert(1 <= i and i <= rank(size(), c));
1165
1166 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks);
1167 uint64_t chunk = m_bv_blocks_select1(ones_before_c + i) - ones_before_c - (c * m_chunks + 1) - i + 1;
1168 uint64_t c_ones_before_chunk =
1169 m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk) - ones_before_c;
1170 uint64_t pi_pos = m_bv_chunks_select0(chunk * m_max_symbol + c + 1) + (i - c_ones_before_chunk)
1171 - chunk * m_max_symbol - c - 1;
1172
1173 return m_perm[pi_pos] + chunk * m_chunksize;
1174 }
1175
1177 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
1178 {
1179 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1180 size_type written_bytes = 0;
1181 written_bytes += write_member(m_size, out, child, "size");
1182 written_bytes += write_member(m_max_symbol, out, child, "max_symbol");
1183 written_bytes += write_member(m_chunks, out, child, "chunks");
1184 written_bytes += write_member(m_chunksize, out, child, "chunksize");
1185 written_bytes += write_member(m_sigma, out, child, "sigma");
1186 written_bytes += m_bv_blocks.serialize(out, child, "bv_blocks");
1187 written_bytes += m_bv_blocks_select0.serialize(out, child, "bv_blocks_select0");
1188 written_bytes += m_bv_blocks_select1.serialize(out, child, "bv_blocks_select1");
1189 written_bytes += m_bv_chunks.serialize(out, child, "bv_chunks");
1190 written_bytes += m_bv_chunks_select0.serialize(out, child, "bv_chunks_select0");
1191 written_bytes += m_bv_chunks_select1.serialize(out, child, "bv_chunks_select1");
1192 written_bytes += m_perm.serialize(out, child, "permutation");
1193 written_bytes += m_ips.serialize(out, child, "inverse_permutation_support");
1194 structure_tree::add_size(child, written_bytes);
1195 return written_bytes;
1196 }
1197
1199 void load(std::istream & in)
1200 {
1201 read_member(m_size, in);
1202 read_member(m_max_symbol, in);
1203 read_member(m_chunks, in);
1204 read_member(m_chunksize, in);
1205 read_member(m_sigma, in);
1206 m_bv_blocks.load(in);
1207 m_bv_blocks_select0.load(in, &m_bv_blocks);
1208 m_bv_blocks_select1.load(in, &m_bv_blocks);
1209 m_bv_chunks.load(in);
1210 m_bv_chunks_select0.load(in, &m_bv_chunks);
1211 m_bv_chunks_select1.load(in, &m_bv_chunks);
1212 m_perm.load(in);
1213 m_ips.load(in, &m_perm);
1214 }
1215
1217 template <typename archive_t>
1218 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
1219 {
1220 ar(CEREAL_NVP(m_size));
1221 ar(CEREAL_NVP(m_max_symbol));
1222 ar(CEREAL_NVP(m_chunks));
1223 ar(CEREAL_NVP(m_chunksize));
1224 ar(CEREAL_NVP(m_sigma));
1225 ar(CEREAL_NVP(m_bv_blocks));
1226 ar(CEREAL_NVP(m_bv_blocks_select0));
1227 ar(CEREAL_NVP(m_bv_blocks_select1));
1228 ar(CEREAL_NVP(m_bv_chunks));
1229 ar(CEREAL_NVP(m_bv_chunks_select0));
1230 ar(CEREAL_NVP(m_bv_chunks_select1));
1231 ar(CEREAL_NVP(m_perm));
1232 ar(CEREAL_NVP(m_ips));
1233 }
1234
1236 template <typename archive_t>
1237 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
1238 {
1239 ar(CEREAL_NVP(m_size));
1240 ar(CEREAL_NVP(m_max_symbol));
1241 ar(CEREAL_NVP(m_chunks));
1242 ar(CEREAL_NVP(m_chunksize));
1243 ar(CEREAL_NVP(m_sigma));
1244 ar(CEREAL_NVP(m_bv_blocks));
1245 ar(CEREAL_NVP(m_bv_blocks_select0));
1246 m_bv_blocks_select0.set_vector(&m_bv_blocks);
1247 ar(CEREAL_NVP(m_bv_blocks_select1));
1248 m_bv_blocks_select1.set_vector(&m_bv_blocks);
1249 ar(CEREAL_NVP(m_bv_chunks));
1250 ar(CEREAL_NVP(m_bv_chunks_select0));
1251 m_bv_chunks_select0.set_vector(&m_bv_chunks);
1252 ar(CEREAL_NVP(m_bv_chunks_select1));
1253 m_bv_chunks_select1.set_vector(&m_bv_chunks);
1254 ar(CEREAL_NVP(m_perm));
1255 ar(CEREAL_NVP(m_ips));
1256 m_ips.set_vector(&m_perm);
1257 }
1258
1260 {
1261 return {this, 0};
1262 };
1264 {
1265 return {this, size()};
1266 };
1268 {
1269 return {this, 0};
1270 };
1272 {
1273 return {this, size()};
1274 };
1275
1277 bool operator==(wt_gmr const & other) const noexcept
1278 {
1279 return (m_size == other.m_size) && (m_max_symbol == other.m_max_symbol) && (m_chunks == other.m_chunks)
1280 && (m_chunksize == other.m_chunksize) && (m_sigma == other.m_sigma) && (m_bv_blocks == other.m_bv_blocks)
1281 && (m_bv_blocks_select0 == other.m_bv_blocks_select0) && (m_bv_blocks_select1 == other.m_bv_blocks_select1)
1282 && (m_bv_chunks == other.m_bv_chunks) && (m_bv_chunks_select0 == other.m_bv_chunks_select0)
1283 && (m_bv_chunks_select1 == other.m_bv_chunks_select1) && (m_perm == other.m_perm) && (m_ips == other.m_ips);
1284 }
1285
1287 bool operator!=(wt_gmr const & other) const noexcept
1288 {
1289 return !(*this == other);
1290 }
1291};
1292} // namespace sdsl
1293
1294#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
void close(bool remove_file=false)
Close the int_vector_buffer.
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
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.
Class inv_multi_perm_support adds access to the inverse of permutations.
Definition wt_gmr.hpp:55
inv_multi_perm_support(inv_multi_perm_support const &p)
Copy constructor.
Definition wt_gmr.hpp:160
bool operator==(inv_multi_perm_support const &other) const noexcept
Equality operator.
Definition wt_gmr.hpp:305
inv_multi_perm_support & operator=(inv_multi_perm_support const &p)
Assignment operation.
Definition wt_gmr.hpp:177
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition wt_gmr.hpp:285
iv_type::size_type size_type
Definition wt_gmr.hpp:58
inv_multi_perm_support(iv_type const *perm, int_vector<> &iv, uint64_t chunksize)
Constructor.
Definition wt_gmr.hpp:77
inv_multi_perm_support & operator=(inv_multi_perm_support &&p)
Assignment move operation.
Definition wt_gmr.hpp:192
void load(std::istream &in, iv_type const *v=nullptr)
Load sampling from disk.
Definition wt_gmr.hpp:274
const_iterator begin() const
Returns a const_iterator to the first element.
Definition wt_gmr.hpp:244
bool operator!=(inv_multi_perm_support const &other) const noexcept
Inequality operator.
Definition wt_gmr.hpp:312
random_access_const_iterator< inv_multi_perm_support > const_iterator
Definition wt_gmr.hpp:63
value_type operator[](size_type i) const
Access operator.
Definition wt_gmr.hpp:223
inv_multi_perm_support()
Default constructor.
Definition wt_gmr.hpp:74
bool empty() const
Returns whether the original vector contains no data.
Definition wt_gmr.hpp:213
iv_type::value_type value_type
Definition wt_gmr.hpp:59
inv_multi_perm_support(inv_multi_perm_support &&p)
Move constructor.
Definition wt_gmr.hpp:171
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize into stream.
Definition wt_gmr.hpp:261
size_type size() const
Returns the size of the original vector.
Definition wt_gmr.hpp:207
void set_vector(iv_type const *v)
Definition wt_gmr.hpp:255
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition wt_gmr.hpp:250
iv_type::difference_type difference_type
Definition wt_gmr.hpp:60
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition wt_gmr.hpp:295
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 wt_gmr.hpp:361
wt_tag index_category
Definition wt_gmr.hpp:368
t_bitvector::difference_type difference_type
Definition wt_gmr.hpp:365
const_iterator end() const
Definition wt_gmr.hpp:782
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
Definition wt_gmr.hpp:704
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition wt_gmr.hpp:756
wt_gmr_rs(wt_gmr_rs &&wt)
Move copy constructor.
Definition wt_gmr.hpp:505
wt_gmr_rs()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition wt_gmr.hpp:742
random_access_const_iterator< wt_gmr_rs > const_iterator
Definition wt_gmr.hpp:366
const_iterator iterator
Definition wt_gmr.hpp:367
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 wt_gmr.hpp:607
bool empty() const
Returns whether the wavelet tree contains no data.
Definition wt_gmr.hpp:550
int_vector ::value_type value_type
Definition wt_gmr.hpp:364
void load(std::istream &in)
Loads the data structure from the given istream.
Definition wt_gmr.hpp:728
std::pair< size_type, value_type > inverse_select(size_type i) const
Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
Definition wt_gmr.hpp:650
size_type const & sigma
Definition wt_gmr.hpp:386
const_iterator end()
Definition wt_gmr.hpp:774
size_type size() const
Returns the size of the original vector.
Definition wt_gmr.hpp:544
bool operator==(wt_gmr_rs const &other) const noexcept
Equality operator.
Definition wt_gmr.hpp:788
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
Definition wt_gmr.hpp:563
iterator begin()
Definition wt_gmr.hpp:770
wt_gmr_rs(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 wt_gmr.hpp:401
wt_gmr_rs & operator=(wt_gmr_rs &&wt)
Move assignment operator.
Definition wt_gmr.hpp:528
wt_gmr_rs & operator=(wt_gmr_rs const &wt)
Assignment operator.
Definition wt_gmr.hpp:520
bool operator!=(wt_gmr_rs const &other) const noexcept
Inequality operator.
Definition wt_gmr.hpp:796
int_alphabet_tag alphabet_category
Definition wt_gmr.hpp:369
wt_gmr_rs(wt_gmr_rs const &wt)
Copy constructor.
Definition wt_gmr.hpp:490
iterator begin() const
Definition wt_gmr.hpp:778
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
Definition wt_gmr.hpp:711
int_vector ::size_type size_type
Definition wt_gmr.hpp:363
A wavelet tree class for integer sequences.
Definition wt_gmr.hpp:826
bool operator!=(wt_gmr const &other) const noexcept
Inequality operator.
Definition wt_gmr.hpp:1287
const_iterator end()
Definition wt_gmr.hpp:1263
bool empty() const
Returns whether the wavelet tree contains no data.
Definition wt_gmr.hpp:1060
wt_gmr()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition wt_gmr.hpp:1218
const_iterator iterator
Definition wt_gmr.hpp:832
t_bitvector::difference_type difference_type
Definition wt_gmr.hpp:830
bool operator==(wt_gmr const &other) const noexcept
Equality operator.
Definition wt_gmr.hpp:1277
wt_gmr(wt_gmr const &wt)
Copy constructor.
Definition wt_gmr.hpp:976
wt_gmr & operator=(wt_gmr const &wt)
Assignment operator.
Definition wt_gmr.hpp:1022
void load(std::istream &in)
Loads the data structure from the given istream.
Definition wt_gmr.hpp:1199
wt_gmr(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 wt_gmr.hpp:872
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
Definition wt_gmr.hpp:1162
wt_gmr(wt_gmr &&wt)
Move constructor.
Definition wt_gmr.hpp:999
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition wt_gmr.hpp:1237
iterator begin() const
Definition wt_gmr.hpp:1267
random_access_const_iterator< wt_gmr > const_iterator
Definition wt_gmr.hpp:831
std::pair< size_type, value_type > inverse_select(size_type i) const
Calculates how many occurrences of symbol input[i] are in the prefix [0..i-1] of the original input.
Definition wt_gmr.hpp:1138
size_type const & sigma
Definition wt_gmr.hpp:857
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 wt_gmr.hpp:1091
const_iterator end() const
Definition wt_gmr.hpp:1271
int_alphabet_tag alphabet_category
Definition wt_gmr.hpp:834
wt_gmr & operator=(wt_gmr &&wt)
Move assignment operator.
Definition wt_gmr.hpp:1030
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
Definition wt_gmr.hpp:1177
iterator begin()
Definition wt_gmr.hpp:1259
size_type size() const
Returns the size of the original vector.
Definition wt_gmr.hpp:1054
wt_tag index_category
Definition wt_gmr.hpp:833
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
Definition wt_gmr.hpp:1073
t_rac::size_type size_type
Definition wt_gmr.hpp:828
t_rac::value_type value_type
Definition wt_gmr.hpp:829
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.
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition util.hpp:597
Namespace for the succinct data structure library.
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
void read_member(T &t, std::istream &in)
Definition io.hpp:119
void _transform_to_compressed(int_vector<> &iv, typename std::enable_if<!(std::is_same< t_rac, int_vector<> >::value), t_rac >::type &rac, const std::string filename)
Definition wt_gmr.hpp:319
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
bool store_to_file(T const &v, std::string const &file)
Store a data structure to a file.
Definition io.hpp:874
ram_fs.hpp
Contains declarations and definitions of data structure concepts.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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.