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, solution: &S) -> Option<CandidateId> {
59        self.inner.next_candidate(solution)
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, solution: &S) -> Option<ListSwapMove<S, V>> {
71        self.inner.next_owned_candidate(solution)
72    }
73
74    fn next_owned_candidate_matching(
75        &mut self,
76        solution: &S,
77        predicate: for<'a> fn(MoveCandidateRef<'a, S, ListSwapMove<S, V>>) -> bool,
78    ) -> Option<ListSwapMove<S, V>> {
79        self.inner
80            .next_owned_candidate_matching(solution, predicate)
81    }
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 ListSwapMoveSelector<S, V, ES> {
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        f.debug_struct("ListSwapMoveSelector")
91            .field("entity_selector", &self.entity_selector)
92            .field("variable_name", &self.variable_name)
93            .field("descriptor_index", &self.descriptor_index)
94            .finish()
95    }
96}
97
98impl<S, V, ES> ListSwapMoveSelector<S, V, ES> {
99    pub fn new(
100        entity_selector: ES,
101        list_len: fn(&S, usize) -> usize,
102        list_get: fn(&S, usize, usize) -> Option<V>,
103        list_set: fn(&mut S, usize, usize, V),
104        variable_name: &'static str,
105        descriptor_index: usize,
106    ) -> Self {
107        Self {
108            entity_selector,
109            list_len,
110            list_get,
111            list_set,
112            element_owner_fn: None,
113            variable_name,
114            descriptor_index,
115            _phantom: PhantomData,
116        }
117    }
118
119    pub fn with_element_owner_fn(
120        mut self,
121        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
122    ) -> Self {
123        self.element_owner_fn = element_owner_fn;
124        self
125    }
126}
127
128impl<S, V, ES> MoveSelector<S, ListSwapMove<S, V>> for ListSwapMoveSelector<S, V, ES>
129where
130    S: PlanningSolution,
131    V: Clone + PartialEq + Send + Sync + Debug + 'static,
132    ES: EntitySelector<S>,
133{
134    type Cursor<'a>
135        = ListSwapMoveCursor<S, V>
136    where
137        Self: 'a;
138
139    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
140        self.open_cursor_with_context(score_director, MoveStreamContext::default())
141    }
142
143    fn open_cursor_with_context<'a, D: Director<S>>(
144        &'a self,
145        score_director: &D,
146        context: MoveStreamContext,
147    ) -> Self::Cursor<'a> {
148        let mut selected =
149            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
150        selected.apply_stream_order(
151            context,
152            STATIC_SWAP_SALTS.entity ^ self.descriptor_index as u64,
153        );
154        let owner_restrictions = crate::list_placement::selected_owner_restrictions(
155            self.element_owner_fn,
156            score_director.working_solution(),
157            score_director
158                .entity_count(self.descriptor_index)
159                .unwrap_or(0),
160            &selected.entities,
161            &selected.route_lens,
162            self.list_get,
163        );
164        let owners = SelectedListOwners::from_selected_restrictions(owner_restrictions);
165        ListSwapMoveCursor::new(SwapCursor::new(
166            NativeSwapEmitter::new(
167                self.list_len,
168                self.list_get,
169                self.list_set,
170                self.variable_name,
171                self.descriptor_index,
172            ),
173            selected.entities,
174            selected.route_lens,
175            context,
176            STATIC_SWAP_SALTS,
177            owners,
178            self.descriptor_index,
179        ))
180    }
181
182    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
183        let selected =
184            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
185        let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
186            self.element_owner_fn,
187            score_director.working_solution(),
188            score_director
189                .entity_count(self.descriptor_index)
190                .unwrap_or(0),
191            &selected.entities,
192            &selected.route_lens,
193            self.list_get,
194        ) else {
195            return selected.list_swap_move_capacity();
196        };
197
198        if owner_restrictions.is_fixed_to_current() {
199            return selected
200                .route_lens
201                .iter()
202                .map(|&len| len * len.saturating_sub(1) / 2)
203                .sum();
204        }
205        let element_owners = owner_restrictions
206            .mixed()
207            .expect("non-fixed owner restrictions retain their matrix");
208        let mut count = 0;
209        for (left_idx, (&left_entity, &left_len)) in selected
210            .entities
211            .iter()
212            .zip(selected.route_lens.iter())
213            .enumerate()
214        {
215            for left_position in 0..left_len {
216                for right_position in left_position + 1..left_len {
217                    if selected_owner_allows(element_owners, left_idx, left_position, left_entity)
218                        && selected_owner_allows(
219                            element_owners,
220                            left_idx,
221                            right_position,
222                            left_entity,
223                        )
224                    {
225                        count += 1;
226                    }
227                }
228                for (right_idx, (&right_entity, &right_len)) in selected
229                    .entities
230                    .iter()
231                    .zip(selected.route_lens.iter())
232                    .enumerate()
233                    .skip(left_idx + 1)
234                {
235                    for right_position in 0..right_len {
236                        if selected_owner_allows(
237                            element_owners,
238                            left_idx,
239                            left_position,
240                            right_entity,
241                        ) && selected_owner_allows(
242                            element_owners,
243                            right_idx,
244                            right_position,
245                            left_entity,
246                        ) {
247                            count += 1;
248                        }
249                    }
250                }
251            }
252        }
253        count
254    }
255}
solverforge_solver/heuristic/selector/list_swap.rs

solverforge_solver/heuristic/selector/
list_swap.rs
