solverforge_solver/heuristic/selector/
sublist_change.rs

1//! Public static adapter for the canonical streamed sublist-change cursor.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::SublistChangeMove;
10use crate::list_placement::selected_segment_allows;
11
12use super::list_kernel::{
13    NativeWindowEmitter, SelectedListOwners, SublistChangeCursor, STATIC_SUBLIST_CHANGE_SALTS,
14};
15
16use super::entity::EntitySelector;
17use super::list_support::collect_selected_entities;
18use super::move_selector::{
19    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
20};
21use super::sublist_support::count_sublist_change_moves_for_len;
22
23pub struct SublistChangeMoveSelector<S, V, ES> {
24    entity_selector: ES,
25    min_sublist_size: usize,
26    max_sublist_size: usize,
27    list_len: fn(&S, usize) -> usize,
28    list_get: fn(&S, usize, usize) -> Option<V>,
29    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
30    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
31    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
32    variable_name: &'static str,
33    descriptor_index: usize,
34    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
35}
36
37pub struct SublistChangeMoveCursor<S, V>
38where
39    S: PlanningSolution,
40    V: Clone + PartialEq + Send + Sync + Debug + 'static,
41{
42    inner: SublistChangeCursor<S, NativeWindowEmitter<S, V>>,
43}
44
45impl<S, V> SublistChangeMoveCursor<S, V>
46where
47    S: PlanningSolution,
48    V: Clone + PartialEq + Send + Sync + Debug + 'static,
49{
50    fn new(inner: SublistChangeCursor<S, NativeWindowEmitter<S, V>>) -> Self {
51        Self { inner }
52    }
53}
54
55impl<S, V> MoveCursor<S, SublistChangeMove<S, V>> for SublistChangeMoveCursor<S, V>
56where
57    S: PlanningSolution,
58    V: Clone + PartialEq + Send + Sync + Debug + 'static,
59{
60    fn next_candidate(&mut self) -> Option<CandidateId> {
61        self.inner.next_candidate()
62    }
63    fn candidate(
64        &self,
65        id: CandidateId,
66    ) -> Option<MoveCandidateRef<'_, S, SublistChangeMove<S, V>>> {
67        self.inner.candidate(id)
68    }
69    fn take_candidate(&mut self, id: CandidateId) -> SublistChangeMove<S, V> {
70        self.inner.take_candidate(id)
71    }
72    fn next_owned_candidate(&mut self) -> Option<SublistChangeMove<S, V>> {
73        self.inner.next_owned_candidate()
74    }
75    fn next_owned_candidate_matching(
76        &mut self,
77        predicate: for<'a> fn(MoveCandidateRef<'a, S, SublistChangeMove<S, V>>) -> bool,
78    ) -> Option<SublistChangeMove<S, V>> {
79        self.inner.next_owned_candidate_matching(predicate)
80    }
81    fn release_candidate(&mut self, id: CandidateId) -> bool {
82        self.inner.release_candidate(id)
83    }
84}
85
86impl<S, V> Iterator for SublistChangeMoveCursor<S, V>
87where
88    S: PlanningSolution,
89    V: Clone + PartialEq + Send + Sync + Debug + 'static,
90{
91    type Item = SublistChangeMove<S, V>;
92    fn next(&mut self) -> Option<Self::Item> {
93        self.next_owned_candidate()
94    }
95}
96
97impl<S, V: Debug, ES: Debug> Debug for SublistChangeMoveSelector<S, V, ES> {
98    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
99        f.debug_struct("SublistChangeMoveSelector")
100            .field("entity_selector", &self.entity_selector)
101            .field("min_sublist_size", &self.min_sublist_size)
102            .field("max_sublist_size", &self.max_sublist_size)
103            .field("variable_name", &self.variable_name)
104            .field("descriptor_index", &self.descriptor_index)
105            .finish()
106    }
107}
108
109impl<S, V, ES> SublistChangeMoveSelector<S, V, ES> {
110    #[allow(clippy::too_many_arguments)]
111    pub fn new(
112        entity_selector: ES,
113        min_sublist_size: usize,
114        max_sublist_size: usize,
115        list_len: fn(&S, usize) -> usize,
116        list_get: fn(&S, usize, usize) -> Option<V>,
117        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
118        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
119        variable_name: &'static str,
120        descriptor_index: usize,
121    ) -> Self {
122        assert!(min_sublist_size >= 1, "min_sublist_size must be at least 1");
123        assert!(
124            max_sublist_size >= min_sublist_size,
125            "max_sublist_size must be >= min_sublist_size"
126        );
127        Self {
128            entity_selector,
129            min_sublist_size,
130            max_sublist_size,
131            list_len,
132            list_get,
133            sublist_remove,
134            sublist_insert,
135            element_owner_fn: None,
136            variable_name,
137            descriptor_index,
138            _phantom: PhantomData,
139        }
140    }
141
142    pub fn with_element_owner_fn(
143        mut self,
144        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
145    ) -> Self {
146        self.element_owner_fn = element_owner_fn;
147        self
148    }
149}
150
151impl<S, V, ES> MoveSelector<S, SublistChangeMove<S, V>> for SublistChangeMoveSelector<S, V, ES>
152where
153    S: PlanningSolution,
154    V: Clone + PartialEq + Send + Sync + Debug + 'static,
155    ES: EntitySelector<S>,
156{
157    type Cursor<'a>
158        = SublistChangeMoveCursor<S, V>
159    where
160        Self: 'a;
161
162    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
163        self.open_cursor_with_context(score_director, MoveStreamContext::default())
164    }
165
166    fn open_cursor_with_context<'a, D: Director<S>>(
167        &'a self,
168        score_director: &D,
169        context: MoveStreamContext,
170    ) -> Self::Cursor<'a> {
171        let mut selected =
172            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
173        selected.apply_stream_order(
174            context,
175            STATIC_SUBLIST_CHANGE_SALTS.entity ^ self.descriptor_index as u64,
176        );
177        let owner_restrictions = crate::list_placement::selected_owner_restrictions(
178            self.element_owner_fn,
179            score_director.working_solution(),
180            score_director
181                .entity_count(self.descriptor_index)
182                .unwrap_or(0),
183            &selected.entities,
184            &selected.route_lens,
185            self.list_get,
186        );
187        let owners = SelectedListOwners::from_selected_restrictions(owner_restrictions);
188        SublistChangeMoveCursor::new(SublistChangeCursor::new(
189            NativeWindowEmitter::new(
190                self.list_len,
191                self.list_get,
192                self.sublist_remove,
193                self.sublist_insert,
194                self.variable_name,
195                self.descriptor_index,
196            ),
197            selected.entities,
198            selected.route_lens,
199            context,
200            STATIC_SUBLIST_CHANGE_SALTS,
201            self.min_sublist_size,
202            self.max_sublist_size,
203            owners,
204            self.descriptor_index,
205        ))
206    }
207
208    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
209        let selected =
210            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
211        let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
212            self.element_owner_fn,
213            score_director.working_solution(),
214            score_director
215                .entity_count(self.descriptor_index)
216                .unwrap_or(0),
217            &selected.entities,
218            &selected.route_lens,
219            self.list_get,
220        ) else {
221            return unfiltered_sublist_change_size(
222                &selected.route_lens,
223                self.min_sublist_size,
224                self.max_sublist_size,
225            );
226        };
227        if owner_restrictions.is_fixed_to_current() {
228            return selected
229                .route_lens
230                .iter()
231                .map(|&route_len| {
232                    count_sublist_change_moves_for_len(
233                        route_len,
234                        0,
235                        self.min_sublist_size,
236                        self.max_sublist_size,
237                    )
238                })
239                .sum();
240        }
241        let element_owners = owner_restrictions
242            .mixed()
243            .expect("non-fixed owner restrictions retain their matrix");
244        let mut count = 0;
245        for (source_idx, (&source_entity, &source_len)) in selected
246            .entities
247            .iter()
248            .zip(selected.route_lens.iter())
249            .enumerate()
250        {
251            for segment_start in 0..source_len {
252                let max_segment = self.max_sublist_size.min(source_len - segment_start);
253                for segment_size in self.min_sublist_size..=max_segment {
254                    let segment_end = segment_start + segment_size;
255                    if selected_segment_allows(
256                        element_owners,
257                        source_idx,
258                        segment_start,
259                        segment_end,
260                        source_entity,
261                    ) {
262                        count += source_len - segment_size;
263                    }
264                    for (destination_idx, (&destination_entity, &destination_len)) in selected
265                        .entities
266                        .iter()
267                        .zip(selected.route_lens.iter())
268                        .enumerate()
269                    {
270                        if destination_idx == source_idx {
271                            continue;
272                        }
273                        if selected_segment_allows(
274                            element_owners,
275                            source_idx,
276                            segment_start,
277                            segment_end,
278                            destination_entity,
279                        ) {
280                            count += destination_len + 1;
281                        }
282                    }
283                }
284            }
285        }
286        count
287    }
288}
289
290fn unfiltered_sublist_change_size(
291    route_lens: &[usize],
292    min_sublist_size: usize,
293    max_sublist_size: usize,
294) -> usize {
295    let total_elements = route_lens.iter().sum::<usize>();
296    let entity_count = route_lens.len();
297    route_lens
298        .iter()
299        .map(|&route_len| {
300            let inter_destinations =
301                total_elements.saturating_sub(route_len) + entity_count.saturating_sub(1);
302            count_sublist_change_moves_for_len(
303                route_len,
304                inter_destinations,
305                min_sublist_size,
306                max_sublist_size,
307            )
308        })
309        .sum()
310}
solverforge_solver/heuristic/selector/sublist_change.rs

solverforge_solver/heuristic/selector/
sublist_change.rs
