SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sd_vector.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors and Jouni Siren. 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_SD_VECTOR
10#define INCLUDED_SDSL_SD_VECTOR
11
12#include <assert.h>
13#include <iosfwd>
14#include <iterator>
15#include <stdexcept>
16#include <stdint.h>
17#include <string>
18#include <utility>
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>
28#include <sdsl/util.hpp>
29
31namespace sdsl
32{
33
34// forward declaration needed for friend declaration
35template <uint8_t t_b = 1,
36 class t_hi_bit_vector = bit_vector,
37 class t_select_1 = typename t_hi_bit_vector::select_1_type,
38 class t_select_0 = typename t_hi_bit_vector::select_0_type>
39class rank_support_sd; // in sd_vector
40// forward declaration needed for friend declaration
41template <uint8_t t_b = 1,
42 class t_hi_bit_vector = bit_vector,
43 class t_select_1 = typename t_hi_bit_vector::select_1_type,
44 class t_select_0 = typename t_hi_bit_vector::select_0_type>
45class select_support_sd; // in sd_vector
46
48
51{
52 template <typename, typename, typename>
53 friend class sd_vector;
54
55public:
57
58private:
59 size_type m_size, m_capacity;
60 size_type m_wl;
61 size_type m_tail, m_items;
62 size_type m_last_high, m_highpos;
63
64 int_vector<> m_low;
65 bit_vector m_high;
66
67public:
69
71
75
76 inline size_type size() const
77 {
78 return m_size;
79 }
80 inline size_type capacity() const
81 {
82 return m_capacity;
83 }
84 inline size_type tail() const
85 {
86 return m_tail;
87 }
88 inline size_type items() const
89 {
90 return m_items;
91 }
92
94
97 inline void set(size_type i)
98 {
99 assert(i >= m_tail && i < m_size);
100 assert(m_items < m_capacity);
101
102 size_type cur_high = i >> m_wl;
103 m_highpos += (cur_high - m_last_high);
104 m_last_high = cur_high;
105 m_low[m_items++] = i; // int_vector truncates the most significant logm bits
106 m_high[m_highpos++] = 1; // write 1 for the entry
107 m_tail = i + 1;
108 }
109};
110
112// representing the positions of 1 by the Elias-Fano representation for non-decreasing sequences
131template <class t_hi_bit_vector = bit_vector,
132 class t_select_1 = typename t_hi_bit_vector::select_1_type,
133 class t_select_0 = typename t_hi_bit_vector::select_0_type>
135{
136public:
143 typedef t_select_0 select_0_support_type;
144 typedef t_select_1 select_1_support_type;
145
150
151 typedef t_hi_bit_vector hi_bit_vector_type;
152
153private:
154 // we need this variables to represent the m ones of the original bit vector of size n
155 size_type m_size = 0; // length of the original bit vector
156 uint8_t m_wl = 0; // log n - log m, where n is the length of the original bit vector
157 // and m is the number of ones in the bit vector, wl is the abbreviation
158 // for ,,width (of) low (part)''
159
160 int_vector<> m_low; // vector for the least significant bits of the positions of the m ones
161 hi_bit_vector_type m_high; // bit vector that represents the most significant bit in permuted order
162 select_1_support_type m_high_1_select; // select support for the ones in m_high
163 select_0_support_type m_high_0_select; // select support for the zeros in m_high
164
165public:
166 uint8_t const & wl = m_wl;
167 hi_bit_vector_type const & high = m_high;
168 int_vector<> const & low = m_low;
169 select_1_support_type const & high_1_select = m_high_1_select;
170 select_0_support_type const & high_0_select = m_high_0_select;
171
173 {}
174
175 sd_vector(sd_vector const & sd) :
176 m_size(sd.m_size),
177 m_wl(sd.m_wl),
178 m_low(sd.m_low),
179 m_high(sd.m_high),
180 m_high_1_select(sd.m_high_1_select),
181 m_high_0_select(sd.m_high_0_select)
182 {
183 m_high_1_select.set_vector(&m_high);
184 m_high_0_select.set_vector(&m_high);
185 }
186
188 {
189 if (this != &v)
190 {
191 sd_vector tmp(v);
192 *this = std::move(tmp);
193 }
194 return *this;
195 }
196
198 {
199 if (this != &v)
200 {
201 m_size = v.m_size;
202 m_wl = v.m_wl;
203 m_low = std::move(v.m_low);
204 m_high = std::move(v.m_high);
205 m_high_1_select = std::move(v.m_high_1_select);
206 m_high_1_select.set_vector(&m_high);
207 m_high_0_select = std::move(v.m_high_0_select);
208 m_high_0_select.set_vector(&m_high);
209 }
210 return *this;
211 }
212
214 {
215 *this = std::move(sd);
216 }
217
219 {
220 m_size = bv.size();
222 uint8_t logm = bits::hi(m) + 1;
223 uint8_t logn = bits::hi(m_size) + 1;
224 if (logm == logn)
225 {
226 --logm; // to ensure logn-logm > 0
227 }
228 m_wl = logn - logm;
229 m_low = int_vector<>(m, 0, m_wl);
230 bit_vector high = bit_vector(m + (1ULL << logm), 0); //
231 uint64_t const * bvp = bv.data();
232 for (size_type i = 0, mm = 0, last_high = 0, highpos = 0; i < (bv.size() + 63) / 64; ++i, ++bvp)
233 {
234 size_type position = 64 * i;
235 uint64_t w = *bvp;
236 while (w)
237 { // process bit_vector word by word
238 uint8_t offset = bits::lo(w);
239 w >>= offset; // note: w >>= (offset+1) can not be applied for offset=63!
240 position += offset;
241 if (position >= bv.size()) // check that we have not reached the end of the bitvector
242 break;
243 // (1) handle high part
244 size_type cur_high = position >> m_wl;
245 highpos += (cur_high - last_high); // write cur_high-last_high 0s
246 last_high = cur_high;
247 // (2) handle low part
248 m_low[mm++] = position; // int_vector truncates the most significant logm bits
249 high[highpos++] = 1; // write 1 for the entry
250 position += 1;
251 w >>= 1;
252 }
253 }
254 m_high = std::move(high);
255 util::init_support(m_high_1_select, &m_high);
256 util::init_support(m_high_0_select, &m_high);
257 }
258
259 template <class t_itr>
260 sd_vector(const t_itr begin, const t_itr end)
261 {
262 if (begin == end)
263 {
264 return;
265 }
266 if (!is_sorted(begin, end))
267 {
268 throw std::runtime_error("sd_vector: source list is not sorted.");
269 }
270 size_type m = std::distance(begin, end);
271 m_size = *(end - 1) + 1;
272 uint8_t logm = bits::hi(m) + 1;
273 uint8_t logn = bits::hi(m_size) + 1;
274 if (logm == logn)
275 {
276 --logm; // to ensure logn-logm > 0
277 }
278 m_wl = logn - logm;
279 m_low = int_vector<>(m, 0, m_wl);
280 bit_vector high = bit_vector(m + (1ULL << logm), 0);
281 auto itr = begin;
282 size_type mm = 0, last_high = 0, highpos = 0;
283 while (itr != end)
284 {
285 auto position = *itr;
286 // (1) handle high part
287 size_type cur_high = position >> m_wl;
288 highpos += (cur_high - last_high); // write cur_high-last_high 0s
289 last_high = cur_high;
290 // (2) handle low part
291 m_low[mm++] = position; // int_vector truncates the most significant logm bits
292 high[highpos++] = 1; // write 1 for the entry
293 ++itr;
294 }
295
296 m_high = std::move(high);
297 util::init_support(m_high_1_select, &m_high);
298 util::init_support(m_high_0_select, &m_high);
299 }
300
302 {
303 if (builder.items() != builder.capacity())
304 {
305 throw std::runtime_error("sd_vector: builder is not at full capacity.");
306 }
307
308 m_size = builder.m_size;
309 m_wl = builder.m_wl;
310 m_low = std::move(builder.m_low);
311 m_high = std::move(builder.m_high);
312 util::init_support(m_high_1_select, &(this->m_high));
313 util::init_support(m_high_0_select, &(this->m_high));
314
315 builder = sd_vector_builder();
316 }
317
319
329 {
330 size_type high_val = (i >> (m_wl));
331 size_type sel_high = m_high_0_select(high_val + 1);
332 size_type rank_low = sel_high - high_val;
333 if (0 == rank_low)
334 return 0;
335 size_type val_low = i & bits::lo_set[m_wl]; // extract the low m_wl = log n -log m bits
336 --sel_high;
337 --rank_low;
338 while (m_high[sel_high] and m_low[rank_low] > val_low)
339 {
340 if (sel_high > 0)
341 {
342 --sel_high;
343 --rank_low;
344 }
345 else
346 return 0;
347 }
348 return m_high[sel_high] and m_low[rank_low] == val_low;
349 }
350
352
359 uint64_t get_int(size_type idx, const uint8_t len = 64) const
360 {
361 uint64_t i = idx + len - 1;
362 uint64_t high_val = (i >> (m_wl));
363 uint64_t sel_high = m_high_0_select(high_val + 1);
364 uint64_t rank_low = sel_high - high_val;
365 if (0 == rank_low)
366 return 0;
367 size_type val_low = i & bits::lo_set[m_wl]; // extract the low m_wl = log n -log m bits
368 --sel_high;
369 --rank_low;
370 while (m_high[sel_high] and m_low[rank_low] > val_low)
371 {
372 if (sel_high > 0)
373 {
374 --sel_high;
375 --rank_low;
376 }
377 else
378 return 0;
379 }
380 uint64_t res = 0;
381 while (true)
382 {
383 while (!m_high[sel_high])
384 {
385 if (sel_high > 0 and (high_val << m_wl) >= idx)
386 {
387 --sel_high;
388 --high_val;
389 }
390 else
391 {
392 return res;
393 }
394 }
395 while (m_high[sel_high])
396 {
397 uint64_t val = (high_val << m_wl) + m_low[rank_low];
398 if (val >= idx)
399 {
400 res |= 1ULL << (val - idx);
401 }
402 else
403 {
404 return res;
405 }
406 if (sel_high > 0)
407 {
408 --sel_high;
409 --rank_low;
410 }
411 else
412 {
413 return res;
414 }
415 }
416 }
417 }
418
421 {
422 return m_size;
423 }
424
426 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
427 {
428 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
429 size_type written_bytes = 0;
430 written_bytes += write_member(m_size, out, child, "size");
431 written_bytes += write_member(m_wl, out, child, "wl");
432 written_bytes += m_low.serialize(out, child, "low");
433 written_bytes += m_high.serialize(out, child, "high");
434 written_bytes += m_high_1_select.serialize(out, child, "high_1_select");
435 written_bytes += m_high_0_select.serialize(out, child, "high_0_select");
436 structure_tree::add_size(child, written_bytes);
437 return written_bytes;
438 }
439
441 void load(std::istream & in)
442 {
443 read_member(m_size, in);
444 read_member(m_wl, in);
445 m_low.load(in);
446 m_high.load(in);
447 m_high_1_select.load(in, &m_high);
448 m_high_0_select.load(in, &m_high);
449 }
450
451 template <typename archive_t>
452 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
453 {
454 ar(CEREAL_NVP(m_size));
455 ar(CEREAL_NVP(m_wl));
456 ar(CEREAL_NVP(m_low));
457 ar(CEREAL_NVP(m_high));
458 ar(CEREAL_NVP(m_high_1_select));
459 ar(CEREAL_NVP(m_high_0_select));
460 }
461
462 template <typename archive_t>
463 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
464 {
465 ar(CEREAL_NVP(m_size));
466 ar(CEREAL_NVP(m_wl));
467 ar(CEREAL_NVP(m_low));
468 ar(CEREAL_NVP(m_high));
469 ar(CEREAL_NVP(m_high_1_select));
470 m_high_1_select.set_vector(&m_high);
471 ar(CEREAL_NVP(m_high_0_select));
472 m_high_0_select.set_vector(&m_high);
473 }
474
476 {
477 return iterator(this, 0);
478 }
479
480 iterator end() const
481 {
482 return iterator(this, size());
483 }
484
485 bool operator==(sd_vector const & v) const
486 {
487 return m_size == v.m_size && m_wl == v.m_wl && m_low == v.m_low && m_high == v.m_high;
488 }
489
490 bool operator!=(sd_vector const & v) const
491 {
492 return !(*this == v);
493 }
494};
495
497template <>
498sd_vector<>::sd_vector(sd_vector_builder & builder);
499
500template <uint8_t t_b>
502{
505 {
506 return r;
507 }
508};
509
510template <>
512{
515 {
516 return n - r;
517 }
518};
519
521
527template <uint8_t t_b, class t_hi_bit_vector, class t_select_1, class t_select_0>
529{
530 static_assert(t_b == 1u or t_b == 0u, "rank_support_sd: bit pattern must be `0` or `1`");
531
532public:
535 enum
536 {
537 bit_pat = t_b
538 };
539 enum
540 {
541 bit_pat_len = (uint8_t)1
542 };
543
544private:
545 bit_vector_type const * m_v;
546
547public:
548 explicit rank_support_sd(bit_vector_type const * v = nullptr)
549 {
550 set_vector(v);
551 }
552
554 {
555 assert(m_v != nullptr);
556 assert(i <= m_v->size());
557 // split problem in two parts:
558 // (1) find >=
559 size_type high_val = (i >> (m_v->wl));
560 size_type sel_high = m_v->high_0_select(high_val + 1);
561 size_type rank_low = sel_high - high_val; //
562 if (0 == rank_low)
564 size_type val_low = i & bits::lo_set[m_v->wl];
565 // now since rank_low > 0 => sel_high > 0
566 do
567 {
568 if (!sel_high)
570 --sel_high;
571 --rank_low;
572 }
573 while (m_v->high[sel_high] and m_v->low[rank_low] >= val_low);
574 return rank_support_sd_trait<t_b>::adjust_rank(rank_low + 1, i);
575 }
576
578 {
579 return rank(i);
580 }
581
583 {
584 return m_v->size();
585 }
586
587 void set_vector(bit_vector_type const * v = nullptr)
588 {
589 m_v = v;
590 }
591
592 void load(std::istream &, bit_vector_type const * v = nullptr)
593 {
594 set_vector(v);
595 }
596
597 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
598 {
599 return serialize_empty_object(out, v, name, this);
600 }
601
602 template <typename archive_t>
603 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
604 {}
605
606 template <typename archive_t>
608 {}
609
610 bool operator==(rank_support_sd const & other) const noexcept
611 {
612 return *m_v == *other.m_v;
613 }
614
615 bool operator!=(rank_support_sd const & other) const noexcept
616 {
617 return !(*this == other);
618 }
619};
620
621template <uint8_t t_b, class t_sd_vec>
623{
625 static size_type select(size_type i, t_sd_vec const * v)
626 {
627 return v->low[i - 1] + // lower part of the number
628 ((v->high_1_select(i) + 1 - i) << (v->wl)); // upper part
629 //^-number of 0 before the i-th 1-^ ^-shift by wl
630 }
631};
632
633template <class t_sd_vec>
634struct select_support_sd_trait<0, t_sd_vec>
635{
637 static size_type select(size_type i, t_sd_vec const * v)
638 {
639 auto ones = v->low.size();
640 assert(0 < i and i <= v->size() - ones);
641 size_type lb = 1, rb = ones + 1;
642 size_type r0 = 0;
643 size_type pos = (size_type)-1;
644 // rb exclusive
645 // invariant: rank0(select_1(rb)) >= i
646 while (lb < rb)
647 {
648 auto mid = lb + (rb - lb) / 2;
650 auto rank0 = x + 1 - mid;
651 if (rank0 >= i)
652 {
653 rb = mid;
654 }
655 else
656 {
657 r0 = rank0;
658 pos = x;
659 lb = mid + 1;
660 }
661 }
662 return pos + i - r0;
663 }
664};
665
667
673template <uint8_t t_b, class t_hi_bit_vector, class t_select_1, class t_select_0>
675{
676public:
679 enum
680 {
681 bit_pat = t_b
682 };
683 enum
684 {
685 bit_pat_len = (uint8_t)1
686 };
687
688private:
689 bit_vector_type const * m_v;
690
691public:
692 explicit select_support_sd(bit_vector_type const * v = nullptr)
693 {
694 set_vector(v);
695 }
696
702
704 {
705 return select(i);
706 }
707
709 {
710 return m_v->size();
711 }
712
713 void set_vector(bit_vector_type const * v = nullptr)
714 {
715 m_v = v;
716 }
717
718 void load(std::istream &, bit_vector_type const * v = nullptr)
719 {
720 set_vector(v);
721 }
722
723 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
724 {
725 return serialize_empty_object(out, v, name, this);
726 }
727
728 template <typename archive_t>
729 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
730 {}
731
732 template <typename archive_t>
734 {}
735
736 bool operator==(select_support_sd const & other) const noexcept
737 {
738 return *m_v == *other.m_v;
739 }
740
741 bool operator!=(select_support_sd const & other) const noexcept
742 {
743 return !(*this == other);
744 }
745};
746
748
751template <typename t_sd_vector = sd_vector<>>
753{
754public:
756 typedef t_sd_vector bit_vector_type;
757 using rank_1 = typename t_sd_vector::rank_1_type;
758 using sel0_type = typename t_sd_vector::select_0_type;
760 enum
761 {
762 bit_pat = 0
763 };
764 enum
765 {
766 bit_pat_len = (uint8_t)1
767 };
768
769private:
770 bit_vector_type const * m_v;
771 int_vector<> m_pointer;
772 int_vector<> m_rank1;
773
774public:
775 explicit select_0_support_sd(bit_vector_type const * v = nullptr)
776 {
777 set_vector(v);
778 if (nullptr != m_v)
779 {
780 size_type rank_0 = 0; // rank0 in H
781 const size_type bs = 1ULL << (m_v->wl);
782 size_type z = 0;
783 size_type rank1 = 0; // rank1 in H
784 size_type zeros = m_v->size() - rank_1(m_v)(m_v->size()); // zeros in B
785 m_pointer = int_vector<>(zeros / (64 * bs) + 1, 0, bits::hi(m_v->high.size() / 64) + 1);
786 m_rank1 = int_vector<>(m_pointer.size(), 0, bits::hi(m_v->high.size()) + 1);
787 uint64_t w = 0;
788 for (size_type i = 0, sel0 = 1; i < m_v->high.size(); i += 64)
789 {
790 size_type old_rank1 = rank1;
791 w = m_v->high.get_int(i, 64);
792 rank1 += bits::cnt(w);
793 rank_0 = (i + 64) - rank1;
794 if (rank1 > 0 and (w >> 63) & 1)
795 {
796 uint64_t pos = rank_0 * bs + m_v->low[rank1 - 1]; // pos of last one (of previous block in B
797 z = pos + 1 - rank1;
798 }
799 else
800 {
801 z = rank_0 * bs - rank1;
802 }
803 while (sel0 <= z and sel0 <= zeros)
804 {
805 m_pointer[(sel0 - 1) / (64 * bs)] = i / 64;
806 m_rank1[(sel0 - 1) / (64 * bs)] = old_rank1;
807 sel0 += 64 * bs;
808 }
809 }
810 }
811 }
812
815 {
816 const size_type bs = 1ULL << (m_v->wl);
817 size_type j = m_pointer[(i - 1) / (64 * bs)] * 64; // index into m_high
818 size_type rank1 = m_rank1[(i - 1) / (64 * bs)]; // rank_1(j*bs*64) in B
819 size_type pos = 0;
820 // size_type rank0 = 0;
821
822 if (rank1 > 0 and (m_v->high[j - 1]) & 1)
823 {
824 pos = (j - rank1) * bs + m_v->low[rank1 - 1]; // starting position of current block
825 // rank0 = pos + 1 - rank1;
826 }
827 else
828 {
829 pos = (j - rank1) * bs; // starting position of current block
830 // rank0 = pos - rank1;
831 }
832 uint64_t w = m_v->high.get_int(j, 64);
833 do
834 {
835 uint64_t _rank1 = rank1 + bits::cnt(w);
836 uint64_t _rank0 = 0;
837 if (_rank1 > 0 and (w >> 63) & 1)
838 {
839 pos = (j + 64 - _rank1) * bs + m_v->low[_rank1 - 1];
840 _rank0 = pos + 1 - _rank1;
841 }
842 else
843 {
844 pos = (j + 64 - _rank1) * bs;
845 _rank0 = pos - _rank1;
846 }
847 if (_rank0 < i)
848 {
849 j += 64;
850 w = m_v->high.get_int(j, 64);
851 rank1 = _rank1;
852 }
853 else
854 {
855 break;
856 }
857 }
858 while (true);
859 // invariant i >zeros
860 do
861 {
862 uint64_t _rank1 = rank1 + bits::lt_cnt[w & 0xFFULL];
863 uint64_t _rank0 = 0;
864 if (_rank1 > 0 and (w >> 7) & 1)
865 {
866 pos = (j + 8 - _rank1) * bs + m_v->low[_rank1 - 1];
867 _rank0 = pos + 1 - _rank1;
868 }
869 else
870 {
871 pos = (j + 8 - _rank1) * bs;
872 _rank0 = pos - _rank1;
873 }
874 if (_rank0 < i)
875 {
876 j += 8;
877 w >>= 8;
878 rank1 = _rank1;
879 }
880 else
881 {
882 break;
883 }
884 }
885 while (true);
886
887 do
888 {
889 bool b = w & 1ULL;
890 w >>= 1; // zeros are shifted in
891 ++j;
892 if (0 == b)
893 {
894 pos = (j - rank1) * bs;
895 size_type zeros = pos - rank1;
896 if (zeros >= i)
897 {
898 pos = pos - (zeros - i) - 1;
899 break;
900 }
901 }
902 else
903 {
904 pos = (j - 1 - rank1) * bs;
905 size_type one_pos = pos + m_v->low[rank1];
906 ++rank1;
907 size_type zeros = one_pos + 1 - rank1;
908 if (zeros >= i)
909 {
910 pos = one_pos - (zeros - i) - 1;
911 break;
912 }
913 }
914 if (j % 64 == 0)
915 {
916 w = m_v->high.get_int(j, 64);
917 }
918 }
919 while (true);
920 return pos;
921 }
922
924 {
925 return select(i);
926 }
927
929 {
930 return m_v->size();
931 }
932
933 void set_vector(bit_vector_type const * v = nullptr)
934 {
935 m_v = v;
936 }
937
938 void load(std::istream & in, bit_vector_type const * v = nullptr)
939 {
940 m_pointer.load(in);
941 m_rank1.load(in);
942 set_vector(v);
943 }
944
945 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
946 {
947 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
948 size_type written_bytes = 0;
949 written_bytes += m_pointer.serialize(out, child, "pointer");
950 written_bytes += m_rank1.serialize(out, child, "rank1");
951 structure_tree::add_size(child, written_bytes);
952 return written_bytes;
953 }
954
955 template <typename archive_t>
956 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
957 {
958 ar(CEREAL_NVP(m_pointer));
959 ar(CEREAL_NVP(m_rank1));
960 }
961
962 template <typename archive_t>
963 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
964 {
965 ar(CEREAL_NVP(m_pointer));
966 ar(CEREAL_NVP(m_rank1));
967 }
968
969 bool operator==(select_0_support_sd const & other) const noexcept
970 {
971 return (m_pointer == other.m_pointer) && (m_rank1 == other.m_rank1);
972 }
973
974 bool operator!=(select_0_support_sd const & other) const noexcept
975 {
976 return !(*this == other);
977 }
978};
979
981 m_size(0),
982 m_capacity(0),
983 m_wl(0),
984 m_tail(0),
985 m_items(0),
986 m_last_high(0),
987 m_highpos(0)
988{}
989
991 m_size(n),
992 m_capacity(m),
993 m_wl(0),
994 m_tail(0),
995 m_items(0),
996 m_last_high(0),
997 m_highpos(0)
998{
999 if (m_capacity > m_size)
1000 {
1001 throw std::runtime_error("sd_vector_builder: requested capacity is larger than vector size.");
1002 }
1003
1004 size_type logm = bits::hi(m_capacity) + 1, logn = bits::hi(m_size) + 1;
1005 if (logm == logn)
1006 {
1007 logm--; // to ensure logn-logm > 0
1008 }
1009 m_wl = logn - logm;
1010 m_low = int_vector<>(m_capacity, 0, m_wl);
1011 m_high = bit_vector(m_capacity + (1ULL << logm), 0);
1012}
1013
1014template <>
1016{
1017 if (builder.items() != builder.capacity())
1018 {
1019 throw std::runtime_error("sd_vector: the builder is not full.");
1020 }
1021
1022 m_size = builder.m_size;
1023 m_wl = builder.m_wl;
1024 m_low = std::move(builder.m_low);
1025 m_high = std::move(builder.m_high);
1026 util::init_support(m_high_1_select, &m_high);
1027 util::init_support(m_high_0_select, &m_high);
1028
1029 builder = sd_vector_builder();
1030}
1031
1032} // namespace sdsl
1033#endif
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
#define CEREAL_NVP(X)
Definition cereal.hpp:31
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
int_vector_size_type size_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.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
Generic iterator for a random access container.
Definition iterators.hpp:24
Rank data structure for sd_vector.
void load(std::istream &, bit_vector_type const *v=nullptr)
void set_vector(bit_vector_type const *v=nullptr)
bit_vector::size_type size_type
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
size_type operator()(size_type i) const
bool operator==(rank_support_sd const &other) const noexcept
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
rank_support_sd(bit_vector_type const *v=nullptr)
size_type rank(size_type i) const
bool operator!=(rank_support_sd const &other) const noexcept
size_type size() const
Class for in-place construction of sd_vector from a strictly increasing sequence.
Definition sd_vector.hpp:51
size_type items() const
Definition sd_vector.hpp:88
size_type tail() const
Definition sd_vector.hpp:84
bit_vector::size_type size_type
Definition sd_vector.hpp:56
void set(size_type i)
Set a bit to 1.
Definition sd_vector.hpp:97
size_type capacity() const
Definition sd_vector.hpp:80
size_type size() const
Definition sd_vector.hpp:76
A bit vector which compresses very sparse populated bit vectors by.
hi_bit_vector_type const & high
sd_vector(bit_vector const &bv)
select_1_support_type const & high_1_select
uint8_t const & wl
t_select_1 select_1_support_type
select_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_1_type
bool operator!=(sd_vector const &v) const
rank_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_0_type
bit_vector::size_type size_type
sd_vector(sd_vector &&sd)
iterator end() const
void load(std::istream &in)
Loads the data structure from the given istream.
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
iterator const_iterator
size_type value_type
t_select_0 select_0_support_type
t_hi_bit_vector hi_bit_vector_type
sd_vector & operator=(sd_vector const &v)
sd_vector(const t_itr begin, const t_itr end)
sd_vector & operator=(sd_vector &&v)
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_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_1_type
bit_vector::difference_type difference_type
select_0_support_type const & high_0_select
sd_vector(sd_vector_builder &builder)
random_access_const_iterator< sd_vector > iterator
sd_vector(sd_vector const &sd)
int_vector const & low
bv_tag index_category
uint64_t 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.
bool operator==(sd_vector const &v) const
select_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_0_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type size() const
Returns the size of the original bit vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
iterator begin() const
Select_0 data structure for sd_vector.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool operator!=(select_0_support_sd const &other) const noexcept
bit_vector::size_type size_type
typename t_sd_vector::rank_1_type rank_1
select_0_support_sd(bit_vector_type const *v=nullptr)
size_type operator()(size_type i) const
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
size_type size() const
bool operator==(select_0_support_sd const &other) const noexcept
typename t_sd_vector::select_0_type sel0_type
void set_vector(bit_vector_type const *v=nullptr)
void load(std::istream &in, bit_vector_type const *v=nullptr)
Select data structure for sd_vector.
void set_vector(bit_vector_type const *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
select_support_sd(bit_vector_type const *v=nullptr)
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
bool operator==(select_support_sd const &other) const noexcept
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool operator!=(select_support_sd const &other) const noexcept
void load(std::istream &, bit_vector_type const *v=nullptr)
size_type operator()(size_type i) const
size_type size() const
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
bit_vector::size_type size_type
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.
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
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.
int_vector ::size_type size(range_type const &r)
Size of a range.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", T const *t=nullptr)
Definition io.hpp:339
Contains declarations and definitions of data structure concepts.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
Definition bits.hpp:689
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 constexpr uint8_t lt_cnt[256]
Lookup table for byte popcounts.
Definition bits.hpp:172
static size_type adjust_rank(size_type r, size_type n)
bit_vector::size_type size_type
static size_type adjust_rank(size_type r, size_type)
bit_vector::size_type size_type
static size_type select(size_type i, t_sd_vec const *v)
static size_type select(size_type i, t_sd_vec const *v)
bit_vector::size_type size_type
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.