PatternDatabase.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*------------------------ File PatternDatabase.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_PatternDatabase
 #define __PBeFS_PatternDatabase
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <algorithm>
 
#include <array>
 
#include <atomic>
 
#include <bit>
 
#include <cstddef>
 
#include <cstdint>
 
#include <cstdio>
 
#include <cstdlib>
 
#include <cstring>
 
#include <filesystem>
 
#include <fstream>
 
#include <iterator>
 
#include <stdexcept>
 
#include <string>
 
#include <thread>
 
#include <utility>
 
#include <vector>
 
#include "PBeFS/astar/SlidingTile.h"
 
#include "PBeFS/astar/Structures.h"
 
#include "PBeFS/core/SearchUtils.h"
 
#include "ADS/succinct/PackedArray.h"
 
#include "ADS/succinct/RankSelect.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*--------------------------------- TYPES ----------------------------------*/
/*--------------------------------------------------------------------------*/
 
enum class BlankRule : std::uint8_t {
 ignored ,   
 minimized   
 };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
using Partition = std::vector< std::vector< int > >;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
struct PDBOptions {
 BlankRule blank = BlankRule::ignored;     
 bool reflect = true;          
 unsigned compress = 1;        
 unsigned threads = 0;         
 std::string cache;            
 };
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS TilePattern ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H >
class TilePattern {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 static constexpr int cells = W * H;       
 
 static_assert( ( W >= 2 ) && ( H >= 2 ) && ( cells <= 32 ) ,
                "TilePattern: at most 32 cells" );
 
 using board_type = std::array< std::uint8_t , cells >;  

 struct Moves {
  int n = 0;                                
  int cell[ 4 ] = { 0 , 0 , 0 , 0 };        
  };
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 [[nodiscard]] static board_type korf_goal( void ) {
  board_type b{};
  for( int i = 0 ; i < cells ; ++i )
   b[ i ] = static_cast< std::uint8_t >( i );
  return( b );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 explicit TilePattern( const std::vector< int > & tiles ,
                       const board_type & goal = korf_goal() )
  : v_tiles( tiles ) , v_goal( goal ) {
  std::uint64_t seen = 0;
  for( std::uint8_t t : goal ) {
   if( ( t >= cells ) || ( ( seen >> t ) & 1u ) )
    throw( std::invalid_argument( "TilePattern::TilePattern: the goal is "
                                  "not a permutation" ) );
   seen |= std::uint64_t( 1 ) << t;
   }
  if( tiles.empty() || ( int( tiles.size() ) >= cells ) )
   throw( std::invalid_argument( "TilePattern::TilePattern: a pattern has "
                                 "1 to W H - 1 tiles" ) );
  seen = 0;
  for( int t : tiles ) {
   if( ( t <= 0 ) || ( t >= cells ) || ( ( seen >> t ) & 1u ) )
    throw( std::invalid_argument( "TilePattern::TilePattern: bad tile " +
                                  std::to_string( t ) ) );
   seen |= std::uint64_t( 1 ) << t;
   }
  f_k = int( tiles.size() );
  board_type cell{};
  for( int c = 0 ; c < cells ; ++c )
   cell[ goal[ c ] % cells ] = std::uint8_t( c );
  for( std::size_t i = 0 ; i < v_goal_cell.size() ; ++i )
   if( i < tiles.size() )
    v_goal_cell[ i ] = cell[ std::size_t( tiles[ i ] ) % cells ];
  f_entries = 1;
  for( int i = 0 ; i < f_k ; ++i )
   f_entries *= std::uint64_t( cells - i );
  f_goal_rank = rank( v_goal_cell.data() );
  }
 
/*---------------------- METHODS FOR READING THE DATA ----------------------*/
 
 [[nodiscard]] int size( void ) const noexcept { return( f_k ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const std::vector< int > & tiles( void ) const noexcept {
  return( v_tiles );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const board_type & goal( void ) const noexcept {
  return( v_goal );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int goal_cell( int i ) const noexcept {
  return( v_goal_cell[ i ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_entries );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::uint64_t goal_rank( void ) const noexcept {
  return( f_goal_rank );
  }
 
/*------------------------- RANKING THE PLACEMENTS -------------------------*/
 
 [[nodiscard]] std::uint64_t rank( const std::uint8_t * p ) const noexcept {
  std::uint64_t r = 0;
  std::uint32_t used = 0;
  for( int i = 0 ; i < f_k ; ++i ) {
   const std::uint32_t below = used & ( ( std::uint32_t( 1 ) << p[ i ] ) -
                                        1u );
   r = r * std::uint64_t( cells - i ) +
       std::uint64_t( p[ i ] - std::popcount( below ) );
   used |= std::uint32_t( 1 ) << p[ i ];
   }
  return( r );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void unrank( std::uint64_t r , std::uint8_t * p ) const noexcept {
  int d[ cells ];
  for( int i = f_k - 1 ; i >= 0 ; --i ) {
   d[ i ] = int( r % std::uint64_t( cells - i ) );
   r /= std::uint64_t( cells - i );
   }
  std::uint32_t free = c_full;
  for( int i = 0 ; i < f_k ; ++i ) {
   p[ i ] = std::uint8_t( select( free , d[ i ] ) );
   free &= ~( std::uint32_t( 1 ) << p[ i ] );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int manhattan( const std::uint8_t * p ) const noexcept {
  int m = 0;
  for( int i = 0 ; i < f_k ; ++i )
   m += distance( p[ i ] , v_goal_cell[ i ] );
  return( m );
  }
 
/*----------------------------- BOARD HELPERS ------------------------------*/
 
 [[nodiscard]] static const Moves & moves( int c ) noexcept {
  return( c_moves[ std::size_t( c ) ] );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static int distance( int a , int b ) noexcept {
  return( std::abs( a / W - b / W ) + std::abs( a % W - b % W ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 static constexpr std::uint32_t c_full = cells == 32 ? ~std::uint32_t( 0 )
  : ( std::uint32_t( 1 ) << cells ) - 1u;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static int select( std::uint32_t x , int j ) noexcept {
  for( ; j > 0 ; --j )
   x &= x - 1u;
  return( std::countr_zero( x ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static std::uint32_t region( std::uint32_t free , int b )
  noexcept {
  std::uint32_t r = std::uint32_t( 1 ) << b , last = 0;
  while( r != last ) {
   last = r;
   std::uint32_t g = r | ( r >> W ) | ( r << W ) |
                     ( ( r & ~c_right ) << 1 ) | ( ( r & ~c_left ) >> 1 );
   r = g & free;
   }
  return( r );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 static constexpr std::uint32_t c_left = [] {
  std::uint32_t m = 0;
  for( int r = 0 ; r < H ; ++r )
   m |= std::uint32_t( 1 ) << ( r * W );
  return( m );
  }();

 static constexpr std::uint32_t c_right = c_left << ( W - 1 );

 static constexpr std::array< Moves , cells > c_moves = [] {
  std::array< Moves , cells > m{};
  for( int b = 0 ; b < cells ; ++b ) {
   const int r = b / W , k = b % W;
   Moves & o = m[ std::size_t( b ) ];
   if( r > 0 )
    o.cell[ o.n++ ] = b - W;
   if( k > 0 )
    o.cell[ o.n++ ] = b - 1;
   if( k < W - 1 )
    o.cell[ o.n++ ] = b + 1;
   if( r < H - 1 )
    o.cell[ o.n++ ] = b + W;
   }
  return( m );
  }();
 
 std::vector< int > v_tiles;                     
 board_type v_goal;                              
 std::array< std::uint8_t , cells > v_goal_cell{};  
 int f_k = 0;                                    
 std::uint64_t f_entries = 0;                    
 std::uint64_t f_goal_rank = 0;                  
 
 };  // end( class( TilePattern ) )
 
/*--------------------------------------------------------------------------*/
/*----------------------------- THE ENCODINGS ------------------------------*/
/*--------------------------------------------------------------------------*/
 
namespace detail {

[[nodiscard]] inline std::vector< std::uint8_t > packed_bytes(
 const std::vector< std::uint64_t > & w , std::size_t n )
{
 std::vector< std::uint8_t > b( n );
 for( std::size_t i = 0 ; i < n ; ++i )
  b[ i ] = std::uint8_t( w[ i >> 3 ] >> ( 8 * ( i & 7 ) ) );
 return( b );
 }

 
template< unsigned B >
[[nodiscard]] inline unsigned packed_field( const std::vector< std::uint8_t >
                                            & d , std::uint64_t i ) noexcept
{
 const std::uint64_t bit = i * B;
 return( ( d[ bit >> 3 ] >> ( bit & 7 ) ) & ( ( 1u << B ) - 1 ) );
 }
 
}  // end( namespace detail )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class ByteEntries {
 
 public:
 
 static constexpr std::uint32_t code = 1;           
 static constexpr const char * name = "byte";       
 static constexpr bool relative = false;            

 
 template< class M >
 [[nodiscard]] static ByteEntries encode( const std::vector< std::uint8_t >
                                          & h , M && , unsigned = 1 ) {
  ADS::Sequential ex;
  ByteEntries e;
  e.f_data = Array( ex , h.size() , [ & ]( std::size_t r ) {
   return( h[ r ] );
   } );
  return( e );
  }

 
 [[nodiscard]] static ByteEntries decode( std::vector< std::uint8_t > data ,
                                          std::uint64_t n , unsigned = 1 ) {
  if( data.size() != n )
   throw( std::runtime_error( "ByteEntries::decode: bad size" ) );
  return( encode( data , 0 ) );
  }

 
 [[nodiscard]] int value( std::uint64_t r , int ) const noexcept {
  return( int( f_data.get( r ) ) );
  }

 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_data.size() );
  }

 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( f_data.size() );
  }

 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  return( detail::packed_bytes( f_data.words() , bytes() ) );
  }
 
 private:
 
 using Array = ADS::PackedArray< 8 >;            
 
 Array f_data;                                   
 
 };  // end( class( ByteEntries ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class NibbleEntries {
 
 public:
 
 static constexpr std::uint32_t code = 2;           
 static constexpr const char * name = "nibble";     
 static constexpr bool relative = false;            

 
 template< class M >
 [[nodiscard]] static NibbleEntries encode( const std::vector< std::uint8_t >
                                            & h , M && m , unsigned = 1 ) {
  ADS::Sequential ex;
  NibbleEntries e;
  e.f_data = Array( ex , h.size() , [ & ]( std::size_t r ) {
   return( std::uint64_t( excess( h[ r ] , m( r ) ) ) );
   } );
  return( e );
  }

 
 [[nodiscard]] static NibbleEntries decode( std::vector< std::uint8_t > data ,
                                            std::uint64_t n , unsigned = 1 ) {
  if( data.size() != ( n + 1 ) / 2 )
   throw( std::runtime_error( "NibbleEntries::decode: bad size" ) );
  ADS::Sequential ex;
  NibbleEntries e;
  e.f_data = Array( ex , n , [ & ]( std::size_t r ) {
   return( detail::packed_field< 4 >( data , r ) );
   } );
  return( e );
  }

 
 [[nodiscard]] int value( std::uint64_t r , int m ) const noexcept {
  return( m + 2 * int( f_data.get( r ) ) );
  }

 [[nodiscard]] std::uint64_t clamped( void ) const noexcept {
  return( f_data.clamped() );
  }

 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_data.size() );
  }

 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( ( f_data.size() + 1 ) / 2 );
  }

 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  return( detail::packed_bytes( f_data.words() , bytes() ) );
  }

 
 [[nodiscard]] static int excess( int h , int m ) {
  if( ( h < m ) || ( ( h - m ) % 2 ) )
   throw( std::logic_error( "NibbleEntries::excess: h - m is not even "
                            "and nonnegative" ) );
  return( ( h - m ) / 2 );
  }
 
 private:
 
 using Array = ADS::PackedArray< 4 , true >;     
 
 Array f_data;                                   
 
 };  // end( class( NibbleEntries ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class Mod3Entries {
 
 public:
 
 static constexpr std::uint32_t code = 3;           
 static constexpr const char * name = "mod3";       
 static constexpr bool relative = true;             
 static constexpr int modulus = 3;                  

 
 template< class M >
 [[nodiscard]] static Mod3Entries encode( const std::vector< std::uint8_t >
                                          & h , M && , unsigned = 1 ) {
  ADS::Sequential ex;
  Mod3Entries e;
  e.f_data = ADS::TritArray( ex , h.size() , [ & ]( std::size_t r ) {
   return( unsigned( h[ r ] % 3 ) );
   } );
  return( e );
  }

 
 [[nodiscard]] static Mod3Entries decode( std::vector< std::uint8_t > data ,
                                          std::uint64_t n , unsigned = 1 ) {
  if( data.size() != ( n + 4 ) / 5 )
   throw( std::runtime_error( "Mod3Entries::decode: bad size" ) );
  for( std::uint8_t b : data )
   if( b >= 243 )
    throw( std::runtime_error( "Mod3Entries::decode: bad byte" ) );
  static constexpr unsigned power[ 5 ] = { 1 , 3 , 9 , 27 , 81 };
  ADS::Sequential ex;
  Mod3Entries e;
  e.f_data = ADS::TritArray( ex , n , [ & ]( std::size_t r ) {
   return( data[ r / 5 ] / power[ r % 5 ] % 3 );
   } );
  return( e );
  }

 
 [[nodiscard]] int residue( std::uint64_t r , int ) const noexcept {
  return( int( f_data.get( r ) ) );
  }

 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_data.size() );
  }

 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( f_data.bytes() );
  }

 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  return( f_data.data() );
  }
 
 private:
 
 ADS::TritArray f_data;                          
 
 };  // end( class( Mod3Entries ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class ParityBitEntries {
 
 public:
 
 static constexpr std::uint32_t code = 6;           
 static constexpr const char * name = "bit";        
 static constexpr bool relative = true;             
 static constexpr int modulus = 4;                  

 
 template< class M >
 [[nodiscard]] static ParityBitEntries encode(
  const std::vector< std::uint8_t > & h , M && m , unsigned = 1 ) {
  ADS::Sequential ex;
  ParityBitEntries e;
  e.f_data = Array( ex , h.size() , [ & ]( std::size_t r ) {
   static_cast< void >( NibbleEntries::excess( h[ r ] , m( r ) ) );
   return( std::uint64_t( ( h[ r ] >> 1 ) & 1 ) );
   } );
  return( e );
  }

 
 [[nodiscard]] static ParityBitEntries decode(
  std::vector< std::uint8_t > data , std::uint64_t n , unsigned = 1 ) {
  if( data.size() != ( n + 7 ) / 8 )
   throw( std::runtime_error( "ParityBitEntries::decode: bad size" ) );
  ADS::Sequential ex;
  ParityBitEntries e;
  e.f_data = Array( ex , n , [ & ]( std::size_t r ) {
   return( detail::packed_field< 1 >( data , r ) );
   } );
  return( e );
  }

 
 [[nodiscard]] int residue( std::uint64_t r , int m ) const noexcept {
  return( 2 * int( f_data.get( r ) ) + ( m & 1 ) );
  }

 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_data.size() );
  }

 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( ( f_data.size() + 7 ) / 8 );
  }

 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  return( detail::packed_bytes( f_data.words() , bytes() ) );
  }
 
 private:
 
 using Array = ADS::PackedArray< 1 >;            
 
 Array f_data;                                   
 
 };  // end( class( ParityBitEntries ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class MinNibbleEntries {
 
 public:
 
 static constexpr std::uint32_t code = 4;           
 static constexpr const char * name = "min";        
 static constexpr bool relative = false;            

 
 template< class M >
 [[nodiscard]] static MinNibbleEntries encode(
  const std::vector< std::uint8_t > & h , M && m , unsigned c = 1 ) {
  ADS::Sequential ex;
  MinNibbleEntries e;
  e.set_group( h.size() , c );
  e.f_data = Array( ex , e.groups() , [ & ]( std::size_t g ) {
   const std::uint64_t a = std::uint64_t( g ) << e.f_shift;
   const std::uint64_t b = std::min( e.f_n , a + ( 1u << e.f_shift ) );
   int x = 15;
   for( std::uint64_t r = a ; r < b ; ++r )
    x = std::min( x , NibbleEntries::excess( h[ r ] , m( r ) ) );
   return( std::uint64_t( x ) );
   } );
  return( e );
  }

 
 [[nodiscard]] static MinNibbleEntries decode(
  std::vector< std::uint8_t > data , std::uint64_t n , unsigned c = 1 ) {
  MinNibbleEntries e;
  e.set_group( n , c );
  if( data.size() != ( e.groups() + 1 ) / 2 )
   throw( std::runtime_error( "MinNibbleEntries::decode: bad size" ) );
  ADS::Sequential ex;
  e.f_data = Array( ex , e.groups() , [ & ]( std::size_t g ) {
   return( detail::packed_field< 4 >( data , g ) );
   } );
  return( e );
  }

 
 [[nodiscard]] int value( std::uint64_t r , int m ) const noexcept {
  return( m + 2 * int( f_data.get( r >> f_shift ) ) );
  }

 [[nodiscard]] std::uint64_t entries( void ) const noexcept { return( f_n ); }

 [[nodiscard]] unsigned group( void ) const noexcept {
  return( 1u << f_shift );
  }

 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( ( groups() + 1 ) / 2 );
  }

 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  return( detail::packed_bytes( f_data.words() , bytes() ) );
  }
 
 private:
 
 using Array = ADS::PackedArray< 4 >;            
 
 // n entries in groups of c, a power of 2
 void set_group( std::uint64_t n , unsigned c ) {
  if( ( c == 0 ) || ! std::has_single_bit( c ) )
   throw( std::invalid_argument( "MinNibbleEntries::set_group: the group "
                                 "is a power of 2" ) );
  f_n = n;
  f_shift = std::countr_zero( c );
  }
 
 // the number of the groups
 [[nodiscard]] std::uint64_t groups( void ) const noexcept {
  return( ( f_n + ( std::uint64_t( 1 ) << f_shift ) - 1 ) >> f_shift );
  }
 
 Array f_data;                                   
 std::uint64_t f_n = 0;                          
 int f_shift = 0;                                
 
 };  // end( class( MinNibbleEntries ) )
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
class SparseEntries {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
 static constexpr std::uint32_t code = 5;           
 static constexpr const char * name = "sparse";     
 static constexpr bool relative = false;            
 
/*------------------------------ CONSTRUCTION ------------------------------*/
 
 template< class M >
 [[nodiscard]] static SparseEntries encode( const std::vector< std::uint8_t >
                                            & h , M && m , unsigned = 1 ) {
  ADS::BitVector b( h.size() );
  Excesses x;
  for( std::uint64_t r = 0 ; r < h.size() ; ++r ) {
   const int mr = m( r );
   if( ( h[ r ] < mr ) || ( ( h[ r ] - mr ) % 2 ) )
    throw( std::logic_error( "SparseEntries::encode: h - m is not even "
                             "and nonnegative" ) );
   const int e = ( h[ r ] - mr ) / 2;
   if( e == 0 )
    continue;
   b.set( r );
   x.push_back( Excesses::Word( e ) );
   }
  SparseEntries s;
  s.f_bits = ADS::RankSelect( std::move( b ) );
  s.f_excess = std::move( x );
  return( s );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static SparseEntries decode( std::vector< std::uint8_t > data ,
                                            std::uint64_t n , unsigned = 1 ) {
  const std::uint64_t words = ( n + 63 ) / 64;
  if( data.size() < 8 * words )
   throw( std::runtime_error( "SparseEntries::decode: bad size" ) );
  ADS::BitVector b( n );
  std::uint64_t z = 0;
  for( std::uint64_t w = 0 ; w < words ; ++w ) {
   std::uint64_t x = 0;
   for( int i = 0 ; i < 8 ; ++i )
    x |= std::uint64_t( data[ 8 * w + std::uint64_t( i ) ] ) << ( 8 * i );
   if( ( w + 1 == words ) && ( n % 64 ) && ( x >> ( n % 64 ) ) )
    throw( std::runtime_error( "SparseEntries::decode: bits past the "
                               "end" ) );
   z += std::uint64_t( std::popcount( x ) );
   for( ; x ; x &= x - 1 )
    b.set( 64 * w + std::uint64_t( std::countr_zero( x ) ) );
   }
  if( data.size() != 8 * words + ( z + 1 ) / 2 )
   throw( std::runtime_error( "SparseEntries::decode: bad size" ) );
  const std::vector< std::uint8_t > tail( data.begin() +
                                         std::ptrdiff_t( 8 * words ) ,
                                         data.end() );
  ADS::Sequential ex;
  SparseEntries s;
  s.f_bits = ADS::RankSelect( std::move( b ) );
  s.f_excess = Excesses( ex , z , [ & ]( std::size_t i ) {
   return( detail::packed_field< 4 >( tail , i ) );
   } );
  return( s );
  }
 
/*-------------------------------- LOOKUPS ---------------------------------*/
 
 [[nodiscard]] int value( std::uint64_t r , int m ) const {
  if( ! f_bits[ r ] )
   return( m );
  return( m + 2 * int( f_excess.get( f_bits.rank1( r ) ) ) );
  }
 
/*---------------------- METHODS FOR READING THE DATA ----------------------*/
 
 [[nodiscard]] std::uint64_t entries( void ) const noexcept {
  return( f_bits.size() );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::uint64_t nonzero( void ) const noexcept {
  return( f_bits.ones() );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( ( f_bits.size() + 63 ) / 64 * 8 + f_bits.directoryBits() / 8 +
          ( f_excess.size() + 1 ) / 2 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::vector< std::uint8_t > payload( void ) const {
  std::vector< std::uint8_t > d;
  const auto & w = f_bits.bits().words();
  const std::size_t words = ( f_bits.size() + 63 ) / 64;
  const auto x = detail::packed_bytes( f_excess.words() ,
                                      ( f_excess.size() + 1 ) / 2 );
  d.reserve( 8 * words + x.size() );
  for( std::size_t i = 0 ; i < words ; ++i )
   for( int k = 0 ; k < 8 ; ++k )
    d.push_back( std::uint8_t( w[ i ] >> ( 8 * k ) ) );
  d.insert( d.end() , x.begin() , x.end() );
  return( d );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 using Excesses = ADS::PackedArray< 4 , true >;  
 
 ADS::RankSelect f_bits;            
 Excesses f_excess;                 
 
 };  // end( class( SparseEntries ) )
 
/*--------------------------------------------------------------------------*/
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS PatternTable --------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H , class Enc = NibbleEntries >
class PatternTable {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using Pattern = TilePattern< W , H >;           
 using board_type = typename Pattern::board_type;   
 
 static constexpr int cells = W * H;             

 static constexpr std::uint32_t file_version = 1;
 
/*------------------------------ CONSTRUCTOR -------------------------------*/
 
 PatternTable( const Pattern & p , BlankRule rule , unsigned compress ,
               Enc entries , bool from_file = false )
  : f_pattern( p ) , f_rule( rule ) , f_compress( compress ) ,
    f_entries( std::move( entries ) ) , f_from_file( from_file ) {
  if constexpr( Enc::relative )
   if( rule != BlankRule::ignored )
    throw( std::invalid_argument( "PatternTable::PatternTable: the "
                                  "residues need the blank ignored" ) );
  if( f_entries.entries() != p.entries() )
   throw( std::invalid_argument( "PatternTable::PatternTable: entries and "
                                 "pattern differ" ) );
  for( int i = 0 ; i < p.size() ; ++i )
   for( int c = 0 ; c < cells ; ++c )
    v_md[ std::size_t( i ) ][ std::size_t( c ) ] =
     std::uint8_t( Pattern::distance( c , p.goal_cell( i ) ) );
  }
 
/*------------------------------ CONSTRUCTION ------------------------------*/

 
 template< ADS::WorkerExecutor Executor = ADS::ThreadPool >
 [[nodiscard]] static std::vector< std::uint8_t > distances(
  const Pattern & p , BlankRule rule , unsigned threads = 0 ) {
  if( threads == 0 )
   threads = std::max( 1u , std::thread::hardware_concurrency() );
  auto h = rule == BlankRule::ignored
           ? distances_ignored< Executor >( p , threads )
           : distances_minimized< Executor >( p , threads );
  for( std::uint8_t x : h )
   if( x == c_unseen )
    throw( std::logic_error( "PatternTable::distances: a placement is "
                             "not reached" ) );
  return( h );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static PatternTable encode( const Pattern & p ,
                                           BlankRule rule ,
                                           const std::vector< std::uint8_t >
                                           & h , unsigned compress = 1 ) {
  std::vector< std::uint8_t > q( std::size_t( p.size() ) );
  auto m = [ & ]( std::uint64_t r ) {
   p.unrank( r , q.data() );
   return( p.manhattan( q.data() ) );
   };
  return( PatternTable( p , rule , compress ,
                        Enc::encode( h , m , compress ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< ADS::WorkerExecutor Executor = ADS::ThreadPool >
 [[nodiscard]] static PatternTable build( const Pattern & p ,
                                          BlankRule rule ,
                                          unsigned compress = 1 ,
                                          unsigned threads = 0 ) {
  return( encode( p , rule , distances< Executor >( p , rule , threads ) ,
                  compress ) );
  }
 
/*-------------------------------- LOOKUPS ---------------------------------*/
 
 [[nodiscard]] int value( const std::uint8_t * q ) const noexcept
  requires( ! Enc::relative ) {
  return( f_entries.value( f_pattern.rank( q ) , manhattan( q ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int manhattan( const std::uint8_t * q ) const noexcept {
  int m = 0;
  for( int i = 0 ; i < f_pattern.size() ; ++i )
   m += v_md[ std::size_t( i ) ][ q[ i ] ];
  return( m );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int residue( const std::uint8_t * q ) const noexcept
  requires( Enc::relative ) {
  return( f_entries.residue( f_pattern.rank( q ) , manhattan( q ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] int exact( const std::uint8_t * q ) const
  requires( Enc::relative ) {
  const int k = f_pattern.size();
  std::uint8_t p[ cells ];
  std::copy( q , q + k , p );
  constexpr int M = Enc::modulus;
  std::uint64_t r = f_pattern.rank( p );
  int v = 0;
  while( r != f_pattern.goal_rank() ) {
   const int want = ( residue( p ) + M - 1 ) % M;
   std::uint32_t occ = 0;
   for( int i = 0 ; i < k ; ++i )
    occ |= std::uint32_t( 1 ) << p[ i ];
   bool moved = false;
   for( int i = 0 ; ( i < k ) && ! moved ; ++i ) {
    const auto & mv = Pattern::moves( p[ i ] );
    for( int j = 0 ; j < mv.n ; ++j ) {
     const int c = mv.cell[ j ];
     if( ( occ >> c ) & 1u )
      continue;
     const std::uint8_t old = p[ i ];
     p[ i ] = std::uint8_t( c );
     if( residue( p ) == want ) {
      r = f_pattern.rank( p );
      moved = true;
      break;
      }
     p[ i ] = old;
     }
    }
   if( ! moved )
    throw( std::logic_error( "PatternTable::exact: no neighbour one step "
                             "closer to the goal" ) );
   ++v;
   }
  return( v );
  }
 
/*---------------------- METHODS FOR READING THE DATA ----------------------*/
 
 [[nodiscard]] const Pattern & pattern( void ) const noexcept {
  return( f_pattern );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] BlankRule rule( void ) const noexcept { return( f_rule ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const Enc & entries( void ) const noexcept {
  return( f_entries );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  return( f_entries.bytes() );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] bool from_file( void ) const noexcept {
  return( f_from_file );
  }
 
/*------------------------------ PERSISTENCE -------------------------------*/

 
 void save( const std::string & path ) const {
  std::vector< std::uint8_t > b = header( f_pattern , f_rule ,
                                          f_compress );
  const auto pay = f_entries.payload();
  put( b , f_entries.entries() , 8 );
  put( b , pay.size() , 8 );
  b.insert( b.end() , pay.begin() , pay.end() );
  put( b , checksum( b.data() , b.size() ) , 8 );
  const std::string tmp = path + ".tmp" +
                          std::to_string( std::hash< std::thread::id >()(
                                           std::this_thread::get_id() ) );
  {
   std::ofstream out( tmp , std::ios::binary | std::ios::trunc );
   out.write( reinterpret_cast< const char * >( b.data() ) ,
              std::streamsize( b.size() ) );
   if( ! out )
    throw( std::runtime_error( "PatternTable::save: cannot write " + tmp )
           );
   }
  std::filesystem::rename( tmp , path );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] static PatternTable load( const std::string & path ,
                                         const Pattern & p , BlankRule rule ,
                                         unsigned compress = 1 ) {
  std::ifstream in( path , std::ios::binary );
  if( ! in )
   throw( std::runtime_error( "PatternTable::load: cannot read " + path ) );
  std::vector< std::uint8_t > b( ( std::istreambuf_iterator< char >( in ) ) ,
                                 std::istreambuf_iterator< char >() );
  const std::vector< std::uint8_t > head = header( p , rule , compress );
  const std::size_t fixed = head.size() + 16;
  if( b.size() < fixed + 8 )
   throw( std::runtime_error( "PatternTable::load: " + path +
                              " is truncated" ) );
  if( ! std::equal( head.begin() , head.begin() + 12 , b.begin() ) )
   throw( std::runtime_error( "PatternTable::load: " + path +
                              " is not a table of this version" ) );
  if( get( b.data() + b.size() - 8 , 8 ) !=
      checksum( b.data() , b.size() - 8 ) )
   throw( std::runtime_error( "PatternTable::load: " + path +
                              " is corrupted (checksum)" ) );
  if( ! std::equal( head.begin() , head.end() , b.begin() ) )
   throw( std::runtime_error( "PatternTable::load: " + path +
                              " holds another table" ) );
  const std::uint64_t n = get( b.data() + head.size() , 8 );
  const std::uint64_t len = get( b.data() + head.size() + 8 , 8 );
  if( ( n != p.entries() ) || ( len != b.size() - fixed - 8 ) )
   throw( std::runtime_error( "PatternTable::load: " + path +
                              " has wrong lengths" ) );
  std::vector< std::uint8_t > pay( b.begin() + std::ptrdiff_t( fixed ) ,
                                   b.end() - 8 );
  return( PatternTable( p , rule , compress ,
                        Enc::decode( std::move( pay ) , n , compress ) ,
                        true ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static std::string file_name( const Pattern & p ,
                                             BlankRule rule ,
                                             unsigned compress = 1 ) {
  std::string s = "pdb-" + std::to_string( W ) + "x" + std::to_string( H ) +
                  ( rule == BlankRule::ignored ? "-ignored-" : "-minimized-" )
                  + Enc::name + "-" + std::to_string( compress ) + "-t";
  for( std::size_t i = 0 ; i < p.tiles().size() ; ++i )
   s += ( i ? "." : "" ) + std::to_string( p.tiles()[ i ] );
  const auto & g = p.goal();
  char hex[ 17 ];
  std::snprintf( hex , sizeof( hex ) , "%016llx" , static_cast<
                 unsigned long long >( checksum( g.data() , g.size() ) ) );
  return( s + "-g" + hex + ".pdb" );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 template< ADS::WorkerExecutor Executor = ADS::ThreadPool >
 [[nodiscard]] static PatternTable cached( const std::string & dir ,
                                           const Pattern & p ,
                                           BlankRule rule ,
                                           unsigned compress = 1 ,
                                           unsigned threads = 0 ) {
  namespace fs = std::filesystem;
  const fs::path own = fs::path( dir ) / file_name( p , rule , compress );
  if( fs::exists( own ) )
   try {
    return( load( own.string() , p , rule , compress ) );
    }
   catch( std::runtime_error & ) {}            // built again below
  fs::create_directories( dir );
  using Bytes = PatternTable< W , H , ByteEntries >;
  const fs::path raw = fs::path( dir ) / Bytes::file_name( p , rule );
  std::vector< std::uint8_t > h;
  if( fs::exists( raw ) )
   try {
    h = Bytes::load( raw.string() , p , rule ).entries().payload();
    }
   catch( std::runtime_error & ) {}
  if( h.empty() ) {
   h = distances< Executor >( p , rule , threads );
   Bytes( p , rule , 1 , ByteEntries::encode( h , 0 ) ).save(
    raw.string() );
   }
  PatternTable t = encode( p , rule , h , compress );
  if( own != raw )
   t.save( own.string() );
  return( t );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] static std::uint64_t checksum( const std::uint8_t * b ,
                                              std::size_t n ) noexcept {
  std::uint64_t h = ADS::splitmix64( 0x5042654653504442ULL ^ n );
  std::size_t i = 0;
  for( ; i + 8 <= n ; i += 8 )
   h = ADS::splitmix64( h ^ get( b + i , 8 ) ) + i;
  if( i < n )
   h = ADS::splitmix64( h ^ get( b + i , int( n - i ) ) );
  return( h );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:

 static constexpr std::uint8_t c_unseen = 0xFF;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the first bytes of a file: magic, version, sizes, rule, encoding,
 // pattern and goal
 
 [[nodiscard]] static std::vector< std::uint8_t > header( const Pattern & p ,
                                                          BlankRule rule ,
                                                          unsigned compress
                                                          ) {
  std::vector< std::uint8_t > b = { 'P' , 'B' , 'e' , 'F' , 'S' , 'P' , 'D' ,
                                    'B' };
  put( b , file_version , 4 );
  put( b , std::uint64_t( W ) , 4 );
  put( b , std::uint64_t( H ) , 4 );
  put( b , std::uint64_t( rule ) , 4 );
  put( b , Enc::code , 4 );
  put( b , compress , 4 );
  put( b , std::uint64_t( p.size() ) , 4 );
  for( int t : p.tiles() )
   b.push_back( std::uint8_t( t ) );
  b.insert( b.end() , p.goal().begin() , p.goal().end() );
  return( b );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // appends the k low bytes of x, the lowest first
 
 static void put( std::vector< std::uint8_t > & b , std::uint64_t x ,
                  int k ) {
  for( int i = 0 ; i < k ; ++i )
   b.push_back( std::uint8_t( x >> ( 8 * i ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the integer of the k bytes at b, the lowest first
 
 [[nodiscard]] static std::uint64_t get( const std::uint8_t * b , int k )
  noexcept {
  std::uint64_t x = 0;
  for( int i = 0 ; i < k ; ++i )
   x |= std::uint64_t( b[ i ] ) << ( 8 * i );
  return( x );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // calls f( a , b ) for the blocks [ a , b ) of [ 0 , n ) on p workers of
 // Executor, each worker taking the next block when it ends one
 
 template< class Executor , class F >
 static void blocks( std::uint64_t n , unsigned p , F && f ) {
  constexpr std::uint64_t block = 1 << 14;
  std::atomic< std::uint64_t > next{ 0 };
  run_workers< Executor >( nullptr , p , [ & ]( unsigned ) {
   for( ; ; ) {
    const std::uint64_t a = next.fetch_add( block ,
                                            std::memory_order_relaxed );
    if( a >= n )
     break;
    f( a , std::min( n , a + block ) );
    }
   } );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // BUILD-IGNORED: the distances with the blank ignored
 
 template< class Executor >
 [[nodiscard]] static std::vector< std::uint8_t > distances_ignored(
  const Pattern & pat , unsigned threads ) {
  const int k = pat.size();
  std::vector< std::uint8_t > h( pat.entries() , c_unseen );
  h[ pat.goal_rank() ] = 0;
  for( int d = 0 ; ; ++d ) {
   if( d + 1 >= c_unseen )
    throw( std::logic_error( "PatternTable::distances_ignored: a distance "
                             "beyond 254" ) );
   std::atomic< std::uint64_t > fresh{ 0 };
   blocks< Executor >( h.size() , threads , [ & ]( std::uint64_t a ,
                                                  std::uint64_t b ) {
    std::uint64_t mine = 0;
    std::uint8_t p[ cells ];
    for( std::uint64_t r = a ; r < b ; ++r ) {
     if( std::atomic_ref< std::uint8_t >( h[ r ] ).load(
          std::memory_order_relaxed ) != d )
      continue;
     pat.unrank( r , p );
     std::uint32_t occ = 0;
     for( int i = 0 ; i < k ; ++i )
      occ |= std::uint32_t( 1 ) << p[ i ];
     for( int i = 0 ; i < k ; ++i ) {
      const std::uint8_t old = p[ i ];
      const auto & mv = Pattern::moves( old );
      for( int j = 0 ; j < mv.n ; ++j ) {
       const int c = mv.cell[ j ];
       if( ( occ >> c ) & 1u )
        continue;
       p[ i ] = std::uint8_t( c );
       std::uint8_t e = c_unseen;
       if( std::atomic_ref< std::uint8_t >( h[ pat.rank( p ) ] )
            .compare_exchange_strong( e , std::uint8_t( d + 1 ) ,
                                      std::memory_order_relaxed ) )
        ++mine;
       }
      p[ i ] = old;
      }
     }
    fresh.fetch_add( mine , std::memory_order_relaxed );
    } );
   if( fresh.load() == 0 )
    return( h );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // BUILD-MINIMIZED: the distances with the blank minimized; the state of
 // ( r , b ) takes 2 bits (0 unseen, 1 current, 2 next, 3 old) at the
 // index r ( n - k ) + f, f being the index of b among the free cells
 
 template< class Executor >
 [[nodiscard]] static std::vector< std::uint8_t > distances_minimized(
  const Pattern & pat , unsigned threads ) {
  const int k = pat.size();
  const std::uint64_t nf = std::uint64_t( cells - k );
  const std::uint64_t states = pat.entries() * nf;
  std::vector< std::uint64_t > s( ( states + 31 ) / 32 , 0 );
  std::vector< std::uint8_t > h( pat.entries() , c_unseen );
 
  // the index of the free cell b, and the mark of the state i as next
  const auto index = [ nf ]( std::uint64_t r , std::uint32_t occ , int b ) {
   const std::uint32_t below = occ & ( ( std::uint32_t( 1 ) << b ) - 1u );
   return( r * nf + std::uint64_t( b - std::popcount( below ) ) );
   };
  const auto mark = [ & ]( std::uint64_t i ) {
   std::atomic_ref< std::uint64_t > w( s[ i / 32 ] );
   const int sh = int( 2 * ( i % 32 ) );
   std::uint64_t old = w.load( std::memory_order_relaxed );
   for( ; ; ) {
    if( ( old >> sh ) & 3u )
     return( false );
    if( w.compare_exchange_weak( old , old | ( std::uint64_t( 2 ) << sh ) ,
                                 std::memory_order_relaxed ) )
     return( true );
    }
   };
 
  std::uint8_t g[ cells ];
  pat.unrank( pat.goal_rank() , g );
  std::uint32_t gocc = 0;
  for( int i = 0 ; i < k ; ++i )
   gocc |= std::uint32_t( 1 ) << g[ i ];
  for( int b = 0 ; b < cells ; ++b )
   if( ! ( ( gocc >> b ) & 1u ) ) {
    const std::uint64_t i = index( pat.goal_rank() , gocc , b );
    s[ i / 32 ] |= std::uint64_t( 1 ) << ( 2 * ( i % 32 ) );
    }
  h[ pat.goal_rank() ] = 0;
 
  constexpr std::uint64_t lo = 0x5555555555555555ULL;
  for( int d = 0 ; ; ++d ) {
   if( d + 1 >= c_unseen )
    throw( std::logic_error( "PatternTable::distances_minimized: a "
                             "distance beyond 254" ) );
   blocks< Executor >( s.size() , threads , [ & ]( std::uint64_t a ,
                                                  std::uint64_t e ) {
    std::uint8_t p[ cells ];
    std::int8_t at[ cells ];
    for( std::uint64_t wi = a ; wi < e ; ++wi ) {
     const std::uint64_t w = std::atomic_ref< std::uint64_t >( s[ wi ] )
                              .load( std::memory_order_relaxed );
     std::uint64_t cur = w & lo & ~( w >> 1 );        // the fields = 1
     while( cur ) {
      const std::uint64_t i = wi * 32 +
                              std::uint64_t( std::countr_zero( cur ) / 2 );
      cur &= cur - 1;
      if( i >= states )
       break;
      const std::uint64_t r = i / nf;
      pat.unrank( r , p );
      std::uint32_t occ = 0;
      std::fill( at , at + cells , std::int8_t( -1 ) );
      for( int t = 0 ; t < k ; ++t ) {
       occ |= std::uint32_t( 1 ) << p[ t ];
       at[ p[ t ] ] = std::int8_t( t );
       }
      const std::uint32_t free = Pattern::c_full & ~occ;
      const int b = Pattern::select( free , int( i % nf ) );
      const std::uint32_t reg = Pattern::region( free , b );
      if( std::countr_zero( reg ) != b )
       continue;                              // not the least of its region
      for( std::uint32_t rr = reg ; rr ; rr &= rr - 1u ) {
       const int c = std::countr_zero( rr );
       const auto & mv = Pattern::moves( c );
       for( int j = 0 ; j < mv.n ; ++j ) {
        const int a2 = mv.cell[ j ];
        const int t = at[ a2 ];
        if( t < 0 )
         continue;
        p[ t ] = std::uint8_t( c );
        const std::uint64_t r2 = pat.rank( p );
        p[ t ] = std::uint8_t( a2 );
        const std::uint32_t occ2 = ( occ & ~( std::uint32_t( 1 ) << a2 ) ) |
                                   ( std::uint32_t( 1 ) << c );
        const std::uint32_t reg2 = Pattern::region( Pattern::c_full & ~occ2 ,
                                                    a2 );
        for( std::uint32_t q = reg2 ; q ; q &= q - 1u )
         mark( index( r2 , occ2 , std::countr_zero( q ) ) );
        std::uint8_t un = c_unseen;
        std::atomic_ref< std::uint8_t >( h[ r2 ] ).compare_exchange_strong(
         un , std::uint8_t( d + 1 ) , std::memory_order_relaxed );
        }
       }
      }
     }
    } );
 
   // current -> old, next -> current
   std::atomic< std::uint64_t > fresh{ 0 };
   blocks< Executor >( s.size() , threads , [ & ]( std::uint64_t a ,
                                                  std::uint64_t e ) {
    std::uint64_t mine = 0;
    for( std::uint64_t wi = a ; wi < e ; ++wi ) {
     std::uint64_t w = s[ wi ];
     const std::uint64_t cur = w & lo & ~( w >> 1 );
     const std::uint64_t nxt = ( w >> 1 ) & lo & ~w;
     w |= cur << 1;
     w = ( w & ~( nxt << 1 ) ) | nxt;
     s[ wi ] = w;
     mine += std::uint64_t( std::popcount( nxt ) );
     }
    fresh.fetch_add( mine , std::memory_order_relaxed );
    } );
   if( fresh.load() == 0 )
    return( h );
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 Pattern f_pattern;                              
 BlankRule f_rule;                               
 unsigned f_compress;                            
 Enc f_entries;                                  
 bool f_from_file;                               
 std::array< std::array< std::uint8_t , cells > , cells > v_md{};
 
 };  // end( class( PatternTable ) )
 
/*--------------------------------------------------------------------------*/
/*---------------------------- CLASS AdditivePDB ---------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H , class Enc = NibbleEntries >
class AdditivePDB {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using Table = PatternTable< W , H , Enc >;      
 using Pattern = TilePattern< W , H >;           
 using board_type = typename Pattern::board_type;   
 
 static constexpr int cells = W * H;             
 
/*------------------------------ CONSTRUCTOR -------------------------------*/
 
 explicit AdditivePDB( std::vector< Table > tables , bool reflect = true )
  : v_tables( std::move( tables ) ) {
  if( v_tables.empty() )
   throw( std::invalid_argument( "AdditivePDB::AdditivePDB: no table" ) );
  v_goal = v_tables.front().pattern().goal();
  std::fill( v_owner.begin() , v_owner.end() , std::int8_t( -1 ) );
  for( std::size_t j = 0 ; j < v_tables.size() ; ++j ) {
   const Pattern & p = v_tables[ j ].pattern();
   if( p.goal() != v_goal )
    throw( std::invalid_argument( "AdditivePDB::AdditivePDB: the tables "
                                  "have different goals" ) );
   for( int i = 0 ; i < p.size() ; ++i ) {
    const int t = p.tiles()[ std::size_t( i ) ];
    if( v_owner[ std::size_t( t ) ] >= 0 )
     throw( std::invalid_argument( "AdditivePDB::AdditivePDB: the tile " +
                                   std::to_string( t ) +
                                   " is in two patterns" ) );
    v_owner[ std::size_t( t ) ] = std::int8_t( j );
    v_place[ std::size_t( t ) ] = std::int8_t( i );
    }
   }
  int blank = 0;
  for( int c = 0 ; c < cells ; ++c )
   if( v_goal[ c ] == 0 )
    blank = c;
  f_reflect = reflect && ( W == H ) && ( blank / W == blank % W );
  if( f_reflect ) {
   board_type cell{};
   for( int c = 0 ; c < cells ; ++c ) {
    cell[ v_goal[ c ] ] = std::uint8_t( c );
    v_transpose[ c ] = std::uint8_t( ( c % W ) * W + c / W );
    }
   for( int t = 0 ; t < cells ; ++t )
    v_sigma[ t ] = v_goal[ v_transpose[ cell[ t ] ] ];
   }
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 AdditivePDB( const Partition & partition ,
              const board_type & goal = Pattern::korf_goal() ,
              const PDBOptions & o = {} )
  : AdditivePDB( make< ADS::ThreadPool >( partition , goal , o ) ) {}
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class Executor >
 [[nodiscard]] static AdditivePDB make(
  const Partition & partition ,
  const board_type & goal = Pattern::korf_goal() ,
  const PDBOptions & o = {} ) {
  std::vector< Table > t;
  for( const auto & tiles : partition ) {
   const Pattern p( tiles , goal );
   if( o.cache.empty() )
    t.push_back( Table::template build< Executor >( p , o.blank ,
                                                   o.compress , o.threads ) );
   else
    t.push_back( Table::template cached< Executor >( o.cache , p , o.blank ,
                                                    o.compress ,
                                                    o.threads ) );
   }
  return( AdditivePDB( std::move( t ) , o.reflect ) );
  }
 
/*-------------------------------- LOOKUPS ---------------------------------*/
 
 [[nodiscard]] int heuristic( const std::uint8_t * q ) const noexcept
  requires( ! Enc::relative ) {
  const int a = sum( q );
  if( ! f_reflect )
   return( a );
  std::uint8_t r[ cells ];
  reflection( q , r );
  return( std::max( a , sum( r ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

 
 [[nodiscard]] int sum( const std::uint8_t * q ) const noexcept
  requires( ! Enc::relative ) {
  int s = 0;
  std::uint8_t p[ cells ];
  for( const Table & t : v_tables ) {
   gather( t , q , p );
   s += t.value( p );
   }
  return( s );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int exact( const std::uint8_t * q ) const
  requires( Enc::relative ) {
  const auto add = [ & ]( const std::uint8_t * x ) {
   int s = 0;
   std::uint8_t p[ cells ];
   for( const Table & t : v_tables ) {
    gather( t , x , p );
    s += t.exact( p );
    }
   return( s );
   };
  const int a = add( q );
  if( ! f_reflect )
   return( a );
  std::uint8_t r[ cells ];
  reflection( q , r );
  return( std::max( a , add( r ) ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] int delta( const std::uint8_t * q , int t , int c ) const
  noexcept requires( Enc::relative ) {
  const int j = v_owner[ std::size_t( t ) ];
  if( j < 0 )
   return( 0 );
  const Table & tb = v_tables[ std::size_t( j ) ];
  std::uint8_t p[ cells ];
  gather( tb , q , p );
  const int before = tb.residue( p );
  p[ std::size_t( v_place[ std::size_t( t ) ] ) ] = std::uint8_t( c );
  constexpr int M = Enc::modulus;
  return( ( tb.residue( p ) - before + 1 + M ) % M - 1 );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 void reflection( const std::uint8_t * q , std::uint8_t * r ) const noexcept
 {
  for( int t = 0 ; t < cells ; ++t )
   r[ v_sigma[ t ] ] = v_transpose[ q[ t ] ];
  }
 
/*---------------------- METHODS FOR READING THE DATA ----------------------*/
 
 [[nodiscard]] const board_type & goal( void ) const noexcept {
  return( v_goal );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] bool reflected( void ) const noexcept { return( f_reflect ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const std::vector< Table > & tables( void ) const noexcept {
  return( v_tables );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] std::size_t bytes( void ) const noexcept {
  std::size_t b = 0;
  for( const Table & t : v_tables )
   b += t.bytes();
  return( b );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 // writes in p the placement of the tiles of t, from the cells q
 static void gather( const Table & t , const std::uint8_t * q ,
                     std::uint8_t * p ) noexcept {
  const auto & ts = t.pattern().tiles();
  for( std::size_t i = 0 ; i < ts.size() ; ++i )
   p[ i ] = q[ ts[ i ] ];
  }
 
 std::vector< Table > v_tables;                  
 board_type v_goal{};                            
 bool f_reflect = false;                         
 std::array< std::int8_t , cells > v_owner{};    
 std::array< std::int8_t , cells > v_place{};    
 std::array< std::uint8_t , cells > v_transpose{};  
 std::array< std::uint8_t , cells > v_sigma{};   
 
 };  // end( class( AdditivePDB ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------------- CLASS SlidingTilePDB --------------------------*/
/*--------------------------------------------------------------------------*/

 
template< int W , int H , class Enc = NibbleEntries >
class SlidingTilePDB : public SlidingTile< W , H > {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using Base = SlidingTile< W , H >;                  
 using PDB = AdditivePDB< W , H , Enc >;             
 using state_type = typename Base::state_type;       
 using cost_type = typename Base::cost_type;         
 using board_type = typename Base::board_type;       
 
 static constexpr int cells = Base::cells;           
 
/*------------------------------ CONSTRUCTOR -------------------------------*/
 
 SlidingTilePDB( const board_type & start , const PDB & pdb )
  : Base( start , pdb.goal() ) , f_pdb( pdb ) {
  if constexpr( Enc::relative )
   if( pdb.reflected() )
    throw( std::invalid_argument( "SlidingTilePDB::SlidingTilePDB: the "
                                  "residues need the sum without the "
                                  "reflection" ) );
  }
 
/*------------------------- METHODS OF THE DOMAIN --------------------------*/
 
 [[nodiscard]] cost_type heuristic( state_type s ) const {
  std::uint8_t q[ cells ];
  cells_of( s , q );
  if constexpr( Enc::relative )
   return( f_pdb.exact( q ) );
  else
   return( f_pdb.heuristic( q ) );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( state_type s , cost_type h , F && f ) const {
  std::uint8_t q[ cells ];
  cells_of( s , q );
  const int b = Base::blank( s );
  Base::for_each_successor( s , h , [ & ]( state_type t , cost_type c ,
                                           cost_type ) {
   f( t , c , child_h( q , h , t , b ) );
   } );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 template< class F >
 void for_each_successor( state_type s , cost_type h , std::uint8_t op ,
                          F && f ) const {
  std::uint8_t q[ cells ];
  cells_of( s , q );
  const int b = Base::blank( s );
  Base::for_each_successor( s , h , op , [ & ]( state_type t , cost_type c ,
                                                cost_type , std::uint8_t o ) {
   f( t , c , child_h( q , h , t , b ) , o );
   } );
  }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 [[nodiscard]] const PDB & pdb( void ) const noexcept { return( f_pdb ); }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 static void cells_of( state_type s , std::uint8_t * q ) noexcept {
  for( int c = 0 ; c < cells ; ++c )
   q[ Base::tile( s , c ) ] = std::uint8_t( c );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 // the heuristic of the successor t of the state of cells q and heuristic
 // h, the blank of which was in b: the tile in b moved there from the
 // blank of t
 cost_type child_h( std::uint8_t * q , cost_type h , state_type t , int b )
  const noexcept {
  const int x = Base::tile( t , b );
  if constexpr( Enc::relative )
   return( h + f_pdb.delta( q , x , b ) );
  else {
   const int from = q[ x ];
   q[ x ] = std::uint8_t( b );
   q[ 0 ] = std::uint8_t( from );
   const cost_type v = f_pdb.heuristic( q );
   q[ x ] = std::uint8_t( from );
   q[ 0 ] = std::uint8_t( b );
   return( v );
   }
  }
 
 const PDB & f_pdb;                              
 
 };  // end( class( SlidingTilePDB ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
[[nodiscard]] inline Partition partition_15_7_8( void ) {
 return( Partition{ { 1 , 2 , 3 , 4 , 5 , 6 , 7 } ,
                    { 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 } } );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
[[nodiscard]] inline Partition partition_15_5_5_5( void ) {
 return( Partition{ { 1 , 2 , 4 , 5 , 8 } , { 3 , 6 , 7 , 10 , 11 } ,
                    { 9 , 12 , 13 , 14 , 15 } } );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
[[nodiscard]] inline Partition partition_15_6_6_3( void ) {
 return( Partition{ { 1 , 2 , 4 , 5 , 8 , 9 } ,
                    { 3 , 6 , 7 , 10 , 11 , 15 } , { 12 , 13 , 14 } } );
 }
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
[[nodiscard]] inline Partition partition_24_6_6_6_6( void ) {
 return( Partition{ { 1 , 5 , 6 , 10 , 11 , 12 } ,
                    { 2 , 3 , 4 , 7 , 8 , 9 } ,
                    { 13 , 14 , 18 , 19 , 23 , 24 } ,
                    { 15 , 16 , 17 , 20 , 21 , 22 } } );
 }
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_PatternDatabase */
 
/*--------------------------------------------------------------------------*/
/*---------------------- End File PatternDatabase.h ------------------------*/
/*--------------------------------------------------------------------------*/