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

solverforge_solver/heuristic/selector/
list_permute.rs
