SparseEntries Class Reference

the entries of a pattern table whose excess is nonzero, by rank More...

#include <PBeFS/astar/PatternDatabase.h>

Public Member Functions
int	value (std::uint64_t r, int m) const
	the value of the rank r, whose placement has Manhattan distance m
std::uint64_t	entries (void) const noexcept
	the number of the entries
std::uint64_t	nonzero (void) const noexcept
	the entries whose excess is nonzero
std::size_t	bytes (void) const noexcept
	the bytes of B, of its directory and of the excesses
std::vector< std::uint8_t >	payload (void) const
	the bytes written in a file

Static Public Member Functions
template<class M>
static SparseEntries	encode (const std::vector< std::uint8_t > &h, M &&m, unsigned=1)
	the encoding of the distances h, m( r ) the Manhattan distance of r
static SparseEntries	decode (std::vector< std::uint8_t > data, std::uint64_t n, unsigned=1)
	the encoding of n entries read from a file: the words of B, then the excesses

Static Public Attributes
static constexpr std::uint32_t	code = 5
	the code in a file
static constexpr const char *	name = "sparse"
	the name
static constexpr bool	relative = false
	absolute values

Detailed Description

the entries of a pattern table whose excess is nonzero, by rank

A vector of bits B tells which entries have a nonzero excess over the Manhattan distance [see NibbleEntries], and these excesses are stored in 4 bits each, in the order of their ranks, saturated at 15. The excess of the rank r is 0 if \( B[ r ] = 0 \), and otherwise the excess number \( rank_1( r ) \) of the list, on the RankSelect of ADS. It takes \( n ( 1 + \rho ) + 4 z \) bits for n entries, z of them nonzero, the directory of rank and select taking \( \rho n \) bits (about 0.4 n), and hence it is smaller than NibbleEntries when fewer than about 64% of the entries are nonzero, at the price of a rank per lookup.

Member Function Documentation

bytes()

std::size_t bytes ( void ) const

inlinenodiscardnoexcept

the bytes of B, of its directory and of the excesses

decode()

SparseEntries decode ( std::vector< std::uint8_t > data, std::uint64_t n, unsigned = 1 )

inlinestaticnodiscard

the encoding of n entries read from a file: the words of B, then the excesses

encode()

template<class M>

SparseEntries encode ( const std::vector< std::uint8_t > & h, M && m, unsigned = 1 )

inlinestaticnodiscard

the encoding of the distances h, m( r ) the Manhattan distance of r

entries()

std::uint64_t entries ( void ) const

inlinenodiscardnoexcept

the number of the entries

nonzero()

std::uint64_t nonzero ( void ) const

inlinenodiscardnoexcept

the entries whose excess is nonzero

payload()

std::vector< std::uint8_t > payload ( void ) const

inlinenodiscard

the bytes written in a file

value()

int value ( std::uint64_t r, int m ) const

inlinenodiscard

the value of the rank r, whose placement has Manhattan distance m

Member Data Documentation

code

std::uint32_t code = 5

staticconstexpr

the code in a file

name

const char* name = "sparse"

staticconstexpr

the name

relative

bool relative = false

staticconstexpr

absolute values

---

The documentation for this class was generated from the following file:

• PBeFS/astar/PatternDatabase.h