PatternTable

Declared in astar/PatternDatabase.h; the same class on the site of Doxygen.

template<int W, int H, class Enc = NibbleEntries>
class PatternTable

the distances of a pattern of the sliding-tile puzzle, encoded by Enc

The table maps the rank of a placement of the tiles of the pattern to its distance from the goal placement in the abstraction given by the rule of the blank [see BlankRule], encoded by Enc (ByteEntries, NibbleEntries, Mod3Entries, ParityBitEntries, MinNibbleEntries or SparseEntries). It is built by build(), read from a file by load(), and taken from a cache directory, or built and saved there, by cached().

Public Types

using Pattern = TilePattern<W, H>

the pattern

using board_type = typename Pattern::board_type

a board

Public Functions

inline PatternTable(const Pattern &p, BlankRule rule, unsigned compress, Enc entries, bool from_file = false)

constructor, taking the pattern, its rule, the parameter of Enc and the entries already encoded

inline int value(const std::uint8_t *q) const noexcept

the value of the placement q, q[ i ] the cell of the i-th tile

inline int manhattan(const std::uint8_t *q) const noexcept

the Manhattan distance of the tiles of the placement q, by a table

inline int residue(const std::uint8_t *q) const noexcept

the residue of the value of the placement q, modulo Enc::modulus

inline int exact(const std::uint8_t *q) const

the value of the placement q from the residues alone

Walks from q to the goal placement, each step to a neighbour whose residue is one less modulo 3, which has a value one less (EXACT of the file header); the number of steps is the value. With the blank ignored, the abstraction is an undirected graph with unit costs, and hence such a neighbour exists until the goal is reached.

inline const Pattern &pattern(void) const noexcept

the pattern

inline BlankRule rule(void) const noexcept

the rule of the blank

inline const Enc &entries(void) const noexcept

the encoded entries

inline std::size_t bytes(void) const noexcept

the bytes of the entries

inline bool from_file(void) const noexcept

true if the table was read from a file

inline void save(const std::string &path) const

writes the table to the file path

The file holds, in little-endian order, the magic “PBeFSPDB”, the version of the format, W, H, the rule of the blank, the code of the encoding and its parameter, the number k of the tiles and the tiles, the goal board, the number of the entries, the length of the payload and the payload, and at the end a checksum of all that precedes it. It is written to a temporary file in the same directory, then renamed, so that a reader never sees it half written.

Public Static Functions

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>
static inline std::vector<std::uint8_t> distances(

const Pattern &p,

BlankRule rule,

unsigned threads = 0

)

the exact distances of the placements of p, one byte each

Runs the breadth-first search of BUILD-IGNORED or BUILD-MINIMIZED [see the file header] on threads workers of Executor (all the cores if 0).

static inline PatternTable encode(

const Pattern &p,

BlankRule rule,

const std::vector<std::uint8_t> &h,

unsigned compress = 1

)

the table of p, from the exact distances h

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>
static inline PatternTable build(

const Pattern &p,

BlankRule rule,

unsigned compress = 1,

unsigned threads = 0

)

the table of p, built on threads workers of Executor

static inline PatternTable load(

const std::string &path,

const Pattern &p,

BlankRule rule,

unsigned compress = 1

)

reads the table of p from the file path

Throws std::runtime_error if the file cannot be read, if its magic, version, checksum or lengths are wrong, or if it holds the table of another pattern, goal, rule or encoding.

static inline std::string file_name(const Pattern &p, BlankRule rule, unsigned compress = 1)

the name of the file of the table of p in a cache directory

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>
static inline PatternTable cached(

const std::string &dir,

const Pattern &p,

BlankRule rule,

unsigned compress = 1,

unsigned threads = 0

)

the table of p from the cache directory dir, or built and saved there

Looks for the file of the table in dir; if it is not there, or it cannot be loaded, looks for the table of the same pattern in bytes (ByteEntries) and encodes it, else builds it by build() on threads workers of Executor; the tables built or encoded are saved in dir, which is created if needed.

static inline std::uint64_t checksum(const std::uint8_t *b, std::size_t n) noexcept

the checksum of the n bytes at b, by words of 8 bytes

Public Static Attributes

static constexpr int cells = W * H

the cells

static constexpr std::uint32_t file_version = 1

the version of the format of the files