solverforge_solver/heuristic/move/
list_permute.rs

1/* ListPermuteMove - permutes a contiguous window within a list variable. */
2
3use std::borrow::Cow;
4use std::fmt::Debug;
5use std::marker::PhantomData;
6
7use smallvec::{smallvec, SmallVec};
8use solverforge_core::domain::PlanningSolution;
9use solverforge_scoring::Director;
10
11use super::list_kernel::{
12    permute_candidate_trace_identity, permute_do_move, permute_is_doable, permute_tabu_signature,
13    permute_undo_move, PermuteCoordinates, StaticListWindowAccess,
14};
15use super::{Move, MoveTabuSignature};
16
17pub const MAX_LIST_PERMUTE_WINDOW_SIZE: usize = 8;
18
19pub struct ListPermuteMove<S, V> {
20    entity_index: usize,
21    start: usize,
22    end: usize,
23    permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
24    inverse_permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
25    list_len: fn(&S, usize) -> usize,
26    list_get: fn(&S, usize, usize) -> Option<V>,
27    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
28    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
29    variable_name: &'static str,
30    descriptor_index: usize,
31    entity_indices: [usize; 1],
32    _phantom: PhantomData<fn() -> V>,
33}
34
35impl<S, V: Debug> Debug for ListPermuteMove<S, V> {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        f.debug_struct("ListPermuteMove")
38            .field("entity", &self.entity_index)
39            .field("start", &self.start)
40            .field("end", &self.end)
41            .field("permutation", &self.permutation)
42            .field("variable_name", &self.variable_name)
43            .finish()
44    }
45}
46
47impl<S, V> ListPermuteMove<S, V> {
48    #[allow(clippy::too_many_arguments)]
49    pub fn new(
50        entity_index: usize,
51        start: usize,
52        end: usize,
53        permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
54        list_len: fn(&S, usize) -> usize,
55        list_get: fn(&S, usize, usize) -> Option<V>,
56        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
57        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
58        variable_name: &'static str,
59        descriptor_index: usize,
60    ) -> Self {
61        let window_len = end.saturating_sub(start);
62        assert!(
63            (2..=MAX_LIST_PERMUTE_WINDOW_SIZE).contains(&window_len),
64            "list permute window length must be 2..={MAX_LIST_PERMUTE_WINDOW_SIZE}",
65        );
66        assert_eq!(
67            permutation.len(),
68            window_len,
69            "list permute permutation length must match window length",
70        );
71        let inverse_permutation = inverse_permutation(&permutation);
72        Self {
73            entity_index,
74            start,
75            end,
76            permutation,
77            inverse_permutation,
78            list_len,
79            list_get,
80            sublist_remove,
81            sublist_insert,
82            variable_name,
83            descriptor_index,
84            entity_indices: [entity_index],
85            _phantom: PhantomData,
86        }
87    }
88
89    #[inline]
90    pub fn entity_index(&self) -> usize {
91        self.entity_index
92    }
93
94    #[inline]
95    pub fn start(&self) -> usize {
96        self.start
97    }
98
99    #[inline]
100    pub fn end(&self) -> usize {
101        self.end
102    }
103
104    #[inline]
105    pub fn permutation(&self) -> &[usize] {
106        &self.permutation
107    }
108
109    fn access(&self) -> StaticListWindowAccess<S, V> {
110        StaticListWindowAccess {
111            list_len: self.list_len,
112            list_get: self.list_get,
113            sublist_remove: self.sublist_remove,
114            sublist_insert: self.sublist_insert,
115            variable_name: self.variable_name,
116            descriptor_index: self.descriptor_index,
117        }
118    }
119
120    fn coordinates(&self) -> PermuteCoordinates {
121        PermuteCoordinates {
122            entity: self.entity_index,
123            start: self.start,
124            end: self.end,
125        }
126    }
127}
128
129impl<S, V> Move<S> for ListPermuteMove<S, V>
130where
131    S: PlanningSolution,
132    V: Clone + Send + Sync + Debug + 'static,
133{
134    type Undo = SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>;
135
136    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
137        permute_is_doable(
138            &self.access(),
139            self.coordinates(),
140            &self.permutation,
141            score_director,
142        )
143    }
144
145    fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
146        permute_do_move(
147            &self.access(),
148            self.coordinates(),
149            &self.permutation,
150            score_director,
151        );
152        self.inverse_permutation.clone()
153    }
154
155    fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
156        permute_undo_move(&self.access(), self.coordinates(), &undo, score_director);
157    }
158
159    fn descriptor_index(&self) -> usize {
160        self.descriptor_index
161    }
162
163    fn entity_indices(&self) -> &[usize] {
164        &self.entity_indices
165    }
166
167    fn variable_name(&self) -> &str {
168        self.variable_name
169    }
170
171    fn telemetry_label(&self) -> &'static str {
172        "list_permute"
173    }
174
175    fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> Cow<'_, MoveTabuSignature> {
176        Cow::Owned(permute_tabu_signature(
177            &self.access(),
178            self.coordinates(),
179            &self.permutation,
180            &self.inverse_permutation,
181            score_director,
182        ))
183    }
184
185    fn candidate_trace_identity(&self) -> Option<crate::stats::CandidateTraceIdentity> {
186        Some(permute_candidate_trace_identity(
187            &self.access(),
188            self.coordinates(),
189            &self.permutation,
190        ))
191    }
192}
193
194fn inverse_permutation(permutation: &[usize]) -> SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> {
195    let mut inverse = smallvec![0; permutation.len()];
196    for (new_idx, &old_idx) in permutation.iter().enumerate() {
197        inverse[old_idx] = new_idx;
198    }
199    inverse
200}
solverforge_solver/heuristic/move/list_permute.rs

solverforge_solver/heuristic/move/
list_permute.rs
