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, solution: &S) -> Option<CandidateId> {
61        self.inner.next_candidate(solution)
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, solution: &S) -> Option<SublistChangeMove<S, V>> {
73        self.inner.next_owned_candidate(solution)
74    }
75    fn next_owned_candidate_matching(
76        &mut self,
77        solution: &S,
78        predicate: for<'a> fn(MoveCandidateRef<'a, S, SublistChangeMove<S, V>>) -> bool,
79    ) -> Option<SublistChangeMove<S, V>> {
80        self.inner
81            .next_owned_candidate_matching(solution, predicate)
82    }
83    fn release_candidate(&mut self, id: CandidateId) -> bool {
84        self.inner.release_candidate(id)
85    }
86}
87
88impl<S, V: Debug, ES: Debug> Debug for SublistChangeMoveSelector<S, V, ES> {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        f.debug_struct("SublistChangeMoveSelector")
91            .field("entity_selector", &self.entity_selector)
92            .field("min_sublist_size", &self.min_sublist_size)
93            .field("max_sublist_size", &self.max_sublist_size)
94            .field("variable_name", &self.variable_name)
95            .field("descriptor_index", &self.descriptor_index)
96            .finish()
97    }
98}
99
100impl<S, V, ES> SublistChangeMoveSelector<S, V, ES> {
101    #[allow(clippy::too_many_arguments)]
102    pub fn new(
103        entity_selector: ES,
104        min_sublist_size: usize,
105        max_sublist_size: usize,
106        list_len: fn(&S, usize) -> usize,
107        list_get: fn(&S, usize, usize) -> Option<V>,
108        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
109        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
110        variable_name: &'static str,
111        descriptor_index: usize,
112    ) -> Self {
113        assert!(min_sublist_size >= 1, "min_sublist_size must be at least 1");
114        assert!(
115            max_sublist_size >= min_sublist_size,
116            "max_sublist_size must be >= min_sublist_size"
117        );
118        Self {
119            entity_selector,
120            min_sublist_size,
121            max_sublist_size,
122            list_len,
123            list_get,
124            sublist_remove,
125            sublist_insert,
126            element_owner_fn: None,
127            variable_name,
128            descriptor_index,
129            _phantom: PhantomData,
130        }
131    }
132
133    pub fn with_element_owner_fn(
134        mut self,
135        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
136    ) -> Self {
137        self.element_owner_fn = element_owner_fn;
138        self
139    }
140}
141
142impl<S, V, ES> MoveSelector<S, SublistChangeMove<S, V>> for SublistChangeMoveSelector<S, V, ES>
143where
144    S: PlanningSolution,
145    V: Clone + PartialEq + Send + Sync + Debug + 'static,
146    ES: EntitySelector<S>,
147{
148    type Cursor<'a>
149        = SublistChangeMoveCursor<S, V>
150    where
151        Self: 'a;
152
153    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
154        self.open_cursor_with_context(score_director, MoveStreamContext::default())
155    }
156
157    fn open_cursor_with_context<'a, D: Director<S>>(
158        &'a self,
159        score_director: &D,
160        context: MoveStreamContext,
161    ) -> Self::Cursor<'a> {
162        let mut selected =
163            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
164        selected.apply_stream_order(
165            context,
166            STATIC_SUBLIST_CHANGE_SALTS.entity ^ self.descriptor_index as u64,
167        );
168        let owner_restrictions = crate::list_placement::selected_owner_restrictions(
169            self.element_owner_fn,
170            score_director.working_solution(),
171            score_director
172                .entity_count(self.descriptor_index)
173                .unwrap_or(0),
174            &selected.entities,
175            &selected.route_lens,
176            self.list_get,
177        );
178        let owners = SelectedListOwners::from_selected_restrictions(owner_restrictions);
179        SublistChangeMoveCursor::new(SublistChangeCursor::new(
180            NativeWindowEmitter::new(
181                self.list_len,
182                self.list_get,
183                self.sublist_remove,
184                self.sublist_insert,
185                self.variable_name,
186                self.descriptor_index,
187            ),
188            selected.entities,
189            selected.route_lens,
190            context,
191            STATIC_SUBLIST_CHANGE_SALTS,
192            self.min_sublist_size,
193            self.max_sublist_size,
194            owners,
195            self.descriptor_index,
196        ))
197    }
198
199    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
200        let selected =
201            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
202        let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
203            self.element_owner_fn,
204            score_director.working_solution(),
205            score_director
206                .entity_count(self.descriptor_index)
207                .unwrap_or(0),
208            &selected.entities,
209            &selected.route_lens,
210            self.list_get,
211        ) else {
212            return unfiltered_sublist_change_size(
213                &selected.route_lens,
214                self.min_sublist_size,
215                self.max_sublist_size,
216            );
217        };
218        if owner_restrictions.is_fixed_to_current() {
219            return selected
220                .route_lens
221                .iter()
222                .map(|&route_len| {
223                    count_sublist_change_moves_for_len(
224                        route_len,
225                        0,
226                        self.min_sublist_size,
227                        self.max_sublist_size,
228                    )
229                })
230                .sum();
231        }
232        let element_owners = owner_restrictions
233            .mixed()
234            .expect("non-fixed owner restrictions retain their matrix");
235        let mut count = 0;
236        for (source_idx, (&source_entity, &source_len)) in selected
237            .entities
238            .iter()
239            .zip(selected.route_lens.iter())
240            .enumerate()
241        {
242            for segment_start in 0..source_len {
243                let max_segment = self.max_sublist_size.min(source_len - segment_start);
244                for segment_size in self.min_sublist_size..=max_segment {
245                    let segment_end = segment_start + segment_size;
246                    if selected_segment_allows(
247                        element_owners,
248                        source_idx,
249                        segment_start,
250                        segment_end,
251                        source_entity,
252                    ) {
253                        count += source_len - segment_size;
254                    }
255                    for (destination_idx, (&destination_entity, &destination_len)) in selected
256                        .entities
257                        .iter()
258                        .zip(selected.route_lens.iter())
259                        .enumerate()
260                    {
261                        if destination_idx == source_idx {
262                            continue;
263                        }
264                        if selected_segment_allows(
265                            element_owners,
266                            source_idx,
267                            segment_start,
268                            segment_end,
269                            destination_entity,
270                        ) {
271                            count += destination_len + 1;
272                        }
273                    }
274                }
275            }
276        }
277        count
278    }
279}
280
281fn unfiltered_sublist_change_size(
282    route_lens: &[usize],
283    min_sublist_size: usize,
284    max_sublist_size: usize,
285) -> usize {
286    let total_elements = route_lens.iter().sum::<usize>();
287    let entity_count = route_lens.len();
288    route_lens
289        .iter()
290        .map(|&route_len| {
291            let inter_destinations =
292                total_elements.saturating_sub(route_len) + entity_count.saturating_sub(1);
293            count_sublist_change_moves_for_len(
294                route_len,
295                inter_destinations,
296                min_sublist_size,
297                max_sublist_size,
298            )
299        })
300        .sum()
301}
solverforge_solver/heuristic/selector/sublist_change.rs

solverforge_solver/heuristic/selector/
sublist_change.rs
