SDSL  3.0.0
Succinct Data Structure Library
rrr_vector.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
10 #define INCLUDED_SDSL_RRR_VECTOR
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/util.hpp>
20 
22 namespace sdsl
23 {
24 
25 // forward declaration needed for friend declaration
26 template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
27 class rank_support_rrr; // in rrr_vector
28 
29 // forward declaration needed for friend declaration
30 template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
31 class select_support_rrr; // in rrr_vector
32 
34 
60 template <uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
62 {
63  static_assert(t_bs >= 3 and t_bs <= 256, "rrr_vector: block size t_bs must be 3 <= t_bs <= 256.");
64  static_assert(t_k > 1, "rrr_vector: t_k must be > 0.");
65 
66  public:
70  typedef t_rac rac_type;
74 
79 
80  friend class rank_support_rrr<0, t_bs, t_rac, t_k>;
81  friend class rank_support_rrr<1, t_bs, t_rac, t_k>;
82  friend class select_support_rrr<0, t_bs, t_rac, t_k>;
83  friend class select_support_rrr<1, t_bs, t_rac, t_k>;
84 
87 
88  enum
89  {
90  block_size = t_bs
91  };
92 
93  private:
94  size_type m_size = 0; // Size of the original bit_vector.
95  rac_type m_bt; // Vector for the block types (bt). bt equals the
96  // number of set bits in the block.
97  bit_vector m_btnr; // Compressed block type numbers.
98  int_vector<> m_btnrp; // Sample pointers into m_btnr.
99  int_vector<> m_rank; // Sample rank values.
100  bit_vector m_invert; // Specifies if a superblock (i.e. t_k blocks)
101  // have to be considered as inverted i.e. 1 and
102  // 0 are swapped
103 
104  public:
105  const rac_type & bt = m_bt;
106  const bit_vector & btnr = m_btnr;
107 
111  : m_size(v.m_size)
112  , m_bt(v.m_bt)
113  , m_btnr(v.m_btnr)
114  , m_btnrp(v.m_btnrp)
115  , m_rank(v.m_rank)
116  , m_invert(v.m_invert)
117  {}
118 
119  rrr_vector(rrr_vector && v) { *this = std::move(v); }
121  {
122  if (this != &v)
123  {
124  rrr_vector tmp(v); // re-use copy-constructor
125  *this = std::move(tmp); // re-use move-assignment
126  }
127  return *this;
128  }
130  {
131  if (this != &v)
132  {
133  m_size = v.m_size;
134  m_bt = std::move(v.m_bt);
135  m_btnr = std::move(v.m_btnr);
136  m_btnrp = std::move(v.m_btnrp);
137  m_rank = std::move(v.m_rank);
138  m_invert = std::move(v.m_invert);
139  }
140  return *this;
141  }
142 
144 
148  rrr_vector(const bit_vector & bv)
149  {
150  m_size = bv.size();
151  int_vector<> bt_array;
152  bt_array.width(bits::hi(t_bs) + 1);
153  bt_array.resize((m_size + t_bs) / ((size_type)t_bs)); // blocks for the bt_array + a dummy block at the end,
154  // if m_size%t_bs == 0
155 
156  // (1) calculate the block types and store them in m_bt
157  size_type pos = 0, i = 0, x;
158  size_type btnr_pos = 0;
159  size_type sum_rank = 0;
160  while (pos + t_bs <= m_size)
161  { // handle all blocks full blocks
162  bt_array[i++] = x = rrr_helper_type::get_bt(bv, pos, t_bs);
163  sum_rank += x;
164  btnr_pos += rrr_helper_type::space_for_bt(x);
165  pos += t_bs;
166  }
167  if (pos < m_size)
168  { // handle last not full block
169  bt_array[i++] = x = rrr_helper_type::get_bt(bv, pos, m_size - pos);
170  sum_rank += x;
171  btnr_pos += rrr_helper_type::space_for_bt(x);
172  }
173  m_btnr = bit_vector(std::max(btnr_pos, (size_type)64), 0); // max necessary for case: t_bs == 1
174  m_btnrp = int_vector<>((bt_array.size() + t_k - 1) / t_k, 0, bits::hi(btnr_pos) + 1);
175  m_rank = int_vector<>((bt_array.size() + t_k - 1) / t_k + ((m_size % (t_k * t_bs)) > 0),
176  0,
177  bits::hi(sum_rank) + 1);
178  // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
179  // only add a finishing block, if the last block of the superblock is not a dummy block
180  m_invert = bit_vector((bt_array.size() + t_k - 1) / t_k, 0);
181 
182  // (2) calculate block type numbers and pointers into btnr and rank samples
183  pos = 0;
184  i = 0;
185  btnr_pos = 0, sum_rank = 0;
186  bool invert = false;
187  while (pos + t_bs <= m_size)
188  { // handle all full blocks
189  if ((i % t_k) == (size_type)0)
190  {
191  m_btnrp[i / t_k] = btnr_pos;
192  m_rank[i / t_k] = sum_rank;
193  // calculate invert bit for that superblock
194  if (i + t_k <= bt_array.size())
195  {
196  size_type gt_half_t_bs = 0; // counter for blocks greater than half of the blocksize
197  for (size_type j = i; j < i + t_k; ++j)
198  {
199  if (bt_array[j] > t_bs / 2) ++gt_half_t_bs;
200  }
201  if (gt_half_t_bs > (t_k / 2))
202  {
203  m_invert[i / t_k] = 1;
204  for (size_type j = i; j < i + t_k; ++j) { bt_array[j] = t_bs - bt_array[j]; }
205  invert = true;
206  }
207  else
208  {
209  invert = false;
210  }
211  }
212  else
213  {
214  invert = false;
215  }
216  }
217  uint16_t space_for_bt = rrr_helper_type::space_for_bt(x = bt_array[i++]);
218  sum_rank += (invert ? (t_bs - x) : x);
219  if (space_for_bt)
220  {
221  number_type bin = rrr_helper_type::decode_btnr(bv, pos, t_bs);
223  rrr_helper_type::set_bt(m_btnr, btnr_pos, nr, space_for_bt);
224  }
225  btnr_pos += space_for_bt;
226  pos += t_bs;
227  }
228  if (pos < m_size)
229  { // handle last not full block
230  if ((i % t_k) == (size_type)0)
231  {
232  m_btnrp[i / t_k] = btnr_pos;
233  m_rank[i / t_k] = sum_rank;
234  m_invert[i / t_k] = 0; // default: set last block to not inverted
235  invert = false;
236  }
237  uint16_t space_for_bt = rrr_helper_type::space_for_bt(x = bt_array[i++]);
238  // no extra dummy block added to bt_array, therefore this condition should hold
239  assert(i == bt_array.size());
240  sum_rank += invert ? (t_bs - x) : x;
241  if (space_for_bt)
242  {
243  number_type bin = rrr_helper_type::decode_btnr(bv, pos, m_size - pos);
245  rrr_helper_type::set_bt(m_btnr, btnr_pos, nr, space_for_bt);
246  }
247  btnr_pos += space_for_bt;
248  assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
249  }
250  else
251  { // handle last empty full block
252  assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
253  }
254  // for technical reasons we add a last element to m_rank
255  m_rank[m_rank.size() - 1] = sum_rank; // sum_rank contains the total number of set bits in bv
256  m_bt = bt_array;
257  }
258 
260 
264  {
265  size_type bt_idx = i / t_bs;
266  uint16_t bt = m_bt[bt_idx];
267  size_type sample_pos = bt_idx / t_k;
268  if (m_invert[sample_pos]) bt = t_bs - bt;
269 #ifndef RRR_NO_OPT
270  if (bt == 0 or bt == t_bs)
271  { // very effective optimization
272  return bt > 0;
273  }
274 #endif
275  uint16_t off = i % t_bs; // i - bt_idx*t_bs;
276  size_type btnrp = m_btnrp[sample_pos];
277  for (size_type j = sample_pos * t_k; j < bt_idx; ++j) { btnrp += rrr_helper_type::space_for_bt(m_bt[j]); }
278  uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
279  number_type btnr = rrr_helper_type::decode_btnr(m_btnr, btnrp, btnrlen);
280  return rrr_helper_type::decode_bit(bt, btnr, off);
281  }
282 
284 
291  uint64_t get_int(size_type idx, uint8_t len = 64) const
292  {
293  uint64_t res = 0;
294  size_type bb_idx = idx / t_bs; // begin block index
295  size_type bb_off = idx % t_bs; // begin block offset
296  uint16_t bt = m_bt[bb_idx];
297  size_type sample_pos = bb_idx / t_k;
298  size_type eb_idx = (idx + len - 1) / t_bs; // end block index
299  if (bb_idx == eb_idx)
300  { // extract only in one block
301  if (m_invert[sample_pos]) bt = t_bs - bt;
302  if (bt == 0)
303  { // all bits are zero
304  res = 0;
305  }
306  else if (bt == t_bs and t_bs <= 64)
307  { // all bits are zero
308  res = bits::lo_set[len];
309  }
310  else
311  {
312  size_type btnrp = m_btnrp[sample_pos];
313  for (size_type j = sample_pos * t_k; j < bb_idx; ++j)
314  {
315  btnrp += rrr_helper_type::space_for_bt(m_bt[j]);
316  }
317  uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
318  number_type btnr = rrr_helper_type::decode_btnr(m_btnr, btnrp, btnrlen);
319  res = rrr_helper_type::decode_int(bt, btnr, bb_off, len);
320  }
321  }
322  else
323  { // solve multiple block case by recursion
324  uint16_t b_len = t_bs - bb_off; // remaining bits in first block
325  uint16_t b_len_sum = 0;
326  do {
327  res |= get_int(idx, b_len) << b_len_sum;
328  idx += b_len;
329  b_len_sum += b_len;
330  len -= b_len;
331  b_len = t_bs;
332  b_len = std::min((uint16_t)len, b_len);
333  } while (len > 0);
334  }
335  return res;
336  }
337 
339  size_type size() const { return m_size; }
340 
343  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
344  {
345  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
346  size_type written_bytes = 0;
347  written_bytes += write_member(m_size, out, child, "size");
348  written_bytes += m_bt.serialize(out, child, "bt");
349  written_bytes += m_btnr.serialize(out, child, "btnr");
350  written_bytes += m_btnrp.serialize(out, child, "btnrp");
351  written_bytes += m_rank.serialize(out, child, "rank_samples");
352  written_bytes += m_invert.serialize(out, child, "invert");
353  structure_tree::add_size(child, written_bytes);
354  return written_bytes;
355  }
356 
358  void load(std::istream & in)
359  {
360  read_member(m_size, in);
361  m_bt.load(in);
362  m_btnr.load(in);
363  m_btnrp.load(in);
364  m_rank.load(in);
365  m_invert.load(in);
366  }
367 
368  template <typename archive_t>
369  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
370  {
371  ar(CEREAL_NVP(m_size));
372  ar(CEREAL_NVP(m_bt));
373  ar(CEREAL_NVP(m_btnr));
374  ar(CEREAL_NVP(m_btnrp));
375  ar(CEREAL_NVP(m_rank));
376  ar(CEREAL_NVP(m_invert));
377  }
378 
379  template <typename archive_t>
380  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
381  {
382  ar(CEREAL_NVP(m_size));
383  ar(CEREAL_NVP(m_bt));
384  ar(CEREAL_NVP(m_btnr));
385  ar(CEREAL_NVP(m_btnrp));
386  ar(CEREAL_NVP(m_rank));
387  ar(CEREAL_NVP(m_invert));
388  }
389 
390  iterator begin() const { return iterator(this, 0); }
391 
392  iterator end() const { return iterator(this, size()); }
393 
394  bool operator==(const rrr_vector & v) const
395  {
396  return m_size == v.m_size && m_bt == v.m_bt && m_btnr == v.m_btnr && m_btnrp == v.m_btnrp &&
397  m_rank == v.m_rank && m_invert == v.m_invert;
398  }
399 
400  bool operator!=(const rrr_vector & v) const { return !(*this == v); }
401 };
402 
403 template <uint8_t t_bit_pattern>
405 {
408 };
409 
410 template <>
412 {
414  static size_type adjust_rank(size_type r, size_type n) { return n - r; }
415 };
416 
418 
428 template <uint8_t t_b, uint16_t t_bs, class t_rac, uint16_t t_k>
429 class rank_support_rrr
430 {
431  static_assert(t_b == 1u or t_b == 0u, "rank_support_rrr: bit pattern must be `0` or `1`");
432 
433  public:
438  enum
439  {
440  bit_pat = t_b
441  };
442  enum
443  {
444  bit_pat_len = (uint8_t)1
445  };
446 
447  private:
448  const bit_vector_type * m_v;
449 
450  public:
452 
454  explicit rank_support_rrr(const bit_vector_type * v = nullptr) { set_vector(v); }
455 
457 
462  const size_type rank(size_type i) const
463  {
464  assert(m_v != nullptr);
465  assert(i <= m_v->size());
466  size_type bt_idx = i / t_bs;
467  size_type sample_pos = bt_idx / t_k;
468  size_type btnrp = m_v->m_btnrp[sample_pos];
469  size_type rank = m_v->m_rank[sample_pos];
470  if (sample_pos + 1 < m_v->m_rank.size())
471  {
472  size_type diff_rank = m_v->m_rank[sample_pos + 1] - rank;
473 #ifndef RRR_NO_OPT
474  if (diff_rank == (size_type)0) { return rank_support_rrr_trait<t_b>::adjust_rank(rank, i); }
475  else if (diff_rank == (size_type)t_bs * t_k)
476  {
477  return rank_support_rrr_trait<t_b>::adjust_rank(rank + i - sample_pos * t_k * t_bs, i);
478  }
479 #endif
480  }
481  const bool inv = m_v->m_invert[sample_pos];
482  for (size_type j = sample_pos * t_k; j < bt_idx; ++j)
483  {
484  uint16_t r = m_v->m_bt[j];
485  rank += (inv ? t_bs - r : r);
486  btnrp += rrr_helper_type::space_for_bt(r);
487  }
488  uint16_t off = i % t_bs;
489  if (!off)
490  { // needed for special case: if i=size() is a multiple of t_bs
491  // the access to m_bt would cause a invalid memory access
493  }
494  uint16_t bt = inv ? t_bs - m_v->m_bt[bt_idx] : m_v->m_bt[bt_idx];
495 
496  uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
497  number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp, btnrlen);
498  uint16_t popcnt = rrr_helper_type::decode_popcount(bt, btnr, off);
500  }
501 
503  const size_type operator()(size_type i) const { return rank(i); }
504 
506  const size_type size() const { return m_v->size(); }
507 
509  void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
510 
512  {
513  if (this != &rs) { set_vector(rs.m_v); }
514  return *this;
515  }
516 
518  void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
519 
521  size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
522  {
523  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
524  structure_tree::add_size(child, 0);
525  return 0;
526  }
527 
528  template <typename archive_t>
529  void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
530  {}
531 
532  template <typename archive_t>
533  void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
534  {}
535 
536  bool operator==(const rank_support_rrr & other) const noexcept { return *m_v == *other.m_v; }
537 
538  bool operator!=(const rank_support_rrr & other) const noexcept { return !(*this == other); }
539 };
540 
542 /*
543  * \tparam t_b The bit pattern of size one. (so `0` or `1`)
544  * \tparam t_bs The block size of the corresponding rrr_vector
545  * \tparam t_rac Type used to store the block type in the corresponding rrr_vector.
546  *
547  * Possible TODO: Add heap which contains the 10 first items of
548  * each binary search could increase performance.
549  * Experiments on select_support_interleaved showed about
550  * 25%.
551  */
552 template <uint8_t t_b, uint16_t t_bs, class t_rac, uint16_t t_k>
554 {
555  static_assert(t_b == 1u or t_b == 0u, "select_support_rrr: bit pattern must be `0` or `1`");
556 
557  public:
562  enum
563  {
564  bit_pat = t_b
565  };
566  enum
567  {
568  bit_pat_len = (uint8_t)1
569  };
570 
571  private:
572  const bit_vector_type * m_v;
573 
574  size_type select1(size_type i) const
575  {
576  if (m_v->m_rank[m_v->m_rank.size() - 1] < i) return size();
577  // (1) binary search for the answer in the rank_samples
578  size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
579  size_type idx, rank;
580  // invariant: m_rank[end] >= i
581  // m_rank[begin] < i
582  while (end - begin > 1)
583  {
584  idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
585  rank = m_v->m_rank[idx];
586  if (rank >= i)
587  end = idx;
588  else
589  { // rank < i
590  begin = idx;
591  }
592  }
593  // (2) linear search between the samples
594  rank = m_v->m_rank[begin]; // now i>rank
595  idx = begin * t_k; // initialize idx for select result
596  size_type diff_rank = m_v->m_rank[end] - rank;
597 #ifndef RRR_NO_OPT
598  if (diff_rank == (size_type)t_bs * t_k)
599  { // optimisation for select<1>
600  return idx * t_bs + i - rank - 1;
601  }
602 #endif
603  const bool inv = m_v->m_invert[begin];
604  size_type btnrp = m_v->m_btnrp[begin];
605  uint16_t bt = 0, btnrlen = 0; // temp variables for block_type and space for block type
606  while (i > rank)
607  {
608  bt = m_v->m_bt[idx++];
609  bt = inv ? t_bs - bt : bt;
610  rank += bt;
611  btnrp += (btnrlen = rrr_helper_type::space_for_bt(bt));
612  }
613  rank -= bt;
614  number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp - btnrlen, btnrlen);
615  return (idx - 1) * t_bs + rrr_helper_type::decode_select(bt, btnr, i - rank);
616  }
617 
618  size_type select0(size_type i) const
619  {
620  if ((size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i) { return size(); }
621  // (1) binary search for the answer in the rank_samples
622  size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
623  size_type idx, rank;
624  // invariant: m_rank[end] >= i
625  // m_rank[begin] < i
626  while (end - begin > 1)
627  {
628  idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
629  rank = idx * t_bs * t_k - m_v->m_rank[idx];
630  if (rank >= i)
631  end = idx;
632  else
633  { // rank < i
634  begin = idx;
635  }
636  }
637  // (2) linear search between the samples
638  rank = begin * t_bs * t_k - m_v->m_rank[begin]; // now i>rank
639  idx = begin * t_k; // initialize idx for select result
640  if (m_v->m_rank[end] == m_v->m_rank[begin])
641  { // only for select<0>
642  return idx * t_bs + i - rank - 1;
643  }
644  const bool inv = m_v->m_invert[begin];
645  size_type btnrp = m_v->m_btnrp[begin];
646  uint16_t bt = 0, btnrlen = 0; // temp variables for block_type and space for block type
647  while (i > rank)
648  {
649  bt = m_v->m_bt[idx++];
650  bt = inv ? t_bs - bt : bt;
651  rank += (t_bs - bt);
652  btnrp += (btnrlen = rrr_helper_type::space_for_bt(bt));
653  }
654  rank -= (t_bs - bt);
655  number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp - btnrlen, btnrlen);
656  return (idx - 1) * t_bs + rrr_helper_type::template decode_select_bitpattern<0, 1>(bt, btnr, i - rank);
657  }
658 
659  public:
660  explicit select_support_rrr(const bit_vector_type * v = nullptr) { set_vector(v); }
661 
663  size_type select(size_type i) const { return t_b ? select1(i) : select0(i); }
664 
665  const size_type operator()(size_type i) const { return select(i); }
666 
667  const size_type size() const { return m_v->size(); }
668 
669  void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
670 
672  {
673  if (this != &rs) { set_vector(rs.m_v); }
674  return *this;
675  }
676 
677  void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
678 
679  size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
680  {
681  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
682  structure_tree::add_size(child, 0);
683  return 0;
684  }
685 
686  template <typename archive_t>
687  void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
688  {}
689 
690  template <typename archive_t>
691  void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
692  {}
693 
694  bool operator==(const select_support_rrr & other) const noexcept { return *m_v == *other.m_v; }
695 
696  bool operator!=(const select_support_rrr & other) const noexcept { return !(*this == other); }
697 };
698 
699 } // end namespace sdsl
700 #include <sdsl/rrr_vector_15.hpp> // include specialization
701 
702 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
int_vector_size_type size_type
Definition: int_vector.hpp:266
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.
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
Generic iterator for a random access container.
Definition: iterators.hpp:24
bool operator==(const rank_support_rrr &other) const noexcept
Definition: rrr_vector.hpp:536
bool operator!=(const rank_support_rrr &other) const noexcept
Definition: rrr_vector.hpp:538
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Definition: rrr_vector.hpp:431
rank_support_rrr & operator=(const rank_support_rrr &rs)
Definition: rrr_vector.hpp:511
Load the data structure from a stream and set the supported vector void load(std::istream &, const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:518
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
Definition: rrr_vector.hpp:529
rrr_helper_type::number_type number_type
Definition: rrr_vector.hpp:437
Serializes the data structure into a stream size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
Definition: rrr_vector.hpp:521
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Definition: rrr_vector.hpp:533
Standard constructor rank_support_rrr(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:454
Answers rank queries const size_type rank(size_type i) const
Definition: rrr_vector.hpp:462
bit_vector_type::rrr_helper_type rrr_helper_type
Definition: rrr_vector.hpp:436
Returns the size of the original vector const size_type size() const
Definition: rrr_vector.hpp:506
Set the supported vector void set_vector(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:509
bit_vector_type::size_type size_type
Definition: rrr_vector.hpp:435
rrr_vector(const rrr_vector &v)
Definition: rrr_vector.hpp:110
Loads the data structure from the given istream void load(std::istream &in)
Definition: rrr_vector.hpp:358
random_access_const_iterator< rrr_vector > iterator
Definition: rrr_vector.hpp:71
rank_support_rrr< 1, t_bs, t_rac, t_k > rank_1_type
Definition: rrr_vector.hpp:75
const bit_vector & btnr
Definition: rrr_vector.hpp:106
Default constructor rrr_vector()
Definition: rrr_vector.hpp:109
rank_support_rrr< 0, t_bs, t_rac, t_k > rank_0_type
Definition: rrr_vector.hpp:76
select_support_rrr< 0, t_bs, t_rac, t_k > select_0_type
Definition: rrr_vector.hpp:78
bool operator!=(const rrr_vector &v) const
Definition: rrr_vector.hpp:400
rrr_vector(rrr_vector &&v)
Definition: rrr_vector.hpp:119
rrr_vector & operator=(const rrr_vector &v)
Definition: rrr_vector.hpp:120
bool operator==(const rrr_vector &v) const
Definition: rrr_vector.hpp:394
rrr_helper_type::number_type number_type
Definition: rrr_vector.hpp:86
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: rrr_vector.hpp:369
bit_vector::difference_type difference_type
Definition: rrr_vector.hpp:69
const rac_type & bt
Definition: rrr_vector.hpp:105
rrr_helper< t_bs > rrr_helper_type
Definition: rrr_vector.hpp:85
bit_vector::size_type size_type
Definition: rrr_vector.hpp:63
Returns the size of the original bit vector size_type size() const
Definition: rrr_vector.hpp:339
iterator end() const
Definition: rrr_vector.hpp:392
Accessing the i th element of the original bit_vector value_type operator[](size_type i) const
Definition: rrr_vector.hpp:263
select_support_rrr< 1, t_bs, t_rac, t_k > select_1_type
Definition: rrr_vector.hpp:77
bv_tag index_category
Definition: rrr_vector.hpp:73
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: rrr_vector.hpp:380
Constructor rrr_vector(const bit_vector &bv)
Definition: rrr_vector.hpp:148
Answers select queries Serializes the data structure into the given ostream size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: rrr_vector.hpp:343
bit_vector::value_type value_type
Definition: rrr_vector.hpp:68
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
iterator begin() const
Definition: rrr_vector.hpp:390
iterator const_iterator
Definition: rrr_vector.hpp:72
rrr_vector & operator=(rrr_vector &&v)
Definition: rrr_vector.hpp:129
bit_vector_type::rrr_helper_type rrr_helper_type
Definition: rrr_vector.hpp:560
void set_vector(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:669
select_support_rrr(const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:660
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
Definition: rrr_vector.hpp:679
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
Definition: rrr_vector.hpp:687
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
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Definition: rrr_vector.hpp:691
rrr_helper_type::number_type number_type
Definition: rrr_vector.hpp:561
const size_type operator()(size_type i) const
Definition: rrr_vector.hpp:665
bit_vector_type::size_type size_type
Definition: rrr_vector.hpp:559
bool operator==(const select_support_rrr &other) const noexcept
Definition: rrr_vector.hpp:694
const size_type size() const
Definition: rrr_vector.hpp:667
void load(std::istream &, const bit_vector_type *v=nullptr)
Definition: rrr_vector.hpp:677
bool operator!=(const select_support_rrr &other) const noexcept
Definition: rrr_vector.hpp:696
select_support_rrr & operator=(const select_support_rrr &rs)
Definition: rrr_vector.hpp:671
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)
#define SDSL_UNUSED
Definition: config.hpp:13
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...
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 size_type adjust_rank(size_type r, size_type n)
Definition: rrr_vector.hpp:414
bit_vector::size_type size_type
Definition: rrr_vector.hpp:413
bit_vector::size_type size_type
Definition: rrr_vector.hpp:406
static size_type adjust_rank(size_type r, SDSL_UNUSED size_type n)
Definition: rrr_vector.hpp:407
Class to encode and decode binomial coefficients on the fly.
Definition: rrr_helper.hpp:281
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
Definition: rrr_helper.hpp:298
static uint16_t space_for_bt(uint16_t i)
Returns the space usage in bits of the binary representation of the number .
Definition: rrr_helper.hpp:287
static uint64_t decode_int(uint16_t k, number_type nr, uint16_t off, uint16_t len)
Decode the len-bit integer starting at position of the block encoded by the pair (k,...
Definition: rrr_helper.hpp:397
binomial::number_type number_type
The used number type, e.g.
Definition: rrr_helper.hpp:283
static number_type bin_to_nr(number_type bin)
Definition: rrr_helper.hpp:314
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
Definition: rrr_helper.hpp:504
static bool decode_bit(uint16_t k, number_type nr, uint16_t off)
Decode the bit at position of the block encoded by the pair (k, nr).
Definition: rrr_helper.hpp:337
static uint16_t get_bt(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
Definition: rrr_helper.hpp:307
static number_type decode_btnr(const bit_vector_type &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
Definition: rrr_helper.hpp:290
static uint16_t decode_popcount(uint16_t k, number_type nr, uint16_t off)
Decode the first off bits bits of the block encoded by the pair (k, nr) and return the set bits.
Definition: rrr_helper.hpp:441
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.