SDSL  3.0.0
Succinct Data Structure Library
rrr_helper.hpp
Go to the documentation of this file.
1 // Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2 // Please see the AUTHORS file for details. Use of this source code is governed
3 // by a BSD license that can be found in the LICENSE file.
9 #ifndef SDSL_RRR_HELPER
10 #define SDSL_RRR_HELPER
11 
12 #ifdef RRR_NO_OPT
13 #ifndef RRR_NO_BS
14 #define RRR_NO_BS
15 #endif
16 #endif
17 
18 #include <algorithm> // for next permutation
19 #include <iostream>
20 
21 #include <sdsl/bits.hpp>
22 #include <sdsl/uint128_t.hpp>
23 #include <sdsl/uint256_t.hpp>
24 
25 namespace sdsl
26 {
27 
29 
31 template <uint16_t log_n>
33 {
34  typedef uint64_t number_type;
35  static inline uint16_t hi(number_type x) { return bits::hi(x); }
36 
38 
44  template <class bit_vector_type>
45  static inline number_type get_int(const bit_vector_type & bv, typename bit_vector_type::size_type pos, uint16_t len)
46  {
47  return bv.get_int(pos, len);
48  }
49 
51 
57  template <class bit_vector_type>
58  static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
59  {
60  bv.set_int(pos, x, len);
61  }
62 
64 
67  static inline uint16_t popcount(number_type x) { return bits::cnt(x); }
68 };
69 
71 template <>
73 {
75  static inline uint16_t hi(number_type x)
76  {
77  if ((x >> 64)) { return bits::hi(x >> 64) + 64; }
78  else
79  {
80  return bits::hi(x);
81  }
82  }
83 
84  template <class bit_vector_type>
85  static inline number_type get_int(const bit_vector_type & bv, typename bit_vector_type::size_type pos, uint16_t len)
86  {
87  if (len <= 64) { return bv.get_int(pos, len); }
88  else
89  {
90  return ((((number_type)bv.get_int(pos + 64, len - 64)) << 64) + bv.get_int(pos, 64));
91  }
92  }
93 
94  template <class bit_vector_type>
95  static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
96  {
97  if (len <= 64) { bv.set_int(pos, x, len); }
98  else
99  {
100  bv.set_int(pos, (uint64_t)x, 64);
101  bv.set_int(pos + 64, x >> 64, len - 64);
102  }
103  }
104 
105  static inline uint16_t popcount(number_type x) { return bits::cnt(x >> 64) + bits::cnt(x); }
106 };
107 
109 template <>
111 {
113  static inline uint16_t hi(number_type x) { return x.hi(); }
114 
115  template <class bit_vector_type>
116  static inline number_type get_int(const bit_vector_type & bv, typename bit_vector_type::size_type pos, uint16_t len)
117  {
118  if (len <= 64) { return number_type(bv.get_int(pos, len)); }
119  else if (len <= 128)
120  {
121  return number_type(bv.get_int(pos, 64), bv.get_int(pos + 64, len - 64));
122  }
123  else if (len <= 192)
124  {
125  return number_type(bv.get_int(pos, 64),
126  bv.get_int(pos + 64, 64),
127  (uint128_t)bv.get_int(pos + 128, len - 128));
128  }
129  else
130  { // > 192
131  return number_type(bv.get_int(pos, 64),
132  bv.get_int(pos + 64, 64),
133  (((uint128_t)bv.get_int(pos + 192, len - 192)) << 64) | bv.get_int(pos + 128, 64));
134  }
135  }
136 
137  template <class bit_vector_type>
138  static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
139  {
140  if (len <= 64) { bv.set_int(pos, x, len); }
141  else if (len <= 128)
142  {
143  bv.set_int(pos, x, 64);
144  bv.set_int(pos + 64, x >> 64, len - 64);
145  }
146  else if (len <= 192)
147  {
148  bv.set_int(pos, x, 64);
149  bv.set_int(pos + 64, x >> 64, 64);
150  bv.set_int(pos + 128, x >> 128, len - 128);
151  }
152  else
153  { // > 192
154  bv.set_int(pos, x, 64);
155  bv.set_int(pos + 64, x >> 64, 64);
156  bv.set_int(pos + 128, x >> 128, 64);
157  bv.set_int(pos + 192, x >> 192, len - 192);
158  }
159  }
160 
161  static inline uint16_t popcount(number_type x) { return x.popcount(); }
162 };
163 
164 template <uint16_t n, class number_type>
166 {
167  static struct impl
168  {
169  number_type table[n + 1][n + 1];
170  number_type L1Mask[n + 1]; // L1Mask[i] contains a word with the i least significant bits set to 1.
171  // i.e. L1Mask[0] = 0, L1Mask[1] = 1,...
172  number_type O1Mask[n]; // O1Mask[i] contains a word with the i least significant bits set to 0.
173 
174  impl()
175  {
176  for (uint16_t k = 0; k <= n; ++k)
177  {
178  table[k][k] = 1; // initialize diagonal
179  }
180  for (uint16_t k = 0; k <= n; ++k)
181  {
182  table[0][k] = 0; // initialize first row
183  }
184  for (uint16_t nn = 0; nn <= n; ++nn)
185  {
186  table[nn][0] = 1; // initialize first column
187  }
188  for (int nn = 1; nn <= n; ++nn)
189  {
190  for (int k = 1; k <= n; ++k) { table[nn][k] = table[nn - 1][k - 1] + table[nn - 1][k]; }
191  }
192  L1Mask[0] = 0;
193  number_type mask = 1;
194  O1Mask[0] = 1;
195  for (int i = 1; i <= n; ++i)
196  {
197  L1Mask[i] = mask;
198  if (i < n) O1Mask[i] = O1Mask[i - 1] << 1;
199  mask = (mask << 1);
200  mask |= (number_type)1;
201  }
202  }
203  } data;
204 };
205 
206 template <uint16_t n, class number_type>
208 
210 
228 template <uint16_t n>
230 {
231  enum
232  {
233  MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6))
234  };
235  static const uint16_t MAX_SIZE = (1 << MAX_LOG);
237  typedef typename trait::number_type number_type;
239 
240  static struct impl
241  {
242  const number_type (&table)[MAX_SIZE + 1][MAX_SIZE + 1] =
243  tBinom::data.table; // table for the binomial coefficients
244  uint16_t space[n + 1]; // for entry i,j \lceil \log( {i \choose j}+1 ) \rceil
245 #ifndef RRR_NO_BS
246  static const uint16_t BINARY_SEARCH_THRESHOLD = n / MAX_LOG;
247 #else
248  static const uint16_t BINARY_SEARCH_THRESHOLD = 0;
249 #endif
250  number_type (&L1Mask)[MAX_SIZE + 1] = tBinom::data.L1Mask;
251  number_type (&O1Mask)[MAX_SIZE] = tBinom::data.O1Mask;
252 
253  impl()
254  {
255  static typename binomial_table<n, number_type>::impl tmp_data;
256  for (int k = 0; k <= n; ++k)
257  {
258  space[k] = (tmp_data.table[n][k] == (number_type)1) ? 0 : trait::hi(tmp_data.table[n][k]) + 1;
259  }
260  }
261  } data;
262 };
263 
264 template <uint16_t n>
266 
268 
279 template <uint16_t n>
281 {
284  typedef typename binomial::trait trait;
285 
287  static inline uint16_t space_for_bt(uint16_t i) { return binomial::data.space[i]; }
288 
289  template <class bit_vector_type>
290  static inline number_type decode_btnr(const bit_vector_type & bv,
291  typename bit_vector_type::size_type btnrp,
292  uint16_t btnrlen)
293  {
294  return trait::get_int(bv, btnrp, btnrlen);
295  }
296 
297  template <class bit_vector_type>
298  static void set_bt(bit_vector_type & bv,
299  typename bit_vector_type::size_type pos,
300  number_type bt,
301  uint16_t space_for_bt)
302  {
303  trait::set_int(bv, pos, bt, space_for_bt);
304  }
305 
306  template <class bit_vector_type>
307  static inline uint16_t get_bt(const bit_vector_type & bv,
308  typename bit_vector_type::size_type pos,
309  uint16_t block_size)
310  {
311  return trait::popcount(trait::get_int(bv, pos, block_size));
312  }
313 
314  static inline number_type bin_to_nr(number_type bin)
315  {
316  if (bin == (number_type)0 or bin == binomial::data.L1Mask[n])
317  { // handle special case
318  return 0;
319  }
320  number_type nr = 0;
321  uint16_t k = trait::popcount(bin);
322  uint16_t nn = n; // size of the block
323  while (bin != (number_type)0)
324  {
325  if (1ULL & bin)
326  {
327  nr += binomial::data.table[nn - 1][k];
328  --k; // go to the case (n-1, k-1)
329  } // else go to the case (n-1, k)
330  bin = (bin >> 1);
331  --nn;
332  }
333  return nr;
334  }
335 
337  static inline bool decode_bit(uint16_t k, number_type nr, uint16_t off)
338  {
339 #ifndef RRR_NO_OPT
340  if (k == n)
341  { // if n==k, then the encoded block consists only of ones
342  return 1;
343  }
344  else if (k == 0)
345  { // if k==0 then the encoded block consists only of zeros
346  return 0;
347  }
348  else if (k == 1)
349  { // if k==1 then the encoded block contains exactly on set bit at
350  return (n - nr - 1) == off; // position n-nr-1
351  }
352 #endif
353  uint16_t nn = n;
354  // if k < n \log n, it is better to do a binary search for each of the on bits
355  if (k + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
356  {
357  while (k > 1)
358  {
359  uint16_t nn_lb = k,
360  nn_rb = nn + 1; // invariant nr >= binomial::data.table[nn_lb-1][k]
361  while (nn_lb < nn_rb)
362  {
363  uint16_t nn_mid = (nn_lb + nn_rb) / 2;
364  if (nr >= binomial::data.table[nn_mid - 1][k]) { nn_lb = nn_mid + 1; }
365  else
366  {
367  nn_rb = nn_mid;
368  }
369  }
370  nn = nn_lb - 1;
371  if (n - nn >= off) { return (n - nn) == off; }
372  nr -= binomial::data.table[nn - 1][k];
373  --k;
374  --nn;
375  }
376  }
377  else
378  { // else do a linear decoding
379  int i = 0;
380  while (k > 1)
381  {
382  if (i > off) { return 0; }
383  if (nr >= binomial::data.table[nn - 1][k])
384  {
385  nr -= binomial::data.table[nn - 1][k];
386  --k;
387  if (i == off) return 1;
388  }
389  --nn;
390  ++i;
391  }
392  }
393  return (n - nr - 1) == off;
394  }
395 
397  static inline uint64_t decode_int(uint16_t k, number_type nr, uint16_t off, uint16_t len)
398  {
399 #ifndef RRR_NO_OPT
400  if (k == n)
401  { // if n==k, then the encoded block consists only of ones
402  return bits::lo_set[len];
403  }
404  else if (k == 0)
405  { // if k==0 then the encoded block consists only of zeros
406  return 0;
407  }
408  else if (k == 1)
409  { // if k==1 then the encoded block contains exactly on set bit at
410  if (n - nr - 1 >= (number_type)off and n - nr - 1 <= (number_type)(off + len - 1))
411  {
412  return 1ULL << ((n - nr - 1) - off);
413  }
414  else
415  return 0;
416  }
417 #endif
418  uint64_t res = 0;
419  uint16_t nn = n;
420  int i = 0;
421  while (k > 1)
422  {
423  if (i > off + len - 1) { return res; }
424  if (nr >= binomial::data.table[nn - 1][k])
425  {
426  nr -= binomial::data.table[nn - 1][k];
427  --k;
428  if (i >= off) res |= 1ULL << (i - off);
429  }
430  --nn;
431  ++i;
432  }
433  if (n - nr - 1 >= (number_type)off and n - nr - 1 <= (number_type)(off + len - 1))
434  {
435  res |= 1ULL << ((n - nr - 1) - off);
436  }
437  return res;
438  }
439 
441  static inline uint16_t decode_popcount(uint16_t k, number_type nr, uint16_t off)
442  {
443 #ifndef RRR_NO_OPT
444  if (k == n)
445  { // if n==k, then the encoded block consists only of ones
446  return off; // i.e. the answer is off
447  }
448  else if (k == 0)
449  { // if k==0, then the encoded block consists only on zeros
450  return 0; // i.e. the result is zero
451  }
452  else if (k == 1)
453  { // if k==1 then the encoded block contains exactly on set bit at
454  return (n - nr - 1) < off; // position n-nr-1, and popcount is 1 if off > (n-nr-1).
455  }
456 #endif
457  uint16_t result = 0;
458  uint16_t nn = n;
459  // if k < n \log n, it is better to do a binary search for each of the on bits
460  if (k + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
461  {
462  while (k > 1)
463  {
464  uint16_t nn_lb = k,
465  nn_rb = nn + 1; // invariant nr >= binomial::data.table[nn_lb-1][k]
466  while (nn_lb < nn_rb)
467  {
468  uint16_t nn_mid = (nn_lb + nn_rb) / 2;
469  if (nr >= binomial::data.table[nn_mid - 1][k]) { nn_lb = nn_mid + 1; }
470  else
471  {
472  nn_rb = nn_mid;
473  }
474  }
475  nn = nn_lb - 1;
476  if (n - nn >= off) { return result; }
477  ++result;
478  nr -= binomial::data.table[nn - 1][k];
479  --k;
480  --nn;
481  }
482  }
483  else
484  {
485  int i = 0;
486  while (k > 1)
487  {
488  if (i >= off) { return result; }
489  if (nr >= binomial::data.table[nn - 1][k])
490  {
491  nr -= binomial::data.table[nn - 1][k];
492  --k;
493  ++result;
494  }
495  --nn;
496  ++i;
497  }
498  }
499  return result + ((n - nr - 1) < off);
500  }
501 
504  static inline uint16_t decode_select(uint16_t k, number_type & nr, uint16_t sel)
505  {
506 #ifndef RRR_NO_OPT
507  if (k == n)
508  { // if n==k, then the encoded block consists only of ones
509  return sel - 1;
510  }
511  else if (k == 1 and sel == 1)
512  {
513  return n - nr - 1;
514  }
515 #endif
516  uint16_t nn = n;
517  // if k < n \log n, it is better to do a binary search for each of the on bits
518  if (sel + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
519  {
520  while (sel > 0)
521  {
522  uint16_t nn_lb = k, nn_rb = nn + 1; // invariant nr >= iii.m_coefficients[nn_lb-1]
523  while (nn_lb < nn_rb)
524  {
525  uint16_t nn_mid = (nn_lb + nn_rb) / 2;
526  if (nr >= binomial::data.table[nn_mid - 1][k]) { nn_lb = nn_mid + 1; }
527  else
528  {
529  nn_rb = nn_mid;
530  }
531  }
532  nn = nn_lb - 1;
533  nr -= binomial::data.table[nn - 1][k];
534  --sel;
535  --nn;
536  --k;
537  }
538  return n - nn - 1;
539  }
540  else
541  {
542  int i = 0;
543  while (sel > 0)
544  { // TODO: this condition only work if the precondition holds
545  if (nr >= binomial::data.table[nn - 1][k])
546  {
547  nr -= binomial::data.table[nn - 1][k];
548  --sel;
549  --k;
550  }
551  --nn;
552  ++i;
553  }
554  return i - 1;
555  }
556  }
557 
560  template <uint8_t pattern, uint8_t len>
561  static inline uint16_t decode_select_bitpattern(uint16_t k, number_type & nr, uint16_t sel)
562  {
563  int i = 0;
564  uint8_t decoded_pattern = 0;
565  uint8_t decoded_len = 0;
566  uint16_t nn = n;
567  while (sel > 0)
568  { // TODO: this condition only work if the precondition holds
569  decoded_pattern = decoded_pattern << 1;
570  ++decoded_len;
571  if (nr >= binomial::data.table[nn - 1][k])
572  {
573  nr -= binomial::data.table[nn - 1][k];
574  // a one is decoded
575  decoded_pattern |= 1; // add to the pattern
576  --k;
577  }
578  --nn;
579  ++i;
580  if (decoded_len == len)
581  { // if decoded pattern length equals len of the searched pattern
582  if (decoded_pattern == pattern)
583  { // and pattern equals the searched pattern
584  --sel;
585  }
586  decoded_pattern = 0;
587  decoded_len = 0; // reset pattern
588  }
589  }
590  return i - len; // return the starting position of $sel$th occurence of the pattern
591  }
592 };
593 
594 } // namespace sdsl
595 #endif
bits.hpp contains the sdsl::bits class.
uint16_t popcount()
Definition: uint256_t.hpp:64
uint16_t hi()
Definition: uint256_t.hpp:70
int_vector ::size_type size_type
Namespace for the succinct data structure library.
size_t block_size(void *ptr)
static void set_int(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
Definition: rrr_helper.hpp:95
static uint16_t popcount(number_type x)
Definition: rrr_helper.hpp:105
static uint16_t hi(number_type x)
Definition: rrr_helper.hpp:75
static number_type get_int(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t len)
Definition: rrr_helper.hpp:85
static uint16_t popcount(number_type x)
Definition: rrr_helper.hpp:161
static void set_int(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
Definition: rrr_helper.hpp:138
static uint16_t hi(number_type x)
Definition: rrr_helper.hpp:113
static number_type get_int(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t len)
Definition: rrr_helper.hpp:116
Trait struct for the binomial coefficient struct to handle different type of integers.
Definition: rrr_helper.hpp:33
static number_type get_int(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t len)
Read a -bit integer of type number_type from a bitvector.
Definition: rrr_helper.hpp:45
static uint16_t popcount(number_type x)
Count the number of set bits in x.
Definition: rrr_helper.hpp:67
static uint16_t hi(number_type x)
Definition: rrr_helper.hpp:35
static void set_int(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
Write a -bit integer x of type number_type to a bitvector.
Definition: rrr_helper.hpp:58
A struct for the binomial coefficients .
Definition: rrr_helper.hpp:230
trait::number_type number_type
Definition: rrr_helper.hpp:237
static const uint16_t MAX_SIZE
Definition: rrr_helper.hpp:235
binomial_table< MAX_SIZE, number_type > tBinom
Definition: rrr_helper.hpp:238
static struct sdsl::binomial_coefficients::impl data
Definition: rrr_helper.hpp:265
binomial_coefficients_trait< MAX_LOG > trait
Definition: rrr_helper.hpp:236
static struct sdsl::binomial_table::impl data
Definition: rrr_helper.hpp:207
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
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
Class to encode and decode binomial coefficients on the fly.
Definition: rrr_helper.hpp:281
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
Definition: rrr_helper.hpp:298
static uint16_t space_for_bt(uint16_t i)
Returns the space usage in bits of the binary representation of the number .
Definition: rrr_helper.hpp:287
static uint64_t decode_int(uint16_t k, number_type nr, uint16_t off, uint16_t len)
Decode the len-bit integer starting at position of the block encoded by the pair (k,...
Definition: rrr_helper.hpp:397
binomial::number_type number_type
The used number type, e.g.
Definition: rrr_helper.hpp:283
static number_type bin_to_nr(number_type bin)
Definition: rrr_helper.hpp:314
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
Definition: rrr_helper.hpp:504
static bool decode_bit(uint16_t k, number_type nr, uint16_t off)
Decode the bit at position of the block encoded by the pair (k, nr).
Definition: rrr_helper.hpp:337
static uint16_t decode_select_bitpattern(uint16_t k, number_type &nr, uint16_t sel)
Definition: rrr_helper.hpp:561
binomial::trait trait
The number trait.
Definition: rrr_helper.hpp:284
static uint16_t get_bt(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
Definition: rrr_helper.hpp:307
static number_type decode_btnr(const bit_vector_type &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
Definition: rrr_helper.hpp:290
static uint16_t decode_popcount(uint16_t k, number_type nr, uint16_t off)
Decode the first off bits bits of the block encoded by the pair (k, nr) and return the set bits.
Definition: rrr_helper.hpp:441
binomial_coefficients< n > binomial
The struct containing the binomial coefficients.
Definition: rrr_helper.hpp:282
uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type.
uint256_t.hpp contains a class for 256-bit unsigned integers.