10#define SDSL_RRR_HELPER
31template <u
int16_t log_n>
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)
47 return bv.get_int(pos, len);
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)
60 bv.set_int(pos, x, len);
77 if ((x >> 64)) {
return bits::hi(x >> 64) + 64; }
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)
87 if (len <= 64) {
return bv.get_int(pos, len); }
90 return ((((
number_type)bv.get_int(pos + 64, len - 64)) << 64) + bv.get_int(pos, 64));
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)
97 if (len <= 64) { bv.set_int(pos, x, len); }
100 bv.set_int(pos, (uint64_t)x, 64);
101 bv.set_int(pos + 64, x >> 64, len - 64);
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)
118 if (len <= 64) {
return number_type(bv.get_int(pos, len)); }
121 return number_type(bv.get_int(pos, 64), bv.get_int(pos + 64, len - 64));
126 bv.get_int(pos + 64, 64),
127 (
uint128_t)bv.get_int(pos + 128, len - 128));
132 bv.get_int(pos + 64, 64),
133 (((
uint128_t)bv.get_int(pos + 192, len - 192)) << 64) | bv.get_int(pos + 128, 64));
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)
140 if (len <= 64) { bv.set_int(pos, x, len); }
143 bv.set_int(pos, x, 64);
144 bv.set_int(pos + 64, x >> 64, len - 64);
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);
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);
164template <u
int16_t n,
class number_type>
169 number_type table[n + 1][n + 1];
170 number_type L1Mask[n + 1];
172 number_type O1Mask[n];
176 for (uint16_t k = 0; k <= n; ++k)
180 for (uint16_t k = 0; k <= n; ++k)
184 for (uint16_t nn = 0; nn <= n; ++nn)
188 for (
int nn = 1; nn <= n; ++nn)
190 for (
int k = 1; k <= n; ++k) { table[nn][k] = table[nn - 1][k - 1] + table[nn - 1][k]; }
193 number_type mask = 1;
195 for (
int i = 1; i <= n; ++i)
198 if (i < n) O1Mask[i] = O1Mask[i - 1] << 1;
200 mask |= (number_type)1;
206template <u
int16_t n,
class number_type>
233 MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6))
244 uint16_t space[n + 1];
246 static const uint16_t BINARY_SEARCH_THRESHOLD = n /
MAX_LOG;
248 static const uint16_t BINARY_SEARCH_THRESHOLD = 0;
256 for (
int k = 0; k <= n; ++k)
289 template <
class bit_vector_type>
291 typename bit_vector_type::size_type btnrp,
297 template <
class bit_vector_type>
299 typename bit_vector_type::size_type pos,
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,
350 return (n - nr - 1) == off;
361 while (nn_lb < nn_rb)
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; }
371 if (n - nn >= off) {
return (n - nn) == off; }
382 if (i > off) {
return 0; }
387 if (i == off)
return 1;
393 return (n - nr - 1) == off;
412 return 1ULL << ((n - nr - 1) - off);
423 if (i > off + len - 1) {
return res; }
428 if (i >= off) res |= 1ULL << (i - off);
435 res |= 1ULL << ((n - nr - 1) - off);
454 return (n - nr - 1) < off;
466 while (nn_lb < nn_rb)
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; }
476 if (n - nn >= off) {
return result; }
488 if (i >= off) {
return result; }
499 return result + ((n - nr - 1) < off);
511 else if (k == 1 and sel == 1)
522 uint16_t nn_lb = k, nn_rb = nn + 1;
523 while (nn_lb < nn_rb)
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; }
560 template <u
int8_t pattern, u
int8_t len>
564 uint8_t decoded_pattern = 0;
565 uint8_t decoded_len = 0;
569 decoded_pattern = decoded_pattern << 1;
575 decoded_pattern |= 1;
580 if (decoded_len == len)
582 if (decoded_pattern == pattern)
bits.hpp contains the sdsl::bits class.
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 uint16_t popcount(number_type x)
static uint16_t hi(number_type x)
static number_type get_int(const bit_vector_type &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)
static number_type get_int(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t len)
Trait struct for the binomial coefficient struct to handle different type of integers.
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.
static uint16_t popcount(number_type x)
Count the number of set bits in x.
static uint16_t hi(number_type x)
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 .
trait::number_type number_type
static const uint16_t MAX_SIZE
binomial_table< MAX_SIZE, number_type > tBinom
static struct sdsl::binomial_coefficients::impl data
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.
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
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.
Class to encode and decode binomial coefficients on the fly.
static void set_bt(bit_vector_type &bv, typename bit_vector_type::size_type pos, number_type bt, uint16_t space_for_bt)
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,...
binomial::number_type number_type
The used number type, e.g.
static number_type bin_to_nr(number_type bin)
static uint16_t decode_select(uint16_t k, number_type &nr, uint16_t sel)
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)
binomial::trait trait
The number trait.
static uint16_t get_bt(const bit_vector_type &bv, typename bit_vector_type::size_type pos, uint16_t block_size)
static number_type decode_btnr(const bit_vector_type &bv, typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
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_coefficients< n > binomial
The struct containing the binomial coefficients.
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.