9#ifndef INCLUDED_SDSL_WT_GMR
10#define INCLUDED_SDSL_WT_GMR
50template <uint64_t t_s = 32,
53 class t_rank =
typename t_bv::rank_1_type>
66 iv_type const * m_perm =
nullptr;
79 m_chunksize(chunksize)
87 if (i == off + chunksize)
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)
105 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
114 max_back_pointer = std::max(max_back_pointer, back_pointer - off);
119 m_marked = t_bv(std::move(marked));
120 util::init_support(m_marked_rank, &m_marked);
128 if (i == off + chunksize)
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)
146 m_back_pointer[m_marked_rank(j)] = back_pointer - off;
153 m_back_pointer[m_marked_rank(i)] = back_pointer - off;
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)
167 m_marked_rank.set_vector(&m_marked);
173 *
this = std::move(p);
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);
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);
209 return nullptr == m_perm ? 0 : m_perm->size();
225 size_type off = (i / m_chunksize) * m_chunksize;
227 while ((j_new = ((*m_perm)[j]) + off) != i)
231 j = m_back_pointer[m_marked_rank(j)] + off;
232 while ((j_new = ((*m_perm)[j]) + off) != i)
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");
270 return written_bytes;
278 m_back_pointer.
load(in);
280 m_marked_rank.load(in, &m_marked);
284 template <
typename archive_t>
294 template <
typename archive_t>
301 m_marked_rank.set_vector(&m_marked);
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);
314 return !(*
this == other);
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)
323 std::string tmp_file_name =
tmp_file(filename,
"_compress_int_vector");
331template <
class t_rac>
333 typename std::enable_if<std::is_same<t_rac,
int_vector<>>::value, t_rac>::type & rac,
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>
376 t_bitvector m_bv_blocks;
378 t_select m_bv_blocks_select1;
379 t_select_zero m_bv_blocks_select0;
381 uint64_t m_block_size = 0;
383 uint64_t m_sigma = 0;
400 template <
typename t_it>
404 for (
auto it =
begin; it !=
end; ++it)
407 if (m_block_size < value)
408 m_block_size = value;
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);
418 uint64_t j = 0, offset = 0;
419 for (
auto it =
begin; it !=
end; ++it, ++j)
421 if (j == m_block_size)
426 ++tmp[(*it) * m_blocks + offset];
429 for (uint64_t i = 0; i < symbols.
size(); ++i)
431 for (uint64_t j = m_blocks * i; j < (i + 1) * m_blocks; ++j)
433 symbols[i] += tmp[j];
437 for (uint64_t i = 0, l = 1; i < tmp.
size(); ++i, ++l)
439 for (uint64_t j = 0; j < tmp[i]; ++j)
446 for (uint64_t i = 1; i < b.
size(); ++i)
448 if (blocks == m_blocks)
465 m_bv_blocks = t_bitvector(std::move(b));
470 for (uint64_t i = 0, tmp = 0, sum = 0; i < m_block_size; ++i)
478 for (uint64_t j = 0; j < m_block_size and it !=
end; ++it, ++j)
480 positions[symbols[*it]++] = j;
483 _transform_to_compressed<t_rac>(positions, m_e, tmp_dir);
485 util::init_support(m_bv_blocks_select0, &m_bv_blocks);
486 util::init_support(m_bv_blocks_select1, &m_bv_blocks);
491 m_bv_blocks(wt.m_bv_blocks),
493 m_bv_blocks_select1(wt.m_bv_blocks_select1),
494 m_bv_blocks_select0(wt.m_bv_blocks_select0),
496 m_block_size(wt.m_block_size),
497 m_blocks(wt.m_blocks),
500 m_bv_blocks_select1.set_vector(&m_bv_blocks);
501 m_bv_blocks_select0.set_vector(&m_bv_blocks);
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)),
511 m_block_size(wt.m_block_size),
512 m_blocks(wt.m_blocks),
515 m_bv_blocks_select1.set_vector(&m_bv_blocks);
516 m_bv_blocks_select0.set_vector(&m_bv_blocks);
523 *
this = std::move(tmp);
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);
537 m_block_size = wt.m_block_size;
538 m_blocks = wt.m_blocks;
539 m_sigma = wt.m_sigma;
566 size_type block = i / m_block_size + 1, val = i % m_block_size, search_begin, search_end, j;
569 j = m_bv_blocks_select0(block) + 1;
570 search_begin = j - block;
573 search_end = m_bv_blocks_select0(block + 1) - (block);
574 if (search_end - search_begin < 50)
576 while (search_begin < search_end and m_e[search_begin] <= val)
578 if (m_e[search_begin] == val)
580 return (block - 1) / m_blocks;
587 if (std::binary_search(m_e.begin() + search_begin, m_e.begin() + search_end, val))
589 return (block - 1) / m_blocks;
609 if (0 == i or c > m_block_size - 1)
615 size_type ones_before_cblock = m_bv_blocks_select0(c * m_blocks + 1) - c * m_blocks;
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);
625 offset = std::find_if(
begin,
627 [&val](
auto const && x)
637 return (
begin - m_e.begin()) + offset - ones_before_cblock;
653 size_type block = i / m_block_size + 1, val = i % m_block_size, offset = 0, search_begin, search_end, j;
656 j = m_bv_blocks_select0(block) + 1;
657 search_begin = j - block;
660 search_end = m_bv_blocks_select0(block + 1) - (block);
662 if (search_end - search_begin < 50)
664 while (search_begin < search_end and m_e[search_begin] <= val)
666 if (m_e[search_begin] == val)
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);
678 offset = std::lower_bound(m_e.begin() + search_begin, m_e.begin() + search_end, val) - m_e.begin();
679 if (offset < search_end)
681 if (m_e[offset] == val)
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);
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;
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");
724 return written_bytes;
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);
741 template <
typename archive_t>
755 template <
typename archive_t>
765 m_bv_blocks_select0.set_vector(&m_bv_blocks);
767 m_bv_blocks_select1.set_vector(&m_bv_blocks);
776 return {
this,
size()};
784 return {
this,
size()};
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);
798 return !(*
this == other);
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>
841 t_bitvector m_bv_blocks;
842 t_bitvector m_bv_chunks;
845 t_inverse_support m_ips;
847 t_select m_bv_blocks_select1, m_bv_chunks_select1;
848 t_select_zero m_bv_blocks_select0, m_bv_chunks_select0;
851 uint64_t m_max_symbol = 0;
853 uint64_t m_chunksize;
854 uint64_t m_sigma = 0;
871 template <
typename t_it>
875 for (
auto it =
begin; it !=
end; ++it)
878 if (m_max_symbol < value)
879 m_max_symbol = value;
882 m_chunksize = (1ULL << (
bits::hi(m_max_symbol - 1) + 1));
883 m_chunks = (m_size + m_chunksize - 1) / m_chunksize;
887 bit_vector b(m_size + m_max_symbol * m_chunks + 1, 0);
890 uint64_t offset = 0, j = 0;
891 for (
auto it =
begin; it !=
end; ++it, ++j)
893 if (j == m_chunksize)
898 ++tmp[(*it) * m_chunks + offset];
901 for (uint64_t i = 0, l = 1; i < tmp.
size(); ++i, ++l)
902 for (uint64_t j = 0; j < tmp[i]; ++j)
908 for (uint64_t i = 1; i < b.
size(); ++i)
910 if (blocks == m_chunks)
927 m_bv_blocks = t_bitvector(std::move(b));
933 bit_vector x(m_size + m_chunks * m_max_symbol + 1, 0);
937 for (uint64_t i = 0; i < m_chunks; ++i)
942 for (uint64_t j = i * m_chunksize; j < (i + 1) * m_chunksize and j < m_size; ++j)
944 ++symbols[*(
begin + j)];
947 for (uint64_t j = 0; j < m_max_symbol; ++j, ++x_pos)
948 for (uint64_t k = 0; k < symbols[j]; ++k)
952 for (uint64_t j = 0, tmp = 0, sum = 0; j < m_max_symbol; ++j)
959 for (uint64_t j = i * m_chunksize, k = 0; j < (i + 1) * m_chunksize and j < m_size; ++j, ++k)
961 perm[i * m_chunksize + (symbols[*(
begin + j)]++)] = k;
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);
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);
977 m_bv_blocks(wt.m_bv_blocks),
978 m_bv_chunks(wt.m_bv_chunks),
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),
986 m_max_symbol(wt.m_max_symbol),
987 m_chunks(wt.m_chunks),
988 m_chunksize(wt.m_chunksize),
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);
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)),
1009 m_max_symbol(wt.m_max_symbol),
1010 m_chunks(wt.m_chunks),
1011 m_chunksize(wt.m_chunksize),
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);
1025 *
this = std::move(tmp);
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);
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;
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;
1093 assert(i <=
size());
1095 if (0 == i or c > m_max_symbol - 1)
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;
1105 uint64_t c_ones_in_chunk = 0;
1107 m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 1 + c) - (chunk * m_max_symbol + 1 + c) + 1;
1109 m_perm.begin() + m_bv_chunks_select0(chunk * m_max_symbol + 2 + c) - (chunk * m_max_symbol + 2 + c) + 1;
1114 c_ones_in_chunk = std::find_if(
begin,
1116 [&val](
auto const && x)
1124 c_ones_in_chunk = std::lower_bound(
begin,
end, val + 1) -
begin;
1126 return c_ones_before_chunk + c_ones_in_chunk;
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;
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);
1164 assert(1 <= i and i <=
rank(
size(), c));
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;
1173 return m_perm[pi_pos] + chunk * m_chunksize;
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");
1195 return written_bytes;
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);
1213 m_ips.load(in, &m_perm);
1217 template <
typename archive_t>
1236 template <
typename archive_t>
1246 m_bv_blocks_select0.set_vector(&m_bv_blocks);
1248 m_bv_blocks_select1.set_vector(&m_bv_blocks);
1251 m_bv_chunks_select0.set_vector(&m_bv_chunks);
1253 m_bv_chunks_select1.set_vector(&m_bv_chunks);
1256 m_ips.set_vector(&m_perm);
1265 return {
this,
size()};
1273 return {
this,
size()};
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);
1289 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
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.
inv_multi_perm_support(inv_multi_perm_support const &p)
Copy constructor.
bool operator==(inv_multi_perm_support const &other) const noexcept
Equality operator.
inv_multi_perm_support & operator=(inv_multi_perm_support const &p)
Assignment operation.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
iv_type::size_type size_type
inv_multi_perm_support(iv_type const *perm, int_vector<> &iv, uint64_t chunksize)
Constructor.
inv_multi_perm_support & operator=(inv_multi_perm_support &&p)
Assignment move operation.
void load(std::istream &in, iv_type const *v=nullptr)
Load sampling from disk.
const_iterator begin() const
Returns a const_iterator to the first element.
bool operator!=(inv_multi_perm_support const &other) const noexcept
Inequality operator.
random_access_const_iterator< inv_multi_perm_support > const_iterator
value_type operator[](size_type i) const
Access operator.
inv_multi_perm_support()
Default constructor.
bool empty() const
Returns whether the original vector contains no data.
iv_type::value_type value_type
inv_multi_perm_support(inv_multi_perm_support &&p)
Move constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize into stream.
size_type size() const
Returns the size of the original vector.
void set_vector(iv_type const *v)
const_iterator end() const
Returns a const_iterator to the element after the last element.
iv_type::difference_type difference_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
Generic iterator for a random access container.
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.
t_bitvector::difference_type difference_type
const_iterator end() const
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
wt_gmr_rs(wt_gmr_rs &&wt)
Move copy constructor.
wt_gmr_rs()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
random_access_const_iterator< wt_gmr_rs > const_iterator
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.
bool empty() const
Returns whether the wavelet tree contains no data.
int_vector ::value_type value_type
void load(std::istream &in)
Loads the data structure from the given istream.
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.
size_type size() const
Returns the size of the original vector.
bool operator==(wt_gmr_rs const &other) const noexcept
Equality operator.
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
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.
wt_gmr_rs & operator=(wt_gmr_rs &&wt)
Move assignment operator.
wt_gmr_rs & operator=(wt_gmr_rs const &wt)
Assignment operator.
bool operator!=(wt_gmr_rs const &other) const noexcept
Inequality operator.
int_alphabet_tag alphabet_category
wt_gmr_rs(wt_gmr_rs const &wt)
Copy constructor.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
int_vector ::size_type size_type
A wavelet tree class for integer sequences.
bool operator!=(wt_gmr const &other) const noexcept
Inequality operator.
bool empty() const
Returns whether the wavelet tree contains no data.
wt_gmr()=default
Default constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
t_bitvector::difference_type difference_type
bool operator==(wt_gmr const &other) const noexcept
Equality operator.
wt_gmr(wt_gmr const &wt)
Copy constructor.
wt_gmr & operator=(wt_gmr const &wt)
Assignment operator.
void load(std::istream &in)
Loads the data structure from the given istream.
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.
size_type select(size_type i, value_type c) const
Calculates the i-th occurrence of the symbol c in the supported vector.
wt_gmr(wt_gmr &&wt)
Move constructor.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Load via cereal.
random_access_const_iterator< wt_gmr > const_iterator
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.
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.
const_iterator end() const
int_alphabet_tag alphabet_category
wt_gmr & operator=(wt_gmr &&wt)
Move assignment operator.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
size_type size() const
Returns the size of the original vector.
value_type operator[](size_type i) const
Recovers the i-th symbol of the original vector.
t_rac::size_type size_type
t_rac::value_type value_type
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.
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.
std::string ram_file_name(std::string const &file)
Returns the corresponding RAM-file name for file.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
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)
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.
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.
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.