1use std::fmt::{self, Debug};
2use std::hash::Hash;
3
4use solverforge_config::{PhaseConfig, SolverConfig};
5use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
6use solverforge_core::score::{ParseableScore, Score};
7
8use crate::heuristic::r#move::Move;
9use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
10use crate::heuristic::MoveSelector;
11use crate::phase::localsearch::{Acceptor, LocalSearchForager, LocalSearchPhase};
12use crate::phase::{Phase, PhaseSequence};
13use crate::runtime::{build_phases, Construction, RuntimePhase};
14use crate::scope::{ProgressCallback, SolverScope};
15
16use super::{LocalSearchStrategy, RuntimeModel};
17
18mod custom;
19pub(crate) mod defaults;
20
21pub use custom::{
22 CustomPhaseNode, CustomSearchPhase, NoCustomPhase, NoCustomPhases, PartitionedPhaseNode,
23};
24
25pub struct SearchContext<
26 S,
27 V = usize,
28 DM = crate::heuristic::selector::DefaultCrossEntityDistanceMeter,
29 IDM = crate::heuristic::selector::DefaultCrossEntityDistanceMeter,
30> where
31 S: PlanningSolution,
32{
33 descriptor: SolutionDescriptor,
34 model: RuntimeModel<S, V, DM, IDM>,
35 random_seed: Option<u64>,
36}
37
38impl<S, V, DM, IDM> SearchContext<S, V, DM, IDM>
39where
40 S: PlanningSolution,
41{
42 pub fn new(
43 descriptor: SolutionDescriptor,
44 model: RuntimeModel<S, V, DM, IDM>,
45 random_seed: Option<u64>,
46 ) -> Self {
47 let model = model
48 .resolve_dynamic_descriptor_indexes(&descriptor)
49 .unwrap_or_else(|message| panic!("{message}"));
50 Self {
51 descriptor,
52 model,
53 random_seed,
54 }
55 }
56
57 pub fn descriptor(&self) -> &SolutionDescriptor {
58 &self.descriptor
59 }
60
61 pub fn model(&self) -> &RuntimeModel<S, V, DM, IDM> {
62 &self.model
63 }
64
65 pub fn seed(&self) -> Option<u64> {
66 self.random_seed
67 }
68
69 pub fn defaults(self) -> SearchBuilder<S, V, DM, IDM, NoCustomPhases> {
70 SearchBuilder {
71 context: self,
72 custom_phases: NoCustomPhases,
73 }
74 }
75}
76
77pub trait Search<
78 S,
79 V = usize,
80 DM = crate::heuristic::selector::DefaultCrossEntityDistanceMeter,
81 IDM = crate::heuristic::selector::DefaultCrossEntityDistanceMeter,
82> where
83 S: PlanningSolution + 'static,
84 S::Score: Score + ParseableScore,
85 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
86 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
87 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
88{
89 type Phase<D, ProgressCb>: Phase<S, D, ProgressCb> + Debug + Send
90 where
91 D: solverforge_scoring::Director<S>,
92 ProgressCb: ProgressCallback<S>;
93
94 fn build<D, ProgressCb>(
95 self,
96 config: &SolverConfig,
97 ) -> PhaseSequence<Self::Phase<D, ProgressCb>>
98 where
99 D: solverforge_scoring::Director<S>,
100 ProgressCb: ProgressCallback<S>;
101}
102
103pub struct SearchBuilder<S, V, DM, IDM, CustomPhases>
104where
105 S: PlanningSolution,
106{
107 context: SearchContext<S, V, DM, IDM>,
108 custom_phases: CustomPhases,
109}
110
111impl<S, V, DM, IDM, CustomPhases> SearchBuilder<S, V, DM, IDM, CustomPhases>
112where
113 S: PlanningSolution + 'static,
114 S::Score: Score + ParseableScore,
115 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
116 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
117 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
118 CustomPhases: custom::CustomPhaseRegistry<S, V, DM, IDM>,
119{
120 pub fn phase<P, F>(
121 self,
122 name: &'static str,
123 builder: F,
124 ) -> SearchBuilder<S, V, DM, IDM, CustomPhaseNode<CustomPhases, F, P>>
125 where
126 F: Fn(&SearchContext<S, V, DM, IDM>) -> P + Send + Sync + 'static,
127 P: CustomSearchPhase<S> + 'static,
128 {
129 assert!(
130 !self.custom_phases.contains(name) && !self.custom_phases.contains_partitioned(name),
131 "custom phase `{name}` was registered more than once",
132 );
133 SearchBuilder {
134 context: self.context,
135 custom_phases: CustomPhaseNode::new(self.custom_phases, name, builder),
136 }
137 }
138
139 pub fn partitioned_phase<P, F>(
140 self,
141 name: &'static str,
142 builder: F,
143 ) -> SearchBuilder<S, V, DM, IDM, PartitionedPhaseNode<CustomPhases, F, P>>
144 where
145 F: Fn(&SearchContext<S, V, DM, IDM>, &solverforge_config::PartitionedSearchConfig) -> P
146 + Send
147 + Sync
148 + 'static,
149 P: CustomSearchPhase<S> + 'static,
150 {
151 assert!(
152 !self.custom_phases.contains(name) && !self.custom_phases.contains_partitioned(name),
153 "partitioned_search partitioner `{name}` was registered more than once",
154 );
155 SearchBuilder {
156 context: self.context,
157 custom_phases: PartitionedPhaseNode::new(self.custom_phases, name, builder),
158 }
159 }
160}
161
162impl<S, V, DM, IDM, CustomPhases> Search<S, V, DM, IDM>
163 for SearchBuilder<S, V, DM, IDM, CustomPhases>
164where
165 S: PlanningSolution + 'static,
166 S::Score: Score + ParseableScore,
167 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
168 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
169 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
170 CustomPhases: custom::CustomPhaseRegistry<S, V, DM, IDM>,
171{
172 type Phase<D, ProgressCb>
173 = SearchRuntimePhase<
174 RuntimePhase<Construction<S, V, DM, IDM>, LocalSearchStrategy<S, V, DM, IDM>>,
175 CustomPhases::Phase,
176 >
177 where
178 D: solverforge_scoring::Director<S>,
179 ProgressCb: ProgressCallback<S>;
180
181 fn build<D, ProgressCb>(
182 self,
183 config: &SolverConfig,
184 ) -> PhaseSequence<Self::Phase<D, ProgressCb>>
185 where
186 D: solverforge_scoring::Director<S>,
187 ProgressCb: ProgressCallback<S>,
188 {
189 let mut phases = Vec::new();
190 if config.phases.is_empty() {
191 for phase in
192 build_phases(config, &self.context.descriptor, &self.context.model).into_phases()
193 {
194 phases.push(SearchRuntimePhase::Builtin(phase));
195 }
196 return PhaseSequence::new(phases);
197 }
198
199 for phase in &config.phases {
200 match phase {
201 PhaseConfig::Custom(custom) => {
202 let phase = self
203 .custom_phases
204 .build_named(&custom.name, &self.context)
205 .unwrap_or_else(|| {
206 panic!(
207 "custom phase `{}` was not registered by the solution search function",
208 custom.name
209 )
210 });
211 phases.push(SearchRuntimePhase::Custom(phase));
212 }
213 PhaseConfig::PartitionedSearch(partitioned) => {
214 let name = partitioned.partitioner.as_deref().unwrap_or_else(|| {
215 panic!("partitioned_search requires a `partitioner` name")
216 });
217 let phase = self
218 .custom_phases
219 .build_partitioned_named(name, partitioned, &self.context)
220 .unwrap_or_else(|| {
221 panic!(
222 "partitioned_search partitioner `{name}` was not registered by the solution search function"
223 )
224 });
225 phases.push(SearchRuntimePhase::Custom(phase));
226 }
227 PhaseConfig::ConstructionHeuristic(_) | PhaseConfig::LocalSearch(_) => {
228 let mut single = config.clone();
229 single.phases = vec![phase.clone()];
230 let mut built =
231 build_phases(&single, &self.context.descriptor, &self.context.model)
232 .into_phases();
233 assert_eq!(
234 built.len(),
235 1,
236 "built-in phase expansion must produce one phase"
237 );
238 phases.push(SearchRuntimePhase::Builtin(built.remove(0)));
239 }
240 }
241 }
242 PhaseSequence::new(phases)
243 }
244}
245
246pub enum SearchRuntimePhase<Builtin, Custom> {
247 Builtin(Builtin),
248 Custom(Custom),
249}
250
251impl<Builtin: Debug, Custom: Debug> Debug for SearchRuntimePhase<Builtin, Custom> {
252 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
253 match self {
254 Self::Builtin(phase) => f
255 .debug_tuple("SearchRuntimePhase::Builtin")
256 .field(phase)
257 .finish(),
258 Self::Custom(phase) => f
259 .debug_tuple("SearchRuntimePhase::Custom")
260 .field(phase)
261 .finish(),
262 }
263 }
264}
265
266impl<S, D, ProgressCb, Builtin, Custom> Phase<S, D, ProgressCb>
267 for SearchRuntimePhase<Builtin, Custom>
268where
269 S: PlanningSolution,
270 D: solverforge_scoring::Director<S>,
271 ProgressCb: ProgressCallback<S>,
272 Builtin: Phase<S, D, ProgressCb>,
273 Custom: CustomSearchPhase<S>,
274{
275 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
276 match self {
277 Self::Builtin(phase) => phase.solve(solver_scope),
278 Self::Custom(phase) => CustomSearchPhase::solve(phase, solver_scope),
279 }
280 }
281
282 fn phase_type_name(&self) -> &'static str {
283 "SearchRuntimePhase"
284 }
285}
286
287pub fn build_search<S, V, DM, IDM, D, ProgressCb, T>(
288 search: T,
289 config: &SolverConfig,
290) -> PhaseSequence<T::Phase<D, ProgressCb>>
291where
292 S: PlanningSolution + 'static,
293 S::Score: Score + ParseableScore,
294 V: Clone + Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
295 DM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
296 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + Send + 'static,
297 D: solverforge_scoring::Director<S>,
298 ProgressCb: ProgressCallback<S>,
299 T: Search<S, V, DM, IDM>,
300 T::Phase<D, ProgressCb>: Phase<S, D, ProgressCb>,
301{
302 search.build::<D, ProgressCb>(config)
303}
304
305pub fn local_search<S, M, MS, A, Fo>(
306 move_selector: MS,
307 acceptor: A,
308 forager: Fo,
309) -> LocalSearchPhase<S, M, MS, A, Fo>
310where
311 S: PlanningSolution,
312 M: Move<S> + 'static,
313 MS: MoveSelector<S, M>,
314 A: Acceptor<S>,
315 Fo: LocalSearchForager<S, M>,
316{
317 LocalSearchPhase::new(move_selector, acceptor, forager, None)
318}
319
320#[cfg(test)]
321mod tests;