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