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