SparseEntries
Declared in astar/PatternDatabase.h; the same class on the site of Doxygen.
-
class SparseEntries
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.
Public Functions
-
inline int value(std::uint64_t r, int m) const
the value of the rank r, whose placement has Manhattan distance m
-
inline std::uint64_t entries(void) const noexcept
the number of the entries
-
inline std::uint64_t nonzero(void) const noexcept
the entries whose excess is nonzero
-
inline std::size_t bytes(void) const noexcept
the bytes of B, of its directory and of the excesses
-
inline std::vector<std::uint8_t> payload(void) const
the bytes written in a file
Public Static Functions
-
template<class M>
static inline 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 inline 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
-
inline int value(std::uint64_t r, int m) const