SDSL 3.0.1
Succinct Data Structure Library
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 <sdsl/int_vector.hpp>
13#include <sdsl/iterators.hpp>
15#include <sdsl/util.hpp>
16
18namespace sdsl
19{
20
21// forward declaration needed for friend declaration
22template <uint8_t t_b = 1,
23 class t_hi_bit_vector = bit_vector,
24 class t_select_1 = typename t_hi_bit_vector::select_1_type,
25 class t_select_0 = typename t_hi_bit_vector::select_0_type>
26class rank_support_sd; // in sd_vector
27
28// forward declaration needed for friend declaration
29template <uint8_t t_b = 1,
30 class t_hi_bit_vector = bit_vector,
31 class t_select_1 = typename t_hi_bit_vector::select_1_type,
32 class t_select_0 = typename t_hi_bit_vector::select_0_type>
33class select_support_sd; // in sd_vector
34
35// forward declaration needed for friend declaration
36template <typename, typename, typename>
37class sd_vector; // in sd_vector
38
40
43{
44 template <typename, typename, typename>
45 friend class sd_vector;
46
47 public:
49
50 private:
51 size_type m_size, m_capacity;
52 size_type m_wl;
53 size_type m_tail, m_items;
54 size_type m_last_high, m_highpos;
55
56 int_vector<> m_low;
57 bit_vector m_high;
58
59 public:
61
63
67
68 inline size_type size() const { return m_size; }
69 inline size_type capacity() const { return m_capacity; }
70 inline size_type tail() const { return m_tail; }
71 inline size_type items() const { return m_items; }
72
74
77 inline void set(size_type i)
78 {
79 assert(i >= m_tail && i < m_size);
80 assert(m_items < m_capacity);
81
82 size_type cur_high = i >> m_wl;
83 m_highpos += (cur_high - m_last_high);
84 m_last_high = cur_high;
85 m_low[m_items++] = i; // int_vector truncates the most significant logm bits
86 m_high[m_highpos++] = 1; // write 1 for the entry
87 m_tail = i + 1;
88 }
89};
90
92// representing the positions of 1 by the Elias-Fano representation for non-decreasing sequences
111template <class t_hi_bit_vector = bit_vector,
112 class t_select_1 = typename t_hi_bit_vector::select_1_type,
113 class t_select_0 = typename t_hi_bit_vector::select_0_type>
115{
116 public:
123 typedef t_select_0 select_0_support_type;
124 typedef t_select_1 select_1_support_type;
125
130
131 typedef t_hi_bit_vector hi_bit_vector_type;
132
133 private:
134 // we need this variables to represent the m ones of the original bit vector of size n
135 size_type m_size = 0; // length of the original bit vector
136 uint8_t m_wl = 0; // log n - log m, where n is the length of the original bit vector
137 // and m is the number of ones in the bit vector, wl is the abbreviation
138 // for ,,width (of) low (part)''
139
140 int_vector<> m_low; // vector for the least significant bits of the positions of the m ones
141 hi_bit_vector_type m_high; // bit vector that represents the most significant bit in permuted order
142 select_1_support_type m_high_1_select; // select support for the ones in m_high
143 select_0_support_type m_high_0_select; // select support for the zeros in m_high
144
145 public:
146 const uint8_t & wl = m_wl;
147 const hi_bit_vector_type & high = m_high;
148 const int_vector<> & low = m_low;
149 const select_1_support_type & high_1_select = m_high_1_select;
150 const select_0_support_type & high_0_select = m_high_0_select;
151
153
155 : m_size(sd.m_size)
156 , m_wl(sd.m_wl)
157 , m_low(sd.m_low)
158 , m_high(sd.m_high)
159 , m_high_1_select(sd.m_high_1_select)
160 , m_high_0_select(sd.m_high_0_select)
161 {
162 m_high_1_select.set_vector(&m_high);
163 m_high_0_select.set_vector(&m_high);
164 }
165
167 {
168 if (this != &v)
169 {
170 sd_vector tmp(v);
171 *this = std::move(tmp);
172 }
173 return *this;
174 }
175
177 {
178 if (this != &v)
179 {
180 m_size = v.m_size;
181 m_wl = v.m_wl;
182 m_low = std::move(v.m_low);
183 m_high = std::move(v.m_high);
184 m_high_1_select = std::move(v.m_high_1_select);
185 m_high_1_select.set_vector(&m_high);
186 m_high_0_select = std::move(v.m_high_0_select);
187 m_high_0_select.set_vector(&m_high);
188 }
189 return *this;
190 }
191
192 sd_vector(sd_vector && sd) { *this = std::move(sd); }
193
195 {
196 m_size = bv.size();
198 uint8_t logm = bits::hi(m) + 1;
199 uint8_t logn = bits::hi(m_size) + 1;
200 if (logm == logn)
201 {
202 --logm; // to ensure logn-logm > 0
203 }
204 m_wl = logn - logm;
205 m_low = int_vector<>(m, 0, m_wl);
206 bit_vector high = bit_vector(m + (1ULL << logm), 0); //
207 const uint64_t * bvp = bv.data();
208 for (size_type i = 0, mm = 0, last_high = 0, highpos = 0; i < (bv.size() + 63) / 64; ++i, ++bvp)
209 {
210 size_type position = 64 * i;
211 uint64_t w = *bvp;
212 while (w)
213 { // process bit_vector word by word
214 uint8_t offset = bits::lo(w);
215 w >>= offset; // note: w >>= (offset+1) can not be applied for offset=63!
216 position += offset;
217 if (position >= bv.size()) // check that we have not reached the end of the bitvector
218 break;
219 // (1) handle high part
220 size_type cur_high = position >> m_wl;
221 highpos += (cur_high - last_high); // write cur_high-last_high 0s
222 last_high = cur_high;
223 // (2) handle low part
224 m_low[mm++] = position; // int_vector truncates the most significant logm bits
225 high[highpos++] = 1; // write 1 for the entry
226 position += 1;
227 w >>= 1;
228 }
229 }
230 m_high = std::move(high);
231 util::init_support(m_high_1_select, &m_high);
232 util::init_support(m_high_0_select, &m_high);
233 }
234
235 template <class t_itr>
236 sd_vector(const t_itr begin, const t_itr end)
237 {
238 if (begin == end) { return; }
239 if (!is_sorted(begin, end)) { throw std::runtime_error("sd_vector: source list is not sorted."); }
240 size_type m = std::distance(begin, end);
241 m_size = *(end - 1) + 1;
242 uint8_t logm = bits::hi(m) + 1;
243 uint8_t logn = bits::hi(m_size) + 1;
244 if (logm == logn)
245 {
246 --logm; // to ensure logn-logm > 0
247 }
248 m_wl = logn - logm;
249 m_low = int_vector<>(m, 0, m_wl);
250 bit_vector high = bit_vector(m + (1ULL << logm), 0);
251 auto itr = begin;
252 size_type mm = 0, last_high = 0, highpos = 0;
253 while (itr != end)
254 {
255 auto position = *itr;
256 // (1) handle high part
257 size_type cur_high = position >> m_wl;
258 highpos += (cur_high - last_high); // write cur_high-last_high 0s
259 last_high = cur_high;
260 // (2) handle low part
261 m_low[mm++] = position; // int_vector truncates the most significant logm bits
262 high[highpos++] = 1; // write 1 for the entry
263 ++itr;
264 }
265
266 m_high = std::move(high);
267 util::init_support(m_high_1_select, &m_high);
268 util::init_support(m_high_0_select, &m_high);
269 }
270
272 {
273 if (builder.items() != builder.capacity())
274 {
275 throw std::runtime_error("sd_vector: builder is not at full capacity.");
276 }
277
278 m_size = builder.m_size;
279 m_wl = builder.m_wl;
280 m_low = std::move(builder.m_low);
281 m_high = std::move(builder.m_high);
282 util::init_support(m_high_1_select, &(this->m_high));
283 util::init_support(m_high_0_select, &(this->m_high));
284
285 builder = sd_vector_builder();
286 }
287
289
299 {
300 size_type high_val = (i >> (m_wl));
301 size_type sel_high = m_high_0_select(high_val + 1);
302 size_type rank_low = sel_high - high_val;
303 if (0 == rank_low) return 0;
304 size_type val_low = i & bits::lo_set[m_wl]; // extract the low m_wl = log n -log m bits
305 --sel_high;
306 --rank_low;
307 while (m_high[sel_high] and m_low[rank_low] > val_low)
308 {
309 if (sel_high > 0)
310 {
311 --sel_high;
312 --rank_low;
313 }
314 else
315 return 0;
316 }
317 return m_high[sel_high] and m_low[rank_low] == val_low;
318 }
319
321
328 uint64_t get_int(size_type idx, const uint8_t len = 64) const
329 {
330 uint64_t i = idx + len - 1;
331 uint64_t high_val = (i >> (m_wl));
332 uint64_t sel_high = m_high_0_select(high_val + 1);
333 uint64_t rank_low = sel_high - high_val;
334 if (0 == rank_low) 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 uint64_t res = 0;
349 while (true)
350 {
351 while (!m_high[sel_high])
352 {
353 if (sel_high > 0 and (high_val << m_wl) >= idx)
354 {
355 --sel_high;
356 --high_val;
357 }
358 else
359 {
360 return res;
361 }
362 }
363 while (m_high[sel_high])
364 {
365 uint64_t val = (high_val << m_wl) + m_low[rank_low];
366 if (val >= idx) { res |= 1ULL << (val - idx); }
367 else
368 {
369 return res;
370 }
371 if (sel_high > 0)
372 {
373 --sel_high;
374 --rank_low;
375 }
376 else
377 {
378 return res;
379 }
380 }
381 }
382 }
383
385 size_type size() const { return m_size; }
386
388 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
389 {
390 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
391 size_type written_bytes = 0;
392 written_bytes += write_member(m_size, out, child, "size");
393 written_bytes += write_member(m_wl, out, child, "wl");
394 written_bytes += m_low.serialize(out, child, "low");
395 written_bytes += m_high.serialize(out, child, "high");
396 written_bytes += m_high_1_select.serialize(out, child, "high_1_select");
397 written_bytes += m_high_0_select.serialize(out, child, "high_0_select");
398 structure_tree::add_size(child, written_bytes);
399 return written_bytes;
400 }
401
403 void load(std::istream & in)
404 {
405 read_member(m_size, in);
406 read_member(m_wl, in);
407 m_low.load(in);
408 m_high.load(in);
409 m_high_1_select.load(in, &m_high);
410 m_high_0_select.load(in, &m_high);
411 }
412
413 template <typename archive_t>
414 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
415 {
416 ar(CEREAL_NVP(m_size));
417 ar(CEREAL_NVP(m_wl));
418 ar(CEREAL_NVP(m_low));
419 ar(CEREAL_NVP(m_high));
420 ar(CEREAL_NVP(m_high_1_select));
421 ar(CEREAL_NVP(m_high_0_select));
422 }
423
424 template <typename archive_t>
425 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
426 {
427 ar(CEREAL_NVP(m_size));
428 ar(CEREAL_NVP(m_wl));
429 ar(CEREAL_NVP(m_low));
430 ar(CEREAL_NVP(m_high));
431 ar(CEREAL_NVP(m_high_1_select));
432 m_high_1_select.set_vector(&m_high);
433 ar(CEREAL_NVP(m_high_0_select));
434 m_high_0_select.set_vector(&m_high);
435 }
436
437 iterator begin() const { return iterator(this, 0); }
438
439 iterator end() const { return iterator(this, size()); }
440
441 bool operator==(const sd_vector & v) const
442 {
443 return m_size == v.m_size && m_wl == v.m_wl && m_low == v.m_low && m_high == v.m_high;
444 }
445
446 bool operator!=(const sd_vector & v) const { return !(*this == v); }
447};
448
450template <>
451sd_vector<>::sd_vector(sd_vector_builder & builder);
452
453template <uint8_t t_b>
455{
457 static size_type adjust_rank(size_type r, size_type) { return r; }
458};
459
460template <>
462{
464 static size_type adjust_rank(size_type r, size_type n) { return n - r; }
465};
466
468
474template <uint8_t t_b, class t_hi_bit_vector, class t_select_1, class t_select_0>
476{
477 static_assert(t_b == 1u or t_b == 0u, "rank_support_sd: bit pattern must be `0` or `1`");
478
479 public:
482 enum
483 {
484 bit_pat = t_b
485 };
486 enum
487 {
488 bit_pat_len = (uint8_t)1
489 };
490
491 private:
492 const bit_vector_type * m_v;
493
494 public:
495 explicit rank_support_sd(const bit_vector_type * v = nullptr) { set_vector(v); }
496
498 {
499 assert(m_v != nullptr);
500 assert(i <= m_v->size());
501 // split problem in two parts:
502 // (1) find >=
503 size_type high_val = (i >> (m_v->wl));
504 size_type sel_high = m_v->high_0_select(high_val + 1);
505 size_type rank_low = sel_high - high_val; //
506 if (0 == rank_low) return rank_support_sd_trait<t_b>::adjust_rank(0, i);
507 size_type val_low = i & bits::lo_set[m_v->wl];
508 // now since rank_low > 0 => sel_high > 0
509 do {
510 if (!sel_high) return rank_support_sd_trait<t_b>::adjust_rank(0, i);
511 --sel_high;
512 --rank_low;
513 } while (m_v->high[sel_high] and m_v->low[rank_low] >= val_low);
514 return rank_support_sd_trait<t_b>::adjust_rank(rank_low + 1, i);
515 }
516
517 size_type operator()(size_type i) const { return rank(i); }
518
519 size_type size() const { return m_v->size(); }
520
521 void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
522
523 void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
524
525 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
526 {
527 return serialize_empty_object(out, v, name, this);
528 }
529
530 template <typename archive_t>
531 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
532 {}
533
534 template <typename archive_t>
536 {}
537
538 bool operator==(const rank_support_sd & other) const noexcept { return *m_v == *other.m_v; }
539
540 bool operator!=(const rank_support_sd & other) const noexcept { return !(*this == other); }
541};
542
543template <uint8_t t_b, class t_sd_vec>
545{
547 static size_type select(size_type i, const t_sd_vec * v)
548 {
549 return v->low[i - 1] + // lower part of the number
550 ((v->high_1_select(i) + 1 - i) << (v->wl)); // upper part
551 //^-number of 0 before the i-th 1-^ ^-shift by wl
552 }
553};
554
555template <class t_sd_vec>
556struct select_support_sd_trait<0, t_sd_vec>
557{
559 static size_type select(size_type i, const t_sd_vec * v)
560 {
561 auto ones = v->low.size();
562 assert(0 < i and i <= v->size() - ones);
563 size_type lb = 1, rb = ones + 1;
564 size_type r0 = 0;
565 size_type pos = (size_type)-1;
566 // rb exclusive
567 // invariant: rank0(select_1(rb)) >= i
568 while (lb < rb)
569 {
570 auto mid = lb + (rb - lb) / 2;
572 auto rank0 = x + 1 - mid;
573 if (rank0 >= i) { rb = mid; }
574 else
575 {
576 r0 = rank0;
577 pos = x;
578 lb = mid + 1;
579 }
580 }
581 return pos + i - r0;
582 }
583};
584
586
592template <uint8_t t_b, class t_hi_bit_vector, class t_select_1, class t_select_0>
594{
595 public:
598 enum
599 {
600 bit_pat = t_b
601 };
602 enum
603 {
604 bit_pat_len = (uint8_t)1
605 };
606
607 private:
608 const bit_vector_type * m_v;
609
610 public:
611 explicit select_support_sd(const bit_vector_type * v = nullptr) { set_vector(v); }
612
615
616 size_type operator()(size_type i) const { return select(i); }
617
618 size_type size() const { return m_v->size(); }
619
620 void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
621
622 void load(std::istream &, const bit_vector_type * v = nullptr) { set_vector(v); }
623
624 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
625 {
626 return serialize_empty_object(out, v, name, this);
627 }
628
629 template <typename archive_t>
630 void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
631 {}
632
633 template <typename archive_t>
635 {}
636
637 bool operator==(const select_support_sd & other) const noexcept { return *m_v == *other.m_v; }
638
639 bool operator!=(const select_support_sd & other) const noexcept { return !(*this == other); }
640};
641
643
646template <typename t_sd_vector = sd_vector<>>
648{
649 public:
651 typedef t_sd_vector bit_vector_type;
652 using rank_1 = typename t_sd_vector::rank_1_type;
653 using sel0_type = typename t_sd_vector::select_0_type;
655 enum
656 {
657 bit_pat = 0
658 };
659 enum
660 {
661 bit_pat_len = (uint8_t)1
662 };
663
664 private:
665 const bit_vector_type * m_v;
666 int_vector<> m_pointer;
667 int_vector<> m_rank1;
668
669 public:
670 explicit select_0_support_sd(const bit_vector_type * v = nullptr)
671 {
672 set_vector(v);
673 if (nullptr != m_v)
674 {
675 size_type rank_0 = 0; // rank0 in H
676 const size_type bs = 1ULL << (m_v->wl);
677 size_type z = 0;
678 size_type rank1 = 0; // rank1 in H
679 size_type zeros = m_v->size() - rank_1(m_v)(m_v->size()); // zeros in B
680 m_pointer = int_vector<>(zeros / (64 * bs) + 1, 0, bits::hi(m_v->high.size() / 64) + 1);
681 m_rank1 = int_vector<>(m_pointer.size(), 0, bits::hi(m_v->high.size()) + 1);
682 uint64_t w = 0;
683 for (size_type i = 0, sel0 = 1; i < m_v->high.size(); i += 64)
684 {
685 size_type old_rank1 = rank1;
686 w = m_v->high.get_int(i, 64);
687 rank1 += bits::cnt(w);
688 rank_0 = (i + 64) - rank1;
689 if (rank1 > 0 and (w >> 63) & 1)
690 {
691 uint64_t pos = rank_0 * bs + m_v->low[rank1 - 1]; // pos of last one (of previous block in B
692 z = pos + 1 - rank1;
693 }
694 else
695 {
696 z = rank_0 * bs - rank1;
697 }
698 while (sel0 <= z and sel0 <= zeros)
699 {
700 m_pointer[(sel0 - 1) / (64 * bs)] = i / 64;
701 m_rank1[(sel0 - 1) / (64 * bs)] = old_rank1;
702 sel0 += 64 * bs;
703 }
704 }
705 }
706 }
707
710 {
711 const size_type bs = 1ULL << (m_v->wl);
712 size_type j = m_pointer[(i - 1) / (64 * bs)] * 64; // index into m_high
713 size_type rank1 = m_rank1[(i - 1) / (64 * bs)]; // rank_1(j*bs*64) in B
714 size_type pos = 0;
715 // size_type rank0 = 0;
716
717 if (rank1 > 0 and (m_v->high[j - 1]) & 1)
718 {
719 pos = (j - rank1) * bs + m_v->low[rank1 - 1]; // starting position of current block
720 // rank0 = pos + 1 - rank1;
721 }
722 else
723 {
724 pos = (j - rank1) * bs; // starting position of current block
725 // rank0 = pos - rank1;
726 }
727 uint64_t w = m_v->high.get_int(j, 64);
728 do {
729 uint64_t _rank1 = rank1 + bits::cnt(w);
730 uint64_t _rank0 = 0;
731 if (_rank1 > 0 and (w >> 63) & 1)
732 {
733 pos = (j + 64 - _rank1) * bs + m_v->low[_rank1 - 1];
734 _rank0 = pos + 1 - _rank1;
735 }
736 else
737 {
738 pos = (j + 64 - _rank1) * bs;
739 _rank0 = pos - _rank1;
740 }
741 if (_rank0 < i)
742 {
743 j += 64;
744 w = m_v->high.get_int(j, 64);
745 rank1 = _rank1;
746 }
747 else
748 {
749 break;
750 }
751 } while (true);
752 // invariant i >zeros
753 do {
754 uint64_t _rank1 = rank1 + bits::lt_cnt[w & 0xFFULL];
755 uint64_t _rank0 = 0;
756 if (_rank1 > 0 and (w >> 7) & 1)
757 {
758 pos = (j + 8 - _rank1) * bs + m_v->low[_rank1 - 1];
759 _rank0 = pos + 1 - _rank1;
760 }
761 else
762 {
763 pos = (j + 8 - _rank1) * bs;
764 _rank0 = pos - _rank1;
765 }
766 if (_rank0 < i)
767 {
768 j += 8;
769 w >>= 8;
770 rank1 = _rank1;
771 }
772 else
773 {
774 break;
775 }
776 } while (true);
777
778 do {
779 bool b = w & 1ULL;
780 w >>= 1; // zeros are shifted in
781 ++j;
782 if (0 == b)
783 {
784 pos = (j - rank1) * bs;
785 size_type zeros = pos - rank1;
786 if (zeros >= i)
787 {
788 pos = pos - (zeros - i) - 1;
789 break;
790 }
791 }
792 else
793 {
794 pos = (j - 1 - rank1) * bs;
795 size_type one_pos = pos + m_v->low[rank1];
796 ++rank1;
797 size_type zeros = one_pos + 1 - rank1;
798 if (zeros >= i)
799 {
800 pos = one_pos - (zeros - i) - 1;
801 break;
802 }
803 }
804 if (j % 64 == 0) { w = m_v->high.get_int(j, 64); }
805 } while (true);
806 return pos;
807 }
808
809 size_type operator()(size_type i) const { return select(i); }
810
811 size_type size() const { return m_v->size(); }
812
813 void set_vector(const bit_vector_type * v = nullptr) { m_v = v; }
814
815 void load(std::istream & in, const bit_vector_type * v = nullptr)
816 {
817 m_pointer.load(in);
818 m_rank1.load(in);
819 set_vector(v);
820 }
821
822 size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const
823 {
824 structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
825 size_type written_bytes = 0;
826 written_bytes += m_pointer.serialize(out, child, "pointer");
827 written_bytes += m_rank1.serialize(out, child, "rank1");
828 structure_tree::add_size(child, written_bytes);
829 return written_bytes;
830 }
831
832 template <typename archive_t>
833 void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const
834 {
835 ar(CEREAL_NVP(m_pointer));
836 ar(CEREAL_NVP(m_rank1));
837 }
838
839 template <typename archive_t>
840 void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar)
841 {
842 ar(CEREAL_NVP(m_pointer));
843 ar(CEREAL_NVP(m_rank1));
844 }
845
846 bool operator==(const select_0_support_sd & other) const noexcept
847 {
848 return (m_pointer == other.m_pointer) && (m_rank1 == other.m_rank1);
849 }
850
851 bool operator!=(const select_0_support_sd & other) const noexcept { return !(*this == other); }
852};
853
855 : m_size(0)
856 , m_capacity(0)
857 , m_wl(0)
858 , m_tail(0)
859 , m_items(0)
860 , m_last_high(0)
861 , m_highpos(0)
862{}
863
865 : m_size(n)
866 , m_capacity(m)
867 , m_wl(0)
868 , m_tail(0)
869 , m_items(0)
870 , m_last_high(0)
871 , m_highpos(0)
872{
873 if (m_capacity > m_size)
874 {
875 throw std::runtime_error("sd_vector_builder: requested capacity is larger than vector size.");
876 }
877
878 size_type logm = bits::hi(m_capacity) + 1, logn = bits::hi(m_size) + 1;
879 if (logm == logn)
880 {
881 logm--; // to ensure logn-logm > 0
882 }
883 m_wl = logn - logm;
884 m_low = int_vector<>(m_capacity, 0, m_wl);
885 m_high = bit_vector(m_capacity + (1ULL << logm), 0);
886}
887
888template <>
890{
891 if (builder.items() != builder.capacity()) { throw std::runtime_error("sd_vector: the builder is not full."); }
892
893 m_size = builder.m_size;
894 m_wl = builder.m_wl;
895 m_low = std::move(builder.m_low);
896 m_high = std::move(builder.m_high);
897 util::init_support(m_high_1_select, &m_high);
898 util::init_support(m_high_0_select, &m_high);
899
900 builder = sd_vector_builder();
901}
902
903} // namespace sdsl
904#endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:31
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.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:566
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.
Definition: sd_vector.hpp:476
bit_vector::size_type size_type
Definition: sd_vector.hpp:480
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
Definition: sd_vector.hpp:481
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
Definition: sd_vector.hpp:531
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Definition: sd_vector.hpp:535
size_type operator()(size_type i) const
Definition: sd_vector.hpp:517
rank_support_sd(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:495
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: sd_vector.hpp:525
bool operator==(const rank_support_sd &other) const noexcept
Definition: sd_vector.hpp:538
void load(std::istream &, const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:523
size_type rank(size_type i) const
Definition: sd_vector.hpp:497
void set_vector(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:521
bool operator!=(const rank_support_sd &other) const noexcept
Definition: sd_vector.hpp:540
size_type size() const
Definition: sd_vector.hpp:519
Class for in-place construction of sd_vector from a strictly increasing sequence.
Definition: sd_vector.hpp:43
size_type items() const
Definition: sd_vector.hpp:71
size_type tail() const
Definition: sd_vector.hpp:70
bit_vector::size_type size_type
Definition: sd_vector.hpp:48
void set(size_type i)
Set a bit to 1.
Definition: sd_vector.hpp:77
size_type capacity() const
Definition: sd_vector.hpp:69
size_type size() const
Definition: sd_vector.hpp:68
A bit vector which compresses very sparse populated bit vectors by.
Definition: sd_vector.hpp:115
const select_1_support_type & high_1_select
Definition: sd_vector.hpp:149
t_select_1 select_1_support_type
Definition: sd_vector.hpp:124
select_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_1_type
Definition: sd_vector.hpp:129
rank_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_0_type
Definition: sd_vector.hpp:126
bit_vector::size_type size_type
Definition: sd_vector.hpp:117
sd_vector(const bit_vector &bv)
Definition: sd_vector.hpp:194
sd_vector(sd_vector &&sd)
Definition: sd_vector.hpp:192
iterator end() const
Definition: sd_vector.hpp:439
const hi_bit_vector_type & high
Definition: sd_vector.hpp:147
void load(std::istream &in)
Loads the data structure from the given istream.
Definition: sd_vector.hpp:403
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
Definition: sd_vector.hpp:298
iterator const_iterator
Definition: sd_vector.hpp:121
size_type value_type
Definition: sd_vector.hpp:118
t_select_0 select_0_support_type
Definition: sd_vector.hpp:123
t_hi_bit_vector hi_bit_vector_type
Definition: sd_vector.hpp:131
sd_vector(const t_itr begin, const t_itr end)
Definition: sd_vector.hpp:236
sd_vector & operator=(sd_vector &&v)
Definition: sd_vector.hpp:176
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
Definition: sd_vector.hpp:388
rank_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_1_type
Definition: sd_vector.hpp:127
const uint8_t & wl
Definition: sd_vector.hpp:146
bit_vector::difference_type difference_type
Definition: sd_vector.hpp:119
sd_vector(sd_vector_builder &builder)
Definition: sd_vector.hpp:271
random_access_const_iterator< sd_vector > iterator
Definition: sd_vector.hpp:120
sd_vector & operator=(const sd_vector &v)
Definition: sd_vector.hpp:166
bool operator==(const sd_vector &v) const
Definition: sd_vector.hpp:441
bv_tag index_category
Definition: sd_vector.hpp:122
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.
Definition: sd_vector.hpp:328
select_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_0_type
Definition: sd_vector.hpp:128
bool operator!=(const sd_vector &v) const
Definition: sd_vector.hpp:446
const int_vector & low
Definition: sd_vector.hpp:148
const select_0_support_type & high_0_select
Definition: sd_vector.hpp:150
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: sd_vector.hpp:414
sd_vector(const sd_vector &sd)
Definition: sd_vector.hpp:154
size_type size() const
Returns the size of the original bit vector.
Definition: sd_vector.hpp:385
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: sd_vector.hpp:425
iterator begin() const
Definition: sd_vector.hpp:437
Select_0 data structure for sd_vector.
Definition: sd_vector.hpp:648
bool operator!=(const select_0_support_sd &other) const noexcept
Definition: sd_vector.hpp:851
void set_vector(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:813
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Definition: sd_vector.hpp:833
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Definition: sd_vector.hpp:840
select_0_support_sd(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:670
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: sd_vector.hpp:822
void load(std::istream &in, const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:815
bit_vector::size_type size_type
Definition: sd_vector.hpp:650
typename t_sd_vector::rank_1_type rank_1
Definition: sd_vector.hpp:652
bool operator==(const select_0_support_sd &other) const noexcept
Definition: sd_vector.hpp:846
size_type operator()(size_type i) const
Definition: sd_vector.hpp:809
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
Definition: sd_vector.hpp:709
size_type size() const
Definition: sd_vector.hpp:811
typename t_sd_vector::select_0_type sel0_type
Definition: sd_vector.hpp:653
Select data structure for sd_vector.
Definition: sd_vector.hpp:594
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
Definition: sd_vector.hpp:630
bool operator!=(const select_support_sd &other) const noexcept
Definition: sd_vector.hpp:639
bool operator==(const select_support_sd &other) const noexcept
Definition: sd_vector.hpp:637
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
Definition: sd_vector.hpp:597
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
Definition: sd_vector.hpp:634
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Definition: sd_vector.hpp:624
void set_vector(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:620
void load(std::istream &, const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:622
size_type operator()(size_type i) const
Definition: sd_vector.hpp:616
select_support_sd(const bit_vector_type *v=nullptr)
Definition: sd_vector.hpp:611
size_type size() const
Definition: sd_vector.hpp:618
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
Definition: sd_vector.hpp:614
bit_vector::size_type size_type
Definition: sd_vector.hpp:596
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.
Number of set bits in v t_int_vec::size_type cnt_one_bits(const t_int_vec &v)
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
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", const T *t=nullptr)
Definition: io.hpp:325
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:686
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 constexpr uint8_t lt_cnt[256]
Lookup table for byte popcounts.
Definition: bits.hpp:163
static size_type adjust_rank(size_type r, size_type n)
Definition: sd_vector.hpp:464
bit_vector::size_type size_type
Definition: sd_vector.hpp:463
static size_type adjust_rank(size_type r, size_type)
Definition: sd_vector.hpp:457
bit_vector::size_type size_type
Definition: sd_vector.hpp:456
static size_type select(size_type i, const t_sd_vec *v)
Definition: sd_vector.hpp:559
static size_type select(size_type i, const t_sd_vec *v)
Definition: sd_vector.hpp:547
bit_vector::size_type size_type
Definition: sd_vector.hpp:546
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.