SDSL 3.0.3
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 <stdint.h>
19
20#include <sdsl/bits.hpp>
21#include <sdsl/uint128_t.hpp>
22#include <sdsl/uint256_t.hpp>
23
24namespace sdsl
25{
26
28
30template <uint16_t log_n>
32{
33 typedef uint64_t number_type;
34 static inline uint16_t hi(number_type x)
35 {
36 return bits::hi(x);
37 }
38
40
46 template <class bit_vector_type>
47 static inline number_type get_int(bit_vector_type const & bv, typename bit_vector_type::size_type pos, uint16_t len)
48 {
49 return bv.get_int(pos, len);
50 }
51
53
59 template <class bit_vector_type>
60 static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
61 {
62 bv.set_int(pos, x, len);
63 }
64
66
69 static inline uint16_t popcount(number_type x)
70 {
71 return bits::cnt(x);
72 }
73};
74
76template <>
78{
80 static inline uint16_t hi(number_type x)
81 {
82 if ((x >> 64))
83 {
84 return bits::hi(x >> 64) + 64;
85 }
86 else
87 {
88 return bits::hi(x);
89 }
90 }
91
92 template <class bit_vector_type>
93 static inline number_type get_int(bit_vector_type const & bv, typename bit_vector_type::size_type pos, uint16_t len)
94 {
95 if (len <= 64)
96 {
97 return bv.get_int(pos, len);
98 }
99 else
100 {
101 return ((((number_type)bv.get_int(pos + 64, len - 64)) << 64) + bv.get_int(pos, 64));
102 }
103 }
104
105 template <class bit_vector_type>
106 static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
107 {
108 if (len <= 64)
109 {
110 bv.set_int(pos, x, len);
111 }
112 else
113 {
114 bv.set_int(pos, (uint64_t)x, 64);
115 bv.set_int(pos + 64, x >> 64, len - 64);
116 }
117 }
118
119 static inline uint16_t popcount(number_type x)
120 {
121 return bits::cnt(x >> 64) + bits::cnt(x);
122 }
123};
124
126template <>
128{
130 static inline uint16_t hi(number_type x)
131 {
132 return x.hi();
133 }
134
135 template <class bit_vector_type>
136 static inline number_type get_int(bit_vector_type const & bv, typename bit_vector_type::size_type pos, uint16_t len)
137 {
138 if (len <= 64)
139 {
140 return number_type(bv.get_int(pos, len));
141 }
142 else if (len <= 128)
143 {
144 return number_type(bv.get_int(pos, 64), bv.get_int(pos + 64, len - 64));
145 }
146 else if (len <= 192)
147 {
148 return number_type(bv.get_int(pos, 64),
149 bv.get_int(pos + 64, 64),
150 (uint128_t)bv.get_int(pos + 128, len - 128));
151 }
152 else
153 { // > 192
154 return number_type(bv.get_int(pos, 64),
155 bv.get_int(pos + 64, 64),
156 (((uint128_t)bv.get_int(pos + 192, len - 192)) << 64) | bv.get_int(pos + 128, 64));
157 }
158 }
159
160 template <class bit_vector_type>
161 static void set_int(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
162 {
163 if (len <= 64)
164 {
165 bv.set_int(pos, x, len);
166 }
167 else if (len <= 128)
168 {
169 bv.set_int(pos, x, 64);
170 bv.set_int(pos + 64, x >> 64, len - 64);
171 }
172 else if (len <= 192)
173 {
174 bv.set_int(pos, x, 64);
175 bv.set_int(pos + 64, x >> 64, 64);
176 bv.set_int(pos + 128, x >> 128, len - 128);
177 }
178 else
179 { // > 192
180 bv.set_int(pos, x, 64);
181 bv.set_int(pos + 64, x >> 64, 64);
182 bv.set_int(pos + 128, x >> 128, 64);
183 bv.set_int(pos + 192, x >> 192, len - 192);
184 }
185 }
186
187 static inline uint16_t popcount(number_type x)
188 {
189 return x.popcount();
190 }
191};
192
193template <uint16_t n, class number_type>
195{
196 static struct impl
197 {
198 number_type table[n + 1][n + 1];
199 number_type L1Mask[n + 1]; // L1Mask[i] contains a word with the i least significant bits set to 1.
200 // i.e. L1Mask[0] = 0, L1Mask[1] = 1,...
201 number_type O1Mask[n]; // O1Mask[i] contains a word with the i least significant bits set to 0.
202
203 impl()
204 {
205 for (uint16_t k = 0; k <= n; ++k)
206 {
207 table[k][k] = 1; // initialize diagonal
208 }
209 for (uint16_t k = 0; k <= n; ++k)
210 {
211 table[0][k] = 0; // initialize first row
212 }
213 for (uint16_t nn = 0; nn <= n; ++nn)
214 {
215 table[nn][0] = 1; // initialize first column
216 }
217 for (int nn = 1; nn <= n; ++nn)
218 {
219 for (int k = 1; k <= n; ++k)
220 {
221 table[nn][k] = table[nn - 1][k - 1] + table[nn - 1][k];
222 }
223 }
224 L1Mask[0] = 0;
225 number_type mask = 1;
226 O1Mask[0] = 1;
227 for (int i = 1; i <= n; ++i)
228 {
229 L1Mask[i] = mask;
230 if (i < n)
231 O1Mask[i] = O1Mask[i - 1] << 1;
232 mask = (mask << 1);
233 mask |= (number_type)1;
234 }
235 }
236 } data;
237};
238
239template <uint16_t n, class number_type>
240typename binomial_table<n, number_type>::impl binomial_table<n, number_type>::data;
241
243
261template <uint16_t n>
263{
264 enum
265 {
266 MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6))
267 };
268 static const uint16_t MAX_SIZE = (1 << MAX_LOG);
272
273 static struct impl
274 {
275 const number_type (&table)[MAX_SIZE + 1][MAX_SIZE + 1] =
276 tBinom::data.table; // table for the binomial coefficients
277 uint16_t space[n + 1]; // for entry i,j \lceil \log( {i \choose j}+1 ) \rceil
278#ifndef RRR_NO_BS
279 static const uint16_t BINARY_SEARCH_THRESHOLD = n / MAX_LOG;
280#else
281 static const uint16_t BINARY_SEARCH_THRESHOLD = 0;
282#endif
283 number_type (&L1Mask)[MAX_SIZE + 1] = tBinom::data.L1Mask;
284 number_type (&O1Mask)[MAX_SIZE] = tBinom::data.O1Mask;
285
286 impl()
287 {
288 static typename binomial_table<n, number_type>::impl tmp_data;
289 for (int k = 0; k <= n; ++k)
290 {
291 space[k] = (tmp_data.table[n][k] == (number_type)1) ? 0 : trait::hi(tmp_data.table[n][k]) + 1;
292 }
293 }
294 } data;
295};
296
297template <uint16_t n>
298typename binomial_coefficients<n>::impl binomial_coefficients<n>::data;
299
301
312template <uint16_t n>
314{
317 typedef typename binomial::trait trait;
318
320 static inline uint16_t space_for_bt(uint16_t i)
321 {
322 return binomial::data.space[i];
323 }
324
325 template <class bit_vector_type>
326 static inline number_type
327 decode_btnr(bit_vector_type const & bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
328 {
329 return trait::get_int(bv, btnrp, btnrlen);
330 }
331
332 template <class bit_vector_type>
333 static void
334 set_bt(bit_vector_type & bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
335 {
336 trait::set_int(bv, pos, bt, space_for_bt);
337 }
338
339 template <class bit_vector_type>
340 static inline uint16_t
341 get_bt(bit_vector_type const & bv, typename bit_vector_type::size_type pos, uint16_t block_size)
342 {
343 return trait::popcount(trait::get_int(bv, pos, block_size));
344 }
345
347 {
348 if (bin == (number_type)0 or bin == binomial::data.L1Mask[n])
349 { // handle special case
350 return 0;
351 }
352 number_type nr = 0;
353 uint16_t k = trait::popcount(bin);
354 uint16_t nn = n; // size of the block
355 while (bin != (number_type)0)
356 {
357 if (1ULL & bin)
358 {
359 nr += binomial::data.table[nn - 1][k];
360 --k; // go to the case (n-1, k-1)
361 } // else go to the case (n-1, k)
362 bin = (bin >> 1);
363 --nn;
364 }
365 return nr;
366 }
367
369 static inline bool decode_bit(uint16_t k, number_type nr, uint16_t off)
370 {
371#ifndef RRR_NO_OPT
372 if (k == n)
373 { // if n==k, then the encoded block consists only of ones
374 return 1;
375 }
376 else if (k == 0)
377 { // if k==0 then the encoded block consists only of zeros
378 return 0;
379 }
380 else if (k == 1)
381 { // if k==1 then the encoded block contains exactly on set bit at
382 return (n - nr - 1) == off; // position n-nr-1
383 }
384#endif
385 uint16_t nn = n;
386 // if k < n \log n, it is better to do a binary search for each of the on bits
387 if (k + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
388 {
389 while (k > 1)
390 {
391 uint16_t nn_lb = k,
392 nn_rb = nn + 1; // invariant nr >= binomial::data.table[nn_lb-1][k]
393 while (nn_lb < nn_rb)
394 {
395 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
396 if (nr >= binomial::data.table[nn_mid - 1][k])
397 {
398 nn_lb = nn_mid + 1;
399 }
400 else
401 {
402 nn_rb = nn_mid;
403 }
404 }
405 nn = nn_lb - 1;
406 if (n - nn >= off)
407 {
408 return (n - nn) == off;
409 }
410 nr -= binomial::data.table[nn - 1][k];
411 --k;
412 --nn;
413 }
414 }
415 else
416 { // else do a linear decoding
417 int i = 0;
418 while (k > 1)
419 {
420 if (i > off)
421 {
422 return 0;
423 }
424 if (nr >= binomial::data.table[nn - 1][k])
425 {
426 nr -= binomial::data.table[nn - 1][k];
427 --k;
428 if (i == off)
429 return 1;
430 }
431 --nn;
432 ++i;
433 }
434 }
435 return (n - nr - 1) == off;
436 }
437
439 static inline uint64_t decode_int(uint16_t k, number_type nr, uint16_t off, uint16_t len)
440 {
441#ifndef RRR_NO_OPT
442 if (k == n)
443 { // if n==k, then the encoded block consists only of ones
444 return bits::lo_set[len];
445 }
446 else if (k == 0)
447 { // if k==0 then the encoded block consists only of zeros
448 return 0;
449 }
450 else if (k == 1)
451 { // if k==1 then the encoded block contains exactly on set bit at
452 if (n - nr - 1 >= (number_type)off and n - nr - 1 <= (number_type)(off + len - 1))
453 {
454 return 1ULL << ((n - nr - 1) - off);
455 }
456 else
457 return 0;
458 }
459#endif
460 uint64_t res = 0;
461 uint16_t nn = n;
462 int i = 0;
463 while (k > 1)
464 {
465 if (i > off + len - 1)
466 {
467 return res;
468 }
469 if (nr >= binomial::data.table[nn - 1][k])
470 {
471 nr -= binomial::data.table[nn - 1][k];
472 --k;
473 if (i >= off)
474 res |= 1ULL << (i - off);
475 }
476 --nn;
477 ++i;
478 }
479 if (n - nr - 1 >= (number_type)off and n - nr - 1 <= (number_type)(off + len - 1))
480 {
481 res |= 1ULL << ((n - nr - 1) - off);
482 }
483 return res;
484 }
485
487 static inline uint16_t decode_popcount(uint16_t k, number_type nr, uint16_t off)
488 {
489#ifndef RRR_NO_OPT
490 if (k == n)
491 { // if n==k, then the encoded block consists only of ones
492 return off; // i.e. the answer is off
493 }
494 else if (k == 0)
495 { // if k==0, then the encoded block consists only on zeros
496 return 0; // i.e. the result is zero
497 }
498 else if (k == 1)
499 { // if k==1 then the encoded block contains exactly on set bit at
500 return (n - nr - 1) < off; // position n-nr-1, and popcount is 1 if off > (n-nr-1).
501 }
502#endif
503 uint16_t result = 0;
504 uint16_t nn = n;
505 // if k < n \log n, it is better to do a binary search for each of the on bits
506 if (k + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
507 {
508 while (k > 1)
509 {
510 uint16_t nn_lb = k,
511 nn_rb = nn + 1; // invariant nr >= binomial::data.table[nn_lb-1][k]
512 while (nn_lb < nn_rb)
513 {
514 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
515 if (nr >= binomial::data.table[nn_mid - 1][k])
516 {
517 nn_lb = nn_mid + 1;
518 }
519 else
520 {
521 nn_rb = nn_mid;
522 }
523 }
524 nn = nn_lb - 1;
525 if (n - nn >= off)
526 {
527 return result;
528 }
529 ++result;
530 nr -= binomial::data.table[nn - 1][k];
531 --k;
532 --nn;
533 }
534 }
535 else
536 {
537 int i = 0;
538 while (k > 1)
539 {
540 if (i >= off)
541 {
542 return result;
543 }
544 if (nr >= binomial::data.table[nn - 1][k])
545 {
546 nr -= binomial::data.table[nn - 1][k];
547 --k;
548 ++result;
549 }
550 --nn;
551 ++i;
552 }
553 }
554 return result + ((n - nr - 1) < off);
555 }
556
559 static inline uint16_t decode_select(uint16_t k, number_type & nr, uint16_t sel)
560 {
561#ifndef RRR_NO_OPT
562 if (k == n)
563 { // if n==k, then the encoded block consists only of ones
564 return sel - 1;
565 }
566 else if (k == 1 and sel == 1)
567 {
568 return n - nr - 1;
569 }
570#endif
571 uint16_t nn = n;
572 // if k < n \log n, it is better to do a binary search for each of the on bits
573 if (sel + 1 < binomial::data.BINARY_SEARCH_THRESHOLD + 1)
574 {
575 while (sel > 0)
576 {
577 uint16_t nn_lb = k, nn_rb = nn + 1; // invariant nr >= iii.m_coefficients[nn_lb-1]
578 while (nn_lb < nn_rb)
579 {
580 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
581 if (nr >= binomial::data.table[nn_mid - 1][k])
582 {
583 nn_lb = nn_mid + 1;
584 }
585 else
586 {
587 nn_rb = nn_mid;
588 }
589 }
590 nn = nn_lb - 1;
591 nr -= binomial::data.table[nn - 1][k];
592 --sel;
593 --nn;
594 --k;
595 }
596 return n - nn - 1;
597 }
598 else
599 {
600 int i = 0;
601 while (sel > 0)
602 { // TODO: this condition only work if the precondition holds
603 if (nr >= binomial::data.table[nn - 1][k])
604 {
605 nr -= binomial::data.table[nn - 1][k];
606 --sel;
607 --k;
608 }
609 --nn;
610 ++i;
611 }
612 return i - 1;
613 }
614 }
615
618 template <uint8_t pattern, uint8_t len>
619 static inline uint16_t decode_select_bitpattern(uint16_t k, number_type & nr, uint16_t sel)
620 {
621 int i = 0;
622 uint8_t decoded_pattern = 0;
623 uint8_t decoded_len = 0;
624 uint16_t nn = n;
625 while (sel > 0)
626 { // TODO: this condition only work if the precondition holds
627 decoded_pattern = decoded_pattern << 1;
628 ++decoded_len;
629 if (nr >= binomial::data.table[nn - 1][k])
630 {
631 nr -= binomial::data.table[nn - 1][k];
632 // a one is decoded
633 decoded_pattern |= 1; // add to the pattern
634 --k;
635 }
636 --nn;
637 ++i;
638 if (decoded_len == len)
639 { // if decoded pattern length equals len of the searched pattern
640 if (decoded_pattern == pattern)
641 { // and pattern equals the searched pattern
642 --sel;
643 }
644 decoded_pattern = 0;
645 decoded_len = 0; // reset pattern
646 }
647 }
648 return i - len; // return the starting position of $sel$th occurence of the pattern
649 }
650};
651
652} // namespace sdsl
653#endif
bits.hpp contains the sdsl::bits class.
uint16_t popcount()
Definition uint256_t.hpp:57
uint16_t hi()
Definition uint256_t.hpp:63
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)
static number_type get_int(bit_vector_type const &bv, typename bit_vector_type::size_type pos, uint16_t len)
static uint16_t popcount(number_type x)
static uint16_t hi(number_type x)
static number_type get_int(bit_vector_type const &bv, typename bit_vector_type::size_type pos, uint16_t len)
static uint16_t popcount(number_type x)
static void set_int(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type x, uint16_t len)
static uint16_t hi(number_type x)
Trait struct for the binomial coefficient struct to handle different type of integers.
static uint16_t popcount(number_type x)
Count the number of set bits in x.
static uint16_t hi(number_type x)
static number_type get_int(bit_vector_type const &bv, typename bit_vector_type::size_type pos, uint16_t len)
Read a -bit integer of type number_type from a bitvector.
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.
A struct for the binomial coefficients .
static const uint16_t MAX_SIZE
trait::number_type number_type
static struct sdsl::binomial_coefficients::impl data
binomial_table< MAX_SIZE, number_type > tBinom
binomial_coefficients_trait< MAX_LOG > trait
static struct sdsl::binomial_table::impl data
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition bits.hpp:486
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:194
Class to encode and decode binomial coefficients on the fly.
binomial_coefficients< n > binomial
The struct containing the binomial coefficients.
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
binomial::number_type number_type
The used number type, e.g.
static uint16_t space_for_bt(uint16_t i)
Returns the space usage in bits of the binary representation of the number .
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,...
static number_type bin_to_nr(number_type bin)
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
static number_type decode_btnr(bit_vector_type const &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
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).
static uint16_t decode_select_bitpattern(uint16_t k, number_type &nr, uint16_t sel)
static uint16_t get_bt(bit_vector_type const &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
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.
binomial::trait trait
The number trait.
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.