SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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>
13#include <assert.h>
14#include <iostream>
15#include <stdint.h>
16#include <string>
17
18#include <sdsl/bits.hpp>
19#include <sdsl/cereal.hpp>
20#include <sdsl/config.hpp>
21#include <sdsl/int_vector.hpp>
22#include <sdsl/io.hpp>
23#include <sdsl/iterators.hpp>
24#include <sdsl/rrr_helper.hpp>
27#include <sdsl/util.hpp>
28
30namespace sdsl
31{
32
33// forward declaration needed for friend declaration
34template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
35class rank_support_rrr; // in rrr_vector
36// forward declaration needed for friend declaration
37template <uint8_t t_b = 1, uint16_t t_bs = 15, class t_rac = int_vector<>, uint16_t t_k = 32>
38class select_support_rrr; // in rrr_vector
39
41
67template <uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
69{
70 static_assert(t_bs >= 3 and t_bs <= 256, "rrr_vector: block size t_bs must be 3 <= t_bs <= 256.");
71 static_assert(t_k > 1, "rrr_vector: t_k must be > 0.");
72
73public:
77 typedef t_rac rac_type;
81
86
87 friend class rank_support_rrr<0, t_bs, t_rac, t_k>;
88 friend class rank_support_rrr<1, t_bs, t_rac, t_k>;
89 friend class select_support_rrr<0, t_bs, t_rac, t_k>;
90 friend class select_support_rrr<1, t_bs, t_rac, t_k>;
91
94
95 enum
96 {
97 block_size = t_bs
98 };
99
100private:
101 size_type m_size = 0; // Size of the original bit_vector.
102 rac_type m_bt; // Vector for the block types (bt). bt equals the
103 // number of set bits in the block.
104 bit_vector m_btnr; // Compressed block type numbers.
105 int_vector<> m_btnrp; // Sample pointers into m_btnr.
106 int_vector<> m_rank; // Sample rank values.
107 bit_vector m_invert; // Specifies if a superblock (i.e. t_k blocks)
108 // have to be considered as inverted i.e. 1 and
109 // 0 are swapped
110
111public:
112 rac_type const & bt = m_bt;
113 bit_vector const & btnr = m_btnr;
114
118 m_size(v.m_size),
119 m_bt(v.m_bt),
120 m_btnr(v.m_btnr),
121 m_btnrp(v.m_btnrp),
122 m_rank(v.m_rank),
123 m_invert(v.m_invert)
124 {}
125
127 {
128 *this = std::move(v);
129 }
131 {
132 if (this != &v)
133 {
134 rrr_vector tmp(v); // re-use copy-constructor
135 *this = std::move(tmp); // re-use move-assignment
136 }
137 return *this;
138 }
140 {
141 if (this != &v)
142 {
143 m_size = v.m_size;
144 m_bt = std::move(v.m_bt);
145 m_btnr = std::move(v.m_btnr);
146 m_btnrp = std::move(v.m_btnrp);
147 m_rank = std::move(v.m_rank);
148 m_invert = std::move(v.m_invert);
149 }
150 return *this;
151 }
152
154
159 {
160 m_size = bv.size();
161 int_vector<> bt_array;
162 bt_array.width(bits::hi(t_bs) + 1);
163 bt_array.resize((m_size + t_bs) / ((size_type)t_bs)); // blocks for the bt_array + a dummy block at the end,
164 // if m_size%t_bs == 0
165
166 // (1) calculate the block types and store them in m_bt
167 size_type pos = 0, i = 0, x;
168 size_type btnr_pos = 0;
169 size_type sum_rank = 0;
170 while (pos + t_bs <= m_size)
171 { // handle all blocks full blocks
172 bt_array[i++] = x = rrr_helper_type::get_bt(bv, pos, t_bs);
173 sum_rank += x;
174 btnr_pos += rrr_helper_type::space_for_bt(x);
175 pos += t_bs;
176 }
177 if (pos < m_size)
178 { // handle last not full block
179 bt_array[i++] = x = rrr_helper_type::get_bt(bv, pos, m_size - pos);
180 sum_rank += x;
181 btnr_pos += rrr_helper_type::space_for_bt(x);
182 }
183 m_btnr = bit_vector(std::max(btnr_pos, (size_type)64), 0); // max necessary for case: t_bs == 1
184 m_btnrp = int_vector<>((bt_array.size() + t_k - 1) / t_k, 0, bits::hi(btnr_pos) + 1);
185 m_rank =
186 int_vector<>((bt_array.size() + t_k - 1) / t_k + ((m_size % (t_k * t_bs)) > 0), 0, bits::hi(sum_rank) + 1);
187 // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
188 // only add a finishing block, if the last block of the superblock is not a dummy block
189 m_invert = bit_vector((bt_array.size() + t_k - 1) / t_k, 0);
190
191 // (2) calculate block type numbers and pointers into btnr and rank samples
192 pos = 0;
193 i = 0;
194 btnr_pos = 0, sum_rank = 0;
195 bool invert = false;
196 while (pos + t_bs <= m_size)
197 { // handle all full blocks
198 if ((i % t_k) == (size_type)0)
199 {
200 m_btnrp[i / t_k] = btnr_pos;
201 m_rank[i / t_k] = sum_rank;
202 // calculate invert bit for that superblock
203 if (i + t_k <= bt_array.size())
204 {
205 size_type gt_half_t_bs = 0; // counter for blocks greater than half of the blocksize
206 for (size_type j = i; j < i + t_k; ++j)
207 {
208 if (bt_array[j] > t_bs / 2)
209 ++gt_half_t_bs;
210 }
211 if (gt_half_t_bs > (t_k / 2))
212 {
213 m_invert[i / t_k] = 1;
214 for (size_type j = i; j < i + t_k; ++j)
215 {
216 bt_array[j] = t_bs - bt_array[j];
217 }
218 invert = true;
219 }
220 else
221 {
222 invert = false;
223 }
224 }
225 else
226 {
227 invert = false;
228 }
229 }
230 uint16_t space_for_bt = rrr_helper_type::space_for_bt(x = bt_array[i++]);
231 sum_rank += (invert ? (t_bs - x) : x);
232 if (space_for_bt)
233 {
234 number_type bin = rrr_helper_type::decode_btnr(bv, pos, t_bs);
236 rrr_helper_type::set_bt(m_btnr, btnr_pos, nr, space_for_bt);
237 }
238 btnr_pos += space_for_bt;
239 pos += t_bs;
240 }
241 if (pos < m_size)
242 { // handle last not full block
243 if ((i % t_k) == (size_type)0)
244 {
245 m_btnrp[i / t_k] = btnr_pos;
246 m_rank[i / t_k] = sum_rank;
247 m_invert[i / t_k] = 0; // default: set last block to not inverted
248 invert = false;
249 }
250 uint16_t space_for_bt = rrr_helper_type::space_for_bt(x = bt_array[i++]);
251 // no extra dummy block added to bt_array, therefore this condition should hold
252 assert(i == bt_array.size());
253 sum_rank += invert ? (t_bs - x) : x;
254 if (space_for_bt)
255 {
256 number_type bin = rrr_helper_type::decode_btnr(bv, pos, m_size - pos);
258 rrr_helper_type::set_bt(m_btnr, btnr_pos, nr, space_for_bt);
259 }
260 btnr_pos += space_for_bt;
261 assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
262 }
263 else
264 { // handle last empty full block
265 assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
266 }
267 // for technical reasons we add a last element to m_rank
268 m_rank[m_rank.size() - 1] = sum_rank; // sum_rank contains the total number of set bits in bv
269 m_bt = bt_array;
270 }
271
273
277 {
278 size_type bt_idx = i / t_bs;
279 uint16_t bt = m_bt[bt_idx];
280 size_type sample_pos = bt_idx / t_k;
281 if (m_invert[sample_pos])
282 bt = t_bs - bt;
283#ifndef RRR_NO_OPT
284 if (bt == 0 or bt == t_bs)
285 { // very effective optimization
286 return bt > 0;
287 }
288#endif
289 uint16_t off = i % t_bs; // i - bt_idx*t_bs;
290 size_type btnrp = m_btnrp[sample_pos];
291 for (size_type j = sample_pos * t_k; j < bt_idx; ++j)
292 {
293 btnrp += rrr_helper_type::space_for_bt(m_bt[j]);
294 }
295 uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
296 number_type btnr = rrr_helper_type::decode_btnr(m_btnr, btnrp, btnrlen);
297 return rrr_helper_type::decode_bit(bt, btnr, off);
298 }
299
301
308 uint64_t get_int(size_type idx, uint8_t len = 64) const
309 {
310 uint64_t res = 0;
311 size_type bb_idx = idx / t_bs; // begin block index
312 size_type bb_off = idx % t_bs; // begin block offset
313 uint16_t bt = m_bt[bb_idx];
314 size_type sample_pos = bb_idx / t_k;
315 size_type eb_idx = (idx + len - 1) / t_bs; // end block index
316 if (bb_idx == eb_idx)
317 { // extract only in one block
318 if (m_invert[sample_pos])
319 bt = t_bs - bt;
320 if (bt == 0)
321 { // all bits are zero
322 res = 0;
323 }
324 else if (bt == t_bs and t_bs <= 64)
325 { // all bits are zero
326 res = bits::lo_set[len];
327 }
328 else
329 {
330 size_type btnrp = m_btnrp[sample_pos];
331 for (size_type j = sample_pos * t_k; j < bb_idx; ++j)
332 {
333 btnrp += rrr_helper_type::space_for_bt(m_bt[j]);
334 }
335 uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
336 number_type btnr = rrr_helper_type::decode_btnr(m_btnr, btnrp, btnrlen);
337 res = rrr_helper_type::decode_int(bt, btnr, bb_off, len);
338 }
339 }
340 else
341 { // solve multiple block case by recursion
342 uint16_t b_len = t_bs - bb_off; // remaining bits in first block
343 uint16_t b_len_sum = 0;
344 do
345 {
346 res |= get_int(idx, b_len) << b_len_sum;
347 idx += b_len;
348 b_len_sum += b_len;
349 len -= b_len;
350 b_len = t_bs;
351 b_len = std::min((uint16_t)len, b_len);
352 }
353 while (len > 0);
354 }
355 return res;
356 }
357
360 {
361 return m_size;
362 }
363
366 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
367 {
368 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
369 size_type written_bytes = 0;
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 written_bytes += m_invert.serialize(out, child, "invert");
376 structure_tree::add_size(child, written_bytes);
377 return written_bytes;
378 }
379
381 void load(std::istream & in)
382 {
383 read_member(m_size, in);
384 m_bt.load(in);
385 m_btnr.load(in);
386 m_btnrp.load(in);
387 m_rank.load(in);
388 m_invert.load(in);
389 }
390
391 template <typename archive_t>
392 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
393 {
394 ar(CEREAL_NVP(m_size));
395 ar(CEREAL_NVP(m_bt));
396 ar(CEREAL_NVP(m_btnr));
397 ar(CEREAL_NVP(m_btnrp));
398 ar(CEREAL_NVP(m_rank));
399 ar(CEREAL_NVP(m_invert));
400 }
401
402 template <typename archive_t>
403 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
404 {
405 ar(CEREAL_NVP(m_size));
406 ar(CEREAL_NVP(m_bt));
407 ar(CEREAL_NVP(m_btnr));
408 ar(CEREAL_NVP(m_btnrp));
409 ar(CEREAL_NVP(m_rank));
410 ar(CEREAL_NVP(m_invert));
411 }
412
414 {
415 return iterator(this, 0);
416 }
417
418 iterator end() const
419 {
420 return iterator(this, size());
421 }
422
423 bool operator==(rrr_vector const & v) const
424 {
425 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
426 && m_invert == v.m_invert;
427 }
428
429 bool operator!=(rrr_vector const & v) const
430 {
431 return !(*this == v);
432 }
433};
434
435template <uint8_t t_bit_pattern>
444
445template <>
447{
450 {
451 return n - r;
452 }
453};
454
456
466template <uint8_t t_b, uint16_t t_bs, class t_rac, uint16_t t_k>
467class rank_support_rrr
468{
469 static_assert(t_b == 1u or t_b == 0u, "rank_support_rrr: bit pattern must be `0` or `1`");
470
471public:
476 enum
477 {
478 bit_pat = t_b
479 };
480 enum
481 {
482 bit_pat_len = (uint8_t)1
483 };
484
485private:
486 bit_vector_type const * m_v;
487
488public:
490
492 explicit rank_support_rrr(bit_vector_type const * v = nullptr)
493 {
494 set_vector(v);
495 }
496
498
503 const size_type rank(size_type i) const
504 {
505 assert(m_v != nullptr);
506 assert(i <= m_v->size());
507 size_type bt_idx = i / t_bs;
508 size_type sample_pos = bt_idx / t_k;
509 size_type btnrp = m_v->m_btnrp[sample_pos];
510 size_type rank = m_v->m_rank[sample_pos];
511 if (sample_pos + 1 < m_v->m_rank.size())
512 {
513 size_type diff_rank = m_v->m_rank[sample_pos + 1] - rank;
514#ifndef RRR_NO_OPT
515 if (diff_rank == (size_type)0)
516 {
518 }
519 else if (diff_rank == (size_type)t_bs * t_k)
520 {
521 return rank_support_rrr_trait<t_b>::adjust_rank(rank + i - sample_pos * t_k * t_bs, i);
522 }
523#endif
524 }
525 bool const inv = m_v->m_invert[sample_pos];
526 for (size_type j = sample_pos * t_k; j < bt_idx; ++j)
527 {
528 uint16_t r = m_v->m_bt[j];
529 rank += (inv ? t_bs - r : r);
531 }
532 uint16_t off = i % t_bs;
533 if (!off)
534 { // needed for special case: if i=size() is a multiple of t_bs
535 // the access to m_bt would cause a invalid memory access
537 }
538 uint16_t bt = inv ? t_bs - m_v->m_bt[bt_idx] : m_v->m_bt[bt_idx];
539
540 uint16_t btnrlen = rrr_helper_type::space_for_bt(bt);
541 number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp, btnrlen);
542 uint16_t popcnt = rrr_helper_type::decode_popcount(bt, btnr, off);
544 }
545
547 const size_type operator()(size_type i) const
548 {
549 return rank(i);
550 }
551
553 const size_type size() const
554 {
555 return m_v->size();
556 }
557
559 void set_vector(bit_vector_type const * v = nullptr)
560 {
561 m_v = v;
562 }
563
565 {
566 if (this != &rs)
567 {
568 set_vector(rs.m_v);
569 }
570 return *this;
571 }
572
574 void load(std::istream &, bit_vector_type const * v = nullptr)
575 {
576 set_vector(v);
577 }
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>
593 {}
594
595 bool operator==(rank_support_rrr const & other) const noexcept
596 {
597 return *m_v == *other.m_v;
598 }
599
600 bool operator!=(rank_support_rrr const & other) const noexcept
601 {
602 return !(*this == other);
603 }
604};
605
607/*
608 * \tparam t_b The bit pattern of size one. (so `0` or `1`)
609 * \tparam t_bs The block size of the corresponding rrr_vector
610 * \tparam t_rac Type used to store the block type in the corresponding rrr_vector.
611 *
612 * Possible TODO: Add heap which contains the 10 first items of
613 * each binary search could increase performance.
614 * Experiments on select_support_interleaved showed about
615 * 25%.
616 */
617template <uint8_t t_b, uint16_t t_bs, class t_rac, uint16_t t_k>
619{
620 static_assert(t_b == 1u or t_b == 0u, "select_support_rrr: bit pattern must be `0` or `1`");
621
622public:
627 enum
628 {
629 bit_pat = t_b
630 };
631 enum
632 {
633 bit_pat_len = (uint8_t)1
634 };
635
636private:
637 bit_vector_type const * m_v;
638
639 size_type select1(size_type i) const
640 {
641 if (m_v->m_rank[m_v->m_rank.size() - 1] < i)
642 return size();
643 // (1) binary search for the answer in the rank_samples
644 size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
645 size_type idx, rank;
646 // invariant: m_rank[end] >= i
647 // m_rank[begin] < i
648 while (end - begin > 1)
649 {
650 idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
651 rank = m_v->m_rank[idx];
652 if (rank >= i)
653 end = idx;
654 else
655 { // rank < i
656 begin = idx;
657 }
658 }
659 // (2) linear search between the samples
660 rank = m_v->m_rank[begin]; // now i>rank
661 idx = begin * t_k; // initialize idx for select result
662 size_type diff_rank = m_v->m_rank[end] - rank;
663#ifndef RRR_NO_OPT
664 if (diff_rank == (size_type)t_bs * t_k)
665 { // optimisation for select<1>
666 return idx * t_bs + i - rank - 1;
667 }
668#endif
669 bool const inv = m_v->m_invert[begin];
670 size_type btnrp = m_v->m_btnrp[begin];
671 uint16_t bt = 0, btnrlen = 0; // temp variables for block_type and space for block type
672 while (i > rank)
673 {
674 bt = m_v->m_bt[idx++];
675 bt = inv ? t_bs - bt : bt;
676 rank += bt;
677 btnrp += (btnrlen = rrr_helper_type::space_for_bt(bt));
678 }
679 rank -= bt;
680 number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp - btnrlen, btnrlen);
681 return (idx - 1) * t_bs + rrr_helper_type::decode_select(bt, btnr, i - rank);
682 }
683
684 size_type select0(size_type i) const
685 {
686 if ((size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i)
687 {
688 return size();
689 }
690 // (1) binary search for the answer in the rank_samples
691 size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
692 size_type idx, rank;
693 // invariant: m_rank[end] >= i
694 // m_rank[begin] < i
695 while (end - begin > 1)
696 {
697 idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
698 rank = idx * t_bs * t_k - m_v->m_rank[idx];
699 if (rank >= i)
700 end = idx;
701 else
702 { // rank < i
703 begin = idx;
704 }
705 }
706 // (2) linear search between the samples
707 rank = begin * t_bs * t_k - m_v->m_rank[begin]; // now i>rank
708 idx = begin * t_k; // initialize idx for select result
709 if (m_v->m_rank[end] == m_v->m_rank[begin])
710 { // only for select<0>
711 return idx * t_bs + i - rank - 1;
712 }
713 bool const inv = m_v->m_invert[begin];
714 size_type btnrp = m_v->m_btnrp[begin];
715 uint16_t bt = 0, btnrlen = 0; // temp variables for block_type and space for block type
716 while (i > rank)
717 {
718 bt = m_v->m_bt[idx++];
719 bt = inv ? t_bs - bt : bt;
720 rank += (t_bs - bt);
721 btnrp += (btnrlen = rrr_helper_type::space_for_bt(bt));
722 }
723 rank -= (t_bs - bt);
724 number_type btnr = rrr_helper_type::decode_btnr(m_v->m_btnr, btnrp - btnrlen, btnrlen);
725 return (idx - 1) * t_bs + rrr_helper_type::template decode_select_bitpattern<0, 1>(bt, btnr, i - rank);
726 }
727
728public:
729 explicit select_support_rrr(bit_vector_type const * v = nullptr)
730 {
731 set_vector(v);
732 }
733
736 {
737 return t_b ? select1(i) : select0(i);
738 }
739
741 {
742 return select(i);
743 }
744
745 const size_type size() const
746 {
747 return m_v->size();
748 }
749
750 void set_vector(bit_vector_type const * v = nullptr)
751 {
752 m_v = v;
753 }
754
756 {
757 if (this != &rs)
758 {
759 set_vector(rs.m_v);
760 }
761 return *this;
762 }
763
764 void load(std::istream &, bit_vector_type const * v = nullptr)
765 {
766 set_vector(v);
767 }
768
769 size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
770 {
771 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
772 structure_tree::add_size(child, 0);
773 return 0;
774 }
775
776 template <typename archive_t>
777 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
778 {}
779
780 template <typename archive_t>
782 {}
783
784 bool operator==(select_support_rrr const & other) const noexcept
785 {
786 return *m_v == *other.m_v;
787 }
788
789 bool operator!=(select_support_rrr const & other) const noexcept
790 {
791 return !(*this == other);
792 }
793};
794
795} // end namespace sdsl
796
797#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
int_vector_size_type size_type
void load(std::istream &in)
Load the int_vector for a stream.
uint8_t width() const noexcept
Returns the width of the integers which are accessed via the [] operator.
size_type size() const noexcept
The number of elements in the int_vector.
int_vector_trait< t_width >::value_type value_type
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.
Generic iterator for a random access container.
Definition iterators.hpp:24
rank_support_rrr & operator=(rank_support_rrr const &rs)
Standard constructor rank_support_rrr(bit_vector_type const *v=nullptr)
Load the data structure from a stream and set the supported vector void load(std::istream &, bit_vector_type const *v=nullptr)
bool operator!=(rank_support_rrr const &other) const noexcept
bool operator==(rank_support_rrr const &other) const noexcept
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
rrr_helper_type::number_type number_type
Serializes the data structure into a stream size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Answers rank queries const size_type rank(size_type i) const
bit_vector_type::rrr_helper_type rrr_helper_type
Returns the size of the original vector const size_type size() const
bit_vector_type::size_type size_type
Set the supported vector void set_vector(bit_vector_type const *v=nullptr)
Loads the data structure from the given istream void load(std::istream &in)
random_access_const_iterator< rrr_vector > iterator
rank_support_rrr< 1, t_bs, t_rac, t_k > rank_1_type
Default constructor rrr_vector()
rank_support_rrr< 0, t_bs, t_rac, t_k > rank_0_type
select_support_rrr< 0, t_bs, t_rac, t_k > select_0_type
Constructor rrr_vector(bit_vector const &bv)
rrr_vector(rrr_vector &&v)
rrr_helper_type::number_type number_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
bit_vector::difference_type difference_type
rrr_helper< t_bs > rrr_helper_type
bit_vector::size_type size_type
Returns the size of the original bit vector size_type size() const
iterator end() const
rrr_vector & operator=(rrr_vector &&v)
bit_vector const & btnr
Accessing the i th element of the original bit_vector value_type operator[](size_type i) const
bool operator==(rrr_vector const &v) const
rrr_vector & operator=(rrr_vector const &v)
rac_type const & bt
select_support_rrr< 1, t_bs, t_rac, t_k > select_1_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bool operator!=(rrr_vector const &v) const
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
bit_vector::value_type value_type
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
iterator begin() const
iterator const_iterator
rrr_vector(rrr_vector const &v)
bit_vector_type::rrr_helper_type rrr_helper_type
select_support_rrr(bit_vector_type const *v=nullptr)
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void set_vector(bit_vector_type const *v=nullptr)
bool operator!=(select_support_rrr const &other) const noexcept
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers select queries size_type select(size_type i) const
void load(std::istream &, bit_vector_type const *v=nullptr)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
select_support_rrr & operator=(select_support_rrr const &rs)
rrr_helper_type::number_type number_type
const size_type operator()(size_type i) const
bit_vector_type::size_type size_type
const size_type size() const
bool operator==(select_support_rrr const &other) const noexcept
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
#define SDSL_UNUSED
Definition config.hpp:12
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
Definition io.hpp:94
void read_member(T &t, std::istream &in)
Definition io.hpp:119
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
rrr_helper.hpp contains the sdsl::binomial struct, a struct which contains informations about the bin...
Contains declarations and definitions of data structure concepts.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
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:194
static size_type adjust_rank(size_type r, size_type n)
bit_vector::size_type size_type
bit_vector::size_type size_type
static size_type adjust_rank(size_type r, SDSL_UNUSED size_type n)
Class to encode and decode binomial coefficients on the fly.
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
static uint16_t space_for_bt(uint16_t i)
Returns the space usage in bits of the binary representation of the number .
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,...
binomial::number_type number_type
The used number type, e.g.
static number_type bin_to_nr(number_type bin)
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
static number_type decode_btnr(bit_vector_type const &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
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).
static uint16_t get_bt(bit_vector_type const &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
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.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.