1use std::fmt::{self, Debug};
2use std::hash::Hash;
3
4use solverforge_config::{ConstructionHeuristicConfig, ConstructionHeuristicType};
5use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
6
7use crate::descriptor_standard::{
8 build_descriptor_construction, standard_target_matches, standard_work_remaining,
9};
10use crate::list_solver::build_list_construction;
11use crate::phase::Phase;
12use crate::scope::{ProgressCallback, SolverScope};
13
14pub struct UnifiedConstruction<S, V>
15where
16 S: PlanningSolution,
17 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + 'static,
18{
19 config: Option<ConstructionHeuristicConfig>,
20 descriptor: SolutionDescriptor,
21 list_construction: Option<ListConstructionArgs<S, V>>,
22 list_variable_name: Option<&'static str>,
23}
24
25impl<S, V> UnifiedConstruction<S, V>
26where
27 S: PlanningSolution,
28 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + 'static,
29{
30 pub(super) fn new(
31 config: Option<ConstructionHeuristicConfig>,
32 descriptor: SolutionDescriptor,
33 list_construction: Option<ListConstructionArgs<S, V>>,
34 list_variable_name: Option<&'static str>,
35 ) -> Self {
36 Self {
37 config,
38 descriptor,
39 list_construction,
40 list_variable_name,
41 }
42 }
43}
44
45impl<S, V> Debug for UnifiedConstruction<S, V>
46where
47 S: PlanningSolution,
48 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
49{
50 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51 f.debug_struct("UnifiedConstruction")
52 .field("config", &self.config)
53 .field("has_list_construction", &self.list_construction.is_some())
54 .field("list_variable_name", &self.list_variable_name)
55 .finish()
56 }
57}
58
59impl<S, V, D, ProgressCb> Phase<S, D, ProgressCb> for UnifiedConstruction<S, V>
60where
61 S: PlanningSolution + 'static,
62 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
63 D: solverforge_scoring::Director<S>,
64 ProgressCb: ProgressCallback<S>,
65{
66 fn solve(&mut self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
67 let config = self.config.as_ref();
68 let explicit_target = config.is_some_and(has_explicit_target);
69 let entity_class = config.and_then(|cfg| cfg.target.entity_class.as_deref());
70 let variable_name = config.and_then(|cfg| cfg.target.variable_name.as_deref());
71 let standard_matches = config.is_some_and(|_| {
72 standard_target_matches(&self.descriptor, entity_class, variable_name)
73 });
74 let list_matches = config.is_some_and(|cfg| {
75 list_target_matches(
76 cfg,
77 &self.descriptor,
78 self.list_construction.as_ref(),
79 self.list_variable_name,
80 )
81 });
82
83 if let Some(cfg) = config {
84 if explicit_target && !standard_matches && !list_matches {
85 panic!(
86 "construction heuristic matched no planning variables for entity_class={:?} variable_name={:?}",
87 cfg.target.entity_class,
88 cfg.target.variable_name
89 );
90 }
91
92 let heuristic = cfg.construction_heuristic_type;
93 if is_list_only_heuristic(heuristic) {
94 assert!(
95 self.list_construction.is_some(),
96 "list construction heuristic {:?} configured against a solution with no planning list variable",
97 heuristic
98 );
99 assert!(
100 !explicit_target || list_matches,
101 "list construction heuristic {:?} does not match the targeted planning list variable for entity_class={:?} variable_name={:?}",
102 heuristic,
103 cfg.target.entity_class,
104 cfg.target.variable_name
105 );
106 self.solve_list(solver_scope);
107 return;
108 }
109
110 if is_standard_only_heuristic(heuristic) {
111 assert!(
112 !explicit_target || standard_matches,
113 "standard construction heuristic {:?} does not match targeted standard planning variables for entity_class={:?} variable_name={:?}",
114 heuristic,
115 cfg.target.entity_class,
116 cfg.target.variable_name
117 );
118 build_descriptor_construction(Some(cfg), &self.descriptor).solve(solver_scope);
119 return;
120 }
121 }
122
123 if self.list_construction.is_none() {
124 build_descriptor_construction(config, &self.descriptor).solve(solver_scope);
125 return;
126 }
127
128 let standard_remaining = standard_work_remaining(
129 &self.descriptor,
130 if explicit_target { entity_class } else { None },
131 if explicit_target { variable_name } else { None },
132 solver_scope.working_solution(),
133 );
134 let list_remaining = self
135 .list_construction
136 .as_ref()
137 .map(|args| {
138 (!explicit_target || list_matches)
139 && list_work_remaining(args, solver_scope.working_solution())
140 })
141 .unwrap_or(false);
142
143 if standard_remaining {
144 build_descriptor_construction(config, &self.descriptor).solve(solver_scope);
145 }
146 if list_remaining {
147 self.solve_list(solver_scope);
148 }
149 }
150
151 fn phase_type_name(&self) -> &'static str {
152 "UnifiedConstruction"
153 }
154}
155
156impl<S, V> UnifiedConstruction<S, V>
157where
158 S: PlanningSolution + 'static,
159 V: Copy + PartialEq + Eq + Hash + Into<usize> + Send + Sync + Debug + 'static,
160{
161 fn solve_list<D, ProgressCb>(&self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>)
162 where
163 D: solverforge_scoring::Director<S>,
164 ProgressCb: ProgressCallback<S>,
165 {
166 let Some(args) = self.list_construction.as_ref() else {
167 panic!("list construction configured against a standard-variable context");
168 };
169 let normalized = normalize_list_construction_config(self.config.as_ref());
170 build_list_construction(
171 normalized.as_ref(),
172 args.element_count,
173 args.assigned_elements,
174 args.entity_count,
175 args.list_len,
176 args.list_insert,
177 args.list_remove,
178 args.index_to_element,
179 args.descriptor_index,
180 args.depot_fn,
181 args.distance_fn,
182 args.element_load_fn,
183 args.capacity_fn,
184 args.assign_route_fn,
185 args.merge_feasible_fn,
186 args.k_opt_get_route,
187 args.k_opt_set_route,
188 args.k_opt_depot_fn,
189 args.k_opt_distance_fn,
190 args.k_opt_feasible_fn,
191 )
192 .solve(solver_scope);
193 }
194}
195
196pub struct ListConstructionArgs<S, V> {
197 pub element_count: fn(&S) -> usize,
198 pub assigned_elements: fn(&S) -> Vec<V>,
199 pub entity_count: fn(&S) -> usize,
200 pub list_len: fn(&S, usize) -> usize,
201 pub list_insert: fn(&mut S, usize, usize, V),
202 pub list_remove: fn(&mut S, usize, usize) -> V,
203 pub index_to_element: fn(&S, usize) -> V,
204 pub descriptor_index: usize,
205 pub depot_fn: Option<fn(&S) -> usize>,
206 pub distance_fn: Option<fn(&S, usize, usize) -> i64>,
207 pub element_load_fn: Option<fn(&S, usize) -> i64>,
208 pub capacity_fn: Option<fn(&S) -> i64>,
209 pub assign_route_fn: Option<fn(&mut S, usize, Vec<V>)>,
210 pub merge_feasible_fn: Option<fn(&S, &[usize]) -> bool>,
211 pub k_opt_get_route: Option<fn(&S, usize) -> Vec<usize>>,
212 pub k_opt_set_route: Option<fn(&mut S, usize, Vec<usize>)>,
213 pub k_opt_depot_fn: Option<fn(&S, usize) -> usize>,
214 pub k_opt_distance_fn: Option<fn(&S, usize, usize) -> i64>,
215 pub k_opt_feasible_fn: Option<fn(&S, usize, &[usize]) -> bool>,
216}
217
218impl<S, V> Clone for ListConstructionArgs<S, V> {
219 fn clone(&self) -> Self {
220 *self
221 }
222}
223
224impl<S, V> Copy for ListConstructionArgs<S, V> {}
225
226pub(super) fn list_work_remaining<S, V>(args: &ListConstructionArgs<S, V>, solution: &S) -> bool
227where
228 S: PlanningSolution,
229 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
230{
231 (args.assigned_elements)(solution).len() < (args.element_count)(solution)
232}
233
234pub(super) fn has_explicit_target(config: &ConstructionHeuristicConfig) -> bool {
235 config.target.variable_name.is_some() || config.target.entity_class.is_some()
236}
237
238pub(super) fn is_list_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
239 matches!(
240 heuristic,
241 ConstructionHeuristicType::ListRoundRobin
242 | ConstructionHeuristicType::ListCheapestInsertion
243 | ConstructionHeuristicType::ListRegretInsertion
244 | ConstructionHeuristicType::ListClarkeWright
245 | ConstructionHeuristicType::ListKOpt
246 )
247}
248
249pub(super) fn is_standard_only_heuristic(heuristic: ConstructionHeuristicType) -> bool {
250 matches!(
251 heuristic,
252 ConstructionHeuristicType::FirstFitDecreasing
253 | ConstructionHeuristicType::WeakestFit
254 | ConstructionHeuristicType::WeakestFitDecreasing
255 | ConstructionHeuristicType::StrongestFit
256 | ConstructionHeuristicType::StrongestFitDecreasing
257 | ConstructionHeuristicType::AllocateEntityFromQueue
258 | ConstructionHeuristicType::AllocateToValueFromQueue
259 )
260}
261
262pub(super) fn list_target_matches<S, V>(
263 config: &ConstructionHeuristicConfig,
264 descriptor: &SolutionDescriptor,
265 list_construction: Option<&ListConstructionArgs<S, V>>,
266 list_variable_name: Option<&'static str>,
267) -> bool
268where
269 S: PlanningSolution,
270 V: Copy + PartialEq + Eq + Hash + Send + Sync + 'static,
271{
272 if !has_explicit_target(config) {
273 return false;
274 }
275
276 let Some(list_variable_name) = list_variable_name else {
277 return false;
278 };
279 let Some(list_construction) = list_construction else {
280 return false;
281 };
282 let Some(list_entity_name) = descriptor
283 .entity_descriptors
284 .get(list_construction.descriptor_index)
285 .map(|entity| entity.type_name)
286 else {
287 return false;
288 };
289
290 config
291 .target
292 .variable_name
293 .as_deref()
294 .is_none_or(|name| name == list_variable_name)
295 && config
296 .target
297 .entity_class
298 .as_deref()
299 .is_none_or(|name| name == list_entity_name)
300}
301
302pub(super) fn normalize_list_construction_config(
303 config: Option<&ConstructionHeuristicConfig>,
304) -> Option<ConstructionHeuristicConfig> {
305 let mut config = config.cloned()?;
306 config.construction_heuristic_type = match config.construction_heuristic_type {
307 ConstructionHeuristicType::FirstFit | ConstructionHeuristicType::CheapestInsertion => {
308 ConstructionHeuristicType::ListCheapestInsertion
309 }
310 other => other,
311 };
312 Some(config)
313}