SDSL  3.0.0
Succinct Data Structure Library
rrr_vector_15.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_RRR_VECTOR_15
10 #define INCLUDED_SDSL_RRR_VECTOR_15
11 
12 #include <algorithm> // for next_permutation
13 #include <iostream>
14 #include <vector>
15 
16 #include <sdsl/int_vector.hpp>
17 #include <sdsl/iterators.hpp>
18 #include <sdsl/rrr_helper.hpp> // for binomial helper class
19 #include <sdsl/rrr_vector.hpp>
20 #include <sdsl/util.hpp>
21 
23 namespace sdsl
24 {
25 
26 // Helper class for the binomial coefficients \f$ 15 \choose k \f$
27 /*
28  * Size of lookup tables:
29  * * m_nr_to_bin: 64 kB = (2^15 entries x 2 bytes)
30  * * m_bin_to_nr: 64 kB = (2^15 entries x 2 bytes)
31  */
32 template <typename T = void>
34 {
35  public:
36  typedef uint32_t number_type;
37 
38  private:
39  static class impl
40  {
41  public:
42  static const int n = 15;
43  static const int MAX_SIZE = 32;
44  uint8_t m_space_for_bt[16];
45  uint8_t m_space_for_bt_pair[256];
46  uint64_t m_C[MAX_SIZE];
47  int_vector<16> m_nr_to_bin;
48  int_vector<16> m_bin_to_nr;
49 
50  impl()
51  {
52  m_nr_to_bin.resize(1 << n);
53  m_bin_to_nr.resize(1 << n);
54  for (int i = 0, cnt = 0, class_cnt = 0; i <= n; ++i)
55  {
56  m_C[i] = cnt;
57  class_cnt = 0;
58  std::vector<bool> b(n, 0);
59  for (int j = 0; j < i; ++j) b[n - j - 1] = 1;
60  do {
61  uint32_t x = 0;
62  for (int k = 0; k < n; ++k) x |= ((uint32_t)b[n - k - 1]) << (n - 1 - k);
63  m_nr_to_bin[cnt] = x;
64  m_bin_to_nr[x] = class_cnt;
65  ++cnt;
66  ++class_cnt;
67  } while (next_permutation(b.begin(), b.end()));
68  if (class_cnt == 1)
69  m_space_for_bt[i] = 0;
70  else
71  m_space_for_bt[i] = bits::hi(class_cnt) + 1;
72  }
73  if (n == 15)
74  {
75  for (int x = 0; x < 256; ++x)
76  {
77  m_space_for_bt_pair[x] = m_space_for_bt[x >> 4] + m_space_for_bt[x & 0x0F];
78  }
79  }
80  }
81  } iii;
82 
83  public:
84  static inline uint8_t space_for_bt(uint32_t i) { return iii.m_space_for_bt[i]; }
85 
86  static inline uint32_t nr_to_bin(uint8_t k, uint32_t nr) { return iii.m_nr_to_bin[iii.m_C[k] + nr]; }
87 
88  static inline uint32_t bin_to_nr(uint32_t bin) { return iii.m_bin_to_nr[bin]; }
89 
90  static inline uint8_t space_for_bt_pair(uint8_t x) { return iii.m_space_for_bt_pair[x]; }
91 };
92 
93 // initialize the inner class
94 template <typename T>
95 typename binomial15_impl<T>::impl binomial15_impl<T>::iii;
96 
98 
100 
111 template <class t_rac, uint16_t t_k>
112 class rrr_vector<15, t_rac, t_k>
113 {
114  public:
118  typedef t_rac rac_type;
121 
122  friend class rank_support_rrr<0, 15, t_rac, t_k>;
123  friend class rank_support_rrr<1, 15, t_rac, t_k>;
124  friend class select_support_rrr<0, 15, t_rac, t_k>;
125  friend class select_support_rrr<1, 15, t_rac, t_k>;
126 
131 
132  enum
133  {
134  block_size = 15
135  };
137 
138  private:
139  size_type m_size = 0; // Size of the original bit_vector.
140  rac_type m_bt; // Vector for block types (bt). bt equals the
141  // number of set bits in the block.
142  bit_vector m_btnr; // Compressed block type numbers.
143  int_vector<> m_btnrp; // Sample pointers into m_btnr.
144  int_vector<> m_rank; // Sample rank values.
145 
146  public:
147  const rac_type & bt = m_bt;
148  const bit_vector & btnr = m_btnr;
149 
151 
154 
157  : m_size(v.m_size)
158  , m_bt(v.m_bt)
159  , m_btnr(v.m_btnr)
160  , m_btnrp(v.m_btnrp)
161  , m_rank(v.m_rank)
162  {}
163 
165  rrr_vector(rrr_vector && v) { *this = std::move(v); }
166 
169  {
170  if (this != &v)
171  {
172  rrr_vector tmp(v);
173  *this = std::move(tmp);
174  }
175  return *this;
176  }
177 
180  {
181  if (this != &v)
182  {
183  m_size = v.m_size;
184  m_bt = std::move(v.m_bt);
185  m_btnr = std::move(v.m_btnr);
186  m_btnrp = std::move(v.m_btnrp);
187  m_rank = std::move(v.m_rank);
188  }
189  return *this;
190  }
191 
193 
197  rrr_vector(const bit_vector & bv)
198  {
199  m_size = bv.size();
200  int_vector<> bt_array;
201  bt_array = int_vector<>(m_size / block_size + 1, 0, bits::hi(block_size) + 1);
202 
203  // (1) calculate the block types and store them in m_bt
204  size_type pos = 0, i = 0, x;
205  size_type btnr_pos = 0;
206  size_type sum_rank = 0;
207  while (pos + block_size <= m_size)
208  { // handle all full blocks
209  bt_array[i++] = x = bits::cnt(bv.get_int(pos, block_size));
210  sum_rank += x;
211  btnr_pos += bi_type::space_for_bt(x);
212  pos += block_size;
213  }
214  if (pos < m_size)
215  { // handle last full block
216  bt_array[i++] = x = bits::cnt(bv.get_int(pos, m_size - pos));
217  sum_rank += x;
218  btnr_pos += bi_type::space_for_bt(x);
219  }
220  m_btnr = bit_vector(std::max(btnr_pos, (size_type)64), 0); // max necessary for case: block_size == 1
221  m_btnrp = int_vector<>((bt_array.size() + t_k - 1) / t_k, 0, bits::hi(btnr_pos) + 1);
222 
223  m_rank = int_vector<>((bt_array.size() + t_k - 1) / t_k + ((m_size % (t_k * block_size)) > 0),
224  0,
225  bits::hi(sum_rank) + 1);
226  // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
227  // only add a finishing block, if the last
228  // block of the superblock is not a dummy
229  // block
230  // (2) calculate block type numbers and pointers into btnr and rank samples
231  pos = 0;
232  i = 0;
233  btnr_pos = 0, sum_rank = 0;
234  while (pos + block_size <= m_size)
235  { // handle all full blocks
236  if ((i % t_k) == 0)
237  {
238  m_btnrp[i / t_k] = btnr_pos;
239  m_rank[i / t_k] = sum_rank;
240  }
241  uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
242  sum_rank += x;
243  if (space_for_bt)
244  {
245  m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, block_size)), space_for_bt);
246  }
247  btnr_pos += space_for_bt;
248  pos += block_size;
249  }
250  if (pos < m_size)
251  { // handle last not full block
252  if ((i % t_k) == 0)
253  {
254  m_btnrp[i / t_k] = btnr_pos;
255  m_rank[i / t_k] = sum_rank;
256  }
257  uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
258  sum_rank += x;
259  if (space_for_bt)
260  {
261  m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, m_size - pos)), space_for_bt);
262  }
263  btnr_pos += space_for_bt;
264  assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
265  }
266  else
267  { // handle last empty full block
268  assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
269  }
270  // for technical reasons add an additional element to m_rank
271  m_rank[m_rank.size() - 1] = sum_rank; // sum_rank contains the total number of set bits in bv
272  m_bt = rac_type(std::move(bt_array));
273  }
274 
276 
280  {
281  size_type bt_idx = i / block_size;
282  uint8_t * bt = (uint8_t *)(m_bt.data());
283  uint32_t i_bt = *(bt + (bt_idx / 2));
284  if (bt_idx % 2 == 1) { i_bt >>= 4; }
285  else
286  {
287  i_bt &= 0x0F;
288  }
289  if (i_bt == 0 or i_bt == block_size) { return i_bt > 0; }
290  size_type sample_pos = bt_idx / t_k;
291  size_type btnrp = m_btnrp[sample_pos];
292  size_type j = (sample_pos * t_k);
293  bt += j / 2;
294  if (j % 2 == 1 and j < bt_idx)
295  {
296  btnrp += bi_type::space_for_bt((*bt++) >> 4);
297  ++j;
298  }
299  while (j + 1 < bt_idx)
300  {
301  btnrp += bi_type::space_for_bt_pair(*(bt++)); // decode two entries at once
302  j += 2;
303  }
304  if (j < bt_idx) { btnrp += bi_type::space_for_bt((*bt) & 0x0F); }
305 
306  uint32_t btnr = m_btnr.get_int(btnrp, bi_type::space_for_bt(i_bt));
307 
308  uint8_t off = (uint8_t)(i % block_size); // i - bt_idx*block_size;
309  return (bi_type::nr_to_bin(i_bt, btnr) >> off) & (uint32_t)1;
310  }
311 
313 
320  uint64_t get_int(size_type idx, uint8_t len = 64) const
321  {
322  uint64_t res = 0;
323  size_type bb_idx = idx / block_size; // begin block index
324  size_type bb_off = idx % block_size; // begin block offset
325  uint16_t bt = m_bt[bb_idx];
326  size_type sample_pos = bb_idx / t_k;
327  size_type eb_idx = (idx + len - 1) / block_size; // end block index
328  if (bb_idx == eb_idx)
329  { // extract only in one block
330  if (bt == 0)
331  { // all bits are zero
332  res = 0;
333  }
334  else if (bt == block_size)
335  { // all bits are zero
336  res = bits::lo_set[len];
337  }
338  else
339  {
340  size_type btnrp = m_btnrp[sample_pos];
341  for (size_type j = sample_pos * t_k; j < bb_idx; ++j) { btnrp += bi_type::space_for_bt(m_bt[j]); }
342  uint32_t btnr = m_btnr.get_int(btnrp, bi_type::space_for_bt(bt));
343  res = (bi_type::nr_to_bin(bt, btnr) >> bb_off) & bits::lo_set[len];
344  }
345  }
346  else
347  { // solve multiple block case by recursion
348  uint8_t b_len = block_size - bb_off;
349  uint8_t b_len_sum = 0;
350  do {
351  res |= get_int(idx, b_len) << b_len_sum;
352  idx += b_len;
353  b_len_sum += b_len;
354  len -= b_len;
355  b_len = block_size;
356  b_len = std::min(len, b_len);
357  } while (len > 0);
358  }
359  return res;
360  }
361 
363  size_type size() const { return m_size; }
364 
366  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
367  {
368  size_type written_bytes = 0;
369  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
370  written_bytes += write_member(m_size, out, child, "size");
371  written_bytes += m_bt.serialize(out, child, "bt");
372  written_bytes += m_btnr.serialize(out, child, "btnr");
373  written_bytes += m_btnrp.serialize(out, child, "btnrp");
374  written_bytes += m_rank.serialize(out, child, "rank_samples");
375  structure_tree::add_size(child, written_bytes);
376  return written_bytes;
377  }
378 
380  void load(std::istream & in)
381  {
382  read_member(m_size, in);
383  m_bt.load(in);
384  m_btnr.load(in);
385  m_btnrp.load(in);
386  m_rank.load(in);
387  }
388 
389  template <typename archive_t>
390  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
391  {
392  ar(CEREAL_NVP(m_size));
393  ar(CEREAL_NVP(m_bt));
394  ar(CEREAL_NVP(m_btnr));
395  ar(CEREAL_NVP(m_btnrp));
396  ar(CEREAL_NVP(m_rank));
397  }
398 
399  template <typename archive_t>
400  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
401  {
402  ar(CEREAL_NVP(m_size));
403  ar(CEREAL_NVP(m_bt));
404  ar(CEREAL_NVP(m_btnr));
405  ar(CEREAL_NVP(m_btnrp));
406  ar(CEREAL_NVP(m_rank));
407  }
408 
409  iterator begin() const { return iterator(this, 0); }
410 
411  iterator end() const { return iterator(this, size()); }
412 
413  bool operator==(const rrr_vector & v) const
414  {
415  return m_size == v.m_size && m_bt == v.m_bt && m_btnr == v.m_btnr && m_btnrp == v.m_btnrp && m_rank == v.m_rank;
416  }
417 
418  bool operator!=(const rrr_vector & v) const { return !(*this == v); }
419 };
420 
422 
424 template <uint8_t t_b, class t_rac, uint16_t t_k>
425 class rank_support_rrr<t_b, 15, t_rac, t_k>
426 {
427  static_assert(t_b == 1u or t_b == 0u, "rank_support_rrr: bit pattern must be `0` or `1`");
428 
429  public:
433  enum
434  {
435  bit_pat = t_b
436  };
437  enum
438  {
439  bit_pat_len = (uint8_t)1
440  };
441 
442  private:
443  const bit_vector_type * m_v;
444  // TODO cache for sequential ranks
445  // mutable size_type m_last_bt;
446  // mutable size_type m_last_w; // store the last decoded word
447  // uint16_t m_space_for_bt[256];
448  public:
450 
452  explicit rank_support_rrr(const bit_vector_type * v = nullptr) { set_vector(v); }
453 
455 
460  const size_type rank(size_type i) const
461  {
463  size_type sample_pos = bt_idx / t_k;
464  size_type btnrp = m_v->m_btnrp[sample_pos];
465  size_type rank = m_v->m_rank[sample_pos];
466  if (sample_pos + 1 < m_v->m_rank.size())
467  {
468  size_type diff_rank = m_v->m_rank[sample_pos + 1] - rank;
469  if (diff_rank == 0) { return rank_support_rrr_trait<t_b>::adjust_rank(rank, i); }
470  else if (diff_rank == (size_type)bit_vector_type::block_size * t_k)
471  {
473  i);
474  }
475  }
476  uint8_t * bt = (uint8_t *)(m_v->m_bt.data());
477 
478  uint8_t last_bt = *(bt + (bt_idx / 2));
479  if (bt_idx % 2 == 1) { last_bt >>= 4; }
480  else
481  {
482  last_bt &= 0x0F;
483  }
484  // if the final block type consists only of ones or zeros, we don't have to
485  // calculate the position pointer and can sum up rank in 64 bit chunks
486  if (last_bt == 0 or last_bt == 15)
487  {
488  if (last_bt == 15) rank += i % bit_vector_type::block_size;
489  size_type j = (sample_pos * t_k) << 2;
490  bt_idx = bt_idx << 2;
491  if (bt_idx == j) return rank_support_rrr_trait<t_b>::adjust_rank(rank, i);
492  // now j < bt_idx
493  const uint64_t * bt64 = m_v->m_bt.data() + (j >> 6); // get the word of the start
494  uint8_t bt64_off = j & 0x3F; // get the offset in the word of the start
495  const uint64_t * bt64_end = m_v->m_bt.data() + (bt_idx >> 6);
496  uint8_t bt64_end_off = bt_idx & 0x3F;
497  // Case (1)
498  if (bt64 == bt64_end)
499  {
500  uint64_t w = ((*bt64) >> bt64_off) & bits::lo_set[bt64_end_off - bt64_off];
501  w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
502  rank += ((0x0101010101010101ull * w) >> 56);
503  }
504  else
505  { // Case (2)
506  uint64_t w = ((*bt64) >> bt64_off);
507  w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
508  rank += ((0x0101010101010101ull * w) >> 56);
509  while ((++bt64) != bt64_end)
510  {
511  w = *bt64;
512  w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
513  rank += ((0x0101010101010101ull * w) >> 56);
514  }
515  // now bt64 == bt64_end
516  if (bt64_end_off > 0)
517  {
518  w = *bt64 << (64 - bt64_end_off);
519  w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
520  rank += ((0x0101010101010101ull * w) >> 56);
521  }
522  }
523  return rank_support_rrr_trait<t_b>::adjust_rank(rank, i); // necessary
524  }
525  size_type j = sample_pos * t_k;
526  bt += j / 2;
527  if (j % 2 == 1 and j < bt_idx)
528  {
529  const uint8_t r = (*bt++) >> 4;
530  rank += r;
531  btnrp += bi_type::space_for_bt(r);
532  ++j;
533  }
534  while (j + 1 < bt_idx)
535  {
536  const uint8_t r = *(bt++);
537  rank += (r >> 4) + (r & 0x0F);
538  btnrp += bi_type::space_for_bt_pair(r); // decode two entries at once
539  j += 2;
540  }
541  if (j < bt_idx)
542  {
543  const uint8_t r = (*bt);
544  rank += r & 0x0F;
545  btnrp += bi_type::space_for_bt(r & 0x0F);
546  ++j;
547  }
548  uint8_t off = i % bit_vector_type::block_size; // i - bt_idx*bit_vector_type::block_size;
549  if (!off)
550  { // needed for special case: if i=size() is a multiple of block_size
551  // the access to m_bt would cause a invalid memory access
553  }
554  uint32_t btnr = m_v->m_btnr.get_int(btnrp, bi_type::space_for_bt(last_bt));
555  return rank_support_rrr_trait<t_b>::adjust_rank(rank + bits::cnt(((uint64_t)(bi_type::nr_to_bin(last_bt,
556  btnr))) &
557  bits::lo_set[off]),
558  i);
559  }
560 
562  const size_type operator()(size_type i) const { return rank(i); }
563 
565  const size_type size() const { return m_v->size(); }
566 
568  void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
569 
571  {
572  if (this != &rs) { set_vector(rs.m_v); }
573  return *this;
574  }
575 
577  void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
578 
580  size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
581  {
582  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
583  structure_tree::add_size(child, 0);
584  return 0;
585  }
586 
587  template <typename archive_t>
588  void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
589  {}
590 
591  template <typename archive_t>
592  void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
593  {}
594 
595  bool operator==(const rank_support_rrr & other) const noexcept { return *m_v == *other.m_v; }
596 
597  bool operator!=(const rank_support_rrr & other) const noexcept { return !(*this == other); }
598 };
599 
601 template <uint8_t t_b, class t_rac, uint16_t t_k>
602 class select_support_rrr<t_b, 15, t_rac, t_k>
603 {
604  static_assert(t_b == 1u or t_b == 0u, "select_support_rrr: bit pattern must be `0` or `1`");
605 
606  public:
610  enum
611  {
612  bit_pat = t_b
613  };
614  enum
615  {
616  bit_pat_len = (uint8_t)1
617  };
618 
619  private:
620  const bit_vector_type * m_v;
621 
622  // TODO: hinted binary search
623  size_type select1(size_type i) const
624  {
625  if (m_v->m_rank[m_v->m_rank.size() - 1] < i) return size();
626  // (1) binary search for the answer in the rank_samples
627  size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
628  size_type idx, rank;
629  // invariant: m_rank[end] >= i
630  // m_rank[begin] < i
631  while (end - begin > 1)
632  {
633  idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
634  rank = m_v->m_rank[idx];
635  if (rank >= i)
636  end = idx;
637  else
638  { // rank < i
639  begin = idx;
640  }
641  }
642  // (2) linear search between the samples
643  rank = m_v->m_rank[begin]; // now i>rank
644  idx = begin * t_k; // initialize idx for select result
645  size_type diff_rank = m_v->m_rank[end] - rank;
646  if (diff_rank == (size_type)bit_vector_type::block_size * t_k)
647  { // optimisation for select<1>
648  return idx * bit_vector_type::block_size + i - rank - 1;
649  }
650  size_type btnrp = m_v->m_btnrp[begin];
651  uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type
652  while (i > rank)
653  {
654  bt = m_v->m_bt[idx++];
655  rank += bt;
656  btnrp += (s = bi_type::space_for_bt(bt));
657  }
658  rank -= bt;
659  uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
660  return (idx - 1) * bit_vector_type::block_size + bits::sel(bi_type::nr_to_bin(bt, btnr), i - rank);
661  }
662 
663  // TODO: hinted binary search
664  size_type select0(size_type i) const
665  {
666  if ((size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i) return size();
667  // (1) binary search for the answer in the rank_samples
668  size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
669  size_type idx, rank;
670  // invariant: m_rank[end] >= i
671  // m_rank[begin] < i
672  while (end - begin > 1)
673  {
674  idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
675  rank = idx * bit_vector_type::block_size * t_k - m_v->m_rank[idx];
676  if (rank >= i)
677  end = idx;
678  else
679  { // rank < i
680  begin = idx;
681  }
682  }
683  // (2) linear search between the samples
684  rank = begin * bit_vector_type::block_size * t_k - m_v->m_rank[begin]; // now i>rank
685  idx = begin * t_k; // initialize idx for select result
686  if (m_v->m_rank[end] == m_v->m_rank[begin])
687  { // only for select<0>
688  return idx * bit_vector_type::block_size + i - rank - 1;
689  }
690  size_type btnrp = m_v->m_btnrp[begin];
691  uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type
692  while (i > rank)
693  {
694  bt = m_v->m_bt[idx++];
695  rank += (bit_vector_type::block_size - bt);
696  btnrp += (s = bi_type::space_for_bt(bt));
697  }
698  rank -= (bit_vector_type::block_size - bt);
699  uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
700  return (idx - 1) * bit_vector_type::block_size + bits::sel(~((uint64_t)bi_type::nr_to_bin(bt, btnr)), i - rank);
701  }
702 
703  public:
704  select_support_rrr(const bit_vector_type * v = nullptr) { set_vector(v); }
705 
707  size_type select(size_type i) const { return t_b ? select1(i) : select0(i); }
708 
709  const size_type operator()(size_type i) const { return select(i); }
710 
711  const size_type size() const { return m_v->size(); }
712 
713  void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
714 
716  {
717  if (this != &rs) { set_vector(rs.m_v); }
718  return *this;
719  }
720 
721  void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
722 
723  size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
724  {
725  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
726  structure_tree::add_size(child, 0);
727  return 0;
728  }
729 
730  template <typename archive_t>
731  void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
732  {}
733 
734  template <typename archive_t>
735  void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
736  {}
737 
738  bool operator==(const select_support_rrr & other) const noexcept { return *m_v == *other.m_v; }
739 
740  bool operator!=(const select_support_rrr & other) const noexcept { return !(*this == other); }
741 };
742 
743 } // end namespace sdsl
744 
745 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
static uint32_t bin_to_nr(uint32_t bin)
static uint8_t space_for_bt_pair(uint8_t x)
static uint8_t space_for_bt(uint32_t i)
static uint32_t nr_to_bin(uint8_t k, uint32_t nr)
value_type get_int(size_type idx, const uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx in the int_vector.
int_vector_size_type size_type
Definition: int_vector.hpp:266
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
int_vector_trait< t_width >::value_type value_type
Definition: int_vector.hpp:255
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
void set_int(size_type idx, value_type x, const uint8_t len=64)
Set the bits from position idx to idx+len-1 to the binary representation of integer x.
Generic iterator for a random access container.
Definition: iterators.hpp:24
rank_support_rrr(const bit_vector_type *v=nullptr)
Standard constructor.
rrr_vector< 15, t_rac, t_k > bit_vector_type
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into a stream.
const size_type rank(size_type i) const
Answers rank queries.
rank_support_rrr & operator=(const rank_support_rrr &rs)
const size_type operator()(size_type i) const
Short hand for rank(i)
const size_type size() const
Returns the size of the original vector.
void set_vector(const bit_vector_type *v=nullptr)
Set the supported vector.
bool operator!=(const rank_support_rrr &other) const noexcept
bool operator==(const rank_support_rrr &other) const noexcept
void load(std::istream &, const bit_vector_type *v=nullptr)
Load the data structure from a stream and set the supported vector.
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Definition: rrr_vector.hpp:431
Answers rank queries const size_type rank(size_type i) const
Definition: rrr_vector.hpp:462
Set the supported vector void set_vector(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:509
A specialization of the rrr_vector class for a block_size of 15.
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
bit_vector::difference_type difference_type
uint64_t get_int(size_type idx, uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
select_support_rrr< 0, 15, t_rac, t_k > select_0_type
rrr_vector(const rrr_vector &v)
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.
bit_vector::value_type value_type
rank_support_rrr< 0, 15, t_rac, t_k > rank_0_type
random_access_const_iterator< rrr_vector > iterator
void load(std::istream &in)
Loads the data structure from the given istream.
rank_support_rrr< 1, 15, t_rac, t_k > rank_1_type
rrr_vector(const bit_vector &bv)
Constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
rrr_vector & operator=(rrr_vector &&v)
Move assignment.
select_support_rrr< 1, 15, t_rac, t_k > select_1_type
bool operator==(const rrr_vector &v) const
size_type size() const
Returns the size of the original bit vector.
rrr_vector & operator=(const rrr_vector &v)
Assignment operator.
bool operator!=(const rrr_vector &v) const
rrr_vector(rrr_vector &&v)
Move constructor.
random_access_const_iterator< rrr_vector > iterator
Definition: rrr_vector.hpp:71
const bit_vector & btnr
Definition: rrr_vector.hpp:106
const rac_type & bt
Definition: rrr_vector.hpp:105
Returns the size of the original bit vector size_type size() const
Definition: rrr_vector.hpp:339
Get the integer value of the binary string of length len starting at position idx uint64_t get_int(size_type idx, uint8_t len=64) const
Definition: rrr_vector.hpp:291
size_type select(size_type i) const
Answers select queries.
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
select_support_rrr & operator=(const select_support_rrr &rs)
bool operator==(const select_support_rrr &other) const noexcept
bool operator!=(const select_support_rrr &other) const noexcept
const size_type operator()(size_type i) const
void set_vector(const bit_vector_type *v=nullptr)
select_support_rrr(const bit_vector_type *v=nullptr)
void load(std::istream &, const bit_vector_type *v=nullptr)
void set_vector(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:669
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Definition: rrr_vector.hpp:555
Answers select queries size_type select(size_type i) const
Definition: rrr_vector.hpp:663
bit_vector_type::size_type size_type
Definition: rrr_vector.hpp:559
const size_type size() const
Definition: rrr_vector.hpp:667
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)
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
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
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
Definition: int_vector.hpp:51
rrr_helper.hpp contains the sdsl::binomial struct, a struct which contains informations about the bin...
rrr_vector.hpp contains the sdsl::rrr_vector class, and classes which support rank and select for rrr...
static SDSL_CONSTEXPR uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
Definition: bits.hpp:594
constexpr static uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
Definition: bits.hpp:197
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
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494
static size_type adjust_rank(size_type r, SDSL_UNUSED size_type n)
Definition: rrr_vector.hpp:407
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.