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

solverforge_solver/heuristic/move/
list_permute.rs
