solverforge_solver/heuristic/selector/
list_change.rs

1/* List change move selector for element relocation.
2
3Generates `ListChangeMove`s that relocate elements within or between list variables.
4Essential for vehicle routing and scheduling problems.
5
6# Example
7
8```
9use solverforge_solver::heuristic::selector::list_change::ListChangeMoveSelector;
10use solverforge_solver::heuristic::selector::entity::FromSolutionEntitySelector;
11use solverforge_solver::heuristic::selector::MoveSelector;
12use solverforge_core::domain::PlanningSolution;
13use solverforge_core::score::SoftScore;
14
15#[derive(Clone, Debug)]
16struct Vehicle { visits: Vec<i32> }
17
18#[derive(Clone, Debug)]
19struct Solution { vehicles: Vec<Vehicle>, score: Option<SoftScore> }
20
21impl PlanningSolution for Solution {
22type Score = SoftScore;
23fn score(&self) -> Option<Self::Score> { self.score }
24fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
25}
26
27fn list_len(s: &Solution, entity_idx: usize) -> usize {
28s.vehicles.get(entity_idx).map_or(0, |v| v.visits.len())
29}
30fn list_remove(s: &mut Solution, entity_idx: usize, pos: usize) -> Option<i32> {
31s.vehicles.get_mut(entity_idx).map(|v| v.visits.remove(pos))
32}
33fn list_insert(s: &mut Solution, entity_idx: usize, pos: usize, val: i32) {
34if let Some(v) = s.vehicles.get_mut(entity_idx) { v.visits.insert(pos, val); }
35}
36
37let selector = ListChangeMoveSelector::<Solution, i32, _>::new(
38FromSolutionEntitySelector::new(0),
39list_len,
40list_remove,
41list_insert,
42"visits",
430,
44);
45```
46*/
47
48use std::fmt::Debug;
49use std::marker::PhantomData;
50
51use solverforge_core::domain::PlanningSolution;
52use solverforge_scoring::Director;
53
54use crate::heuristic::r#move::ListChangeMove;
55
56use super::entity::EntitySelector;
57use super::list_support::{collect_selected_entities, ordered_index};
58use super::move_selector::{
59    CandidateId, CandidateStore, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
60};
61
62/// A move selector that generates list change moves.
63///
64/// Enumerates all valid (source_entity, source_pos, dest_entity, dest_pos)
65/// combinations for relocating elements within or between list variables.
66///
67/// # Type Parameters
68/// * `S` - The solution type
69/// * `V` - The list element type
70///
71/// # Complexity
72///
73/// For n entities with average route length m:
74/// - Intra-entity moves: O(n * m * m)
75/// - Inter-entity moves: O(n * n * m * m)
76/// - Total: O(n² * m²) worst case
77///
78/// Use with a forager that quits early for better performance.
79pub struct ListChangeMoveSelector<S, V, ES> {
80    // Selects entities (vehicles) for moves.
81    entity_selector: ES,
82    list_len: fn(&S, usize) -> usize,
83    // Read element by position for exact move/value tabu metadata.
84    list_get: fn(&S, usize, usize) -> Option<V>,
85    // Remove element at position.
86    list_remove: fn(&mut S, usize, usize) -> Option<V>,
87    // Insert element at position.
88    list_insert: fn(&mut S, usize, usize, V),
89    // Variable name for notifications.
90    variable_name: &'static str,
91    // Entity descriptor index.
92    descriptor_index: usize,
93    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
94}
95
96enum ListChangeStage {
97    Intra,
98    Inter,
99}
100
101pub struct ListChangeMoveCursor<S, V>
102where
103    S: PlanningSolution,
104    V: Clone + PartialEq + Send + Sync + Debug + 'static,
105{
106    store: CandidateStore<S, ListChangeMove<S, V>>,
107    entities: Vec<usize>,
108    route_lens: Vec<usize>,
109    context: MoveStreamContext,
110    src_idx: usize,
111    src_pos_offset: usize,
112    stage: ListChangeStage,
113    intra_dst_offset: usize,
114    dst_idx: usize,
115    inter_dst_pos_offset: usize,
116    list_len: fn(&S, usize) -> usize,
117    list_get: fn(&S, usize, usize) -> Option<V>,
118    list_remove: fn(&mut S, usize, usize) -> Option<V>,
119    list_insert: fn(&mut S, usize, usize, V),
120    variable_name: &'static str,
121    descriptor_index: usize,
122}
123
124impl<S, V> ListChangeMoveCursor<S, V>
125where
126    S: PlanningSolution,
127    V: Clone + PartialEq + Send + Sync + Debug + 'static,
128{
129    #[allow(clippy::too_many_arguments)]
130    fn new(
131        entities: Vec<usize>,
132        route_lens: Vec<usize>,
133        context: MoveStreamContext,
134        list_len: fn(&S, usize) -> usize,
135        list_get: fn(&S, usize, usize) -> Option<V>,
136        list_remove: fn(&mut S, usize, usize) -> Option<V>,
137        list_insert: fn(&mut S, usize, usize, V),
138        variable_name: &'static str,
139        descriptor_index: usize,
140    ) -> Self {
141        Self {
142            store: CandidateStore::new(),
143            entities,
144            route_lens,
145            context,
146            src_idx: 0,
147            src_pos_offset: 0,
148            stage: ListChangeStage::Intra,
149            intra_dst_offset: 0,
150            dst_idx: 0,
151            inter_dst_pos_offset: 0,
152            list_len,
153            list_get,
154            list_remove,
155            list_insert,
156            variable_name,
157            descriptor_index,
158        }
159    }
160
161    fn current_source(&self) -> Option<(usize, usize, usize)> {
162        let src_entity = *self.entities.get(self.src_idx)?;
163        let src_len = self.route_lens[self.src_idx];
164        if src_len == 0 {
165            return Some((src_entity, src_len, 0));
166        }
167        let src_pos = ordered_index(
168            self.src_pos_offset,
169            src_len,
170            self.context,
171            0x1157_C4A4_6E00_0002 ^ src_entity as u64 ^ self.descriptor_index as u64,
172        );
173        Some((src_entity, src_len, src_pos))
174    }
175
176    fn advance_source_position(&mut self) {
177        self.src_pos_offset += 1;
178        self.stage = ListChangeStage::Intra;
179        self.intra_dst_offset = 0;
180        self.dst_idx = 0;
181        self.inter_dst_pos_offset = 0;
182
183        while self.src_idx < self.route_lens.len()
184            && self.src_pos_offset >= self.route_lens[self.src_idx]
185        {
186            self.src_idx += 1;
187            self.src_pos_offset = 0;
188        }
189    }
190
191    fn push_move(
192        &mut self,
193        src_entity: usize,
194        src_pos: usize,
195        dst_entity: usize,
196        dst_pos: usize,
197    ) -> CandidateId {
198        self.store.push(ListChangeMove::new(
199            src_entity,
200            src_pos,
201            dst_entity,
202            dst_pos,
203            self.list_len,
204            self.list_get,
205            self.list_remove,
206            self.list_insert,
207            self.variable_name,
208            self.descriptor_index,
209        ))
210    }
211}
212
213impl<S, V> MoveCursor<S, ListChangeMove<S, V>> for ListChangeMoveCursor<S, V>
214where
215    S: PlanningSolution,
216    V: Clone + PartialEq + Send + Sync + Debug + 'static,
217{
218    fn next_candidate(&mut self) -> Option<CandidateId> {
219        loop {
220            let (src_entity, src_len, src_pos) = self.current_source()?;
221            if src_len == 0 {
222                self.src_idx += 1;
223                continue;
224            }
225
226            match self.stage {
227                ListChangeStage::Intra => {
228                    while self.intra_dst_offset < src_len {
229                        let dst_pos = ordered_index(
230                            self.intra_dst_offset,
231                            src_len,
232                            self.context,
233                            0x1157_C4A4_6E00_0003 ^ src_entity as u64 ^ src_pos as u64,
234                        );
235                        self.intra_dst_offset += 1;
236                        if src_pos == dst_pos || dst_pos == src_pos + 1 {
237                            continue;
238                        }
239                        return Some(self.push_move(src_entity, src_pos, src_entity, dst_pos));
240                    }
241                    self.stage = ListChangeStage::Inter;
242                    self.dst_idx = 0;
243                    self.inter_dst_pos_offset = 0;
244                }
245                ListChangeStage::Inter => {
246                    while self.dst_idx < self.entities.len() {
247                        if self.dst_idx == self.src_idx {
248                            self.dst_idx += 1;
249                            self.inter_dst_pos_offset = 0;
250                            continue;
251                        }
252                        let dst_entity = self.entities[self.dst_idx];
253                        let dst_len = self.route_lens[self.dst_idx];
254                        if self.inter_dst_pos_offset <= dst_len {
255                            let dst_pos = ordered_index(
256                                self.inter_dst_pos_offset,
257                                dst_len + 1,
258                                self.context,
259                                0x1157_C4A4_6E00_0004
260                                    ^ src_entity as u64
261                                    ^ dst_entity as u64
262                                    ^ src_pos as u64,
263                            );
264                            self.inter_dst_pos_offset += 1;
265                            return Some(self.push_move(src_entity, src_pos, dst_entity, dst_pos));
266                        }
267                        self.dst_idx += 1;
268                        self.inter_dst_pos_offset = 0;
269                    }
270                    self.advance_source_position();
271                }
272            }
273        }
274    }
275
276    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListChangeMove<S, V>>> {
277        self.store.candidate(id)
278    }
279
280    fn take_candidate(&mut self, id: CandidateId) -> ListChangeMove<S, V> {
281        self.store.take_candidate(id)
282    }
283}
284
285impl<S, V> Iterator for ListChangeMoveCursor<S, V>
286where
287    S: PlanningSolution,
288    V: Clone + PartialEq + Send + Sync + Debug + 'static,
289{
290    type Item = ListChangeMove<S, V>;
291
292    fn next(&mut self) -> Option<Self::Item> {
293        let id = self.next_candidate()?;
294        Some(self.take_candidate(id))
295    }
296}
297
298impl<S, V: Debug, ES: Debug> Debug for ListChangeMoveSelector<S, V, ES> {
299    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
300        f.debug_struct("ListChangeMoveSelector")
301            .field("entity_selector", &self.entity_selector)
302            .field("variable_name", &self.variable_name)
303            .field("descriptor_index", &self.descriptor_index)
304            .finish()
305    }
306}
307
308impl<S, V, ES> ListChangeMoveSelector<S, V, ES> {
309    /// Creates a new list change move selector.
310    ///
311    /// # Arguments
312    /// * `entity_selector` - Selects entities to consider for moves
313    /// * `list_len` - Function to get list length for an entity
314    /// * `list_remove` - Function to remove element at position
315    /// * `list_insert` - Function to insert element at position
316    /// * `variable_name` - Name of the list variable
317    /// * `descriptor_index` - Entity descriptor index
318    pub fn new(
319        entity_selector: ES,
320        list_len: fn(&S, usize) -> usize,
321        list_get: fn(&S, usize, usize) -> Option<V>,
322        list_remove: fn(&mut S, usize, usize) -> Option<V>,
323        list_insert: fn(&mut S, usize, usize, V),
324        variable_name: &'static str,
325        descriptor_index: usize,
326    ) -> Self {
327        Self {
328            entity_selector,
329            list_len,
330            list_get,
331            list_remove,
332            list_insert,
333            variable_name,
334            descriptor_index,
335            _phantom: PhantomData,
336        }
337    }
338}
339
340impl<S, V, ES> MoveSelector<S, ListChangeMove<S, V>> for ListChangeMoveSelector<S, V, ES>
341where
342    S: PlanningSolution,
343    V: Clone + PartialEq + Send + Sync + Debug + 'static,
344    ES: EntitySelector<S>,
345{
346    type Cursor<'a>
347        = ListChangeMoveCursor<S, V>
348    where
349        Self: 'a;
350
351    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
352        self.open_cursor_with_context(score_director, MoveStreamContext::default())
353    }
354
355    fn open_cursor_with_context<'a, D: Director<S>>(
356        &'a self,
357        score_director: &D,
358        context: MoveStreamContext,
359    ) -> Self::Cursor<'a> {
360        let mut selected =
361            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
362        selected.apply_stream_order(
363            context,
364            0x1157_C4A4_6E00_0001 ^ self.descriptor_index as u64,
365        );
366        ListChangeMoveCursor::new(
367            selected.entities,
368            selected.route_lens,
369            context,
370            self.list_len,
371            self.list_get,
372            self.list_remove,
373            self.list_insert,
374            self.variable_name,
375            self.descriptor_index,
376        )
377    }
378
379    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
380        collect_selected_entities(&self.entity_selector, score_director, self.list_len)
381            .list_change_move_capacity()
382    }
383}
solverforge_solver/heuristic/selector/list_change.rs

solverforge_solver/heuristic/selector/
list_change.rs
