solverforge_solver/heuristic/selector/
list_permute.rs

1//! Public static adapter for the canonical streamed list-permute 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::{ListPermuteMove, MAX_LIST_PERMUTE_WINDOW_SIZE};
10use crate::heuristic::selector::list_kernel::{
11    count_list_permute_moves_for_len, factorial, NativeWindowEmitter, PermuteCursor,
12    SelectedListOwners,
13};
14use crate::list_placement::selected_segment_allows;
15
16use super::entity::EntitySelector;
17use super::list_support::collect_selected_entities;
18use super::move_selector::{
19    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
20};
21
22pub struct ListPermuteMoveSelector<S, V, ES> {
23    entity_selector: ES,
24    min_window_size: usize,
25    max_window_size: usize,
26    list_len: fn(&S, usize) -> usize,
27    list_get: fn(&S, usize, usize) -> Option<V>,
28    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
29    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
30    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
31    variable_name: &'static str,
32    descriptor_index: usize,
33    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
34}
35
36pub struct ListPermuteMoveCursor<S, V>
37where
38    S: PlanningSolution,
39    V: Clone + Send + Sync + Debug + 'static,
40{
41    inner: PermuteCursor<S, NativeWindowEmitter<S, V>>,
42}
43
44impl<S, V> ListPermuteMoveCursor<S, V>
45where
46    S: PlanningSolution,
47    V: Clone + Send + Sync + Debug + 'static,
48{
49    fn new(inner: PermuteCursor<S, NativeWindowEmitter<S, V>>) -> Self {
50        Self { inner }
51    }
52}
53
54impl<S, V> MoveCursor<S, ListPermuteMove<S, V>> for ListPermuteMoveCursor<S, V>
55where
56    S: PlanningSolution,
57    V: Clone + Send + Sync + Debug + 'static,
58{
59    fn next_candidate(&mut self, solution: &S) -> Option<CandidateId> {
60        self.inner.next_candidate(solution)
61    }
62    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListPermuteMove<S, V>>> {
63        self.inner.candidate(id)
64    }
65    fn take_candidate(&mut self, id: CandidateId) -> ListPermuteMove<S, V> {
66        self.inner.take_candidate(id)
67    }
68    fn next_owned_candidate(&mut self, solution: &S) -> Option<ListPermuteMove<S, V>> {
69        self.inner.next_owned_candidate(solution)
70    }
71    fn next_owned_candidate_matching(
72        &mut self,
73        solution: &S,
74        predicate: for<'a> fn(MoveCandidateRef<'a, S, ListPermuteMove<S, V>>) -> bool,
75    ) -> Option<ListPermuteMove<S, V>> {
76        self.inner
77            .next_owned_candidate_matching(solution, predicate)
78    }
79    fn release_candidate(&mut self, id: CandidateId) -> bool {
80        self.inner.release_candidate(id)
81    }
82}
83
84impl<S, V: Debug, ES: Debug> Debug for ListPermuteMoveSelector<S, V, ES> {
85    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
86        f.debug_struct("ListPermuteMoveSelector")
87            .field("entity_selector", &self.entity_selector)
88            .field("min_window_size", &self.min_window_size)
89            .field("max_window_size", &self.max_window_size)
90            .field("variable_name", &self.variable_name)
91            .finish()
92    }
93}
94
95impl<S, V, ES> ListPermuteMoveSelector<S, V, ES> {
96    #[allow(clippy::too_many_arguments)]
97    pub fn new(
98        entity_selector: ES,
99        min_window_size: usize,
100        max_window_size: usize,
101        list_len: fn(&S, usize) -> usize,
102        list_get: fn(&S, usize, usize) -> Option<V>,
103        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
104        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
105        variable_name: &'static str,
106        descriptor_index: usize,
107    ) -> Self {
108        assert!(
109            min_window_size >= 2,
110            "list permute min_window_size must be at least 2",
111        );
112        assert!(
113            min_window_size <= max_window_size,
114            "list permute min_window_size must be <= max_window_size",
115        );
116        assert!(
117            max_window_size <= MAX_LIST_PERMUTE_WINDOW_SIZE,
118            "list permute max_window_size must be <= {MAX_LIST_PERMUTE_WINDOW_SIZE}",
119        );
120        Self {
121            entity_selector,
122            min_window_size,
123            max_window_size,
124            list_len,
125            list_get,
126            sublist_remove,
127            sublist_insert,
128            element_owner_fn: None,
129            variable_name,
130            descriptor_index,
131            _phantom: PhantomData,
132        }
133    }
134
135    pub fn with_element_owner_fn(mut self, owner_fn: Option<fn(&S, &V) -> Option<usize>>) -> Self {
136        self.element_owner_fn = owner_fn;
137        self
138    }
139}
140
141impl<S, V, ES> MoveSelector<S, ListPermuteMove<S, V>> for ListPermuteMoveSelector<S, V, ES>
142where
143    S: PlanningSolution,
144    V: Clone + Send + Sync + Debug + 'static,
145    ES: EntitySelector<S>,
146{
147    type Cursor<'a>
148        = ListPermuteMoveCursor<S, V>
149    where
150        Self: 'a;
151
152    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
153        self.open_cursor_with_context(score_director, MoveStreamContext::default())
154    }
155
156    fn open_cursor_with_context<'a, D: Director<S>>(
157        &'a self,
158        score_director: &D,
159        context: MoveStreamContext,
160    ) -> Self::Cursor<'a> {
161        let selected =
162            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
163        let owner_restrictions = crate::list_placement::selected_owner_restrictions(
164            self.element_owner_fn,
165            score_director.working_solution(),
166            score_director
167                .entity_count(self.descriptor_index)
168                .unwrap_or(0),
169            &selected.entities,
170            &selected.route_lens,
171            self.list_get,
172        );
173        let owners = SelectedListOwners::from_selected_restrictions(owner_restrictions);
174        ListPermuteMoveCursor::new(PermuteCursor::new(
175            NativeWindowEmitter::new(
176                self.list_len,
177                self.list_get,
178                self.sublist_remove,
179                self.sublist_insert,
180                self.variable_name,
181                self.descriptor_index,
182            ),
183            selected.entities,
184            selected.route_lens,
185            context,
186            self.min_window_size,
187            self.max_window_size,
188            owners,
189            self.descriptor_index,
190        ))
191    }
192
193    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
194        let selected =
195            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
196        let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
197            self.element_owner_fn,
198            score_director.working_solution(),
199            score_director
200                .entity_count(self.descriptor_index)
201                .unwrap_or(0),
202            &selected.entities,
203            &selected.route_lens,
204            self.list_get,
205        ) else {
206            return selected
207                .route_lens
208                .iter()
209                .map(|&route_len| {
210                    count_list_permute_moves_for_len(
211                        route_len,
212                        self.min_window_size,
213                        self.max_window_size,
214                    )
215                })
216                .sum();
217        };
218        if owner_restrictions.is_fixed_to_current() {
219            return selected
220                .route_lens
221                .iter()
222                .map(|&route_len| {
223                    count_list_permute_moves_for_len(
224                        route_len,
225                        self.min_window_size,
226                        self.max_window_size,
227                    )
228                })
229                .sum();
230        }
231        let owners = owner_restrictions
232            .mixed()
233            .expect("non-fixed owner restrictions retain their matrix");
234        let mut count = 0;
235        for (entity_idx, &route_len) in selected.route_lens.iter().enumerate() {
236            for start in 0..route_len {
237                let max_valid = self.max_window_size.min(route_len - start);
238                for size in self.min_window_size..=max_valid {
239                    if selected_segment_allows(
240                        owners,
241                        entity_idx,
242                        start,
243                        start + size,
244                        selected.entities[entity_idx],
245                    ) {
246                        count += factorial(size).saturating_sub(1);
247                    }
248                }
249            }
250        }
251        count
252    }
253}
solverforge_solver/heuristic/selector/list_permute.rs

solverforge_solver/heuristic/selector/
list_permute.rs
