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> 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    fn access(&self) -> StaticListWindowAccess<S, V> {
129        StaticListWindowAccess {
130            list_len: self.list_len,
131            list_get: self.list_get,
132            sublist_remove: self.sublist_remove,
133            sublist_insert: self.sublist_insert,
134            variable_name: self.variable_name,
135            descriptor_index: self.descriptor_index,
136        }
137    }
138
139    fn coordinates(&self) -> PermuteCoordinates {
140        PermuteCoordinates {
141            entity: self.entity_index,
142            start: self.start,
143            end: self.end,
144        }
145    }
146}
147
148impl<S, V> Move<S> for ListPermuteMove<S, V>
149where
150    S: PlanningSolution,
151    V: Clone + Send + Sync + Debug + 'static,
152{
153    type Undo = Vec<V>;
154
155    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
156        permute_is_doable(
157            &self.access(),
158            self.coordinates(),
159            &self.permutation,
160            score_director,
161        )
162    }
163
164    fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
165        permute_do_move(
166            &self.access(),
167            self.coordinates(),
168            &self.permutation,
169            score_director,
170        )
171    }
172
173    fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
174        permute_undo_move(&self.access(), self.coordinates(), undo, score_director);
175    }
176
177    fn descriptor_index(&self) -> usize {
178        self.descriptor_index
179    }
180
181    fn entity_indices(&self) -> &[usize] {
182        &self.entity_indices
183    }
184
185    fn variable_name(&self) -> &str {
186        self.variable_name
187    }
188
189    fn telemetry_label(&self) -> &'static str {
190        "list_permute"
191    }
192
193    fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> MoveTabuSignature {
194        permute_tabu_signature(
195            &self.access(),
196            self.coordinates(),
197            &self.permutation,
198            &self.inverse_permutation,
199            score_director,
200        )
201    }
202
203    fn candidate_trace_identity(&self) -> Option<crate::stats::CandidateTraceIdentity> {
204        Some(permute_candidate_trace_identity(
205            &self.access(),
206            self.coordinates(),
207            &self.permutation,
208        ))
209    }
210}
211
212fn inverse_permutation(permutation: &[usize]) -> SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> {
213    let mut inverse = smallvec![0; permutation.len()];
214    for (new_idx, &old_idx) in permutation.iter().enumerate() {
215        inverse[old_idx] = new_idx;
216    }
217    inverse
218}
solverforge_solver/heuristic/move/list_permute.rs

solverforge_solver/heuristic/move/
list_permute.rs
