SDSL 3.0.1
Succinct Data Structure Library
|
A struct for the binomial coefficients .
More...
#include <rrr_helper.hpp>
Classes | |
struct | impl |
Public Types | |
enum | { MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6)) } |
typedef binomial_coefficients_trait< MAX_LOG > | trait |
typedef trait::number_type | number_type |
typedef binomial_table< MAX_SIZE, number_type > | tBinom |
Static Public Attributes | |
static const uint16_t | MAX_SIZE = (1 << MAX_LOG) |
static struct sdsl::binomial_coefficients::impl | data |
A struct for the binomial coefficients .
data.table[m][k] contains the number for
. Size of data.table : Let
and
then the tables requires
bytes space. Examples: n <= 64: 64*64*8 bytes = 4 kB * 8 = 32 kB 64 < n <= 128: 128*128*16 bytes = 16 kB * 16 = 256 kB 128 < n <= 256: 256*256*32 bytes = 64 kB * 32 = 2048 kB = 2 MB The table is shared now for all n's in on of these ranges.
data.space[k] returns the bits needed to encode a value between [0..data.table[n][k]], given n and k. Size of data.space is bytes. E.g. 64*8=512 bytes for n=63, 2kB for n=127, and 8kB for n=255.
BINARY_SEARCH_THRESHOLD is equal to
Definition at line 229 of file rrr_helper.hpp.
typedef trait::number_type sdsl::binomial_coefficients< n >::number_type |
Definition at line 237 of file rrr_helper.hpp.
typedef binomial_table<MAX_SIZE, number_type> sdsl::binomial_coefficients< n >::tBinom |
Definition at line 238 of file rrr_helper.hpp.
typedef binomial_coefficients_trait<MAX_LOG> sdsl::binomial_coefficients< n >::trait |
Definition at line 236 of file rrr_helper.hpp.
anonymous enum |
Enumerator | |
---|---|
MAX_LOG |
Definition at line 231 of file rrr_helper.hpp.
|
static |
Definition at line 265 of file rrr_helper.hpp.
|
static |
Definition at line 235 of file rrr_helper.hpp.