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

#include <PBeFS/astar/PatternDatabase.h>

Public Types
using	Pattern = TilePattern< W , H >
	the pattern
using	board_type = typename Pattern::board_type
	a board

Public Member Functions
	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
int	value (const std::uint8_t *q) const noexcept
	the value of the placement q, q[ i ] the cell of the i-th tile
int	manhattan (const std::uint8_t *q) const noexcept
	the Manhattan distance of the tiles of the placement q, by a table
int	residue (const std::uint8_t *q) const noexcept
	the residue of the value of the placement q, modulo Enc::modulus
int	exact (const std::uint8_t *q) const
	the value of the placement q from the residues alone
const Pattern &	pattern (void) const noexcept
	the pattern
BlankRule	rule (void) const noexcept
	the rule of the blank
const Enc &	entries (void) const noexcept
	the encoded entries
std::size_t	bytes (void) const noexcept
	the bytes of the entries
bool	from_file (void) const noexcept
	true if the table was read from a file
void	save (const std::string &path) const
	writes the table to the file path

Static Public Member Functions
template<ADS::WorkerExecutor Executor = ADS::ThreadPool>
static 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
static 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 PatternTable	build (const Pattern &p, BlankRule rule, unsigned compress=1, unsigned threads=0)
	the table of p, built on threads workers of Executor
static PatternTable	load (const std::string &path, const Pattern &p, BlankRule rule, unsigned compress=1)
	reads the table of p from the file path
static 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 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
static 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

Static Public 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

Detailed Description

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

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().

Member Typedef Documentation

◆ board_type

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

using board_type = typename Pattern::board_type

a board

◆ Pattern

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

using Pattern = TilePattern< W , H >

the pattern

Constructor & Destructor Documentation

◆ PatternTable()

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

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

inline

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

Member Function Documentation

◆ build()

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

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>

PatternTable build	(	const Pattern &	p,
		BlankRule	rule,
		unsigned	compress = 1,
		unsigned	threads = 0 )

inlinestaticnodiscard

the table of p, built on threads workers of Executor

◆ bytes()

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

std::size_t bytes ( void ) const

inlinenodiscardnoexcept

the bytes of the entries

◆ cached()

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

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>

PatternTable cached	(	const std::string &	dir,
		const Pattern &	p,
		BlankRule	rule,
		unsigned	compress = 1,
		unsigned	threads = 0 )

inlinestaticnodiscard

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.

◆ checksum()

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

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

inlinestaticnodiscardnoexcept

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

◆ distances()

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

template<ADS::WorkerExecutor Executor = ADS::ThreadPool>

std::vector< std::uint8_t > distances	(	const Pattern &	p,
		BlankRule	rule,
		unsigned	threads = 0 )

inlinestaticnodiscard

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).

◆ encode()

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

PatternTable encode	(	const Pattern &	p,
		BlankRule	rule,
		const std::vector< std::uint8_t > &	h,
		unsigned	compress = 1 )

inlinestaticnodiscard

the table of p, from the exact distances h

◆ entries()

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

const Enc & entries ( void ) const

inlinenodiscardnoexcept

the encoded entries

◆ exact()

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

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

inlinenodiscard

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.

◆ file_name()

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

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

inlinestaticnodiscard

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

◆ from_file()

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

bool from_file ( void ) const

inlinenodiscardnoexcept

true if the table was read from a file

◆ load()

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

PatternTable load	(	const std::string &	path,
		const Pattern &	p,
		BlankRule	rule,
		unsigned	compress = 1 )

inlinestaticnodiscard

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.

◆ manhattan()

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

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

inlinenodiscardnoexcept

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

◆ pattern()

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

const Pattern & pattern ( void ) const

inlinenodiscardnoexcept

the pattern

◆ residue()

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

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

inlinenodiscardnoexcept

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

◆ rule()

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

BlankRule rule ( void ) const

inlinenodiscardnoexcept

the rule of the blank

◆ save()

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

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

inline

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.

◆ value()

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

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

inlinenodiscardnoexcept

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

Member Data Documentation

◆ cells

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

int cells = W * H

staticconstexpr

the cells

◆ file_version

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

std::uint32_t file_version = 1

staticconstexpr

the version of the format of the files

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

PBeFS/astar/PatternDatabase.h

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ board_type

◆ Pattern

Constructor & Destructor Documentation

◆ PatternTable()

Member Function Documentation

◆ build()

◆ bytes()

◆ cached()

◆ checksum()

◆ distances()

◆ encode()

◆ entries()

◆ exact()

◆ file_name()

◆ from_file()

◆ load()

◆ manhattan()

◆ pattern()

◆ residue()

◆ rule()

◆ save()

◆ value()

Member Data Documentation

◆ cells

◆ file_version