SDSL 3.0.1
Succinct Data Structure Library
Loading...
Searching...
No Matches
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
25namespace sdsl
26{
27
29
31template <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
71template <>
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
109template <>
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
164template <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
206template <uint16_t n, class number_type>
208
210
228template <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);
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
264template <uint16_t n>
266
268
279template <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
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
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
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
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.