SDSL  3.0.0
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 
18 namespace sdsl
19 {
20 
21 // forward declaration needed for friend declaration
22 template <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>
26 class rank_support_sd; // in sd_vector
27 
28 // forward declaration needed for friend declaration
29 template <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>
33 class select_support_sd; // in sd_vector
34 
35 // forward declaration needed for friend declaration
36 template <typename, typename, typename>
37 class 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
111 template <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 
154  sd_vector(const sd_vector & sd)
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 
194  sd_vector(const bit_vector & bv)
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 
450 template <>
451 sd_vector<>::sd_vector(sd_vector_builder & builder);
452 
453 template <uint8_t t_b>
455 {
457  static size_type adjust_rank(size_type r, size_type) { return r; }
458 };
459 
460 template <>
462 {
464  static size_type adjust_rank(size_type r, size_type n) { return n - r; }
465 };
466 
468 
474 template <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>
535  void CEREAL_LOAD_FUNCTION_NAME(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 
543 template <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 
555 template <class t_sd_vec>
556 struct 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 
592 template <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>
634  void CEREAL_LOAD_FUNCTION_NAME(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 
646 template <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 
888 template <>
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:30
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:266
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
Definition: int_vector.hpp:590
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.
Definition: sd_vector.hpp:476
bit_vector::size_type size_type
Definition: sd_vector.hpp:477
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=(const sd_vector &v)
Definition: sd_vector.hpp:166
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 & operator=(sd_vector &&v)
Definition: sd_vector.hpp:176
sd_vector(sd_vector_builder &builder)
Definition: sd_vector.hpp:271
random_access_const_iterator< sd_vector > iterator
Definition: sd_vector.hpp:120
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 void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
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:51
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 SDSL_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:696
constexpr static 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:197
constexpr static uint8_t lt_cnt[256]
Lookup table for byte popcounts.
Definition: bits.hpp:173
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494
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.