SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
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 <assert.h>
14#include <iostream>
15#include <stdint.h>
16#include <string>
17#include <utility>
18#include <vector>
19
20#include <sdsl/bits.hpp>
21#include <sdsl/cereal.hpp>
22#include <sdsl/int_vector.hpp>
23#include <sdsl/io.hpp>
24#include <sdsl/iterators.hpp>
25#include <sdsl/rrr_vector.hpp>
28#include <sdsl/util.hpp>
30namespace sdsl
31{
32
33// Helper class for the binomial coefficients \f$ 15 \choose k \f$
34/*
35 * Size of lookup tables:
36 * * m_nr_to_bin: 64 kB = (2^15 entries x 2 bytes)
37 * * m_bin_to_nr: 64 kB = (2^15 entries x 2 bytes)
38 */
39template <typename T = void>
41{
42public:
43 typedef uint32_t number_type;
44
45private:
46 static class impl
47 {
48 public:
49 static int const n = 15;
50 static int const MAX_SIZE = 32;
51 uint8_t m_space_for_bt[16];
52 uint8_t m_space_for_bt_pair[256];
53 uint64_t m_C[MAX_SIZE];
54 int_vector<16> m_nr_to_bin;
55 int_vector<16> m_bin_to_nr;
56
57 impl()
58 {
59 m_nr_to_bin.resize(1 << n);
60 m_bin_to_nr.resize(1 << n);
61 for (int i = 0, cnt = 0, class_cnt = 0; i <= n; ++i)
62 {
63 m_C[i] = cnt;
64 class_cnt = 0;
65 std::vector<bool> b(n, 0);
66 for (int j = 0; j < i; ++j)
67 b[n - j - 1] = 1;
68 do
69 {
70 uint32_t x = 0;
71 for (int k = 0; k < n; ++k)
72 x |= ((uint32_t)b[n - k - 1]) << (n - 1 - k);
73 m_nr_to_bin[cnt] = x;
74 m_bin_to_nr[x] = class_cnt;
75 ++cnt;
76 ++class_cnt;
77 }
78 while (next_permutation(b.begin(), b.end()));
79 if (class_cnt == 1)
80 m_space_for_bt[i] = 0;
81 else
82 m_space_for_bt[i] = bits::hi(class_cnt) + 1;
83 }
84 if (n == 15)
85 {
86 for (int x = 0; x < 256; ++x)
87 {
88 m_space_for_bt_pair[x] = m_space_for_bt[x >> 4] + m_space_for_bt[x & 0x0F];
89 }
90 }
91 }
92 } iii;
93
94public:
95 static inline uint8_t space_for_bt(uint32_t i)
96 {
97 return iii.m_space_for_bt[i];
98 }
99
100 static inline uint32_t nr_to_bin(uint8_t k, uint32_t nr)
101 {
102 return iii.m_nr_to_bin[iii.m_C[k] + nr];
103 }
104
105 static inline uint32_t bin_to_nr(uint32_t bin)
106 {
107 return iii.m_bin_to_nr[bin];
108 }
109
110 static inline uint8_t space_for_bt_pair(uint8_t x)
111 {
112 return iii.m_space_for_bt_pair[x];
113 }
114};
115
116// initialize the inner class
117template <typename T>
118typename binomial15_impl<T>::impl binomial15_impl<T>::iii;
119
121
123
134template <class t_rac, uint16_t t_k>
135class rrr_vector<15, t_rac, t_k>
136{
137public:
141 typedef t_rac rac_type;
144
145 friend class rank_support_rrr<0, 15, t_rac, t_k>;
146 friend class rank_support_rrr<1, 15, t_rac, t_k>;
147 friend class select_support_rrr<0, 15, t_rac, t_k>;
148 friend class select_support_rrr<1, 15, t_rac, t_k>;
149
154
155 enum
156 {
157 block_size = 15
158 };
160
161private:
162 size_type m_size = 0; // Size of the original bit_vector.
163 rac_type m_bt; // Vector for block types (bt). bt equals the
164 // number of set bits in the block.
165 bit_vector m_btnr; // Compressed block type numbers.
166 int_vector<> m_btnrp; // Sample pointers into m_btnr.
167 int_vector<> m_rank; // Sample rank values.
168
169public:
170 rac_type const & bt = m_bt;
171 bit_vector const & btnr = m_btnr;
172
174
177
180 m_size(v.m_size),
181 m_bt(v.m_bt),
182 m_btnr(v.m_btnr),
183 m_btnrp(v.m_btnrp),
184 m_rank(v.m_rank)
185 {}
186
189 {
190 *this = std::move(v);
191 }
192
195 {
196 if (this != &v)
197 {
198 rrr_vector tmp(v);
199 *this = std::move(tmp);
200 }
201 return *this;
202 }
203
206 {
207 if (this != &v)
208 {
209 m_size = v.m_size;
210 m_bt = std::move(v.m_bt);
211 m_btnr = std::move(v.m_btnr);
212 m_btnrp = std::move(v.m_btnrp);
213 m_rank = std::move(v.m_rank);
214 }
215 return *this;
216 }
217
219
224 {
225 m_size = bv.size();
226 int_vector<> bt_array;
227 bt_array = int_vector<>(m_size / block_size + 1, 0, bits::hi(block_size) + 1);
228
229 // (1) calculate the block types and store them in m_bt
230 size_type pos = 0, i = 0, x;
231 size_type btnr_pos = 0;
232 size_type sum_rank = 0;
233 while (pos + block_size <= m_size)
234 { // handle all full blocks
235 bt_array[i++] = x = bits::cnt(bv.get_int(pos, block_size));
236 sum_rank += x;
237 btnr_pos += bi_type::space_for_bt(x);
238 pos += block_size;
239 }
240 if (pos < m_size)
241 { // handle last full block
242 bt_array[i++] = x = bits::cnt(bv.get_int(pos, m_size - pos));
243 sum_rank += x;
244 btnr_pos += bi_type::space_for_bt(x);
245 }
246 m_btnr = bit_vector(std::max(btnr_pos, (size_type)64), 0); // max necessary for case: block_size == 1
247 m_btnrp = int_vector<>((bt_array.size() + t_k - 1) / t_k, 0, bits::hi(btnr_pos) + 1);
248
249 m_rank = int_vector<>((bt_array.size() + t_k - 1) / t_k + ((m_size % (t_k * block_size)) > 0),
250 0,
251 bits::hi(sum_rank) + 1);
252 // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
253 // only add a finishing block, if the last
254 // block of the superblock is not a dummy
255 // block
256 // (2) calculate block type numbers and pointers into btnr and rank samples
257 pos = 0;
258 i = 0;
259 btnr_pos = 0, sum_rank = 0;
260 while (pos + block_size <= m_size)
261 { // handle all full blocks
262 if ((i % t_k) == 0)
263 {
264 m_btnrp[i / t_k] = btnr_pos;
265 m_rank[i / t_k] = sum_rank;
266 }
267 uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
268 sum_rank += x;
269 if (space_for_bt)
270 {
271 m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, block_size)), space_for_bt);
272 }
273 btnr_pos += space_for_bt;
274 pos += block_size;
275 }
276 if (pos < m_size)
277 { // handle last not full block
278 if ((i % t_k) == 0)
279 {
280 m_btnrp[i / t_k] = btnr_pos;
281 m_rank[i / t_k] = sum_rank;
282 }
283 uint16_t space_for_bt = bi_type::space_for_bt(x = bt_array[i++]);
284 sum_rank += x;
285 if (space_for_bt)
286 {
287 m_btnr.set_int(btnr_pos, bi_type::bin_to_nr(bv.get_int(pos, m_size - pos)), space_for_bt);
288 }
289 btnr_pos += space_for_bt;
290 assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
291 }
292 else
293 { // handle last empty full block
294 assert(m_rank.size() - 1 == ((i + t_k - 1) / t_k));
295 }
296 // for technical reasons add an additional element to m_rank
297 m_rank[m_rank.size() - 1] = sum_rank; // sum_rank contains the total number of set bits in bv
298 m_bt = rac_type(std::move(bt_array));
299 }
300
302
306 {
307 size_type bt_idx = i / block_size;
308 uint8_t * bt = (uint8_t *)(m_bt.data());
309 uint32_t i_bt = *(bt + (bt_idx / 2));
310 if (bt_idx % 2 == 1)
311 {
312 i_bt >>= 4;
313 }
314 else
315 {
316 i_bt &= 0x0F;
317 }
318 if (i_bt == 0 or i_bt == block_size)
319 {
320 return i_bt > 0;
321 }
322 size_type sample_pos = bt_idx / t_k;
323 size_type btnrp = m_btnrp[sample_pos];
324 size_type j = (sample_pos * t_k);
325 bt += j / 2;
326 if (j % 2 == 1 and j < bt_idx)
327 {
328 btnrp += bi_type::space_for_bt((*bt++) >> 4);
329 ++j;
330 }
331 while (j + 1 < bt_idx)
332 {
333 btnrp += bi_type::space_for_bt_pair(*(bt++)); // decode two entries at once
334 j += 2;
335 }
336 if (j < bt_idx)
337 {
338 btnrp += bi_type::space_for_bt((*bt) & 0x0F);
339 }
340
341 uint32_t btnr = m_btnr.get_int(btnrp, bi_type::space_for_bt(i_bt));
342
343 uint8_t off = (uint8_t)(i % block_size); // i - bt_idx*block_size;
344 return (bi_type::nr_to_bin(i_bt, btnr) >> off) & (uint32_t)1;
345 }
346
348
355 uint64_t get_int(size_type idx, uint8_t len = 64) const
356 {
357 uint64_t res = 0;
358 size_type bb_idx = idx / block_size; // begin block index
359 size_type bb_off = idx % block_size; // begin block offset
360 uint16_t bt = m_bt[bb_idx];
361 size_type sample_pos = bb_idx / t_k;
362 size_type eb_idx = (idx + len - 1) / block_size; // end block index
363 if (bb_idx == eb_idx)
364 { // extract only in one block
365 if (bt == 0)
366 { // all bits are zero
367 res = 0;
368 }
369 else if (bt == block_size)
370 { // all bits are zero
371 res = bits::lo_set[len];
372 }
373 else
374 {
375 size_type btnrp = m_btnrp[sample_pos];
376 for (size_type j = sample_pos * t_k; j < bb_idx; ++j)
377 {
378 btnrp += bi_type::space_for_bt(m_bt[j]);
379 }
380 uint32_t btnr = m_btnr.get_int(btnrp, bi_type::space_for_bt(bt));
381 res = (bi_type::nr_to_bin(bt, btnr) >> bb_off) & bits::lo_set[len];
382 }
383 }
384 else
385 { // solve multiple block case by recursion
386 uint8_t b_len = block_size - bb_off;
387 uint8_t b_len_sum = 0;
388 do
389 {
390 res |= get_int(idx, b_len) << b_len_sum;
391 idx += b_len;
392 b_len_sum += b_len;
393 len -= b_len;
394 b_len = block_size;
395 b_len = std::min(len, b_len);
396 }
397 while (len > 0);
398 }
399 return res;
400 }
401
404 {
405 return m_size;
406 }
407
409 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
410 {
411 size_type written_bytes = 0;
412 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
413 written_bytes += write_member(m_size, out, child, "size");
414 written_bytes += m_bt.serialize(out, child, "bt");
415 written_bytes += m_btnr.serialize(out, child, "btnr");
416 written_bytes += m_btnrp.serialize(out, child, "btnrp");
417 written_bytes += m_rank.serialize(out, child, "rank_samples");
418 structure_tree::add_size(child, written_bytes);
419 return written_bytes;
420 }
421
423 void load(std::istream & in)
424 {
425 read_member(m_size, in);
426 m_bt.load(in);
427 m_btnr.load(in);
428 m_btnrp.load(in);
429 m_rank.load(in);
430 }
431
432 template <typename archive_t>
433 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
434 {
435 ar(CEREAL_NVP(m_size));
436 ar(CEREAL_NVP(m_bt));
437 ar(CEREAL_NVP(m_btnr));
438 ar(CEREAL_NVP(m_btnrp));
439 ar(CEREAL_NVP(m_rank));
440 }
441
442 template <typename archive_t>
443 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
444 {
445 ar(CEREAL_NVP(m_size));
446 ar(CEREAL_NVP(m_bt));
447 ar(CEREAL_NVP(m_btnr));
448 ar(CEREAL_NVP(m_btnrp));
449 ar(CEREAL_NVP(m_rank));
450 }
451
453 {
454 return iterator(this, 0);
455 }
456
457 iterator end() const
458 {
459 return iterator(this, size());
460 }
461
462 bool operator==(rrr_vector const & v) const
463 {
464 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;
465 }
466
467 bool operator!=(rrr_vector const & v) const
468 {
469 return !(*this == v);
470 }
471};
472
474
476template <uint8_t t_b, class t_rac, uint16_t t_k>
477class rank_support_rrr<t_b, 15, t_rac, t_k>
478{
479 static_assert(t_b == 1u or t_b == 0u, "rank_support_rrr: bit pattern must be `0` or `1`");
480
481public:
485 enum
486 {
487 bit_pat = t_b
488 };
489 enum
490 {
491 bit_pat_len = (uint8_t)1
492 };
493
494private:
495 bit_vector_type const * m_v;
496 // TODO cache for sequential ranks
497 // mutable size_type m_last_bt;
498 // mutable size_type m_last_w; // store the last decoded word
499 // uint16_t m_space_for_bt[256];
500
501public:
503
505 explicit rank_support_rrr(bit_vector_type const * v = nullptr)
506 {
507 set_vector(v);
508 }
509
511
516 const size_type rank(size_type i) const
517 {
519 size_type sample_pos = bt_idx / t_k;
520 size_type btnrp = m_v->m_btnrp[sample_pos];
521 size_type rank = m_v->m_rank[sample_pos];
522 if (sample_pos + 1 < m_v->m_rank.size())
523 {
524 size_type diff_rank = m_v->m_rank[sample_pos + 1] - rank;
525 if (diff_rank == 0)
526 {
528 }
529 else if (diff_rank == (size_type)bit_vector_type::block_size * t_k)
530 {
532 - sample_pos * t_k * bit_vector_type::block_size,
533 i);
534 }
535 }
536 uint8_t * bt = (uint8_t *)(m_v->m_bt.data());
537
538 uint8_t last_bt = *(bt + (bt_idx / 2));
539 if (bt_idx % 2 == 1)
540 {
541 last_bt >>= 4;
542 }
543 else
544 {
545 last_bt &= 0x0F;
546 }
547 // if the final block type consists only of ones or zeros, we don't have to
548 // calculate the position pointer and can sum up rank in 64 bit chunks
549 if (last_bt == 0 or last_bt == 15)
550 {
551 if (last_bt == 15)
553 size_type j = (sample_pos * t_k) << 2;
554 bt_idx = bt_idx << 2;
555 if (bt_idx == j)
557 // now j < bt_idx
558 uint64_t const * bt64 = m_v->m_bt.data() + (j >> 6); // get the word of the start
559 uint8_t bt64_off = j & 0x3F; // get the offset in the word of the start
560 uint64_t const * bt64_end = m_v->m_bt.data() + (bt_idx >> 6);
561 uint8_t bt64_end_off = bt_idx & 0x3F;
562 // Case (1)
563 if (bt64 == bt64_end)
564 {
565 uint64_t w = ((*bt64) >> bt64_off) & bits::lo_set[bt64_end_off - bt64_off];
566 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
567 rank += ((0x0101010101010101ull * w) >> 56);
568 }
569 else
570 { // Case (2)
571 uint64_t w = ((*bt64) >> bt64_off);
572 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
573 rank += ((0x0101010101010101ull * w) >> 56);
574 while ((++bt64) != bt64_end)
575 {
576 w = *bt64;
577 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
578 rank += ((0x0101010101010101ull * w) >> 56);
579 }
580 // now bt64 == bt64_end
581 if (bt64_end_off > 0)
582 {
583 w = *bt64 << (64 - bt64_end_off);
584 w = (w & 0x0f0f0f0f0f0f0f0full) + ((w >> 4) & 0x0f0f0f0f0f0f0f0full);
585 rank += ((0x0101010101010101ull * w) >> 56);
586 }
587 }
588 return rank_support_rrr_trait<t_b>::adjust_rank(rank, i); // necessary
589 }
590 size_type j = sample_pos * t_k;
591 bt += j / 2;
592 if (j % 2 == 1 and j < bt_idx)
593 {
594 const uint8_t r = (*bt++) >> 4;
595 rank += r;
596 btnrp += bi_type::space_for_bt(r);
597 ++j;
598 }
599 while (j + 1 < bt_idx)
600 {
601 const uint8_t r = *(bt++);
602 rank += (r >> 4) + (r & 0x0F);
603 btnrp += bi_type::space_for_bt_pair(r); // decode two entries at once
604 j += 2;
605 }
606 if (j < bt_idx)
607 {
608 const uint8_t r = (*bt);
609 rank += r & 0x0F;
610 btnrp += bi_type::space_for_bt(r & 0x0F);
611 ++j;
612 }
613 uint8_t off = i % bit_vector_type::block_size; // i - bt_idx*bit_vector_type::block_size;
614 if (!off)
615 { // needed for special case: if i=size() is a multiple of block_size
616 // the access to m_bt would cause a invalid memory access
618 }
619 uint32_t btnr = m_v->m_btnr.get_int(btnrp, bi_type::space_for_bt(last_bt));
621 rank + bits::cnt(((uint64_t)(bi_type::nr_to_bin(last_bt, btnr))) & bits::lo_set[off]),
622 i);
623 }
624
627 {
628 return rank(i);
629 }
630
632 const size_type size() const
633 {
634 return m_v->size();
635 }
636
638 void set_vector(bit_vector_type const * v = nullptr)
639 {
640 m_v = v;
641 }
642
644 {
645 if (this != &rs)
646 {
647 set_vector(rs.m_v);
648 }
649 return *this;
650 }
651
653 void load(std::istream &, bit_vector_type const * v = nullptr)
654 {
655 set_vector(v);
656 }
657
659 size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
660 {
661 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
662 structure_tree::add_size(child, 0);
663 return 0;
664 }
665
666 template <typename archive_t>
667 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
668 {}
669
670 template <typename archive_t>
672 {}
673
674 bool operator==(rank_support_rrr const & other) const noexcept
675 {
676 return *m_v == *other.m_v;
677 }
678
679 bool operator!=(rank_support_rrr const & other) const noexcept
680 {
681 return !(*this == other);
682 }
683};
684
686template <uint8_t t_b, class t_rac, uint16_t t_k>
687class select_support_rrr<t_b, 15, t_rac, t_k>
688{
689 static_assert(t_b == 1u or t_b == 0u, "select_support_rrr: bit pattern must be `0` or `1`");
690
691public:
695 enum
696 {
697 bit_pat = t_b
698 };
699 enum
700 {
701 bit_pat_len = (uint8_t)1
702 };
703
704private:
705 bit_vector_type const * m_v;
706
707 // TODO: hinted binary search
708 size_type select1(size_type i) const
709 {
710 if (m_v->m_rank[m_v->m_rank.size() - 1] < i)
711 return size();
712 // (1) binary search for the answer in the rank_samples
713 size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
714 size_type idx, rank;
715 // invariant: m_rank[end] >= i
716 // m_rank[begin] < i
717 while (end - begin > 1)
718 {
719 idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
720 rank = m_v->m_rank[idx];
721 if (rank >= i)
722 end = idx;
723 else
724 { // rank < i
725 begin = idx;
726 }
727 }
728 // (2) linear search between the samples
729 rank = m_v->m_rank[begin]; // now i>rank
730 idx = begin * t_k; // initialize idx for select result
731 size_type diff_rank = m_v->m_rank[end] - rank;
732 if (diff_rank == (size_type)bit_vector_type::block_size * t_k)
733 { // optimisation for select<1>
734 return idx * bit_vector_type::block_size + i - rank - 1;
735 }
736 size_type btnrp = m_v->m_btnrp[begin];
737 uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type
738 while (i > rank)
739 {
740 bt = m_v->m_bt[idx++];
741 rank += bt;
742 btnrp += (s = bi_type::space_for_bt(bt));
743 }
744 rank -= bt;
745 uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
746 return (idx - 1) * bit_vector_type::block_size + bits::sel(bi_type::nr_to_bin(bt, btnr), i - rank);
747 }
748
749 // TODO: hinted binary search
750 size_type select0(size_type i) const
751 {
752 if ((size() - m_v->m_rank[m_v->m_rank.size() - 1]) < i)
753 return size();
754 // (1) binary search for the answer in the rank_samples
755 size_type begin = 0, end = m_v->m_rank.size() - 1; // min included, max excluded
756 size_type idx, rank;
757 // invariant: m_rank[end] >= i
758 // m_rank[begin] < i
759 while (end - begin > 1)
760 {
761 idx = (begin + end) >> 1; // idx in [0..m_rank.size()-1]
762 rank = idx * bit_vector_type::block_size * t_k - m_v->m_rank[idx];
763 if (rank >= i)
764 end = idx;
765 else
766 { // rank < i
767 begin = idx;
768 }
769 }
770 // (2) linear search between the samples
771 rank = begin * bit_vector_type::block_size * t_k - m_v->m_rank[begin]; // now i>rank
772 idx = begin * t_k; // initialize idx for select result
773 if (m_v->m_rank[end] == m_v->m_rank[begin])
774 { // only for select<0>
775 return idx * bit_vector_type::block_size + i - rank - 1;
776 }
777 size_type btnrp = m_v->m_btnrp[begin];
778 uint8_t bt = 0, s = 0; // temp variables for block_type and space for block type
779 while (i > rank)
780 {
781 bt = m_v->m_bt[idx++];
782 rank += (bit_vector_type::block_size - bt);
783 btnrp += (s = bi_type::space_for_bt(bt));
784 }
785 rank -= (bit_vector_type::block_size - bt);
786 uint32_t btnr = m_v->m_btnr.get_int(btnrp - s, s);
787 return (idx - 1) * bit_vector_type::block_size + bits::sel(~((uint64_t)bi_type::nr_to_bin(bt, btnr)), i - rank);
788 }
789
790public:
792 {
793 set_vector(v);
794 }
795
798 {
799 return t_b ? select1(i) : select0(i);
800 }
801
803 {
804 return select(i);
805 }
806
807 const size_type size() const
808 {
809 return m_v->size();
810 }
811
812 void set_vector(bit_vector_type const * v = nullptr)
813 {
814 m_v = v;
815 }
816
818 {
819 if (this != &rs)
820 {
821 set_vector(rs.m_v);
822 }
823 return *this;
824 }
825
826 void load(std::istream &, bit_vector_type const * v = nullptr)
827 {
828 set_vector(v);
829 }
830
831 size_type serialize(std::ostream &, structure_tree_node * v = nullptr, std::string name = "") const
832 {
833 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
834 structure_tree::add_size(child, 0);
835 return 0;
836 }
837
838 template <typename archive_t>
839 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
840 {}
841
842 template <typename archive_t>
844 {}
845
846 bool operator==(select_support_rrr const & other) const noexcept
847 {
848 return *m_v == *other.m_v;
849 }
850
851 bool operator!=(select_support_rrr const & other) const noexcept
852 {
853 return !(*this == other);
854 }
855};
856
857} // end namespace sdsl
858
859#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
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)
A generic vector class for integers of width .
Definition io.hpp:36
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
int_vector_trait< t_width >::value_type value_type
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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
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 & operator=(rank_support_rrr const &rs)
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.
const size_type operator()(size_type i) const
Short hand for rank(i)
rank_support_rrr(bit_vector_type const *v=nullptr)
Standard constructor.
const size_type size() const
Returns the size of the original vector.
bool operator!=(rank_support_rrr const &other) const noexcept
void load(std::istream &, bit_vector_type const *v=nullptr)
Load the data structure from a stream and set the supported vector.
void set_vector(bit_vector_type const *v=nullptr)
Set the supported vector.
bool operator==(rank_support_rrr const &other) const noexcept
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers rank queries const size_type rank(size_type i) const
Set the supported vector void set_vector(bit_vector_type const *v=nullptr)
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)
bool operator==(rrr_vector const &v) const
rrr_vector & operator=(rrr_vector &&v)
Move assignment.
rrr_vector(rrr_vector const &v)
Copy constructor.
bool operator!=(rrr_vector const &v) const
select_support_rrr< 0, 15, t_rac, t_k > select_0_type
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
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.
rrr_vector & operator=(rrr_vector const &v)
Assignment operator.
rank_support_rrr< 1, 15, t_rac, t_k > rank_1_type
rrr_vector(bit_vector const &bv)
Constructor.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
select_support_rrr< 1, 15, t_rac, t_k > select_1_type
size_type size() const
Returns the size of the original bit vector.
rrr_vector(rrr_vector &&v)
Move constructor.
random_access_const_iterator< rrr_vector > iterator
Returns the size of the original bit vector size_type size() const
bit_vector const & btnr
rac_type const & bt
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
size_type select(size_type i) const
Answers select queries.
bool operator==(select_support_rrr const &other) const noexcept
bool operator!=(select_support_rrr const &other) const noexcept
void load(std::istream &, bit_vector_type const *v=nullptr)
size_type serialize(std::ostream &, structure_tree_node *v=nullptr, std::string name="") const
select_support_rrr & operator=(select_support_rrr const &rs)
const size_type operator()(size_type i) const
select_support_rrr(bit_vector_type const *v=nullptr)
void set_vector(bit_vector_type const *v=nullptr)
void set_vector(bit_vector_type const *v=nullptr)
rrr_vector< t_bs, t_rac, t_k > bit_vector_type
Answers select queries size_type select(size_type i) const
bit_vector_type::size_type size_type
const size_type size() const
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)
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_vector.hpp contains the sdsl::rrr_vector class, and classes which support rank and select for rrr...
Contains declarations and definitions of data structure concepts.
static 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:586
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 cnt(uint64_t x)
Counts the number of set bits in x.
Definition bits.hpp:486
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, SDSL_UNUSED size_type n)
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.