SDSL 3.0.1
Succinct Data Structure Library
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
14#include <sdsl/bit_vectors.hpp>
15#include <sdsl/int_vector.hpp>
16#include <sdsl/vectors.hpp>
17
19namespace sdsl
20{
21
23
36template <uint64_t t_s = 32,
37 class t_rac = int_vector<>,
38 class t_bv = bit_vector,
39 class t_rank = typename t_bv::rank_1_type>
41{
42 public:
43 typedef t_rac iv_type;
44 typedef typename iv_type::size_type size_type;
45 typedef typename iv_type::value_type value_type;
46 typedef typename iv_type::difference_type difference_type;
47 typedef t_bv bit_vector_type;
48 typedef t_rank rank_type;
50
51 private:
52 const iv_type * m_perm = nullptr; // pointer to supported permutation
53 uint64_t m_chunksize; // size of one permutation
54 int_vector<> m_back_pointer; // back pointers
55 bit_vector_type m_marked; // back pointer marking
56 rank_type m_marked_rank; // rank support for back pointer marking
57
58 public:
61
63 inv_multi_perm_support(const iv_type * perm, int_vector<> & iv, uint64_t chunksize)
64 : m_perm(perm)
65 , m_chunksize(chunksize)
66 {
67 bit_vector marked(iv.size(), 0);
68 bit_vector done(m_chunksize, 0);
69
70 size_type max_back_pointer = 0;
71 for (size_type i = 0, off = 0; i < iv.size(); ++i)
72 {
73 if (i == off + chunksize)
74 {
75 off = i;
76 util::set_to_value(done, 0);
77 }
78 if (!done[i - off])
79 {
80 done[i - off] = 1;
81 size_type back_pointer = i, j = i, j_new = 0;
82 uint64_t steps = 0, all_steps = 0;
83 while ((j_new = (iv[j] + off)) != i)
84 {
85 j = j_new;
86 done[j - off] = 1;
87 ++steps;
88 ++all_steps;
89 if (t_s == steps)
90 {
91 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
92 marked[j] = 1;
93 steps = 0;
94 back_pointer = j;
95 }
96 }
97 if (all_steps > t_s)
98 {
99 marked[i] = 1;
100 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
101 }
102 }
103 }
104
105 m_marked = t_bv(std::move(marked));
106 util::init_support(m_marked_rank, &m_marked);
107
108 util::set_to_value(done, 0);
109 size_type n_bp = m_marked_rank(iv.size());
110 m_back_pointer = int_vector<>(n_bp, 0, bits::hi(max_back_pointer) + 1);
111
112 for (size_type i = 0, off = 0; i < iv.size(); ++i)
113 {
114 if (i == off + chunksize)
115 {
116 off = i;
117 util::set_to_value(done, 0);
118 }
119 if (!done[i - off])
120 {
121 done[i - off] = 1;
122 size_type back_pointer = i, j = i, j_new = 0;
123 uint64_t steps = 0, all_steps = 0;
124 while ((j_new = (iv[j] + off)) != i)
125 {
126 j = j_new;
127 done[j - off] = 1;
128 ++steps;
129 ++all_steps;
130 if (t_s == steps)
131 {
132 m_back_pointer[m_marked_rank(j)] = back_pointer - off;
133 steps = 0;
134 back_pointer = j;
135 }
136 }
137 if (all_steps > t_s) { m_back_pointer[m_marked_rank(i)] = back_pointer - off; }
138 }
139 }
140 }
141
144 : m_perm(p.m_perm)
145 , m_chunksize(p.m_chunksize)
146 , m_back_pointer(p.m_back_pointer)
147 , m_marked(p.m_marked)
148 , m_marked_rank(p.m_marked_rank)
149 {
150 m_marked_rank.set_vector(&m_marked);
151 }
152
154 inv_multi_perm_support(inv_multi_perm_support && p) { *this = std::move(p); }
155
158 {
159 if (this != &p)
160 {
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 m_marked_rank.set_vector(&m_marked);
167 }
168 return *this;
169 }
170
173 {
174 if (this != &p)
175 {
176 m_perm = std::move(p.m_perm);
177 m_chunksize = std::move(p.m_chunksize);
178 m_back_pointer = std::move(p.m_back_pointer);
179 m_marked = std::move(p.m_marked);
180 m_marked_rank = std::move(p.m_marked_rank);
181 m_marked_rank.set_vector(&m_marked);
182 }
183 return *this;
184 }
185
187 size_type size() const { return nullptr == m_perm ? 0 : m_perm->size(); }
188
190 bool empty() const { return size() == 0; }
191
193 /*
194 * \par Time complexity
195 * \f$ \Order{t_s} \f$
196 */
198 {
199 size_type off = (i / m_chunksize) * m_chunksize;
200 size_type j = i, j_new = 0;
201 while ((j_new = ((*m_perm)[j]) + off) != i)
202 {
203 if (m_marked[j])
204 {
205 j = m_back_pointer[m_marked_rank(j)] + off;
206 while ((j_new = ((*m_perm)[j]) + off) != i) j = j_new;
207 }
208 else
209 {
210 j = j_new;
211 }
212 }
213 return j;
214 }
215
217 const_iterator begin() const { return const_iterator(this, 0); }
218
220 const_iterator end() const { return const_iterator(this, size()); }
221
222 void set_vector(const iv_type * v) { m_perm = v; }
223
225 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
226 {
227 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
228 size_type written_bytes = 0;
229 written_bytes += write_member(m_chunksize, out, child, "chunksize");
230 written_bytes += m_back_pointer.serialize(out, child, "back_pointer");
231 written_bytes += m_marked.serialize(out, child, "marked");
232 written_bytes += m_marked_rank.serialize(out, child, "marked_rank");
233 structure_tree::add_size(child, written_bytes);
234 return written_bytes;
235 }
236
238 void load(std::istream & in, const iv_type * v = nullptr)
239 {
240 set_vector(v);
241 read_member(m_chunksize, in);
242 m_back_pointer.load(in);
243 m_marked.load(in);
244 m_marked_rank.load(in, &m_marked);
245 }
246
248 template <typename archive_t>
249 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
250 {
251 ar(CEREAL_NVP(m_chunksize));
252 ar(CEREAL_NVP(m_back_pointer));
253 ar(CEREAL_NVP(m_marked));
254 ar(CEREAL_NVP(m_marked_rank));
255 }
256
258 template <typename archive_t>
259 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
260 {
261 ar(CEREAL_NVP(m_chunksize));
262 ar(CEREAL_NVP(m_back_pointer));
263 ar(CEREAL_NVP(m_marked));
264 ar(CEREAL_NVP(m_marked_rank));
265 m_marked_rank.set_vector(&m_marked);
266 }
267
269 bool operator==(inv_multi_perm_support const & other) const noexcept
270 {
271 return (m_chunksize == other.m_chunksize) && (m_back_pointer == other.m_back_pointer) &&
272 (m_marked == other.m_marked) && (m_marked_rank == other.m_marked_rank);
273 }
274
276 bool operator!=(inv_multi_perm_support const & other) const noexcept { return !(*this == other); }
277};
278
279template <class t_rac>
281 typename std::enable_if<!(std::is_same<t_rac, int_vector<>>::value), t_rac>::type & rac,
282 const std::string filename)
283{
284 std::string tmp_file_name = tmp_file(filename, "_compress_int_vector");
285 store_to_file(iv, tmp_file_name);
286 util::clear(iv);
287 int_vector_buffer<> buf(tmp_file_name, std::ios::in, 1024 * 1024, iv.width());
288 rac = t_rac(buf);
289 buf.close(true); // delete tmp_file
290}
291
292template <class t_rac>
294 typename std::enable_if<std::is_same<t_rac, int_vector<>>::value, t_rac>::type & rac,
295 const std::string)
296{
297 rac = std::move(iv);
298}
299
301
317template <class t_rac = int_vector<>,
318 class t_bitvector = bit_vector,
319 class t_select = typename t_bitvector::select_1_type,
320 class t_select_zero = typename t_bitvector::select_0_type>
322{
323 public:
326 typedef typename t_bitvector::difference_type difference_type;
331 enum
332 {
333 lex_ordered = 0
334 };
335
336 private:
337 t_bitvector m_bv_blocks;
338 t_rac m_e;
339 t_select m_bv_blocks_select1;
340 t_select_zero m_bv_blocks_select0;
341 uint64_t m_size; // input length
342 uint64_t m_block_size = 0; // size of the blocks
343 uint64_t m_blocks; // blocks per character
344 uint64_t m_sigma = 0;
345
346 public:
347 const size_type & sigma = m_sigma;
348
350 wt_gmr_rs() = default;
351
353
361 template <typename t_it>
362 wt_gmr_rs(t_it begin, t_it end, std::string tmp_dir = ram_file_name(""))
363 : m_size(std::distance(begin, end))
364 {
365 // Determine max. symbol
366 for (auto it = begin; it != end; ++it)
367 {
368 value_type value = *it;
369 if (m_block_size < value) m_block_size = value;
370 }
371 ++m_block_size;
372
373 // Create and fill m_bv_blocks
374 m_blocks = (m_size + m_block_size - 1) / m_block_size;
375 bit_vector b(m_size + m_block_size * m_blocks + 1, 0);
376 int_vector<> symbols(m_block_size, 0, bits::hi(m_size) + 1);
377 {
378 int_vector<> tmp(m_block_size * m_blocks, 0, bits::hi(m_block_size) + 1);
379 uint64_t j = 0, offset = 0;
380 for (auto it = begin; it != end; ++it, ++j)
381 {
382 if (j == m_block_size)
383 {
384 ++offset;
385 j = 0;
386 }
387 ++tmp[(*it) * m_blocks + offset];
388 }
389
390 for (uint64_t i = 0; i < symbols.size(); ++i)
391 {
392 for (uint64_t j = m_blocks * i; j < (i + 1) * m_blocks; ++j) { symbols[i] += tmp[j]; }
393 }
394
395 for (uint64_t i = 0, l = 1; i < tmp.size(); ++i, ++l)
396 {
397 for (uint64_t j = 0; j < tmp[i]; ++j) b[l++] = 1;
398 }
399
400 // calc m_sigma
401 bool write = true;
402 uint64_t blocks = 0;
403 for (uint64_t i = 1; i < b.size(); ++i)
404 {
405 if (blocks == m_blocks)
406 {
407 blocks = 0;
408 write = true;
409 }
410 if (b[i])
411 {
412 if (write)
413 {
414 ++m_sigma;
415 write = false;
416 }
417 }
418 else
419 ++blocks;
420 }
421
422 m_bv_blocks = t_bitvector(std::move(b));
423 }
424
425 // Create and fill e
426 int_vector<> positions(m_size, 0, bits::hi(m_block_size) + 1);
427 for (uint64_t i = 0, tmp = 0, sum = 0; i < m_block_size; ++i)
428 {
429 tmp = symbols[i];
430 symbols[i] = sum;
431 sum += tmp;
432 }
433 for (auto it = begin; it != end;)
434 {
435 for (uint64_t j = 0; j < m_block_size and it != end; ++it, ++j) { positions[symbols[*it]++] = j; }
436 }
437 _transform_to_compressed<t_rac>(positions, m_e, tmp_dir);
438
439 util::init_support(m_bv_blocks_select0, &m_bv_blocks);
440 util::init_support(m_bv_blocks_select1, &m_bv_blocks);
441 }
442
445 : m_bv_blocks(wt.m_bv_blocks)
446 , m_e(wt.m_e)
447 , m_bv_blocks_select1(wt.m_bv_blocks_select1)
448 , m_bv_blocks_select0(wt.m_bv_blocks_select0)
449 , m_size(wt.m_size)
450 , m_block_size(wt.m_block_size)
451 , m_blocks(wt.m_blocks)
452 , m_sigma(wt.m_sigma)
453 {
454 m_bv_blocks_select1.set_vector(&m_bv_blocks);
455 m_bv_blocks_select0.set_vector(&m_bv_blocks);
456 }
457
460 : m_bv_blocks(std::move(wt.m_bv_blocks))
461 , m_e(std::move(wt.m_e))
462 , m_bv_blocks_select1(std::move(wt.m_bv_blocks_select1))
463 , m_bv_blocks_select0(std::move(wt.m_bv_blocks_select0))
464 , m_size(wt.m_size)
465 , m_block_size(wt.m_block_size)
466 , m_blocks(wt.m_blocks)
467 , m_sigma(wt.m_sigma)
468 {
469 m_bv_blocks_select1.set_vector(&m_bv_blocks);
470 m_bv_blocks_select0.set_vector(&m_bv_blocks);
471 }
472
475 {
476 wt_gmr_rs tmp(wt);
477 *this = std::move(tmp);
478 return *this;
479 }
480
483 {
484 m_bv_blocks = std::move(wt.m_bv_blocks);
485 m_e = std::move(wt.m_e);
486 m_bv_blocks_select1 = std::move(wt.m_bv_blocks_select1);
487 m_bv_blocks_select1.set_vector(&m_bv_blocks);
488 m_bv_blocks_select0 = std::move(wt.m_bv_blocks_select0);
489 m_bv_blocks_select0.set_vector(&m_bv_blocks);
490 m_size = wt.m_size;
491 m_block_size = wt.m_block_size;
492 m_blocks = wt.m_blocks;
493 m_sigma = wt.m_sigma;
494 return *this;
495 }
496
498 size_type size() const { return m_size; }
499
501 bool empty() const { return m_size == 0; }
502
504
512 {
513 assert(i < m_size);
514 size_type block = i / m_block_size + 1, val = i % m_block_size, search_begin, search_end, j;
515 while (true)
516 {
517 j = m_bv_blocks_select0(block) + 1;
518 search_begin = j - block;
519 if (m_bv_blocks[j])
520 {
521 search_end = m_bv_blocks_select0(block + 1) - (block);
522 if (search_end - search_begin < 50)
523 { // After a short test, this seems to be a good threshold
524 while (search_begin < search_end and m_e[search_begin] <= val)
525 {
526 if (m_e[search_begin] == val) { return (block - 1) / m_blocks; }
527 ++search_begin;
528 }
529 }
530 else
531 {
532 if (std::binary_search(m_e.begin() + search_begin, m_e.begin() + search_end, val))
533 {
534 return (block - 1) / m_blocks;
535 }
536 }
537 }
538 block += m_blocks;
539 }
540 }
541
543
553 {
554 if (0 == i or c > m_block_size - 1) { return 0; }
555
556 size_type offset = 0;
557 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - c * m_blocks;
558
559 auto begin = m_e.begin() + m_bv_blocks_select0(c * m_blocks + (i - 1) / m_block_size + 1) -
560 (c * m_blocks + (i - 1) / m_block_size + 1) + 1;
561 auto end = m_e.begin() + m_bv_blocks_select0(c * m_blocks + (i - 1) / m_block_size + 2) -
562 (c * m_blocks + (i - 1) / m_block_size + 1);
563
564 size_type val = (i - 1) % m_block_size;
565 if (end - begin < 50)
566 { // After a short test, this seems to be a good threshold
567 offset = std::find_if(begin, end, [&val](const decltype(*begin) x) { return x > val; }) - begin;
568 }
569 else
570 {
571 offset = std::lower_bound(begin, end, val + 1) - begin;
572 }
573 return (begin - m_e.begin()) + offset - ones_before_cblock;
574 }
575
577
586 std::pair<size_type, value_type> inverse_select(size_type i) const
587 {
588 assert(i < m_size);
589 size_type block = i / m_block_size + 1, val = i % m_block_size, offset = 0, search_begin, search_end, j;
590 while (true)
591 {
592 j = m_bv_blocks_select0(block) + 1;
593 search_begin = j - block;
594 if (m_bv_blocks[j])
595 {
596 search_end = m_bv_blocks_select0(block + 1) - (block);
597 offset = 0;
598 if (search_end - search_begin < 50)
599 { // After a short test, this seems to be a good threshold
600 while (search_begin < search_end and m_e[search_begin] <= val)
601 {
602 if (m_e[search_begin] == val)
603 {
604 value_type c = (block - 1) / m_blocks;
605 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks);
606 size_type r = search_begin - ones_before_cblock;
607 return std::make_pair(r, c);
608 }
609 ++search_begin;
610 }
611 }
612 else
613 {
614 offset = std::lower_bound(m_e.begin() + search_begin, m_e.begin() + search_end, val) - m_e.begin();
615 if (offset < search_end)
616 {
617 if (m_e[offset] == val)
618 {
619 value_type c = (block - 1) / m_blocks;
620 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks);
621 size_type r = offset - ones_before_cblock;
622 return std::make_pair(r, c);
623 }
624 }
625 }
626 }
627 block += m_blocks;
628 }
629 }
630
632
641 {
642 size_type k = m_bv_blocks_select0(c * m_blocks + 1) - (c * m_blocks) + i;
643 return (m_bv_blocks_select1(k) - k) * m_block_size + m_e[k - 1] - c * m_blocks * m_block_size;
644 }
645
647 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
648 {
649 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
650 size_type written_bytes = 0;
651 written_bytes += write_member(m_size, out, child, "size");
652 written_bytes += write_member(m_block_size, out, child, "block_size");
653 written_bytes += write_member(m_blocks, out, child, "blocks");
654 written_bytes += write_member(m_sigma, out, child, "sigma");
655 written_bytes += m_e.serialize(out, child, "E");
656 written_bytes += m_bv_blocks.serialize(out, child, "bv_blocks");
657 written_bytes += m_bv_blocks_select0.serialize(out, child, "bv_blocks_select0");
658 written_bytes += m_bv_blocks_select1.serialize(out, child, "bv_blocks_select1");
659 structure_tree::add_size(child, written_bytes);
660 return written_bytes;
661 }
662
664 void load(std::istream & in)
665 {
666 read_member(m_size, in);
667 read_member(m_block_size, in);
668 read_member(m_blocks, in);
669 read_member(m_sigma, in);
670 m_e.load(in);
671 m_bv_blocks.load(in);
672 m_bv_blocks_select0.load(in, &m_bv_blocks);
673 m_bv_blocks_select1.load(in, &m_bv_blocks);
674 }
675
677 template <typename archive_t>
678 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
679 {
680 ar(CEREAL_NVP(m_size));
681 ar(CEREAL_NVP(m_block_size));
682 ar(CEREAL_NVP(m_blocks));
683 ar(CEREAL_NVP(m_sigma));
684 ar(CEREAL_NVP(m_e));
685 ar(CEREAL_NVP(m_bv_blocks));
686 ar(CEREAL_NVP(m_bv_blocks_select0));
687 ar(CEREAL_NVP(m_bv_blocks_select1));
688 }
689
691 template <typename archive_t>
692 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
693 {
694 ar(CEREAL_NVP(m_size));
695 ar(CEREAL_NVP(m_block_size));
696 ar(CEREAL_NVP(m_blocks));
697 ar(CEREAL_NVP(m_sigma));
698 ar(CEREAL_NVP(m_e));
699 ar(CEREAL_NVP(m_bv_blocks));
700 ar(CEREAL_NVP(m_bv_blocks_select0));
701 m_bv_blocks_select0.set_vector(&m_bv_blocks);
702 ar(CEREAL_NVP(m_bv_blocks_select1));
703 m_bv_blocks_select1.set_vector(&m_bv_blocks);
704 }
705
706 iterator begin() { return { this, 0 }; };
707 const_iterator end() { return { this, size() }; };
708 iterator begin() const { return { this, 0 }; };
709 const_iterator end() const { return { this, size() }; };
710
712 bool operator==(wt_gmr_rs const & other) const noexcept
713 {
714 return (m_size == other.m_size) && (m_block_size == other.m_block_size) && (m_blocks == other.m_blocks) &&
715 (m_sigma == other.m_sigma) && (m_e == other.m_e) && (m_bv_blocks == other.m_bv_blocks) &&
716 (m_bv_blocks_select0 == other.m_bv_blocks_select0) && (m_bv_blocks_select1 == other.m_bv_blocks_select1);
717 }
718
720 bool operator!=(wt_gmr_rs const & other) const noexcept { return !(*this == other); }
721};
722
724
741template <class t_rac = int_vector<>,
742 class t_inverse_support = inv_multi_perm_support<32, t_rac>,
743 class t_bitvector = bit_vector,
744 class t_select = typename t_bitvector::select_1_type,
745 class t_select_zero = typename t_bitvector::select_0_type>
747{
748 public:
749 typedef typename t_rac::size_type size_type;
750 typedef typename t_rac::value_type value_type;
751 typedef typename t_bitvector::difference_type difference_type;
756 enum
757 {
758 lex_ordered = 0
759 };
760
761 private:
762 t_bitvector m_bv_blocks; // 0 indicates end of block. Corresponds to B in the paper.
763 t_bitvector m_bv_chunks; // 0 indicates end of symbol in chunk. Corresponds to X in the paper.
764
765 t_rac m_perm; // Contains permutation of each chunk. Corresponds to \f$ \pi \f$ in the paper.
766 t_inverse_support m_ips; // Support for inverse permutation
767
768 t_select m_bv_blocks_select1, m_bv_chunks_select1;
769 t_select_zero m_bv_blocks_select0, m_bv_chunks_select0;
770
771 uint64_t m_size; // input length
772 uint64_t m_max_symbol = 0; // maximum character + 1
773 uint64_t m_chunks; // number of chunks
774 uint64_t m_chunksize;
775 uint64_t m_sigma = 0;
776
777 public:
778 const size_type & sigma = m_sigma;
779
781 wt_gmr() = default;
782
784
792 template <typename t_it>
793 wt_gmr(t_it begin, t_it end, std::string tmp_dir = ram_file_name(""))
794 : m_size(std::distance(begin, end))
795 {
796 // Determine max. symbol
797 for (auto it = begin; it != end; ++it)
798 {
799 value_type value = *it;
800 if (m_max_symbol < value) m_max_symbol = value;
801 }
802 ++m_max_symbol;
803 m_chunksize = (1ULL << (bits::hi(m_max_symbol - 1) + 1)); // In some cases this is better than m_max_smbol
804 m_chunks = (m_size + m_chunksize - 1) / m_chunksize;
805
806 // calc m_bv_blocks
807 {
808 bit_vector b(m_size + m_max_symbol * m_chunks + 1, 0);
809 int_vector<> tmp(m_max_symbol * m_chunks, 0, bits::hi(m_max_symbol - 1) + 2);
810
811 uint64_t offset = 0, j = 0;
812 for (auto it = begin; it != end; ++it, ++j)
813 {
814 if (j == m_chunksize)
815 {
816 ++offset;
817 j = 0;
818 }
819 ++tmp[(*it) * m_chunks + offset];
820 }
821
822 for (uint64_t i = 0, l = 1; i < tmp.size(); ++i, ++l)
823 for (uint64_t j = 0; j < tmp[i]; ++j) b[l++] = 1;
824
825 // calc m_sigma
826 bool write = true;
827 uint64_t blocks = 0;
828 for (uint64_t i = 1; i < b.size(); ++i)
829 {
830 if (blocks == m_chunks)
831 {
832 blocks = 0;
833 write = true;
834 }
835 if (b[i])
836 {
837 if (write)
838 {
839 ++m_sigma;
840 write = false;
841 }
842 }
843 else
844 ++blocks;
845 }
846
847 m_bv_blocks = t_bitvector(std::move(b));
848 }
849
850 // Calc perm and bv_chunks
851 {
852 uint64_t x_pos = 0;
853 bit_vector x(m_size + m_chunks * m_max_symbol + 1, 0);
854
855 // fill perm and m_bv_chunks for every chunk
856 int_vector<> perm(m_size, 0, bits::hi(m_max_symbol - 1) + 1);
857 for (uint64_t i = 0; i < m_chunks; ++i)
858 {
859 int_vector<> symbols(m_max_symbol, 0, bits::hi(m_max_symbol - 1) + 2);
860
861 // calc symbols
862 for (uint64_t j = i * m_chunksize; j < (i + 1) * m_chunksize and j < m_size; ++j)
863 {
864 ++symbols[*(begin + j)];
865 }
866 // calc m_bv_chunks
867 for (uint64_t j = 0; j < m_max_symbol; ++j, ++x_pos)
868 for (uint64_t k = 0; k < symbols[j]; ++k) x[++x_pos] = 1;
869
870 // calc symbols prefix sum
871 for (uint64_t j = 0, tmp = 0, sum = 0; j < m_max_symbol; ++j)
872 {
873 tmp = symbols[j];
874 symbols[j] = sum;
875 sum += tmp;
876 }
877 // calc perm
878 for (uint64_t j = i * m_chunksize, k = 0; j < (i + 1) * m_chunksize and j < m_size; ++j, ++k)
879 {
880 perm[i * m_chunksize + (symbols[*(begin + j)]++)] = k;
881 }
882 }
883 m_bv_chunks = t_bitvector(std::move(x));
884 m_ips = t_inverse_support(&m_perm, perm, m_chunksize);
885 _transform_to_compressed<t_rac>(perm, m_perm, tmp_dir);
886 m_ips.set_vector(&m_perm);
887 }
888 util::init_support(m_bv_chunks_select1, &m_bv_chunks);
889 util::init_support(m_bv_chunks_select0, &m_bv_chunks);
890 util::init_support(m_bv_blocks_select1, &m_bv_blocks);
891 util::init_support(m_bv_blocks_select0, &m_bv_blocks);
892 }
893
895 wt_gmr(const wt_gmr & wt)
896 : m_bv_blocks(wt.m_bv_blocks)
897 , m_bv_chunks(wt.m_bv_chunks)
898 , m_perm(wt.m_perm)
899 , m_ips(wt.m_ips)
900 , m_bv_blocks_select1(wt.m_bv_blocks_select1)
901 , m_bv_chunks_select1(wt.m_bv_chunks_select1)
902 , m_bv_blocks_select0(wt.m_bv_blocks_select0)
903 , m_bv_chunks_select0(wt.m_bv_chunks_select0)
904 , m_size(wt.m_size)
905 , m_max_symbol(wt.m_max_symbol)
906 , m_chunks(wt.m_chunks)
907 , m_chunksize(wt.m_chunksize)
908 , m_sigma(wt.m_sigma)
909 {
910 m_ips.set_vector(&m_perm);
911 m_bv_blocks_select1.set_vector(&m_bv_blocks);
912 m_bv_chunks_select1.set_vector(&m_bv_chunks);
913 m_bv_blocks_select0.set_vector(&m_bv_blocks);
914 m_bv_chunks_select0.set_vector(&m_bv_chunks);
915 }
916
919 : m_bv_blocks(std::move(wt.m_bv_blocks))
920 , m_bv_chunks(std::move(wt.m_bv_chunks))
921 , m_perm(std::move(wt.m_perm))
922 , m_ips(std::move(wt.m_ips))
923 , m_bv_blocks_select1(std::move(wt.m_bv_blocks_select1))
924 , m_bv_chunks_select1(std::move(wt.m_bv_chunks_select1))
925 , m_bv_blocks_select0(std::move(wt.m_bv_blocks_select0))
926 , m_bv_chunks_select0(std::move(wt.m_bv_chunks_select0))
927 , m_size(wt.m_size)
928 , m_max_symbol(wt.m_max_symbol)
929 , m_chunks(wt.m_chunks)
930 , m_chunksize(wt.m_chunksize)
931 , m_sigma(wt.m_sigma)
932 {
933 m_ips.set_vector(&m_perm);
934 m_bv_blocks_select1.set_vector(&m_bv_blocks);
935 m_bv_chunks_select1.set_vector(&m_bv_chunks);
936 m_bv_blocks_select0.set_vector(&m_bv_blocks);
937 m_bv_chunks_select0.set_vector(&m_bv_chunks);
938 }
939
941 wt_gmr & operator=(const wt_gmr & wt)
942 {
943 wt_gmr tmp(wt);
944 *this = std::move(tmp);
945 return *this;
946 }
947
950 {
951 m_bv_blocks = std::move(wt.m_bv_blocks);
952 m_bv_chunks = std::move(wt.m_bv_chunks);
953 m_perm = std::move(wt.m_perm);
954 m_ips = std::move(wt.m_ips);
955 m_ips.set_vector(&m_perm);
956 m_bv_blocks_select1 = std::move(wt.m_bv_blocks_select1);
957 m_bv_blocks_select1.set_vector(&m_bv_blocks);
958 m_bv_chunks_select1 = std::move(wt.m_bv_chunks_select1);
959 m_bv_chunks_select1.set_vector(&m_bv_chunks);
960 m_bv_blocks_select0 = std::move(wt.m_bv_blocks_select0);
961 m_bv_blocks_select0.set_vector(&m_bv_blocks);
962 m_bv_chunks_select0 = std::move(wt.m_bv_chunks_select0);
963 m_bv_chunks_select0.set_vector(&m_bv_chunks);
964 m_size = wt.m_size;
965 m_max_symbol = wt.m_max_symbol;
966 m_chunks = wt.m_chunks;
967 m_chunksize = wt.m_chunksize;
968 m_sigma = wt.m_sigma;
969 return *this;
970 }
971
973 size_type size() const { return m_size; }
974
976 bool empty() const { return m_size == 0; }
977
979
987 {
988 assert(i < size());
989 uint64_t chunk = i / m_chunksize;
990 uint64_t x = m_ips[i];
991 return m_bv_chunks_select1(x + 1) - x - (chunk * m_max_symbol) - 1;
992 }
993
995
1005 {
1006 assert(i <= size());
1007
1008 if (0 == i or c > m_max_symbol - 1) { return 0; }
1009
1010 uint64_t chunk = (i - 1) / m_chunksize;
1011 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks + 1) + 1;
1012 uint64_t c_ones_before_chunk = m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk + 1) + 1 -
1013 ones_before_c;
1014
1015 uint64_t c_ones_in_chunk = 0;
1016 auto begin = m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 1 + c) -
1017 (chunk * m_max_symbol + 1 + c) + 1;
1018 auto end = m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 2 + c) - (chunk * m_max_symbol + 2 + c) +
1019 1;
1020
1021 size_type val = (i - 1) % m_chunksize;
1022 if (end - begin < 50)
1023 { // After a short test, this seems to be a good threshold
1024 c_ones_in_chunk = std::find_if(begin, end, [&val](const decltype(*begin) x) { return x > val; }) - begin;
1025 }
1026 else
1027 {
1028 c_ones_in_chunk = std::lower_bound(begin, end, val + 1) - begin;
1029 }
1030 return c_ones_before_chunk + c_ones_in_chunk;
1031 }
1032
1034
1042 std::pair<size_type, value_type> inverse_select(size_type i) const
1043 {
1044 assert(i < size());
1045 uint64_t chunk = i / m_chunksize;
1046 uint64_t x = m_ips[i];
1047 uint64_t tmp = m_bv_chunks_select1(x + 1);
1048 uint64_t c = tmp - x - (chunk * m_max_symbol) - 1;
1049
1050 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks + 1) + 1;
1051 uint64_t c_before_chunk = m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk + 1) + 1 -
1052 ones_before_c;
1053 uint64_t c_in_chunk = tmp - m_bv_chunks_select0(c + 1 + chunk * m_max_symbol) - 1;
1054 return std::make_pair(c_before_chunk + c_in_chunk, c);
1055 }
1056
1058
1067 {
1068 assert(1 <= i and i <= rank(size(), c));
1069
1070 uint64_t ones_before_c = m_bv_blocks_select0(c * m_chunks + 1) - (c * m_chunks);
1071 uint64_t chunk = m_bv_blocks_select1(ones_before_c + i) - ones_before_c - (c * m_chunks + 1) - i + 1;
1072 uint64_t c_ones_before_chunk = m_bv_blocks_select0(c * m_chunks + chunk + 1) - (c * m_chunks + chunk) -
1073 ones_before_c;
1074 uint64_t pi_pos = m_bv_chunks_select0(chunk * m_max_symbol + c + 1) + (i - c_ones_before_chunk) -
1075 chunk * m_max_symbol - c - 1;
1076
1077 return m_perm[pi_pos] + chunk * m_chunksize;
1078 }
1079
1081 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
1082 {
1083 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
1084 size_type written_bytes = 0;
1085 written_bytes += write_member(m_size, out, child, "size");
1086 written_bytes += write_member(m_max_symbol, out, child, "max_symbol");
1087 written_bytes += write_member(m_chunks, out, child, "chunks");
1088 written_bytes += write_member(m_chunksize, out, child, "chunksize");
1089 written_bytes += write_member(m_sigma, out, child, "sigma");
1090 written_bytes += m_bv_blocks.serialize(out, child, "bv_blocks");
1091 written_bytes += m_bv_blocks_select0.serialize(out, child, "bv_blocks_select0");
1092 written_bytes += m_bv_blocks_select1.serialize(out, child, "bv_blocks_select1");
1093 written_bytes += m_bv_chunks.serialize(out, child, "bv_chunks");
1094 written_bytes += m_bv_chunks_select0.serialize(out, child, "bv_chunks_select0");
1095 written_bytes += m_bv_chunks_select1.serialize(out, child, "bv_chunks_select1");
1096 written_bytes += m_perm.serialize(out, child, "permutation");
1097 written_bytes += m_ips.serialize(out, child, "inverse_permutation_support");
1098 structure_tree::add_size(child, written_bytes);
1099 return written_bytes;
1100 }
1101
1103 void load(std::istream & in)
1104 {
1105 read_member(m_size, in);
1106 read_member(m_max_symbol, in);
1107 read_member(m_chunks, in);
1108 read_member(m_chunksize, in);
1109 read_member(m_sigma, in);
1110 m_bv_blocks.load(in);
1111 m_bv_blocks_select0.load(in, &m_bv_blocks);
1112 m_bv_blocks_select1.load(in, &m_bv_blocks);
1113 m_bv_chunks.load(in);
1114 m_bv_chunks_select0.load(in, &m_bv_chunks);
1115 m_bv_chunks_select1.load(in, &m_bv_chunks);
1116 m_perm.load(in);
1117 m_ips.load(in, &m_perm);
1118 }
1119
1121 template <typename archive_t>
1122 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
1123 {
1124 ar(CEREAL_NVP(m_size));
1125 ar(CEREAL_NVP(m_max_symbol));
1126 ar(CEREAL_NVP(m_chunks));
1127 ar(CEREAL_NVP(m_chunksize));
1128 ar(CEREAL_NVP(m_sigma));
1129 ar(CEREAL_NVP(m_bv_blocks));
1130 ar(CEREAL_NVP(m_bv_blocks_select0));
1131 ar(CEREAL_NVP(m_bv_blocks_select1));
1132 ar(CEREAL_NVP(m_bv_chunks));
1133 ar(CEREAL_NVP(m_bv_chunks_select0));
1134 ar(CEREAL_NVP(m_bv_chunks_select1));
1135 ar(CEREAL_NVP(m_perm));
1136 ar(CEREAL_NVP(m_ips));
1137 }
1138
1140 template <typename archive_t>
1141 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
1142 {
1143 ar(CEREAL_NVP(m_size));
1144 ar(CEREAL_NVP(m_max_symbol));
1145 ar(CEREAL_NVP(m_chunks));
1146 ar(CEREAL_NVP(m_chunksize));
1147 ar(CEREAL_NVP(m_sigma));
1148 ar(CEREAL_NVP(m_bv_blocks));
1149 ar(CEREAL_NVP(m_bv_blocks_select0));
1150 m_bv_blocks_select0.set_vector(&m_bv_blocks);
1151 ar(CEREAL_NVP(m_bv_blocks_select1));
1152 m_bv_blocks_select1.set_vector(&m_bv_blocks);
1153 ar(CEREAL_NVP(m_bv_chunks));
1154 ar(CEREAL_NVP(m_bv_chunks_select0));
1155 m_bv_chunks_select0.set_vector(&m_bv_chunks);
1156 ar(CEREAL_NVP(m_bv_chunks_select1));
1157 m_bv_chunks_select1.set_vector(&m_bv_chunks);
1158 ar(CEREAL_NVP(m_perm));
1159 ar(CEREAL_NVP(m_ips));
1160 m_ips.set_vector(&m_perm);
1161 }
1162
1163 iterator begin() { return { this, 0 }; };
1164 const_iterator end() { return { this, size() }; };
1165 iterator begin() const { return { this, 0 }; };
1166 const_iterator end() const { return { this, size() }; };
1167
1169 bool operator==(wt_gmr const & other) const noexcept
1170 {
1171 return (m_size == other.m_size) && (m_max_symbol == other.m_max_symbol) && (m_chunks == other.m_chunks) &&
1172 (m_chunksize == other.m_chunksize) && (m_sigma == other.m_sigma) && (m_bv_blocks == other.m_bv_blocks) &&
1173 (m_bv_blocks_select0 == other.m_bv_blocks_select0) &&
1174 (m_bv_blocks_select1 == other.m_bv_blocks_select1) && (m_bv_chunks == other.m_bv_chunks) &&
1175 (m_bv_chunks_select0 == other.m_bv_chunks_select0) &&
1176 (m_bv_chunks_select1 == other.m_bv_chunks_select1) && (m_perm == other.m_perm) && (m_ips == other.m_ips);
1177 }
1178
1180 bool operator!=(wt_gmr const & other) const noexcept { return !(*this == other); }
1181};
1182} // namespace sdsl
1183
1184#endif
bit_vectors.hpp contains classes for uncompressed and compressed bit vector representations.
#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.
Definition: int_vector.hpp:595
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:41
bool operator==(inv_multi_perm_support const &other) const noexcept
Equality operator.
Definition: wt_gmr.hpp:269
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: wt_gmr.hpp:249
iv_type::size_type size_type
Definition: wt_gmr.hpp:44
void load(std::istream &in, const iv_type *v=nullptr)
Load sampling from disk.
Definition: wt_gmr.hpp:238
inv_multi_perm_support(const iv_type *perm, int_vector<> &iv, uint64_t chunksize)
Constructor.
Definition: wt_gmr.hpp:63
inv_multi_perm_support & operator=(inv_multi_perm_support &&p)
Assignment move operation.
Definition: wt_gmr.hpp:172
const_iterator begin() const
Returns a const_iterator to the first element.
Definition: wt_gmr.hpp:217
bool operator!=(inv_multi_perm_support const &other) const noexcept
Inequality operator.
Definition: wt_gmr.hpp:276
random_access_const_iterator< inv_multi_perm_support > const_iterator
Definition: wt_gmr.hpp:49
value_type operator[](size_type i) const
Access operator.
Definition: wt_gmr.hpp:197
inv_multi_perm_support()
Default constructor.
Definition: wt_gmr.hpp:60
inv_multi_perm_support(const inv_multi_perm_support &p)
Copy constructor.
Definition: wt_gmr.hpp:143
bool empty() const
Returns whether the original vector contains no data.
Definition: wt_gmr.hpp:190
iv_type::value_type value_type
Definition: wt_gmr.hpp:45
inv_multi_perm_support(inv_multi_perm_support &&p)
Move constructor.
Definition: wt_gmr.hpp:154
inv_multi_perm_support & operator=(const inv_multi_perm_support &p)
Assignment operation.
Definition: wt_gmr.hpp:157
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize into stream.
Definition: wt_gmr.hpp:225
size_type size() const
Returns the size of the original vector.
Definition: wt_gmr.hpp:187
const_iterator end() const
Returns a const_iterator to the element after the last element.
Definition: wt_gmr.hpp:220
iv_type::difference_type difference_type
Definition: wt_gmr.hpp:46
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition: wt_gmr.hpp:259
void set_vector(const iv_type *v)
Definition: wt_gmr.hpp:222
Generic iterator for a random access container.
Definition: iterators.hpp:24
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
A wavelet tree class for integer sequences.
Definition: wt_gmr.hpp:322
wt_tag index_category
Definition: wt_gmr.hpp:329
t_bitvector::difference_type difference_type
Definition: wt_gmr.hpp:326
const_iterator end() const
Definition: wt_gmr.hpp:709
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:640
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition: wt_gmr.hpp:692
const size_type & sigma
Definition: wt_gmr.hpp:347
wt_gmr_rs(wt_gmr_rs &&wt)
Move copy constructor.
Definition: wt_gmr.hpp:459
wt_gmr_rs()=default
Default constructor.
wt_gmr_rs & operator=(const wt_gmr_rs &wt)
Assignment operator.
Definition: wt_gmr.hpp:474
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: wt_gmr.hpp:678
random_access_const_iterator< wt_gmr_rs > const_iterator
Definition: wt_gmr.hpp:327
const_iterator iterator
Definition: wt_gmr.hpp:328
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:552
bool empty() const
Returns whether the wavelet tree contains no data.
Definition: wt_gmr.hpp:501
int_vector ::value_type value_type
Definition: wt_gmr.hpp:325
void load(std::istream &in)
Loads the data structure from the given istream.
Definition: wt_gmr.hpp:664
wt_gmr_rs(const wt_gmr_rs &wt)
Copy constructor.
Definition: wt_gmr.hpp:444
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:586
const_iterator end()
Definition: wt_gmr.hpp:707
size_type size() const
Returns the size of the original vector.
Definition: wt_gmr.hpp:498
bool operator==(wt_gmr_rs const &other) const noexcept
Equality operator.
Definition: wt_gmr.hpp:712
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
Definition: wt_gmr.hpp:511
iterator begin()
Definition: wt_gmr.hpp:706
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:362
wt_gmr_rs & operator=(wt_gmr_rs &&wt)
Move assignment operator.
Definition: wt_gmr.hpp:482
bool operator!=(wt_gmr_rs const &other) const noexcept
Inequality operator.
Definition: wt_gmr.hpp:720
int_alphabet_tag alphabet_category
Definition: wt_gmr.hpp:330
iterator begin() const
Definition: wt_gmr.hpp:708
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:647
int_vector ::size_type size_type
Definition: wt_gmr.hpp:324
A wavelet tree class for integer sequences.
Definition: wt_gmr.hpp:747
bool operator!=(wt_gmr const &other) const noexcept
Inequality operator.
Definition: wt_gmr.hpp:1180
const_iterator end()
Definition: wt_gmr.hpp:1164
bool empty() const
Returns whether the wavelet tree contains no data.
Definition: wt_gmr.hpp:976
wt_gmr()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
Definition: wt_gmr.hpp:1122
const_iterator iterator
Definition: wt_gmr.hpp:753
t_bitvector::difference_type difference_type
Definition: wt_gmr.hpp:751
bool operator==(wt_gmr const &other) const noexcept
Equality operator.
Definition: wt_gmr.hpp:1169
wt_gmr & operator=(const wt_gmr &wt)
Assignment operator.
Definition: wt_gmr.hpp:941
void load(std::istream &in)
Loads the data structure from the given istream.
Definition: wt_gmr.hpp:1103
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:793
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:1066
wt_gmr(wt_gmr &&wt)
Move constructor.
Definition: wt_gmr.hpp:918
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Definition: wt_gmr.hpp:1141
iterator begin() const
Definition: wt_gmr.hpp:1165
random_access_const_iterator< wt_gmr > const_iterator
Definition: wt_gmr.hpp:752
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:1042
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:1004
const_iterator end() const
Definition: wt_gmr.hpp:1166
wt_gmr(const wt_gmr &wt)
Copy constructor.
Definition: wt_gmr.hpp:895
int_alphabet_tag alphabet_category
Definition: wt_gmr.hpp:755
wt_gmr & operator=(wt_gmr &&wt)
Move assignment operator.
Definition: wt_gmr.hpp:949
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:1081
const size_type & sigma
Definition: wt_gmr.hpp:778
iterator begin()
Definition: wt_gmr.hpp:1163
size_type size() const
Returns the size of the original vector.
Definition: wt_gmr.hpp:973
wt_tag index_category
Definition: wt_gmr.hpp:754
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
Definition: wt_gmr.hpp:986
t_rac::size_type size_type
Definition: wt_gmr.hpp:749
t_rac::value_type value_type
Definition: wt_gmr.hpp:750
int_vector.hpp contains the sdsl::int_vector class.
int_vector ::size_type size_type
void set_to_value(t_int_vec &v, uint64_t k)
Set all entries of int_vector to value k.
Definition: util.hpp:563
Namespace for the succinct data structure library.
std::string ram_file_name(const std::string &file)
Returns the corresponding RAM-file name for file.
Definition: ram_fs.hpp:174
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition: io.hpp:84
void read_member(T &t, std::istream &in)
Definition: io.hpp:111
std::string tmp_file(const cache_config &config, std::string name_part="")
Returns a name for a temporary file. I.e. the name was not used before.
Definition: io.hpp:698
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:280
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:53
bool store_to_file(const T &v, const std::string &file)
Store a data structure to a file.
Definition: io.hpp:798
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651