solverforge_solver/descriptor_standard/
selectors.rs1use std::any::Any;
2use std::fmt::{self, Debug};
3use std::marker::PhantomData;
4
5use solverforge_config::MoveSelectorConfig;
6use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
7use solverforge_scoring::Director;
8
9use crate::heuristic::selector::decorator::VecUnionSelector;
10use crate::heuristic::selector::move_selector::MoveSelector;
11
12use super::bindings::{collect_bindings, find_binding, VariableBinding};
13use super::move_types::{DescriptorChangeMove, DescriptorEitherMove, DescriptorSwapMove};
14
15#[derive(Clone)]
16pub struct DescriptorChangeMoveSelector<S> {
17 binding: VariableBinding,
18 solution_descriptor: SolutionDescriptor,
19 allows_unassigned: bool,
20 _phantom: PhantomData<fn() -> S>,
21}
22
23impl<S> Debug for DescriptorChangeMoveSelector<S> {
24 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
25 f.debug_struct("DescriptorChangeMoveSelector")
26 .field("binding", &self.binding)
27 .finish()
28 }
29}
30
31impl<S> DescriptorChangeMoveSelector<S> {
32 fn new(binding: VariableBinding, solution_descriptor: SolutionDescriptor) -> Self {
33 let allows_unassigned = binding.allows_unassigned;
34 Self {
35 binding,
36 solution_descriptor,
37 allows_unassigned,
38 _phantom: PhantomData,
39 }
40 }
41}
42
43impl<S> MoveSelector<S, DescriptorEitherMove<S>> for DescriptorChangeMoveSelector<S>
44where
45 S: PlanningSolution + 'static,
46{
47 fn open_cursor<'a, D: Director<S>>(
48 &'a self,
49 score_director: &D,
50 ) -> impl Iterator<Item = DescriptorEitherMove<S>> + 'a {
51 let count = score_director
52 .entity_count(self.binding.descriptor_index)
53 .unwrap_or(0);
54 let descriptor = self.solution_descriptor.clone();
55 let binding = self.binding.clone();
56 let allows_unassigned = self.allows_unassigned;
57 let solution = score_director.working_solution() as &dyn Any;
58 let moves: Vec<_> = (0..count)
59 .flat_map(move |entity_index| {
60 let entity = descriptor
61 .get_entity(solution, binding.descriptor_index, entity_index)
62 .expect("entity lookup failed for change selector");
63 let current_value = (binding.getter)(entity);
64 let unassign_move = (allows_unassigned && current_value.is_some()).then({
65 let binding = binding.clone();
66 let descriptor = descriptor.clone();
67 move || {
68 DescriptorEitherMove::Change(DescriptorChangeMove::new(
69 binding.clone(),
70 entity_index,
71 None,
72 descriptor.clone(),
73 ))
74 }
75 });
76 binding
77 .values_for_entity(&descriptor, solution, entity)
78 .into_iter()
79 .map({
80 let binding = binding.clone();
81 let descriptor = descriptor.clone();
82 move |value| {
83 DescriptorEitherMove::Change(DescriptorChangeMove::new(
84 binding.clone(),
85 entity_index,
86 Some(value),
87 descriptor.clone(),
88 ))
89 }
90 })
91 .chain(unassign_move)
92 })
93 .collect();
94 moves.into_iter()
95 }
96
97 fn size<D: Director<S>>(&self, score_director: &D) -> usize {
98 let count = score_director
99 .entity_count(self.binding.descriptor_index)
100 .unwrap_or(0);
101 let mut total = 0;
102 for entity_index in 0..count {
103 let entity = self
104 .solution_descriptor
105 .get_entity(
106 score_director.working_solution() as &dyn Any,
107 self.binding.descriptor_index,
108 entity_index,
109 )
110 .expect("entity lookup failed for change selector");
111 total += self
112 .binding
113 .values_for_entity(
114 &self.solution_descriptor,
115 score_director.working_solution() as &dyn Any,
116 entity,
117 )
118 .len()
119 + usize::from(self.allows_unassigned && (self.binding.getter)(entity).is_some());
120 }
121 total
122 }
123}
124
125#[derive(Clone)]
126pub struct DescriptorSwapMoveSelector<S> {
127 binding: VariableBinding,
128 solution_descriptor: SolutionDescriptor,
129 _phantom: PhantomData<fn() -> S>,
130}
131
132impl<S> Debug for DescriptorSwapMoveSelector<S> {
133 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134 f.debug_struct("DescriptorSwapMoveSelector")
135 .field("binding", &self.binding)
136 .finish()
137 }
138}
139
140impl<S> DescriptorSwapMoveSelector<S> {
141 fn new(binding: VariableBinding, solution_descriptor: SolutionDescriptor) -> Self {
142 Self {
143 binding,
144 solution_descriptor,
145 _phantom: PhantomData,
146 }
147 }
148}
149
150impl<S> MoveSelector<S, DescriptorEitherMove<S>> for DescriptorSwapMoveSelector<S>
151where
152 S: PlanningSolution + 'static,
153{
154 fn open_cursor<'a, D: Director<S>>(
155 &'a self,
156 score_director: &D,
157 ) -> impl Iterator<Item = DescriptorEitherMove<S>> + 'a {
158 let count = score_director
159 .entity_count(self.binding.descriptor_index)
160 .unwrap_or(0);
161 let binding = self.binding.clone();
162 let descriptor = self.solution_descriptor.clone();
163 let moves: Vec<_> = (0..count)
164 .flat_map(move |left_entity_index| {
165 ((left_entity_index + 1)..count).map({
166 let binding = binding.clone();
167 let descriptor = descriptor.clone();
168 move |right_entity_index| {
169 DescriptorEitherMove::Swap(DescriptorSwapMove::new(
170 binding.clone(),
171 left_entity_index,
172 right_entity_index,
173 descriptor.clone(),
174 ))
175 }
176 })
177 })
178 .collect();
179 moves.into_iter()
180 }
181
182 fn size<D: Director<S>>(&self, score_director: &D) -> usize {
183 let count = score_director
184 .entity_count(self.binding.descriptor_index)
185 .unwrap_or(0);
186 count.saturating_mul(count.saturating_sub(1)) / 2
187 }
188}
189
190#[derive(Clone)]
191pub enum DescriptorLeafSelector<S> {
192 Change(DescriptorChangeMoveSelector<S>),
193 Swap(DescriptorSwapMoveSelector<S>),
194}
195
196impl<S> Debug for DescriptorLeafSelector<S>
197where
198 S: PlanningSolution,
199{
200 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
201 match self {
202 Self::Change(selector) => selector.fmt(f),
203 Self::Swap(selector) => selector.fmt(f),
204 }
205 }
206}
207
208impl<S> MoveSelector<S, DescriptorEitherMove<S>> for DescriptorLeafSelector<S>
209where
210 S: PlanningSolution + 'static,
211{
212 fn open_cursor<'a, D: Director<S>>(
213 &'a self,
214 score_director: &D,
215 ) -> impl Iterator<Item = DescriptorEitherMove<S>> + 'a {
216 enum DescriptorLeafIter<A, B> {
217 Change(A),
218 Swap(B),
219 }
220
221 impl<T, A, B> Iterator for DescriptorLeafIter<A, B>
222 where
223 A: Iterator<Item = T>,
224 B: Iterator<Item = T>,
225 {
226 type Item = T;
227
228 fn next(&mut self) -> Option<Self::Item> {
229 match self {
230 Self::Change(iter) => iter.next(),
231 Self::Swap(iter) => iter.next(),
232 }
233 }
234 }
235
236 match self {
237 Self::Change(selector) => {
238 DescriptorLeafIter::Change(selector.open_cursor(score_director))
239 }
240 Self::Swap(selector) => DescriptorLeafIter::Swap(selector.open_cursor(score_director)),
241 }
242 }
243
244 fn size<D: Director<S>>(&self, score_director: &D) -> usize {
245 match self {
246 Self::Change(selector) => selector.size(score_director),
247 Self::Swap(selector) => selector.size(score_director),
248 }
249 }
250}
251
252fn collect_descriptor_leaf_selectors<S>(
253 config: Option<&MoveSelectorConfig>,
254 descriptor: &SolutionDescriptor,
255) -> Vec<DescriptorLeafSelector<S>>
256where
257 S: PlanningSolution + 'static,
258{
259 let bindings = collect_bindings(descriptor);
260 let mut leaves = Vec::new();
261
262 fn collect<S>(
263 cfg: &MoveSelectorConfig,
264 descriptor: &SolutionDescriptor,
265 bindings: &[VariableBinding],
266 leaves: &mut Vec<DescriptorLeafSelector<S>>,
267 ) where
268 S: PlanningSolution + 'static,
269 {
270 match cfg {
271 MoveSelectorConfig::ChangeMoveSelector(change) => {
272 let matched = find_binding(
273 bindings,
274 change.target.entity_class.as_deref(),
275 change.target.variable_name.as_deref(),
276 );
277 assert!(
278 !matched.is_empty(),
279 "change_move selector matched no standard planning variables for entity_class={:?} variable_name={:?}",
280 change.target.entity_class,
281 change.target.variable_name
282 );
283 for binding in matched {
284 leaves.push(DescriptorLeafSelector::Change(
285 DescriptorChangeMoveSelector::new(binding, descriptor.clone()),
286 ));
287 }
288 }
289 MoveSelectorConfig::SwapMoveSelector(swap) => {
290 let matched = find_binding(
291 bindings,
292 swap.target.entity_class.as_deref(),
293 swap.target.variable_name.as_deref(),
294 );
295 assert!(
296 !matched.is_empty(),
297 "swap_move selector matched no standard planning variables for entity_class={:?} variable_name={:?}",
298 swap.target.entity_class,
299 swap.target.variable_name
300 );
301 for binding in matched {
302 leaves.push(DescriptorLeafSelector::Swap(
303 DescriptorSwapMoveSelector::new(binding, descriptor.clone()),
304 ));
305 }
306 }
307 MoveSelectorConfig::UnionMoveSelector(union) => {
308 for child in &union.selectors {
309 collect(child, descriptor, bindings, leaves);
310 }
311 }
312 MoveSelectorConfig::LimitedNeighborhood(_) => {
313 panic!("limited_neighborhood must be handled by the canonical runtime");
314 }
315 MoveSelectorConfig::ListChangeMoveSelector(_)
316 | MoveSelectorConfig::NearbyListChangeMoveSelector(_)
317 | MoveSelectorConfig::ListSwapMoveSelector(_)
318 | MoveSelectorConfig::NearbyListSwapMoveSelector(_)
319 | MoveSelectorConfig::SubListChangeMoveSelector(_)
320 | MoveSelectorConfig::SubListSwapMoveSelector(_)
321 | MoveSelectorConfig::ListReverseMoveSelector(_)
322 | MoveSelectorConfig::KOptMoveSelector(_)
323 | MoveSelectorConfig::ListRuinMoveSelector(_) => {
324 panic!("list move selector configured against a standard-variable context");
325 }
326 MoveSelectorConfig::CartesianProductMoveSelector(_) => {
327 panic!("cartesian_product move selectors are not supported in the canonical solver path");
328 }
329 }
330 }
331
332 match config {
333 Some(cfg) => collect(cfg, descriptor, &bindings, &mut leaves),
334 None => {
335 for binding in bindings {
336 leaves.push(DescriptorLeafSelector::Change(
337 DescriptorChangeMoveSelector::new(binding.clone(), descriptor.clone()),
338 ));
339 leaves.push(DescriptorLeafSelector::Swap(
340 DescriptorSwapMoveSelector::new(binding, descriptor.clone()),
341 ));
342 }
343 }
344 }
345
346 assert!(
347 !leaves.is_empty(),
348 "move selector configuration produced no standard neighborhoods"
349 );
350
351 leaves
352}
353
354pub fn build_descriptor_move_selector<S>(
355 config: Option<&MoveSelectorConfig>,
356 descriptor: &SolutionDescriptor,
357) -> VecUnionSelector<S, DescriptorEitherMove<S>, DescriptorLeafSelector<S>>
358where
359 S: PlanningSolution + 'static,
360{
361 VecUnionSelector::new(collect_descriptor_leaf_selectors(config, descriptor))
362}