solverforge_solver/heuristic/move/
list_permute.rs

1/* ListPermuteMove - permutes a contiguous window within a list variable. */
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use smallvec::{smallvec, SmallVec};
7use solverforge_core::domain::PlanningSolution;
8use solverforge_scoring::Director;
9
10use super::metadata::{
11    encode_option_debug, encode_usize, hash_str, MoveTabuScope, ScopedValueTabuToken,
12    TABU_OP_LIST_PERMUTE,
13};
14use super::{Move, MoveTabuSignature};
15
16pub const MAX_LIST_PERMUTE_WINDOW_SIZE: usize = 8;
17
18pub struct ListPermuteMove<S, V> {
19    entity_index: usize,
20    start: usize,
21    end: usize,
22    permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
23    inverse_permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
24    list_len: fn(&S, usize) -> usize,
25    list_get: fn(&S, usize, usize) -> Option<V>,
26    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
27    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
28    variable_name: &'static str,
29    descriptor_index: usize,
30    entity_indices: [usize; 1],
31    _phantom: PhantomData<fn() -> V>,
32}
33
34impl<S, V> Clone for ListPermuteMove<S, V> {
35    fn clone(&self) -> Self {
36        Self {
37            entity_index: self.entity_index,
38            start: self.start,
39            end: self.end,
40            permutation: self.permutation.clone(),
41            inverse_permutation: self.inverse_permutation.clone(),
42            list_len: self.list_len,
43            list_get: self.list_get,
44            sublist_remove: self.sublist_remove,
45            sublist_insert: self.sublist_insert,
46            variable_name: self.variable_name,
47            descriptor_index: self.descriptor_index,
48            entity_indices: self.entity_indices,
49            _phantom: PhantomData,
50        }
51    }
52}
53
54impl<S, V: Debug> Debug for ListPermuteMove<S, V> {
55    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
56        f.debug_struct("ListPermuteMove")
57            .field("entity", &self.entity_index)
58            .field("start", &self.start)
59            .field("end", &self.end)
60            .field("permutation", &self.permutation)
61            .field("variable_name", &self.variable_name)
62            .finish()
63    }
64}
65
66impl<S, V> ListPermuteMove<S, V> {
67    #[allow(clippy::too_many_arguments)]
68    pub fn new(
69        entity_index: usize,
70        start: usize,
71        end: usize,
72        permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
73        list_len: fn(&S, usize) -> usize,
74        list_get: fn(&S, usize, usize) -> Option<V>,
75        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
76        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
77        variable_name: &'static str,
78        descriptor_index: usize,
79    ) -> Self {
80        let window_len = end.saturating_sub(start);
81        assert!(
82            (2..=MAX_LIST_PERMUTE_WINDOW_SIZE).contains(&window_len),
83            "list permute window length must be 2..={MAX_LIST_PERMUTE_WINDOW_SIZE}",
84        );
85        assert_eq!(
86            permutation.len(),
87            window_len,
88            "list permute permutation length must match window length",
89        );
90        let inverse_permutation = inverse_permutation(&permutation);
91        Self {
92            entity_index,
93            start,
94            end,
95            permutation,
96            inverse_permutation,
97            list_len,
98            list_get,
99            sublist_remove,
100            sublist_insert,
101            variable_name,
102            descriptor_index,
103            entity_indices: [entity_index],
104            _phantom: PhantomData,
105        }
106    }
107
108    #[inline]
109    pub fn entity_index(&self) -> usize {
110        self.entity_index
111    }
112
113    #[inline]
114    pub fn start(&self) -> usize {
115        self.start
116    }
117
118    #[inline]
119    pub fn end(&self) -> usize {
120        self.end
121    }
122
123    #[inline]
124    pub fn permutation(&self) -> &[usize] {
125        &self.permutation
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 = Vec<V>;
135
136    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
137        let solution = score_director.working_solution();
138        let len = (self.list_len)(solution, self.entity_index);
139        self.start < self.end
140            && self.end <= len
141            && valid_non_identity_permutation(&self.permutation)
142    }
143
144    fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
145        score_director.before_variable_changed(self.descriptor_index, self.entity_index);
146        let segment = (self.sublist_remove)(
147            score_director.working_solution_mut(),
148            self.entity_index,
149            self.start,
150            self.end,
151        );
152        let reordered = self
153            .permutation
154            .iter()
155            .map(|&index| segment[index].clone())
156            .collect();
157        (self.sublist_insert)(
158            score_director.working_solution_mut(),
159            self.entity_index,
160            self.start,
161            reordered,
162        );
163        score_director.after_variable_changed(self.descriptor_index, self.entity_index);
164        segment
165    }
166
167    fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
168        score_director.before_variable_changed(self.descriptor_index, self.entity_index);
169        let _ = (self.sublist_remove)(
170            score_director.working_solution_mut(),
171            self.entity_index,
172            self.start,
173            self.end,
174        );
175        (self.sublist_insert)(
176            score_director.working_solution_mut(),
177            self.entity_index,
178            self.start,
179            undo,
180        );
181        score_director.after_variable_changed(self.descriptor_index, self.entity_index);
182    }
183
184    fn descriptor_index(&self) -> usize {
185        self.descriptor_index
186    }
187
188    fn entity_indices(&self) -> &[usize] {
189        &self.entity_indices
190    }
191
192    fn variable_name(&self) -> &str {
193        self.variable_name
194    }
195
196    fn telemetry_label(&self) -> &'static str {
197        "list_permute"
198    }
199
200    fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> MoveTabuSignature {
201        let scope = MoveTabuScope::new(self.descriptor_index, self.variable_name);
202        let entity_id = encode_usize(self.entity_index);
203        let variable_id = hash_str(self.variable_name);
204        let mut touched_value_ids = SmallVec::<[u64; 8]>::new();
205        for pos in self.start..self.end {
206            let value = (self.list_get)(score_director.working_solution(), self.entity_index, pos);
207            touched_value_ids.push(encode_option_debug(value.as_ref()));
208        }
209
210        let mut move_id = smallvec![
211            TABU_OP_LIST_PERMUTE,
212            encode_usize(self.descriptor_index),
213            variable_id,
214            entity_id,
215            encode_usize(self.start),
216            encode_usize(self.end),
217        ];
218        move_id.extend(self.permutation.iter().copied().map(encode_usize));
219        move_id.extend(touched_value_ids.iter().copied());
220
221        let mut undo_move_id = smallvec![
222            TABU_OP_LIST_PERMUTE,
223            encode_usize(self.descriptor_index),
224            variable_id,
225            entity_id,
226            encode_usize(self.start),
227            encode_usize(self.end),
228        ];
229        undo_move_id.extend(self.inverse_permutation.iter().copied().map(encode_usize));
230        undo_move_id.extend(touched_value_ids.iter().copied());
231
232        let destination_value_tokens: SmallVec<[ScopedValueTabuToken; 2]> = touched_value_ids
233            .iter()
234            .copied()
235            .map(|value_id| scope.value_token(value_id))
236            .collect();
237
238        MoveTabuSignature::new(scope, move_id, undo_move_id)
239            .with_entity_tokens([scope.entity_token(entity_id)])
240            .with_destination_value_tokens(destination_value_tokens)
241    }
242}
243
244fn valid_non_identity_permutation(permutation: &[usize]) -> bool {
245    let len = permutation.len();
246    if !(2..=MAX_LIST_PERMUTE_WINDOW_SIZE).contains(&len) {
247        return false;
248    }
249    let mut seen = [false; MAX_LIST_PERMUTE_WINDOW_SIZE];
250    let mut is_identity = true;
251    for (idx, &value) in permutation.iter().enumerate() {
252        if value >= len || seen[value] {
253            return false;
254        }
255        seen[value] = true;
256        is_identity &= value == idx;
257    }
258    !is_identity
259}
260
261fn inverse_permutation(permutation: &[usize]) -> SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> {
262    let mut inverse = smallvec![0; permutation.len()];
263    for (new_idx, &old_idx) in permutation.iter().enumerate() {
264        inverse[old_idx] = new_idx;
265    }
266    inverse
267}
solverforge_solver/heuristic/move/list_permute.rs

solverforge_solver/heuristic/move/
list_permute.rs
