10#define SDSL_RRR_HELPER
30template <u
int16_t log_n>
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)
49 return bv.get_int(pos, len);
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)
62 bv.set_int(pos, x, len);
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)
97 return bv.get_int(pos, len);
101 return ((((
number_type)bv.get_int(pos + 64, len - 64)) << 64) + bv.get_int(pos, 64));
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)
110 bv.set_int(pos, x, len);
114 bv.set_int(pos, (uint64_t)x, 64);
115 bv.set_int(pos + 64, x >> 64, len - 64);
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)
144 return number_type(bv.get_int(pos, 64), bv.get_int(pos + 64, len - 64));
149 bv.get_int(pos + 64, 64),
150 (
uint128_t)bv.get_int(pos + 128, len - 128));
155 bv.get_int(pos + 64, 64),
156 (((
uint128_t)bv.get_int(pos + 192, len - 192)) << 64) | bv.get_int(pos + 128, 64));
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)
165 bv.set_int(pos, x, len);
169 bv.set_int(pos, x, 64);
170 bv.set_int(pos + 64, x >> 64, len - 64);
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);
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);
193template <u
int16_t n,
class number_type>
198 number_type table[n + 1][n + 1];
199 number_type L1Mask[n + 1];
201 number_type O1Mask[n];
205 for (uint16_t k = 0; k <= n; ++k)
209 for (uint16_t k = 0; k <= n; ++k)
213 for (uint16_t nn = 0; nn <= n; ++nn)
217 for (
int nn = 1; nn <= n; ++nn)
219 for (
int k = 1; k <= n; ++k)
221 table[nn][k] = table[nn - 1][k - 1] + table[nn - 1][k];
225 number_type mask = 1;
227 for (
int i = 1; i <= n; ++i)
231 O1Mask[i] = O1Mask[i - 1] << 1;
233 mask |= (number_type)1;
239template <u
int16_t n,
class number_type>
266 MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6))
277 uint16_t space[n + 1];
279 static const uint16_t BINARY_SEARCH_THRESHOLD = n /
MAX_LOG;
281 static const uint16_t BINARY_SEARCH_THRESHOLD = 0;
289 for (
int k = 0; k <= n; ++k)
325 template <
class bit_vector_type>
327 decode_btnr(bit_vector_type
const & bv,
typename bit_vector_type::size_type btnrp, uint16_t btnrlen)
332 template <
class bit_vector_type>
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)
382 return (n - nr - 1) == off;
393 while (nn_lb < nn_rb)
395 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
408 return (n - nn) == off;
435 return (n - nr - 1) == off;
454 return 1ULL << ((n - nr - 1) - off);
465 if (i > off + len - 1)
474 res |= 1ULL << (i - off);
481 res |= 1ULL << ((n - nr - 1) - off);
500 return (n - nr - 1) < off;
512 while (nn_lb < nn_rb)
514 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
554 return result + ((n - nr - 1) < off);
566 else if (k == 1 and sel == 1)
577 uint16_t nn_lb = k, nn_rb = nn + 1;
578 while (nn_lb < nn_rb)
580 uint16_t nn_mid = (nn_lb + nn_rb) / 2;
618 template <u
int8_t pattern, u
int8_t len>
622 uint8_t decoded_pattern = 0;
623 uint8_t decoded_len = 0;
627 decoded_pattern = decoded_pattern << 1;
633 decoded_pattern |= 1;
638 if (decoded_len == len)
640 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 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 .
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 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)
binomial::trait trait
The number trait.
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.