PBeFS
Parallel Best-First Search
Loading...
Searching...
No Matches
Domain.h
Go to the documentation of this file.
1/*--------------------------------------------------------------------------*/
2/*----------------------------- File Domain.h ------------------------------*/
3/*--------------------------------------------------------------------------*/
22/*--------------------------------------------------------------------------*/
23/*------------------------------ DEFINITIONS -------------------------------*/
24/*--------------------------------------------------------------------------*/
25
26#ifndef __PBeFS_Domain
27 #define __PBeFS_Domain
28 /* self-identification: #endif at the end of the file */
29
30/*--------------------------------------------------------------------------*/
31/*-------------------------------- INCLUDES --------------------------------*/
32/*--------------------------------------------------------------------------*/
33
34#include <concepts>
35
36#include <cstddef>
37
38#include <cstdint>
39
40#include <type_traits>
41
42#include <utility>
43
44#include "PBeFS/core/SearchUtils.h"
45
46/*--------------------------------------------------------------------------*/
47/*------------------------------- NAMESPACE --------------------------------*/
48/*--------------------------------------------------------------------------*/
49
51namespace PBeFS_di_unipi_it
52{
53
54/*--------------------------------------------------------------------------*/
55/*-------------------------------- CONCEPTS --------------------------------*/
56/*--------------------------------------------------------------------------*/
57
58namespace detail {
59
61 template< class State , class Cost >
62 struct successor_sink {
63 void operator()( const State & , Cost , Cost ) const noexcept {}
64 };
65
68 template< class State , class Cost >
69 struct op_sink {
70 void operator()( const State & , Cost , Cost , std::uint8_t ) const
71 noexcept {}
72 };
73
75 struct index_sink {
76 void operator()( std::size_t ) const noexcept {}
77 };
78
79 } // end( namespace detail )
80
81/*--------------------------------------------------------------------------*/
83
101
102template< class D >
103concept Domain = requires( const D & d , const typename D::state_type & s ,
104 typename D::cost_type h ) {
105 typename D::state_type;
106 typename D::cost_type;
107 requires std::is_arithmetic_v< typename D::cost_type >;
108 requires std::equality_comparable< typename D::state_type >;
109 requires std::copyable< typename D::state_type >;
110 { d.initial_state() } -> std::convertible_to< typename D::state_type >;
111 { d.is_goal( s ) } -> std::convertible_to< bool >;
112 { d.heuristic( s ) } -> std::convertible_to< typename D::cost_type >;
113 { d.hash( s ) } -> std::convertible_to< std::uint64_t >;
114 d.for_each_successor( s , h ,
115 detail::successor_sink< typename D::state_type ,
116 typename D::cost_type >{} );
117 };
118
119/*--------------------------------------------------------------------------*/
121
125
126template< class D >
127concept FeatureDomain = Domain< D > &&
128 requires( const D & d , const typename D::state_type & s ) {
129 { d.num_features() } -> std::convertible_to< std::size_t >;
130 d.for_each_feature( s , detail::index_sink{} );
131 };
132
133/*--------------------------------------------------------------------------*/
135
141
142template< class D >
143concept IncrementalFeatureDomain = FeatureDomain< D > &&
144 requires( const D & d , const typename D::state_type & s ) {
145 d.for_each_feature_change( s , s , detail::index_sink{} );
146 };
147
148/*--------------------------------------------------------------------------*/
150
153
154template< class D >
155concept AbstractFeatureDomain = FeatureDomain< D > &&
156 requires( const D & d , std::size_t i ) {
157 { d.num_abstract_features() } -> std::convertible_to< std::size_t >;
158 { d.abstract_feature( i ) } -> std::convertible_to< std::size_t >;
159 };
160
161/*--------------------------------------------------------------------------*/
163
166
167template< class D >
168concept AbstractStateDomain = Domain< D > &&
169 requires( const D & d , const typename D::state_type & s ) {
170 { d.abstract_state( s ) } -> std::convertible_to< std::uint64_t >;
171 };
172
173/*--------------------------------------------------------------------------*/
175
180
181template< class D >
182concept NBlockDomain = Domain< D > &&
183 requires( const D & d , const typename D::state_type & s , std::size_t b ) {
184 { d.num_nblocks() } -> std::convertible_to< std::size_t >;
185 { d.nblock( s ) } -> std::convertible_to< std::size_t >;
186 d.for_each_nblock_successor( b , detail::index_sink{} );
187 };
188
189/*--------------------------------------------------------------------------*/
191
194
195template< class D >
196concept PairwiseDomain = Domain< D > &&
197 requires( const D & d , const typename D::state_type & s ) {
198 { d.pairwise_heuristic( s , s ) }
199 -> std::convertible_to< typename D::cost_type >;
200 };
201
202/*--------------------------------------------------------------------------*/
204
205inline constexpr std::uint8_t no_op = 0xFF;
206
207/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
209
215
216template< class D >
217concept OperatorDomain = Domain< D > &&
218 requires( const D & d , const typename D::state_type & s ,
219 typename D::cost_type h , std::uint8_t op ) {
220 d.for_each_successor( s , h , op , detail::op_sink<
221 typename D::state_type , typename D::cost_type >{} );
222 };
223
224/*--------------------------------------------------------------------------*/
226
228
229template< class D >
230concept PerfectHashDomain = Domain< D > &&
231 requires( const D & d , const typename D::state_type & s ) {
232 { d.perfect_hash( s ) } -> std::convertible_to< std::uint64_t >;
233 };
234
235/*--------------------------------------------------------------------------*/
236/*--------------------------------- TYPES ----------------------------------*/
237/*--------------------------------------------------------------------------*/
238
240template< Domain D >
241using state_t = typename D::state_type;
242
244template< Domain D >
245using cost_t = typename D::cost_type;
246
251
252template< class D >
253struct OperatorOf {
254 std::uint8_t op = no_op;
255 constexpr OperatorOf( void ) = default;
256 constexpr OperatorOf( std::uint8_t o ) : op( o ) {}
257 };
258
259template< class D > requires( ! OperatorDomain< D > )
260struct OperatorOf< D > {
261 static constexpr std::uint8_t op = no_op;
262 constexpr OperatorOf( void ) = default;
263 constexpr OperatorOf( std::uint8_t ) {}
264 };
265
266/*--------------------------------------------------------------------------*/
267/*------------------------------- FUNCTIONS --------------------------------*/
268/*--------------------------------------------------------------------------*/
270
274
275template< Domain D , class F >
276void for_each_child( const D & d , const state_t< D > & s , cost_t< D > h ,
277 std::uint8_t op , F && f ) {
278 if constexpr( OperatorDomain< D > )
279 d.for_each_successor( s , h , op , std::forward< F >( f ) );
280 else
281 d.for_each_successor( s , h , [ & ]( const state_t< D > & t , cost_t< D > c ,
282 cost_t< D > ht ) {
283 f( t , c , ht , no_op );
284 } );
285 }
286
287/*--------------------------------------------------------------------------*/
288
289} // end( namespace PBeFS_di_unipi_it )
290
291/*--------------------------------------------------------------------------*/
292
293#endif /* __PBeFS_Domain */
294
295/*--------------------------------------------------------------------------*/
296/*--------------------------- End File Domain.h ----------------------------*/
297/*--------------------------------------------------------------------------*/
SearchUtils.h
Header file for the small helpers shared by the searches: a stopwatch, the placement of the workers o...
PBeFS_di_unipi_it::AbstractFeatureDomain
a FeatureDomain that also provides a feature projection
Definition Domain.h:155
PBeFS_di_unipi_it::AbstractStateDomain
a Domain with a state abstraction
Definition Domain.h:168
PBeFS_di_unipi_it::Domain
a search domain
Definition Domain.h:103
PBeFS_di_unipi_it::FeatureDomain
a Domain whose states are described by a set of features
Definition Domain.h:127
PBeFS_di_unipi_it::IncrementalFeatureDomain
a FeatureDomain that also gives the features changed by a move
Definition Domain.h:143
PBeFS_di_unipi_it::NBlockDomain
a Domain whose state space is partitioned into nblocks
Definition Domain.h:182
PBeFS_di_unipi_it::OperatorDomain
a Domain that knows the operator by which a state was generated
Definition Domain.h:217
PBeFS_di_unipi_it::PairwiseDomain
a Domain with a heuristic between any two states
Definition Domain.h:196
PBeFS_di_unipi_it::PerfectHashDomain
a Domain with a perfect hash of its states
Definition Domain.h:230
PBeFS_di_unipi_it
namespace for the Parallel Best-First Search library
Definition AStar.h:83
PBeFS_di_unipi_it::for_each_child
void for_each_child(const D &d, const state_t< D > &s, cost_t< D > h, std::uint8_t op, F &&f)
the successors of s but its parent, when D knows the operators
Definition Domain.h:276
PBeFS_di_unipi_it::cost_t
typename D::cost_type cost_t
the cost type of a Domain
Definition Domain.h:245
PBeFS_di_unipi_it::state_t
typename D::state_type state_t
the state type of a Domain
Definition Domain.h:241
PBeFS_di_unipi_it::no_op
constexpr std::uint8_t no_op
the operator of the root, which no state was generated by
Definition Domain.h:205
PBeFS_di_unipi_it::OperatorOf< D >::op
static constexpr std::uint8_t op
no operator
Definition Domain.h:261
PBeFS_di_unipi_it::OperatorOf< D >::OperatorOf
constexpr OperatorOf(std::uint8_t)
Definition Domain.h:263
PBeFS_di_unipi_it::OperatorOf< D >::OperatorOf
constexpr OperatorOf(void)=default
PBeFS_di_unipi_it::OperatorOf::op
std::uint8_t op
the operator
Definition Domain.h:254
PBeFS_di_unipi_it::OperatorOf::OperatorOf
constexpr OperatorOf(std::uint8_t o)
Definition Domain.h:256
PBeFS_di_unipi_it::OperatorOf::OperatorOf
constexpr OperatorOf(void)=default