SDSL  3.0.0
Succinct Data Structure Library
select_support_mcl.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
8 #ifndef INCLUDED_SDSL_SELECT_SUPPORT_MCL
9 #define INCLUDED_SDSL_SELECT_SUPPORT_MCL
10 
11 #include <sdsl/int_vector.hpp>
12 #include <sdsl/select_support.hpp>
13 #include <sdsl/util.hpp>
14 
16 namespace sdsl
17 {
18 
20 
54 template <uint8_t t_b = 1, uint8_t t_pat_len = 1>
56 {
57  private:
58  static_assert(t_b == 1u or t_b == 0u or t_b == 10u or t_b == 11u,
59  "select_support_mcl: bit pattern must be `0`,`1`,`10`, `01`, or `11`");
60  static_assert(t_pat_len == 1u or t_pat_len == 2u, "select_support_mcl: bit pattern length must be 1 or 2");
61 
62  public:
64  enum
65  {
66  bit_pat = t_b
67  };
68  enum
69  {
70  bit_pat_len = t_pat_len
71  };
72 
73  private:
74  uint32_t m_logn = 0, // \f$ log(size) \f$
75  m_logn2 = 0, // \f$ log^2(size) \f$
76  m_logn4 = 0; // \f$ log^4(size) \f$
77  // entry i of m_superblock equals the answer to select_1(B,i*4096)
78  int_vector<0> m_superblock;
79  int_vector<0> * m_longsuperblock = nullptr;
80  int_vector<0> * m_miniblock = nullptr;
81  size_type m_arg_cnt = 0;
82  void initData();
83  void init_fast(const bit_vector * v = nullptr);
84 
85  public:
86  explicit select_support_mcl(const bit_vector * v = nullptr);
90 
91  void init_slow(const bit_vector * v = nullptr);
93  inline size_type select(size_type i) const;
95  inline size_type operator()(size_type i) const;
96  size_type serialize(std::ostream & out, structure_tree_node * v = nullptr, std::string name = "") const;
97  void load(std::istream & in, const bit_vector * v = nullptr);
98  void set_vector(const bit_vector * v = nullptr);
100  template <typename archive_t>
101  void CEREAL_SAVE_FUNCTION_NAME(archive_t & ar) const;
103  template <typename archive_t>
104  void CEREAL_LOAD_FUNCTION_NAME(archive_t & ar);
107  bool operator==(const select_support_mcl & other) const noexcept;
108  bool operator!=(const select_support_mcl & other) const noexcept;
109 };
110 
111 template <uint8_t t_b, uint8_t t_pat_len>
113  : select_support(f_v)
114 {
115  if (t_pat_len > 1 or (vv != nullptr and vv->size() < 100000))
116  init_slow(vv);
117  else
118  init_fast(vv);
119  return;
120 }
121 
122 template <uint8_t t_b, uint8_t t_pat_len>
124  : select_support(ss.m_v)
125  , m_logn(ss.m_logn)
126  , m_logn2(ss.m_logn2)
127  , m_logn4(ss.m_logn4)
128  , m_superblock(ss.m_superblock)
129  , m_arg_cnt(ss.m_arg_cnt)
130 {
131  size_type sb = (m_arg_cnt + 4095) >> 12;
132  if (ss.m_longsuperblock != nullptr)
133  {
134  m_longsuperblock = new int_vector<0>[sb]; // copy longsuperblocks
135  for (size_type i = 0; i < sb; ++i) { m_longsuperblock[i] = ss.m_longsuperblock[i]; }
136  }
137  m_miniblock = nullptr;
138  if (ss.m_miniblock != nullptr)
139  {
140  m_miniblock = new int_vector<0>[sb]; // copy miniblocks
141  for (size_type i = 0; i < sb; ++i) { m_miniblock[i] = ss.m_miniblock[i]; }
142  }
143 }
144 
145 template <uint8_t t_b, uint8_t t_pat_len>
147  : select_support(ss.m_v)
148 {
149  *this = std::move(ss);
150 }
151 
152 template <uint8_t t_b, uint8_t t_pat_len>
154 {
155  if (this != &ss)
156  {
157  select_support_mcl tmp(ss);
158  *this = std::move(tmp);
159  }
160  return *this;
161 }
162 
163 template <uint8_t t_b, uint8_t t_pat_len>
165 {
166  if (this != &ss)
167  {
168  m_logn = ss.m_logn; // copy log n
169  m_logn2 = ss.m_logn2; // copy (logn)^2
170  m_logn4 = ss.m_logn4; // copy (logn)^4
171  m_superblock = std::move(ss.m_superblock); // move long superblock
172  m_arg_cnt = ss.m_arg_cnt; // copy count of 1-bits
173  m_v = ss.m_v; // copy pointer to the supported bit vector
174 
175  delete[] m_longsuperblock;
176  m_longsuperblock = ss.m_longsuperblock;
177  ss.m_longsuperblock = nullptr;
178 
179  delete[] m_miniblock;
180  m_miniblock = ss.m_miniblock;
181  ss.m_miniblock = nullptr;
182  }
183  return *this;
184 }
185 
186 template <uint8_t t_b, uint8_t t_pat_len>
188 {
189  delete[] m_longsuperblock;
190  delete[] m_miniblock;
191 }
192 
193 template <uint8_t t_b, uint8_t t_pat_len>
195 {
196  set_vector(v);
197  initData();
198  if (m_v == nullptr) return;
199  // Count the number of arguments in the bit vector
201 
202  const size_type SUPER_BLOCK_SIZE = 4096;
203 
204  if (m_arg_cnt == 0) // if there are no arguments in the vector we are done...
205  return;
206 
207  size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE; // number of superblocks
208  delete[] m_miniblock;
209  m_miniblock = new int_vector<0>[sb];
210 
211  m_superblock = int_vector<0>(sb, 0, m_logn);
212 
213  size_type arg_position[SUPER_BLOCK_SIZE], arg_cnt = 0;
214  size_type sb_cnt = 0;
215  for (size_type i = 0; i < v->size(); ++i)
216  {
218  {
219  arg_position[arg_cnt % SUPER_BLOCK_SIZE] = i;
220  assert(arg_position[arg_cnt % SUPER_BLOCK_SIZE] == i);
221  ++arg_cnt;
222  if (arg_cnt % SUPER_BLOCK_SIZE == 0 or arg_cnt == m_arg_cnt)
223  { //
224  assert(sb_cnt < sb);
225  m_superblock[sb_cnt] = arg_position[0];
226 
227  size_type pos_diff = arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE] - arg_position[0];
228  if (pos_diff > m_logn4)
229  { // longblock
230  if (m_longsuperblock == nullptr) m_longsuperblock = new int_vector<0>[sb]; // create longsuperblock
231  m_longsuperblock[sb_cnt] = int_vector<0>(SUPER_BLOCK_SIZE,
232  0,
233  bits::hi(arg_position[(arg_cnt - 1) % SUPER_BLOCK_SIZE]) +
234  1);
235 
236  for (size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; ++j)
237  m_longsuperblock[sb_cnt][j] = arg_position[j]; // copy argument positions to longsuperblock
238  }
239  else
240  { // short block
241  m_miniblock[sb_cnt] = int_vector<0>(64, 0, bits::hi(pos_diff) + 1);
242  for (size_type j = 0; j <= (arg_cnt - 1) % SUPER_BLOCK_SIZE; j += 64)
243  {
244  m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
245  }
246  }
247  ++sb_cnt;
248  }
249  }
250  }
251 }
252 
253 template <uint8_t t_b, uint8_t t_pat_len>
255 {
256  set_vector(v);
257  initData();
258  if (m_v == nullptr) return;
259  // Count the number of arguments in the bit vector
261 
262  const size_type SUPER_BLOCK_SIZE = 64 * 64;
263 
264  if (m_arg_cnt == 0) // if there are no arguments in the vector we are done...
265  return;
266 
267  // size_type sb = (m_arg_cnt+63+SUPER_BLOCK_SIZE-1)/SUPER_BLOCK_SIZE; // number of superblocks, add 63 as the
268  // last block could contain 63 uninitialized bits
269  size_type sb = (m_arg_cnt + SUPER_BLOCK_SIZE - 1) / SUPER_BLOCK_SIZE; // number of superblocks
270  delete[] m_miniblock;
271  m_miniblock = new int_vector<0>[sb];
272 
273  m_superblock = int_vector<0>(sb, 0, m_logn); // TODO: hier koennte man logn noch optimieren...s
274 
275  bit_vector::size_type arg_position[SUPER_BLOCK_SIZE];
276  const uint64_t * data = v->data();
277  uint64_t carry_new = 0;
278  size_type last_k64 = 1, sb_cnt = 0;
279  for (size_type i = 0, cnt_old = 0, cnt_new = 0, last_k64_sum = 1; i < (((v->bit_size() + 63) >> 6) << 6);
280  i += 64, ++data)
281  {
282  cnt_new += select_support_trait<t_b, t_pat_len>::args_in_the_word(*data, carry_new);
283  cnt_new = std::min(cnt_new,
284  m_arg_cnt); // For (0, 1), we may find nonexistent args in the padding after the bitvector.
285  if (cnt_new >= last_k64_sum)
286  {
287  arg_position[last_k64 - 1] = i + select_support_trait<t_b, t_pat_len>::ith_arg_pos_in_the_word(
288  *data,
289  last_k64_sum - cnt_old,
290  carry_new);
291  last_k64 += 64;
292  last_k64_sum += 64;
293 
294  if (last_k64 == SUPER_BLOCK_SIZE + 1)
295  {
296  m_superblock[sb_cnt] = arg_position[0];
297  size_type pos_of_last_arg_in_the_block = arg_position[last_k64 - 65];
298 
299  for (size_type ii = arg_position[last_k64 - 65] + 1, j = last_k64 - 65;
300  ii < v->size() and j < SUPER_BLOCK_SIZE;
301  ++ii)
303  {
304  pos_of_last_arg_in_the_block = ii;
305  ++j;
306  }
307  size_type pos_diff = pos_of_last_arg_in_the_block - arg_position[0];
308  if (pos_diff > m_logn4)
309  { // long block
310  if (m_longsuperblock == nullptr)
311  m_longsuperblock = new int_vector<0>[sb + 1]; // create longsuperblock
312  // GEANDERT am 2010-07-17 +1 nach pos_of_last_arg..
313  m_longsuperblock[sb_cnt] = int_vector<0>(SUPER_BLOCK_SIZE,
314  0,
315  bits::hi(pos_of_last_arg_in_the_block) + 1);
316  for (size_type j = arg_position[0], k = 0;
317  k < SUPER_BLOCK_SIZE and j <= pos_of_last_arg_in_the_block;
318  ++j)
320  {
321  if (k >= SUPER_BLOCK_SIZE)
322  {
323  for (size_type ii = 0; ii < SUPER_BLOCK_SIZE; ++ii)
324  {
325  std::cout << "(" << ii << "," << m_longsuperblock[sb_cnt][ii] << ") ";
326  }
327  std::cout << std::endl;
328  std::cout << "k=" << k << " SUPER_BLOCK_SIZE=" << SUPER_BLOCK_SIZE << std::endl;
329  std::cout << "pos_of_last_arg_in_the_block" << pos_of_last_arg_in_the_block
330  << std::endl;
331  std::cout.flush();
332  }
333  m_longsuperblock[sb_cnt][k++] = j;
334  }
335  }
336  else
337  {
338  m_miniblock[sb_cnt] = int_vector<0>(64, 0, bits::hi(pos_diff) + 1);
339  for (size_type j = 0; j < SUPER_BLOCK_SIZE; j += 64)
340  {
341  m_miniblock[sb_cnt][j / 64] = arg_position[j] - arg_position[0];
342  }
343  }
344  ++sb_cnt;
345  last_k64 = 1;
346  }
347  }
348  cnt_old = cnt_new;
349  }
350  // handle last block: append long superblock
351  if (last_k64 > 1)
352  {
353  if (m_longsuperblock == nullptr) m_longsuperblock = new int_vector<0>[sb + 1]; // create longsuperblock
354  m_longsuperblock[sb_cnt] = int_vector<0>(SUPER_BLOCK_SIZE, 0, bits::hi(v->size() - 1) + 1);
355  for (size_type i = arg_position[0], k = 0; i < v->size(); ++i)
356  {
357  if (select_support_trait<t_b, t_pat_len>::found_arg(i, *v)) { m_longsuperblock[sb_cnt][k++] = i; }
358  }
359  ++sb_cnt;
360  }
361 }
362 
363 template <uint8_t t_b, uint8_t t_pat_len>
365 {
366  assert(i > 0 and i <= m_arg_cnt);
367 
368  i = i - 1;
369  size_type sb_idx = i >> 12; // i/4096
370  size_type offset = i & 0xFFF; // i%4096
371  if (m_longsuperblock != nullptr and !m_longsuperblock[sb_idx].empty()) { return m_longsuperblock[sb_idx][offset]; }
372  else
373  {
374  if ((offset & 0x3F) == 0)
375  {
376  assert(sb_idx < m_superblock.size());
377  assert((offset >> 6) < m_miniblock[sb_idx].size());
378  return m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6 /*/64*/];
379  }
380  else
381  {
382  i = i - (sb_idx << 12) - ((offset >> 6) << 6);
383  // now i > 0 and i <= 64
384  assert(i > 0);
385  size_type pos = m_superblock[sb_idx] + m_miniblock[sb_idx][offset >> 6] + 1;
386 
387  // now pos is the position from where we search for the ith argument
388  size_type word_pos = pos >> 6;
389  size_type word_off = pos & 0x3F;
390  const uint64_t * data = m_v->data() + word_pos;
391  uint64_t carry = select_support_trait<t_b, t_pat_len>::init_carry(data, word_pos);
393 
394  if (args >= i)
395  {
396  return (word_pos << 6) +
398  }
399  word_pos += 1;
400  size_type sum_args = args;
402  uint64_t old_carry = carry;
404  while (sum_args + args < i)
405  {
406  sum_args += args;
407  assert(data + 1 < m_v->data() + ((m_v->bit_size() + 63) >> 6));
408  old_carry = carry;
410  word_pos += 1;
411  }
412  return (word_pos << 6) +
414  }
415  }
416 }
417 
418 template <uint8_t t_b, uint8_t t_pat_len>
420 {
421  return select(i);
422 }
423 
424 template <uint8_t t_b, uint8_t t_pat_len>
426 {
427  m_arg_cnt = 0;
428  if (nullptr == m_v) { m_logn = m_logn2 = m_logn4 = 0; }
429  else
430  {
431  m_logn = bits::hi(((m_v->bit_size() + 63) >> 6) << 6) + 1; // TODO maybe it's better here to take a max(...,12)
432  m_logn2 = m_logn * m_logn;
433  m_logn4 = m_logn2 * m_logn2;
434  }
435  delete[] m_longsuperblock;
436  m_longsuperblock = nullptr;
437  delete[] m_miniblock;
438  m_miniblock = nullptr;
439 }
440 
441 template <uint8_t t_b, uint8_t t_pat_len>
443 {
444  m_v = v;
445 }
446 
447 template <uint8_t t_b, uint8_t t_pat_len>
448 auto select_support_mcl<t_b, t_pat_len>::serialize(std::ostream & out, structure_tree_node * v, std::string name) const
449  -> size_type
450 {
451  structure_tree_node * child = structure_tree::add_child(v, name, util::class_name(*this));
452  size_type written_bytes = 0;
453  // write the number of 1-bits in the supported bit_vector
454  out.write((char *)&m_arg_cnt, sizeof(size_type) / sizeof(char));
455  written_bytes = sizeof(size_type) / sizeof(char);
456  // number of superblocks in the data structure
457  size_type sb = (m_arg_cnt + 4095) >> 12;
458 
459  if (m_arg_cnt)
460  { // if there exists 1-bits to be supported
461  written_bytes += m_superblock.serialize(out, child, "superblock"); // serialize superblocks
462  bit_vector mini_or_long; // Helper vector: mini or long block?
463  if (m_longsuperblock != nullptr)
464  {
465  mini_or_long.resize(sb); // resize indicator bit_vector to the number of superblocks
466  for (size_type i = 0; i < sb; ++i) mini_or_long[i] = !m_miniblock[i].empty();
467  }
468  written_bytes += mini_or_long.serialize(out, child, "mini_or_long");
469  size_type written_bytes_long = 0;
470  size_type written_bytes_mini = 0;
471  for (size_type i = 0; i < sb; ++i)
472  if (!mini_or_long.empty() and !mini_or_long[i])
473  {
474  written_bytes_long += m_longsuperblock[i].serialize(out);
475  }
476  else
477  {
478  written_bytes_mini += m_miniblock[i].serialize(out);
479  }
480  written_bytes += written_bytes_long;
481  written_bytes += written_bytes_mini;
483  child, "longsuperblock", util::class_name(m_longsuperblock));
484  structure_tree::add_size(child_long, written_bytes_long);
486  child, "minisuperblock", util::class_name(m_miniblock));
487  structure_tree::add_size(child_mini, written_bytes_mini);
488  }
489  structure_tree::add_size(child, written_bytes);
490  return written_bytes;
491 }
492 
493 template <uint8_t t_b, uint8_t t_pat_len>
494 void select_support_mcl<t_b, t_pat_len>::load(std::istream & in, const bit_vector * v)
495 {
496  set_vector(v);
497  initData();
498  // read the number of 1-bits in the supported bit_vector
499  in.read((char *)&m_arg_cnt, sizeof(size_type) / sizeof(char));
500  size_type sb = (m_arg_cnt + 4095) >> 12;
501 
502  if (m_arg_cnt)
503  { // if there exists 1-bits to be supported
504  m_superblock.load(in); // load superblocks
505 
506  delete[] m_miniblock;
507  m_miniblock = nullptr;
508  delete[] m_longsuperblock;
509  m_longsuperblock = nullptr;
510 
511  bit_vector mini_or_long; // Helper vector: mini or long block?
512  mini_or_long.load(in); // Load the helper vector
513  m_miniblock = new int_vector<0>[sb]; // Create miniblock int_vector<0>
514  if (!mini_or_long.empty()) m_longsuperblock = new int_vector<0>[sb]; // Create longsuperblock int_vector<0>
515 
516  for (size_type i = 0; i < sb; ++i)
517  if (!mini_or_long.empty() and not mini_or_long[i]) { m_longsuperblock[i].load(in); }
518  else
519  {
520  m_miniblock[i].load(in);
521  }
522  }
523 }
524 
525 template <uint8_t t_b, uint8_t t_pat_len>
526 template <typename archive_t>
528 {
529  ar(CEREAL_NVP(m_arg_cnt));
530  ar(CEREAL_NVP(m_logn));
531  ar(CEREAL_NVP(m_logn2));
532  ar(CEREAL_NVP(m_logn4));
533  size_type sb = (m_arg_cnt + 4095) >> 12;
534  if (m_arg_cnt)
535  {
536  ar(CEREAL_NVP(m_superblock));
537  bit_vector mini_or_long;
538  if (m_longsuperblock != nullptr)
539  {
540  mini_or_long.resize(sb);
541  for (size_type i = 0; i < sb; ++i) { mini_or_long[i] = !m_miniblock[i].empty(); }
542  }
543  ar(CEREAL_NVP(mini_or_long));
544  for (size_type i = 0; i < sb; ++i)
545  {
546  if (!mini_or_long.empty() and !mini_or_long[i]) { ar(CEREAL_NVP(m_longsuperblock[i])); }
547  else
548  {
549  ar(CEREAL_NVP(m_miniblock[i]));
550  }
551  }
552  }
553 }
554 
555 template <uint8_t t_b, uint8_t t_pat_len>
556 template <typename archive_t>
558 {
559  delete[] m_longsuperblock;
560  m_longsuperblock = nullptr;
561  delete[] m_miniblock;
562  m_miniblock = nullptr;
563 
564  ar(CEREAL_NVP(m_arg_cnt));
565  ar(CEREAL_NVP(m_logn));
566  ar(CEREAL_NVP(m_logn2));
567  ar(CEREAL_NVP(m_logn4));
568 
569  size_type sb = (m_arg_cnt + 4095) >> 12;
570 
571  if (m_arg_cnt)
572  {
573  ar(CEREAL_NVP(m_superblock));
574 
575  delete[] m_miniblock;
576  m_miniblock = nullptr;
577  delete[] m_longsuperblock;
578  m_longsuperblock = nullptr;
579 
580  bit_vector mini_or_long;
581  ar(CEREAL_NVP(mini_or_long));
582  m_miniblock = new int_vector<0>[sb];
583 
584  if (!mini_or_long.empty()) { m_longsuperblock = new int_vector<0>[sb]; }
585 
586  for (size_type i = 0; i < sb; ++i)
587  {
588  if (!mini_or_long.empty() and !mini_or_long[i]) { ar(CEREAL_NVP(m_longsuperblock[i])); }
589  else
590  {
591  ar(CEREAL_NVP(m_miniblock[i]));
592  }
593  }
594  }
595 }
596 
597 template <uint8_t t_b, uint8_t t_pat_len>
599 {
600  return (m_logn == other.m_logn) && (m_logn2 == other.m_logn2) && (m_logn4 == other.m_logn4) &&
601  (m_superblock == other.m_superblock) && (m_arg_cnt == other.m_arg_cnt) &&
602  ((m_longsuperblock == nullptr && other.m_longsuperblock == nullptr) ||
603  (*m_longsuperblock == *other.m_longsuperblock)) &&
604  ((m_miniblock == other.m_miniblock) || (*m_miniblock == *other.m_miniblock));
605 }
606 
607 template <uint8_t t_b, uint8_t t_pat_len>
609 {
610  return !(*this == other);
611 }
612 } // namespace sdsl
613 
614 #endif
#define CEREAL_NVP(X)
Definition: cereal.hpp:30
bool empty() const noexcept
Equivalent to size() == 0.
Definition: int_vector.hpp:524
int_vector_size_type size_type
Definition: int_vector.hpp:266
size_type bit_size() const noexcept
The number of bits in the int_vector.
Definition: int_vector.hpp:571
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.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Definition: int_vector.hpp:545
A class supporting constant time select queries.
select_support_mcl< t_b, t_pat_len > & operator=(select_support_mcl &&)
void init_slow(const bit_vector *v=nullptr)
select_support_mcl(select_support_mcl< t_b, t_pat_len > &&ss)
size_type select(size_type i) const
Select function.
bool operator==(const select_support_mcl &other) const noexcept
void load(std::istream &in, const bit_vector *v=nullptr)
Load the select_support from an in file stream.
bool operator!=(const select_support_mcl &other) const noexcept
select_support_mcl(const bit_vector *v=nullptr)
size_type operator()(size_type i) const
Alias for select(i).
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serialize the select_support to an out file stream.
select_support_mcl(const select_support_mcl< t_b, t_pat_len > &ss)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
Serialise (save) via cereal.
select_support_mcl< t_b, t_pat_len > & operator=(const select_support_mcl &ss)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Serialise (load) via cereal.
void set_vector(const bit_vector *v=nullptr)
This method sets the supported bit_vector.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
const bit_vector * vv
int_vector< 1 >::size_type size_type
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.
int_vector ::size_type size_type
Namespace for the succinct data structure library.
bool empty(const range_type &r)
Empty range check.
Definition: wt_helper.hpp:782
int_vector ::size_type size(const range_type &r)
Size of a range.
Definition: wt_helper.hpp:787
select_support.hpp contains classes that support a sdsl::bit_vector with constant time select informa...
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 uint64_t get_carry(uint64_t)
static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
static size_type args_in_the_word(uint64_t, uint64_t &)
static uint64_t init_carry(const uint64_t *, size_type)
static bool found_arg(size_type, const bit_vector &)
static size_type arg_cnt(const bit_vector &)
static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.