SDSL 3.0.1
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
22namespace sdsl
23{
24
25// forward declaration needed for friend declaration
26template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
27class rank_support_rrr; // in rrr_vector
28
29// forward declaration needed for friend declaration
30template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
31class select_support_rrr; // in rrr_vector
32
34
60template <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
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
403template <uint8_t t_bit_pattern>
405{
408};
409
410template <>
412{
414 static size_type adjust_rank(size_type r, size_type n) { return n - r; }
415};
416
418
428template <uint8_t t_b, uint16_t t_bs, class t_rac, uint16_t t_k>
429class 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);
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>
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 */
552template <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>
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:31
int_vector_size_type size_type
Definition: int_vector.hpp:229
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
Definition: int_vector.hpp:595
size_type size() const noexcept
The number of elements in the int_vector.
int_vector_trait< t_width >::value_type value_type
Definition: int_vector.hpp:221
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:521
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:434
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
rank_support_rrr & operator=(const rank_support_rrr &rs)
Definition: rrr_vector.hpp:511
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:67
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
rrr_vector & operator=(rrr_vector &&v)
Definition: rrr_vector.hpp:129
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
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:558
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
select_support_rrr & operator=(const select_support_rrr &rs)
Definition: rrr_vector.hpp:671
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
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
static void add_size(structure_tree_node *v, uint64_t value)
#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:53
rrr_helper.hpp contains the sdsl::binomial struct, a struct which contains informations about the bin...
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
static constexpr 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:187
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.