solverforge_solver/heuristic/selector/
list_swap.rs

1//! Public static adapter for the canonical streamed list-swap kernel.
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::ListSwapMove;
10use crate::heuristic::selector::list_kernel::{
11    NativeSwapEmitter, SelectedListOwners, SwapCursor, STATIC_SWAP_SALTS,
12};
13use crate::list_placement::selected_owner_allows;
14
15use super::entity::EntitySelector;
16use super::list_support::collect_selected_entities;
17use super::move_selector::{
18    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
19};
20
21/// Native list swap selector.  It retains its public move type while the
22/// shared cursor owns ordering, ownership pruning, and candidate ownership.
23pub struct ListSwapMoveSelector<S, V, ES> {
24    entity_selector: ES,
25    list_len: fn(&S, usize) -> usize,
26    list_get: fn(&S, usize, usize) -> Option<V>,
27    list_set: fn(&mut S, usize, usize, V),
28    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
29    variable_name: &'static str,
30    descriptor_index: usize,
31    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
32}
33
34/// Public cursor facade that hides the crate-private generic emitter/kernel.
35pub struct ListSwapMoveCursor<S, V>
36where
37    S: PlanningSolution,
38    V: Clone + PartialEq + Send + Sync + Debug + 'static,
39{
40    inner: SwapCursor<S, NativeSwapEmitter<S, V>>,
41}
42
43impl<S, V> ListSwapMoveCursor<S, V>
44where
45    S: PlanningSolution,
46    V: Clone + PartialEq + Send + Sync + Debug + 'static,
47{
48    fn new(inner: SwapCursor<S, NativeSwapEmitter<S, V>>) -> Self {
49        Self { inner }
50    }
51}
52
53impl<S, V> MoveCursor<S, ListSwapMove<S, V>> for ListSwapMoveCursor<S, V>
54where
55    S: PlanningSolution,
56    V: Clone + PartialEq + Send + Sync + Debug + 'static,
57{
58    fn next_candidate(&mut self) -> Option<CandidateId> {
59        self.inner.next_candidate()
60    }
61
62    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListSwapMove<S, V>>> {
63        self.inner.candidate(id)
64    }
65
66    fn take_candidate(&mut self, id: CandidateId) -> ListSwapMove<S, V> {
67        self.inner.take_candidate(id)
68    }
69
70    fn next_owned_candidate(&mut self) -> Option<ListSwapMove<S, V>> {
71        self.inner.next_owned_candidate()
72    }
73
74    fn next_owned_candidate_matching(
75        &mut self,
76        predicate: for<'a> fn(MoveCandidateRef<'a, S, ListSwapMove<S, V>>) -> bool,
77    ) -> Option<ListSwapMove<S, V>> {
78        self.inner.next_owned_candidate_matching(predicate)
79    }
80
81    fn release_candidate(&mut self, id: CandidateId) -> bool {
82        self.inner.release_candidate(id)
83    }
84}
85
86impl<S, V> Iterator for ListSwapMoveCursor<S, V>
87where
88    S: PlanningSolution,
89    V: Clone + PartialEq + Send + Sync + Debug + 'static,
90{
91    type Item = ListSwapMove<S, V>;
92
93    fn next(&mut self) -> Option<Self::Item> {
94        self.next_owned_candidate()
95    }
96}
97
98impl<S, V: Debug, ES: Debug> Debug for ListSwapMoveSelector<S, V, ES> {
99    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
100        f.debug_struct("ListSwapMoveSelector")
101            .field("entity_selector", &self.entity_selector)
102            .field("variable_name", &self.variable_name)
103            .field("descriptor_index", &self.descriptor_index)
104            .finish()
105    }
106}
107
108impl<S, V, ES> ListSwapMoveSelector<S, V, ES> {
109    pub fn new(
110        entity_selector: ES,
111        list_len: fn(&S, usize) -> usize,
112        list_get: fn(&S, usize, usize) -> Option<V>,
113        list_set: fn(&mut S, usize, usize, V),
114        variable_name: &'static str,
115        descriptor_index: usize,
116    ) -> Self {
117        Self {
118            entity_selector,
119            list_len,
120            list_get,
121            list_set,
122            element_owner_fn: None,
123            variable_name,
124            descriptor_index,
125            _phantom: PhantomData,
126        }
127    }
128
129    pub fn with_element_owner_fn(
130        mut self,
131        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
132    ) -> Self {
133        self.element_owner_fn = element_owner_fn;
134        self
135    }
136}
137
138impl<S, V, ES> MoveSelector<S, ListSwapMove<S, V>> for ListSwapMoveSelector<S, V, ES>
139where
140    S: PlanningSolution,
141    V: Clone + PartialEq + Send + Sync + Debug + 'static,
142    ES: EntitySelector<S>,
143{
144    type Cursor<'a>
145        = ListSwapMoveCursor<S, V>
146    where
147        Self: 'a;
148
149    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
150        self.open_cursor_with_context(score_director, MoveStreamContext::default())
151    }
152
153    fn open_cursor_with_context<'a, D: Director<S>>(
154        &'a self,
155        score_director: &D,
156        context: MoveStreamContext,
157    ) -> Self::Cursor<'a> {
158        let mut selected =
159            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
160        selected.apply_stream_order(
161            context,
162            STATIC_SWAP_SALTS.entity ^ self.descriptor_index as u64,
163        );
164        let owner_restrictions = crate::list_placement::selected_owner_restrictions(
165            self.element_owner_fn,
166            score_director.working_solution(),
167            score_director
168                .entity_count(self.descriptor_index)
169                .unwrap_or(0),
170            &selected.entities,
171            &selected.route_lens,
172            self.list_get,
173        );
174        let owners = SelectedListOwners::from_selected_restrictions(owner_restrictions);
175        ListSwapMoveCursor::new(SwapCursor::new(
176            NativeSwapEmitter::new(
177                self.list_len,
178                self.list_get,
179                self.list_set,
180                self.variable_name,
181                self.descriptor_index,
182            ),
183            selected.entities,
184            selected.route_lens,
185            context,
186            STATIC_SWAP_SALTS,
187            owners,
188            self.descriptor_index,
189        ))
190    }
191
192    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
193        let selected =
194            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
195        let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
196            self.element_owner_fn,
197            score_director.working_solution(),
198            score_director
199                .entity_count(self.descriptor_index)
200                .unwrap_or(0),
201            &selected.entities,
202            &selected.route_lens,
203            self.list_get,
204        ) else {
205            return selected.list_swap_move_capacity();
206        };
207
208        if owner_restrictions.is_fixed_to_current() {
209            return selected
210                .route_lens
211                .iter()
212                .map(|&len| len * len.saturating_sub(1) / 2)
213                .sum();
214        }
215        let element_owners = owner_restrictions
216            .mixed()
217            .expect("non-fixed owner restrictions retain their matrix");
218        let mut count = 0;
219        for (left_idx, (&left_entity, &left_len)) in selected
220            .entities
221            .iter()
222            .zip(selected.route_lens.iter())
223            .enumerate()
224        {
225            for left_position in 0..left_len {
226                for right_position in left_position + 1..left_len {
227                    if selected_owner_allows(element_owners, left_idx, left_position, left_entity)
228                        && selected_owner_allows(
229                            element_owners,
230                            left_idx,
231                            right_position,
232                            left_entity,
233                        )
234                    {
235                        count += 1;
236                    }
237                }
238                for (right_idx, (&right_entity, &right_len)) in selected
239                    .entities
240                    .iter()
241                    .zip(selected.route_lens.iter())
242                    .enumerate()
243                    .skip(left_idx + 1)
244                {
245                    for right_position in 0..right_len {
246                        if selected_owner_allows(
247                            element_owners,
248                            left_idx,
249                            left_position,
250                            right_entity,
251                        ) && selected_owner_allows(
252                            element_owners,
253                            right_idx,
254                            right_position,
255                            left_entity,
256                        ) {
257                            count += 1;
258                        }
259                    }
260                }
261            }
262        }
263        count
264    }
265}
solverforge_solver/heuristic/selector/list_swap.rs

solverforge_solver/heuristic/selector/
list_swap.rs
