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